数据库查询优化器＜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 > 18

AST 的作用主要有三个：

1. 让数据库理解 SQL 的结构
   SQL 文本只是字符串，数据库不能直接优化字符串，必须先把它变成结构化形式。
2. 为语义分析做准备
   例如检查users表是否存在、age列是否存在、类型是否匹配、函数是否合法等。
3. 为逻辑计划生成做准备
   数据库会根据 AST 生成逻辑查询计划，例如选择、投影、连接等关系代数表达式。

可以把整个流程理解为：

SQL 文本 → 词法分析：拆成 token → 语法分析：生成 AST → 语义分析：检查表名、列名、类型 → 逻辑计划：关系代数表达式 → 逻辑优化：查询重写 → 物理计划：选择具体执行算法 → 执行

简单说：

AST 是数据库把 SQL 从“字符串”变成“结构化语法表示”的第一步。

它还不是执行计划，只是 SQL 的语法骨架。

逻辑查询计划

逻辑查询计划是数据库把 SQL 的含义转换成的一种关系代数形式的操作树。它描述“要做哪些逻辑操作”，但还不决定“具体用什么物理算法执行”。

可以理解为：

SQL 文本 → AST 抽象语法树 → 语义分析 → 逻辑查询计划 → 逻辑优化 → 物理执行计划 → 执行

1. 逻辑查询计划描述什么

逻辑查询计划主要描述这些逻辑算子：

例如 SQL：

SELECT name FROM users WHERE age > 18;

可以转换成逻辑查询计划：

Projection[name] └── Selection[age > 18] └── TableScan[users]

用关系代数表示就是：

π_name(σ_age>18(users))

意思是：

1. 从users表取数据；
2. 过滤age > 18的行；
3. 只输出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]

区别是：

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 查询，而数据库内部通常不会直接执行 SQL 文本。SQL 会先被解析成一种内部表示，例如：

SQL 语句 → 语法树 AST → 逻辑查询计划 → 关系代数表达式 → 物理执行计划

查询重写 / 逻辑优化发生在生成物理执行计划之前。它的核心目标是：

在不改变查询语义的前提下，将原始查询转换为更容易执行、代价更低的等价逻辑查询计划。

也就是说，逻辑优化阶段并不直接决定“用哈希连接还是嵌套循环连接”，那属于物理优化阶段。逻辑优化主要处理的是：

能不能少读一些行？ 能不能少保留一些列？ 能不能把过滤条件提前？ 能不能把子查询改成连接？ 能不能改变连接顺序？ 能不能消除无用的 JOIN、DISTINCT、GROUP BY？

例如，SQL：

SELECT o.order_id, c.name FROM orders o JOIN customers c ON o.customer_id = c.customer_id WHERE c.region = 'Asia';

可以先抽象为关系代数表达式：

π_order_id, name ( σ_region='Asia' ( orders ⋈ orders.customer_id = customers.customer_id customers ) )

逻辑优化器可能将选择条件下推：

π_order_id, name ( orders ⋈ orders.customer_id = customers.customer_id σ_region='Asia'(customers) )

这样可以先过滤customers，再进行连接，从而减少连接输入规模。

回到顶部

二、关系代数符号约定

下面使用常见关系代数符号：

其中，选择、投影、连接是逻辑优化中最重要的几个算子。

回到顶部

三、选择运算的等价规则

选择运算σ对应 SQL 中的WHERE或部分HAVING条件。

1. 选择级联规则

如果一个关系上连续做多次选择：

σ_p(σ_q(R)) ≡ σ_p AND q(R)

也就是说：

先过滤 q，再过滤 p

等价于：

一次性过滤 p AND q

例如 SQL：

SELECT * FROM users WHERE age > 18 AND city = 'Tokyo';

可以看作：

σ_age>18 AND city='Tokyo'(users)

也可以看作：

σ_age>18(σ_city='Tokyo'(users))

两者等价。

2. 选择交换规则

连续选择的顺序可以交换：

σ_p(σ_q(R)) ≡ σ_q(σ_p(R))

例如：

