How indexes
make a database
read faster?
How makes
indexing your
DB faster
Database collection of records
'
is a .
users
id name
age bio total -
blogs
I 1 I 1 I 1 1 11 I
413 6013 413 12813 413
I 1
20013
Users table has 5 columns and each record of the
table will be 20013
long .
Say the users table has 100 crows
total size = 200×100 = 2000013
Users
id name age bio total - biog
1 A 23 7
2 13 21 10
3 C 22 8
4 D 23 2
1
5 E 22
6 F 24 15
: : : : :
Bytes Scuant to read
I
How reads
from disk happen ?
One disk read = one block read ¥
60GB Block 1 Block 2 Block 3 Block 4
60013 60013 60013 60013
Even if we read one byte it will read
,
in
the entire block that contains the Entire block is read
byte
Each record is 20013
Users table in blocks
-
Block size is 60013
id name age bio total - blogs
}
1 A 23 7
Each block can
2 B 21 10
hold 3 records
3 C 22 8 =
}
4 D 23 2
1
5 E 22
6 F 24 15
: : : : :
'
'
The entire users
having 10090ms
can
fit in
103-0=33.3
~ 34 Blocks
Block 's Block 2 Block 3 Block 4
60013 60013 60013 60013
So the entire table
,
reading will require
34 Blocks the disk
the database
engine
to read
from .
If hypothetically Read 1 Block takes 1sec
time to read entire table = 34sec .
Query : Find all users with
age
== 23
id name age bio total - biog
1 A 23 7
2 13 21 10
3 C 22 8
4 D 23 2
I
5 E 22
6 F 24 15
| f "
. -
: : : : :
Flow :
iterate table now by row Time taken to answer this
block by block is same time taken
query as
read the block in to read the blocks
memory
check age = -23
-
on each record
add the 34 blocks 34sec
if yes ,
record to an output buffer =
if no ,
discard
return the
output buffer
lets see how indexes make this fast . . .
Indexes
Indexes are smaller referential tables On a
very high level
that holds roue
references against µ
the indexed value
'
'
Eg Say we create index
: an on
age
it look like this
would
something
users idx
-
age .
Each
entry in index is
age id 413 -1 413=813
=
big
21 2 £ I
A
3 id
ordered 22
age
22 5
the
by
I
indexed 23
value 23 4 There will be 100 entries in the
6 index total
24 ,
so size
of index
8×100
'
i. : will be = 80013
=
One disk block = 60013
So index will require 2 blocks
,
only
on the disk .
Query : Find all users with
age
== 23 with index
Flow :
}
iterate index ( worst case
complete index )
block by block Read the index and
check age = -23
-
in entries note the relevant ids
' '
if yes ,
add the id in a
buffer matching criteria
if no ,
discard
}
for all the relevant id in the
buffer for the relevant ids
read the recordsfrom the dist
fetch the actual records
add to an
output buffer from the disk
return the output buffer
let's walk through on our data 2 example
id the relevant
age To find ids ,
21 2
y
ordered 22 3 We read the index
5
by the 22
and filter out relevant ids
23 I *
indexed
23 4 * Blocks read
value = 2
24 6 T
÷
'
: worst case
Relevant IDs with 23 are [ 1,4 ]
age
__ =
Users table in blocks
id name age bio total - biog
}
1 A 23 7
2 B 21 10
3 C 22 8
}
4 D 23 2
I
5 E 22
6 F 24 15
: : : : :
we need row ids 1 and 4
which Block 's 9
are
present in
Block 2 .
So , We read the Block 's Block 2 Block 's Block
60013 60013
two blocks the
60013 60013
from disk ,
extract the records and return
Blocks oread = 2
Total Blocks read = 2 + 2 → 4 block ~
4sec
( Index ) ( record /
}
Time take without index =
32sec 8x
with index = 4sec