17 May, 2009

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.

.
.
.

12 comments:

Timur Akhmadeev said...

Hermant,

>An Index is an ordered structure
*logically* ordered structure. Rows in an index block physically are not ordered (that would make painful order maintenance), but they are ordered logically via row directory.

Hemant K Chitale said...

Agreed. I've updated the line.

Towards the end, I did put in '...to the "last" Leaf Block, although "last" isn't accurate in the sense of physical location'
to state that the ordering is'nt physical.

Anonymous said...

Hi,

Good one. Learned about "leaf node 90-10 splits" statistic.

However, when a 90-10 split takes place, how'come the index blocks are 100 percent used? They all should be 90% used (although PCTFREE = 1%). Isnt' it?

Dan

Hemant K Chitale said...

PCTFREE is used only at CREATE time. After that, it is ignored.
Richard Foote prefers to call such splits 99-1 because only the "highest" Key Value goes to the new block. Therefore, the index can well be 100% full.

Even if you run the test case with PCTFREE of 10, you'd still get the index leaf blocks 100% full.

Log Buffer said...

"Hemant K Chitale examines 90-10 Index Block Splits and their possible causes. [...]"

Log Buffer #147

LIU GaoYuan said...

I have recently encountered another performance issue with an INSERT statement. From the dumped output, the three physical IOs are from one index, one is a branch block, and the other two are leaf blocks, the index is based on one sample_date. I think I will have encountered this 90-10 split. The database is Oracle 9.2.0.4, and I do see "leaf node 90-10 splits" in the session statistics?

Hemant K Chitale said...

GaoYuan,

Ah ! OK. Thanks. I've updated my post to indicate that you do find this statistic reported in your 9.2.0.4 environment.

Hemant

vineeth said...

Hemant,

i got different leaf nod splits after the second insert.tested in 11.2, tablespace with ASSM, 8k block size

leaf node 90-10 splits 404
leaf node splits 415

Regards,
Vineeth

Hemant K Chitale said...

Proliant,
You must have had very much higher number of leaf blocks to achieve that many block splits. Check your leaf block count. I had 263 at the end of the first round and 268 at the end of the second round.
Also, confirm that you are not reporting cumulative statistics -- I reset the counters for the session statistics by creating a new session each time.

Hemant

Anonymous said...

Hi Hemant,
what happens with a partitioned table with local indexes and the older partitions gets dropped.

Also, what happens if the index is reverse key index ?

Hemant K Chitale said...

Anonymous,
Apologies for the delay in the reply.

1. A LOCALly partitioned index has one partition for each Table Partition. If you DROP a Table Partition, the correspondig Index Partition is automatically dropped. (A GLOBAL index has to be UPDATEd).

2. Even a Reverse Key Index will suffer Block Splits. Conducting a thought experiment -- which I shall attempt to validate -- I imagine that 50-50 splits would occur.

Hemant

Hemant K Chitale said...

Anonymous,
See my latest post (of 20-Feb-11) on Index Block Splits with a REVERSE KEY Index.

Hemant