7、查询优化.md

### 查询优化

#### 基本思路

DBMS 会从三个层面进行优化：

* 语义优化：利用模型的语义及完整性规则，优化查询。
* 语法优化---逻辑层优化：利用语法结构，优化操作执行顺序；
* 执行优化---物理层优化：存取路径和执行算法的选择与执行次序优化
  * 所谓的建立索引，就是用户给 DBMS 在物理层面多提供了存取路径和算法的选择



语义优化---内容等价

* 去掉无关的表
* 去掉无关的属性
* 改写成等价的效果更好的语句
* ....



语法优化(逻辑层优化)---语法等价性

* 尽可能早做选择运算
* 尽可能早做投影运算
* 改写成等价的效果更好的语句
* .....



执行优化(物理层优化)

* 选取每个关系代数相应的执行层例行程序

* 依据相关信息进行代价估算,并选择代价最少的例行程序及确定相应的参数

* 形成查询计划：以基本的例行程序为基本，并确定这些例行程序的执行顺序





#### 逻辑查询优化

* 逻辑查询优化使得关系性数据库成为可能，不然就有组合爆炸问题。



策略

* (1)、尽可能地早做选择和投影：可使中间结果变小，节省几个数量级的执行时间。

* (2)、把选择与投影串接起来：一元运算序列可一起执行，只需对整个关系扫描一遍。

* (3)、把投影与其前或后的二元运算结合起来：在第一次用关系时去掉一些无关属性，可以避免多次扫描整个关系。

* (4)、把某些选择与其前的笛卡尔积合并成一个连接：当R×S前有选择运算且其中有条件是R、S属性间比较的运算时，可将其转化为连接运算可节省时间。

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

* (6)、找出表达式里的公共子表达式：若公共子表达式结果不大，则预先计算，以后可读入此结果，节时多，尤当视图情况下有用。


	<img src="https://img-blog.csdnimg.cn/202011271355491.png?" width="30%" height="50%" />

交换的等价性

* [定义] 设E1, E2是两个关系操作表达式。若E1, E2表示相同的映射，即当E1, E2的同名变量代入相同关系后产生相同的结果(映像集合)，则说E1, E2是等价的，记为E1E2。
* 注：关系可被看成 (1)k元组集合(属性有先后次序)。(2)一组属性（名）到值的映像集合(元组中的属性没有先后次序)。只有把关系看成是从一组属性名到值的映像的集合，等价性才成立。



定理

1. 连接，笛卡尔积的交换律
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127135628192.png)


2. 连接，笛卡尔积的结合
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127135642777.png)

3. 投影的串接定律
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127135655331.png)


4. 选择的串接定律
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140109167.png)


5. 选择与投影的交换
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140120563.png)


6. 选择与笛卡尔积的交换
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140134766.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)

7. 选择与并的交换
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140148138.png)

8. 选择与差的交换
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140202632.png)

9. 投影与笛卡尔积的交换**
   ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140214329.png)

10. .投影与并的交换
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140226556.png)




优化步骤

* 1、构造查询树

  * 把用高级语言定义的查询转换为关系代数表达式

  * 注：查询树是一种表示关系代数表达式的树形结构。在一个查询树中，叶子结点表示关系，父结点表示关系代数操作。查询树以自底向上的方式执行：当一个内结点的操作分量可用时，这个内结点所表示的操作启动执行，执行结束后用结果关系代替这个内结点。

* 2、利用等价转换规则反复地对查询表达式进行尝试性转换，将原始的语法树转換成“优化”的形式
  * 对每一个选择，利用等价变换规则4~9尽可能把它移到树的叶端。目的是使选择操作尽早执行
  * 对每一个投影利用等价变换规则3,9等的一般形式尽可能把它移向树的叶端。目的是使投影操作尽早执行
  * 对每个叶节点加必要的投影操作，以消除对查询无用的属性。
  * 如果笛卡尔乘积后还须按连接条件进行选择操作,可将两者组合成连接操作
  * 总结：选择下沉，投影随后


应用举例：从数据库中找出选修了课程名为“IS”的学生姓名

```sql
Select Cname
From Student, Course, SC
WHERE Student.Sno = SC.Sno AND SC.Cno = Course.Cno AND Student.Sdept =’IS’;
```

* 1、构造查询树：查询语句转关系代数表达式为：$∏_{Cname}$($σ_{Student.Sdept=’IS’}$(Student ⋈ Course ⋈ SC))
  	![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140250951.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)

