Column Partition and Permutation for Run Length Encoding in Columnar Databases
Jia Shi · 2020
Effective compression is essential when databases are used in Big Data applications. For in-memory columnar databases, compression can help to load the columns faster and speed up query evaluation. In this paper, we consider compressing columns using the Run Length Encoding (RLE). This algorithm encodes each region with identical value using a single run. The question we study in this paper is 'how to rearrange table columns for better compression?' We observe that not every column of a table benefits from column compression in an ideal column arrangement. Because finding the optimal column arrangement is NP-hard, we propose an incremental heuristic that identifies the set of columns to be compressed and the order of rows that offer a better compression ratio. Our preliminary experiments confirm that our algorithm improves the compression rate by up to 25% on test data, compared with compressing all columns of a table.