StarRocks ds_hll_accumulate 深度解析DataSketches HyperLogLog 近似去重聚合函数【免费下载链接】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_hll_accumulate展开讲清它的语法、参数语义、返回类型与完整用法示例并深入到 BE 侧DataSketchesHll的源码实现解释log_k精度控制、HLL_4/6/8目标类型以及序列化/反序列化链路的工作原理。读完之后你将能够把任意列的值累积为可序列化、可合并、可跨分区/跨节点聚合的 HLL 草图sketch并基于ds_hll_combine与ds_hll_estimate完成大规模数据的近似去重统计。函数定位DataSketches HLL 函数族的累积器ds_hll_accumulate的作用是把输入表达式的值累积进一个 HyperLogLog 草图并返回序列化后的草图二进制VARBINARY。它是 StarRocks 基于 Apache DataSketches 实现的 HLL 近似去重函数族中的一员与ds_hll_combine、ds_hll_estimate、ds_hll_count_distinct配合形成完整的累积 → 合并 → 估算工作流ds_hll_accumulate将原始值累积进 HLL 草图产出 VARBINARY 序列化结果ds_hll_combine把多个已序列化的草图合并成一个草图见 ds_hll_combine 文档ds_hll_estimate从序列化草图中估算去重数量见 ds_hll_estimate 文档ds_hll_count_distinct一步到位的近似去重计数函数直接返回估计值见 ds_hll_count_distinct 文档。这种先累积出可存储、可传输的草图对象的设计使得 HLL 草图可以作为中间状态落表、跨批次或跨节点传递再进行 union 合并与基数估算这是它与直接返回 BIGINT 的ds_hll_count_distinct最本质的区别。语法与参数官方语法继承自 ds_hll_accumulate 文档sketch ds_hll_accumulate(expr) sketch ds_hll_accumulate(expr, log_k) sketch ds_hll_accumulate(expr, log_k, tgt_type)参数说明如下参数类型/取值默认值说明expr任意数据类型—要累积进草图的表达式列、字面量或表达式均可log_k整数范围[4, 21]17控制草图的精度与内存占用log_k越大寄存器越多精度越高内存也越大tgt_typeHLL_4/HLL_6/HLL_8HLL_6目标 HLL 类型决定草图寄存器位宽从源码可以印证这些默认值。BE 侧的常量定义在 be/src/types/constexpr.h 中DEFAULT_HLL_LOG_K 17第 32 行而 be/src/exprs/agg/data_sketch/ds_hll.h 中明确写出static const datasketches::target_hll_type DEFAULT_HLL_TGT_TYPE datasketches::HLL_6;即缺省目标类型为HLL_6。FE 侧在 fe/fe-core/src/main/java/com/starrocks/catalog/FunctionSet.java 中注册了三个重载单参、exprINT、exprINTVARCHAR均返回 VARBINARY、中间聚合状态也为 VARBINARY说明该函数支持多阶段聚合partial/final——草图本身即可作为聚合中间状态在节点间流转。返回类型与典型使用方式ds_hll_accumulate返回 VARBINARY内容是 DataSketches 的 HLL 草图序列化字节流。典型用法分两类作为聚合中间结果落表在GROUP BY中按维度生成草图列存入库后续对同一维度不同分区的草图用ds_hll_combine合并再用ds_hll_estimate求基数临时验证直接查看某列的草图对象或配合ds_hll_estimate快速得到近似去重数。完整示例继承自官方文档可直接运行-- 建测试表 CREATE TABLE t1 ( id BIGINT, province VARCHAR(64), age SMALLINT, dt VARCHAR(10) ) DUPLICATE KEY(id) DISTRIBUTED BY HASH(id) BUCKETS 3; -- 插入测试数据 INSERT INTO t1 SELECT generate_series, generate_series, generate_series % 100, 2024-07-24 FROM table(generate_series(1, 1000)); -- 基本用法单参数 SELECT ds_hll_accumulate(id) FROM t1; -- 自定义 log_k SELECT ds_hll_accumulate(province, 20) FROM t1; -- 同时指定 log_k 与 tgt_type SELECT ds_hll_accumulate(age, 12, HLL_6) FROM t1; -- GROUP BY 用法 SELECT dt, ds_hll_accumulate(id), ds_hll_accumulate(province, 20), ds_hll_accumulate(age, 12, HLL_6), ds_hll_accumulate(dt) FROM t1 GROUP BY dt ORDER BY 1 LIMIT 3;几点实操注意草图参数必须与后续ds_hll_combine/ds_hll_estimate中草图的log_k一致合并不同log_k的草图会失败或产生错误结果因此建议整条链路固定log_ktgt_type不同HLL_4位宽最小、HLL_8最大的草图同样不宜混用默认HLL_6是精度与体积的平衡选择返回的 VARBINARY 是二进制 blob如需肉眼查看可结合hex()等字符串函数以实际版本函数支持为准。源码级实现解析ds_hll_accumulate的 BE 实现核心是 be/src/exprs/agg/data_sketch/ds_hll.h 与 be/src/exprs/agg/data_sketch/ds_hll.cpp 中的DataSketchesHll类它包装了 DataSketches C 库的hll_sketch_alloc/hll_union_alloc。几个关键机制值得了解1. 输入经过哈希后喂给 union。update(uint64_t hash_value)的注释明确要求输入必须是哈希值// Add a hash value to this HLL value // NOTE: input must be a hash_value void update(uint64_t hash_value);也就是说聚合框架会先把expr的值哈希成 64 位整数再调用_sketch_union-update(hash_value)累加。这解释了为什么expr可以是任意数据类型——任何类型都能被统一哈希。2. 累积器内部是一个 union 对象草图惰性求值。DataSketchesHll持有hll_union_type成员get_hll_sketch()带_is_changed标记只有在状态变化后真正需要结果时才通过_sketch_union-get_result(_tgt_type)物化出hll_sketch。序列化时调用serialize_compact()即以紧凑格式输出草图字节流。3. 反序列化有严格的前缀校验。is_valid()检查序列化数据第一个字节是否为HLL_PREINTS、HASH_SET_PREINTS或LIST_PREINTS三种合法前缀之一防止把非法二进制误当草图处理deserialize()会重建hll_union并把读入的草图 union 进去这是ds_hll_combine等从 VARBINARY 恢复草图再合并能力的底层基础。4. 基数估算采用非 HIP 估计器。estimate_cardinality()的源码注释说明它刻意使用 composite非 HIPHistoric Inverse Probability估计器以避免 union 内部乱序标记未设置时 HIP 累积器带来的偏差——这属于ds_hll_estimate侧的细节但保证了累积→合并→估算全链路的估计一致性。5. 内存可计量。类内部使用STLCountingAllocatoruint8_t计数分配器并暴露mem_usage()说明草图的内存开销被纳入 BE 的内存计量体系log_k调大时草图体积的增长是可观测的。此外FE 解析层在 fe/fe-core/src/main/java/com/starrocks/sql/parser/SyntaxSugars.java 中还提供了一个兼容糖approx_count_distinct_hll_sketch(col)会被改写为ds_hll_count_distinct(col)方便从旧版 HLL 函数命名迁移过来的 SQL 平滑运行。与相近函数的选择建议只需要最终去重数、不需要复用中间草图直接用ds_hll_count_distinct(col[, log_k[, tgt_type]])一步到位返回 BIGINT需要跨分区/跨天/跨节点合并去重例如按天存草图、月末合并出全局 DAU用ds_hll_accumulate产草图落表 ds_hll_combine合并 ds_hll_estimate估算追求更高的估计质量且数据允许可关注同族的ds_theta_*系列函数仓库文档同目录下提供了ds_theta_accumulate、ds_theta_combine、ds_theta_count_distinct等Theta 草图在支持交集等更复杂集合运算上更有优势。小结ds_hll_accumulate是 StarRocks 中把列数据沉淀为可复用 HLL 草图的入口函数默认log_k17、tgt_typeHLL_6的参数语义在 BE 源码DEFAULT_HLL_LOG_K、DEFAULT_HLL_TGT_TYPE中有明确对应其内部经由哈希累积、union 合并、紧凑序列化三套机制保证了草图在多阶段聚合与跨实例流转中的正确性。理解expr 任意类型 → 哈希值 → HLL union → 紧凑序列化这条链路后你就能放心地把它用进按天落草图、周期性合并估算的大规模近似去重场景。【免费下载链接】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），仅供参考