《大规模分布式计算深入解析》7.2 Sort-based aggregate 与 spill

排序聚合先按分组键排序再顺序扫描,用比较次数换常量内存。100 万行约 19,931,568.6 次比较,却只需当前组 32 字节;输入已按分组键有序时只需 100 万次扫描。hash 随分组数涨内存并可能溢出,排序聚合恒为常量内存,取舍看基数与输入顺序。

7.2 Sort-based aggregate 与 spill

排序聚合换了一个方向:不维护「键 → 累加器」的哈希表,而是先按分组键把数据排好序,让相同的键必然相邻,然后顺序扫一遍,遇到新键就换一个累加器。它用排序的比较成本,换来了恒定的内存占用。

本节沿一条判断链走:现象是 hash 聚合的分组表大到溢出、而内存又不能无限加,机制是排序后同键相邻、只需一个累加器,账本是 1993 万次比较与 32 字节内存,判据是分组基数与输入是否已有序。

排序后顺序扫

步骤动作内存
排序按分组键做(外部)排序排序缓冲区,可溢出
扫描顺序读,比较相邻键当前组一个累加器
输出键变化时输出上一组无额外状态

关键性质是「同键相邻」:一旦排序完成,聚合退化成一次线性扫描,不需要哈希、不需要随机访存、也不需要为每个分组保留一个槽位。内存占用与分组数彻底解耦。

比较次数是 n log2 n

排序聚合的主要成本在排序,而排序的比较次数不是行数,而是行数乘以 log2 行数。lab 用例 59 的口径是 100 万行:

// 用例 59:排序聚合的比较次数
double comparisons = Operator.sortComparisons(1_000_000L);
// 1,000,000 × log2(1,000,000)
// = 1,000,000 × 19.9315686
// = 19,931,568.6 次
量取值来源
行数1,000,000统一场景
log2(100 万)19.9315686公式推导
比较次数19,931,568.6用例 59
相对行数的倍数约 19.93 倍公式推导

100 万行要比较约 1993 万次,是行数的近 20 倍。这个倍数随 log2 n 缓慢增长:行数翻倍,倍数只增加 1。所以排序聚合的成本近似线性于行数,只是带一个 20 左右的常数因子。

常量内存:只需当前组的 32 字节

排序聚合真正的优势在内存。lab 用例 60 的口径很极端:不管有多少分组,只需要保存当前组的累加器。

排序聚合内存 = 当前组一条累加器 = 32 字节
方案内存占用随分组数增长溢出风险
hash 聚合分组数 × 32 字节(用例 55)是,线性高基数时必然溢出
排序聚合32 字节(用例 60)否,恒定只取决于排序缓冲

3.2MB 与 32 字节差 10 万倍(公式推导:3,200,000 ÷ 32)。这个差距在分组数继续上升时会进一步拉大:hash 聚合的内存随基数线性增长,排序聚合始终是 32 字节,多出来的内存需求全部转移到了排序缓冲区——而排序缓冲区的大小是可以配置、可以溢出的。

已有序输入:100 万次顺序扫描

如果输入已经按分组键有序,排序这一步完全消失,只剩线性扫描。lab 用例 61:

已有序时比较次数 = 行数 = 1,000,000 次
输入状态比较次数内存说明
未排序19,931,568.6(用例 59)32 字节 + 排序缓冲需要先排序
已按分组键有序1,000,000(用例 61)32 字节直接扫描

两者相差约 19.93 倍(公式推导)。这个差距说明:排序聚合的性能几乎完全取决于「输入是否已经有序」。有序时它比 hash 聚合更省——既不用建表,也不用随机访存;无序时它要为排序付出 1993 万次比较的代价。

排序聚合的溢出行为

排序聚合也会溢出,但溢出的对象不同:hash 聚合溢出的是聚合表本身,排序聚合溢出的是排序的中间结果。

溢出对象触发条件IO 特征
hash 聚合分组表超过内存聚合表写出一遍、读回一遍
排序聚合排序数据超过内存生成 run、归并读、归并写,约 3 倍数据量

排序聚合的溢出更可预测:它的内存需求与分组数无关,只与排序缓冲区有关,而排序缓冲区大小是固定配置。代价是外部排序的 3 倍 IO(6.2 用例 51 已算过),在数据量很大时这笔 IO 不能忽略。

与 hash 聚合的取舍

两种聚合没有绝对优劣,取决于分组基数与输入顺序:

维度hash 聚合sort 聚合
主要成本每行一次哈希与随机访存n log2 n 次比较
内存分组数 × 每组字节常量 32 字节 + 排序缓冲
分组数小表小,缓存友好,最快仍要排序,偏慢
分组数大表大,可能溢出内存恒定,只付排序
输入已有序无额外收益比较次数降到 n
输出顺序无序按分组键有序

这是一张典型的「小基数选 hash、大基数或有序输入选 sort」的表。分组少时 hash 的表小到能驻留缓存,排序纯属浪费;分组多到 hash 溢出时,排序聚合的常量内存反而成了优势。如果下游还需要按分组键排序,sort 聚合顺带满足,又省一次排序。

判据:什么时候选排序聚合

