7.1 Hash aggregate 与分组
聚合把多行压成每组一行。最常见的实现是 hash 聚合:维护一张「分组键 → 累加器」的哈希表,每来一行就按键找到累加器、更新状态,最后把表里每个条目输出成一行。它的成本和分组数直接挂钩,而不是和输入行数直接挂钩——这是它和排序聚合最根本的区别。
本节沿一条判断链走:现象是同一个聚合查询在不同数据上快慢差几十倍,机制是聚合表大小由分组基数决定,账本是 3.2MB 表、4 个溢出分区与 90% 的 shuffle 削减,判据是分组数落在哪个量级。
逐行更新的聚合表
| 阶段 | 动作 | 成本 |
|---|---|---|
| 构建/更新 | 每行算分组键、查表、更新累加器 | 每行一次哈希与随机访存 |
| 溢出 | 表超出内存时按分区落盘 | 额外 IO |
| 输出 | 遍历表,每组输出一行 | 正比于分组数 |
输入行数只影响更新次数,分组数才决定表的大小。这两个量可以完全脱钩:100 万行聚合成 10 组,表只有 320B;10 万行如果每行一个键,表反而更大。判断 hash 聚合的瓶颈,先看基数,再看行数。
分组数决定表大小:10 万组 × 32 字节 = 3.2MB
lab 用例 55 给出最基本的口径:聚合表内存等于分组数乘以每组字节数。
// 用例 55:聚合表内存
long bytes = Operator.hashAggTableBytes(100_000L, 32);
// 100,000 × 32 = 3,200,000 字节 = 3.2MB
| 量 | 取值 | 说明 |
|---|---|---|
| 分组数 | 100,000 | 不同分组键的数量 |
| 每组字节 | 32 | 键、累加器与指针 |
| 聚合表内存 | 3,200,000 字节 | 用例 55,即 3.2MB |
3.2MB 是一个会被缓存接住的尺寸:它放不进最小的 L1,但对 L2 或 L3 来说不算大。这意味着 10 万组的聚合,更新时的大部分查表可能命中缓存,随机访存的代价被压低。分组数再往上走一个数量级,这个优势就没了。
分组极少:10 组 = 320B,驻留 L1
反过来,如果分组数很小,聚合表会小到几乎不占空间。lab 用例 56:
聚合表 = 10 × 32 字节 = 320 字节
| 分组数 | 聚合表内存 | 缓存层级 | 更新成本 |
|---|---|---|---|
| 10 | 320B(用例 56) | 可驻留 L1 | 几乎全是缓存命中 |
| 1,000 | 32,000B(公式推导) | 可驻留 L1/L2 | 命中率高 |
| 100,000 | 3,200,000B(用例 55) | 超出 L1,进 L2/L3 | 部分随机访存 |
| 1,000,000 | 32,000,000B(公式推导) | 超出多数缓存 | 随机访存主导 |
分组数少时,聚合几乎是无成本的:320B 的表完全在 L1 里,每行的更新只是一次极快的缓存读写。这也解释了一个常见现象——GROUP BY 一个低基数列(比如状态、类型)常常比高基数列快一个数量级,即使扫描的行数完全相同。
分组多到放不下:200MB 切成 4 个溢出分区
当分组数大到表放不进内存,hash 聚合必须溢出。lab 用例 57 的场景是 200MB 聚合表、64MB 内存:
分区数 = ceil(200MB ÷ 64MB)
= ceil(3.125)
= 4 个分区
| 量 | 取值 | 说明 |
|---|---|---|
| 聚合表 | 200MB | 全量分组状态 |
| 内存上限 | 64MB | 单分区可用内存 |
| 整除结果 | 3.125 | 公式推导 |
| 溢出分区 | 4 | 用例 57,向上取整 |
溢出分区的切法是按分组键的哈希做,保证同一个分组只落在一个分区里,这样每个分区可以独立聚合、独立输出,不需要跨分区合并。代价是多了一轮写盘与读盘;4 个分区意味着聚合表被完整地写出去又读回来一次。
map 端预聚合:100 万行压到 10 万组,shuffle 降 90%
分布式聚合最有效的一刀不在 reduce 端,而在 map 端先做一次局部聚合。lab 用例 58 的口径是 100 万行输入、预聚合后剩 10 万组:
shuffle 削减比例 = 1 - 部分聚合行数 ÷ 输入行数
= 1 - 100,000 ÷ 1,000,000
= 1 - 0.1
= 90%
| 方案 | shuffle 行数 | 相对数据量 | 说明 |
|---|---|---|---|
| 不预聚合 | 1,000,000 | 100% | 原始行全部过网络 |
| map 端预聚合 | 100,000(用例 58) | 10% | 每组只发一条中间结果 |
90% 的削减同时作用于网络、磁盘和 reduce 端的内存:少传 90% 的行,就少 90% 的反序列化、少 90% 的聚合表压力。如果每行按 32 字节估算,shuffle 数据从 32MB 降到 3.2MB(公式推导),这对 200MB 就要溢出的 reduce 端是决定性的。
基数估计与分区选择
溢出分区数取决于「聚合表会有多大」,而聚合表大小取决于分组数——分组数事先往往不知道。引擎只能靠统计信息估算基数:
| 估算情况 | 后果 |
|---|---|
| 低估分组数 | 分区不足,运行中被迫二次溢出 |
| 高估分组数 | 分区过多,小文件与调度开销上升 |
| 估算准确 | 一次分区到位,无二次溢出 |
基数估计错了,溢出策略就会错。低估是最危险的方向:以为 64MB 够用,实际表到了 200MB,运行到一半才被迫切 4 个分区,前面的工作要重做。稳妥的做法是按偏大的基数预留,或直接采用可动态增加分区的实现。
判据:分组数落在哪个量级
| 分组数量级 | 聚合表 | 策略 |
|---|---|---|
| 十级 | 320B(用例 56) | 单机内存聚合,无需关心 |
| 十万级 | 3.2MB(用例 55) | 单机内存聚合,注意缓存 |
| 百万级 | 32MB(公式推导) | 可能接近内存上限,评估溢出 |
| 千万级以上 | 数百 MB | 必须分区溢出 + map 端预聚合 |
判据的主轴是「分组数 × 每组字节」与可用内存的比较。前者远小于内存,hash 聚合就是最优解;前者接近或超过内存,就必须提前规划溢出分区,并在 map 端尽量预聚合,把进入 shuffle 的行数压下来。
累加器的状态设计
「每组 32 字节」是一个常见估算,真实占用取决于聚合函数需要保存多少状态:
| 聚合函数 | 需要的状态 | 每组字节 |
|---|---|---|
| count | 一个计数 | 最小 |
| sum | 一个数值 | 小 |
| avg | 和加计数 | 稍大 |
| count distinct | 去重集合或草图 | 显著变大 |
去重类聚合会把表撑大一个量级:它不能只存一个数值,而要存见过的值(或近似的草图)。10 万组普通 sum 是 3.2MB,同样分组数的 count distinct 可能是几十 MB。这就是为什么估算聚合表大小时,必须先看聚合函数,而不是只看分组数。
两阶段聚合的执行计划
分布式 hash 聚合几乎都拆成两段:map 端先做局部聚合,shuffle 按分组键重分布,reduce 端再合并同键的部分结果。
| 阶段 | 输入 | 输出 |
|---|---|---|
| map 局部聚合 | 原始行 | 每个键的部分结果 |
| shuffle | 部分结果 | 按分组键分区 |
| reduce 合并 | 同键的多个部分结果 | 每组一行最终结果 |
用例 58 的 90% 削减发生在前两段之间:map 端把 100 万行压成 10 万条部分结果,shuffle 只需要搬这 10 万条。reduce 端的合并成本也随之下降,因为到达的中间结果少了 90%。
值得注意的是,map 端预聚合要求聚合函数可合并——sum、count、min、max 都满足,avg 只要同时传和与计数也能合并。不可合并的聚合(比如中位数)只能把原始行全部送到 reduce 端。
倾斜分组的处理
分组键分布不均时,某个键可能占据大部分行,对应的 reduce 分区成为长尾:
| 现象 | 原因 | 对策 |
|---|---|---|
| 单分区远慢于其他 | 热点键 | 热点键拆成两阶段聚合 |
| 分区大小不均 | 哈希偏斜 | 加盐打散热点键 |
| 少数键巨大 | 天然高基数集中 | 单独处理或限制输出 |
加盐的本质是把一个热键拆成多个子键:先按「键 + 随机后缀」做局部聚合,再把子键的结果按原键合并。代价是多一轮 shuffle,收益是把一个巨大的分区摊平成多个小分区。是否值得,取决于热点键占总行数的比例——占比越高,收益越大。
输出阶段
聚合的输出规模由分组数决定,而不是输入行数:
| 输入行数 | 分组数 | 输出行数 |
|---|---|---|
| 1,000,000 | 100,000 | 100,000(用例 58 口径) |
| 1,000,000 | 10 | 10 |
| 10,000,000 | 100,000 | 100,000(公式推导) |
输入从 100 万涨到 1000 万,只要分组数不变,输出仍是 10 万行。这也是聚合能压缩数据的原因:它把「行数」这个维度消掉了。反过来说,高基数聚合的输出本身就很大,下游如果还要排序或写文件,成本会重新出现。
三个常见误解
误解一:聚合只要分组不多,内存永远够用。 真相:表大小是分组数乘每组字节,10 万组 3.2MB 尚可,但分组到千万级就是几百 MB,200MB 的表在 64MB 内存下要切 4 个分区。
误解二:map 端预聚合只是提前算一点,对 shuffle 影响不大。 真相:100 万行预聚合到 10 万组后 shuffle 数据降 90%,网络、磁盘与 reduce 端内存都按同一比例节省。
误解三:分组数少所以聚合一定快,不用管实现。 真相:分组少时表小到能驻留 L1(10 组 320B),但每行仍要哈希与探测;分组多时瓶颈转为随机访存与溢出。
一句话总结本节
Hash 聚合的成本由分组基数而非输入行数决定:10 万组、每组 32 字节是 3.2MB 表,10 组只有 320B 可驻留 L1;200MB 的表在 64MB 内存下要切成 4 个溢出分区,而 map 端预聚合把 100 万行压到 10 万组,让 shuffle 数据降 90%。判断策略先算「分组数 × 每组字节」,再决定是否需要分区与预聚合。
分组聚合和外存边界
部分聚合仅适用于支持分解的聚合函数。若状态溢写,最终阶段需按键合并对应状态。
flowchart TD
A[输入向量与分组键] --> B[更新分区内聚合状态]
B --> C{状态超预算}
C -->|是| D[(写出可合并的分区状态)]
C -->|否| E[保留内存状态]
D --> F[逐分区读回及合并]
E --> F
F --> G[最终化聚合]
上游实现参照
本节 lab
在 bd-engine-lab 中验证 hash 聚合的表大小、溢出与预聚合账本:
- 源码:
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。 - 断言:用例 55 验证「10 万分组 × 32 字节 = 3.2MB 聚合表」;用例 56 验证「10 个分组时聚合表 320B」;用例 57 验证「200MB 表、64MB 内存切 4 个溢出分区」;用例 58 验证「100 万行预聚合到 10 万组,shuffle 降 90%」。
- 整卷 runner 的预期汇总为
TOTAL: 116 passed, 0 failed。
对应本节判断链:同一聚合查询快慢差异巨大 → 拆出「分组数决定表大小」这条机制 → 算出 3.2MB 表、4 个溢出分区与 90% 的 shuffle 削减 → 按分组数量级决定是否分区溢出并做 map 端预聚合。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。