《大规模分布式计算深入解析》5.1 两阶段聚合:partial 与 final

局部聚合把行转为可合并状态,再按分组键汇合。能省多少网络由每个实例实际组数、刷新次数、状态宽度和目的分布决定。

5.1 两阶段聚合:partial 与 final

局部聚合把行转为可合并状态,再按分组键汇合。能省多少网络由每个实例实际组数、刷新次数、状态宽度和目的分布决定。

从原始输入到中间状态

flowchart TB
  A["Task A:按组积累 SUM 与 COUNT"] --> X
  B["Task B:按组积累 SUM 与 COUNT"] --> X
  A -.->|"内存回收:同一组可多次 flush"| X
  X["按 group key 重新分区"] --> C["合并可加计数和求和状态"]
  C --> N{"总非 NULL 计数为 0?"}
  N -->|"是"| L["AVG = NULL"]
  N -->|"否"| R["AVG = 总和 / 总计数"]

一亿条每条 24 B 的投影,逻辑交换输入为 2400 MB。假设 16 个实例各看到同样 100 万组,每组只输出一次、每个状态为 24 B,局部聚合后为 384 MB 逻辑载荷,减少 84%。若各实例组集合互斥,则可能只有 100 万条状态;若高基数或哈希表多次 flush,同组会输出多份状态。跨机比例另按实际布局和计划估计。

核对状态可组合性

AVG(x) 的状态用 SUM(x), COUNT(x),排除 NULL 后再合并,分母为零时得 NULL。精确 COUNT DISTINCT 可先对分组键和值去重,再在值不重叠的分区求和;不同分区的局部去重计数通常不能直接相加。读计划中的 PARTIAL、INTERMEDIATE 与 FINAL,确认中间输出行数和状态大小,不能仅根据 SQL 的 GROUP BY 判断阶段数。

实验与资料

下载卷六实验包 ,参照包内 README。src/ 下的 Java 8 教学模型 · sql-counterexamples.py 的语义对照 · trino-probe.py 的真实执行计划。

Trino 聚合与 NULL 语义 · Trino 分布式计划

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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