CorBit: Leveraging Correlations for
Compressing Bitmap Indexes

Abstract

A bitmap index is a secondary index structure that supports equality and range predicates. In its simplest form, a bitmap index stores one bitmap per unique column value indicating qualifying tuples. To use such indexes in large-scale data warehousing, they need to be space efficient. Existing schemes such as Roaring can compress individual bitmaps but do not consider cross-column compression.

In this paper, we introduce CorBit, a technique that leverages column correlations to compress bitmap indexes on a given table. The high-level idea is to only store the bits that need to be flipped (the diff) when encoding the bitmaps of a column that correlates with another column that already has a bitmap index in place. CorBit automatically determines which columns to store an index for and which column bitmaps to diff-encode, minimizing the overall size of the index. Compared to Roaring, CorBit consumes 9.1% less space on the DMV dataset while incurring a 12.6% runtime overhead.

Basic Idea

If two columns in a table are highly correlated, we only materialize the bitmap index of one column. For each unique value in the other column, we find the closest bitmap in the materialized column w.r.t. Hamming distance and only store the differences in its bitmap. If the Hamming distance is small, the diff-encoded bitmaps will be sparse, allowing various bitmap compression methods such as Roaring or run-length encoding to save more space.

For example, the two columns Language and Country in a user information table are usually highly correlated, as shown above. Specifically, the skewed frequency counts in the table indicate that if we would materialize the bitmaps of the Country column, using diff-encoding for the Language column would save space. E.g., for the value German in Language we choose the Germany bitmap as reference and store the XOR of the two bitmaps.

Measuring Correlation

To decide which column pairs to consider for our cross-column compression scheme, a naïve approach would be to consider all pairs of columns and calculate actual sizes of encoded indexes, as shown below.

Unfortunately, the naïve approach is computationally expensive. A better method would be to find a suitable and efficient metric that can help us identify potentially correlated column pairs.

Therefore, we have evaluated a number of metrics that measure the correlation of categorical features, and we also designed our own metric called Total Reduced Popcnt based on the contingency table. It directly measures how much the total population count of the diff-encoded bitmaps can be reduced. This metric is defined as $$\eta_{A,B} = \sum_{a \in U_A} \max \{0, \max_{b \in U_B} \{2 |\sigma_{A=a \land B=b} R| - |\sigma_{B=b} R|\} \}$$ where $A$ and $B$ are two columns in relation $R$. This metric is highly positively related to the saved space. This approach only requires traversing the dataset once and then utilizing contingency tables for subsequent calculations.

Compressing a Bitmap Index

As we have identified an appropriate correlation metric, namely Total Reduced Popcnt, which exhibits a strong positive correlation with the saved space. What we need to annotate here is the Total Popcnt, the sum of the population counts of the bitmaps of the column, which we can calculate easily.

Once we obtain an annotated complete digraph, we can employ a greedy algorithm to obtain a near-optimal solution. This involves greedily selecting the best edge and adding it to the dependency graph and continue the process as long as it results in an overall reduction in space consumption.

Finally, we compute the original bitmaps and XOR bitmaps that need to be stored based on the obtained dependency graph. Since we used Total Reduced Popcnt as a correlation metric, the intermediate results allow us to select, for each bitmap in a column, the closest bitmap in its referenced column. This is also one of the advantages of employing Total Reduced Popcnt.

Balancing between Space-saving and Performance Overhead

Since the XOR operation also takes time, for performance considerations, we choose to store a XOR bitmap only if it saves $p$ of the space compared to the encoded original bitmap. By adjusting the parameter $p$, users can strike a balance between performance and space. To save more space, a smaller value of $p$ can be chosen, such as 50%. On the other hand, if performance is of greater concern, a larger value of $p$, such as 90%, can be selected.

Results

We evaluate on multiple real-world datasets with various settings. Compared to Roaring, CorBit consumes 9.1% less space on the DMV dataset while incurring a 12.6% runtime overhead.

The table below shows the top 5 columns with the highest space savings in the DMV dataset. We observe that the Scofflaw Indicator references the Revocation Indicator, and Zip and County reference City. These relationships are reasonable based on the meanings of these columns, and CorBit has successfully discovered the correlations, leading to space savings.

Refer to the paper for more results.

Citation

@inproceedings{corbit,
  title={CorBit: Leveraging Correlations for Compressing Bitmap Indexes},
  author={Xi Lyu and Andreas Kipf and Pascal Pfeil and Dominik Horn and Jana Giceva and Tim Kraska},
  year={2023},
  booktitle={Proceedings of the VLDB Endowment},
  booksubtitle={5th International Workshop on Applied AI for Database Systems and Applications}
}