Curious Case Of The Ever Increasing Index Solution (A Big Hurt)

Based on the excellent comments in the Quiz post, we have some clever cookies out there 🙂

I guess the first thing to point out is that based in the basic scenario provided, the index shouldn’t ordinarily be continually growing in this fashion. Although the index values are monotonically increasing, the deletions are leaving behind fully emptied leaf blocks which can generally be recycled in future block splits.

OK, so why is this index behaving in this fashion, continually to increase in size while the number of rows in the table remains relatively constant ?

Well, there are a number of contributing factors.

As stated, the index values are indeed monotonically increasing so all inserts into the index are hitting the right-most index leaf block within the index structure and the deletions which all occur on the “left-side” of the index are leaving behind leaf blocks that contain nothing but deleted index entries. As Marcus and David mentioned in the comments, the use of a Reverse Key index would therefore alleviate this problem as subsequent inserts will be performed within the same leaf blocks in the index structure, automatically cleaning out and reusing space used by previously deleted index entries. This solution though may create as many problems as it solves (if say range predicate statements relied on a Non-Reverse index).

Additionally, the processing is being performed with a PL/SQL block. Oracle has a whole lot of smarts to make PL/SQL as efficient as possible and so the manner in which code runs within PL/SQL compared to other native languages can vary significantly. Unfortunately at times, these smarts might not be quite so smart after all.

The tablespace used to store the index is a Locally Managed Tablespace (LMT) with Automatic Segment Storage Management (ASSM). Instead of freelists (or freelist groups), Oracle uses a set of bitmap blocks within the index segment to determine the amount of free space available within its blocks and whether a block is available for inserts. As Vyacheslav and Alberto highlighted in the comments, there are a number of “issues” in the manner in which these bitmap blocks are maintained within PL/SQL processing. This is effectively locking out the vast number of these now effectively empty leaf blocks from being recycled and reconsidered for subsequent inserts. By rebuilding the index once in a Manual Segment Space Management (MSSM) tablespace would also alleviate this issue.

The actual processing involved within the PL/SQL block can also have an impact. The procedure contained the following important statement:

select min(id),max(id) into n,m from bowie;

By removing this statement from the PL/SQL block and either manually defining the values to be processed or passing them through to the procedure, can impact how PL/SQL manages the freespace bitmaps within the segment. For example, if one used something similar to the following:

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

The number of leaf blocks allocated will be nowhere as significant as before and stabilised after a few runs to approximate:

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     289040       89040        744          4

Finally, the PL/SQL procedure only performed a Commit after 1000 iterations. This means that there were 1000 deletions performed during a logical transaction. As Greg mentioned in the comments, Unique Key index values can be reused within a single transaction BUT only if the same actual values are reused. The procedure introduces new values for those that have been deleted and so the deleted entries can’t be reused during the same transaction. This means there will be at least 1000 deleted index entries that can’t be reused during the running of the procedure and sufficient additional leaf blocks to accommodate these 1000 index entries will need to be allocated, even if we use some of the solutions mentioned, such as Reverse Key indexes or MSSM tablespaces. By performing either all the necessary deletions within one transaction followed by the inserts or having a Commit for each delete/insert pairing, these additional blocks won’t be required. For example:

SQL> declare
  2        n number:= 1;
  3        m number:= 200000;
  4    begin
  5      for i in 1..200000 loop
  6           delete from bowie where id=n+i-1;
  7           commit;
  8           insert into bowie values(m+i,'David Bowie');
  9           commit;
 10      end loop;
 11  end;
 12  /

Although of course, the inefficiencies in the processing or the potential breaking of business rules may not make the index savings worthwhile.

So in summary, there a number of things we could do to fix this scenario, rather than simply periodically rebuilding the index all the time. Depending on applicability, we could convert the index to a Reverse Key index (or say Hash Partition), we could move the index to a MSSM tablespace, we could modify our procedure logic to remove the reference to fetching MIN/MAX values, not use PL/SQL, or to make the index as efficient as possible, change the transactional logic to not perform large numbers of inserts and deletes within the same transaction.

So there’s quite a lot happening within what on the surface looks like a simple piece of PL/SQL 🙂