《大规模分布式计算深入解析》8.1 逻辑计划与规则优化

规则优化不改语义,只改执行顺序。本节用谓词下推把 1000 万行先过滤到 100 万行、中间结果减 90%,列裁剪让 100 列只读 5 列,常量折叠在 100 万行上省下 200 万次运算,并用 6 条规则、每条改写 3 个节点共 18 次改写说明规则链的账本。

8.1 逻辑计划与规则优化

一条 SQL 进到引擎里,先被解析成语法树,再被翻译成逻辑计划,最后才变成可执行的物理计划。逻辑计划只回答「算什么」,不回答「怎么算」;规则优化(rule-based optimization,RBO)就在这一层做等价改写,把明显吃亏的形状换成明显划算的形状。

它不像代价优化那样估算行数,只依赖一组「几乎总是成立」的启发式。正因为不依赖统计,它便宜、稳定、可预期;也正因为它不懂代价,它能做的只是把结构摆正,摆不到最优。

逻辑计划是一棵算子树

逻辑计划的节点是关系算子,数据从叶子向上流动。一次三表查询的初始计划通常长这样:

节点作用初始位置
Scan读表叶子
Filter谓词过滤常在 Join 之上
Join两表关联中层
Project选列与表达式常在根附近
Aggregate分组聚合根附近

初始计划由 SQL 的书写顺序决定,而不是由数据决定。用户先写 WHERE 还是先写 JOIN,解析出来的树可能只差一个节点位置,但执行代价可能差一个数量级。规则优化的任务,就是把这些位置摆到合理的地方。

谓词下推:1000 万先变 100 万

最典型的改写是谓词下推:把 Filter 从 Join 之上挪到 Join 之下,让过滤尽早发生。lab 用例 67 的口径是 1000 万行经过谓词后只剩 100 万行:

下推前:Scan 1000 万 → Join(输入 1000 万)
下推后:Scan 1000 万 → Filter 100 万 → Join(输入 100 万)
中间结果减少 = 1 - 100 万 / 1000 万 = 90%
口径进入 Join 的行数相对基线
不下推10,000,000100%
下推1,000,00010%
减少9,000,00090%(用例 67)

这 90% 不是扫描量的减少,而是中间结果的减少。表还是要读 1000 万行,但 Join、Shuffle、排序这些下游算子只处理 100 万行。分布式执行里,中间结果的每一行都要过网络、进缓冲区、参与比较,省下 900 万行往往比省下 900 万行扫描更值钱。

列裁剪:100 列只读 5 列

第二个规则是列裁剪:只保留上层真正用到的列,其余列在 Scan 处就不读。lab 用例 68 给出 100 列里只保留 5 列:

保留比例 = 5 / 100 = 5%
省掉的列 = 100 - 5 = 95 列
口径读取列数占全表比例
不裁剪100100%
裁剪后55%(用例 68)

对列式存储,这个改写的收益是直接的:不读的列不占 I/O、不解压、不占内存。按「100 万行 × 95 列」做公式推导,等于少碰 9500 万个单元格;对行式存储,收益则体现在每行变短、网络传输量下降。同一规则在不同存储格式上的兑现方式不同,但账都能算。

常量折叠:每条省两次运算

常量折叠在编译期把能算的表达式算掉。比如 WHERE dt = '2026-11-15' AND hour = 15,hour 的比较条件如果只剩常量,就可以提前求值;a + 1 + 1 可以折叠成 a + 2。lab 用例 69 的口径是 100 万行、每行省 2 次常量运算:

省下的运算次数 = 行数 × 每条省下的运算数
               = 1,000,000 × 2
               = 2,000,000 次
参数取值说明
参与行数1,000,000本例
每行省下运算2折叠为常量
总省下2,000,000 次用例 69

常量折叠的收益和行数成正比、和表达式复杂度成正比。它不难实现,却常被忽略:一个在 SELECT 里重复出现的 CASE WHEN,如果条件全是常量,本可以在规划期就定下来,却可能被逐行执行几百万次。

规则链的改写账本

真实优化器不是一条规则,而是一条规则链。每条规则扫描计划树,找到匹配的片段就替换。lab 用例 70 用 6 条规则、每条改写 3 个节点来刻画这条链的工作量:

总改写次数 = 规则数 × 每条规则改写节点数
           = 6 × 3
           = 18 次
规则典型作用命中位置
谓词下推Filter 下移Join 之上
列裁剪收缩 Project全树
常量折叠表达式求值Filter、Project
谓词合并多个 Filter 合一Filter 链
投影消除去掉冗余 ProjectProject 链
子查询展开改写相关子查询子查询节点

18 次改写是规则链的「账面工作量」,不是收益。改写次数多说明规则命中的节点多,但不代表每次都划算:一条规则可能把计划改得更规整,却让另一条规则失去匹配机会。

规则顺序决定能否命中

规则链的执行顺序会影响结果。经典的三条规则是「谓词下推」「列裁剪」「投影消除」,它们的相对顺序不同,命中次数就不同:

顺序可能的结果风险
先下推再裁剪过滤后再收缩列,收益叠加低
先裁剪再下推下推可能引用已被裁掉的列需规则内约束
反复迭代到不动点每条规则充分命中编译时间上升

多数引擎采用「迭代到不动点」:规则链跑一遍,若有改写就再跑一遍,直到没有规则能命中。这能避免顺序敏感,代价是编译时间随迭代次数上升。规则数量少时几乎无感,规则上百条时就要限制迭代轮数。

