Indexing Alternatives to B-Tree Indexes
Oracle Tips by Burleson Consulting
As you may know, Oracle offers several
alternative indexing methods to enhance the standard B-tree indexes.
These include bitmap indexes, function-based indexes, and
It was a common misconception that bitmap
indexes were only appropriate for columns with a very small number
of distinct values—say, fewer than 50. Current research in Oracle8i
has shown that bitmap indexes can substantially improve the speed of
queries using columns with up to 1000 distinct values, because
retrieval from a bitmap index is done in RAM and is almost always
faster than using a traditional B-tree index. Most experienced Remote DBAs
will look for table that contain columns with fewer than 1000
distinct values, build a bitmap index on these columns, and then see
if the query is faster.
To use the alternative indexing structures,
you must first identify SQL statements that are using the BIF. In
the next example, we can search the v$sqlarea view to find
all SQL statements that are using the to_char BIF.
v$sqlarea -- or stats$sql_summary
sql_text like ‘%to_char%’;
Once identified, function-based indexes can
be created to remove the full-table scans and replace them with
index-range scans. For details on tuning with function-based
indexes, see Chapter 23.
Reverse-Key Indexes and SQL Performance
There is, however, a major scalability danger
with automatically generated synthetic keys. Every insertion to a
table requires a corresponding insertion to its primary key index.
If the primary key values are being generated in ascending order,
then all inserts will need to change the high-order leaf block in
the B-tree. There is an obvious danger here of contention for that
block of the index, if several users attempt concurrent inserts
(whereas the inserts to the table itself can easily be distributed
to a variety of blocks by using multiple process freelists).
Prior to Oracle8, the standard strategy to
avoid this problem was to ensure that the synthetic key values were
not generated in order. This was done by permuting the values
generated by the sequence number generator before using them.
Various permutation schemes such as adding a leading check digit, or
reversing the order of the digits, have been used. These schemes
have the effect of distributing inserts evenly over the range of
values in the index, thus preventing leaf block contention. In
Oracle8, the same effect may be obtained by using a reverse-key
The major disadvantage of distributing
inserts in this way is that the data density of index leaf blocks
will be typically only 75 percent of capacity rather than almost 100
percent, making fast full-index scans on the primary key index less
efficient. However, this access path is not typical and is seldom
performance critical when used. So, reverse-key indexes should be
used in general for synthetic primary key indexes.
This is an excerpt from "Oracle High-Performance SQL Tuning" by
Donald K. Burleson, published by Oracle Press.