Databend introduces HybridBitmap, a new internal representation that keeps small bitmaps as lightweight SmallBitmap structures and only promotes them to RoaringTreemap once a size threshold is exceeded. This avoids deserializing every row-level bitmap into a full Roaring Bitmap during aggregation, cutting allocation and construction overhead. Benchmarks across bitmap_intersect, bitmap_union, bitmap_intersect_empty, and bitmap_union_disjoint show 58-80% median latency improvements after PR 19041, with the biggest gains in workloads dominated by many small bitmaps such as user segmentation, behavioral analytics, and funnel analysis. The optimization does not help when bitmaps quickly grow large, since RoaringTreemap operations then dominate the cost.
Table of contents
Databend Workloads That BenefitHybridBitmap: One Representation for Small and Large SetsSmallBitmap: Lower Construction Cost for Small SetsRoaringTreemap: Compression and Fast Operations for Large SetsOperation Matrix: Choosing the Right Computation PathBenchmark: Faster Small-Bitmap AggregationWhen This Optimization Helps MostConclusion: Delay the Cost of Large BitmapsQuestions this post answers
How much faster is bitmap aggregation in Databend after the HybridBitmap optimization in PR 19041?
Median latency dropped by 58% to 80% across common bitmap aggregation paths after PR 19041. For example, bitmap_intersect went from 15.27 ms to 4.729 ms (69% improvement), and bitmap_union_disjoint dropped from 345.5 ms to 84.98 ms (75.4% improvement), with the largest gains seen when many small bitmaps are aggregated together. Track database performance optimizations like Databend's bitmap work as they land, on daily.dev.
What is HybridBitmap in Databend and how does it differ from using RoaringTreemap directly?
HybridBitmap is a representation that starts as a lightweight SmallBitmap backed by smallvec for small sets and only switches to RoaringTreemap once a size threshold is exceeded. Unlike always deserializing into RoaringTreemap, this avoids unnecessary allocation and construction cost when most row-level bitmaps in an aggregation are small, while still using Roaring Bitmap's compression once sets grow large. Developers choosing bitmap data structures for analytics workloads can follow these design tradeoffs on daily.dev.
When does the HybridBitmap optimization in Databend not help performance?
It provides little benefit when input bitmaps or intermediate aggregation results quickly grow into large bitmaps, because the bottleneck then shifts to large-set operations inside RoaringTreemap itself rather than construction and deserialization cost. The optimization specifically targets workloads with many small, row-level bitmaps rather than uniformly large ones. Engineers evaluating whether an optimization fits their workload shape can compare notes on daily.dev.