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,000 | 100% |
| 下推 | 1,000,000 | 10% |
| 减少 | 9,000,000 | 90%(用例 67) |
这 90% 不是扫描量的减少,而是中间结果的减少。表还是要读 1000 万行,但 Join、Shuffle、排序这些下游算子只处理 100 万行。分布式执行里,中间结果的每一行都要过网络、进缓冲区、参与比较,省下 900 万行往往比省下 900 万行扫描更值钱。
列裁剪:100 列只读 5 列
第二个规则是列裁剪:只保留上层真正用到的列,其余列在 Scan 处就不读。lab 用例 68 给出 100 列里只保留 5 列:
保留比例 = 5 / 100 = 5%
省掉的列 = 100 - 5 = 95 列
| 口径 | 读取列数 | 占全表比例 |
|---|---|---|
| 不裁剪 | 100 | 100% |
| 裁剪后 | 5 | 5%(用例 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 链 |
| 投影消除 | 去掉冗余 Project | Project 链 |
| 子查询展开 | 改写相关子查询 | 子查询节点 |
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 之前先缩小数据量。第二类是分区裁剪:如果过滤条件落在分区列上,直接跳过不匹配的分区。
| 改写 | 作用对象 | 收益来源 |
|---|---|---|
| 局部聚合 | Aggregate | Shuffle 数据量下降 |
| 分区裁剪 | 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
上游实现参照
本节 lab
在 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。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。