Logo image
Back
Dynamic bitmap index recompression through workload-based optimizations
Conference proceeding

Dynamic bitmap index recompression through workload-based optimizations

Fredton Doan, David Chiu, Brasil Lukes, Jason Sawin, Gheorghi Guzun and Guadalupe Canahuate
Proceedings of the 17th International Database Engineering & Applications Symposium, pp.96-105
IDEAS '13
10/09/2013
DOI: 10.1145/2513591.2513641

View Online

Abstract

Many large-scale read-only databases and data warehouses use bitmap indices in an effort to speed up data analysis. These indices have the dual properties of compressibility and being able to leverage fast bit-wise operations for query processing. Numerous hybrid run-length encoding compression schemes have been proposed that greatly compress the index and enable querying without the need to decompress. Typically, these schemes align their compression with the computer architecture's word size to further accelerate queries. Previously, we introduced Variable Length Compression (VLC), which uses a general encoding that can achieve better compression than word-aligned schemes. However, VLC's querying efficiency can vary widely due to mismatched alignment of compressed columns. In this paper, we present an optimizer which recompresses the bitmap over time. Based on query history, our approach allows the VLC user to specify the priority of compression versus query efficiency, then possibly recompress the bitmap accordingly. In an empirical study using scientific data sets, we showed that our approach was able to achieve both better compression ratios and query speedup over WAH and PLWAH. On the largest data set, our VLC optimizer compressed up to 1.73x better than WAH, and 1.46x over PLWAH. We also show a slight improvement in query efficiency in most experiments, while observing lucrative (11x to 16x) speedup in special cases.
 bitmap compression indexing modeling optimization

Details

Metrics

12 Record Views
Logo image