 |
|
|
Bitmap Index Design and Evaluation |
Full Paper (PDF)
Slides (PDF)
|
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. |
References, where available, link to the DBLP on the World Wide Web.
[1]...
[2]...
[3]Surajit Chaudhuri, Umeshwar Dayal:
An Overview of Data Warehousing and OLAP Technology.
SIGMOD Record 26(1): 65-74(1997)[4]...
[5]...
[6]Clark D. French:
"One Size Fits All" Database Architectures Do Not Work for DDS.
SIGMOD Conference 1995: 449-450[7]Goetz Graefe:
Query Evaluation Techniques for Large Databases.
Computing Surveys 25(2): 73-170(1993)[8]Patrick E. O'Neil:
Model 204 Architecture and Performance.
HPTS 1987: 40-59[9]Patrick E. O'Neil, Goetz Graefe:
Multi-Table Joins Through Bitmapped Join Indices.
SIGMOD Record 24(3): 8-11(1995)[10]Patrick E. O'Neil, Dallan Quass:
Improved Query Performance with Variant Indexes.
SIGMOD Conference 1997: 38-49[11]Thin-Fong Tsuei, Allan Packer, Keng-Tai Ko:
Database Buffer Size Investigation for OLTP Workloads (Experience Paper).
SIGMOD Conference 1997: 112-122[12]...
[13]Harry K. T. Wong, Jianzhong Li, Frank Olken, Doron Rotem, Linda Wong:
Bit Transposition for Very Large Scientific and Statistical Databases.
Algorithmica 1(3): 289-309(1986)[14]Harry K. T. Wong, Hsiu-Fen Liu, Frank Olken, Doron Rotem, Linda Wong:
Bit Transposed Files.
VLDB 1985: 448-457
|
@inproceedings{DBLP:conf/sigmod/ChanI98,
author = {Chee Yong Chan and
Yannis E. Ioannidis},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {Bitmap Index Design and Evaluation},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-955-5},
pages = {355-366},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
