StarRocks ds_theta_a_not_b 函数详解：基于 Theta Sketch 的集合差运算

StarRocks ds_theta_a_not_b 函数详解：基于 Theta Sketch 的集合差运算

【免费下载链接】starrocksThe world's fastest open query engine for sub-second analytics both on and off the data lakehouse. With the flexibility to support nearly any scenario, StarRocks provides best-in-class performance for multi-dimensional analytics, real-time analytics, and ad-hoc queries. A Linux Foundation project.项目地址: https://gitcode.com/GitHub_Trending/st/starrocks

ds_theta_a_not_b是 StarRocks 提供的标量（Scalar）集合运算函数，用于对两个已序列化的 Apache DataSketches Theta Sketch 执行集合差运算，返回|A \ B|（属于 sketch A 但不属于 sketch B 的元素）的去重基数估计。本文以官方函数文档为主线，结合 StarRocks 后端 C++ 实现与单元测试，讲解其语法、行为语义、边界条件处理以及在实际用户画像、人群圈选场景中的组合用法。

函数定位：Theta Sketch 集合运算家族的一员

ds_theta_a_not_b属于 StarRocks 的 Theta Sketch 标量函数家族。该家族以VARBINARY类型的紧凑（compact）Theta Sketch 作为输入与输出载体，通过估算而非精确计算的方式，在亚线性内存下完成基数（distinct count）度量。与 HyperLogLog（HLL）不同，Theta Sketch 保留了足够的内部状态以支持集合间的交、并、差运算，这正是ds_theta_a_not_b无需保存原始明细数据即可完成集合差计算的前提。

与之配套的标量函数还包括：

• ds_theta_estimate：读取序列化 sketch 并返回其去重基数估计值（DOUBLE）；
• ds_theta_union：两两求并集，估算|A ∪ B|；
• ds_theta_intersect：两两求交集，估算|A ∩ B|；
• ds_theta_a_not_b：两两求差集，估算|A \ B|。

在聚合侧，StarRocks 还提供了ds_theta_accumulate（从原始值构建 sketch）、ds_theta_combine（跨行合并 sketch）、ds_theta_count_distinct与ds_theta_intersect_cond_agg等聚合函数，用于 sketch 的构建与批量合并。从后端代码看，这些函数的注册位于 aggregate_resolver_approx.cpp，而ds_theta_combine、ds_theta_intersect_cond_agg等均在其中完成注册。

语法与参数说明

ds_theta_a_not_b的完整语法如下：

VARBINARY ds_theta_a_not_b(sketch_a, sketch_b)

参数说明：

返回值：

• 返回一个新的序列化 compact sketch，其去重基数估计值为|A \ B|，即存在于sketch_a中但不存在于sketch_b中的元素个数；
• 任一输入为NULL时返回NULL。

函数的输入输出均为 Apache DataSketches 标准的 C++ compact theta sketch 二进制格式（使用默认哈希种子），因此不仅可以消费本仓库聚合函数产出的 sketch，也可以读取由外部 Apache DataSketches 生态（如 Parquet、Iceberg 中的 sketch 列）写入的VARBINARY数据。

使用示例：人群差集分析

官方文档给出的典型场景是计算"出现在人群 A 中、但未出现在人群 B 中的去重用户数"。以下示例将 cohort 表按day关联后，对两列 sketch 做差集并输出估计值：

-- Distinct users in cohort A who did not appear in cohort B. SELECT ds_theta_estimate(ds_theta_a_not_b(a.sk, b.sk)) FROM cohort_a a JOIN cohort_b b USING (day);

该查询的执行链路为：

1. ds_theta_a_not_b(a.sk, b.sk)逐行对两个 sketch 求差集，输出一个序列化的 compact sketch；
2. 外层ds_theta_estimate(...)解析该结果 sketch 并返回其基数估计值（DOUBLE）。

由于ds_theta_a_not_b返回的是 sketch 而非数值，它天然支持与其它集合运算组合嵌套。例如可以构造更复杂的表达："A 中不包含于 B，且不包含于 C"的估计：

SELECT ds_theta_estimate( ds_theta_a_not_b( ds_theta_a_not_b(a.sk, b.sk), c.sk ) ) FROM cohort_a a JOIN cohort_b b USING (day) JOIN cohort_c c USING (day);

也可以在求差之前先对右侧做并集合并，表达"A 减去 B 与 C 的并集"：

SELECT ds_theta_estimate( ds_theta_a_not_b( a.sk, ds_theta_union(b.sk, c.sk) ) ) FROM cohort_a a JOIN cohort_b b USING (day) JOIN cohort_c c USING (day);