条件结论
分组数小、能放进缓存hash 聚合,最快
分组数大到 hash 表溢出sort 聚合,常量内存
输入已按分组键有序sort 聚合,退化为线性扫描
下游需要按分组键有序输出sort 聚合顺带满足
聚合函数不可逆、需要全部行两者均可,看基数

判据可以压成一句:hash 聚合的成本随基数增长,sort 聚合的成本随「是否已排序」变化。基数小选 hash,基数大或已有序选 sort;两者都在溢出时,比的是谁的 IO 更少——hash 只写读聚合表,sort 要付 3 倍数据的排序 IO。

排序键与聚合键一致时的收益

排序聚合的性能几乎完全取决于输入是否已经按分组键有序。这个条件在真实执行计划里并不罕见:

数据来源是否已按分组键有序额外排序成本
聚簇存储扫描是0(用例 52 口径)
上一个排序算子输出是0(用例 52 口径)
任意 shuffle 输出否n log2 n(用例 59)

把聚合接在排序后面,是执行计划里最值得利用的一条性质:排序的成本已经由上游付过,聚合只剩一次线性扫描。这也是为什么有些引擎在生成计划时,会刻意把「排序 + 聚合」合并成一个算子——避免先排一次、再为聚合排第二次。

排序聚合的并行形态

分布式排序聚合先按分组键分区,再在各分区内独立排序与扫描:

分区方式分区之间结果拼接
范围分区键区间不重叠输出天然有序,可直接拼接
哈希分区键交叉各分区输出无序,需再合并

范围分区让「分区」和「排序」合并成一件事:切分完成后,分区之间已经有序,只需处理分区内部。哈希分区均匀但不保序,分区内仍要完整排序,输出还要额外归并。选择哪种,取决于下游是否需要有序结果——需要就范围分区,不需要则哈希分区更抗倾斜。

常量内存的边界

「常量内存」是相对分组数而言的,它不意味着整个算子只占 32 字节:

组成是否随分组数增长说明
当前组累加器否,32 字节(用例 60)换组时重置
排序缓冲区否,固定配置可调大调小
溢出 run是,随数据量增长落盘,不占内存

分组数从 10 万涨到 1000 万,累加器仍然是 32 字节,多出来的只有排序缓冲区与落盘的 run。这正是排序聚合在高基数场景下的价值:内存需求与基数脱钩,只与数据量和缓冲区配置有关。

与去重、窗口的关系

排序带来的「相同值相邻」不只对聚合有用,去重和窗口计算也能直接受益:

算子排序后的收益
distinct相同值相邻,一次扫描即可去重
窗口分区内有序,窗口边界清晰
聚合同键相邻,只需一个累加器
连接双指针归并,顺序访问

一次排序可以喂饱多个算子:如果一条查询里同时有去重、聚合和窗口,先统一排一次序,比每个算子各排一次便宜得多。这也是 sort-based 执行框架在复杂查询里仍被保留的原因——它的收益会随算子数量叠加。

排序聚合的失败模式

排序聚合不是没有代价,它最常见的失败模式是「数据量大、又没排序」:

失败模式表现应对
大表无序26.5754 秒级排序加溢出 IO换 hash 聚合或先分区
键太宽比较成本高于模型值字典编码成定长键
分区倾斜单分区排序成为长尾范围分区改哈希或拆热点

它最适合「已经有序」或「分组数极大」两类场景:前者排序成本为 0,后者内存不随基数增长。两者都不满足时,排序就是纯开销,此时 hash 聚合通常更快。判断顺序应该是先看输入顺序,再看基数,最后才看内存。

三个常见误解

误解一:排序聚合比 hash 聚合慢,永远不该选。 真相:hash 聚合内存随分组数增长并可能溢出,排序聚合只要 32 字节常量内存,输入已有序时更只需 100 万次顺序扫描。

误解二:排序聚合的比较次数和行数成正比。 真相:是 n log2 n,100 万行约 1993 万次比较,是行数的近 20 倍。

误解三:两种聚合的内存差别只是常数因子。 真相:hash 聚合内存等于分组数乘每组字节,排序聚合恒为当前组 32 字节,分组数大时差几个数量级。

一句话总结本节

排序聚合用比较次数换常量内存:100 万行要 19,931,568.6 次比较,是行数的近 20 倍,但只需保存当前组的 32 字节;输入已按分组键有序时,比较次数降到 100 万次,只剩线性扫描。分组基数小选 hash 聚合,基数大到表溢出或输入已有序时选排序聚合,代价从随机访存变成可预测的排序 IO。

本节 lab

下载卷五 Java 8 实验 · 实验运行与版本说明

在 bd-engine-lab 中验证排序聚合的比较次数与内存口径:

  • 源码:src/operator/Operator.java 与 src/operator/OperatorSuite.java。
  • 运行:cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。
  • 断言:用例 59 验证「100 万行排序聚合约 19,931,568.6 次比较」;用例 60 验证「排序聚合只需当前组的 32 字节」;用例 61 验证「已按分组键有序时只需 100 万次顺序扫描」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:hash 聚合表随分组数膨胀到溢出 → 换成先排序再顺序扫描 → 算出 1993 万次比较与 32 字节常量内存 → 基数大或输入已有序时选排序聚合,否则用 hash 聚合。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图