《大规模分布式计算深入解析》8.3 Join reorder 与代价模型

join 顺序的候选数是阶乘级的:3 表 6 种、4 表 24 种、10 表光 DP 就要枚举 10240 个子集。本节用 1000 行 × 1 万行、右表 NDV 1000 算出中间结果 1 万行,说明两种顺序为何相差 10 倍,以及代价模型如何据此挑顺序。

8.3 Join reorder 与代价模型

多表 join 的执行顺序不是语法问题,是代价问题。同样三张表,先关联哪两张、中间结果多大、要不要 shuffle,最终耗时可能差一个数量级。join reorder 要做的,就是在所有合法顺序里挑一个中间结果最小的。

难处在于候选数量。顺序不是线性增长,而是阶乘增长;搜索空间稍大一点,穷举就变得不现实。于是真实优化器必须在「搜得更全」和「搜得更快」之间做取舍。

顺序为什么值钱

A、B、C 三张表做 join,逻辑结果与顺序无关,但执行过程完全不同。每个 join 都会产生一个中间结果,而中间结果要落盘或走网络,是分布式执行里最贵的部分。

顺序第一步中间结果第二步输入
(A ⋈ B) ⋈ CA 与 B 的匹配行上一步结果 + C
(A ⋈ C) ⋈ BA 与 C 的匹配行上一步结果 + B
(B ⋈ C) ⋈ AB 与 C 的匹配行上一步结果 + A

三个顺序的逻辑结果一样,中间结果可能差几个数量级。代价优化的目标不是让某一步最快,而是让整棵树的累计中间结果最小;因为每一步的输出都是下一步的输入,前面的膨胀会被后面继承。

n! 种顺序

n 张表的 join 顺序候选数是 n 的阶乘。lab 用例 75 给出两个小例子:

3 表:3! = 3 × 2 × 1 = 6 种
4 表:4! = 4 × 3 × 2 × 1 = 24 种
表数顺序数增长
36用例 75
424用例 75
5120公式推导
103,628,800公式推导

阶乘增长很快失效:5 表 120 种还能穷举,10 表 362 万种就不可接受了。这还是只算「左深树」的排列;若允许 bushy 树(两侧都可以是中间结果),候选更多。

DP 枚举:2^n × n

为了不重复计算子计划,优化器用动态规划:先算所有单表、再算所有两表组合、三表组合,逐层向上,每层只保留每个子集的当前最优计划。

lab 用例 76 的口径是 10 表,子集枚举规模约 2^n × n:

子集规模 ≈ 2^n × n
         = 2^10 × 10
         = 1024 × 10
         = 10,240 个子集
表数2^n2^n × n
532160
101,02410,240(用例 76)
1532,768491,520

DP 把阶乘降成了指数,但指数仍然会爆。10 表 10240 个子集可以接受,15 表就接近 50 万;再往上,连枚举子集本身都成了负担。这就是为什么大查询必须做搜索空间裁剪。

中间结果账本

顺序好坏,最终要落到中间结果的行数上。lab 用例 77 给了一个具体场景:1000 行的小表与 1 万行的表关联,右表 join key 的 NDV 是 1000:

中间结果 ≈ 左行数 × 右行数 / 右表 NDV
         = 1,000 × 10,000 / 1,000
         = 10,000 行
参数取值
左表行数1,000
右表行数10,000
右表 NDV1,000
中间结果10,000 行(用例 77)

这里输出等于右表行数,说明是「一对多」关联:左表 key 唯一,右表每个 key 平均 10 行,1000 个 key 正好铺满 1 万行。中间结果没有膨胀,是一个相对安全的顺序。

两种顺序差 10 倍

换一个顺序,账本立刻不同。lab 用例 78 对比两种顺序:一种中间结果 1 万行,另一种 10 万行:

倍数 = 第二种顺序中间结果 / 第一种顺序中间结果
     = 100,000 / 10,000
     = 10 倍
顺序中间结果相对
顺序一10,000 行1×
顺序二100,000 行10×(用例 78)

10 倍中间结果意味着 10 倍的 shuffle、10 倍的落盘、10 倍的下一阶段输入。如果后续还有两三个 join,这个差距会继续叠加。join reorder 的价值就体现在这里:它不改一条 SQL,也不改一个算子,只换顺序,就能把整条链路的中间数据压下来。

代价模型怎么选顺序

有了候选与行数,选择就变成比较代价。代价模型通常把每个候选计划的代价拆成几项相加:

代价项来源与行数的关系
扫描读表线性
Shuffle按 key 重分布线性 × 网络系数
build建哈希表线性
probe探测线性
落盘中间结果溢出线性 × 磁盘系数

累计代价沿树求和,而不是只看根节点。一个计划即使最后一步很快,只要中间某步产生了巨大的中间结果,累计代价仍然很高。这也是为什么「先 join 选择性高的两张表」几乎是通用经验:它把膨胀挡在最早的位置。

