询优化器＜1＞查询重写 / 逻辑优化
前置知识
语法树
AST是Abstract Syntax Tree，中文通常叫抽象语法树。
在数据库里，用户写的 SQL 文本会先经过词法分析和语法分析，被转换成一种树形结构，这棵树就是 AST。它描述的是 SQL 的语法结构，而不是最终怎么执行。
例如 SQL：
SELECT name, age FROM users WHERE age > 18;可以抽象成一棵 AST：
SelectStatement ├── SelectList │ ├── Column: name │ └── Column: age ├── From │ └── Table: users └── Where └── GreaterThan ├── Column: age └── Literal: 18它的意思是：
这是一个 SELECT 查询 查询的列是 name 和 age 查询的表是 users 过滤条件是 age > 18AST 的作用主要有三个：
- 让数据库理解 SQL 的结构
SQL 文本只是字符串，数据库不能直接优化字符串，必须先把它变成结构化形式。 - 为语义分析做准备
例如检查users表是否存在、age列是否存在、类型是否匹配、函数是否合法等。 - 为逻辑计划生成做准备
数据库会根据 AST 生成逻辑查询计划，例如选择、投影、连接等关系代数表达式。
可以把整个流程理解为：
SQL 文本 → 词法分析：拆成 token → 语法分析：生成 AST → 语义分析：检查表名、列名、类型 → 逻辑计划：关系代数表达式 → 逻辑优化：查询重写 → 物理计划：选择具体执行算法 → 执行简单说：
AST 是数据库把 SQL 从“字符串”变成“结构化语法表示”的第一步。
它还不是执行计划，只是 SQL 的语法骨架。
逻辑查询计划
逻辑查询计划是数据库把 SQL 的含义转换成的一种关系代数形式的操作树。它描述“要做哪些逻辑操作”，但还不决定“具体用什么物理算法执行”。
可以理解为：
SQL 文本 → AST 抽象语法树 → 语义分析 → 逻辑查询计划 → 逻辑优化 → 物理执行计划 → 执行1. 逻辑查询计划描述什么
逻辑查询计划主要描述这些逻辑算子：
| SQL 部分 | 逻辑算子 |
|---|---|
FROM | 表扫描 |
WHERE | 选择 / 过滤σ |
SELECT | 投影π |
JOIN | 连接⋈ |
GROUP BY | 分组聚合γ |
HAVING | 聚合后过滤 |
DISTINCT | 去重 |
ORDER BY | 排序 |
LIMIT | 限制输出行数 |
例如 SQL：
SELECT name FROM users WHERE age > 18;可以转换成逻辑查询计划：
Projection[name] └── Selection[age > 18] └── TableScan[users]用关系代数表示就是：
π_name(σ_age>18(users))意思是：
- 从
users表取数据； - 过滤
age > 18的行； - 只输出
name列。
2. 逻辑查询计划不是物理执行计划
逻辑查询计划只说明做什么，不说明怎么做。
例如：
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.customer_id;逻辑查询计划可能是：
Join[o.customer_id = c.customer_id] ├── TableScan[orders] └── TableScan[customers]它只说明要把orders和customers按条件连接起来。
但它还没有决定：
用 Hash Join 还是 Nested Loop Join？ 先扫描 orders 还是先扫描 customers？ 用全表扫描还是索引扫描？ 是否并行执行？ 内存如何分配？这些属于物理执行计划阶段。
3. 逻辑查询计划和 AST 的区别
AST 是 SQL 的语法结构，逻辑查询计划是 SQL 的关系操作语义。
同一个 SQL：
SELECT name FROM users WHERE age > 18;AST 更像：
SelectStatement ├── SelectList │ └── Column: name ├── From │ └── Table: users └── Where └── GreaterThan ├── Column: age └── Literal: 18逻辑查询计划更像：
Projection[name] └── Selection[age > 18] └── TableScan[users]区别是：
| 对比项 | AST | 逻辑查询计划 |
|---|---|---|
| 表示内容 | SQL 的语法结构 | 查询的关系代数操作 |
| 更接近 | SQL 文本 | 数据库内部执行语义 |
| 关注点 | SELECT、FROM、WHERE怎么写 | 扫描、过滤、投影、连接怎么组合 |
| 是否可优化 | 不方便直接优化 | 适合做查询重写和逻辑优化 |
4. 一个 JOIN 查询的例子
SELECT c.name, o.amount FROM customers c JOIN orders o ON c.customer_id = o.customer_id WHERE c.region = 'Asia' AND o.amount > 100;初始逻辑查询计划可能是：
Projection[c.name, o.amount] └── Selection[c.region = 'Asia' AND o.amount > 100] └── Join[c.customer_id = o.customer_id] ├── TableScan[customers] └── TableScan[orders]关系代数表示：
π_c.name,o.amount( σ_c.region='Asia' AND o.amount>100( customers ⋈_c.customer_id=o.customer_id orders ) )逻辑优化后，可以变成：
Projection[c.name, o.amount] └── Join[c.customer_id = o.customer_id] ├── Projection[c.customer_id, c.name] │ └── Selection[c.region = 'Asia'] │ └── TableScan[customers] └── Projection[o.customer_id, o.amount] └── Selection[o.amount > 100] └── TableScan[orders]也就是：
π_c.name,o.amount( π_c.customer_id,c.name(σ_c.region='Asia'(customers)) ⋈_c.customer_id=o.customer_id π_o.customer_id,o.amount(σ_o.amount>100(orders)) )这里做了两个重要优化：
选择下推：先过滤行 投影下推：先减少列5. 总结
逻辑查询计划就是数据库把 SQL 转换成的“关系代数操作树”。
它回答的是：
这个查询在逻辑上需要扫描哪些表、过滤哪些行、保留哪些列、执行哪些连接、做哪些聚合。
但它还不回答：
具体用哪个索引、哪个连接算法、哪个扫描方式、多少并行度。
这些要到物理执行计划阶段才决定。
关系代数基础
下面用一个大表总结关系代数基础符号：
| 符号 | 名称 | 作用 | 输入 | 输出 | SQL 对应 | 示例 | 说明 |
|---|---|---|---|---|---|---|---|
R、S、T | 关系 | 表示一张表或中间结果 | — | 一个关系 | 表名 / 子查询 | Student | 关系可以理解为数据库中的表 |
| 元组 | Tuple | 表中的一行 | — | 一行数据 | 一行记录 | (1, 'Alice', 20) | 关系由多个元组组成 |
| 属性 | Attribute | 表中的一列 | — | 一列字段 | 列名 | name、age | 属性组成关系的 schema |
σ_p(R) | 选择 | 按条件筛选行 | 一个关系R | 满足条件的行 | WHERE | σ_age>18(Student) | 横向筛选；保留满足谓词p的元组 |
π_A(R) | 投影 | 选择需要的列 | 一个关系R | 指定列组成的新关系 | SELECT 列 | π_name,age(Student) | 纵向裁剪；经典关系代数中投影会去重 |
R × S | 笛卡尔积 | 两个关系的所有行两两组合 | 两个关系 | 组合后的关系 | FROM R, S/CROSS JOIN | Student × Dept | 若R有 m 行、S有 n 行，结果有m × n行 |
R ⋈_p S | 条件连接 / θ 连接 | 按条件连接两个关系 | 两个关系 | 满足连接条件的组合行 | JOIN ... ON | Student ⋈_Student.dept_id=Dept.dept_id Dept | 可理解为σ_p(R × S) |
R ⋈ S | 自然连接 | 自动按同名属性连接 | 两个关系 | 按同名列匹配后的关系 | NATURAL JOIN | Student ⋈ Dept | 会合并同名属性；工程中要谨慎使用 |
R ⟕_p S | 左外连接 | 保留左表所有行，右表无匹配则补 NULL | 两个关系 | 左表完整保留的连接结果 | LEFT JOIN ... ON | Student ⟕_Student.dept_id=Dept.dept_id Dept | 不满足普通内连接的交换律 |
R ⟖_p S | 右外连接 | 保留右表所有行，左表无匹配则补 NULL | 两个关系 | 右表完整保留的连接结果 | RIGHT JOIN ... ON | Student ⟖_Student.dept_id=Dept.dept_id Dept | 可视为左右表交换后的左外连接 |
R ⟗_p S | 全外连接 | 保留左右两边所有行，无匹配处补 NULL | 两个关系 | 双方都完整保留的连接结果 | FULL OUTER JOIN | Student ⟗_Student.dept_id=Dept.dept_id Dept | SQL 支持情况因数据库而异 |
R ⋉_p S | 半连接 | 返回R中能在S找到匹配的行 | 两个关系 | 只包含左表属性的关系 | EXISTS/IN | Student ⋉_Student.dept_id=Dept.dept_id Dept | 不输出右表列；常用于子查询优化 |
R ▷_p S | 反连接 | 返回R中不能在S找到匹配的行 | 两个关系 | 只包含左表属性的关系 | NOT EXISTS/NOT IN | Student ▷_Student.dept_id=Dept.dept_id Dept | NOT IN受 NULL 影响，实际优化要谨慎 |
R ∪ S | 并 | 合并两个关系的元组 | 两个兼容关系 | 出现在R或S中的元组 | UNION | π_name(Student) ∪ π_name(Teacher) | 要求两个关系属性个数和类型兼容 |
R ∩ S | 交 | 取两个关系共同的元组 | 两个兼容关系 | 同时出现在R和S中的元组 | INTERSECT | π_name(Student) ∩ π_name(Teacher) | 不是所有数据库都直接支持INTERSECT |
R − S | 差 | 从R中去掉也在S中的元组 | 两个兼容关系 | 属于R但不属于S的元组 | EXCEPT/MINUS | π_name(Student) − π_name(Teacher) | 不满足交换律，即R − S ≠ S − R |
ρ_x(R) | 关系重命名 | 给关系改名 | 一个关系 | 改名后的关系 | 表别名 | ρ_S1(Student) | 常用于自连接 |
ρ_{a/b}(R) | 属性重命名 | 给属性改名 | 一个关系 | 改列名后的关系 | 列别名 | ρ_{student_name/name}(Student) | 防止列名冲突或统一 schema |
γ_G,F(R) | 分组聚合 | 按属性分组并计算聚合函数 | 一个关系 | 聚合后的关系 | GROUP BY | γ_dept_id,COUNT(*)(Student) | G是分组列，F是聚合函数 |
δ(R) | 去重 | 删除重复元组 | 一个关系 | 无重复元组的关系 | DISTINCT | δ(Student) | 经典关系代数默认集合语义；SQL 默认多重集语义 |
τ_A(R) | 排序 | 按属性排序 | 一个关系 | 有序结果 | ORDER BY | τ_age DESC(Student) | 经典关系代数通常无序，排序属于扩展算子 |
LIMIT_n(R) | 限制行数 | 只取前 n 行 | 一个关系 | 最多 n 行 | LIMIT/FETCH FIRST | LIMIT_10(Student) | 通常需要和排序一起使用才有确定意义 |
attrs(R) | 属性集合 | 表示关系R的所有列 | 一个关系 | 属性集合 | schema | attrs(Student) | 常用于描述规则前提 |
attrs(p) | 谓词属性集合 | 表示条件p用到的列 | 一个谓词 | 属性集合 | 条件涉及列 | attrs(age > 18) = {age} | 常用于判断谓词能否下推 |
p、q | 谓词 | 过滤或连接条件 | 表达式 | TRUE / FALSE / UNKNOWN | WHERE/ON | age > 18 | SQL 中还要考虑 NULL 三值逻辑 |
A ⊆ B | 子集 | 表示属性集合包含关系 | 两个集合 | 布尔判断 | — | {name} ⊆ {id,name,age} | 常用于投影规则前提 |
≡ | 等价 | 表示两个表达式结果相同 | 两个表达式 | 等价关系 | 查询重写 | σ_p(σ_q(R)) ≡ σ_{p AND q}(R) | 查询优化的理论基础 |
最核心的几个：
| 符号 | 口诀 | SQL 对应 |
|---|---|---|
σ | 选行 | WHERE |
π | 选列 | SELECT |
⋈ | 连表 | JOIN |
γ | 分组统计 | GROUP BY |
∪ / ∩ / − | 集合运算 | UNION / INTERSECT / EXCEPT |
ρ | 改名 | 别名AS |
回到顶部
查询重写 / 逻辑优化
回到顶部
一、查询重写 / 逻辑优化阶段的作用
在数据库系统中，用户提交的是 SQL 查询，而数据库内部通常不会直接执行 SQL 文本。SQL 会先被解析成一种内部表示，例如：
SQL 语句 → 语法树 AST → 逻辑查询计划 → 关系代数表达式 → 物理执行计划