Partitioned Compression of Bitmap Indices

A bitmap index is a type of database index in which querying is implemented using logical operations (AND, OR, XOR) at the CPU level. To accelerate these operations, we compress the bitmaps using run-length encoding (RLE). To improve RLE, and thus improve the efficiency of the compression, we can reorder the rows of the bitmap to maximize the run lengths in the columns. Finding the perfect row-reordering is NP-hard, so approximations must be used. A commonly-used approximation for row-reordering is lexicographically sorting the bitmap. Unfortunately, bitmap indices are often to large to fit entirely into memory, so a full sort is often unfeasible. A partition-sorting scheme is investigated in which a bitmap index is split into several partitions which are then sorted individually. This partitioned-sorting scheme achieves compression efficiency approaching a full sort, with enormous savings in CPU time