|
|
|
@inproceedings{DBLP:conf/vldb/Johnson99,
author = {Theodore Johnson},
editor = {Malcolm P. Atkinson and
Maria E. Orlowska and
Patrick Valduriez and
Stanley B. Zdonik and
Michael L. Brodie},
title = {Performance Measurements of Compressed Bitmap Indices},
booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
UK},
publisher = {Morgan Kaufmann},
year = {1999},
isbn = {1-55860-615-7},
pages = {278-289},
ee = {db/conf/vldb/Johnson99.html},
crossref = {DBLP:conf/vldb/99},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Bitmap indices are commonly used by DBMS's to accelerate decision support queries. A bitmap index is a collection of bitmaps in which each bit is mapped to a record ID (RID). A bit in a bitmap is set if the corresponding RID has property P (i.e., the RID represents a customer that lives in New York), and is reset otherwise. A significant advance of bitmap indices is that complex logical selection operations can be perfromed very quickly, by performing bit-wise AND, OR, and NOT operations. Bitmap are also compact representations of densely popolated sets. By using bitmap compression techniques, they are also compact representations of sparsely populated sets.
In spite of the great interest in bitmap indices, little has been published about the comparative performance of bitmap compression algorithms (i.e., compression ratios and times for Boolean operations) in a DBMS environment. We have implemented the three main bitmap compression techniques (LZ compression, variable bit-length codes, and variable byte-length codes) and built a generic bitmap index from them. We have tested each of these compression techniques (and their variants) for their compression ratio on a wide variety of synthetic and actual bitmap indices. Because bitmap indices are valuable for complex selection conditions, we evaluate four methods for performing a Boolean operation between compressed bitmaps, including methods that use compressed or partially uncompressed bitmaps directly.
Our results show that the best bitmap index compression technique and the best Boolean operation algorithms strongly depend on the bitmaps being compressed or operated on and the operations being performed. These results are a step towards understanding the space-time tradeoff in adaptive compressed bitmap indices, developing a bitmap index design methodology for compressed bitmaps, and optimizing Boolean expression evaluation on compressed bitmaps.
Copyright © 1999 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
