第3篇 系统篇
第9章 关系查询处理和查询优化
复习笔记
一、概述
本章介绍关系数据库的查询处理（query processing）和查询优化（query optimization）技术。查询优化一般可分为代数优化（也称为逻辑优化）和物理优化（也称为非代数优化）。代数优化是指关系代数表达式的优化，物理优化则是指通过存取路径和底层操作算法的选择进行的优化。
二、关系数据库系统的查询处理
查询处理是关系数据库管理系统执行查询语句的过程，其任务是把用户提交给关系数据库管理系统的查询语句转换为高效的查询执行计划。
01查询处理步骤
关系数据库管理系统查询处理可以分为4个阶段：查询分析、查询检查、查询优化和查询执行，如图 9-1所示。
图9-1 查询处理步骤
（1）查询分析
首先对查询语句进行扫描、词法分析和语法分析。从查询语句中识别出语言符号，如 SQL关键字、属性名和关系名等，进行语法检查和语法分析，即判断查询语句是否符合SQL语法规则。
（2）查询检查
根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效。如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作。还要根据数据字典中的用户权限和完整性约束。对用户的存取权限进行检查时，如果该用户没有相应的访问权限或违反了完整性约束，就拒绝执行该查询。检查通过后便把 SOL查询语句转换成内部表示，即等价的关系代数表达式。这个过程中要把数据库对象的外部名称转换为内部表示。关系数据库管理系统一般都用查询树（query tree），也称为语法分析树（syntax tree）来表示扩展的关系代数表达式。
（3）查询优化
查询优化就是选择一个高效执行的查询处理策略。查询优化有多种方法。按照优化的层次一般可将查询优化分为代数优化和物理优化。
①代数优化
代数优化是指关系代数表达式的优化，即按照一定的规则，通过对关系代数表达式进行等价变换，改变代数表达式中操作的次序和组合，使查询执行更高效。
②物理优化
物理优化则是指存取路径和底层操作算法的选择。
（4）查询执行
依据优化器得到的执行策略生成查询执行计划，由代码生成器（code generator）生成执行这个查询计划的代码。
02实现查询操作的算法
（1）选择操作的实现
①简单的全表扫描方法
对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出。对于小表，这种方法简单有效。对于大表顺序扫描十分费时，效率很低。
②索引（或散列）扫描方法
如果选择条件中的属性上有索引（例如B+树索引或 Hash 索引），可以用索引扫描方法。通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。
（2）连接操作的实现
连接操作是查询处理中最耗时的操作之一。等值连接（或自然连接）最常用的实现算法有：
①嵌套循环方法（nested loop）
这是最简单可行的算法。
②排序-合并方法
适合连接的诸表已经排好序的情况。
③索引连接（index join）方法
按索引进行连接。
④Hash Join 方法
把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个 hash文件中。
三、关系数据库系统的查询优化
关系系统的查询优化既是RDBMS实现的关键技术又是关系系统的优点所在。
01查询优化的优点
（1）它减轻了用户选择存取路径的负担。用户不必考虑如何最好地表达查询以获得较好的效率。
（2）系统可以比用户程序的“优化”做得更好。
02查询优化的特点
（1）优化器可以从数据字典中获取许多统计信息，根据这些信息做出正确的估算，选择高效的执行计划，而用户程序则难以获得这些信息。
（2）如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
（3）优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。
（4）优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。
03目标
查询优化的总目标是：选择有效的策略，求得给定关系表达式的值，使得查询代价最小。
四、代数优化
01关系代数表达式等价变换规则
（1）连接、笛卡儿积的交换律
设E1和E2是关系代数表达式，F是连接运算的条件，则有
（2）连接、笛卡儿积的结合律
设E1、E2、E3是关系代数表达式，F1和F2是连接运算的条件，则有
（3）投影的串接定律
这里，E是关系代数表达式，Ai（i=1，2，…，n），Bi（i=1，2，…，m）是属性名，且{A1，A2，…，An}构成{B1，B2，…，Bm}的子集。
（4）选择的串接定律
这里，E是关系代数表达式，F1、F2是选择条件。选择的串接律说明选择条件可以合并，这样一次就可检查全部条件。
（5）选择与投影操作的交换律
这里，选择条件F只涉及属性A1，A2，…，An。
若F中有不属于A1，A2，…，An的属性B1，B2，…，Bm，则有更一般的规则：
（6）选择与笛卡儿积的交换律
如果F中涉及的属性都是E1中的属性，则
如果F=F1˄F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则可推出：
若F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则仍有
它使部分选择在笛卡儿积前先做。
（7）选择与并的分配律
设E=E1∪E2，E1、E2有相同的属性名，则
（8）选择与差运算的分配律
若E1与E2有相同的属性名，则
（9）选择对自然连接的分配律
F只涉及E1与E2的公共属性。
（10）投影与笛卡儿积的分配律
设E1与E2是两个关系表达式，A1，A2，…，An是E1的属性，B1，B2，…，Bm是E2的属性，则
（11）投影与并的分配律
设E1与E2有相同的属性名，则
02查询树的启发式优化
典型的启发式规则有：
（1）选择运算应尽可能先做。
（2）把投影运算和选择运算同时进行。
（3）把投影同其前或其后的双目运算结合起来。
（4）把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。
（5）找出公共子表达式。
五、物理优化
物理优化是要选择高效合理的操作算法或存取路径，求得优化的查询计划，达到查询优化的目标。选择的方法可以是：基于规则的启发式优化；基于代价估算的优化；两者结合的优化方法。
01基于启发式规则的存取路径选择优化
（1）选择操作的启发式规则
①对于小关系，使用全表顺序扫描，即使选择列上有索引。
②对于大关系：
a.对于选择条件是主码=值的查询，查询结果最多是一个元组，可以选择主码索引；
b.对于选择条件是非主属性=值的查询，并且选择列上有索引，则要估算查询结果的元组数目，比例较小（<10%）可以使用索引扫描方法，否则使用全表顺序扫描；
c.对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，同样要估算查询结果的元组数目，比例较小（<10%）可以使用索引扫描方法，否则使用全表顺序扫描；
d.对于用 AND 连接的合取选择条件，如果涉及这些属性的组合索引，则优先采用组合索引扫描方法；如某些属性上有一般的索引，使用索引扫描方法，否则使用全表顺序扫描；
e.对于用OR连接的析取选择条件，一般使用全表顺序扫描。
（2）连接操作的启发式规则
①如果两个表都已经按照连接属性排序，则选用排序-合并方法。
②如果一个表在连接属性上有索引，则可以选用索引连接方法。
③如果上面两个规则都不适用，其中一个表较小，则可以选用Hash Join方法。
④最后可以选用嵌套循环方法，并选择其中较小的表，即占用的块数较少的表作为外表。
02基于代价估算的优化
在编译执行的系统中，一次编译优化，多次执行，查询优化和查询执行是分开的，适合采用精细复杂的基于代价的优化方法。
（1）统计信息
基于代价的优化方法要计算各种操作算法的执行代价，它与数据库的状态密切相关。为此，在数据字典中存储了优化器需要的统计信息（database statistics），主要包括如下几个方面：
①对每个基本表，该表的元组总数（N）、元组长度（l）、占用的块数（B）、占用的溢出块数（BO）；
②对基表的每个列，该列不同值的个数、选择率、该列最大值、最小值，该列上是否已经建立了索引，是哪种索引（B+树索引、Hash索引、聚集索引）；
③对索引，例如B+树索引，该索引的层数（L）、不同索引值的个数、索引的选择基数、索引的叶结点数（Y）。
（2）代价估算
①全表扫描算法的代价估算公式。如果基本表大小为B 块，全表扫描算法的代价cost=B；如果选择条件是码=值，那么平均搜索代价cost=B/2。
②索引扫描算法的代价估算公式
a.如果选择条件是码=值，则采用该表的主索引，若为B+树，层数为L，所以cost=L+1；
b.如果选择条件涉及非码属性，若为 B+树索引，选择条件是相等比较，S 是索引的选择基数，所以（最坏的情况）cost=L+S；
c.如果比较条件是>，>=，<，<=操作，假设有一半的元组满足条件，那么就要存取一半的叶结点，并通过索引访问一半的表存储块。所以cost=L+Y/2+B/2。如果可以获得更准确的选择基数，可以进一步修正Y/2与B/2。
③嵌套循环连接算法的代价估算公式
把连接结果写回磁盘，则cost=Br+Br Bs/（K-1）+（Frs*r=Nr*s）/Mrs。
④排序一合并连接算法的代价估算公式
a.如果连接表已经按照连接属性排好序，则cost=Br十Bs+（Frs*rs*s）/Mrs；
b.如果必须对文件排序，那么还需要在代价函数中加上排序的代价。对于包含B个块的文件排序的代价大约是（2*B）+（2*B*log2B）。
六、查询计划的执行
查询优化完成后，关系数据库管理系统为用户查询生成了一个查询计划。该查询计划的执行可以分为自顶向下和自底向上两种执行方法。
01自顶向下
在自顶向下的执行方式中，系统反复向查询计划顶端的操作符发出需要查询结果元组的请求，操作符收到请求后，就试图计算下一个（几个）元组并返回这些元组。
02自底向上
在自底向上的执行方式中，查询计划从叶结点开始执行，叶结点操作符不断地产生元组并将它们放入其输出缓冲区中，直到缓冲区填满为止，这时它必须等待其父操作符将元组从该缓冲区中取走才能继续执行。
