Source-linked AI summary
Better bitmap performance with Roaring bitmaps
Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin
TL;DR
Bitmap indexes speed set queries but can consume substantial memory, and common RLE compression can impair random access. The paper introduces Roaring, which stores dense and sparse chunks differently, and compares it with WAH and Concise. Across synthetic and real data, Roaring often uses less memory and is faster, though RLE formats can compress better on long runs and extremely sparse data can impose overhead.
Problem
Bitmap indexes accelerate queries but can use much memory, while RLE-based compressed formats have slow random access.
Method
Roaring partitions the index space into chunks, storing dense chunks as bitmaps and sparse chunks as packed arrays, then compares the format with WAH and Concise.
Results
Roaring often uses less memory and is faster than WAH and Concise, reaching up to 900× faster intersections on CENSUS1881.
Takeaways & Limitations
The results challenge the view that RLE-based bitmap compression is the most efficient alternative.
Takeaways & Limitations
Concise and WAH can compress better on WIKILEAKS long runs, and Roaring can use 4× as much memory on extremely sparse CENSUS2000 data.
Abstract
from arXiv · showhide
Bitmap indexes are commonly used in databases and search engines. By exploiting bit-level parallelism, they can significantly accelerate queries. However, they can use much memory, and thus we might prefer compressed bitmap indexes. Following Oracle's lead, bitmaps are often compressed using run-length encoding (RLE). Building on prior work, we introduce the Roaring compressed bitmap format: it uses packed arrays for compression instead of RLE. We compare it to two high-performance RLE-based bitmap encoding techniques: WAH (Word Aligned Hybrid compression scheme) and Concise (Compressed `n' Composable Integer Set). On synthetic and real data, we find that Roaring bitmaps (1) often compress significantly better (e.g., 2 times) and (2) are faster than the compressed alternatives (up to 900 times faster for intersections). Our results challenge the view that RLE-based bitmap compression is best.
1. INTRODUCTION
Bitmap indexes accelerate set operations but can consume substantial memory, motivating compressed formats. Roaring replaces RLE-based compression with chunk-specific arrays and bitmaps while preserving fast access and improving performance against WAH and Concise.
- Motivation: Bitmaps represent integer sets compactly and support unions and intersections through bitwise operations.They are often advantageous at relatively high density, while compressed bitmaps can be preferable at moderately low density.
- Prior formats: Most compressed bitmap formats derive from Oracle’s BBC and use run-length encoding, including WAH and Concise.WAH uses fill and literal words, while Concise reallocates bits to reduce fill-word memory usage.
- Prior formats: 64 bits per integer versus 32 bits per integer: WAH requires twice the space of Concise for the illustrated sparse set when w = 32.RLE formats also have slow random access, with checking or changing a bit requiring O(n) time.
- Roaring approach: Roaring partitions [0, n) into chunks, storing dense chunks as bitmaps and sparse chunks as packed arrays of 16-bit integers.This design avoids the random-access sacrifice associated with RLE compression.
- Reported contribution: 4× faster than WAH and Concise on the cited synthetic test: Roaring is reported to achieve at least this speedup and sometimes hundreds of times more.The approach also targets lower memory use through packed arrays.
- Optimization strategy: Roaring uses binary search for sparse-chunk intersections and predicts dense-versus-sparse results to reduce wasteful conversions.These strategies are presented as part of the effort to surpass RLE-based formats.
2. ROARING BITMAP
Roaring stores 32-bit indexes in a two-level structure organized around 2^16-sized chunks. Each chunk uses either a packed array or a bitmap according to its cardinality, while auxiliary counters support fast aggregate operations.
- Chunk organization: Roaring partitions 32-bit indexes into chunks of 2^16 integers sharing the same 16 most significant bits.Specialized containers store the corresponding 16 least significant bits.
- Container selection: At most 4096 integers: a chunk uses a sorted packed array; above 4096, it uses a 2^16-bit bitmap.This threshold keeps container-level storage at no more than 16 bits per integer.
- Index structure: The first-level dynamic array is sorted by shared high bits and typically remains small; for n = 1,000,000, it has at most 16 entries.Individual containers should generally remain below about 8 kB.
- Example: The illustrative list stores sparse values in array containers and dense even values in a bitmap container.This demonstrates how Roaring selects representations within one bitmap.
- Supported operations: Container cardinality counters enable fast bitmap cardinality computation and support rank and select queries.Cardinality is obtained by summing the container counters.
- Scope: Below 0.1% density, container overhead can make Roaring exceed 16 bits per integer, and the authors consider a bitmap unlikely to be appropriate.The layout assumes substantially fewer containers than stored integers.
3. ACCESS OPERATIONS
Roaring locates the relevant high-bit container before accessing, inserting, or removing a value. Bitmap and array containers then use different operations suited to their density.
- Membership: Membership checks first binary-search the container for x/2^16, then access a bit or binary-search an array for x mod 2^16.Bitmap containers provide direct bit access, while array containers use a second binary search.
- Updates: Insertion and deletion locate the container, then update a bitmap bit or perform array search followed by linear-time modification.Bitmap updates also adjust the container cardinality.
- Representation changes: Containers switch representation at cardinality 4096: additions can convert arrays to bitmaps, while removals can convert bitmaps to arrays.Conversions create a new container with the updated representation and discard the old one.
4. LOGICAL OPERATIONS
Roaring implements logical operations by matching sorted first-level keys and dispatching to container-specific algorithms. It combines cardinality-aware representation choices, fast bit operations, and in-place aggregation to improve throughput.
- Dispatch: Sorted first-level arrays compare container keys in O(n1 + n2) time, after which matching containers perform a second-level union or intersection.Every nonempty result container is added with its common key.
- Bitmap operations: Bitmap-container unions iterate over 1024 64-bit words, compute OR operations, and count result bits with Long.bitCount.The corresponding routine writes a new bitmap container and returns its cardinality.
- Throughput: 700 million 64-bit words per second versus 500 million when maintaining cardinality: the estimated cardinality penalty is about 30%.WAH and Concise additionally decode word types before each bitwise operation.
- Intersections: Intersections first count set bits in 1024 AND results, then emit either a bitmap or an array according to the 4096 threshold.Set bits can be extracted on the fly using the optimized conversion routine.
- Mixed containers: Bitmap-versus-array intersections scan the sorted array and test membership in the bitmap, while unions copy the bitmap and set array values.This avoids processing the full bitmap when one container is sparse.
- Array operations: Array intersections use simple merge when cardinalities are within 64× and galloping search when one array is much smaller.Galloping search skips comparisons by advancing exponentially before binary searching.
- Memory optimization: In-place operations avoid allocating and initializing new memory areas.They are available for selected bitmap-bitmap and array-bitmap unions and intersections.
- Aggregation: For unions of many bitmaps, containers with equal keys are grouped in a priority queue and merged in place, with cardinality computed once at the end.The largest-cardinality container is cloned as the starting accumulator.
5. EXPERIMENTS
The experiments compare Roaring with BitSet, WAH, and Concise on synthetic and real data, measuring storage, bitmap operations, and updates. Roaring generally provides strong space savings and speed, while specific data distributions create exceptions.
- Synthetic experiments: Roaring used 50% of Concise’s space and 25% of WAH’s space on sparse synthetic bitmaps.
- Synthetic experiments: Roaring intersections were 4–5 times faster than Concise and WAH across tested synthetic densities.For moderate densities, Roaring unions were 30% faster than Concise and WAH.
- Synthetic experiments: Roaring required less time than WAH and Concise for sorted insertions and performed much better for random removals.WAH and Concise do not support efficient random-order insertion like Roaring.
- Real-data experiments: CENSUS2000 was omitted because its average bitmap cardinality was 30 over a universe of 37 019 068, an ill-suited bitmap scenario.In this scenario, Roaring used 4× as much memory as Concise but was about 4× faster for intersections.
- Real-data experiments: On real data, Roaring was always faster on average than WAH and Concise, and it was 40× smaller than BitSet on CENSUS1881 and WIKILEAKS.On two other data sets, BitSet was more than twice as fast as Roaring but used three times as much memory.
- Real-data experiments: Roaring was up to 900× faster than the alternatives on CENSUS1881, especially when intersecting sparse and dense bitmaps.The result was attributed to large differences in bitmap cardinalities.
6. CONCLUSION
Roaring is presented as a compact two-level bitmap index that often outperforms WAH and Concise, while the authors identify data-ordering cases where those alternatives may compress better. The paper also points to information retrieval as a future application area.
- Roaring stores bitmap entries as 32-bit integers in a space-efficient two-level index.
- Roaring often uses less memory and is faster than the competitive WAH and Concise compression schemes.
- When data contains long runs of consecutive values, Concise or WAH may offer better compression ratios than Roaring.
- Even when alternatives compress better on ordered data such as WIKILEAKS, Roaring might still be faster.
- The authors plan to investigate further information-retrieval applications, noting that Apache Lucene adopted a Roaring format in version 5.0.