Information Technology Reference
In-Depth Information
Chapter 11
Online Index Construction and Maintenance
In the preceding chapters, we have assumed that tuples in a relation are accessed via
a sparse B-tree index on the primary key of the relation. In this chapter we extend
our database and transaction model with read, delete, and update actions based on
ranges of non-primary-key attributes. To accelerate these actions,
secondary indexes
must be constructed. A secondary index, as considered here, is a
dense B-tree
whose
leaf pages contain index records that point to the tuples stored in leaf pages of the
sparse primary B-tree index of the relation.
A relation can have many secondary indexes on different attributes or combina-
tions of attributes, thus making it possible for the query optimizer to find efficient
execution plans for many kinds of queries. However, this comes with the price of an
overhead on updates: when a transaction inserts or deletes a tuple, all the indexes
must also be updated within the same transaction.
In database performance tuning, it is common that new secondary indexes
are constructed when it is found that some regularly performed
SQL
state-
ments need acceleration, while secondary indexes that are found to be
seldom used in query-execution plans are dropped. Index construction for a
large relation is a heavy and time-consuming operation; in many cases we
cannot
afford
the
relation
to
be
inaccessible
for
transactions
during
index
construction.
In this chapter we present an
online index-construction
algorithm that allows
transactions to update the relation while a secondary index is being constructed.
When the index construction is completed, the new index can also be used in query-
execution plans. We also briefly address the question of online maintenance of the
physical clustering of B-tree indexes.
