导读本文介绍 Databend 针对 Bitmap 聚合场景的一次性能优化通过引入 HybridBitmap在小集合阶段使用轻量的 SmallBitmap只在集合真正膨胀后切换到 RoaringTreemap避免大量小 bitmap 被过早反序列化和构造成完整大集合结构。Benchmark 显示在大量小 bitmap 聚合场景下bitmap_intersect、bitmap_union等函数获得了显著性能提升。阅读时间约 6-8 分钟。典型场景大量小 Bitmap 参与聚合Bitmap 函数在 SQL 数据库中常用于高效表示和加速集合计算广泛应用于海量数据下的高维过滤与精确去重场景。目前Databend 已支持丰富的 bitmap 计算函数具体用法可参考产品文档。在分布式聚合场景中Bitmap 的经典链路为从大量行中读取较小的 bitmap并对它们做聚合计算随着聚合层级向上递增最终汇聚并输出一个包含完整交并集信息的大 Bitmap。例如SELECTbitmap_intersect(user_tags)FROMeventsWHEREdt...;在优化前这类查询的执行路径通常可以简化为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 → 超过阈值 → RoaringTreemapSmallBitmap降低小集合构造成本SmallBitmap 使用一种特殊的 vec 结构表示默认在元素数量较少时使用栈上空间当超出阈值后再转换为堆上动态存储。SmallBitmap 在修改时会通过 binary search 保证元素有序且唯一从而保持与常规 bitmap 一致的集合语义。由于 SmallBitmap 主要依赖栈上空间在行内 bitmap 较小时可以以极低成本完成反序列化和构造从而提高大量小 bitmap 的读取效率。同时在xor等中间结果可能变小的计算中也可以尝试将大 bitmap 转回小 bitmap减少后续物化成本。RoaringTreemap承接大集合压缩与计算RoaringTreemap 是一种压缩位图算法广泛应用于 Spark、Hive、Lucene 等高性能计算框架。相关论文可参考https://arxiv.org/pdf/1603.06549。压缩 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 的构造成本。左侧状态右侧状态处理策略SmallSmall直接在有序 small vec 上做集合运算避免构造 RoaringTreemapSmallLarge根据操作语义决定是否提升为 Large例如 union/xor 可能需要膨胀intersect/sub 可以优先保留小集合LargeSmall遍历 small 集合对 Large 做 contains、insert 或 remove 等局部操作LargeLarge直接使用 RoaringTreemap 原生集合运算Largeserialized small尽量直接基于序列化 bytes 计算减少将每行小 bitmap 完整反序列化为 RoaringTreemap 的成本在聚合场景下输入通常以 bytes 的形式从列中读取。对于大量行内小 bitmap如果每一行都先反序列化成完整 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 前后本地补测的数据。BenchmarkPR 19041 前 medianPR 19041 后 median性能提升bitmap_intersect/10000015.27 ms4.729 ms69.0%bitmap_intersect/100000001.609 s533.1 ms66.9%bitmap_union/10000019.67 ms7.628 ms61.2%bitmap_union/100000002.009 s831.9 ms58.6%bitmap_intersect_empty/10000011.81 ms4.197 ms64.5%bitmap_intersect_empty/1000000122.9 ms41.56 ms66.2%bitmap_union_disjoint/10000036.61 ms7.236 ms80.2%bitmap_union_disjoint/1000000345.5 ms84.98 ms75.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。
