尧图网页设计 
StarRocks HLL_CARDINALITY 函数详解HLL 基数估算的读取与底层实现【免费下载链接】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 标量函数HLL_CARDINALITY展开讲解如何从单个 HLLHyperLogLog类型的值中估算基数distinct 数量并结合 hll.h、hll.cpp 等后端源码剖析其存储格式演进与估算算法。读完本文你将掌握HLL_CARDINALITY的语法、返回值、典型用法理解它与hll_hash、hll_union_agg等函数如何配合完成 UV独立访客类去重统计并了解 StarRocks 在内存与存储层面为 HLL 所做的大量优化。函数定位HLL 体系中的读取端StarRocks 的 HLL 是一套完整的数据类型与函数体系。HLLHyperLogLog是一种以固定内存开销估算超大集合基数的近似算法其核心价值在于只保存固定大小的寄存器register数据即可在毫秒级估算出海量去重值个数且无需保存原始数据。整套体系在仓库中对应文件包括标量函数hll_cardinality.md、hll_hash.md、hll_empty.md聚合函数hll_union_agg.md、hll_union.md、hll_raw_agg.mdBE 端实现hyperloglog_functions.cpp、hll.h、hll.cpp单元测试hll_test.cpp。在这套体系中HLL_CARDINALITY承担读取/估算职责它接收一个已经构建好的 HLL 值可能来自hll_hash的转换结果、表中 HLL 列、或hll_union_agg的聚合结果返回该集合的基数估算值。语法与返回值HLL_CARDINALITY的完整语法如下HLL_CARDINALITY(hll)参数说明参数类型说明hllHLL一个 HLL 类型的值通常来自 HLL 类型的表列、hll_hash()的返回结果或hll_union_agg()的聚合结果返回值类型为BIGINT即估算出的集合基数。值得注意的边界行为若传入的 HLL 为空集例如由hll_empty()生成的空 HLL返回0若 HLL 处于 EXPLICIT显式存储格式即集合内哈希值不超过 160 个时直接返回精确的元素个数见 hll.cpp 中estimate_cardinality()对HLL_DATA_EXPLICIT分支的处理。官方示例与扩展用法原文档给出了在 MySQL 客户端中的典型查询MySQL select HLL_CARDINALITY(uv_set) from test_uv; --------------------------- | hll_cardinality(uv_set) | --------------------------- | 3 | ---------------------------其中uv_set是表中一个 HLL 类型的列值为3表示该集合的基数估算为 3。与 hll_hash 配合即时构建并估算HLL_CARDINALITY最常见的搭档是hll_hash。hll_hash将一个普通值字符串等通过 murmur hash 转为 HLL 类型二者组合即可在不建表的情况下快速验证mysql select hll_cardinality(hll_hash(a)); -------------------------------- | hll_cardinality(hll_hash(a)) | -------------------------------- | 1 | --------------------------------hll_hash的源码见 hyperloglog_functions.cpp对每行输入调用HashUtil::murmur_hash64A计算 64 位哈希再通过hll.update(hash)写入 HLL。注意它在内部已做哈希因此使用hll_hash后无需再对同一值重复 hash。与 hll_empty 配合空值兜底当某行没有可统计的 HLL 值时可用hll_empty()生成空 HLL 作为默认值补位插入与导入均支持空 HLL 被HLL_CARDINALITY估算时返回 0insert into hllDemo(k1,v1) values(10,hll_empty());与 hll_union_agg 配合全量 UV 统计在报表场景中通常先用hll_union_agg合并多行 HLL 值再用HLL_CARDINALITY读取最终基数。聚合函数文档中的经典示例MySQL select HLL_UNION_AGG(uv_set) from test_uv; ------------------------- | HLL_UNION_AGG(uv_set) | ------------------------- | 17721 | -------------------------hll_union_agg的返回值本身就是 HLL 类型若要拿到可读的基数数值需再套一层HLL_CARDINALITY。仓库的统计结果写出器statistic_result_writer.cpp也采用了hll_cardinality(hll_union(...))的嵌套写法来输出 distinct 统计值。底层原理HyperLogLog 的存储格式演进理解HLL_CARDINALITY的返回值需要先理解 StarRocks HLL 的存储设计。为节省空间hll.h 声明 HLL 值根据集合规模在四种格式间转换枚举值格式触发条件最大占用空间HLL_DATA_EMPTY(0)空集合集合为空1 字节HLL_DATA_EXPLICIT(1)显式存储哈希值哈希值数量 ≤ 1601 1 160×8 1282 字节HLL_DATA_SPARSE(2)只存非零寄存器索引值非零寄存器数 ≤ 40961 4 3×4096 12293 字节HLL_DATA_FULL(3)存储全部寄存器非零寄存器数超过 40961 16384 字节关键常量定义在 constexpr.hconstexpr int HLL_COLUMN_PRECISION 14; // 精度对应 2^14 16384 个寄存器 constexpr int HLL_EXPLICLIT_INT64_NUM 160; // EXPLICIT 格式元素上限 constexpr int HLL_SPARSE_THRESHOLD 4096; // SPARSE 序列化阈值 constexpr int HLL_REGISTERS_COUNT 16 * 1024; // 寄存器总数一个 HLL 值只允许沿empty - explicit - sparse - full单向演进不允许回退源码注释明确说明这些枚举值会持久化到存储设备不可变更。内存中 SPARSE 与 FULL 的实现相同二者差异主要体现在序列化编码时见 hll.cpp当非零寄存器数大于 4096 时采用 FULL 编码直接拷贝 16384 字节否则采用 SPARSE 编码每个非零寄存器用 2 字节索引 1 字节值表示。基数估算算法的源码级解析HLL_CARDINALITY在 BE 端的执行路径非常直接。函数声明见 hyperloglog_functions.h实现见 hyperloglog_functions.cppDEFINE_UNARY_FN_WITH_IMPL(hllCardinalityImpl, hll_ptr) { return hll_ptr-estimate_cardinality(); } StatusOrColumnPtr HyperloglogFunctions::hll_cardinality(FunctionContext* context, const starrocks::Columns columns) { return VectorizedStrictUnaryFunctionhllCardinalityImpl::evaluateTYPE_HLL, TYPE_BIGINT(columns[0]); }即入参为TYPE_HLL列逐行取出HyperLogLog对象并调用estimate_cardinality()输出TYPE_BIGINT。真正的估算逻辑位于 hll.cpp其流程分三档空集直接返回0EXPLICIT 格式返回哈希集合的元素个数精确值SPARSE/FULL 格式走经典 HyperLogLog 估算——按寄存器数量选取经验常数alpha16384 个寄存器时alpha 0.7213 / (1 1.079 / 16384)通过 65 项谐波均值表harmomic_tables计算调和平均当估算值E num_streams * 2.5且存在零寄存器时改用**线性计数Linear Counting**提升小基数精度当num_streams 16384且estimate 72000时套用四阶多项式偏差校正该修正思路参考了 Redis 的实现以平滑线性计数切换为 HyperLogLog 时的波动。值得指出estimate_cardinality()返回的是经过std::lround取整的近似值。官方文档明确说明 HLL 估算误差约为 1%因此它适合替代COUNT(DISTINCT)以大幅降低内存与计算开销但不适合需要精确去重计数的场景。性能优化细节寄存器更新与合并StarRocks 对 HLL 寄存器操作做了多层优化这些细节决定了HLL_CARDINALITY背后数据写入与合并的速度寄存器更新_update_registershll.h用哈希值低 14 位定位寄存器索引再取剩余高位中首个置 1 位的位置max保留更大值寄存器合并 SIMD 化merge_registers_impl在 hll.cpp 中为 AVX-512、AVX2、SSE4.2 分别提供_mm512_max_epu8/_mm256_max_epu8/_mm128_max_epu8的向量化逐字节取 max 实现并通过MFV_*宏按 CPU 能力自动分派普通路径则退化为逐字节比较寄存器内存管理寄存器缓冲区仅在真正需要时分配HLL_REGISTERS_COUNT即 16KB且可通过set_registers_allocator注册进程级自定义分配器hll.cpp便于在统一的 MemChunk 池中管理反序列化安全校验deserialize与is_validhll.cpp会校验编码类型、长度及 SPARSE 索引是否越界防止恶意或损坏数据导致越界写入。测试验证hll_test.cpp 中的行为确认BE 单元测试 hll_test.cpp 对上述行为做了系统验证可作为理解HLL_CARDINALITY语义的参考空 HLL 序列化后长度为 1estimate_cardinality()返回0第 95-112 行100 个哈希值处于 EXPLICIT 格式序列化长度为1 1 100 * 8估算值精确等于100第 113-141 行超过阈值后转换到 SPARSE/FULL 格式且合并更多元素后估算值单调增长第 171-235 行非法输入空 Slice、未知类型、长度不符会被is_valid拒绝反序列化失败的对象估算值回落为0第 83-112、286 行。使用场景与注意事项推荐场景UV 统计业务表将用户 ID 列通过hll_hash在导入时构造成 HLL 列如col1hll_hash(user_id)按天/小时聚合后用hll_union_agg合并、hll_cardinality读取实现任意时间窗口的独立访客去重大规模去重加速当COUNT(DISTINCT)因基数极大导致内存或耗时超标时用 HLL 方案换取约 1% 误差下的数量级性能提升指标中间态存储HLL 可作为表的值列详见 hll_union_agg.md通过聚合压缩数据量、加速查询其可合并特性让预聚合结果可以在查询期继续合并。注意事项HLL_CARDINALITY的入参必须是 HLL 类型直接传入普通字符串需要先用hll_hash转换返回值为近似值误差约 1%对精确性要求严苛的场景如对账不适合使用HLL 类型列在导入时用hll_hash指定来源列、用hll_empty()兜底空值导入映射示例见 hll_empty.md否则无法生成合法 HLL 数据空集或反序列化失败的对象会估算为0若数据链路异常如导入格式错误需结合is_valid类校验手段排查数据质量问题。小结HLL_CARDINALITY是 StarRocks HLL 体系中把算法结果翻译成业务指标的最后一环。它的语法极简但背后的价值来自整套 HyperLogLog 工程实现单向演进的四种存储格式、约 1% 误差的估算修正、SIMD 化的寄存器合并以及完整的序列化安全校验。将它与hll_hash写入端、hll_union_agg合并端、hll_empty兜底端组合使用即可在 StarRocks 中构建一套高性价比的海量去重统计方案。【免费下载链接】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 HLL_CARDINALITY 函数详解：HLL 基数估算的读取与底层实现
StarRocks HLL_CARDINALITY 函数详解HLL 基数估算的读取与底层实现【免费下载链接】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 标量函数HLL_CARDINALITY展开讲解如何从单个 HLLHyperLogLog类型的值中估算基数distinct 数量并结合 hll.h、hll.cpp 等后端源码剖析其存储格式演进与估算算法。读完本文你将掌握HLL_CARDINALITY的语法、返回值、典型用法理解它与hll_hash、hll_union_agg等函数如何配合完成 UV独立访客类去重统计并了解 StarRocks 在内存与存储层面为 HLL 所做的大量优化。函数定位HLL 体系中的读取端StarRocks 的 HLL 是一套完整的数据类型与函数体系。HLLHyperLogLog是一种以固定内存开销估算超大集合基数的近似算法其核心价值在于只保存固定大小的寄存器register数据即可在毫秒级估算出海量去重值个数且无需保存原始数据。整套体系在仓库中对应文件包括标量函数hll_cardinality.md、hll_hash.md、hll_empty.md聚合函数hll_union_agg.md、hll_union.md、hll_raw_agg.mdBE 端实现hyperloglog_functions.cpp、hll.h、hll.cpp单元测试hll_test.cpp。在这套体系中HLL_CARDINALITY承担读取/估算职责它接收一个已经构建好的 HLL 值可能来自hll_hash的转换结果、表中 HLL 列、或hll_union_agg的聚合结果返回该集合的基数估算值。语法与返回值HLL_CARDINALITY的完整语法如下HLL_CARDINALITY(hll)参数说明参数类型说明hllHLL一个 HLL 类型的值通常来自 HLL 类型的表列、hll_hash()的返回结果或hll_union_agg()的聚合结果返回值类型为BIGINT即估算出的集合基数。值得注意的边界行为若传入的 HLL 为空集例如由hll_empty()生成的空 HLL返回0若 HLL 处于 EXPLICIT显式存储格式即集合内哈希值不超过 160 个时直接返回精确的元素个数见 hll.cpp 中estimate_cardinality()对HLL_DATA_EXPLICIT分支的处理。官方示例与扩展用法原文档给出了在 MySQL 客户端中的典型查询MySQL select HLL_CARDINALITY(uv_set) from test_uv; --------------------------- | hll_cardinality(uv_set) | --------------------------- | 3 | ---------------------------其中uv_set是表中一个 HLL 类型的列值为3表示该集合的基数估算为 3。与 hll_hash 配合即时构建并估算HLL_CARDINALITY最常见的搭档是hll_hash。hll_hash将一个普通值字符串等通过 murmur hash 转为 HLL 类型二者组合即可在不建表的情况下快速验证mysql select hll_cardinality(hll_hash(a)); -------------------------------- | hll_cardinality(hll_hash(a)) | -------------------------------- | 1 | --------------------------------hll_hash的源码见 hyperloglog_functions.cpp对每行输入调用HashUtil::murmur_hash64A计算 64 位哈希再通过hll.update(hash)写入 HLL。注意它在内部已做哈希因此使用hll_hash后无需再对同一值重复 hash。与 hll_empty 配合空值兜底当某行没有可统计的 HLL 值时可用hll_empty()生成空 HLL 作为默认值补位插入与导入均支持空 HLL 被HLL_CARDINALITY估算时返回 0insert into hllDemo(k1,v1) values(10,hll_empty());与 hll_union_agg 配合全量 UV 统计在报表场景中通常先用hll_union_agg合并多行 HLL 值再用HLL_CARDINALITY读取最终基数。聚合函数文档中的经典示例MySQL select HLL_UNION_AGG(uv_set) from test_uv; ------------------------- | HLL_UNION_AGG(uv_set) | ------------------------- | 17721 | -------------------------hll_union_agg的返回值本身就是 HLL 类型若要拿到可读的基数数值需再套一层HLL_CARDINALITY。仓库的统计结果写出器statistic_result_writer.cpp也采用了hll_cardinality(hll_union(...))的嵌套写法来输出 distinct 统计值。底层原理HyperLogLog 的存储格式演进理解HLL_CARDINALITY的返回值需要先理解 StarRocks HLL 的存储设计。为节省空间hll.h 声明 HLL 值根据集合规模在四种格式间转换枚举值格式触发条件最大占用空间HLL_DATA_EMPTY(0)空集合集合为空1 字节HLL_DATA_EXPLICIT(1)显式存储哈希值哈希值数量 ≤ 1601 1 160×8 1282 字节HLL_DATA_SPARSE(2)只存非零寄存器索引值非零寄存器数 ≤ 40961 4 3×4096 12293 字节HLL_DATA_FULL(3)存储全部寄存器非零寄存器数超过 40961 16384 字节关键常量定义在 constexpr.hconstexpr int HLL_COLUMN_PRECISION 14; // 精度对应 2^14 16384 个寄存器 constexpr int HLL_EXPLICLIT_INT64_NUM 160; // EXPLICIT 格式元素上限 constexpr int HLL_SPARSE_THRESHOLD 4096; // SPARSE 序列化阈值 constexpr int HLL_REGISTERS_COUNT 16 * 1024; // 寄存器总数一个 HLL 值只允许沿empty - explicit - sparse - full单向演进不允许回退源码注释明确说明这些枚举值会持久化到存储设备不可变更。内存中 SPARSE 与 FULL 的实现相同二者差异主要体现在序列化编码时见 hll.cpp当非零寄存器数大于 4096 时采用 FULL 编码直接拷贝 16384 字节否则采用 SPARSE 编码每个非零寄存器用 2 字节索引 1 字节值表示。基数估算算法的源码级解析HLL_CARDINALITY在 BE 端的执行路径非常直接。函数声明见 hyperloglog_functions.h实现见 hyperloglog_functions.cppDEFINE_UNARY_FN_WITH_IMPL(hllCardinalityImpl, hll_ptr) { return hll_ptr-estimate_cardinality(); } StatusOrColumnPtr HyperloglogFunctions::hll_cardinality(FunctionContext* context, const starrocks::Columns columns) { return VectorizedStrictUnaryFunctionhllCardinalityImpl::evaluateTYPE_HLL, TYPE_BIGINT(columns[0]); }即入参为TYPE_HLL列逐行取出HyperLogLog对象并调用estimate_cardinality()输出TYPE_BIGINT。真正的估算逻辑位于 hll.cpp其流程分三档空集直接返回0EXPLICIT 格式返回哈希集合的元素个数精确值SPARSE/FULL 格式走经典 HyperLogLog 估算——按寄存器数量选取经验常数alpha16384 个寄存器时alpha 0.7213 / (1 1.079 / 16384)通过 65 项谐波均值表harmomic_tables计算调和平均当估算值E num_streams * 2.5且存在零寄存器时改用**线性计数Linear Counting**提升小基数精度当num_streams 16384且estimate 72000时套用四阶多项式偏差校正该修正思路参考了 Redis 的实现以平滑线性计数切换为 HyperLogLog 时的波动。值得指出estimate_cardinality()返回的是经过std::lround取整的近似值。官方文档明确说明 HLL 估算误差约为 1%因此它适合替代COUNT(DISTINCT)以大幅降低内存与计算开销但不适合需要精确去重计数的场景。性能优化细节寄存器更新与合并StarRocks 对 HLL 寄存器操作做了多层优化这些细节决定了HLL_CARDINALITY背后数据写入与合并的速度寄存器更新_update_registershll.h用哈希值低 14 位定位寄存器索引再取剩余高位中首个置 1 位的位置max保留更大值寄存器合并 SIMD 化merge_registers_impl在 hll.cpp 中为 AVX-512、AVX2、SSE4.2 分别提供_mm512_max_epu8/_mm256_max_epu8/_mm128_max_epu8的向量化逐字节取 max 实现并通过MFV_*宏按 CPU 能力自动分派普通路径则退化为逐字节比较寄存器内存管理寄存器缓冲区仅在真正需要时分配HLL_REGISTERS_COUNT即 16KB且可通过set_registers_allocator注册进程级自定义分配器hll.cpp便于在统一的 MemChunk 池中管理反序列化安全校验deserialize与is_validhll.cpp会校验编码类型、长度及 SPARSE 索引是否越界防止恶意或损坏数据导致越界写入。测试验证hll_test.cpp 中的行为确认BE 单元测试 hll_test.cpp 对上述行为做了系统验证可作为理解HLL_CARDINALITY语义的参考空 HLL 序列化后长度为 1estimate_cardinality()返回0第 95-112 行100 个哈希值处于 EXPLICIT 格式序列化长度为1 1 100 * 8估算值精确等于100第 113-141 行超过阈值后转换到 SPARSE/FULL 格式且合并更多元素后估算值单调增长第 171-235 行非法输入空 Slice、未知类型、长度不符会被is_valid拒绝反序列化失败的对象估算值回落为0第 83-112、286 行。使用场景与注意事项推荐场景UV 统计业务表将用户 ID 列通过hll_hash在导入时构造成 HLL 列如col1hll_hash(user_id)按天/小时聚合后用hll_union_agg合并、hll_cardinality读取实现任意时间窗口的独立访客去重大规模去重加速当COUNT(DISTINCT)因基数极大导致内存或耗时超标时用 HLL 方案换取约 1% 误差下的数量级性能提升指标中间态存储HLL 可作为表的值列详见 hll_union_agg.md通过聚合压缩数据量、加速查询其可合并特性让预聚合结果可以在查询期继续合并。注意事项HLL_CARDINALITY的入参必须是 HLL 类型直接传入普通字符串需要先用hll_hash转换返回值为近似值误差约 1%对精确性要求严苛的场景如对账不适合使用HLL 类型列在导入时用hll_hash指定来源列、用hll_empty()兜底空值导入映射示例见 hll_empty.md否则无法生成合法 HLL 数据空集或反序列化失败的对象会估算为0若数据链路异常如导入格式错误需结合is_valid类校验手段排查数据质量问题。小结HLL_CARDINALITY是 StarRocks HLL 体系中把算法结果翻译成业务指标的最后一环。它的语法极简但背后的价值来自整套 HyperLogLog 工程实现单向演进的四种存储格式、约 1% 误差的估算修正、SIMD 化的寄存器合并以及完整的序列化安全校验。将它与hll_hash写入端、hll_union_agg合并端、hll_empty兜底端组合使用即可在 StarRocks 中构建一套高性价比的海量去重统计方案。【免费下载链接】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），仅供参考