规则优化不懂代价

RBO 的根本局限是它没有行数概念。谓词下推几乎总是对的,但「把小表放 build 侧」「先 join 选择性高的表」这类决策,靠规则只能猜,靠代价才能算。

决策RBO 能否处理原因
谓词尽量早能结构上总是减少中间结果
列尽量少能结构上总是减少 I/O
Join 顺序不能需要行数与选择率
Join 算法不能需要代价比较
是否 broadcast不能需要实际大小

这张表就是 8.2 的入口:规则优化把计划摆正,剩下的顺序与算法选择交给代价优化。两者不是替代关系,而是流水线上的前后两道工序。

下推不是无条件合法

谓词下推要遵守外连接的语义。把 WHERE 条件推进 LEFT JOIN 的右表,可能把「补 NULL」的行提前过滤掉,结果就从外连接退化成内连接:

场景能否下推说明
内连接能两侧过滤都等价
左外连接,条件在左表能不影响右表补 NULL
左外连接,条件在右表不能直接下推会误删补 NULL 行
全外连接需按侧判断两侧都可能补 NULL
含 OR 的谓词需先拆分否则可能改变真值

规则改写的第一条纪律是「语义等价」,收益排在后面。优化器里每条规则都要带前置条件,条件不满足就跳过;这也是为什么规则链需要反复迭代——某条规则本轮不合法,下推别的节点后可能就合法了。

聚合下推与分区裁剪

除了三个基础规则,分布式计划还有两类高频改写。第一类是聚合下推:把 SUM、COUNT、MIN、MAX 拆成「局部聚合 + 全局聚合」,让聚合在 Shuffle 之前先缩小数据量。第二类是分区裁剪:如果过滤条件落在分区列上,直接跳过不匹配的分区。

改写作用对象收益来源
局部聚合AggregateShuffle 数据量下降
分区裁剪Scan不读无关分区
限制下推Limit上游少产数据
子查询展开相关子查询变成可并行的 join

分区裁剪是「谓词下推」在存储层的延伸:逻辑计划把条件下推到 Scan,Scan 再用分区元数据决定读哪些目录。它和 5.1 的文件级下推是同一条链路的两端,逻辑层负责把条件下移,存储层负责把条件兑现成「少读文件」。

规则链的编译时间账

规则链不是免费的。每条规则都要遍历计划树、做模式匹配,规则越多、树越大,规划时间越长。一个上百条规则的优化器,在小查询上可能把规划时间做到与执行时间同一量级。

规则链工作量 ≈ 规则数 × 节点数 × 迭代轮数
规模典型规划时间备注
十几条规则、小计划毫秒级几乎无感
上百条规则、大计划数十毫秒需限制迭代轮数
规则爆炸、反复迭代可达秒级点查场景不可接受

工程上的折中是「按查询规模裁剪规则集」:点查走精简规则链,复杂分析查询才跑完整规则链。规则优化本来就是为了省时间,如果规划本身成了瓶颈,就本末倒置了。

三个常见误解

误解一:规则越多,优化效果越好。 真相:规则之间会互相遮挡,改写次数多不等于收益大;6 条规则 18 次改写只是账面工作量,真正要看的是中间结果与 I/O 降了多少。

误解二:谓词下推能减少扫描量。 真相:扫描量没变,减少的是进入 Join 与 Shuffle 的中间行数;本例 1000 万行扫描不变,进入 Join 的从 1000 万降到 100 万。

误解三:规则优化可以替代代价优化。 真相:RBO 不懂行数,无法判断 join 顺序与算法;它只能把计划摆正,最优顺序必须交给 8.2 的 CBO。

一句话总结本节

规则优化在逻辑计划上做等价改写:谓词下推把进入 Join 的 1000 万行压到 100 万行、中间结果减 90%;列裁剪把 100 列压到 5 列、只读 5%;常量折叠在 100 万行上省下 200 万次运算;6 条规则每条改写 3 个节点共 18 次改写。它便宜稳定但不懂代价,join 顺序与算法选择必须交给 CBO。

逻辑计划、代价与运行时反馈

规则只在语义等价时重写。物理计划用统计选择,运行时反馈只影响可改写的剩余部分。

flowchart TD
    A[解析与类型绑定] --> B[逻辑重写]
    B --> C[生成物理候选]
    S[(统计与约束)] --> C
    C --> D[代价估算与选择]
    D --> E[物理阶段执行]
    E --> F[可用的实际行数和分区大小]
    F -->|适用引擎与阶段| G[重选剩余计划]
    G --> E

上游实现参照

Spark Catalyst 规则源码

本节 lab

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

在 bd-engine-lab 中验证规则改写的账本:

  • 源码: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。
  • 断言:用例 67 验证「谓词下推把 1000 万行过滤到 100 万行,中间结果减少 90%」;用例 68 验证「100 列只保留 5 列,列裁剪后只读 5%」;用例 69 验证「100 万行、每行省 2 次常量运算,共省 200 万次」;用例 70 验证「6 条规则、每条改写 3 个节点,共 18 次改写」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:看到计划里 Filter 在 Join 之上 → 谓词下推让 1000 万行先过滤成 100 万行 → 列裁剪只读 5% 的列、常量折叠省 200 万次运算 → 6 条规则共 18 次改写 → 规则只能摆正结构,顺序与算法交给 CBO。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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