σ_age>18(σ_city='Tokyo'(users))

等价于：

σ_city='Tokyo'(σ_age>18(users))

这个规则说明，多个过滤条件之间的执行顺序可以重新排列。优化器通常会优先执行选择率更高的条件，也就是更能减少数据量的条件。

3. 选择条件分解规则

复合条件可以拆成多个简单条件：

σ_p AND q(R) ≡ σ_p(σ_q(R))

例如：

σ_age>18 AND city='Tokyo'(users)

可以分解为：

σ_age>18(σ_city='Tokyo'(users))

这条规则是谓词下推的基础。优化器可以把不同的过滤条件推到不同的数据源上。

回到顶部

四、投影运算的等价规则

投影运算π对应 SQL 中的SELECT列表。它的作用是保留需要的列，丢弃不需要的列。

1. 投影级联规则

如果连续做多次投影，只需要保留最外层需要的属性：

π_A(π_B(R)) ≡ π_A(R)

前提是：

A ⊆ B

例如：

π_name(π_id,name,age(users))

等价于：

π_name(users)

这说明中间多余的投影可以被消除。

2. 投影下推规则

对于连接查询：

π_A(R ⋈_p S)

可以重写为：

π_A( π_B(R) ⋈_p π_C(S) )

其中：

B = A 中属于 R 的属性 ∪ 连接条件 p 中属于 R 的属性 C = A 中属于 S 的属性 ∪ 连接条件 p 中属于 S 的属性

例如 SQL：

SELECT o.order_id, c.name FROM orders o JOIN customers c ON o.customer_id = c.customer_id;

最终只需要：

orders.order_id customers.name

但是连接条件还需要：

orders.customer_id customers.customer_id

所以可以在连接前裁剪列：

π_order_id, name ( π_order_id, customer_id(orders) ⋈ orders.customer_id = customers.customer_id π_customer_id, name(customers) )

投影下推的作用是减少中间结果的宽度，降低内存、网络传输和连接代价。

回到顶部

五、选择与投影的交换规则

选择和投影有时可以交换：

σ_p(π_A(R)) ≡ π_A(σ_p(R))

前提是条件p涉及的属性都包含在A中。

如果p中使用了某些最终不输出的列，则需要先临时保留这些列：

π_A(σ_p(R)) ≡ π_A(σ_p(π_{A ∪ attrs(p)}(R)))

其中attrs(p)表示谓词p中涉及的属性集合。

例如：

SELECT name FROM users WHERE age > 18;

虽然最终只输出name，但是过滤条件需要age，因此不能一开始只保留name，而应当先保留：

name, age

逻辑形式为：

π_name( σ_age>18( π_name, age(users) ) )

回到顶部

六、笛卡尔积与连接的转换规则

SQL 中旧式连接写法：

SELECT * FROM R, S WHERE R.a = S.b;

在关系代数中可以表示为：

σ_R.a=S.b(R × S)

它等价于条件连接：

R ⋈_R.a=S.b S

因此有规则：

σ_p(R × S) ≡ R ⋈_p S

这是非常重要的重写规则。因为真正执行笛卡尔积通常代价极高，而连接算子可以使用索引、哈希、排序等物理方法高效执行。

回到顶部

七、连接运算的等价规则

连接是查询优化中最核心的部分。多表查询的性能往往主要取决于连接顺序和连接输入规模。

1. 内连接交换律

对于内连接：

R ⋈_p S ≡ S ⋈_p R

例如：

orders JOIN customers

和：

customers JOIN orders

在逻辑上是等价的，只要连接条件正确调整。

这个规则允许优化器决定先访问哪张表。

2. 内连接结合律

对于内连接：

(R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T)

例如三表连接：

(orders ⋈ customers) ⋈ regions

可以改写为：

orders ⋈ (customers ⋈ regions)

这使得优化器可以枚举不同的连接顺序。

例如，如果customers ⋈ regions的结果很小，那么先执行这个连接可能更优。

3. 选择下推到连接

如果选择条件只涉及关系R中的属性：

σ_p(R ⋈ S) ≡ σ_p(R) ⋈ S

