Bitmap indexing has been touted as a promising approach for processing
complex adhoc queries in read-mostly environments, like those of
decision support systems. Nevertheless, only few possible bitmap
schemes have been proposed in the past and very little is known about
the space-time tradeoff that they offer. In this paper, we present
a general framework to study the design space of bitmap indexes for
selection queries and examine the disk-space and time characteristics
that the various alternative index choices offer. In particular, we
draw a parallel between bitmap indexing and number representation in
different number systems, and define a space of two orthogonal
dimensions that captures a wide array of bitmap indexes, both old
and new. Within that space, we identify (analytically or
experimentally) the following interesting points: (1) the time-optimal
bitmap index; (2) the space-optimal bitmap index; (3) the bitmap index
with the optimal space-time tradeoff (knee); and (4) the time-optimal
bitmap index under a given disk-space constraint. Finally, we examine
the impact of bitmap compression and bitmap buffering on the space-time
tradeoffs among those indexes. As part of this work, we also describe
a bitmap-index-based evaluation algorithm for selection queries that
represents an improvement over earlier proposals. We believe that this
study offers a useful first set of guidelines for physical database
design using bitmap indexes.
Wisconsin DBMS Research Home Page