DBMS笔记 05 关系查询处理与查询优化

第五章：关系查询处理与查询优化

5.1 查询处理

查询处理阶段：

1. 查询分析：语法、语义、视图检查、合法性。
2. 查询检查：安全性检查（用户权限）、视图展开、转换成关系代数表达式。
3. 查询优化：生成高效的执行策略。
4. 查询执行：生成并执行查询计划。

分析 → 检查 → 优化 → 执行。

---

5.2 查询优化

分类

1. 代数优化：用关系代数等价变换，优化表达式。
2. 物理优化：选择高效的存取路径和操作算法。

优化方法

• 基于规则 (rule-based)：按固定规则简化表达式。
• 基于代价 (cost-based)：估算 I/O、CPU，选代价最小的。
• 基于语义 (semantic-based)：利用约束条件（如主键、外键）简化查询。

优化目标

• 选择高效的执行策略。
• 主要衡量：I/O 代价 + CPU 代价（I/O 为主）。

---

5.3 代数优化

关系代数常见等价规则

1. 选择运算的交换律、结合律。
2. 投影与选择的交换。
3. 选择与连接的交换。
4. 投影与连接的交换。
5. 连接交换律、结合律。
6. 并、差、交的交换律。

能下推的选择尽量下推，减少中间结果大小：

• 尽可能先执行选择/投影。
• 把选择条件尽早下推到数据源。
• 投影尽早，减少属性数。
• 把笛卡尔积 + 选择 转换为连接。

---

5.4 物理优化

物理优化手段

1. 存取路径选择
   • 有索引：用索引。
   • 无索引：全表扫描。
   • AND 条件：可选交集索引。
   • OR 条件：用并集索引。
2. 连接算法优化
   • 嵌套循环连接 (Nested Loop Join)：逐条扫描。适合小表嵌套大表。
   • 排序-合并连接 (Sort-Merge Join)：两边排好序后合并。
   • 索引连接 (Index Join)：用一表索引快速查另一表。
   • 哈希连接 (Hash Join)：用哈希表匹配。

---

概念对比

• 代数优化 vs 物理优化
  • 代数优化：式子层面，用等价变换简化。
  • 物理优化：执行层面，选路径、算法。
• 基于规则 vs 基于代价
  • 规则：固定启发式，不算代价。
  • 代价：估算 I/O/CPU，选开销最小。
• 选择下推
  • WHERE 条件越早用越好（减少中间结果）。
• 连接算法区别
  • 嵌套循环：最笨，适合小表。
  • 排序合并：需要排序。
  • 索引连接：依赖索引。
  • 哈希连接：适合大数据。

---

重点复习

1. 查询代价最重要是 I/O 代价 ✅
   I/O 比 CPU 消耗大，通常是瓶颈。
2. 代数优化先做的操作 → 尽早选择运算 ✅
   减少中间结果。
3. 物理优化时 AND 条件 → 多个索引时取交集。
   OR 条件 → 索引并集。
4. 错误选项常见陷阱
   • “尽早做笛卡尔积” ❌ （应避免笛卡尔积）
   • “HAVING 可以代替 WHERE” ❌ （用途不同）
   • “DROP 删除数据” ❌ （是删除表定义）
5. 连接算法易考
   • 小表 + 大表 → 嵌套循环。
   • 两表已排序 → 排序合并。
   • 一边有索引 → 索引连接。
   • 大表 & 无索引 → 哈希连接。

---

速记

• 查询处理 4 步：分析 → 检查 → 优化 → 执行
• 优化方法 3 种：规则 / 代价 / 语义
• 代数优化口诀：尽早选择、尽早投影、避免笛卡尔积
• 物理优化口诀：小表套大表、排序用合并、有索引用索引、大数据用哈希