StarRocks 中 PERCENTILE_CONT 函数详解线性插值百分位计算的用法与源码实现【免费下载链接】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 的PERCENTILE_CONT聚合函数展开先给出函数语法、参数约束、返回值语义与完整示例再结合 FE 的类型检查与 BE 的聚合实现源码解释“线性插值”在引擎内部如何落地、分布式聚合中中间状态如何序列化与合并帮助读者既能直接在生产查询中正确使用该函数也能理解其底层算法与性能设计。一、函数定位与语法PERCENTILE_CONT是 StarRocks 提供的精确百分位聚合函数用于计算一组值中某个百分比位置percentile上的取值。与PERCENTILE_APPROX等近似函数不同它给出精确结果当没有输入值恰好落在目标百分位上时会对相邻的两个输入值做**线性插值linear interpolation**来得到结果。函数语法如下PERCENTILE_CONT(expr, percentile)参数说明与官方文档 percentile_cont.md 保持一致参数说明expr用于排序取值的表达式必须是数值类型、DATE或DATETIME。例如想求物理成绩的中位数就传入物理成绩列。percentile目标百分位取值范围为[0, 1]的常量浮点数。例如求中位数时传0.5。返回值返回指定百分位位置上的值。如果没有任何输入值恰好位于该百分位处结果由最接近目标位置的两个输入值线性插值计算得出。使用注意该函数忽略 NULL 输入——NULL 值不会参与排序也不会影响百分位计算。二、示例按科目求中位数假设存在一张exam表数据如下SELECT * FROM exam ORDER BY Subject; ------------------ | Subject | Score | ------------------ | chemistry | 80 | | chemistry | 100 | | chemistry | NULL | | math | 60 | | math | 70 | | math | 85 | | physics | 75 | | physics | 80 | | physics | 85 | | physics | 99 | ------------------计算每个科目的中位数percentile 0.5NULL 会被自动忽略SELECT Subject, PERCENTILE_CONT(Score, 0.5) FROM exam GROUP BY Subject;结果---------------------------------------- | Subject | percentile_cont(Score, 0.5) | ---------------------------------------- | chemistry | 90 | | math | 70 | | physics | 82.5 | ----------------------------------------逐条解读这个结果可以更直观地理解插值规则设去 NULL 后有n个值u (n - 1) × percentileindex floor(u)结果 a[index] (u - index) × (a[index1] - a[index])chemistry有效值[80, 100]u 1 × 0.5 0.5结果 80 0.5 × (100 - 80) 90math有效值[60, 70, 85]u 2 × 0.5 1index 1恰好命中a[1] 70无需插值physics有效值[75, 80, 85, 99]u 3 × 0.5 1.5结果 80 0.5 × (85 - 80) 82.5。这也解释了为什么对整数输入结果可能出现小数如82.5——插值会落在两个相邻整数之间。三、FE 侧函数注册与参数校验从源码结构看PERCENTILE_CONT在 FE 中作为内置聚合函数注册签名覆盖DATE、DATETIME和DOUBLE输入输入类型 第二个DOUBLE常量参数中间态类型为VARBINARY// PercentileCont addBuiltin(AggregateFunction.createBuiltin(FunctionSet.PERCENTILE_CONT, Lists.newArrayList(DateType.DATE, FloatType.DOUBLE), DateType.DATE, VarbinaryType.VARBINARY, false, false, false)); addBuiltin(AggregateFunction.createBuiltin(FunctionSet.PERCENTILE_CONT, Lists.newArrayList(DateType.DATETIME, FloatType.DOUBLE), DateType.DATETIME, VarbinaryType.VARBINARY, false, false, false)); addBuiltin(AggregateFunction.createBuiltin(FunctionSet.PERCENTILE_CONT, Lists.newArrayList(FloatType.DOUBLE, FloatType.DOUBLE), FloatType.DOUBLE, VarbinaryType.VARBINARY, false, false, false));见 FunctionSet.java。中间态统一为VARBINARY意味着该函数走的是“部分聚合 → 序列化 → 最终聚合”的多阶段执行路径这也正是后文 BE 序列化/合并逻辑存在的原因。在类型检查阶段优化器对第二个参数有额外约束——必须是常量。TypeChecker.java 中可以看到case PERCENTILE_CONT: if (!isMergeAggFn) { checkColType(arguments.get(0), aggCall, definedTypes[0], argTypes.get(0)); if (argTypes.size() 2) { checkArgument(aggCall.getArguments().get(1).isConstant(), %s want constant arg in %s, but input is %s, PREFIX, aggCall, aggCall.getArguments().get(1)); } } break;因此PERCENTILE_CONT(Score, p)中p若为列或非常量表达式会在计划校验阶段直接报错。这解释了文档中 “It is a constant floating-point number from 0 to 1” 的约束来源。函数名在 FunctionSet.java 中定义为常量PERCENTILE_CONT percentile_contFunctionAnalyzer.java 等位置也将其纳入聚合函数分析流程。四、BE 侧百分位状态与线性插值实现BE 中该函数由模板类PercentileContAggregateFunction实现位于 percentile_cont.h并在 aggregate_resolver_others.cpp 中按输入类型注册percentile_cont, false, AggregateFactory::MakePercentileContAggregateFunctionTYPE_DOUBLE()); percentile_cont, false, AggregateFactory::MakePercentileContAggregateFunctionTYPE_DATETIME()); percentile_cont, false, AggregateFactory::MakePercentileContAggregateFunctionTYPE_DATE());4.1 聚合状态items、grid 与 rate每个分组的状态PercentileState由三部分组成见 percentile_cont.htemplate LogicalType LT, typename guard::Guard struct PercentileState { ItemType items; // 本节点本地收到的原始值 GridType grid; // 从其他节点 merge 过来的、已排序的“行”每行两端带哨兵 double rate 0.0; // 目标百分位 };本地更新时update()把值直接追加进itemsupdate_batch()对整列做memcpy批量追加分布式合并时merge()把对端发来的有序数据追加为grid中的新行不重新整体排序把排序成本推迟到finalize阶段用归并解决。init_state_if_needed()中实现了对第二个参数的运行期校验见 percentile_cont.h参数个数必须为 2否则报错Percentile rate is requiredrate必须落在[0, 1]否则报错Percentile rate must be between 0 and 1。4.2 线性插值的精确公式finalize阶段的核心计算见 percentile_cont.hdouble u ((double)rowsNum - 1) * rate; auto index (size_t)u; // ... ResultType result calculateResultLT, InputCppType, ResultType(junior_elm, senior_elm, u, index);其中rowsNum是去 NULL 后的总行数junior_elm/senior_elm是有序序列中第index与第index 1个元素。插值公式在 calculateResult 中按类型分支实现} else if constexpr (lt_is_arithmeticLT) { result junior_elm (u - (double)index) * (senior_elm - junior_elm); }数值类型标准线性插值结果可能为小数DATE类型按儒略日差值插值result._julian junior._julian (u - index) * (senior._julian - junior._julian)DATETIME类型按 Unix 秒插值from_unix_second(junior.to_unix_second() (u - index) * (senior.to_unix_second() - junior.to_unix_second()))。边界情形也有专门处理items.size() 1或rate 1时直接返回最大/唯一值rate 0时直接返回最小值。此外从源码结构看数值类型的最终输出类型由 PercentileResultLT 决定对算术类型特化为TYPE_DOUBLE与示例中82.5这类小数结果相吻合DATE/DATETIME则保持原类型返回。4.3 多段有序数据的归并查找败者树 k 路归并由于merge阶段只追加已排序的行而不整体重排finalize需要在items未排序与grid若干有序行之间高效地定位第index与第index1个元素。实现上items在序列化前会被 pdqsort 排序见 serialize_to_column 中的pdqsort调用最终所有数据段都是有序的kWayMergeSort 用**败者树loser tree**做 k 路归并并在数到第goal/goal1个元素时提前终止避免做完整归并每一行被组织为[min哨兵, 升序数据…, max哨兵]布局代码注释特别说明行尾和虚拟叶子不能按“值”判断真实数据可能恰好等于类型极值如 DATE 的0000-01-01/9999-12-31必须按“位置”判断否则可能读越界当rate 0.5且数据量较大时reverse true即从序列尾部反向归并——因为目标位置靠近末尾从尾部数只需走rowsNum - 1 - u步就能到达显著减少归并步数见 percentile_cont.h。这一设计意味着求 99 分位rate 0.99时归并从尾部正向推进而求 1 分位时从头部推进归并的工作量总是与min(u, rowsNum - 1 - u)量级相关而不是与总行数线性相关。4.4 分布式中间态的序列化格式BE 中间态序列化为VARBINARY字节串格式为rate(double) total_items(size_t) 全部元素定长类型见 serialize_to_column// should serialize: rate_size, vector_size, all vector element. size_t new_size old_size sizeof(double) sizeof(size_t) total_items_size * sizeof(InputCppType);反序列化时merge()会先校验头部长度、元素数量是否会溢出Invalid percentile_cont merge data: ...等防御性错误把 payload 复制为一行并加上 min/max 哨兵后放入grid从而保证多阶段聚合的合并结果与单机一次性聚合完全一致。convert_to_serialize_format()则用于非聚合上下文把每个输入行编码为[rate, 1, element]的单元素中间态。五、与 percentile_disc 的区别同文件实现同一个头文件还实现了PERCENTILE_DISC见 PercentileDiscAggregateFunction两者差异在于percentile_disc不做插值而是取有序序列中ceil((n-1) * rate)位置上真实存在的输入值“choose the uppper one”且其结果类型与输入类型完全一致。文档 percentile_disc 中对其有单独说明实际选型时可按“允许小数/插值结果cont还是必须取原始值disc”来区分。六、相关测试与验证路径BE 表达式测试be/test/exprs/percentile_functions_test.cpp 覆盖percentile_empty、percentile_hash等基础路径FE 分析/计划测试AnalyzeAggregateTest.java、AggregateTest.java 中包含percentile_cont的解析与计划生成用例可用于确认函数在不同输入类型下的行为。七、小结与使用建议PERCENTILE_CONT(expr, p)求精确百分位p必须是[0,1]内的常量输入支持数值、DATE、DATETIMENULL 被忽略。结果语义为线性插值数值输入的结果类型在实现中会呈现为DOUBLE可能出现小数如示例中的82.5要求结果必须是数据集中真实存在的值时应改用PERCENTILE_DISC。从源码看其实现采用“本地收集 有序行归并”的聚合状态多阶段聚合通过rate count payload的字节格式序列化最终用败者树 k 路归并 提前终止高百分位时反向归并来定位目标元素在大数据量下避免了全量排序的开销。若只需近似结果且对延迟敏感可对比仓库中的PERCENTILE_APPROX/PERCENTILE_APPROX_WEIGHTED同见 FunctionSet.java 中的注册逻辑在精度与性能之间做取舍。【免费下载链接】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），仅供参考