Indexes And Small Tables Part IV (Treefingers)

As I asked in my previous post, the key question when comparing the associated costs of accessing a small table via a Full Table Scan (FTS) vs. an index scan is why does Oracle visit the segment header during a FTS but not during an index scan ?

The answer all comes down to understanding why Oracle must visit the table segment header during a FTS and how Oracle can avoid visiting the index segment header during an index scan.

Oracle must visit the table segment header during a FTS because it contains vital information necessary to perform the FTS, namely the extent map and the High Water Mark (HWM) associated with the table. Even with a table that only contains 1 data block worth of rows as in the SMALL table in my examples, Oracle has no way of automatically determining there’s actually only just the one block worth of data. It has to somehow look that up and determine exactly what table blocks Oracle needs to access during the FTS operation and the table segment header contains this necessary meta data. During “most” FTS operations, which are generally speaking larger, “expensive” operations, these accesses to the table segment header constitute a relatively small overhead. However, for FTS operations on “small” tables, accessing the table segment header can actually be a significant proportion of the overall associated costs.

During an index scan operation, there’s nothing of interest within the index segment header. The critical index block, the index block by which all index scans must start is the root block of the index (except Fast Full Index Scans which are basically the FTS equivalent for indexes). There’s no need to access the index segment header because it’s the root block that actually contains all the necessary information by which to start the index scan operation. The root blocks contains the pointers to subsequent index blocks (be it a branch or leaf blocks) that Oracle needs to follow in order to find the index entry of interest. The key to starting an index scan therefore is in determining the location of the index root block.

But how can Oracle determine the location of the index root block ?

Well Oracle implements a little “trick”, a golden rule with regard to indexes that doesn’t change regardless of the Oracle version, regardless of the O/S version, regardless of the type of tablespace or tablespace option of the index and regardless of how the index is created or grows and block splits over time.

The index root block is always, always, always the block immediately after the index segment header.

Always.

Therefore, when the Oracle code issues the associated function calls to perform an index scan, the first index block that Oracle assesses is the index segment header plus an offset of 1. Whereas a FTS accesses the table segment header, an index scan accesses the index segment block id plus 1.

With a tiny index that only has a level of 0 (or height of 1), note there is not “root” block as such as all the index entries can fit within one index leaf block. However, this block, this one and only leaf block within the index structure is also always the block immediately after the index segment header.

Always.

When we add more index entries into this one and only leaf block, we’ll eventually reach a point when it’s full and Oracle must perform an index block split operation. Oracle will then allocate 2 new blocks to the index. Assuming a 50-50 block split, one of these new blocks is assigned the lower 1/2 of all the current index entry values and the other new block is assigned the other upper 1/2 of the current index entry values. The original index leaf block content is then cleaned out and reassigned with just relative block address pointers and value boundaries associated with the 2 new leaf blocks.

The original index leaf block has been “reborn” as the root block of the index.

It’s quite easy to demonstrate how the original index block in a level 0 index or the root block of an index never changes and is always the block that follows the index segment header.

First, just create a little table and associated index:

SQL> CREATE TABLE same_root (id NUMBER, name VARCHAR2(30));

Table created.

SQL> INSERT INTO same_root VALUES (1, ‘The Thin White Duke’);

1 row created.

SQL> COMMIT;

Commit complete.

SQL> CREATE INDEX same_root_i ON same_root(name);

Index created.

If we dump the block immediately following the index segment header, we can confirm it’s our index block of interest, containing our one and only index entry:

SQL> select header_file, header_block from dba_segments where segment_name=’SAME_ROOT_I’;

HEADER_FILE HEADER_BLOCK
----------- ------------
          5       107441

SQL> alter system dump datafile 5 block 107442;

System altered.

Following is an extract of the index block dump:

