Databend通过Bitmap优化加速大规模集合聚合

典型场景：大量小 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 的构造成本。

在聚合场景下，输入通常以 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 前后本地补测的数据。

这些结果覆盖了小 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。