关系代数如何优化查询树

在数据库系统中，关系代数查询树的优化是提高查询执行效率的关键步骤。优化的目标是：减少中间结果的大小、减少 I/O 次数、尽早过滤数据、选择高效算法。下面从基本概念 → 优化原则 → 常用优化技术 → 示例系统说明。

一、什么是查询树（Query Tree）

• 查询树是用关系代数操作符表示的查询执行计划
• 叶子节点：关系（表）
• 内部节点：选择（σ）、投影（π）、连接（⋈）、并（∪）等操作

示例：

        π
        |
       ⋈
      / \
     σ   R
     |
     S

二、关系代数优化的基本思想

核心原则：

1. 先做选择（σ），后做连接（⋈）
2. 先做投影（π），减少列数
3. 让代价小的操作先做
4. 利用等价变换规则重写查询树

三、常用的关系代数优化规则

1. 选择下推（Selection Pushdown）⭐最重要

规则：

σ_条件(R ⋈ S)  ≡  (σ_条件1(R)) ⋈ (σ_条件2(S))

• 将选择尽可能下推到叶子节点
• 尽早减少元组数量

✅ 好处：减少连接时的数据量

2. 投影下推（Projection Pushdown）

规则：

π_属性(R ⋈ S)  ≡  π_属性( π_属性(R) ⋈ π_属性(S) )

• 只保留后续需要的列
• 减少中间结果宽度

3. 选择与投影交换

σ(π(R)) ≡ π(σ(R))   （属性兼容时）

• 顺序可调整，以更优者优先

4. 连接顺序优化（Join Reorder）

对于多表连接：

(R ⋈ S) ⋈ T

• 选择结果最小的连接顺序
• 通常：小表先连，选择性高的条件先连

5. 合并连续选择

σ_c1(σ_c2(R)) ≡ σ_(c1 ∧ c2)(R)

• 减少操作符数量

6. 利用索引

• σ、⋈ 若涉及索引属性，优先使用索引扫描
• 查询优化器会结合代价模型选择

四、优化示例

原始查询

SELECT A
FROM R, S
WHERE R.x = S.x AND R.y > 10

原始查询树

        π_A
         |
        ⋈(R.x=S.x)
       / \
      R   S
（选择 R.y>10 未下推）

优化后查询树

        π_A
         |
   ⋈(R.x=S.x)
   / \
 σ_y>10(R)  S

✅ 先过滤 R 中 90% 的数据，再连接

五、查询优化的两个层面

1. 逻辑优化（代数级）
   • 使用等价规则重写查询树
2. 物理优化（执行级）
   • 选择扫描方式（全表 / 索引）
   • 选择连接算法（嵌套循环 / 哈希 / 排序合并）

六、总结口诀

选择下推早过滤，
投影下推少字段，
连接顺序重代价，
等价变换提效率。

如果你愿意，我也可以：

• 用具体 SQL + 查询树图讲解
• 对比 MySQL / PostgreSQL 优化器
• 结合考试题 / 数据库原理考点讲