What If Your Bitmap Knew Its Own Density?
Bitmap indexes power analytics queries across billions of rows. But the dominant implementation treats all data the same: fixed boundaries, uniform containers, no adaptation. What if the bitmap could see its own density distribution?
Roaring bitmaps are one of the most successful data structures in modern analytics. They also make a decision so deeply embedded in their design that most people never question it: every container boundary falls at a multiple of 65,536. This post is about what that decision costs.
If you've used Apache Druid, Apache Pinot, ClickHouse, or any system that filters across millions of rows, you've relied on bitmap indexes. The dominant implementation, Roaring Bitmap, partitions the 32-bit integer space into fixed chunks of 2^16 values. Each chunk gets a container. The container type (array, bitmap, or run-length) depends on density, but the boundaries themselves are arithmetic: 0-65535, 65536-131071, 131072-196607, and so on.
Simple, fast, predictable, and completely blind to the data it holds.
The Assumption That Became Invisible
Fixed boundaries assume uniform data distribution. Real analytics data is almost never uniform.
The 2^16 partitioning scheme was designed for a world where the integer set is the primary concern and the data topology is secondary. It works well when values are reasonably distributed across the integer space. But analytics data has structure.
Time-series data clusters around recent timestamps. Geographic data clusters by region. User behavior data follows power laws: a few users generate most of the events, a few products receive most of the views. When you map these patterns onto fixed 65,536-value chunks, you get a mismatch between where the boundaries are and where they should be.
Dense regions, where thousands of values pack into a small range, get split across multiple containers, each partially filled. Sparse regions, where values are scattered across a wide range, create containers that are mostly empty. The boundary placement has nothing to do with the data. It's an arithmetic convenience.
Consider a Druid segment with a user_id dimension. If user IDs are sequential integers starting from 1, the first container (IDs 0-65535) might hold 50,000 values while the next dozen containers hold a few hundred each. The dense container is nearly full. The sparse containers waste memory on metadata that exceeds the data itself.
Now consider the same segment with a city dimension. Dictionary-encoded city IDs might cluster around popular cities: IDs 0-50 represent cities with millions of events, while IDs 51-10000 represent cities with dozens. Fixed boundaries can't express this. They partition uniformly regardless of how the data is actually distributed.
The overhead isn't just memory. Every set operation (AND, OR, XOR) iterates over containers. Empty or near-empty containers still participate in the iteration. When two bitmaps have different density profiles mapped onto the same fixed boundaries, the set operation processes containers that contribute nothing to the result.
What Analytics Engines Build Around It
Production analytics engines compensate for uniform partitioning with layers of external infrastructure. The compensation works, but it reveals what the bitmap itself is missing.
Apache Druid stores each dimension column's bitmap index inside a segment. Because roaring bitmaps have no concept of time, Druid partitions data into time-based segments externally. A query for "events in the last hour" first prunes irrelevant segments, then runs bitmap operations on the survivors. The segment granularity (hourly, daily, monthly) is a global configuration that can't adapt to different data densities within the same time range.
Because roaring bitmaps don't manage their own size, Druid recommends segment sizes of 300-700MB and provides tuning parameters for target rows per segment. DBAs monitor segment sizes and adjust configurations. When real-time ingestion creates many small segments, a background compaction process rebuilds them into larger ones, reconstructing every bitmap from scratch.
Because roaring bitmaps use the same container representation regardless of access patterns, Druid offers a segment-level choice between roaring and concise compression. One choice, applied uniformly to every bitmap in the segment, decided at ingestion time before any queries arrive.
Each of these compensations is a well-engineered solution to a structural limitation. Time-based partitioning compensates for the bitmap's lack of temporal awareness. Segment sizing compensates for the bitmap's inability to self-regulate. Compaction compensates for the bitmap's inability to consolidate cold data incrementally. The compression choice compensates for the bitmap's inability to adapt to workload.
The Coordinator service, one of Druid's most complex subsystems, exists largely to manage segment lifecycle. Segments need to be created, loaded, replicated, compacted, and eventually dropped. Much of this complexity traces back to a single root cause: the bitmap has no concept of hot versus cold data, so the infrastructure around it must handle temperature externally.
The same pattern appears across the analytics ecosystem. Pinot's segment compaction, ClickHouse's merge tree optimization, Elasticsearch's segment merging inside Lucene. All external lifecycle management for data structures that don't manage their own lifecycle.
The Missing Properties
Three properties would change the equation: density-aware boundaries, thermal state per region, and self-managing compression. Roaring provides none of them.
Density-aware boundaries. If container boundaries derived from the data's actual distribution rather than arithmetic intervals, dense regions would consolidate into fewer containers and sparse regions would merge into larger but sparser ones. Set operations would process fewer containers, and each container would carry more useful data.
Thermal state. If each container tracked how recently and frequently it was accessed, the bitmap could maintain fast representations for hot containers and compressed representations for cold ones, within a single bitmap, without external compaction. A query that touches only recent data would interact only with hot containers. Historical data would self-compress.
Self-managing compression. If the bitmap could transition containers between representations based on workload (array for tiny sets, bitmap for dense regions, run-length for sequential ranges, deep compression for cold data), the "roaring vs. concise" configuration choice would disappear. The bitmap would choose, per container, at runtime.
These aren't independent features. They compose. Density-aware boundaries create containers that match data topology, which makes thermal tracking meaningful (temperature varies by container, not uniformly). Thermal state enables intelligent compression selection (hot containers prioritize speed, cold containers prioritize space). Self-managing compression feeds back into density awareness (compressed containers occupy less memory, allowing boundary drift to adapt).
Can a bitmap with these properties be fast enough? Self-description and thermal management have costs: per-container metadata, boundary computation, state machine transitions. If those costs exceed the savings, roaring's simplicity plus the external infrastructure wins.
These are measurable claims. The answer turns out to be more interesting than we expected.
What's Next
In an upcoming post, we'll show benchmark results comparing a bitmap with these properties against roaring at scale. The numbers will speak for themselves, including the operations where the new approach loses.
We're not proposing that roaring bitmaps are obsolete. Roaring is a remarkable piece of engineering that runs in production at staggering scale. But for analytics workloads where data has topology, where temperature varies, and where the operational cost of external lifecycle management matters, there might be a bitmap that can handle more of this internally.
As always, we'll publish everything. The wins, the losses, and the "wait, why is contains() slower at 100K?" investigations that the commit history preserves.
Related Posts
Nacre Array Benchmarks: The Numbers
We promised the full benchmark numbers. Here they are: every operation, every scale, wins and losses. Vec is still faster at some things. Nacre Array is faster at others. The crossover points tell the real story.
Nacre Array: What If Your Vec Had a Spine?
Mother-of-pearl is 3,000 times tougher than the crystals it's made of. The secret is layered organization with flexible mortar between rigid segments. We built an array that works the same way.
What Happens When Bitmap Boundaries Listen to the Data?
What if bitmap container boundaries adapted to data density instead of falling at fixed intervals? We benchmarked 14 operations at three scales to find out. The results surprised us in both directions.
Why Nature Builds Better Arrays
Every system that stores sequential data eventually hits the same wall: cold data costs the same as hot, inserts require shifting everything, and there's no way to split without copying. What if the structure itself knew the difference?
Why Your Data Structure Doesn't Have a Metabolism
Data structures are benchmarked at birth, compared as static objects, and optimized for a single moment in time. But biological systems invest in costly metabolic machinery that pays off across a lifecycle. What if the overhead isn't the problem, but the investment?