数据库系统概论第五版（王珊）-系统篇（九）

查询处理是关系数据库管理系统执行查询语句的过程，其任务是把用户提交给关系数据库管理系统的查询语句转换为高效的查询执行计划。

9.1.1 查询处理步骤

关系数据库管理系统查询处理可以分为4个阶段：查询分析、查询检查、查询优化和查询执行。

1. 查询分析
   对查询语句进行扫描、词法分析和语法分析。
2. 查询检查
   对合法的查询语句进行语义检查，即根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效。
   如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作。
   还要根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。
3. 查询优化
   可以分为代数优化和物理优化。
   代数优化是指关系代数表达式的优化，即按照一定的规则， 通过对关系代数表达式进行等价变换，改变代数表达式中操作的次序和组合，使查询执行更高效:
   物理优化则是指存取路径和底层操作算法的选择。选择的依据可以是基于规则(rulebased)的，也可以是基于代价(cost based)的，还可以是基于语义(semantic basised)的.
4. 查询执行
   依据优化器得到的执行策略生成查询执行计划，由代码生成器(code generator) 生成执行这个查询计划的代码，然后加以执行，回送查询结果。

9.1.2 实现查询操作的算法示例

1. 选择操作的实现
   选择操作只涉及一个关系，一般采用全表扫描或者**基于索引扫描（B+树或者hash索引）**的算法。
2. 连接操作的实现
   这里介绍等值连接最常见用的几种算法。
   （1）嵌套循环连接
   （2）排序-合并算法：尤其适合参与连接的诸表已经排序好的情况。
   （3）索引连接算法
   （4）hash join算法：处理等值连接。它把连接属性作为hash码，用同一个hash函数把Student表和SC表中的元组散列到hash表中。

1. 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较高的效率，而且在于系统可以比用户程序的“优化”做得更好。这是因为:
   （1）优化器可以从数据字典中获取许多统计信息，例如每个关系表中的元组数、关系中每个属性值的分布情况、哪些属性上已经建立了索引等。优化器可以根据这些信息做出正确的估算，选择高效的执行计划，而用户程序则难以获得这些信息。
   （2）如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中则必须重写程序，而重写程序在实际应用中往往是不太可能的。
   （3）优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。
   （4）优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。
2. 目前关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。在集中式数据库中，查询执行开销主要包括磁盘存取块数(IO代价)、处理机时间(CPU代价)以及查询的内存开销。在分布式数据库中还要加上通
   信代价，即
   总代价=I/O代价+CPU代价+内存代价+通信代价
   由于磁盘I/O操作涉及机械动作，需要的时间与内存操作相比要高几个数量级，因此，在计算查询代价时一般用查询处理读写的块数作为衡量单位。
   查询优化的总目标是选择有效的策略，求得给定关系表达式的值，使得查询代价较小。因为查询优化的搜索空间有时非常大，实际系统选择的策略不一定是最优的，而是较优的。

9.3.1 关系代数表达式等价交换原则

P281-P282
代数优化策略是通过对关系代数表达式的等价变换来提高查询效率。
关系代数表达式的等价是指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。两个关系表达式E1和E2是等价的，可记为E=E2。
常见的等价交换规则：

1. 连接、笛卡尔积的交换律
2. 连接、笛卡尔积的结合律
3. 投影的串接的定律
4. 选择的串接定律
5. 选择与投影操作的交换律
6. 投影与笛卡尔积的交换律
7. 选择与并的分配律
8. 选择与差运算的分配律
9. 选择对自然连接的分配律
   10.投影与笛卡尔积的分配律
10. 投影与并的分配律

9.3.2 查询树的启发式优化

本节讨论应用启发式规则的代数优化。典型的启发式规则有：

1. 选择运算应尽可能先做。
2. 投影运算与选择运算同时进行。
3. 投影同其前或后的双目运算结合起来。
4. 把某些选择同在它前面要执行的笛卡尔积结合起来称为一个连接运算。
5. 找出公共子表达式。

