Index Block Splits : 90-10

UPDATE 20-Feb-11 : I have also covered the case of a REVERSE KEY Index for the same data set.

An Index is a logically ordered structure. Unlike a Heap Organised Table (where a new row can, in theory, be inserted into any block that has free space), an Index can handle Inserts only by allowing each new Key Value to be inserted into the correct (leaf) block (and the correct position in that block).
{Note : Updates to Key Values are handled by "deleting" the old values and inserting the new values into the correct index leaf blocks appropriate for the new values}.

Let's say that we have an Index Key that is so long that only 4 values can fit into an Index Block. Let's further assume that the current Index (Leaf) Blocks contain these values :

Block 1 :
Abacus
Carrot

Block 2 :
Dandelion
Elephant
Heat
Iridium

Block 3 :
Lamb
Militant
Tight 

If we need to insert the new Key Value "Fear", then Oracle has to :
a. identify the correct Leaf Block (which is Block 2)
b. verify if the new value can be inserted into the block (between "Elephant" and "Heat")
c. insert the value if it can OR split the block into two blocks.

Since Oracle will have to split the block, it creates two Leaf Blocks, 2 and 3 and the erstwhile Block 3 becomes Block 4 :

Block 1 :
Abacus
Carrot

Block 2 :
Dandelion
Elephant

Block 3 :
Fear
Heat
Iridium

Block 4 :
Lamb
Militant
Tight 

(Oracle actually maintains pointers between the Leaf Blocks, so when it split Block 2, it had to update pointers to and from Blocks 2, 3 and 4).

This is a "normal" Leaf Block split, also known as a "50-50 split".

Howevever, a 90-10 split occurs when the new value is in the "right most" (ie highest Leaf Block). This is what occurs in an index on a "monotonically increasing" Key -- eg a Sequence (TRANSACTION_ID, JOURNAL_ID, ENTRY_ID etc) or a Date (TRANSACTION_DATE, JOURNAL_DATE, POSTING_DATE) where every new value inserted is larger than previous value.
In such a case, when Oracle splits the Leaf Block, it only copies the "right-most" (ie highest) value to the new Leaf Block.

The number of Index Leaf Block Splits has been available as "leaf node splits" in V$SYSSTAT / V$SESSTAT. The statistic "leaf node 90-10 splits" has been introduced in only recently -- in 10g but not in 9i. [UPDATE : 01-Dec-09 : Liu GaoYuan, in his comment, mentions that he does see this statistic in his 9.2.0.4 environment] However, even the 10.2 Reference Manual section on Statistics doesn't explain "leaf node 90-10 splits", only "leaf node splits".

When you see both statistics, remember that, since "leaf node 90-10 splits" has only recently appeared as a separate statistic, this is a subset of "leaf node splits". That is, "leaf node splits" accounts for both "50-50" and "90-10" splits.


In this example below, I create a demo table "demo_ibs_90_10" which could be an EMPLOYEE table. There 's a Unique Index on employee_id + country_nam e + employee_name. I've deliberately inserted fairly long employee names to enlarge the size of the Key so that not too many Key Values fit into one Leaf Block.

SQL> drop table demo_ibs_90_10 purge;

Table dropped.

SQL>
SQL> -- REM create the demo table
SQL> create table demo_ibs_90_10 (
2    employee_id  number not null,
3    country_name varchar2(10) not null,
4    dept_name varchar2(18) not null,
5    employee_name  varchar2(128) not null,
6    join_date  date)
7  /

Table created.

SQL>
SQL> -- create the index with a PCTFREE of 1 to pack it tightly
SQL> create unique index demo_ibs_90_10_u1 on demo_ibs_90_10 (employee_id,country_name,employee_name) pctfree 1;

Index created.

SQL> 

In the first Batched Insert of 50,653 rows, the Index "grows" to 263 Blocks incurring 262 "90-10 " splits along the way. Approximately 193 Key Values fit into each Leaf Block.

SQL> delete source_table;

50653 rows deleted.

SQL> insert into source_table select * from dba_objects where object_id is not null;

50653 rows created.

SQL> select max(object_id) from source_table;

MAX(OBJECT_ID)
--------------
   53214

SQL>
SQL>
SQL> -- REM create a new session and run an insert
SQL> -- then check the statistics for the insert
SQL> connect hemant/hemant
Connected.
SQL> insert into demo_ibs_90_10
2  select object_id, substr(owner,1,10),substr(object_type,1,18),rpad(object_name,20,dbms_random.string('X',3)),created
3  from source_table
4  where object_id is not null
5  order by object_id
6  /

50653 rows created.

SQL> commit;

Commit complete.

SQL>
SQL> select sn.name, ms.value
2  from v$statname sn, v$mystat ms
3  where sn.statistic#=ms.statistic#
4  and sn.name like '%leaf node %'
5  order by 1
6  /

NAME                                                                  VALUE
---------------------------------------------------------------- ----------
leaf node 90-10 splits                                                  262
leaf node splits                                                        262

SQL>
SQL> exec dbms_stats.gather_table_stats('','DEMO_IBS_90_10',estimate_percent=>100,cascade=>TRUE);

PL/SQL procedure successfully completed.

SQL> select num_rows, distinct_keys, blevel, leaf_blocks, distinct_keys/leaf_blocks
2  from user_indexes where index_name = 'DEMO_IBS_90_10_U1'
3  /

NUM_ROWS DISTINCT_KEYS     BLEVEL LEAF_BLOCKS DISTINCT_KEYS/LEAF_BLOCKS
---------- ------------- ---------- ----------- -------------------------
50653         50653          1         263                192.596958

SQL> analyze index demo_ibs_90_10_u1 validate structure;

Index analyzed.

SQL> select lf_rows, lf_blks, br_blks, del_lf_rows, pct_used from index_stats;

