StarRocks ds_theta_intersect 标量函数详解：基于 Apache DataSketches Theta 的集合交集基数估计

StarRocks ds_theta_intersect 标量函数详解基于 Apache DataSketches Theta 的集合交集基数估计【免费下载链接】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本篇技术指南聚焦 StarRocks 提供的标量函数ds_theta_intersect讲解如何在不存储底层明细数据的前提下对两列序列化的 Apache DataSketches Theta sketch 执行逐行pairwise交集运算并通过ds_theta_estimate得到|A ∩ B|的近似基数。读者读完本文后将掌握该函数的语法、返回语义、底层实现原理、空值与 NULL 边界行为以及它与其他 ds_theta 系列函数accumulate / combine / union / a_not_b在真实业务场景中的组合用法。函数定位为 Theta sketch 提供集合运算能力ds_theta_intersect是 StarRocks 在 标量函数目录 中提供的 Apache DataSketches Theta sketch 标量集合运算函数之一与其同族的还有ds_theta_union并集、ds_theta_a_not_b差集和ds_theta_estimate基数估计。与 HyperLogLogHLL类 sketch 不同Theta sketch 保留了足够的内部状态来支持交集运算这正是ds_theta_intersect能够在不存储底层原始值的情况下完成集合交集的根本原因。对于 HLL sketch通常只能做并集合并与基数估计而 Theta sketch 基于保留一个随机采样子集 theta 阈值的结构天然支持交、并、差三种集合操作从而让两个群体重叠度分析这类需求可以完全在 sketch 层面完成。该函数在 StarRocks BEBackend中的实现位于 ds_theta_functions.cpp由DsThetaFunctions类声明见 ds_theta_functions.h提供直接复用 Apache DataSketches C 库的datasketches::theta_intersection_alloc。语法与参数VARBINARY ds_theta_intersect(sketch_a, sketch_b)参数类型说明sketch_aVARBINARY序列化后的 compact Theta sketchsketch_bVARBINARY序列化后的 compact Theta sketch返回值VARBINARY一个新的 compact Theta sketch其去重基数估计\|A ∩ B\|两个入参必须是compact 形式的 Theta sketch 序列化字节不是原始值也不是非 compact 的 update sketch 状态返回值同样是 compact 形式的序列化 sketch可继续作为其他 ds_theta 系列函数的输入进行链式组合。官方示例群体重叠度分析原文档给出的经典场景是同时出现在 cohort A 与 cohort B 中的去重用户数-- Distinct users who appeared in both cohort A and cohort B. SELECT ds_theta_estimate(ds_theta_intersect(a.sk, b.sk)) FROM cohort_a a JOIN cohort_b b USING (day);其执行逻辑可以拆解为两层ds_theta_intersect(a.sk, b.sk)对每一行配对执行一次交集输出一个新的 sketch外层ds_theta_estimate将该 sketch 解析并返回其去重基数估计DOUBLE类型。ds_theta_estimate的完整说明见 ds_theta_estimate.md它接受任意符合 Apache DataSketches C compact theta 格式默认哈希种子的 sketch包括由本函数产生的结果。返回值语义NULL、空 sketch 与错误处理从 ds_theta_intersect 的实现 与测试用例 ds_theta_test.cpp 可以归纳出完整的返回规则输入情形行为任一侧为 SQLNULL返回NULLTestIntersectNullInput验证任一侧为零长度VARBINARY空切片返回一个真实的有效空 sketch非 NULL估计值为 0两侧均为非空合法 sketch返回交集后的 compact sketch输入非法/损坏的字节如随机字符串抛出内部错误Status::InternalError不会静默吞掉关键点在于零长度切片与空 sketch的区别零长度切片没有 8 字节的 sketch 头而合法的空 sketch 带有is_empty() true的头信息。实现中针对a_slice.size 0 || b_slice.size 0的分支会直接构造一个空的 compact sketch 返回注释为empty ∩ X empty而不是去调用wrap()解析从而规避了at least 8 bytes expected的解析异常保证∅ ∩ X ∅的集合代数语义在任何输入下都成立——这正是测试TestIntersectBothEmpty、TestIntersectOneEmpty覆盖的回归场景。底层原理从源码看交集是怎么算出来的ds_theta_intersect的逐行实现非常直接ds_theta_functions.cpp用ColumnViewerTYPE_VARBINARY逐行读取左右两列任一侧为 NULL 则builder.append_null()对空切片走短路分支返回空 sketch否则通过wrapped_compact_theta_sketch::wrap(data, size)就地解析输入字节wrap只解析头部不拷贝数据创建datasketches::theta_intersection_allocalloc_type实例使用datasketches::DEFAULT_SEED作为哈希种子依次update()两个 sketch调用inter.get_result()得到结果 sketch经append_compact序列化后写入结果ColumnBuilderTYPE_VARBINARY。几个值得注意的实现细节默认哈希种子互操作性ds_theta_functions.h 明确指出本函数族使用 Apache DataSketches C 标准 compact 序列化格式与默认哈希种子datasketches::DEFAULT_SEED因此结果与任何基于相同默认构建的 Apache DataSketches 实现互通——例如从 Parquet、Iceberg 等外部数据源加载的 sketch 字节可以直接喂给本函数参与运算。内存计数所有 sketch 内存都通过STLCountingAllocatoruint64_t见 ds_theta.h分配并累计到局部变量mem便于在大查询中精确追踪该函数的内存开销。异常收敛wrap()在遇到损坏字节时会抛异常被捕获后转换为带函数名的Status::InternalError如ds_theta_intersect failed: ...而不是返回一个误导性的空结果。空输入与 NULL 的工程细节一个值得借鉴的健壮性设计尽管函数文档只承诺NULL 输入返回 NULLStarRocks 的实现和测试在空值与边界输入上做了远超文档要求的防御性处理TestEstimateEmptySketchInput零长度 VARBINARY非 SQL NULL在ds_theta_estimate中估计值为 0TestIntersectBothEmpty/TestIntersectOneEmpty交集两侧任意为空结果都是估计值为 0 的有效空 sketch且不会报错TestANotBSerializedEmptySketchRhs/TestANotBSerializedEmptySketchLhs针对ds_theta_a_not_b中序列化空 sketch 参与运算可能触发 null 计数器分配器解引用导致段错误的隐患做了专门回归说明 ds_theta 系列在空 sketch 路径上经过了细致的打磨TestCombineRejectsMalformedInput/TestIntersectCondAggRejectsMalformedInput损坏输入必须显式报错保证数据损坏可见、可诊断。这些用例集中在 ds_theta_test.cpp 中是理解该函数边界行为的权威参考。实战组合从原始值到交集估计的完整链路ds_theta_intersect只负责两个 sketch 求交集sketch 从哪来官方生态给出的推荐链路是构建 sketch用聚合函数 ds_theta_accumulate 对原始列按组构建 sketch 并落表CREATE TABLE sketches AS SELECT grp, ds_theta_accumulate(id) AS sk FROM t GROUP BY grp;跨行合并按需用聚合函数 ds_theta_combine 将多行 sketch 合并为一张SELECT year(day), ds_theta_estimate(ds_theta_combine(daily_sk)) FROM daily_sketches GROUP BY year(day);集合运算用ds_theta_intersect或ds_theta_union/ds_theta_a_not_b做两两运算再用ds_theta_estimate输出基数。一个把并集与交集同时算出的典型写法来自 ds_theta_estimate.md 的示例SELECT ds_theta_estimate(ds_theta_union(a.sk, b.sk)) AS u, ds_theta_estimate(ds_theta_intersect(a.sk, b.sk)) AS i FROM cohort_a a JOIN cohort_b b USING (day);如果需要按组做锚定集合 ∩ 窗口集合的条件交集聚合StarRocks 还提供了聚合变体ds_theta_intersect_cond_agg见 ds_theta_intersect_cond_agg.md其 BE 实现位于 ds_theta_intersect_cond.h测试覆盖了分组内多锚点、多窗口、序列化/反序列化往返等场景TestIntersectCondAgg*系列。使用注意事项输入必须是 compact 序列化 sketch直接传入原始值或非标准字节会触发解析错误需先经ds_theta_accumulate构建。预哈希差异ds_theta_accumulate 在写入 DataSketches 之前会对输入值做预哈希因此 StarRocks 累积产生的 sketch 与基于同一批原始值由外部工具构建的 sketch之间做集合运算结果不正确。正确做法是只对由同一累积路径产生的 sketch 执行ds_theta_intersect、ds_theta_union、ds_theta_a_not_b。近似性Theta sketch 的估计是近似值精度由 sketch 的lg_k参数决定。从测试注释看默认lg_k12在 95% 置信区间下约有 3.125% 的相对误差测试中采用 ±10% 的宽松界以保证不抖动见 ds_theta_test.cpp 中TestMergeDisjointSets的说明。NULL 传播任一输入为 NULL 即返回 NULL在 JOIN 场景下需留意USING (day)的匹配行为。小结ds_theta_intersect是 StarRocks ds_theta 标量函数族中的核心成员它以纯 sketch 层面的运算替代了取出明细、在内存中求交集、再去重计数的重型方案让|A ∩ B|的近似估计在亚秒级完成且完全兼容 Apache DataSketches 标准 compact 序列化格式。配合ds_theta_accumulate/ds_theta_combine/ds_theta_estimate可以构建出一整套面向用户重叠、漏斗分析、渠道归因等场景的低成本基数分析管线。【免费下载链接】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），仅供参考