Curious Case Of The Ever Increasing Index Quiz (She’ll Drive The Big Car)

I received an email recently that had a nice example of what can potentially go wrong with an index.

Let’s first create a simple table with a unique index and populate it with 200,000 rows (following demo run on 11.2.0.1):

SQL> create table bowie (id number constraint bowie_pk primary key, name varchar2(100));

Table created.

SQL> insert into bowie select rownum, 'BOWIE' from dual connect by level <= 200000;

200000 rows created.

SQL> commit;

Commit complete.

SQL> analyze index bowie_pk validate structure;

Index analyzed.

SQL> select name, height, lf_rows, del_lf_rows, lf_blks, br_blks from index_stats;

NAME             HEIGHT    LF_ROWS DEL_LF_ROWS    LF_BLKS    BR_BLKS
------------ ---------- ---------- ----------- ---------- ----------
BOWIE_PK              2     200000           0        374          1

So far, everything is as expected. With have an index with 200,000 rows that currently has 374 leaf blocks.

OK, what we want to do is basically gradually delete the current set of rows and replace them with 200,000 new rows, with ever-increasing Primary Key values. To this end, we create the following procedure:

SQL> create or replace procedure delete_insert_rows
  2  as
  3       n number;
  4       m number;
  5  begin
  6       select min(id),max(id) into n,m from bowie;
  7       for i in 1..200000 loop
  8           delete from bowie where id=n+i-1;
  9           insert into bowie values(m+i,'David Bowie');
 10           if (i mod 1000=0) then
 11                commit;
 12           end if;
 13       end loop;
 14       commit;
 15  end;
 16  /

Procedure created.

So the procedure basically determines the current MIN and MAX values of our PK column and gradually deletes the current rows and then inserts new ones. Every 1000 iterations, we commit the changes. Nothing too complex here.

When we run this procedure for the first time:

SQL> exec delete_insert_rows

PL/SQL procedure successfully completed.

SQL> analyze index bowie_pk validate structure;

Index analyzed.

SQL> select name, height, lf_rows, del_lf_rows, lf_blks, br_blks from index_stats;

NAME             HEIGHT    LF_ROWS DEL_LF_ROWS    LF_BLKS    BR_BLKS
------------ ---------- ---------- ----------- ---------- ----------
BOWIE_PK              2     293820       93820        619          1

We notice we now have a whole bunch of deleted leaf entries and that the index has grown from 374 to 619 leaf blocks.

If we run the procedure again:

SQL> exec delete_insert_rows

PL/SQL procedure successfully completed.

SQL> analyze index bowie_pk validate structure;

Index analyzed.

SQL> select name, height, lf_rows, del_lf_rows, lf_blks, br_blks from index_stats;

NAME             HEIGHT    LF_ROWS DEL_LF_ROWS    LF_BLKS    BR_BLKS
------------ ---------- ---------- ----------- ---------- ----------
BOWIE_PK              3     347841      147841        994          3

Things have gone even worse. We still only have 200,000 rows in the table but the index now has an additional 147,841 deleted entries and the number of leaf blocks has again increased substantially to 994 leaf blocks.

If we have a look at a partial treedump of the index:

SQL> select object_id from dba_objects where object_name = 'BOWIE_PK';

 OBJECT_ID
----------
     74060

SQL> alter session set events 'immediate trace name treedump level 74060';

Session altered.

—– begin tree dump
branch: 0x100378b 16791435 (0: nrow: 2, level: 2)
   branch: 0x1003ce0 16792800 (-1: nrow: 733, level: 1)
      leaf: 0x100378e 16791438 (-1: nrow: 149 rrow: 0)
      leaf: 0x100378f 16791439 (0: nrow: 571 rrow: 0)
      leaf: 0x100378c 16791436 (1: nrow: 291 rrow: 0)
      leaf: 0x1003795 16791445 (2: nrow: 571 rrow: 0)
      leaf: 0x1003796 16791446 (3: nrow: 433 rrow: 0)
      leaf: 0x1003797 16791447 (4: nrow: 4 rrow: 0)
      leaf: 0x1003790 16791440 (5: nrow: 571 rrow: 0)
      leaf: 0x1003791 16791441 (6: nrow: 146 rrow: 0)
      leaf: 0x1003792 16791442 (7: nrow: 571 rrow: 0)
      leaf: 0x1003793 16791443 (8: nrow: 288 rrow: 0)
      leaf: 0x1003794 16791444 (9: nrow: 571 rrow: 0)
      leaf: 0x10037a9 16791465 (10: nrow: 430 rrow: 0)

… (most of the treedump has been cut out, following is the last portion of the dump)

  
     leaf: 0x1003e70 16793200 (248: nrow: 533 rrow: 533)
      leaf: 0x1003e74 16793204 (249: nrow: 533 rrow: 533)
      leaf: 0x1003e78 16793208 (250: nrow: 533 rrow: 533)
      leaf: 0x1003e7c 16793212 (251: nrow: 533 rrow: 533)
      leaf: 0x1003e41 16793153 (252: nrow: 533 rrow: 533)
      leaf: 0x1003e45 16793157 (253: nrow: 533 rrow: 533)
      leaf: 0x1003e49 16793161 (254: nrow: 533 rrow: 533)
      leaf: 0x1003e4d 16793165 (255: nrow: 533 rrow: 533)
      leaf: 0x1003e51 16793169 (256: nrow: 533 rrow: 533)
      leaf: 0x1003e3e 16793150 (257: nrow: 533 rrow: 533)
      leaf: 0x1003e03 16793091 (258: nrow: 533 rrow: 533)
      leaf: 0x1003e07 16793095 (259: nrow: 236 rrow: 236)
—– end tree dump

We notice that the first portion of the index contains leaf blocks with nothing but deleted index entries. The number of rrows is 0 for a vast number of leaf blocks. We also notice that the root block has a rba of 0x100378b 16791435, which is only a few values below some of the rba values of the left most indexes in the index structure (say) 0x100378e 16791438. Therefore, this highlights that even though these left most blocks in the index structure contain nothing but deleted index entries, Oracle is not recycling them as it should do. Oracle is simply adding new blocks to the index structure rather than recycling empty leaf blocks, resulting in the index growing bigger and bigger.

The leaf blocks however at the right most end of the index structure (the second portion of the partial treedump), shows us a nice compact set of leaf blocks with lots of index entries per block (most with 533 per leaf block) and with no deleted index entries (rrows matches the nrows value). 

If we run the procedure 10 times in total, we get an index that looks like the following:

SQL> select name, height, lf_rows, del_lf_rows, lf_blks, br_blks from index_stats;

NAME             HEIGHT    LF_ROWS DEL_LF_ROWS    LF_BLKS    BR_BLKS
------------ ---------- ---------- ----------- ---------- ----------
BOWIE_PK              3    1325132     1125132       4136          7

We now have 1,125,132 deleted index entries and the index is now over 10 times the original size, up from 374 to a massive 4,136 leaf blocks, even though the table only contains 200,000 rows.

There are a number of contributing factors here 🙂

The question is why, why is the index behaving in this fashion and what can we do to ensure the index doesn’t grow in this manner and can remain basically the same size as we delete and insert new rows into the table ?