How DB index works internally at high level?

Question

I have around 500 GB of data in one table of MySQL which has around 5 billion records. It has around 15 columns. It has index on all the required columns. When I do select * from big_table where index_column = some_value it takes couple of minutes to return the data.

I am not sure how indexing works internally here.Here is my understanding

1. DB vendor will bring indexed column complete(not just data in where clause) data in memory first
2. Find the values(in where clause) under data fetched in step_1 to get the record row location in actual table.
3. Then another IO call will go to disk to get all required data based on row location fetched in step_2

Is that correct ? I am not sure on first step i.e. whether complete data of indexed column is fetched in memory or values are searched on disk itself without bringing the complete data in memory ?

Answer 1

This is an example for Db2, so a number of details will differ if you use another DBMS, but in general, it will look pretty much the same. Lets create a sample table:

create table test 
( x int not null generated always as identity
, y int not null
, z int not null
);

create unique index testix on test (x);
insert into test (y,z) 
with t(n,m) as ( 
    values (0, rand()) 
    union all 
    select n+1, rand() 
    from t where n<100000
) select 10000*m, 1000*m from t;

So, we have a table with 100000 rows. Let's examine the unique index, before we add any data we will have just the root node:

select nlevels, nleaf from syscat.indexes where indname = 'TESTIX'

NLEVELS NLEAF               
1       1

NLEVELS is the height of the tree, and NLEAF are the number of leaf-pages. After adding data:

NLEVELS NLEAF               
2       206

So we have a tree that in ASCII-art looks something like:

1         R
2   ... / | \ ...

The 206 leaf-pages address all data in the table. If we look at the plan for a query like:

select * from test where x = 1234

it will look like:

                Rows 
              RETURN
              (   1)
               Cost 
                I/O 
                |
                 1 
              FETCH 
              (   2)
              13.637 
                 2 
           /----+-----\
          1           100001 
       IXSCAN   TABLE:    LELLE   
       (   3)          TEST
       6.82834          Q1
          1 
         |
       100001 
 INDEX:    LELLE   
       TESTIX
         Q1

But what information did we touch to achieve this?

select num_executions, rows_read, pool_data_l_reads, pool_data_p_reads, pool_index_l_reads, pool_index_p_reads 
from sysibmadm.snapdyn_sql 
where stmt_text = 'select * from test where x = 1234'

NUM_EXECUTIONS       ROWS_READ            POOL_DATA_L_READS    POOL_DATA_P_READS    POOL_INDEX_L_READS   POOL_INDEX_P_READS  
-------------------- -------------------- -------------------- -------------------- -------------------- --------------------
                   1                   16                   35                   12                   66                   30

• ROWS_READ (16) is the number of rows (data) that we accessed for this query
• POOL_DATA_L_READS (35) is the number of pages read from memory for data

• POOL_DATA_P_READS (12) is the number of pages that could not be found in memory and had to be read from disk. In any normal situation, 1 logical read results in 0 or 1 physical reads.

• POOL_INDEX_L_READS (66) is the number of pages read from memory for index

• POOL_INDEX_P_READS (30) is the number of pages that could not be found in memory and had to be read from disk

So, even with this minimal amount of data in the table we only touch a fraction of pages (66) compared with the total number of pages (206+intermediate pages) for indexes.

In general, a read from the index will be a walk down the tree choosing a path at each new level.

Answer 2

Nothing is ever "searched on disk"; "search" means comparing one thing to another, and both things must reside in RAM for that. From here it's up to the buffer pool management strategy implemented by a particular DBMS. It might choose to read the entire index into memory (buffer pool) if a) there's enough memory and b) it expects to scan a relatively large portion of the index. A simple unique key lookup will load individual index pages (if they aren't already present in the buffer, that is).

Answer 3

select * from big_table where index_column = some_value
INDEX(index_column)

Here's how it works. But I will assume, for the sake of argument, that you will be fetching 300 rows. I will count the likely disk hits as a good way to estimate the query time for a huge table.

1. In the BTree for INDEX(index_column), drill down to the first (if any) row with value some_value. The BTree will be about 5 levels deep. You may have the necessary non-leaf nodes in InnoDB's buffer_pool, so I won't count them as disk hits.
2. But the leaf node(s) needed may not be cached, so I will count them. This will be about 4 blocks. (Rule of Thumb = 100 records per block; 300/100 = 3, but probably not aligned, so 4 is a good number.
3. Scan through the 300 index entries.
4. If the index is very random (eg UUID), then the entries will point to lots of random places in the data. If it is not random at all but tracks the PRIMARY KEY, then the 300 might be consecutive in the data. A secondary key (in InnoDB) contains a copy of the PRIMARY KEY column value(s).
5. So, now we do the SELECT *, which involves fetching the 300 rows from the data BTree using the PRIMARY KEY. We will get all the columns (*) This will be anywhere from 4 (see above) and 300 disk hits to get to the 300 rows. Actually, there will also be the necessary non-leaf node BTree nodes, but I won't count them.

Total:

Index range scan:  4 blocks
Data lookup via PK:  4-300

Total: 8-304 disk hits. If you have a spinning drive, then assume 10ms per disk hit (another Rule of Thumb). Time: 80 ms to 3 seconds.

Note: Each block of index or data is 16KB and is independently "cached" in the buffer_pool. No table or index is "completely" loaded into RAM; its blocks come and go on (roughly) a "least recently used" basis.

So, your test took "a couple of minutes"? Are you are fetching about 12000 randomly located rows??

You are using InnoDB? Nothing else was running at the same time? (Some things may interfere.)

Another thing that will take a lot of extra disk hits: If you have some TEXT or BLOB columns, and if they are stored "off-record", then each one of them is another disk hit. You should really provide SHOW CREATE TABLE.

You say "It has index on all the required columns." -- A "composite" index? Is the index_column the first column in such? If not, then much of what I said does not apply.