Hybrid Query Optimization for Hard-to-Compress Bit-vectors

Abstract Bit-vectors are widely used for indexing and summarizing data due to their efficient processing in modern computers. Sparse bit-vectors can be further compressed to reduce their space requirement. Spe-cial compression schemes based on run-length encoders have been designed to avoid explicit decompression and minimize the decoding overhead during query execu-tion. Moreover, highly compressed bit-vectors can ex-hibit a faster query time than the non-compressed ones. However, for hard-to-compress bit-vectors, compression does not speed up queries, and can add considerable overhead. In these cases, bit-vectors are often stored verbatim (non-compressed). On the other hand, queries are answered by execut-ing a cascade of bit-wise operations involving indexed bit-vectors and intermediate results. Often, even when the original bit-vectors are hard-to-compress, the in-termediate results become sparse. It could be feasible to improve query performance by compressing these bit-vectors as the query is executed. In this scenario it would be necessary to operate verbatim and com-pressed bit-vectors together. In this paper, we propose a hybrid framework where compressed and verbatim bitmaps can coexist and design algorithms to execute queries under this hybrid model. Our query optimizer i