jump to navigation

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

Posted by Richard Foote in Index Internals, Indexing Myth, Oracle Indexes, Quiz.
trackback

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: 0×1003795 16791445 (2: nrow: 571 rrow: 0)
      leaf: 0×1003796 16791446 (3: nrow: 433 rrow: 0)
      leaf: 0×1003797 16791447 (4: nrow: 4 rrow: 0)
      leaf: 0×1003790 16791440 (5: nrow: 571 rrow: 0)
      leaf: 0×1003791 16791441 (6: nrow: 146 rrow: 0)
      leaf: 0×1003792 16791442 (7: nrow: 571 rrow: 0)
      leaf: 0×1003793 16791443 (8: nrow: 288 rrow: 0)
      leaf: 0×1003794 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 ?

About these ads

Comments»

1. Marcus Mönnig - January 4, 2012

We should regularly rebuild the index… Just kidding… I always wanted to say that… :-)

Given that we do not depend on index range scans or need the forward order in the index for the sorted order, using a reverse key index would eliminate the problem seen above.

Richard Foote - January 5, 2012

Hi Marcus

Indeed as the inserts will generally just use the same leaf blocks that contain some of the deleted entries. But the advantages would need to outweigh any of the disadvantages you’ve mentioned.

2. goryszewskigGregG - January 4, 2012

Hi,
as far I know when using unique index Oracle will reuse marked as deleted index slots even in the same transaction.
So maybe the problem is we are commiting every 1000 rows .
Just a wild guess .
Regards
GregG

Richard Foote - January 5, 2012

Hi Greg

They will only use the same slots in a unique index in the same transaction if the values are the same, which isn’t the case here. So in a unique index, the delete of an ID 42 followed by an insert of 42 would simply reuse the slot for 42, whereas in a Non-Unique index, an additional 42 index entry is created and the deleted entry remains.

3. Vyacheslav Rasskazov - January 4, 2012

I think, this is ASSM issue related to the lack of bitmap space management blocks maintenance through PL/SQL optimization. Switch to MSSM tablespace solves this problem.

Richard Foote - January 5, 2012

Hi Vyacheslav

Indeed :)

4. Raj Jamadagni - January 4, 2012

i wonder if you could delete/commit/insert (without harming business transaction integrity)? Current method of delete/insert means, oracle needs to account for a possible rollback of whole transaction.

Richard Foote - January 5, 2012

Hi Raj

This would certainly reduce some of the slippage in growth due to the deletes not being cleaned out within the same transaction. But it would be less efficient and indeed could stuff up or put at risk business integrity.

5. Ahmed AANGOUR - January 5, 2012

Is it because we have a PK? Maybe the new keys can’t be placed into the first leaf blocks because they’re not appropriate?

Richard Foote - January 5, 2012

Hi Ahmed

No, it being a PK contraint policed via a Unique index is not the issue. You would get the same results in it were a Non-Unique index (I’m sure).

6. Alberto Frosi (@Albertofro) - January 5, 2012

Hi Richard,
I’m agree with Vyacheslav, the problem is ASSM tablespace.
I’ve created a MSSM tablespace testing same situation.


create tablespace mssm_tbs
datafile 'C:\oraclexe\app\oracle\oradata\XE\mssm01.dbf' size 100M
extent management local autoallocate segment space management manual;

NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   379                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   379                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   379                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   379                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   402                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201500                 1500                   407                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201500                 1500                   407                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      202044                 2044                   407                    1    

In my case the values don’t grow.
I’ll wait your answer hoping my formatting is well done… ;-)
Ciao
Alberto

Richard Foote - January 5, 2012

Thanks Alberto, you saved me having to include this in the solution post :)

7. Alberto Frosi (@Albertofro) - January 5, 2012

Sorry I guess no…another try….


blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   379                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   379                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   379                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   379                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201000                 1000                   402                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201500                 1500                   407                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      201500                 1500                   407                    1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME                           HEIGHT                 LF_ROWS                DEL_LF_ROWS            LF_BLKS                BR_BLKS                
------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 
BOWIE_PK                       2                      202044                 2044                   407                    1                      
8. Alberto Frosi (@Albertofro) - January 5, 2012
PROCEDURE delete_insert_rows compilato
blocco anonimo completato
index BOWIE_PK analizzato.
NAME        HEIGHT LF_ROWS   DEL_LF_ROWS  LF_BLKS   BR_BLKS                
------------------------------- ---------------------- ------
BOWIE_PK    2      201000    1000         379        1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME      HEIGHT  LF_ROWS DEL_LF_ROWS LF_BLKS  BR_BLKS                
------------------------------ ---------------------- 
BOWIE_PK  2      201000   1000        379       1                      

