StarRocks ds_theta_a_not_b 函数详解基于 Theta Sketch 的集合差运算【免费下载链接】starrocksThe worlds 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/starrocksds_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类型的紧凑compactTheta Sketch 作为输入与输出载体通过估算而非精确计算的方式在亚线性内存下完成基数distinct count度量。与 HyperLogLogHLL不同Theta Sketch 保留了足够的内部状态以支持集合间的交、并、差运算这正是ds_theta_a_not_b无需保存原始明细数据即可完成集合差计算的前提。与之配套的标量函数还包括ds_theta_estimate读取序列化 sketch 并返回其去重基数估计值DOUBLEds_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)参数说明参数类型说明sketch_aVARBINARY作为被减集合的 compact theta sketchsketch_bVARBINARY作为减集合的 compact theta sketch返回值返回一个新的序列化 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);该查询的执行链路为ds_theta_a_not_b(a.sk, b.sk)逐行对两个 sketch 求差集输出一个序列化的 compact sketch外层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并针对边界情况做了精细处理。整体执行流程如下使用ColumnViewerTYPE_VARBINARY逐行读取两个输入列任一行输入为NULL时输出行写入NULL对应文档中任一输入为 NULL 返回 NULL的语义通过wrapped_compact_theta_sketch::wrap()解析输入字节该方法会校验 sketch 头部遇到畸形输入会抛出异常并被捕获随后以Status::InternalError形式返回ds_theta_a_not_b failed: ...错误信息对非空场景调用theta_a_not_b_type::compute(a, b)计算结果并通过append_compact序列化为 compact sketch 写入结果列。值得关注的是代码中对空 sketch 的短路short-circuit处理这些分支在语义上对应集合论的恒等式同时在实现上规避了上游库的一个潜在缺陷输入状态数学语义实现行为sketch_a为空字节串∅ \ X ∅直接构造并返回一个空 compact sketchsketch_a为序列化空 sketch非零长度∅ \ X ∅直接复用输入的sketch_a字节sketch_b为空字节串X \ ∅ X直接复用输入的sketch_a字节sketch_b为序列化空 sketch非零长度X \ ∅ X直接复用输入的sketch_a字节两者均为非空|A \ B|调用compute(a, b)求差并序列化代码注释解释了短路的必要性theta_a_not_b::compute()的捷径路径会使用wrapped_compact_theta_sketch::get_allocator()构建结果——这是一个字节计数器为空指针的默认构造STLCountingAllocator若此时再对该结果序列化会解引用空指针导致段错误segfault。因此 StarRocks 在进入compute()之前显式拦截所有空 sketch 场景。上述边界行为在 ds_theta_test.cpp 中有对应的单元测试覆盖TestANotBEmptyLhssketch_a为空字节串时结果估计为 0TestANotBEmptyRhssketch_b为空字节串时结果估计与输入sketch_a的估计一致约 500TestANotBSerializedEmptySketchRhssketch_b为序列化空 sketch 时同样返回sketch_a本身TestANotBSerializedEmptySketchLhssketch_a为序列化空 sketch 时结果估计为 0。与内存控制相关的实现细节从代码结构看sketch 运算的每一次分配都经由STLCountingAllocatoruint64_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()上报内存占用的同一套机制。使用注意事项输入必须为标准 compact theta sketch函数不会对任意字节做宽容处理畸形输入会以错误而非空结果形式上报便于尽早发现数据链路中的 sketch 损坏问题。结果是近似估计ds_theta_a_not_b返回的是基于 theta sampling 的基数估计最终数值需要通过ds_theta_estimate解析对精度要求极高的小基数场景建议结合业务对误差的容忍度评估是否适用。输出为 sketch可继续组合不要试图直接对返回值做数值运算应继续用ds_theta_estimate解析或用ds_theta_union/ds_theta_intersect进一步参与集合运算。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用户可以自由组合并、交、差等集合语义构建出完整的近似集合分析管线。KeywordsDS_THETA_A_NOT_B, DS_THETA_UNION, DS_THETA_INTERSECT, DS_THETA_ESTIMATE, DS_THETA_ACCUMULATE, DS_THETA_COMBINE【免费下载链接】starrocksThe worlds 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 StarRocks ds_theta_a_not_b 函数详解：基于 Theta Sketch 的集合差运算
StarRocks ds_theta_a_not_b 函数详解基于 Theta Sketch 的集合差运算【免费下载链接】starrocksThe worlds 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/starrocksds_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类型的紧凑compactTheta Sketch 作为输入与输出载体通过估算而非精确计算的方式在亚线性内存下完成基数distinct count度量。与 HyperLogLogHLL不同Theta Sketch 保留了足够的内部状态以支持集合间的交、并、差运算这正是ds_theta_a_not_b无需保存原始明细数据即可完成集合差计算的前提。与之配套的标量函数还包括ds_theta_estimate读取序列化 sketch 并返回其去重基数估计值DOUBLEds_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)参数说明参数类型说明sketch_aVARBINARY作为被减集合的 compact theta sketchsketch_bVARBINARY作为减集合的 compact theta sketch返回值返回一个新的序列化 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);该查询的执行链路为ds_theta_a_not_b(a.sk, b.sk)逐行对两个 sketch 求差集输出一个序列化的 compact sketch外层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并针对边界情况做了精细处理。整体执行流程如下使用ColumnViewerTYPE_VARBINARY逐行读取两个输入列任一行输入为NULL时输出行写入NULL对应文档中任一输入为 NULL 返回 NULL的语义通过wrapped_compact_theta_sketch::wrap()解析输入字节该方法会校验 sketch 头部遇到畸形输入会抛出异常并被捕获随后以Status::InternalError形式返回ds_theta_a_not_b failed: ...错误信息对非空场景调用theta_a_not_b_type::compute(a, b)计算结果并通过append_compact序列化为 compact sketch 写入结果列。值得关注的是代码中对空 sketch 的短路short-circuit处理这些分支在语义上对应集合论的恒等式同时在实现上规避了上游库的一个潜在缺陷输入状态数学语义实现行为sketch_a为空字节串∅ \ X ∅直接构造并返回一个空 compact sketchsketch_a为序列化空 sketch非零长度∅ \ X ∅直接复用输入的sketch_a字节sketch_b为空字节串X \ ∅ X直接复用输入的sketch_a字节sketch_b为序列化空 sketch非零长度X \ ∅ X直接复用输入的sketch_a字节两者均为非空|A \ B|调用compute(a, b)求差并序列化代码注释解释了短路的必要性theta_a_not_b::compute()的捷径路径会使用wrapped_compact_theta_sketch::get_allocator()构建结果——这是一个字节计数器为空指针的默认构造STLCountingAllocator若此时再对该结果序列化会解引用空指针导致段错误segfault。因此 StarRocks 在进入compute()之前显式拦截所有空 sketch 场景。上述边界行为在 ds_theta_test.cpp 中有对应的单元测试覆盖TestANotBEmptyLhssketch_a为空字节串时结果估计为 0TestANotBEmptyRhssketch_b为空字节串时结果估计与输入sketch_a的估计一致约 500TestANotBSerializedEmptySketchRhssketch_b为序列化空 sketch 时同样返回sketch_a本身TestANotBSerializedEmptySketchLhssketch_a为序列化空 sketch 时结果估计为 0。与内存控制相关的实现细节从代码结构看sketch 运算的每一次分配都经由STLCountingAllocatoruint64_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()上报内存占用的同一套机制。使用注意事项输入必须为标准 compact theta sketch函数不会对任意字节做宽容处理畸形输入会以错误而非空结果形式上报便于尽早发现数据链路中的 sketch 损坏问题。结果是近似估计ds_theta_a_not_b返回的是基于 theta sampling 的基数估计最终数值需要通过ds_theta_estimate解析对精度要求极高的小基数场景建议结合业务对误差的容忍度评估是否适用。输出为 sketch可继续组合不要试图直接对返回值做数值运算应继续用ds_theta_estimate解析或用ds_theta_union/ds_theta_intersect进一步参与集合运算。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用户可以自由组合并、交、差等集合语义构建出完整的近似集合分析管线。KeywordsDS_THETA_A_NOT_B, DS_THETA_UNION, DS_THETA_INTERSECT, DS_THETA_ESTIMATE, DS_THETA_ACCUMULATE, DS_THETA_COMBINE【免费下载链接】starrocksThe worlds 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考