前提：

attrs(p) ⊆ attrs(R)

类似地，如果条件只涉及S：

σ_p(R ⋈ S) ≡ R ⋈ σ_p(S)

例如：

SELECT * FROM orders o JOIN customers c ON o.customer_id = c.customer_id WHERE c.region = 'Asia';

关系代数原式：

σ_c.region='Asia'( orders ⋈ orders.customer_id = customers.customer_id customers )

可以重写为：

orders ⋈ orders.customer_id = customers.customer_id σ_region='Asia'(customers)

这就是典型的谓词下推。

4. 连接条件分解

如果连接条件由多个条件组成：

R ⋈_{p AND q} S

可以写成：

σ_q(R ⋈_p S)

或者：

σ_p AND q(R × S)

优化器可以根据不同条件的性质决定如何处理。例如，等值条件可能适合哈希连接，范围条件可能适合索引范围扫描或嵌套循环连接。

5. 多表连接重排

利用交换律和结合律，多表连接可以重排：

(A ⋈ B) ⋈ C

可以变成：

(A ⋈ C) ⋈ B

也可以变成：

A ⋈ (B ⋈ C)

在数据库优化器中，连接重排是最重要的优化之一。对于n张表的连接，可能的连接顺序非常多，因此优化器通常需要结合代价估计来选择较优方案。

回到顶部

八、并、交、差的等价规则

集合运算在关系代数中也有一系列等价规则。

1. 并集交换律

R ∪ S ≡ S ∪ R

2. 并集结合律

(R ∪ S) ∪ T ≡ R ∪ (S ∪ T)

3. 交集交换律

R ∩ S ≡ S ∩ R

4. 交集结合律

(R ∩ S) ∩ T ≡ R ∩ (S ∩ T)

5. 选择对并集的分配

σ_p(R ∪ S) ≡ σ_p(R) ∪ σ_p(S)

6. 投影对并集的分配

π_A(R ∪ S) ≡ π_A(R) ∪ π_A(S)

7. 选择对交集的分配

σ_p(R ∩ S) ≡ σ_p(R) ∩ σ_p(S)

8. 差集的注意事项

差集通常不满足交换律：

R − S ≠ S − R

也不满足普通结合律：

(R − S) − T ≠ R − (S − T)

因此优化器对差集的重写必须更加谨慎。

回到顶部

九、重命名规则

重命名算子ρ用于处理属性名或关系名冲突，尤其在自连接中非常重要。

例如：

SELECT * FROM employee e1 JOIN employee e2 ON e1.manager_id = e2.employee_id;

同一张表employee出现两次，因此需要重命名：

ρ_e1(employee) ⋈ e1.manager_id = e2.employee_id ρ_e2(employee)

重命名可以与选择、投影交换，但必须同步修改属性名：

ρ(σ_p(R)) ≡ σ_ρ(p)(ρ(R)) ρ(π_A(R)) ≡ π_ρ(A)(ρ(R))

其中ρ(p)表示将谓词中的属性名按重命名规则替换。

回到顶部

十、半连接与反连接规则

很多 SQL 子查询可以转化为半连接或反连接。

1. 半连接

半连接记作：

R ⋉_p S

它表示：

返回R中能够在S中找到匹配的元组，但不输出S的列。

半连接可以用普通连接和投影表示：

R ⋉_p S ≡ π_attrs(R)(R ⋈_p S)

SQL 中的EXISTS和部分IN子查询常常可以改写为半连接。

例如：

SELECT * FROM customers c WHERE EXISTS ( SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id );

可以表示为：

customers ⋉ customers.customer_id = orders.customer_id orders

2. 反连接

反连接记作：

R ▷_p S

它表示：

返回R中无法在S中找到匹配的元组。

反连接可以用差集表示：

R ▷_p S ≡ R − π_attrs(R)(R ⋈_p S)

SQL 中的NOT EXISTS通常可以改写为反连接。

例如：

SELECT * FROM customers c WHERE NOT EXISTS ( SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id );

可以表示为：

customers ▷ customers.customer_id = orders.customer_id orders

