Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















Performance Measurements of Compressed Bitmap Indices

Theodore Johnson

  View Paper (PDF)  

Return to Understanding Database Performance

Abstract
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.


References

Note: References link to DBLP on the Web.

[1]
...
[2]
...
[3]
Chee Yong Chan , Yannis E. Ioannidis : Bitmap Index Design and Evaluation. SIGMOD Conference 1998 : 355-366
[4]
...
[5]
...
[6]
Jean-Loup Gailly, Mark Adler : Zlib Home Page [old location: http://quest.jpl.nasa.gov/zlib]. http://www.cdrom.com/pub/infozip/zlib/
[7]
Alistair Moffat , Justin Zobel : Parameterised Compression for Sparse Bitmaps. SIGIR 1992 : 274-285
[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]
...
[12]
...
[13]
Ming-Chuan Wu , Alejandro P. Buchmann : Encoded Bitmap Indexing for Data Warehouses. ICDE 1998 : 220-230

BIBTEX

@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-5},
   pages     = {278-289},
   crossref  = {DBLP:conf/vldb/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM