8.3 Join reorder 与代价模型
多表 join 的执行顺序不是语法问题,是代价问题。同样三张表,先关联哪两张、中间结果多大、要不要 shuffle,最终耗时可能差一个数量级。join reorder 要做的,就是在所有合法顺序里挑一个中间结果最小的。
难处在于候选数量。顺序不是线性增长,而是阶乘增长;搜索空间稍大一点,穷举就变得不现实。于是真实优化器必须在「搜得更全」和「搜得更快」之间做取舍。
顺序为什么值钱
A、B、C 三张表做 join,逻辑结果与顺序无关,但执行过程完全不同。每个 join 都会产生一个中间结果,而中间结果要落盘或走网络,是分布式执行里最贵的部分。
| 顺序 | 第一步中间结果 | 第二步输入 |
|---|---|---|
| (A ⋈ B) ⋈ C | A 与 B 的匹配行 | 上一步结果 + C |
| (A ⋈ C) ⋈ B | A 与 C 的匹配行 | 上一步结果 + B |
| (B ⋈ C) ⋈ A | B 与 C 的匹配行 | 上一步结果 + A |
三个顺序的逻辑结果一样,中间结果可能差几个数量级。代价优化的目标不是让某一步最快,而是让整棵树的累计中间结果最小;因为每一步的输出都是下一步的输入,前面的膨胀会被后面继承。
n! 种顺序
n 张表的 join 顺序候选数是 n 的阶乘。lab 用例 75 给出两个小例子:
3 表:3! = 3 × 2 × 1 = 6 种
4 表:4! = 4 × 3 × 2 × 1 = 24 种
| 表数 | 顺序数 | 增长 |
|---|---|---|
| 3 | 6 | 用例 75 |
| 4 | 24 | 用例 75 |
| 5 | 120 | 公式推导 |
| 10 | 3,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^n | 2^n × n |
|---|---|---|
| 5 | 32 | 160 |
| 10 | 1,024 | 10,240(用例 76) |
| 15 | 32,768 | 491,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 |
| 右表 NDV | 1,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
在 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 倍 → 代价模型沿树累加,统计失真时顺序会选反。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。