回到顶部

十一、子查询重写规则

SQL 中的子查询通常会被逻辑优化器改写成连接、半连接、反连接或聚合连接。

1.IN子查询改写为半连接

SQL：

SELECT * FROM orders WHERE customer_id IN ( SELECT customer_id FROM customers WHERE region = 'Asia' );

逻辑形式可以改写为：

orders ⋉ orders.customer_id = customers.customer_id σ_region='Asia'(customers)

这里半连接只判断orders.customer_id是否出现在右侧结果中，不需要输出customers的列。

2.EXISTS子查询改写为半连接

SQL：

SELECT * FROM customers c WHERE EXISTS ( SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id );

关系代数形式：

customers ⋉ customers.customer_id = orders.customer_id orders

3.NOT EXISTS子查询改写为反连接

SQL：

SELECT * FROM customers c WHERE NOT EXISTS ( SELECT 1 FROM orders o WHERE o.customer_id = c.customer_id );

关系代数形式：

customers ▷ customers.customer_id = orders.customer_id orders

4. 标量子查询改写

SQL：

SELECT * FROM orders WHERE amount > ( SELECT AVG(amount) FROM orders );

可以理解为先计算聚合结果：

γ_AVG(amount)(orders)

然后再与外层查询结合：

σ_orders.amount > avg_amount( orders × γ_AVG(amount)(orders) )

在实际优化中，数据库通常会将这个标量子查询单独计算一次，再作为常量或单行关系参与过滤。

回到顶部

十二、聚合与分组的等价规则

扩展关系代数中，分组聚合通常写作：

γ_G, F(R)

其中：

G 表示分组属性 F 表示聚合函数

例如：

SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id;

可以写成：

γ_customer_id, COUNT(*)(orders)

1. 分组键上的选择可以下推

如果选择条件只涉及分组键，则可以下推到聚合之前：

σ_p(γ_G, F(R)) ≡ γ_G, F(σ_p(R))

前提：

attrs(p) ⊆ G

例如：

SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id HAVING customer_id > 100;

可以改写为：

SELECT customer_id, COUNT(*) FROM orders WHERE customer_id > 100 GROUP BY customer_id;

关系代数表示为：

σ_customer_id>100( γ_customer_id, COUNT(*)(orders) )

改写为：

γ_customer_id, COUNT(*)( σ_customer_id>100(orders) )

2. 聚合结果上的选择不能下推

如果条件依赖聚合结果，则不能下推。

例如：

SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id HAVING COUNT(*) > 10;

关系代数形式：

σ_COUNT(*)>10( γ_customer_id, COUNT(*)(orders) )

这里COUNT(*)是聚合之后才产生的值，因此不能改写为：

γ_customer_id, COUNT(*)( σ_COUNT(*)>10(orders) )

因为原始orders表中并不存在COUNT(*)这个属性。

3. 聚合前投影下推

聚合前只需要保留分组列和聚合函数使用的列：

γ_G, F(A)(R) ≡ γ_G, F(A)(π_{G ∪ A}(R))

例如：

SELECT customer_id, SUM(amount) FROM orders GROUP BY customer_id;

只需要保留：

customer_id, amount

因此可写为：

γ_customer_id, SUM(amount)( π_customer_id, amount(orders) )

回到顶部

十三、外连接相关的逻辑重写

外连接比内连接复杂，因为外连接会产生 NULL 填充行。因此，内连接的交换律和结合律不能简单应用到外连接上。

1. 外连接不能随意交换

一般来说：

R ⟕ S ≠ S ⟕ R

其中⟕表示左外连接。

例如：

A LEFT JOIN B ON A.id = B.a_id

表示保留A中所有行。

而：

B LEFT JOIN A ON A.id = B.a_id

表示保留B中所有行。

两者语义不同。

2. 外连接转内连接

在某些情况下，外连接可以转换为内连接。

例如：

SELECT * FROM orders o LEFT JOIN customers c ON o.customer_id = c.customer_id WHERE c.region = 'Asia';

