Posted in Cloud & Infrastructure, Engineering

Roaring Bitmaps and Bitmap Indexes Explained: Fast Filtering in Analytics Databases

Ask an analytics database “how many users are in the US, on the free plan, who logged in this week” and it needs to intersect three (or thirty) large sets of row IDs fast. A naive approach — scanning every row and checking each predicate — doesn’t scale. The classic fix is a bitmap index: one bit per row per value, so filtering becomes a bitwise AND. The modern twist is Roaring Bitmaps, a compressed bitmap format that keeps the speed of a plain bitmap while using a fraction of the memory, and which now sits inside most of the analytics engines you’ve heard of — ClickHouse, Apache Druid, Lucene/Elasticsearch, Apache Spark, Pinot, and more.

AT A GLANCE

AspectDetail
What it isCompressed bitset data structure for representing sets of integers (e.g. row/document IDs)
License / projectApache License 2.0, open-source, reference implementations in Java, C/C++, Go, Rust, Python, JS, C#, and more — roaringbitmap.org
Core ideaSplits 32-bit integers into 65,536-value chunks; each chunk auto-picks the smallest of three container types (array, bitmap, or run)
Why it mattersEnables fast AND/OR/XOR/ANDNOT set operations directly on compressed data — no need to decompress first
Who uses itApache Lucene, Elasticsearch/OpenSearch, Apache Druid, ClickHouse, Apache Spark, Apache Pinot, Hive, Trino, Flink, Iceberg, Delta Lake, Redis, and products from Google, Netflix, Datadog
Good fit forLow/medium-cardinality filter columns, segment-level indexes in columnar/analytics databases, set-based retention/cohort analysis

Short Verdict

A bitmap index is a simple, powerful idea — one bit per row, per distinct value — that makes filtering and counting over large columns extremely cheap, as long as the uncompressed bitmaps don’t blow up your memory footprint on sparse or high-cardinality data. Roaring Bitmaps solve exactly that problem: by adapting storage per 65,536-value chunk instead of using one encoding for an entire column, Roaring keeps the random-access speed of an uncompressed bitmap while shrinking storage the way older run-length formats (WAH, EWAH, Concise) did — without their decompression overhead. That combination is why it’s become the de facto standard bitmap format across modern analytics and search engines.

What a Bitmap Index Actually Is

A bitmap index maps each distinct value in a column to a bitmap (a bit vector) the length of the table: bit i is 1 if row i has that value, 0 otherwise. Filtering on “country = US” becomes “look up the bitmap for US.” Combining predicates — “country = US AND plan = free” — becomes a bitwise AND of two bitmaps, which CPUs do extremely fast, word at a time. Counting matching rows is a population count (popcount) over the result. This is why bitmap indexes have traditionally been favored for low-to-medium cardinality columns (status flags, categories, countries, boolean tags) in data warehouses and OLAP systems, where B-tree indexes don’t help much and the set-intersection pattern dominates the query workload.

The catch is storage. A raw (uncompressed) bitmap for a billion-row table costs 125MB per distinct value, even if that value only matches a handful of rows. Classic compression schemes like WAH (Word-Aligned Hybrid), EWAH, and Concise solve the size problem using run-length encoding, but they typically have to be decompressed, at least partially, before you can perform bitwise operations or random access — which costs CPU time that eats into the speed advantage bitmaps are supposed to provide.

How Roaring Bitmaps Work

Roaring Bitmaps, introduced by Chambi, Lemire, Kaser, and Godin, take a different approach: instead of one compression strategy applied uniformly, a Roaring bitmap splits the 32-bit integer space into chunks of 65,536 consecutive values, and each chunk independently picks whichever of three container types is smallest:

  • Array container — used when a chunk is sparse (few set bits); stores the actual set values as a sorted array of 16-bit integers.
  • Bitmap container — used when a chunk is dense; stores a plain 8KB bitmap, giving O(1) access.
  • Run container — used when a chunk has long runs of consecutive set bits; stores (start, length) run pairs, similar in spirit to run-length encoding.

Because each container picks the most efficient representation for its own local data distribution, Roaring adapts automatically to sparse, dense, and clustered data within the same bitmap — no manual tuning required. Critically, AND, OR, XOR, and ANDNOT operations are implemented to work directly on whichever container types are involved, without first expanding everything into plain bitmaps. According to the project’s own benchmarks, this makes Roaring “often hundreds of times faster” than older formats like WAH, EWAH, and Concise, while also giving constant-time random access to individual bits — something compressed run-length formats generally can’t offer. A published serialization format also means a Roaring bitmap written by one language’s implementation (say, Java) can be read directly by another (say, Go or C), which matters when a search engine and an analytics pipeline need to interoperate.