搜索空间裁剪

穷举不可行时,优化器用三类手段裁剪:

手段做法代价
只保留左深树限制树形可能错过 bushy 最优解
按启发式定序小表先 join依赖「小表」估得准
限制 DP 层数只枚举前 k 层大查询可能退化
贪心扩展每次挑当前最优局部最优

左深树是分布式引擎最常见的取舍:它的中间结果总是「左侧子树 + 一张新表」,便于流水线执行,搜索空间也从 n! 降到可控范围。代价是放弃了 bushy 树可能的更优解,但在大多数星型模型上损失不大。

均匀假设的崩塌

join reorder 的输入是 8.2 的基数估算,而基数估算依赖 1/NDV 的均匀假设。一旦数据倾斜,估算就会失真。

情况估算实际后果
key 均匀接近准确接近估算顺序可信
单 key 占 50%按平均算远大于估算顺序可能选反
统计过期NDV 偏小NDV 偏大中间结果低估
多列相关独立假设强相关选择率失真

顺序选反的代价不是「慢一点」,而是「慢一个数量级」。用例 78 的 10 倍差距在倾斜场景下还可能更大。所以 8.2 强调统计维护,9.1 强调运行时纠偏——它们最终都是为了让 join reorder 的输入更靠谱。

树形:左深、右深与 bushy

候选顺序不只由「表的排列」决定,还由树的形状决定。同样的排列,可以组织成不同形状的树:

形状结构优点缺点
左深每次与一张新表 join流式执行、内存友好右表必须可广播或可探测
右深反过来的左深与左深对称同上,方向相反
bushy两侧都是子树可能产生更小中间结果搜索空间大、调度复杂

左深树天然适配 hash join:左侧是不断增长的「流」,右侧是一张待 build 的表。只要右侧能装进内存,整条链就能流水线跑完,中间结果不必全部物化。bushy 树虽然理论上可能更优,却要求同时物化两棵子树,在分布式环境里往往得不偿失。

什么时候 reorder 没有意义

并非所有 join 都值得重排。当所有表都很小、或所有连接都是「多对一」时,顺序带来的差异会被其他成本淹没:

场景reorder 收益原因
全部小表低中间结果都装得下,瓶颈在启动
多对一外键链低每步都不放大,顺序差异小
大表 × 大表高中间结果可能爆炸
高选择性过滤高先过滤能大幅缩小输入
已有强过滤条件中取决于过滤后剩余行数

判断要不要 reorder,看的是「中间结果会不会放大」。如果每个 join 都是多对一、输出不超过输入,那么任何顺序的累计中间结果都差不多;此时优化器花在搜索上的时间反而是浪费。反过来,只要存在一对多或多对多,顺序就值得认真算。

这也是启发式仍然有用的原因:在搜索成本受限时,「小表先 join」「高选择性先过滤」这类规则能快速给出一个不差解,再把剩余预算留给 DP。规则与代价不是二选一,而是搜索预算的两段分配。

三个常见误解

误解一:join 顺序只影响性能,不影响结果。 真相:逻辑结果确实与顺序无关,但中间结果从 1 万行变 10 万行会带来 10 倍的 shuffle 与落盘,性能差距是实打实的。

误解二:候选多就一定能找到最优顺序。 真相:n! 增长让穷举不可行,DP 也只能压到 2^n × n;10 表就要枚举 10240 个子集,更大的查询必须裁剪搜索空间。

误解三:代价模型选出的顺序一定对。 真相:代价模型吃的是估算行数,统计过期或数据倾斜会让输入失真,选出的「最优」可能还不如一条稳定启发式。

一句话总结本节

join 顺序的候选是阶乘级:3 表 6 种、4 表 24 种,10 表 DP 要枚举 10240 个子集。1000 行乘 1 万行再除以 NDV 1000,中间结果 1 万行;换一种顺序变 10 万行,差 10 倍,shuffle 与落盘随之差 10 倍。代价模型沿树累加中间结果,统计失真时顺序可能选反。

本节 lab

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

在 bd-engine-lab 中验证 join 顺序与中间结果:

  • 源码:src/optimizer/Optimizer.java 与 src/optimizer/OptimizerSuite.java。
  • 运行:cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。
  • 断言:用例 75 验证「3 表 6 种 join 顺序、4 表 24 种」;用例 76 验证「10 表 DP 枚举 2^10 × 10 = 10240 个子集」;用例 77 验证「1000 行 × 1 万行、右表 NDV 1000,中间结果 1 万行」;用例 78 验证「两种顺序中间结果 1 万 vs 10 万,差 10 倍」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:看到多表 join 慢 → 候选顺序按 n! 爆炸、DP 压到 2^n × n → 用行数除以 NDV 算每个顺序的中间结果 → 1 万与 10 万差 10 倍 → 代价模型沿树累加,统计失真时顺序会选反。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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