行为语义与边界条件：源码级解析

ds_theta_a_not_b的底层实现位于 ds_theta_functions.cpp 的DsThetaFunctions::ds_theta_a_not_b中。该实现基于 Apache DataSketches 的datasketches::theta_a_not_b_alloc（引入自datasketches/theta_a_not_b.hpp），并针对边界情况做了精细处理。

整体执行流程如下：

1. 使用ColumnViewer<TYPE_VARBINARY>逐行读取两个输入列；
2. 任一行输入为NULL时，输出行写入NULL（对应文档中"任一输入为 NULL 返回 NULL"的语义）；
3. 通过wrapped_compact_theta_sketch::wrap()解析输入字节；该方法会校验 sketch 头部，遇到畸形输入会抛出异常并被捕获，随后以Status::InternalError形式返回"ds_theta_a_not_b failed: ..."错误信息；
4. 对非空场景调用theta_a_not_b_type::compute(a, b)计算结果，并通过append_compact序列化为 compact sketch 写入结果列。

值得关注的是代码中对空 sketch 的短路（short-circuit）处理，这些分支在语义上对应集合论的恒等式，同时在实现上规避了上游库的一个潜在缺陷：

代码注释解释了短路的必要性：theta_a_not_b::compute()的捷径路径会使用wrapped_compact_theta_sketch::get_allocator()构建结果——这是一个字节计数器为空指针的默认构造STLCountingAllocator，若此时再对该结果序列化，会解引用空指针导致段错误（segfault）。因此 StarRocks 在进入compute()之前显式拦截所有空 sketch 场景。

上述边界行为在 ds_theta_test.cpp 中有对应的单元测试覆盖：

• TestANotBEmptyLhs：sketch_a为空字节串时结果估计为 0；
• TestANotBEmptyRhs：sketch_b为空字节串时，结果估计与输入sketch_a的估计一致（约 500）；
• TestANotBSerializedEmptySketchRhs：sketch_b为序列化空 sketch 时同样返回sketch_a本身；
• TestANotBSerializedEmptySketchLhs：sketch_a为序列化空 sketch 时结果估计为 0。

与内存控制相关的实现细节

从代码结构看，sketch 运算的每一次分配都经由STLCountingAllocator<uint64_t>（定义于 ds_theta.h），并以局部变量int64_t mem = 0作为计数器的地址传入theta_union_type::builder(alloc_type(&mem)).build()或theta_a_not_b_type构造函数。这意味着每个函数调用周期内的 sketch 内存占用都会被精确记账并随作用域释放，避免了长生命周期聚合状态下内存无限增长的问题。这也是聚合侧DataSketchesTheta类通过mem_usage()上报内存占用的同一套机制。

使用注意事项

1. 输入必须为标准 compact theta sketch：函数不会对任意字节做宽容处理，畸形输入会以错误（而非空结果）形式上报，便于尽早发现数据链路中的 sketch 损坏问题。
2. 结果是近似估计：ds_theta_a_not_b返回的是基于 theta sampling 的基数估计，最终数值需要通过ds_theta_estimate解析；对精度要求极高的小基数场景，建议结合业务对误差的容忍度评估是否适用。
3. 输出为 sketch，可继续组合：不要试图直接对返回值做数值运算，应继续用ds_theta_estimate解析，或用ds_theta_union/ds_theta_intersect进一步参与集合运算。
4. NULL 语义：任一输入为NULL时结果即为NULL，在 JOIN 场景中需注意关联键的匹配情况对结果行数的影响。

总结

ds_theta_a_not_b为 StarRocks 提供了基于 Theta Sketch 的原生集合差运算能力，它把 Apache DataSketches 的近似基数估计与 SQL 标量表达式无缝衔接，使得"用户人群 A 减去人群 B"这类分析可以完全在 SQL 层完成，而无需物化明细数据。配合ds_theta_union、ds_theta_intersect以及聚合侧的ds_theta_accumulate/ds_theta_combine，用户可以自由组合并、交、差等集合语义，构建出完整的近似集合分析管线。

Keywords

DS_THETA_A_NOT_B, DS_THETA_UNION, DS_THETA_INTERSECT, DS_THETA_ESTIMATE, DS_THETA_ACCUMULATE, DS_THETA_COMBINE

【免费下载链接】starrocksThe world's fastest open query engine for sub-second analytics both on and off the data lakehouse. With the flexibility to support nearly any scenario, StarRocks provides best-in-class performance for multi-dimensional analytics, real-time analytics, and ad-hoc queries. A Linux Foundation project.项目地址: https://gitcode.com/GitHub_Trending/st/starrocks