StarRocks APPROX_TOP_K 函数完全指南语法参数、示例与 SpaceSaving 近似 TopK 算法实现解析【免费下载链接】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/starrocksStarRocks 自 v3.0 起提供APPROX_TOP_K聚合函数用于在超大分组中低开销地统计某个表达式取值频次最高的前k个值及其近似出现次数是高频值分布分析、热门维度探查的典型工具。本文完整覆盖该函数的语法、参数取值范围、返回结构与官方示例并深入 StarRocks BE 的聚合函数源码剖析其基于 SpaceSaving 思想的计数器实现、多阶段聚合的序列化协议以及 FE 参数校验规则帮助你在实际业务中正确选型并理解结果误差的来源。1. 函数概览与适用场景APPROX_TOP_K(expr)返回表达式expr中出现频次最高的前k个取值以及它们的近似出现次数。与COUNT(DISTINCT ...)或GROUP BY expr精确统计不同它用固定大小的计数器状态换取 O(1) 级别的状态开销因此在以下场景特别有价值对高基数列如 URL、设备 ID、商品 SKU快速查看最热前几名按维度分组后观察各组内部的取值分布例如每门学科的分数分布与精确GROUP BY相比避免在分组前对高基数列做全量哈希去重带来的内存与 shuffle 成本。该函数自v3.0起支持见官方文档 approx_top_k.md。文档给出的函数描述为Returns the topkmost frequently occurring item values in anexpralong with their approximate counts.2. 语法与参数详解2.1 语法APPROX_TOP_K(expr [ , k [ , counter_num ] ] )从 FE 内置函数注册代码看APPROX_TOP_K共注册了 3 个重载(expr)、(expr, INT)、(expr, INT, INT)中间状态类型为VARBINARY见 FunctionSet.java 的registerBuiltinApproxTopKWindowFunction方法。2.2 参数说明参数类型与约束说明exprSTRING、BOOLEAN、DATE、DATETIME 或数值类型的表达式待统计取值的列或表达式k可选INTEGER 字面量 0最大值100000返回结果条数不指定时默认5counter_num可选INTEGER 字面量k最大值100000计数器容量。越大结果越精确但 CPU 与内存开销也越大不指定时按公式min(max(2 * k, 100), 100000)计算关于counter_num的默认值需要注意BE 源码中的实际公式是min(max(2 * k, 100), 100000)即先取2*k与100的较大者再与100000取较小者见 approx_top_k.h 中的get_k_and_counter_numint32_t counter_num; if (ctx-get_num_args() 2) { counter_num ColumnHelper::get_const_valueTYPE_INT(ctx-get_constant_column(2)); } else { counter_num std::min(std::max(2 * k, 100), MAX_COUNTER_NUM); // MAX_COUNTER_NUM 100000 }源码中同时保留了硬约束DCHECKk 0、counter_num 0、k 100000、counter_num 100000、counter_num k。这些约束在 FE 语义分析阶段就会被提前校验详见第 6 节。2.3 类型支持范围BE 侧通过类型分发只为特定类型族注册approx_top_k映射见 aggregate_resolver_approx.cpp 的ApproxTopKBuilderif constexpr (lt_is_integerlt || lt_is_decimallt || lt_is_floatlt || lt_is_stringlt || lt_is_date_or_datetimelt || lt_is_booleanlt) { resolver-add_aggregate_mappinglt, TYPE_ARRAY, ApproxTopKState, AggregateFunctionPtr, false( approx_top_k, true, AggregateFactory::MakeApproxTopKAggregateFunctionlt()); }即支持整数、Decimal、浮点、字符串、日期时间、布尔类型与文档中STRING、BOOLEAN、DATE、DATETIME 或数值类型的描述一致返回类型统一为TYPE_ARRAY。3. 返回类型与误差模型3.1 返回类型结果为STRUCT类型的 ARRAY。每个 STRUCT 包含两个字段item取值本身保持原始输入类型countBIGINT该取值的近似出现次数。数组按count降序排列。从 BE 输出实现get_values可以看到结果被写进ArrayColumnNullableColumnStructColumnitem, count结构approx_top_k.h。另外该函数的结果永远非 NULL空输入返回空数组——BE 中is_result_non_nullable()返回trueapprox_top_k.hFE 也将APPROX_TOP_K列入alwaysReturnNonNullableFunctions集合FunctionSet.java。3.2 NULL 值处理NULL被当作一个独立的取值参与统计作为数组中的一个 item 返回。源码中专门有一个null_counter字段独立累加 NULL 行数输出阶段按计数与其他 item 合并排序approx_top_k.h。这也是示例结果中频繁出现{item:null,count:1}的原因。3.3 误差上界文档给出的误差保证为每个count的误差至多为2.0 * numRows / counter_numnumRows为总行数counter_num越大精度越高代价是更多内存当不同取值的数量少于counter_num时结果是精确的计数器不会发生淘汰。4. 官方示例scores 表上的取值分布官方示例使用 Window_function.md 中的scores样例表其建表与数据如下可复制执行CREATE TABLE scores ( id int(11) NULL, name varchar(11) NULL, subject varchar(11) NULL, score int(11) NULL ) DISTRIBUTED BY HASH(score) BUCKETS 10; INSERT INTO scores VALUES (1, lily, math, NULL), (1, lily, english, 100), (1, lily, physics, 60), (2, tom, math, 80), (2, tom, english, 98), (2, tom, physics, NULL), (3, jack, math, 95), (3, jack, english, NULL), (3, jack, physics, 99), (4, amy, math, 80), (4, amy, english, 92), (4, amy, physics, 99), (5, mike, math, 70), (5, mike, english, 85), (5, mike, physics, 85), (6, amber, math, 92), (6, amber, NULL, 90), (6, amber, physics, 100);4.1 各学科的分数分布-- Calculate the score distribution of each subject. SELECT subject, APPROX_TOP_K(score) AS top_k FROM scores GROUP BY subject;----------------------------------------------------------------------------------------------------------------------------- | subject | top_k | ----------------------------------------------------------------------------------------------------------------------------- | physics | [{item:99,count:2},{item:null,count:1},{item:100,count:1},{item:85,count:1},{item:60,count:1}] | | english | [{item:null,count:1},{item:92,count:1},{item:98,count:1},{item:100,count:1},{item:85,count:1}] | | NULL | [{item:90,count:1}] | | math | [{item:80,count:2},{item:null,count:1},{item:92,count:1},{item:95,count:1},{item:70,count:1}] | -----------------------------------------------------------------------------------------------------------------------------4.2 单学科math的分数分布-- Calculate the score distribution of the math subject. SELECT subject, APPROX_TOP_K(score) AS top_k FROM scores WHERE subject IN (math) GROUP BY subject;---------------------------------------------------------------------------------------------------------------------------- | subject | top_k | ---------------------------------------------------------------------------------------------------------------------------- | math | [{item:80,count:2},{item:null,count:1},{item:95,count:1},{item:92,count:1},{item:70,count:1}] | ----------------------------------------------------------------------------------------------------------------------------两点观察不指定k时默认返回 5 条DEFAULT_K 5见 approx_top_k.h。示例中每组不同取值数均远小于默认counter_num因此count是精确值结果数组按count降序排列count相同的 item 之间顺序由计数器淘汰顺序决定不保证稳定——这与源码中_maintain_ordering仅维护按 count 非降序这一弱序有关。5. 源码实现SpaceSaving 式计数器approx_top_k的 BE 实现位于 approx_top_k.h核心是ApproxTopKStateLT聚合状态。从源码结构看其设计要点如下。5.1 状态结构template LogicalType LT struct ApproxTopKState { struct Counter { CppType value {}; // 取值 int64_t count 0; // 计数 const size_t _index; // 该计数器在 counters 数组中的下标 }; int32_t k 0; int32_t counter_num 0; int32_t unused_idx 0; // 已使用的计数器数量 mutable VectorWithAggStateAllocatorCounter counters; // 定容计数器数组 mutable Counter null_counter{0}; // NULL 专用计数器 phmap::flat_hash_mapCppType, Counter*, ... table; // 取值 - 计数器 的哈希索引 bool is_init false; };counters是一个定长counter_num个的计数器数组table是哈希索引二者配合实现 O(1) 查找状态内存分配走VectorWithAggStateAllocator聚合状态分配器避免高频小对象走全局堆。5.2 更新逻辑process每次处理一个新取值或合并一段计数时process分三种情况approx_top_k.h取值已存在找到对应计数器count count然后维护数组排序计数器未满unused_idx counter_num占用下一个空计数器写入取值与计数计数器已满淘汰计数最小的计数器替换为新取值。这里有一个关键细节——源码注释明确写道// This is by design, space space algorithm requires increasing it instead of setting to count min_counter.count count;即满员替换时不是把最小计数器重置为新值而是把原最小计数累加到新值上而非。这正是经典 SpaceSavingHeavy Hitters算法的做法被淘汰取值的计数转移给新值从而保证每个保留取值的计数只会被高估、不会低估误差上界即为文档所述的2.0 * numRows / counter_num。5.3 有序数组加速最小值查找counters数组被维护为count 非降序排列approx_top_k.h 的_maintain_ordering每次某计数器计数变化后只向相邻位置冒泡而不在数组中查找最小值——最小值恒在数组前段。淘汰时_min_index用std::upper_bound找到与最小 count 相同的最后一个下标再淘汰减少无谓交换。table哈希索引会在交换后同步重建被移动区间的映射保证值查找与计数器位置始终一致。5.4 输出与 NULL 合并get_valuesapprox_top_k.h把按 count 升序排好的计数器倒序写出恰好得到 count 降序的 ARRAY若存在 NULL 计数则按计数大小与其余 item 交错插入。输出条数为min(k, 实际有效计数器数)。6. FE 参数校验错误信息与边界FE 在语义分析阶段就对k与counter_num做了严格字面量校验。FE 计划测试 AggregateTest.java 的testApproxTopK方法完整刻画了这些规则可视为参数约束的权威依据用例 SQL期望结果approx_top_k(L_LINENUMBER)/(..., 10000)/(..., 100, 10000)/(..., 10000, 10000)/(..., 1, 1)正常生成计划边界值 1 与 10000 合法approx_top_k(L_LINENUMBER, 111)报错The second parameter of APPROX_TOP_K must be a constant positive integerapprox_top_k(L_LINENUMBER, 1, 111)报错The third parameter of APPROX_TOP_K must be a constant positive integerapprox_top_k(L_LINENUMBER, 100001)报错The maximum number of the second parameter is 100000approx_top_k(L_LINENUMBER, 0)报错第二参数必须为正的整数常量approx_top_k(L_LINENUMBER, 1, 100001)报错The maximum number of the third parameter is 100000approx_top_k(L_LINENUMBER, 1, -1)报错第三参数必须为正的整数常量approx_top_k(L_LINENUMBER, 100, 99)报错The second parameter must be smaller than or equal to the third parameter即k counter_num关键结论第二、三参数必须是常量整数字面量不能是列或表达式且1 k counter_num 100000首参数不允许隐式类型转换isCastMatchAllowed对APPROX_TOP_K特判要求候选函数首参类型严格匹配FunctionSet.java这与结果中item保持原始输入类型的语义一致。7. 多阶段聚合序列化与合并协议APPROX_TOP_K是标准的两阶段partial / merge / finalize聚合函数。FE 侧将其标记为BE 中不支持常量上下文不能下推 agg_state 合并状态的函数之一FunctionSet.java 的注释Functions with constant contexts in be are not supported因此中间态完全由 BE 的序列化协议承担。BE 侧序列化格式approx_top_k.h 的serialize_state为一段二进制[null_count: int64][effective_counter_num: int32] 重复 effective_counter_num 次: [value][count: int64]其中字符串类型Slice的 value 会先写长度再写内容count 0的空计数器不写入只序列化有效计数器减少 shuffle 数据传输量。merge阶段反序列化后逐个回填对于已满的计数器只有当对端计数大于本地最小计数时才发生替换且此时直接赋值而非累加避免跨阶段误差被重复放大approx_top_k.h 的is_merge分支。测试 AggregateTest.java 还验证了一个细节两阶段聚合new_planner_agg_stage2的 merge 阶段计划中不应把首参常量追加为approx_top_k(intermediate, 1, 3, 10)而应保持approx_top_k, 3, 10——因为 BE 是按位置读取常量参数的错位会导致类型不匹配。8. 使用建议与代价权衡结合文档与源码可以给出以下实践建议默认参数足够应对探查不传参数时k5、counter_nummin(max(2k,100),100000)100。若分组内不同取值数 ≤ 100结果是精确的若取值基数远超 100count是只高估不低估的近似值。调大counter_num换精度误差上界为2.0 * numRows / counter_num。例如总行数 1000 万、counter_num10000时单个计数的误差上界约为 2000 次。但counter_num上限为 100000且它直接决定每个分组状态的计数器数量与内存占用。k与counter_num需满足k counter_num否则 FE 直接报错见第 6 节表格。只关心 Top-K 而非全局精确分布若需要精确完整分布仍应使用GROUP BYAPPROX_TOP_K的价值在于以恒定状态成本快速回答哪些取值最热。NULL 是合法 item结果中{item:null,count:N}表示 N 行输入为 NULL做下游解析时需注意。9. 小结与延伸阅读APPROX_TOP_K是 StarRocks v3.0 提供的轻量级频率统计函数语法上是(expr[, k[, counter_num]])的三参数聚合语义上返回按近似频次降序的ARRAYSTRUCTitem, count实现上是 BE 中基于定长计数器数组 哈希索引、按 SpaceSaving 思想淘汰累加的聚合状态并通过二进制序列化支持跨阶段 merge。文档承诺的2.0 * numRows / counter_num误差上界与源码中淘汰计数累加到新值的行为一一对应。相关参考官方函数文档approx_top_k.md示例表定义Window_function.mdBE 聚合实现approx_top_k.h、类型注册 aggregate_resolver_approx.cppFE 函数注册与参数规则FunctionSet.javaFE 参数校验测试AggregateTest.java同族函数approx_count_distinct.md、aggregate-functions.mdx【免费下载链接】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），仅供参考