LF_ROWS    LF_BLKS    BR_BLKS DEL_LF_ROWS   PCT_USED
---------- ---------- ---------- ----------- ----------
50653        263          1           0        100

SQL>
SQL> REM  #################
SQL> REM  OBSERVATION !
SQL> REM  The first set of block creations are all from Block Splits.
SQL> REM  And all of these are 90-10 Splits !
SQL> REM  #################
SQL> 

In the second round, I insert 1 row in each of 1,000 transactions. This creates 5 new Leaf Blocks, all from 90-10 splits. (Remember that approximately 193 Values fit into 1 Leaf Block).

SQL> -- REM run another set of inserts
SQL> -- REM we now simulate a Row-By-Row Insert that would happen for creating new Employees
SQL> connect hemant/hemant
Connected.
SQL>
SQL> declare
2  i number;
3
4  begin
5  for i in 1..1000
6  loop
7  insert into demo_ibs_90_10
8  select object_id+100000+i,substr(owner,1,10),substr(object_type,1,18),rpad(object_name,20,dbms_random.string('X',3)),created+vsize(object_name)
9  from source_table
10  where object_id is not null
11  and object_id = 1000+i;
12  commit;
13  end loop;
14  end;
15  /

PL/SQL procedure successfully completed.

SQL>
SQL> select sn.name, ms.value
2  from v$statname sn, v$mystat ms
3  where sn.statistic#=ms.statistic#
4  and sn.name like '%leaf node %'
5  order by 1
6  /

NAME                                                                  VALUE
---------------------------------------------------------------- ----------
leaf node 90-10 splits                                                    5
leaf node splits                                                          5

SQL>
SQL> exec dbms_stats.gather_table_stats('','DEMO_IBS_90_10',estimate_percent=>100,cascade=>TRUE);

PL/SQL procedure successfully completed.

SQL> select num_rows, distinct_keys, blevel, leaf_blocks, distinct_keys/leaf_blocks
2  from user_indexes where index_name = 'DEMO_IBS_90_10_U1'
3  /

NUM_ROWS DISTINCT_KEYS     BLEVEL LEAF_BLOCKS DISTINCT_KEYS/LEAF_BLOCKS
---------- ------------- ---------- ----------- -------------------------
51653         51653          1         268                192.735075

SQL> analyze index demo_ibs_90_10_u1 validate structure;

Index analyzed.

SQL> select lf_rows, lf_blks, br_blks, del_lf_rows, pct_used from index_stats;

LF_ROWS    LF_BLKS    BR_BLKS DEL_LF_ROWS   PCT_USED
---------- ---------- ---------- ----------- ----------
51653        268          1           0        100

SQL>
SQL> 

In the final round, I insert another 1,000 rows, in a single Transaction. Again we see 90-10 splits to add 6 Leaf Blocks.

SQL> -- REM run another set of inserts
SQL> -- REM we now run a bulk insert again !
SQL> connect hemant/hemant
Connected.
SQL>
SQL> insert into demo_ibs_90_10
2  select object_id+200000,substr(owner,1,10),substr(object_type,1,18),rpad(object_name,20,dbms_random.string('X',3)),created+vsize(object_name)
3  from source_table
4  where object_id is not null
5  and object_id between 1000 and 2000
6  /

1001 rows created.

SQL>
SQL> commit;

Commit complete.

SQL>
SQL> select sn.name, ms.value
2  from v$statname sn, v$mystat ms
3  where sn.statistic#=ms.statistic#
4  and sn.name like '%leaf node %'
5  order by 1
6  /

NAME                                                                  VALUE
---------------------------------------------------------------- ----------
leaf node 90-10 splits                                                    6
leaf node splits                                                          6

SQL>
SQL> exec dbms_stats.gather_table_stats('','DEMO_IBS_90_10',estimate_percent=>100,cascade=>TRUE);

PL/SQL procedure successfully completed.

SQL> select num_rows, distinct_keys, blevel, leaf_blocks, distinct_keys/leaf_blocks
2  from user_indexes where index_name = 'DEMO_IBS_90_10_U1'
3  /

NUM_ROWS DISTINCT_KEYS     BLEVEL LEAF_BLOCKS DISTINCT_KEYS/LEAF_BLOCKS
---------- ------------- ---------- ----------- -------------------------
 52654         52654          1         274                192.167883

SQL> analyze index demo_ibs_90_10_u1 validate structure;

Index analyzed.

SQL> select lf_rows, lf_blks, br_blks, del_lf_rows, pct_used from index_stats;

LF_ROWS    LF_BLKS    BR_BLKS DEL_LF_ROWS   PCT_USED
---------- ---------- ---------- ----------- ----------
 52654        274          1           0        100

SQL> 

So, we find that adding new valus to an index on a monotonically increasing sequence always causes 90-10 Leaf Block splits.
What happens if there have been DELETEs in between ? Remember that Oracle can't insert new Key Values into "just any Leaf Block" even if it is 90% free. Therefore, new values for such a Key (monotonically increasing) will always go to the "right-end" of the B-Tree structure (ie to the "last" Leaf Block, although "last" isn't accurate in the sense of physical location). However, if all Key Values from an "older" Leaf Block have been deleted, then that Block is a candidate for re-use and it can be used as the "next" block after the "right-most" block (ie the one with the highest Key Value). It should be noted that this means that Index Leaf Blocks may well *not* be contiguous, even for a Key that is only increasing in value.


UPDATE 20-Feb-11 : I have also covered the case of a REVERSE KEY Index for the same data set.

Next, I will take up 50-50 Block Splits and demonstrate how they can cause an Index to grow faster than is the case with 90-10 splits, only because of the nature of the data and the pattern of inserts.

.
.
.