blocco anonimo completato
index BOWIE_PK analizzato.
NAME      HEIGHT  LF_ROWS DEL_LF_ROWS LF_BLKS  BR_BLKS                
------------------------------ ---------------------- 
BOWIE_PK  2      201000   1000        379       1                     

blocco anonimo completato
index BOWIE_PK analizzato.
NAME      HEIGHT  LF_ROWS DEL_LF_ROWS LF_BLKS  BR_BLKS                
------------------------------ ---------------------- 
BOWIE_PK  2      201000   1000        379       1      

blocco anonimo completato
index BOWIE_PK analizzato.

NAME      HEIGHT  LF_ROWS DEL_LF_ROWS LF_BLKS  BR_BLKS                
------------------------------ ---------------------- 
BOWIE_PK  2      201000   1000        402       1  
 

blocco anonimo completato
index BOWIE_PK analizzato.

NAME      HEIGHT  LF_ROWS DEL_LF_ROWS LF_BLKS  BR_BLKS                
------------------------------ ---------------------- 
BOWIE_PK  2      201000   1500        407       1  

blocco anonimo completato
index BOWIE_PK analizzato.
NAME      HEIGHT  LF_ROWS DEL_LF_ROWS LF_BLKS  BR_BLKS                
------------------------------ ---------------------- 
BOWIE_PK  2      201000   1500        407       1  

blocco anonimo completato
index BOWIE_PK analizzato.

NAME      HEIGHT  LF_ROWS DEL_LF_ROWS LF_BLKS  BR_BLKS                
------------------------------ ---------------------- 
BOWIE_PK  2      202044   2044        407       1  
9. nodeisdown - January 5, 2012

Hi,
Shouldn’t we collect stats after every package call?

David Fitzjarrell (@ddfdba) - January 5, 2012

Collectng stats won’t change Oracle’s behaviour. Also a reverse-key index won’t eliminate the behaviour although it does improve the situation considerably:

SQL> create table bowie (id number, name varchar2(100));

Table created.

SQL> create unique index bowie_pk on bowie(id) reverse;

Index created.

SQL> alter table bowie add constraint bowie_pk primary key(id) using index bowie_pk;

Table altered.

SQL>

SQL> analyze index bowie_pk validate structure;

Index analyzed.

SQL>
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 512 1

SQL>

SQL> analyze index bowie_pk validate structure;

Index analyzed.

SQL>
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 210249 10249 523 1

SQL>

Notice that the leaf blocks only increase by 11 after 10 iterations of the procedure. The problem is caused by Oracle not releasing deleted leaf blocks to the pool until the branch they belong to is completely empty. The reverse key index makes more of the new keys fit into the existing ranges so the branch doesn’t need to be completely empty and the leaf blocks can be reused. That being said it’s not a common occurrence to use a reverse key index for a primary key unless block contention rears its ugly head, however it is nice to know that taking the time to create a reversed primary key can mitigate the problem.

Richard Foote - January 5, 2012

Hi David

Thanks for the demo :)

Although Reverse Key index won’t change the problem as such, it does make it Irrelevant as we now don’t have empty leaf blocks to worry about. All the inserts will basically go into leaf blocks that contain some data and will simply clean out any deleted deadwood that might exist.

Richard Foote - January 5, 2012

Hi Nodeisdown

I agree you should, especially with code dependant on correct stats. Dynamic sampling will likely be OK in this scenario though, although the recursive SQL could add to the problem of the leaf blocks being locked away due to the bitmap space management.

David Fitzjarrell (@ddfdba) - January 6, 2012

Richard,

I believe I said what you did in my response, using more words. :D And you’re welcome for the demo — I tend to play with Oracle as much as I can and set up examples to examine and possibly explain observed behaviour. Thank you for providing yet another avenue to pursue with my curiosity.

10. Curious Case Of The Ever Increasing Index Solution (A Big Hurt) « Richard Foote’s Oracle Blog - January 5, 2012

[...] on the excellent comments in the Quiz post, we have some clever cookies out [...]

11. Vyacheslav Rasskazov - January 5, 2012

It seems, that this ASSM issue related to parsing. session_cached_cursors=0 disables such huge growing of leaf blocks. Performance, of course, worse. May be, better to regularly coalesce such index.

Richard Foote - January 5, 2012

Hi Vyacheslav

Thanks for the heads-up. It does in part explain why doing away with the select statement within the procedure improves matters significantly.

I would still avoid the index coalesce if I could :)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,808 other followers

%d bloggers like this: