数据库复习之——查询优化技术_数据库语法树查询优化

一、查询优化的基本概念与思路

1. 从三个层面进行数据库的查询优化：

1. 语义优化：利用模型的语义及完整性约束规则
2. 语法优化—逻辑层优化：利用语法结构，优化操作执行顺序
3. 执行优化—物理层优化：存取路径和执行算法的选择与执行次序优化

2. 查询优化的整体思路

（1）语义优化（内容等价性）：

​ 在用户\程序员的角度，在写SQL查询语句的时候：去掉无关的表和属性，并将其改写成等价的效果更好的语句

（2）语法优化—逻辑层优化（语法等价性）：

​ DBMS能将SQL语句转换成关系代数表达式，从关系代数表达式的层面对语法树进行优化；其基本思想是：改变关系代数的操作次 序，尽可能早地做选择、投影运算，将其改造成等价地效果更好地语句。

（3）执行优化—物理层优化：存取路径和执行算法的选择与执行次序优化

​ 经过逻辑层优化之后，将为每个关系代数操作选择优化的执行层例行程序，并形成物理查询计划。然后执行引擎依照查询计划调用相 应的例行程序进行处理，并返回结果。

【查询优化的语言描述】：

• 程序员在写查询SQL语句的时候，应该避免使用无关的表和字段；
• SQL语句转换成关系代数，要尽量先进行选择操作和投影操作，以降低笛卡尔积的数据规模；
• 为每个关系代数操作选则优化的执行例行程序，并形成物理查询计划；之后执行引擎将按照计划调用相应的例行程序处理并返回结果。物理查询优化的具体流程是：
  • 获取数据的相关信息（需要定期统计）；
  • 在实现同一关系操作的不同例行程序库中选择相应的基本执行层例行程序；
  • 依据相关信息进行代价估算，并选择一个代价例行程序；
  • 形成查询计划：以基本的例行程序为基本，确定这些例行程序的执行顺序；

二、逻辑层查询优化技术

基本思想：尽可能早的进行选择和投影操作；

1. 逻辑查询优化的基本策略

（1）尽可能早做选择操作和投影操作：可以使中间结果变小，节省几个数量级地执行时间

（2）将选择与投影串接起来：一元运算序列可一起执行，只需要对整个关系扫描一遍

（3）将投影与其前或后的二元运算结合起来：在第一次用关系的时候，去掉一些无关属性，可避免多次扫描整个关系

（4）将某些选择与其前的笛卡尔积合并成一个连接：当RxS前有选择运算，且选择的条件是R和S关系间的属性比较运算时，可将其转化为连接运算以节省时间。

（5）执行连接运算之前可对关系做适当的预处理：文件排序、建立临时索引等，可以使两关系公共值高效连接。

（6）找出表达式中的公共子表达式：若公共子表达式的结果不大，则预先计算，以后可读入此结果。

2. 关系代数操作次序交换的等价性（关系代数交换定理）

a. 定义

假设E1、E2是两个关系操作表达式。若E1、E2表示相同的映射，即当E1、E2的同名变量带入相同关系后产生相同的结果（映射集合），则说E1、E2是等价的，记E1=E2

b. 等价性定理

（1）定理1：连接与连接、积与积的交换律

​ 假设$E_1、E_2$是关系代数表达式，$F$ 是 $E_1、E_2$ 中属性的附加限制条件，那么：

​ $E_1{\bowtie }_F{E}_2\equiv E2{\bowtie }_{F}E1$

​ $E_1\bowtie E_2\equiv E2\bowtie E1$

​ $E_1\times E_2\equiv E2\times E1$

​ 并交运算也有这种交换律；

​ 通常而言，我们选择结果集合较小的表达式放到内存缓冲区中。

（2）定理2：连接与连接、积与积的结合律

​ 假设$E_1、E_2、E_3$是关系代数表达式，$F_1、F_2$ 是条件，那么：

​ $(E_1{\bowtie }_{F_1}{E}_2){\bowtie }_{F_2}{E}_3\equiv E_1{\bowtie }_{F_1}(E_2{\bowtie }_{F_2}{E}_3)$

​ $(E_1\bowtie E_2)\bowtie E_3\equiv E_1\bowtie (E_2\bowtie E_3)$

​ $(E_1\times E_2)\times E_3\equiv E_1\times (E_2\times E_3)$

​ 并交运算也有这种结合律；

​ $SELECT\ast FROMWHERE...$ 通常，我们选择结果集小的表达式先运算。

（3）定理3：投影串接律

​ 假设属性集 { A 1 、 A 2 、 A 3 } ⊆ { B 1 , B 2 , B 3 } , E \{A_1、A_2、A_3\} \subseteq \{B_1,B_2,B_3\} ,\quad E { A1​、A2​