StarRocks HLL_CARDINALITY 函数详解：HLL 基数估算的读取与底层实现
【免费下载链接】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
导读
本文围绕 StarRocks 标量函数HLL_CARDINALITY展开，讲解如何从单个 HLL（HyperLogLog）类型的值中估算基数（distinct 数量），并结合 hll.h、hll.cpp 等后端源码剖析其存储格式演进与估算算法。读完本文，你将掌握HLL_CARDINALITY的语法、返回值、典型用法，理解它与hll_hash、hll_union_agg等函数如何配合完成 UV（独立访客）类去重统计，并了解 StarRocks 在内存与存储层面为 HLL 所做的大量优化。
函数定位：HLL 体系中的"读取端"
StarRocks 的 HLL 是一套完整的数据类型与函数体系。HLL（HyperLogLog）是一种以固定内存开销估算超大集合基数的近似算法，其核心价值在于：只保存固定大小的寄存器（register）数据，即可在毫秒级估算出海量去重值个数，且无需保存原始数据。整套体系在仓库中对应文件包括：
- 标量函数：hll_cardinality.md、hll_hash.md、hll_empty.md；
- 聚合函数：hll_union_agg.md、hll_union.md、hll_raw_agg.md；
- BE 端实现：hyperloglog_functions.cpp、hll.h、hll.cpp；
- 单元测试：hll_test.cpp。
在这套体系中，HLL_CARDINALITY承担"读取/估算"职责：它接收一个已经构建好的 HLL 值（可能来自hll_hash的转换结果、表中 HLL 列、或hll_union_agg的聚合结果），返回该集合的基数估算值。
语法与返回值
HLL_CARDINALITY的完整语法如下：
HLL_CARDINALITY(hll)参数说明：
| 参数 | 类型 | 说明 |
|---|---|---|
hll | HLL | 一个 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估算时返回 0：
insert 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) | 显式存储哈希值 | 哈希值数量 ≤ 160 | 1 + 1 + 160×8 = 1282 字节 |
HLL_DATA_SPARSE(2) | 只存非零寄存器（索引+值） | 非零寄存器数 ≤ 4096 | 1 + 4 + 3×4096 = 12293 字节 |
HLL_DATA_FULL(3) | 存储全部寄存器 | 非零寄存器数超过 4096 | 1 + 16384 字节 |
关键常量定义在 constexpr.h：
constexpr 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.cpp：
DEFINE_UNARY_FN_WITH_IMPL(hllCardinalityImpl, hll_ptr) { return hll_ptr->estimate_cardinality(); } StatusOr<ColumnPtr> HyperloglogFunctions::hll_cardinality(FunctionContext* context, const starrocks::Columns& columns) { return VectorizedStrictUnaryFunction<hllCardinalityImpl>::evaluate<TYPE_HLL, TYPE_BIGINT>(columns[0]); }即：入参为TYPE_HLL列，逐行取出HyperLogLog对象并调用estimate_cardinality()，输出TYPE_BIGINT。真正的估算逻辑位于 hll.cpp，其流程分三档：
- 空集：直接返回
0； - EXPLICIT 格式：返回哈希集合的元素个数（精确值）；
- SPARSE/FULL 格式：走经典 HyperLogLog 估算——
- 按寄存器数量选取经验常数
alpha（16384 个寄存器时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_registers（hll.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_valid（hll.cpp）会校验编码类型、长度及 SPARSE 索引是否越界，防止恶意或损坏数据导致越界写入。
测试验证：hll_test.cpp 中的行为确认
BE 单元测试 hll_test.cpp 对上述行为做了系统验证，可作为理解HLL_CARDINALITY语义的参考：
- 空 HLL 序列化后长度为 1，
estimate_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 列（如col1=hll_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 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
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
