以下内容为参考课件和《数据库系统概论》（第5版，王珊等著）的个人整理，若有错误欢迎指出

第九章 查询优化

文章目录

• • 第九章 查询优化
  • • 一、概述
    • • 1、目的
      • 2、查询处理基本步骤
      • 3、操作实现方法
      • 4、查询代价的度量
    • 二、代数优化
    • • 1、关系代数等价
      • 2、常用的等价变换规则（关系代数）
      • 3、一般准则（启发式优化）
      • 4、查询树

一、概述

1、目的

得到更好的查询性能。一般分为代数优化（基于关系代数的等价变换）和物理优化（存取路径等底层操作）。

2、查询处理基本步骤

语法分析和翻译，转化为内部表示形式（一般为查询树）；然后进行优化；最后执行 执行计划。

3、操作实现方法

• 选取操作的实现

  • 全表扫描方法，对于每一个元组都测试是否满足选择条件。

  • 折半扫描方法，如果文件按照某一属性排序，就可以折半扫描

  • 索引扫描方法，对属性建立索引表，根据索引项的指示去访问。

• 连接操作的实现

  • 嵌套循环方法，即外层循环是一个表，内层循环是另一个表
  • 排序-合并方法，按照连接的属性排序，然后操作。一般用于等值连接，即以一个表为基准，在另一个表查找，找到第一个比基准大的，那就说明没有或者在此之前找到了，那么基准表就可以下一个元组了，然后另一个表继续往后找。
  • 索引连接方法，对一个表的连接属性建立索引，在另一个表中按照索引进行查找。
  • Hash Join方法，对元素较少的表建立Hash表，然后通过hash值查找。一般也是用于等值连接。

4、查询代价的度量

总代价 = IO代价（IO块数或次数）+CPU代价+通信开销（client、server的通信）+ 内存代价

• 不会直接用时间算（不同设备有差异）

• 主存中缓冲区的大小是一个重要影响因素

• 减小中间结果的大小十分重要

二、代数优化

1、关系代数等价

结果有相同的属性集和元组集

2、常用的等价变换规则（关系代数）

• 连接、笛卡尔积的交换律、结合律

• 投影的串接定律： Π A 1 . . . . A n ( Π B 1 . . . B m ( E ) ) = Π A 1 . . . A n ( E ) \Pi_{A_1....A_n}(\Pi_{B_1...B_m}(E))=\Pi_{A_1...A_n}(E) ΠA1​....An​​(ΠB1​...Bm​​(E))=ΠA1​...An​​(E)

• 选择的串接律（合并条件）： σ F 1 ( σ F 2 ( E ) ) = σ F 1 ∧ F 2 ( E ) \sigma_{F_1}(\sigma_{F_2}(E))=\sigma_{F_1\wedge F_2}(E) σF1​​(σF2​​(E))=σF1​∧F2​​(E)

• 选择与其他操作的交换律：

  假设相同属性同名

  • σ F ( E 1 × E 2 ) = σ F ( E 1 ) × σ F ( E 2 ) \sigma_F(E_1\times E_2) = \sigma_F(E_1)\times\sigma_F(E_2) σF​(E1​×E2​)=σF​(E1​)×σF​(E2​)，这个是否含有相应属性而选择
  • σ F ( E 1 ∪ E 2 ) = σ F ( E 1 ) ∪ σ F ( E 2 ) \sigma_F(E_1\cup E_2) = \sigma_F(E_1)\cup \sigma_F(E_2) σF​(E1​∪E2​)=σF​(E1​)∪σF​(E2​)
  • σ F ( E 1 − E 2 ) = σ F ( E 1 ) − σ F ( E 2 ) \sigma_F(E_1 - E_2) = \sigma_F(E_1)- \sigma_F(E_2) σF​(E1​−E2​)=σF​(E1​)−σF​(E2​)
  • σ F ( E 1 ⋈ E 2 ) = σ F ( E 1 ) ⋈ σ F ( E 2 ) \sigma_F(E_1\Join E_2) = \sigma_F(E_1)\Join\sigma_F(E_2) σF​(E1​⋈E2​)=σF​(E1​)⋈σF​(E2​)， F F F 只涉及公共属性

• 投影和其他操作的交换律

  • Π A 1 . . . A n , B 1 . . . B m ( E 1 × E 2 ) = Π A 1 . . . A n ( E 1 ) × Π B 1 . . . B m ( E 2 ) \Pi_{A_1...A_n,B_1...B_m}(E_1\times E_2) = \Pi_{A_1...A_n}(E_1)\times \Pi_{B_1...B_m}(E_2) ΠA1​...An​,B1​...Bm​​(E1​×E2​)=ΠA1​...An​​(E1​)×ΠB1​...Bm​​(E2​)
  • Π A 1 . . . A n ( E 1 ∪ E 2 ) = Π A 1 . . . A n ( E 1 ) ∪ Π A 1 . . . A n ( E 2 ) \Pi_{A_1...A_n}(E_1\cup E_2) = \Pi_{A_1...A_n}(E_1)\cup \Pi_{A_1...A_n}(E_2) ΠA1​...An​​(E1​∪E2​)=ΠA1​...An​​(E1​)∪ΠA1​...An​​(E2​)​，假设相同属性 名字相同
  • 对于与选择的复合，若先投影，那么投影结果要包含所要的和选择涉及的属性

3、一般准则（启发式优化）

• 选择运算尽可能先做——减小中间关系

• 连接前适当预处理（排序、索引）

• 投影和选择一起做——避免重复扫描

• 投影还能与一些双目运算结合起来算——减少扫描次数

• 一些选择（等值）+笛卡尔积操作 转为 连接操作

• 公共子表达式只算一次，多次引用

• 连接操作尽量生成小的结果，可以借助交换律、或先投影去掉没用的属性

4、查询树

关系代数表达式的树形表示：叶节点是输入的关系（表），内部节点是关系操作，自底向上执行。

先按照表达式画出树，再根据上述规则优化。

例子：


优化后（尽量早做选择，连接代替笛卡尔积，先连接产生较小的结果，用投影去除没用的属性）：