Bitmap functions are commonly used in SQL databases to represent sets efficiently and accelerate set operations. They are especially useful for high-dimensional filtering and exact deduplication at large scale. Databend already supports a broad set of bitmap functions. For usage details, see the Databend bitmap function documentation. ` In distributed aggregation, a typical bitmap workflow looks like this: read many small bitmaps from many rows, aggregate them layer by layer, and eventually produce a larger bitmap that contains the final union, intersection, or other set result.

For example:

SELECT bitmap_intersect(user_tags)
FROM events
WHERE dt = '...';

Before this optimization, the execution path for this type of query could be simplified as:

row bytes -> deserialize RoaringTreemap -> aggregate state operate -> result

There are two obvious cost centers in this path:

• Bitmaps are usually stored as bytes. When a query touches many rows, deserializing every row into a full bitmap structure amplifies read and construction cost by row count. For bitmaps with only a few elements, it is better to compute directly on bytes or on a lightweight representation whenever possible.

• When two bitmaps are combined, the engine should reuse existing structures as much as possible. Rebuilding bitmap objects on every operation creates extra allocations and temporary objects.

Databend Workloads That Benefit

This optimization is especially useful for the following Databend workloads:

• User segmentation:

  bitmap_intersect
  

  /

  bitmap_union
  

  across different user tag groups.

• Behavioral analytics: computing sets for visits, clicks, purchases, and other events.

• Funnel analysis: intersecting user sets across funnel steps.

• Permission or resource set checks: quickly testing set containment or overlap.

• Large-scale low-cardinality aggregation: many rows contain small bitmaps that are eventually merged into one result.

These workloads share the same shape: the number of input rows is large, but each row-level bitmap is small. If every row is expanded into a full

RoaringTreemap

The purpose of

HybridBitmap

RoaringTreemap

HybridBitmap: One Representation for Small and Large Sets

Bitmap functions are mostly used in aggregation, where data often follows this pattern:

many small row-level bitmaps -> gradually larger aggregate result

Databend therefore represents bitmaps with two structures:

• SmallBitmap
  

  : represents small sets with

  smallvec
  

  , with low construction cost.

• RoaringTreemap
  

  : represents large sets with Roaring Bitmap, which is well suited for compressed high-cardinality sets and set operations.

The state transition is straightforward:

SmallBitmap -> threshold exceeded -> RoaringTreemap

SmallBitmap: Lower Construction Cost for Small Sets

SmallBitmap

When modified,

SmallBitmap

Because

SmallBitmap

In some operations such as

xor

RoaringTreemap: Compression and Fast Operations for Large Sets

RoaringTreemap

Compressed bitmaps matter in database systems. Without compression, large row-level bitmaps can introduce heavy read and compute overhead.

There are other mature compressed bitmap formats, such as Oracle BBC, WAH, and EWAH. However, these formats do not support efficient random access. Computing an intersection may require fully decompressing a large bitmap.

Roaring Bitmap takes a different approach: it partitions data into multiple containers. This makes it fast to check whether a value exists, while still providing good compression ratio and set operation performance in many workloads.

The trade-off is that, compared with

SmallBitmap

RoaringTreemap

With this hybrid representation, Databend can choose the right structure at different stages of computation. For example, in a

bitmap_intersect

• When reading row-level bitmaps, Databend keeps bytes in a small bitmap representation whenever possible.

• During result computation, Databend switches to

  RoaringTreemap
  

  only if the result grows.

• When one side is a

  RoaringTreemap
  

  and the other side is a serialized small bitmap, Databend tries to compute the intersection directly from the small bitmap bytes instead of fully deserializing every row into

  RoaringTreemap
  

  .

This reduces the read and construction cost of many small bitmaps, while preserving the performance benefits of

RoaringTreemap

Operation Matrix: Choosing the Right Computation Path

HybridBitmap

RoaringTreemap

RoaringTreemap

RoaringTreemap

union/xor

intersect/sub

contains

insert

remove

RoaringTreemap

RoaringTreemap

In aggregation workloads, inputs are usually read from columns as bytes. If every small row-level bitmap is first deserialized into a full

RoaringTreemap

By separating the

small

large

serialized small

RoaringTreemap

Benchmark: Faster Small-Bitmap Aggregation

Because benchmark coverage, function naming, and later implementation details differ before and after PR 19041, this section only shows small-bitmap aggregation paths that can be reproduced and aligned between the two versions.

The

bitmap_intersect

bitmap_union

bitmap_intersect_empty

bitmap_union_disjoint

bitmap_intersect/100000

bitmap_intersect/10000000

bitmap_union/100000

bitmap_union/10000000

bitmap_intersect_empty/100000

bitmap_intersect_empty/1000000

bitmap_union_disjoint/100000

bitmap_union_disjoint/1000000

These results cover several common paths: small bitmap intersection, union, fast convergence to an empty result, and disjoint union where the result keeps growing. The biggest gains appear when a large number of small bitmaps participate in aggregation.

Before the optimization, every row-level bitmap had to be deserialized into a full

RoaringTreemap

After the optimization,

SmallBitmap

RoaringTreemap

When This Optimization Helps Most

These benchmarks focus on aggregation over many small bitmaps. They do not imply the same speedup for every bitmap workload.

When input bitmaps or intermediate results quickly grow into large bitmaps, the bottleneck shifts back to large-set operations inside

RoaringTreemap

In other words,

HybridBitmap

Conclusion: Delay the Cost of Large Bitmaps

The bottleneck in bitmap aggregation does not always come from the set operation itself. Often, it comes from constructing a full large-set data structure too early for a very small set.

When many row-level small bitmaps participate in aggregation, deserialization, object construction, and memory allocation are all multiplied by row count. That can become a major part of query execution cost.

The core value of

HybridBitmap

RoaringTreemap

• Use

  SmallBitmap
  

  while the bitmap is still small, keeping construction and allocation overhead low.

• Switch to

  RoaringTreemap
  

  only when the set actually grows, and then rely on its compression and large-set operation performance.

This optimization does not replace Roaring Bitmap. It avoids using Roaring Bitmap before it is needed.

The benchmark results show that the most visible gains come from aggregating many small bitmaps, such as

bitmap_intersect

bitmap_union

RoaringTreemap

This makes

HybridBitmap

For Databend, this optimization is not only about making a few bitmap functions faster.

In a cloud data warehouse, many query costs come from repeatedly constructing, deserializing, and allocating small objects.

HybridBitmap

For users, the result is lower CPU usage, fewer memory allocations, more stable aggregation performance, and better cost-performance in user profiling, tag analytics, funnel analysis, and similar workloads.