这个查询中，WHERE c.region = 'Asia'会过滤掉右表为 NULL 的行。因此，左外连接产生的 NULL 扩展行不会保留下来。

所以它等价于：

SELECT * FROM orders o JOIN customers c ON o.customer_id = c.customer_id WHERE c.region = 'Asia';

关系代数上可以理解为：

σ_c.region='Asia'(orders ⟕ customers) ≡ σ_c.region='Asia'(orders ⋈ customers)

前提是谓词c.region = 'Asia'对 NULL 不成立，也就是它会拒绝 NULL 扩展行。这类谓词称为null-rejecting predicate。

回到顶部

十四、视图展开规则

如果查询引用了视图，优化器通常会先将视图展开成其定义。

例如：

CREATE VIEW asia_customers AS SELECT * FROM customers WHERE region = 'Asia';

查询：

SELECT name FROM asia_customers WHERE age > 30;

展开为：

SELECT name FROM customers WHERE region = 'Asia' AND age > 30;

关系代数表示：

π_name( σ_age>30( σ_region='Asia'(customers) ) )

根据选择级联规则，可进一步合并为：

π_name( σ_region='Asia' AND age>30(customers) )

回到顶部

十五、连接消除规则

如果一个连接不会影响查询结果，则可以被消除。

例如：

SELECT o.order_id, o.amount FROM orders o JOIN customers c ON o.customer_id = c.customer_id;

如果满足：

orders.customer_id 是外键 customers.customer_id 是主键或唯一键 查询结果不使用 customers 的任何列 连接不会过滤 orders 的行

那么该查询可以改写为：

SELECT o.order_id, o.amount FROM orders o;

关系代数上可以理解为：

π_order_id, amount( orders ⋈ orders.customer_id = customers.customer_id customers ) ≡ π_order_id, amount(orders)

但这条规则依赖完整性约束，例如主键、外键、唯一性和非空约束。没有这些约束时，不能随意消除连接。

回到顶部

十六、DISTINCT 与重复消除规则

在纯关系代数中，关系通常被看作集合，不包含重复元组。而 SQL 默认是多重集语义，即允许重复行。

因此，涉及DISTINCT的优化必须特别注意。

如果某列本身已经唯一：

SELECT DISTINCT customer_id FROM customers;

并且customer_id是主键，则：

SELECT DISTINCT customer_id FROM customers;

等价于：

SELECT customer_id FROM customers;

关系代数中可以理解为：如果customer_id是唯一属性，那么对它做重复消除没有意义。

类似地：

δ(π_key(R)) ≡ π_key(R)

其中δ表示重复消除，前提是key是唯一键。

回到顶部

十七、常见逻辑优化规则总结表

回到顶部

十八、一个完整示例

考虑 SQL：

SELECT c.name FROM customers c JOIN orders o ON c.customer_id = o.customer_id WHERE c.region = 'Asia' AND o.amount > 100;

1. 初始关系代数表达式

π_c.name( σ_c.region='Asia' AND o.amount>100( customers ⋈ c.customer_id=o.customer_id orders ) )

2. 选择条件分解

π_c.name( σ_c.region='Asia'( σ_o.amount>100( customers ⋈ c.customer_id=o.customer_id orders ) ) )

3. 选择下推

π_c.name( σ_c.region='Asia'(customers) ⋈ c.customer_id=o.customer_id σ_o.amount>100(orders) )

4. 投影下推

最终只需要c.name，连接还需要两边的customer_id，所以：

π_c.name( π_customer_id, name( σ_region='Asia'(customers) ) ⋈ c.customer_id=o.customer_id π_customer_id( σ_amount>100(orders) ) )

这样得到的逻辑计划相比初始计划更优：

先过滤 customers.region = 'Asia' 先过滤 orders.amount > 100 只保留连接和输出需要的列 再进行 JOIN 最后输出 name

这正是逻辑优化的基本思想。

回到顶部

十九、关系代数等价规则在 SQL 中的限制

教科书中的关系代数通常基于集合语义，但 SQL 具有更多复杂特性。因此，实际数据库优化器在使用这些规则时必须考虑以下因素：