* 2、利用等价代换原则进行优化
  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127140304273.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)


执行步骤分组方式

* 每个二元运算结点(积、并、差、连接等)和其所有一元运算直接祖先结点放在一组；对于其后代结点，若后代结点是一串一元运算且以树叶为终点，则将这些一元运算结点放在该组中；若该二元运算结点是笛卡儿积，且其后代结点不能和它组合成等连接，则不能将后代结点归入该组。
* 产生一个程序：它以每组结点为一步，但后代组先执行。 



#### 物理查询优化

为什么要物理查询优化？一个例子：$σ_{Cname=“数据结构”}$(Course) 的执行方案方案

* 1：表空间扫描方法：直接对Course表进行扫描，从第一条检索到最后一条，将满足条件的记录找出方案
* 2：利用Course上的Cname排序索引的方法：利用排序索引可以进行诸如二分查找等快速检索，找到相应的索引项，依据指针将满足条件的记录找出
* 当条件更复杂时，可选择的方案还会更多



物理查询运算符

* 获取关系元组的操作
  * TableScan(R） ---表空间扫描算法
  * SortTableScan(R）---表空间扫描并排序算法
  * IndexScan(R）---索引扫描算法
  * SortIndexScan(R）---索引扫描并排序算法
* 操作实现算法
  * 关系操作的各种实现算法：$\delta$(R）, $\gamma$(R） , $\tau$(R），$\sigma_F$(R），$\prod_F$(R）
  * 集合上的操作：$\bigcup_S$, $\bigcap_S$，$-_S$
  * 包上的操作：$\bigcup_B$, $\bigcap_B$，$-_B$
  * 积，连接：PRODUCT， JOIN
* 基于索引算法、基于散列算法、基于排序算法；一趟算法、两趟算法
* 迭代器构造--流水化、物化； 





算法选择与次序优化

* DBMS如何衡量物理查询计划的优劣

  * 衡量I/O访问次数
  * 衡量CPU的占用时间
  * 内存使用代价(与缓冲区数目与大小的匹配)
  * 中间结果存储代价
  * 计算量(如搜索记录、合并记录、排序记录、字段值的计算等)
  * 网络通信量
  * 。。。

* 判断依据：统计信息---存放在数据字典或系统目录中

  * TR或T(R）：关系R的元组数目；

  * BR或B(R）：关系R的磁盘块数目； 

  * IR或I(R）：关系R的每个元组的字节数； 

  * fR或f(R）: R的块因子 , 即一块能够存储的R的元组数目

  * V(A, R):  R中属性A出现不同值的数目，即$\prod_A$(R） 的数目.

  * SC(A, R): R中属性A的选择基数，满足A上等值条件的平均记录数

  * b：每个磁盘块的字节数； 

    ...

* 如何收集这些信息

  * 当一个表装入内存和创建索引的时候，统计信息不是被自动收集的，必须由DBA使用特定的命令来完成信息统计，这些命令就是收集统计信息并把其存入系统目录中的实用程序
  * 随着表的更新操作，统计信息可能会过时，过时的统计信息会使DBMS确定方案时决策错误，因此要求DBA定期的对有频繁更新操作的Table进行统计
  * DBA要熟悉统计信息收集命令的使用，并定期执行



代价估算

* 概念

  * 已知表达式E中的各个关系的统计信息

    TR或T(R）：关系R的元组数目；

    BR或B(R）：关系R的磁盘块数目；

    IR或I(R）：关系R的每个元组的字节数；

    fR或f(R）: R的块因子 , 即一块能够存储的R的元组数目

    V(R, A):  R中属性A出现不同值的数目，即A(R）的数目.

    SC(R, A): R中属性A的选择基数，满足A上等值条件的平均记录数

  * 给定一个表达式E，如何计算E的元组数目T(E)以及属性A上不同值的数目V(E,A)。

  * 在E实际获得之前计算T(A),V(E,A)等是很难的事情；因而，要“估算”，代价估算

  

* 估算一个投影$\prod_L$(R）的大小

  * 简单:  T($\prod_L$(R）= T(R）
  * 投影运算只是对列有所取舍，并未对行有所变化，如并未消除重复
  * 投影运算并未减少行数，但可能有效地减少了存储结果关系的块数
  * 例如：磁盘块大小=1024 Byte R的元组长度=120 Byte, 8元组/块，T(R）=10,000, 则B(R） = 10000/8 = 1250;$\prod_L$(R）的元组长度=20 Byte, 50元组/块，则B($\prod_L$(R） = 10000/50 = 200;

  

* 估算选择运算 S = $σ_{A=c}$(R）的大小

  * T(S) 介于 0 to T(R）–V(R,A)+1之间---最多：A属性不同值的元组都只存在一个，剩余的都是A=c的元组
  * 估计: T(S) = T(R）/ V(R,A)  ---A属性不同值的元组数假设是平均分布的
  * 当不知道V(R,A)时，估计：T(S) = T(R）/10.

  


* 估算选择运算 S = $σ_{A<c}$(R）的大小


  * T(S) 介于 0 to T(R） 之间---最多：所有元组都满足条件

  * 估计: T(S) = T(R）/2---直觉，应有一半的元组，

  * 实际应用的估计： T(S) = T(R）/3 

    

* 估算选择运算 S = $σ_{A and B}$(R）的大小

  * 估计：T(S) = T(R） *$P_A$*$P_B$
  * 示例：估算 $σ_{A=10 AND B<20}$(R） = $σ_{B<20}$($σ_{A=10}$(R）))
    * A=10，得出T(S) = T(R）/V(R,A); 
    * B<20，得出T(S) = T(S)/3

  

* 估算选择运算 S = $σ_{C1 or C2}$(R）的大小

  * 估计：T(S)=n(1-(1-m1/n)(1-m2/n))

    * R有n个元组，其中有m1个满足C1, 有m2个满足C2
    * (1-m1/n)是不满足C1的那些元组，(1-m2/n)是不满足C2的那些元组
    * 两数之积是不在S中的那部分R的元组，1减去这个积就是属于S的那部分元组出现的概率。
  * 示例：估算选择运算 S = $σ_{A=10 or B<20}$(R）的大小

    * 估计：T(S)=n(1-(1-m1/n)(1-m2/n))
    * n = T(R）=10000,  V(R,A)=50
    * m1=T(R）/V(R,A)=10000/50=200;
    * m2=T(R）/3 = 10000/3 = 3333（有m1个满足C1, 有m2个满足C2，(1-m1/n)(1-m2/n)不满足这个条件的元组的概率1- (1-m1/n)(1-m2/n)满足这个条件的元组的概率 )
    * 简单估计：T(S)= T(R）/3 = 10000/3 = 3333
    * 复杂估计：T(S)=10000*(1-(1-200/10000)(1-3333/10000) = 3466

  

* 估算连接运算 S = R(X,Y) Natural Join S(Y,Z)的大小
  * 估计：T (S)=T(R）T(S)/max(V(R,Y),V(S,Y))

    * 假定V(R,Y)>=V(S,Y),R中元组r和S中元组有相同Y值的概率=1/V(R,Y)
    * 假定V(R,Y)<V(S,Y),R中元组r和S中元组有相同Y值的概率=1/V(S,Y)
    * 则，在Y上相等的概率 = 1/max(V(R,Y),V(S,Y))
  * 例：T(R）=10000, T(S)=50000, V(R, Y) = 500, V(S, Y)=1000  

    * 估计：T(S)=10000*50000/1000=500000。*
  * 例：T(R）=10000, T(S)=50000, V(R, Y) = 2000, V(S, Y)=1000  

    * 估计：T(S)=10000*50000/2000=250000。




* 总结
  * T(R）--R的元祖个数，V(R, A)—R中属性A上出现的不同值的数目
  * 判断满足单一条件元组出现的概率
    * 出现等于某一个值的概率 = 1 / V(R,A), 或者简单的概率 = 1/10 
    * 出现不等于某一个值的概率 = 1 – 1/V(R,A), 或者简单的概率 = 1-1/10
    * 出现小于或不等于某一个值的概率直觉上 = 1/2, 实际处理概率=1/3 
  * 判断满足多个条件的元组出现的概率
    * 如果是“与”，则将满足两个条件的概率相乘
    * 如果是“或”，则=(1-(1-m1/n)(1-m2/n)，不出现满足条件1的元组的概率(1-m1/n)，不出现满足条件2的元组的概率(1-m2/n)，二者相乘是不同时出现的概率，则1- (1-m1/n)(1-m2/n)即为去掉不同时出现的概率，即为或条件的概率。
  * 复杂的表达式可以依上原则进行估算，确定估算公式。