Myth: Space is never reused in an index

Tom Kyte elaborates on the myth that space is never reused in an index.

This excerpt is from Tom Kyte's new book Expert Oracle Database Architecture: 9i and 10g Programming Techniques and Solutions, published by Apress in September 2005. Tom Kyte is Vice President of the Core Technologies Group at Oracle and has been using Oracle since 1988. To see other frequently asked questions and myths about indexes, click here.

This is a myth that I would like to dispel once and for all. Space is reused in an index. The myth goes like this: you have a table, T, in which there is a column, X. At some point, you put the value X = 5 in the table. Later you delete it. The myth is that the space used by X = 5 will not be reused unless you put X = 5 back into the index later. The myth states that once an index slot is used, it will be there forever and can be reused only by the same value. A corollary to this is the myth that free space is never returned to the index structure, and a block will never be reused. Again, this is simply not true.

The first part of the myth is trivial to disprove. All we need to do is to create a table like this:

ops$tkyte@ORA10GR1> create table t ( x int, constraint t_pk primary key(x) );
Table created.

ops$tkyte@ORA10GR1> insert into t values (1);
1 row created.

ops$tkyte@ORA10GR1> insert into t values (2);
1 row created.

ops$tkyte@ORA10GR1> insert into t values (9999999999);
1 row created.

ops$tkyte@ORA10GR1> analyze index t_pk validate structure;
Index analyzed.

ops$tkyte@ORA10GR1> select lf_blks, br_blks, btree_space
2 from index_stats;

LF_BLKS        BR_BLKS       BTREE_SPACE
------------- -------------  ----------------------
            1             0                   7996

So, according to the myth, if I delete from T where X = 2, that space will never be reused unless I reinsert the number 2. Currently, this index is using one leaf block of space. If the index key entries are never reused upon deletion, and I keep inserting and deleting and never reuse a value, this index should grow like crazy. Let's see:

ops$tkyte@ORA10GR1> begin
   2                 for i in 2 .. 999999
   3                 loop
   4                           delete from t where x = i;
   5                           commit;
   6                           insert into t values (i+1);
   7                           commit;
   8                 end loop;
   9   end;
 10   /
PL/SQL procedure successfully completed.

ops$tkyte@ORA10GR1> analyze index t_pk validate structure;
Index analyzed.

ops$tkyte@ORA10GR1> select lf_blks, br_blks, btree_space
2 from index_stats;

LF_BLKS        BR_BLKS       BTREE_SPACE
------------- -------------  ----------------------
            1             0                  7996

This shows the space in the index was reused. As with most myths, however, there is a nugget of truth in there. The truth is that the space used by that initial number 2 (in between 1 and 9,999,999,999) would remain on that index block forever. The index will not "coalesce" itself. This means if I load a table with values 1 to 500,000 and then delete every other row (all of the even numbers), there will be 250,000 "holes" in the index on that column. Only if I reinsert data that will fit onto a block where there is a hole will the space be reused. Oracle will make no attempt to "shrink" or compact the index. This can be done via an ALTER INDEX REBUILD or COALESCE command. On the other hand, if I load a table with values 1 to 500,000 and then delete from the table every row where the value was 250,000 or less, I would find the blocks that were cleaned out of the index were put back onto the freelist for the index. This space can be totally reused.

If you recall, this was the second myth: index space is never "reclaimed." It states that once an index block is used, it will be stuck in that place in the index structure forever and will only be reused if you insert data that would go into that place in the index anyway. We can show that this is false as well. First, we need to build a table with about 500,000 rows in it. For that, we'll use the big_table script. After we have that table with its corresponding primary key index, we'll measure how many leaf blocks are in the index and how many blocks are on the freelist for the index. Remember, with an index, a block will only be on the freelist if the block is entirely empty, unlike a table. So any blocks we see on the freelist are completely empty and available for reuse:

ops$tkyte@ORA10GR1> select count(*) from big_table;

COUNT(*)
--------------
     500000

ops$tkyte@ORA10GR1> declare
   2        l_freelist_blocks number;
   3  begin
   4        dbms_space.free_blocks
   5        ( segment_owner => user,
   6          segment_name => 'BIG_TABLE_PK',
   7          segment_type => 'INDEX',
   8          freelist_group_id => 0,
   9          free_blks => l_freelist_blocks );
 10       dbms_output.put_line( 'blocks on freelist = ' || l_freelist_blocks );
 11  end;
 12  /
blocks on freelist = 0
PL/SQL procedure successfully completed.

ops$tkyte@ORA10GR1> select leaf_blocks from user_indexes
2 where index_name = 'BIG_TABLE_PK';

LEAF_BLOCKS
---------------------
                1043

Before we perform this mass deletion, we have no blocks on the freelist and there are 1,043 blocks in the "leafs" of the index, holding data. Now, we'll perform the delete and measure the space utilization again:

ops$tkyte@ORA10GR1> delete from big_table where id <= 250000;
250000 rows deleted.

ops$tkyte@ORA10GR1> commit;
Commit complete.

ops$tkyte@ORA10GR1> declare
   2       l_freelist_blocks number;
   3   begin
   4       dbms_space.free_blocks
   5       ( segment_owner => user,
   6         segment_name => 'BIG_TABLE_PK',
   7         segment_type => 'INDEX',
   8         freelist_group_id => 0,
   9         free_blks => l_freelist_blocks );
 10       dbms_output.put_line( 'blocks on freelist = ' || l_freelist_blocks );
 11                 dbms_stats.gather_index_stats
 12                 ( user, 'BIG_TABLE_PK' );
 13   end;
 14   /
blocks on freelist = 520
PL/SQL procedure successfully completed.

ops$tkyte@ORA10GR1> select leaf_blocks from user_indexes
2 where index_name = 'BIG_TABLE_PK';

LEAF_BLOCKS
---------------------
                 523

As we can see, over half of the index is on the freelist now (520 blocks) and there are only 523 leaf blocks. If we add 523 and 520, we get the original 1043. This means the blocks are totally empty and ready to be reused (blocks on the freelist for an index must be empty, unlike blocks on the freelist for a heap organized table).

This demonstration highlights two points:

  • Space is reused on index blocks as soon as a row comes along that can reuse it.
  • When an index block is emptied, it can be taken out of the index structure and may be reused later. This is probably the genesis of this myth in the first place: blocks are not visible as having "free space" on them in an index structure as they are in a table. In a table, you can see blocks on the freelists, even if they have data on them. In an index, you will only see completely empty blocks on the freelists; blocks that have at least one index entry (and remaining free space) will not be as clearly visible.

To see other frequently asked questions and myths about indexes, click here.


This was first published in October 2005

Dig deeper on Oracle database design and architecture

Pro+

Features

Enjoy the benefits of Pro+ membership, learn more and join.

0 comments

Oldest 

Forgot Password?

No problem! Submit your e-mail address below. We'll send you an email containing your password.

Your password has been sent to:

-ADS BY GOOGLE

SearchDataManagement

SearchBusinessAnalytics

SearchSAP

SearchSQLServer

TheServerSide

SearchDataCenter

SearchContentManagement

SearchFinancialApplications

Close