Optimizing Queries on Compressed Bitmaps
Sihem Amer-Yahia, Theodore J. Johnson · 2000
Bitmap indices are used by DBMS's to accelerate decision support queries. A significant advantage of bitmap indices is that complex logical selection operations can be performed very quickly, by performing bit-wise AND, OR, and NOT operators. Although bitmap indices can be space inefficient for high cardinality attributes, the space use of compressed bitmaps compares well to other indexing methods. Oracle and Sybase IQ are two commercial products that make extensive use of compressed bitmap indices. Our recent research showed that there are several fast algorithms for evaluating Boolean operators on compressed bitmaps. Depending on the nature of the operand bitmaps (their format, density and clusterdness) and the operation to be performed (AND, NOT, ...), these algorithms can have execution times that are orders of magnitude different. Choosing an algorithm for performing a Boolean operation has global effects in the Boolean query expression, requiring global optimization. We present a linear time dynamic programming search strategy based on a cost model to optimize query expression evaluation plans. We also present rewriting heuristics that rewrite the query expression to an equivalent one to encourage better algorithms assignments. Our performance results show that the optimizer requires a negligible amount of time to execute, and that optimized complex queries can execute up to three times faster than unoptimized queries on real data. 1