11. 查询优化

1. Motivation (动机)

性能差异巨大：同一个 SQL 查询可以转化为多种等价的关系代数表达式。好计划和坏计划的代价差异可能是天壤之别（Enormous）。
依赖统计：为了选出最优计划，数据库必须维护统计信息（如行数、分布），以便估算中间结果的大小。

2. Concepts (核心概念)

优化通常结合两种流派：

2.1 基于代价的优化 (Cost-based Optimization)

生成 (Generate) -> 估算 (Estimate) -> 选择 (Choose) 最便宜的计划。

2.2 启发式优化 (Heuristic Optimization)

利用经验规则变换查询树。
★ 两大金科玉律 (Golden Rules)：
1. 尽早执行选择 (Perform selection early)：目的是减少行数（Tuples）。
2. 尽早执行投影 (Perform projection early)：目的是减少列数（Attributes），降低内存占用。

3. Methods: 核心等价规则与实例 (Equivalence Rules)

这是考试中进行树变换的法律依据。理解这些规则的“变换前 vs 变换后”是解题关键。

3.1 选择操作 (Selection, ) —— 最核心

核心思想：尽早过滤 (Filter Early)。

规则 1：串接/拆分律 (Cascade/Splitting)
- 公式：
- 场景：查找“CS 系”且“>20 岁”的学生。
- 变换前：一次性检查两个条件。
- 变换后：拆分成两层。
- 目的：拆分是为了方便后续将某个条件独立下推。
规则 2：交换律 (Commutativity)
- 公式：
- 应用：过滤性越强（能剔除更多数据）的条件，应该越先执行。
规则 3：分配律/下推 (Pushing Selection Down) —— ★★★ 必考
- 公式：（假设条件只涉及 R）
- 场景：连接 Student 和 Course，但只关心 CS 系的学生。
- Bad Plan：先让 Student 和 Course 做巨大的 Join，再从结果中找 CS 系。
- Good Plan：先在 Student 表里筛选出 CS 系（假设只剩 100 人），再让这 100 人去 Join。
- 收益：极大地减少了 Join 操作的数据量。

3.2 投影操作 (Projection, )

核心思想：尽早瘦身 (Slim Down)。

规则：下推投影 (Pushing Projection)
- 公式：
- 场景：连接 Student 和 Course，最后只显示 Name 和 Title。
- Bad Plan：带着家庭住址、电话、课程介绍等所有列去做 Join，内存爆炸。
- Good Plan：
  1. Student 表只保留 ID, Name。
  2. Course 表只保留 SID, Title。
  3. 两个“瘦身”后的表做 Join。
- 收益：减少元组宽度，提高内存利用率。

3.3 连接操作 (Join, )

核心思想：谁生成的结果小，谁先连。

规则：结合律 (Associativity)
- 公式：
- 场景：表 T1 (1000行), T2 (1000行), T3 (2行)。
  - T1 和 T2 连接产生 100万行。
  - T2 和 T3 连接产生 5行。
- Bad Plan： -> 中间产生 100 万行数据，慢死。
- Good Plan： -> 中间只产生 5 行数据，秒杀。

4. Heuristic Algorithm (启发式优化步骤)

做题时的标准流程（请背诵）：

拆分 (Deconstruct)：利用规则 1，将 AND 连接的复杂条件拆分为单个小条件。
下推选择 (Push Selections Down)：利用规则 3，将选择操作尽可能压到树的叶节点（Relation）上方。这是最有效的优化。
下推投影 (Push Projections Down)：将投影操作尽可能下推，在叶节点上方创建新的投影，丢弃无用列。
重组连接 (Reorder Joins)：利用结合律，先执行能产生最小中间结果的连接。
合并 (Combine)：将“笛卡尔积 + 随后的选择”合并为“连接 (Join)”操作。

5. Exam Guide: How to Draw Query Trees (考试画图实战指南)

这是考试中最常见的题型，分为画“初始树”和“优化树”。

A. 初始查询树 (Initial/Canonical Query Tree)

原则：最笨的执行方式，严格对应 SQL 语法结构。

叶子 (Leaves)：将 FROM 子句中的所有表列在底部。
笛卡尔积 ()：从下往上，用将所有表两两相连。
选择 ()：在最顶层的上方画一个巨大的。关键：将 WHERE 子句中的所有条件（包括连接条件 A.id=B.id 和过滤条件 age>20）全部写在这个里。
投影 ()：在上方画，列出 SELECT 后的列名。

B. 优化后的查询树 (Optimized Query Tree)

原则：应用启发式规则，先过滤后连接。

叶子处理：表仍在底部，但每个表的头顶立刻画上属于它的单表过滤条件 ()（如 age>20）。
连接 ()：用代替。关键：将连接条件（如 A.id=B.id）直接写在符号旁边。
投影 ()：最后在顶部画。

6. Examples (典型例题解析)

案例：Library (LBI) 数据库优化

查询：找到 Date < 5/1/2018 的书籍 Title。

涉及表：Book, Borrow, Card。

演变过程 (Evolution)：

初始状态 (Canonical Tree)：

底部是 Book X Borrow X Card（笛卡尔积）。
顶部是一个巨大的（包含连接条件 Book.id=Borrow.id 等和过滤条件 Date < ...）。
评价：效率极低，中间结果巨大。

Step 1: 拆分 (Split)

将巨大的拆成三个独立的：两个连接条件，一个日期过滤条件。

Step 2: 下推选择 (Push Selection)

发现 Date < ... 只跟 Borrow 表有关。
操作：直接把这个条件压到 Borrow 表头顶。
操作：把连接条件变为 Join ()。
结果：在 Join 发生前，大部分借阅记录已经被过滤掉了。

Step 3: 下推投影 (Push Projection)

发现最后只要 Title。
操作：在 Book 表上只保留 Title, BookNo；在 Card 表上只保留 CardNo。
结果：参与 Join 的表变“瘦”了。

最终结果：

一棵高度优化的树：叶子节点先做和（既少行又少列），中间节点做（连接），完全避免了笛卡尔积。

7. 复习口诀 (Summary)

“选择投影皆下推，先做小表后做堆。”

看到 AND -> 拆分。
看到 (Selection) -> 下推到叶子（最重要）。
看到 (Projection) -> 下推以瘦身。
看到 多表连接 -> 调整顺序（小结果先连）。