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.
