典型场景：大量小 Bitmap 参与聚合
Bitmap 函数在 SQL 数据库中常用于高效表示和加速集合计算，广泛应用于海量数据下的高维过滤与精确去重场景。目前，Databend 已内置丰富的 bitmap 计算函数，具体用法可参考官方产品文档。
在分布式聚合场景中，Bitmap 的经典链路如下：从大量行中读入较小的 bitmap，然后对它们进行聚合计算；随着聚合层级向上递增，最终汇聚并输出一个包含完整交并集信息的大 Bitmap。例如：
复制代码SELECT bitmap_intersect(user_tags)
FROM events
WHERE dt = '...';
在优化前，这类查询的执行路径大致可以简化为：
复制代码row bytes -> deserialize RoaringTreemap -> aggregate state operate -> result
这个流程存在两个明显的成本点：
- Bitmap 主要以 bytes 形式存储。当涉及大量行的计算时，每行 bitmap 都需要反序列化为完整结构，这会使读取和构造成本被行数显著放大。对于元素数量极少的 bitmap，更理想的方式是尽量直接基于 bytes 或轻量结构完成计算，避免不必要的开销。
- 两个 bitmap 进行计算时，需要尽可能复用已有结构，避免每次都重新构建一个新的 bitmap，否则会产生大量内存分配和临时对象成本，影响整体性能。
适合哪些 Databend 查询场景
这类优化尤其适合以下 Databend 使用场景：
- 用户标签圈选：对不同标签人群执行
bitmap_intersect/bitmap_union操作； - 行为分析：计算访问、点击、购买等事件集合的聚合结果；
- 漏斗分析：按步骤求用户集合的交集，分析转化路径；
- 权限或资源集合计算：快速判断集合之间的包含关系，提高查询效率；
- 大规模低基数聚合：大量行内的小 bitmap 汇聚成一个结果 bitmap，减少重复构造。
这些场景有一个共同特征：输入行数很大，但每行 bitmap 很小。如果每一行都构造成完整的 RoaringTreemap，查询成本就会被行数放大。HybridBitmap 的设计初衷，就是让小 bitmap 尽量停留在轻量表示里，只有在结果真正膨胀时再切换到 RoaringTreemap，从而降低整体计算开销。
HybridBitmap：小集合与大集合的分层表示
Bitmap 函数主要应用于聚合场景，而这些场景往往伴随着“大量行内小 bitmap → 聚合结果逐步变大”的数据形态。因此，Databend 的 Bitmap 采用了两种结构进行混合表示：
- SmallBitmap：使用 smallvec 表示小集合，构造成本低，适合低基数数据。
- RoaringTreemap：使用 Roaring Bitmap 表示大集合，擅长高基数集合的压缩和高效计算。
状态切换遵循一条简单的规则：
复制代码SmallBitmap → 超过阈值 → RoaringTreemap
SmallBitmap：降低小集合构造成本
SmallBitmap 采用特殊的 vec 结构：默认元素数量较少时使用栈上空间，避免堆分配；当超出阈值后，再转换为堆上动态存储。SmallBitmap 在修改时会通过 binary search 保证元素有序且唯一，从而保持与常规 bitmap 一致的集合语义。
由于 SmallBitmap 主要依赖栈上空间，当行内 bitmap 较小时，可以以极低的成本完成反序列化和构造，大幅提升大量小 bitmap 的读取效率。同时，在 xor 这类中间结果可能变小的计算中，也可以尝试将大 bitmap 转回小 bitmap，减少后续的物化成本。
RoaringTreemap：承接大集合压缩与计算
RoaringTreemap 是一种压缩位图算法，广泛应用于 Spark、Hive、Lucene 等高性能计算框架。相关论文可参考：arxiv.org/pdf/1603.06…。
压缩 bitmap 对数据库系统至关重要，否则行内 bitmap 较大时可能带来严重的读取和计算开销。虽然也存在 Oracle BBC、WAH、EWAH 等成熟的压缩位图格式，但这些格式不支持高效的随机访问，计算交集时可能需要完整解压整个大 bitmap。
Roaring Bitmap 的独特之处在于将数据分割为多个块，允许快速检查某个值是否存在，同时在许多场景下也能提供出色的计算性能和压缩比。当然，相比于 SmallBitmap，它在低基数小集合上的构造成本仍然偏高。
基于这种混合结构，可以在不同计算阶段选择不同的表示方式。例如，在大多数行内 bitmap 都较小的 bitmap_intersect 场景下：
- 读取行内 bitmap 时，尽量以 small bitmap 的形式表示 bytes，避免过早反序列化。
- 进行结果计算时，如果结果逐步膨胀，再切换为 RoaringTreemap。
- 当一侧是 RoaringTreemap、另一侧是 serialized small bitmap 时，尽量直接基于 small bitmap bytes 与 RoaringTreemap 做 intersect，减少不必要的转换。
这既可以利用 SmallBitmap 降低大量小 bitmap 的读取和构造成本，也能保留 RoaringTreemap 在大集合计算上的优势，实现性能的平衡。
操作矩阵：不同状态下的计算路径
HybridBitmap 的核心思路并非要替代 RoaringTreemap，而是在不同数据规模下选择最合适的计算路径，避免小 bitmap 过早承担完整 RoaringTreemap 的构造成本。
| 左侧状态 | 右侧状态 | 处理策略 |
|---|---|---|
| Small | Small | 直接在有序 small vec 上执行集合运算，避免构造 RoaringTreemap |
| Small | Large | 根据操作语义决定是否提升为 Large，例如 union/xor 可能需要膨胀，intersect/sub 可以优先保留小集合 |
| Large | Small | 遍历 small 集合，对 Large 执行 contains、insert 或 remove 等局部操作 |
| Large | Large | 直接使用 RoaringTreemap 原生集合运算，发挥其高性能优势 |
| Large | serialized small | 尽量直接基于序列化 bytes 计算，减少将每行小 bitmap 完整反序列化为 RoaringTreemap 的成本 |
在聚合场景下，输入通常以 bytes 的形式从列中读取。如果每一行都先反序列化成完整 RoaringTreemap，再参与聚合计算，实际成本会远高于集合本身的大小。
通过区分 small、large 和 serialized small 的计算路径，可以让小 bitmap 尽量停留在低成本的表示中，只在结果真正膨胀时再切换到 RoaringTreemap，从而显著降低整体开销。
Benchmark：小 Bitmap 聚合性能提升
由于 PR 19041 前后的 benchmark 覆盖、函数命名和后续版本实现都有差异，这里只展示能够在两个版本之间复现并对齐的小 bitmap 聚合路径。其中 bitmap_intersect 使用 PR 19041 summary 中已有数据，bitmap_union、bitmap_intersect_empty 和 bitmap_union_disjoint 是基于相同思路在 PR 19041 前后本地补测的数据。
| Benchmark | PR 19041 前 median | PR 19041 后 median | 性能提升 |
|---|---|---|---|
bitmap_intersect/100000 |
15.27 ms | 4.729 ms | 69.0% |
bitmap_intersect/10000000 |
1.609 s | 533.1 ms | 66.9% |
bitmap_union/100000 |
19.67 ms | 7.628 ms | 61.2% |
bitmap_union/10000000 |
2.009 s | 831.9 ms | 58.6% |
bitmap_intersect_empty/100000 |
11.81 ms | 4.197 ms | 64.5% |
bitmap_intersect_empty/1000000 |
122.9 ms | 41.56 ms | 66.2% |
bitmap_union_disjoint/100000 |
36.61 ms | 7.236 ms | 80.2% |
bitmap_union_disjoint/1000000 |
345.5 ms | 84.98 ms | 75.4% |
这些结果覆盖了小 bitmap 交集、并集、快速收敛为空，以及互不相交并集持续膨胀的几类路径。收益最明显的，就是大量小 bitmap 参与聚合计算的场景。
优化前，每行 bitmap 都需要反序列化为完整 RoaringTreemap，即使每行只有几个元素，也要承担较高的构造成本；优化后，SmallBitmap 可以直接以低成本结构表示，并在计算过程中减少完整 RoaringTreemap 的创建，因此能够显著降低 CPU 与内存分配的开销。
适用边界：什么时候收益最明显
这些 benchmark 主要验证的是大量小 bitmap 聚合的路径，并不代表所有 bitmap 场景都有同等收益。当输入 bitmap 或中间结果很快膨胀为大 bitmap 时，性能瓶颈会重新回到 RoaringTreemap 的大集合运算本身，此时优化收益会逐渐趋于平缓。
因此，HybridBitmap 最适合的不是“所有 bitmap 计算”，而是输入数据中存在大量小集合、且聚合过程中结果逐步变化的场景，例如用户画像、标签分析等典型应用。
总结：延迟支付大 Bitmap 的成本
Bitmap 聚合的性能瓶颈，很多时候并不来自集合运算本身，而是来自“为了处理一个很小的集合，过早构造了一个完整的大集合结构”。在大量行内小 bitmap 参与聚合的场景下，每一行的反序列化、对象构造和内存分配都会被行数放大，最终成为查询执行中的主要成本。
HybridBitmap 的核心价值在于延迟支付 RoaringTreemap 的成本：当 bitmap 还很小的时候，使用 SmallBitmap 保持低构造、低分配的表示；当集合真正膨胀后，再切换到 RoaringTreemap，继续利用它在大集合压缩和集合运算上的优势。这个优化并非要替换 Roaring Bitmap，而是避免在不需要 Roaring Bitmap 的阶段过早使用它，从而提升整体效率。
从 benchmark 结果看，收益最明显的，是大量小 bitmap 聚合的场景，例如 bitmap_intersect 和 bitmap_union。当然，当输入 bitmap 或中间结果很快膨胀为大集合时，性能瓶颈会重新回到 RoaringTreemap 的大集合运算本身，优化收益也会逐渐趋于平缓。
也正因为如此，HybridBitmap 更像是对 bitmap 生命周期进行分层建模：小集合用轻量结构承接，高基数集合交还给压缩位图处理，各取所长。
对于 Databend 来说，这类优化的意义不只是让某几个 bitmap 函数跑得更快。在云数仓场景下，很多查询成本来自大量细小对象的重复构造、反序列化和内存分配。HybridBitmap 体现的是 Databend 一贯的优化方向：尽量让执行路径贴近真实 workload，在不牺牲通用性的前提下，减少不必要的数据结构转换和计算开销。
最终，这会体现在用户能感知到的层面上：更低的 CPU 消耗、更少的内存分配、更稳定的聚合性能，以及在用户画像、标签分析、漏斗分析等场景中更好的 cost-performance。
