Mysql – How DB index works internally at high level

indexMySQL

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 ?

Best Answer

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.

Related Question