Where It Shows Up in Real Databases

Apache Lucene (and therefore Elasticsearch/OpenSearch) uses Roaring-style bitsets for its doc ID sets and cached filters — small sets use a sparse array representation, larger/denser sets switch to a bitmap, mirroring Roaring’s core idea. Elastic has also documented using Roaring for its own filter caching and aggregations. Apache Druid, a column-oriented analytics database built for sub-second OLAP queries, uses compressed bitmap indexes — Roaring or a Druid-specific “Concise” format — as the default inverted index for its string-encoded dictionary columns; Druid’s own segment design docs describe choosing a bitmap index implementation per column to balance compression against AND/OR performance across segments. ClickHouse ships a dedicated family of bitmap functions (bitmapBuild, bitmapAnd, bitmapOr, bitmapXor, groupBitmap, and more) backed by the Roaring format, letting you build and intersect bitmaps directly in SQL for use cases like retention analysis and audience segmentation. The same format backs set operations inside Apache Spark, Apache Pinot, and several data-lake table formats (Iceberg, Delta Lake).

Comparison: Bitmap Index Approaches

FormatCompression strategyRandom accessOperate without decompressing?
Plain/uncompressed bitmapNoneO(1), fastestYes, but memory-expensive on sparse data
WAH / EWAH / ConciseRun-length encoding of wordsSlow (sequential scan)Partial — often needs decoding runs first
Roaring BitmapsPer-chunk adaptive (array/bitmap/run container)O(1) within containersYes — native operations per container type

Pros

  • Combines the compactness of compressed formats with near-uncompressed-bitmap speed.
  • Adapts automatically to sparse, dense, and clustered data without manual index tuning.
  • Cross-language, standardized serialization — portable between systems and libraries.
  • Battle-tested: embedded in Lucene, Druid, ClickHouse, Spark, Pinot, and others for years.

Cons / Trade-offs

  • Bitmap indexes in general still work best on low-to-medium cardinality columns; very high-cardinality columns (e.g. unique IDs) gain little and can even bloat storage.
  • Roaring’s container-switching logic adds implementation complexity compared with a plain bitmap — not something you’d hand-roll for a one-off script.
  • Write-heavy, highly randomized updates to individual bits can still be costlier than in a plain uncompressed bitmap, depending on container churn.
  • It’s a building block, not a query planner — the database still has to decide when a bitmap index is the right strategy versus a B-tree or a full scan.

Who It’s a Good Fit For

Engineers building or tuning OLAP/analytics systems, search indexes, or any workload dominated by set intersections/unions over large ID spaces — audience segmentation, retention cohorts, log/event filtering, faceted search — benefit most. If you’re evaluating or operating ClickHouse, Druid, Elasticsearch, or similar systems, understanding that a Roaring-backed bitmap index sits underneath your filter and aggregation queries helps explain why certain predicates (low-cardinality equality filters) are fast and others (range scans on high-cardinality numeric columns) are not.

Bottom Line

Bitmap indexes turn filtering into bitwise arithmetic, and Roaring Bitmaps make that arithmetic cheap at scale by compressing adaptively instead of uniformly. You rarely interact with Roaring directly unless you’re using ClickHouse’s bitmap functions or writing a custom data structure, but it’s quietly doing the heavy lifting behind fast filters and aggregations in most of the serious analytics and search engines in production today.

FAQ

Is a Roaring Bitmap the same thing as a bitmap index?
No. A bitmap index is the database concept (one bit per row per value). Roaring is a compressed data structure commonly used to store and operate on those bitmaps efficiently.

Why not just use an uncompressed bitmap?
Uncompressed bitmaps are fast but can waste enormous amounts of memory for sparse or high-cardinality columns — a billion-row table needs 125MB per distinct value stored as a plain bitmap, regardless of how few rows actually match.

Which databases use Roaring Bitmaps today?
Documented users include Apache Lucene (and Elasticsearch/OpenSearch), Apache Druid, ClickHouse, Apache Spark, Apache Pinot, Hive, Trino, Flink, and several data lake table formats like Iceberg and Delta Lake, per the RoaringBitmap project’s own list.

Do I need to implement Roaring myself to benefit from it?
No. If you use ClickHouse’s bitmap functions, or rely on Druid’s or Elasticsearch’s default indexing, you’re already using Roaring (or a closely related format) under the hood.

Does Roaring help with high-cardinality columns too?
Less so. Its advantage is adapting per-chunk between sparse and dense regions; a column where nearly every value is unique doesn’t compress well with any bitmap approach, and a different index structure (hash or B-tree) is usually a better fit.

Sources

Unknown's avatar

Author:

Innovations, logic & design thinking