代数优化不涉及底层的存取路径，物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划，达到查询优化的且标。
选择的方法可以是:
（1）基于规则的启发式优化。
启发式规则是指那些在大多数情况下都适用，但不是在每种情况下都是最好的规则。
（2）基于代价估算的优化。
使用优化器估算不同执行策略的代价，并选出具有最小代价的执行计划。
（3）两者结合的优化方法。
查询优化器通常会把这两种技术结合在一起使用。

9.4.1 基于启发式规则的存取路径选择优化

1. 选择操作的启发式规则
   对于小关系，使用全表顺序扫描，即使选择列上有索引。
   对于大关系，启发式规则有：
   （1）对于选择条件是“主码=值”的查询，查询结果最多是-一个元组，可以选择主码索引。一般的关系数据库管理系统会自动建立主码索引。
   （2）对于选择条件是“非主属性=值”的查询，并且选择列上有索引，则要估算查询结果的元组数目，如果比例较小(<10%)可以使用索引扫描方法，否则还是使用全表顺序扫描。
   （3）对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，同样要估算查询结果的元组数目，如果选择率<10%可以使用索引扫描方法，否则还是使用全表顺序扫描。
   （4）对于用AND连接的合取选择条件，如果有涉及这些属性的组合索引，则优先采用组合索引扫描方法;如果某些属性上有一般索引，则可以用[例9.1-C4]中介绍的索引扫描方法，否则使用全表顺序扫描。
2. 连接操作的启发式规则
   （1）如果2个表都已经按照连接属性排序，则选用排序合并算法。
   （2）如果一个表在连接属性上有索引，则可以选用索引连接算法。
   （3）如果上面2个规则都不适用，其中一个表较小，则可以选用hash join算法。
   （4）最后可以选用嵌套循环算法，并选择其中较小的表，确切地讲是占用的块数(B)较少的表，作为外表(外循环的表)。

9.4.2 基于代价估算的优化

启发式规则优化是定性的选择，比较粗糙，但是实现简单而且优化本身的代价较小，适合解释执行的系统。因为解释执行的系统，其优化开销包含在查询总开销之中。
统计信息
基于代价的优化方法要计算各种操作算法的执行代价，它与数据库的状态密切相关。为此在数据字典中存储了优化器需要的统计信息(database statistics)， 主要包括如下几个方面:
（1）对每个基本表，该表的元组总数(N)、 元组长度(I)、 占用的块数(B)、占用的溢出块数( BO);
（2）对基本表的每个列，该列不同值的个数(m)、该列最大值、最小值，该列上是否已经建立了索引，是哪种索引(B+树索引、hash 索引、聚集索引)。
（3）对索引，例如B+树索引，该索引的层数(L)、不同索引值的个数、索引的选择基
数S (有S个元组具有某个索引值)、索引的叶结点数(Y);

查询计划的执行可以分为自顶向下和自底向上两种执行方法。

在自顶向下的执行方式中，系统反复向查询计划顶端的操作符发出需要查询结果元组的请求，操作符收到请求后，就试图计算下一个(几个)元组并返回这些元组。在计算时，如果操作符的输入缓冲区为空，它就会向其孩子操作符发送需求元组的请…这种需求元组的请求会一直传 到叶子结点，启动叶子操作符运行，并返回其父操作符一个(几个)元组，父操作符再计算自己的输出返回给上层操作符，直至顶端操作符。重复这一过程，直到处理完整个关系。

在自底向上的执行方式中，查询计划从叶结点开始执行，叶结点操作符不断地产生元组并将它们放入其输出缓冲区中，直到缓冲区填满为止，这时它必须等待其父操作符将元组从该缓冲区中取走才能继续执行。然后其父结点操作符开始执行，利用下层的输入元组来产生它自己的输出元组，直到其输出缓冲区满为止。这个过程不断重复，直到产生所有的输出元组。

显然，自顶向下的执行方式是一种被动的、需求驱动的执行方式。而自底向上的执行方式是一-种主动的执行方式。