以下内容为参考课件和《数据库系统概论》（第5版，王珊等著）的个人整理，若有错误欢迎指出
第九章 查询优化
文章目录
一、概述
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、查询树
关系代数表达式的树形表示：叶节点是输入的关系（表），内部节点是关系操作，自底向上执行。
先按照表达式画出树，再根据上述规则优化。
例子：
优化后（尽量早做选择，连接代替笛卡尔积，先连接产生较小的结果，用投影去除没用的属性）：