Databases Reference
In-Depth Information
Figure 2.4
Comparison of composite index and scan I/O time for the same query.
Thus, we see that the composite index time reduces the exhaustive scan time by a fac-
tor of about 55 to 1. Multiplying 55 times 750 target rows to get a rough estimate, we
see that at approximately 41,250 target rows and higher, a table scan becomes the
more efficient method of satisfying this query. The overall plot of I/O time is shown
in Figure 2.4.
2.3
Bitmap Indexing
One of the most basic rules of thumb for index design in data warehouses is to create
indexes on each column of each of the dimension tables and all the corresponding for-
eign keys in the fact table. This facilitates any joins required between the fact table and
the corresponding dimension tables, including multiple joins. Join indexes that map an
attribute value (or a concatenation of several attribute values) of a dimension table to
one or more rows in a fact table are just variations on the composite index searches we
discussed in Section 2.3. Thus, a join index is really a binary precomputed join, and
composite join indexes are really
n
-way precomputed joins. These techniques can
greatly enhance performance of a data warehouse.
Highly analytical queries that are weakly selective can make use of bitmap (or bit
vector) indexes [O'Neil 1995].
Bitmap indexes
are particularly useful for low-selectivity
queries, such as those that search based on few alternative values, like male/female
