Multiple Index Access - Relational Database Index Design and the Optimizers - page 196

C1 C2 C3 C4 C5

P,C

CNO

Figure 10.2 Six thin
indexes—adequate
performance for any
WHERE clause.

CUST (Query table)

1,000,000 rows, many columns

table rows tends to be the longest component of the response time: The DBMS
may have to read thousands of table rows that could be some distance from each
other. Fat indexes eliminate these table touches. Designing the fat indexes is
analogous to indexing the dimension tables—which we considered in Chapter 9
(the minimum number is one per search column), but the length of the index
rowsmaybeanissue.

Multiple Index Access and Fact Tables

It may seem tempting to build several thin indexes, the primary key and the
foreign keys, on a large fact table. They would consume much less disk space than
the fat indexes recommended in Chapter 9. Unfortunately, however, a multiple
index scan with B-tree indexes, together with the scan and sort of a huge number
of pointers, would probably be too slow with current hardware if the table has,
say, a billion rows.

Multiple Index Access with Bitmap Indexes

Index ANDing and index ORing are much faster with bitmap indexes. Bitmap
indexes are more efficient than traditional B-tree indexes for unpredictable queries
against very large tables for which there are no table touches, for example,
SELECT COUNT, or a small number of table touches . According to Sasha and
Bonnet (7, p. 281), the CIA was among the first users of bitmap indexes:
The comparative advantage of bitmaps is that it is easy to use multiple bitmaps
to answer a single query. Consider a query on several predicates, each of
which is indexed. A conventional database would use just one of the indexes,
though some systems might attempt to intersect the record identifiers of multiple
indexes. Bitmaps work better because they are more compact, and intersecting
several bitmaps is much faster than intersecting several collections of record
identifiers. In the best case the improvement is proportional to the word size of
the machine because two bitmaps can be intersected word-sized bits at a time.
That best case occurs when each predicate is unselective, but all the predicates