第九章 关系查询处理和查询优化
本章主要介绍关系数据库查询管理和查询优化，主要分为代数优化（又称逻辑优化）和物理优化（也称非代数优化）。
9.1 关系型数据库系统的查询处理
查询处理是关系型数据库管理系统执行查询语句的过程，主要负责将用户提交给数据库管理系统的查询语句转化为高效的执行计划
1.查询处理步骤
关系数据库管理系统查询处理分为四个步骤：查询分析、查询检查、查询优化和查询执行
查询分析
首先对查询语句进行扫描、词法分析和语法分析。
查询检查
对合法的查询语句进行语义检查。如果该用户没有相应访问权限或者违反了完整性约束，就拒绝执行该查询。但是这时候完整性检查时初步的、静态的检查。检查之后将SQL查询语句转化为内部标识，也就是等价的
关系代数表达式
。DBMS一般都用语法分析树来表示扩展的关系代数表达式，对于这部分，更详细的请参见《编译原理》
查询优化
查询优化是选择一个高效执行的查询处理策略。查询优化方法按照优化的层次一般可分为
代数优化
和
物理优化
查询执行
根据优化器得到的策略生成查询执行计划，由
代码生成器
生成执行这个查询计划的代码，然后执行并返回结果
2.实现查询操作的算法
1.选择操作的实现
（1）简单的全表扫描算法
全表扫描算法只需要很少内存就可以运行而且控制简单。但是对于规模大的表进行顺序扫描，效率将会非常低。
（2）索引扫描算法
如果选择条件中的属性上有索引（比如B+树索引或者hash索引），可以使用索引扫描的方法，首先通过索引找到满足条件的元组指针，再通过指针在基本表中查询元组。一般情况下，当选择率较低的时候，基于索引的选择算法要优于全表扫描算法，但是当选择率比较高的时候，或者要查找的元素均匀分布在表中的时候，使用索引的性能还不如全表扫描。
2.连接操作的实现
连接操作时查询处理中最常用也是最耗时的操作之一。比如：
SELECT * FROM Student,SC WHERE Student.Sno=Sc.Sno
（1）循环嵌套算法
最简单可行的算法，对于外层循环的每一个元组，检索内层循环中的每一个元组。类似于双层for循环，是最简单通用的连接算法，但是效率较低。
（2）排序-合并算法
这是等值链接常用的算法，适合参与连接的诸表已经排好序的情况。其具体步骤是：
-
如果参与连接的表没有排好序，则先对两表的连接属性N进行排序。使用最高效的排序算法快排，时间复杂度为O(nlog
2
n) - 取出A表的第一个行的连接属性N，依次扫描B表中属性N相同的元组，把他们联结起来
- 当扫描到和当前A表元组N属性不一样的B表元组的时候，返回A表扫描他的下一个元组，再扫描B表中具有相同的N属性的元组，连接
这样子两个表都只需要扫描一次，但是如果两表无序，那需要承受两次排序的额外开销。但是一般对于大型表，先排序后使用该算法执行连接，总的时间开销还是会减少的。
（3）索引连接算法
算法步骤如下：
- 在B表上已经建立了属性N的索引
- 对于A表上的每一元组，由该元组的属性N通过B的索引查找找到相应的B元组
- 把这些B元组和A中的元组连接起来
（4）hash join算法
该算法也是处理等值链接的算法，他把连接属性作为hash码，用同一个hash函数将A表和B表中的元组散列到hash表中。第一步为划分节点，创建hash表，对包含较少元组的表进行进一步处理，将他的元组按照hash函数分散到hash表的桶中；第二部，试探阶段，对另一个表进行一遍处理，把该表的元组也按照同一个hash函数进行散列，找到适合的hash桶，并且把两个表中处于同一个桶的元组联系起来
9.2 关系数据库系统的查询优化
查询优化概述
查询优化的有点在于用户不必考虑如何最好的表达查询已获得较高效率，系统会自动选择最高效率的方式，而且系统可以比用户程序优化做的更好
目前关系数据库管理系统通过某种代价模型计算出各种查询方式所需要的代价，在集中式数据库中，查询执行开销总代价组成如下：
总代价=IO代价+CPU代价+内存代价+通信代价
9.3 代数优化
代数优化的策略是用过对关系代数表达式的等价变换来提高查询效率。常用的等价变换规则有：
1.连接、笛卡尔积交换律
2.连接、笛卡尔积结合律
3.投影的串接定律
4.选择的串接定律
5.选择与笛卡尔积的交换律
6.选择与投影操作的交换律
7.选择与并的分配率
查询树的启发式优化
启发式优化指的是大多数情况下都适用，但是并不是每种情况下都是最好的规则。启发式规则优化是定性的选择，比较粗糙，但是实现简单而且优化本身的代价较小，适合解释执行的系统。
以下的规则对查询树有一定的优化作用：
- 选择运算应该尽可能先做
- 把对同一个关系的投影运算和选择运算同时进行
- 把投影同其前后的双目运算结合起来
- 把某些选择同他前面需要执行的笛卡尔积结合起来成为一个连接运算
- 找出公共子表达式
9.4 物理优化
物理优化要选择高效合理的操作算法或者存取路径，求得优化的查询计划，达成查询优化目标。选择的方法可以是：
- 基于规则的启发式优化
- 基于代价估算的优化
基于启发式规则的存取路径选择优化
1.选择操作的启发式规则
对于小关系，直接使用全表顺序扫描
对于大关系，启发式规则有：
- 对于选择条件是“主码=值”的查询，查询结果最多是一个原则，可以选择主码作为索引，一般数据库会主动建立主码索引
- 对于选择条件是“非主属性=值”的查询，并且选择列上有索引，则要估算查询结果的元组数目。如果比例小于10%则使用索引扫描方法，否则使用全表顺序扫描。
- 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，处理方法和2一样
- 对于用AND连接的合取选择条件，如果涉及到这些属性的组合索引，则优先采用组合索引扫描方法，如果有一般索引，则可以使用索引扫描，不然依然是全表顺序扫描。
- 对于OR连接的选择条件，一般使用全表顺序扫描。
2.连接操作的启发式规则
-
如果2个表都已经按照连接属性排序，则使用排序-合并算法
-
如果一个表在连接属性上有索引，则选用索引连接算法
-
如果上两个规则都不适用，而且其中一个表比较小，可以使用hash join算法。