Leaf block dump
===============
header address 98959964=0x5e6025c
kdxcolev 0
KDXCOLEV Flags = – – –
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0x26
kdxcofeo 8007=0x1f47
kdxcoavs 7969
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8036
row#0[8007] flag: ——, lock: 0, len=29
col 0; len 19; (19):  54 68 65 20 54 68 69 6e 20 57 68 69 74 65 20 44 75 6b 65
col 1; len 6; (6):  01 41 a3 aa 00 00
—– end of leaf block dump —–

Note that it is indeed our one and only index leaf block.

If we now take a treedump of the index:

SQL> SELECT object_id FROM dba_objects where object_name = ‘SAME_ROOT_I’;

 OBJECT_ID
----------
     67721

SQL> ALTER SESSION SET EVENTS ‘immediate trace name treedump level 67721’;

Session altered.

 

Following is the treedump output:

—– begin tree dump
leaf: 0x141a3b2 21078962(0: nrow: 1 rrow: 1)
—– end tree dump

We note that the relative block address of our one and only index leaf block is 21078962.

If we now add a whole bunch of new rows to the table so that the leaf block can no longer hold all the index entries, thereby forcing the index to block split and grow:

SQL> insert into same_root select rownum+1, ‘David Bowie’ from dual connect by level <=100000;

100000 rows created.

SQL> commit;

Commit complete.

And now take a block dump of the same index block:

SQL> alter system dump datafile 5 block 107442;

System altered.

Branch block dump
=================
header address 98959940=0x5e60244
kdxcolev 2
KDXCOLEV Flags = – – –
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 2
kdxconro 2
kdxcofbo 32=0x20
kdxcofeo 8016=0x1f50
kdxcoavs 7984
kdxbrlmc 21238606=0x144134e
kdxbrsno 1
kdxbrbksz 8060
kdxbr2urrc 0
row#0[8038] dba: 21238607=0x144134f
col 0; len 11; (11):  44 61 76 69 64 20 42 6f 77 69 65
col 1; len 5; (5):  01 41 be 5f 01
row#1[8016] dba: 21238769=0x14413f1
col 0; len 11; (11):  44 61 76 69 64 20 42 6f 77 69 65
col 1; len 5; (5):  01 44 12 ba 01
—– end of branch block dump —–

We notice that the block is no longer a leaf block but has changed itself into an index branch block.

But not just any branch block. If we now take a new treedump:

SQL> ALTER SESSION SET EVENTS ‘immediate trace name treedump level 67721’;

Session altered.

branch: 0x141a3b2 21078962(0: nrow: 3, level: 2)
   branch: 0x144134e 21238606 (-1: nrow: 161, level: 1)
      leaf: 0x141a3b3 21078963 (-1: nrow: 179 rrow: 179)
      leaf: 0x141a3b4 21078964 (0: nrow: 179 rrow: 179)
      leaf: 0x141a3b5 21078965 (1: nrow: 179 rrow: 179)
      leaf: 0x141a3b6 21078966 (2: nrow: 179 rrow: 179)
      leaf: 0x141a3b7 21078967 (3: nrow: 179 rrow: 179)

….

The above partial listing of the treedump clearly shows that the index has grown from a level 0 index to a level 2 index and that the root block is the very same index block as the original leaf block listed as it has the same relative block address as before (21078962).

Indeed the original leaf block is now the index root block which is still the same block that immediately follows the index segment header.

Because Oracle doesn’t have to visit the index segment header and can simply directly access the block following the index segment header as this block is always the first index block of interest when performing an index scan, the index scan has that little advantage over the FTS. And it’s this little advantage that can give the index scan the edge over a FTS, even if we’re potentially accessing data from a very small table.

And you can’t get much smaller than a table that has all it’s rows in the one table block.

So far though, the example I’ve shown has been a “normal”, everyday, non-unique index that has a 1 consistent get advantage over the FTS when accessing a row of interest. I’ll next discuss how indexes can having an even bigger edge and more significant advantage over a FTS of a tiny table,  than just the 1 consistent get …