数据库系统（五）数据库查询优化

数据库查询优化

📌 本讲学习目标

• 基本内容
  1. 理解查询优化的必要性和概念
  2. 掌握查询优化的基本思路
  3. 掌握逻辑查询优化方法
  4. 理解物理查询优化方法
• 重点难点
  • 查询优化的整体思路
  • 基于关系代数的逻辑查询优化
  • 物理查询优化的代价估算方法

---

🔍 什么是查询优化？

为什么需要查询优化

• 执行效率问题：不同操作顺序导致性能差异巨大

  -- 示例：检索选修"DB"课程的学生姓名
  π Sname (σ Cname='DB' (Student × SC × Course))

  • 数据量估算：
    • Student: 10,000条
    • SC: 500,000条 (10000学生×50课程)
    • Course: 1,000条
    • 笛卡尔积结果: 10000×500000×1000 = 5×10¹²条

查询优化的定义

核心目标：使数据库查询的执行时间最短
优化层面：

1. 语义优化：利用模型语义和完整性规则
2. 语法优化（逻辑层）：优化操作执行顺序
3. 执行优化（物理层）：选择存取路径和执行算法

---

🧠 查询优化总体思路

三层优化框架

graph LR
A[SQL查询] --> B[逻辑查询计划]
B --> C[物理查询计划]
C --> D[执行结果]

1. 语义优化

• 去掉无关的表和属性
• 改写成等价但更高效的语句
• 依据：完整性规则和模型语义

2. 语法优化（逻辑层）

• 核心策略：
  • 尽早执行选择运算（σ）
  • 尽早执行投影运算（π）
• 等价变换定理：

  -- 原始
  π A1..An (σ Cond (R1 × ... × Rm))
  
  -- 优化后
  π A1..An (σ Cond (π a1(σ Cond(R1)) × ... × π am(σ Cond(Rm)))

3. 执行优化（物理层）

• 为每个关系操作选择最优算法
• 基于代价估算选择执行方案
• 关键组件：
  • 统计信息（数据字典）
  • 算法库（不同操作的实现）
  • 代价估算模型

---

⚙️ 逻辑层查询优化

优化策略

1. 尽早做选择和投影：减少中间结果大小
2. 串接一元运算：单次扫描完成多个操作
3. 投影与二元运算结合：避免多次扫描
4. 选择与笛卡尔积合并为连接

   σ F(R × S) → R ⋈ F S  -- 当F涉及R和S的属性比较时

5. 连接前预处理：排序/建立临时索引
6. 处理公共子表达式：预先计算复用结果

等价变换定理

定理	描述	公式
L3	投影串接	π A(π B(E)) ≡ π A(E)
L4	选择串接	σ F1(σ F2(E)) ≡ σ F1∧F2(E)
L6	选择与积交换	σ F(R×S) ≡ σ F(R)×S (F仅涉R属性)
L7	投影与积交换	π A(R×S) ≡ π B(R)×π C(S)
L8	选择与并交换	σ F(E1∪E2) ≡ σ F(E1)∪σ F(E2)

---

⚡ 物理层查询优化

优化要素

graph TD
A[统计信息] --> B[代价估算]
B --> C[算法选择]
C --> D[查询计划生成]

关键统计信息

符号	含义
T(R)	关系R的元组数
B(R)	关系R占用的磁盘块数
V(R,A)	属性A的不同值数量
SC(R,A)	属性A的选择基数

代价估算方法

1. 投影运算：

   • T(π L(R)) = T(R) （仅影响列数）

2. 选择运算：

   • 等值选择：T(σ A=c(R)) ≈ T(R)/V(R,A)
   • 范围选择：T(σ A<c(R)) ≈ T(R)/3
   • 复合条件：

     T(σ C1∧C2(R)) ≈ T(R)/(V(R,A)*3)
     T(σ C1∨C2(R)) = n[1-(1-m1/n)(1-m2/n)]

3. 连接运算：

   T(R ⋈ S) = T(R)T(S)/max(V(R,Y), V(S,Y))

统计信息收集

• DB2：RUNSTATS ON TABLE tablename
• Oracle：ANALYZE TABLE tablename COMPUTE STATISTICS

---

💎 总结回顾

查询优化流程

flowchart LR
A[SQL查询] --> B[逻辑优化]
B --> C[物理优化]
C --> D[执行计划]

核心技术

• 逻辑优化：关系代数操作次序优化
• 物理优化：代价估算 + 算法选择
• DBMS核心：自动优化机制 + 执行引擎

图示说明：优化过程通过改变操作顺序和算法选择，显著减少中间结果大小和I/O开销，最终提升查询性能。