第5章查询处理和查询优化查询是数据库管理系统中使用最频繁、最基本的操作,对系统性能有很大影响。因此，查询优化技术是关系数据库的关键技术。关系数据库的查询使用SQL语句实现,对于同一个SQL查询,通常可以有多个等价的关系代数表达式。由于存取路径的不同,每个关系代数表达式的查询代价和效率也是不同的。在关系数据库中,为了提高查询效率,需要对一个查询请求获得一个相对高效的查询计划。本章主要介绍关系数据库中查询处理的基本过程,查询优化的基本方法和技术。
5.1关系数据库系统的查询处理
查询处理是指从数据库中提取数据所涉及的处理过程,包括将用户提交的查询语句转变为数据库的查询计划,并且执行这个查询计划获得查询结果。
5.1.1查询处理过程
关系数据库的查询处理可以分为五个阶段: 查询分析、查询检查、建立查询的内部表示、查询优化和查询执行。图51给出了关系数据库中查询处理的一般过程。
1. 查询分析
查询处理过程的第一步是对用户提交的查询语句进行查询分析,包括词法分析、语法分析等,判断查询语句是否符合SQL的语法规则。
2. 查询检查
根据数据字典对符合语法的查询语句进行语义检查,检查语句中的数据库对象是否存在以及是否有效,包括属性名、关系名、关键字等。进一步,还要根据用户权限检查用户的存取权限,确定该用户是否具有访问相应数据的权限。进行完整性约束条件检查，确定查询语句是否违反完整性约束条件。〖1〗〖2〗数据库系统原理第5章查询处理和查询优化〖2〗〖2〗3. 建立查询的内部表示
SQL语言并不适合在数据库系统内部表示查询。为了便于机器处理,需要将查询转换为系统内部的表示形式。图51查询处理的过程4. 查询优化
通常一个查询会有多种可选的执行策略,不同的处理策略实现查询的效率是不一样的。查询优化就是选择高效的查询处理策略的过程。具体可以采用代数优化和物理优化等优化技术。代数优化是指利用关系代数表达式的等价变换规则进行优化。物理优化主要是结合索引、数据值的分布等数据存储特征,进一步改善查询效率,还可以通过代价估算确定若干查询计划,从中选择代价最低的查询计划。
5. 查询执行
最后,根据查询优化获得的执行策略,DBMS生成查询计划,包括如何访问数据库文件和如何存储中间结果等,以便从数据库文件中检索数据,输出查询结果。
查询语句的具体实现可以分为解释和编译两种实现方法。解释方式主要是指对于每一条查询语句,DBMS不保留可执行代码,每一次都重新解释执行查询语句,事务完成后返回查询结果。这种方法具有灵活、应变性强的特点,但是开销比较大、效率比较低,主要适用于不重复使用的偶然查询。编译方式是指在运行之前,先进行编译处理,生成可执行代码。需要运行时,直接执行可执行代码。当数据库中某些数据发生改变时,再重新进行编译。编译方法的主要优点是执行效率高、系统开销小。
5.1.2执行查询操作的基本算法
为了实现查询处理过程中的不同关系操作,关系数据库系统需要合适的算法实现这些关系操作。下面我们简单介绍实现选择、连接和投影等关系操作的典型算法,每种算法可能只适用于特定的存储结构或存储路径。5.5节将讨论如何估计这些算法的代价。
1. 选择操作的实现
SQL语言中,表示选择的条件非常丰富,针对不同的选择条件可以采用不同的实现算法和优化策略。下面,我们结合实例介绍几种典型的实现方法。
【例51】Select  from student where <条件表达式>,其中条件表达式可以有以下几种情况: C1: 无条件
C2: Sno= '200636'
C3: Sage>18
C4: Sdept='计算机' and Sno='200636'
C5: Sdept='计算机' and Sage>18
C6: Sage>18 or Sdept='计算机'（1）  顺序扫描方法
顺序扫描法是实现选择操作最简单的一种方法。该方法按照关系中元组的物理顺序扫描每一个元组,检查该元组是否满足选择条件,如果满足,则输出该元组。这种方法不需要特殊的存取路径,简单、有效,适用于任何关系,尤其适用于被选中的元组数占有较大比例或元组数较少的关系,例51中列出的所有选择条件都可以采用这种方法实现。但是,由于此方法是按照顺序扫描所有元组,所以对于元组数很多的大表,该方法的效率比较低。
（2）  二分查找法
如果选择条件涉及相等比较,并且物理文件是按照选择字段有序组织的,那么可以使用二分查找来定位符合选择条件的元组。通常,二分查找法比顺序扫描方法有效。例如,如果字段Sno是表student的排序属性,那么就可以用二分查找法实现C2中的选择条件。当然,如果选择是作用在非排序属性上,代价也会相应增加。
（3）  使用索引(或散列)的扫描方法
索引是使用最多的一种存取路径,可以快速、直接、有序地存取元组。这里主要介绍如何使用索引实现选择操作,有关索引文件的详细内容将在13.4节中介绍。在选择操作中,如果选择条件涉及的属性上有索引(例如B+树索引或散列索引),可以使用索引扫描方法。也就是说,通过索引查找满足条件的元组指针,然后通过该指针继续检索满足查询条件的元组。
下面,结合具体实例看一下索引的建立能够在一定程度上提高查询的效率。
以C2为例,检索Sno='200636'的元组,假设Sno上有索引(或Sno是散列键)。实现的具体方法是: 使用索引(或散列)得到Sno为'200636'元组的指针,然后通过元组指针在student表中检索符合查询条件的元组。
以C3为例,检索Sage>18的所有元组,假设Sage 上有B+树索引。实现的具体方法是: 使用B+树索引找到Sage=18的索引项,以此为入口点在B+树的顺序集上得到Sage>18的所有元组指针,然后通过这些元组指针到student表中检索到所有年龄大于18岁的学生。
（4） 复合选择
关系代数中的选择条件除了上面提到的最简单的等值或比较运算条件之外,还有很多由多个条件通过逻辑合取(AND)和析取(OR)连接而成的复合选择条件。
对于合取选择条件,可以使用以下方法实现: 
① 使用组合索引实现合取选择。如果合取条件中的相等条件包含两个或两个以上的属性,并且在组合字段上存在组合索引(或散列),那么可以直接使用这个组合索引。以C4为例,如果在(Sdept,Sno)上建立了组合索引,通过这个组合索引可以直接找到满足条件的元组。
② 使用单独索引实现合取选择。如果合取条件中某一个属性具有索引,则通过索引找到符合与该属性有关的查询条件的元组指针,通过元组指针得到符合该条件的元组,并对得到的元组检查其余的查询条件是否满足,最后将满足条件的元组作为结果输出。以C5为例,如果Sdept上有索引,可以先找到Sdept='计算机'的元组指针,通过这些元组指针到student表中检索,对得到的元组检查另一些选择条件(如Sage>18)是否满足,最后把满足条件的元组作为结果输出。
③ 使用多个索引实现合取选择。如果合取条件中涉及的属性都存在索引,那么可以分别检索满足单个条件的元组指针集,这些元组指针集的交集就提供了满足合取条件的指针。如果只有部分属性有索引,那么就需要进一步测试检索到的元组,以确定是否满足其余条件。以C5为例,假设Sdept和Sage上都有索引。分别使用索引(或散列)的扫描方法找到Sdept='计算机'的所有元组指针和Sage>18的所有元组指针,然后求这两组指针集的交集,再到student表中检索,就可以得到值为Sdept='计算机'且Sage>18的学生。
在合取选择条件的多个简单条件中进行选择时,通常要考虑每个条件的选择性(selectivity)。所谓选择性,就是满足条件的元组(记录)数占关系中元组(记录)总数的比例。它是介于0～1之间的值,选择性为0意味着没有满足条件的元组,选择性为1说明所有的元组都满足条件。虽然不能得到所有条件的准确的选择性,但是在DBMS数据字典中常常会记录选择性的估计值,可以在优化的时候使用。一般地,如果选择条件的选择性为s,满足该条件的元组数则可以估计为(s×元组数)。所估计的值越小,就越有必要首先使用这个条件来检索元组。
与合取选择条件相比,析取条件就是用逻辑连接符OR连接的查询条件,处理和优化的难度就大得多。以C6为例,Sage>18 or Sdept='计算机',如果Sdept上有索引,而Sage上没有索引,对于这种选择条件,满足析取条件的元组是满足单个条件的元组的并集,所以基本上无法进行优化。因此,只要任意一个条件没有索引,就只能使用顺序扫描方法。当条件中涉及的属性具有索引时,才能通过优化检索满足条件的元组,然后再通过合并操作消除重复元组。
2. 连接操作的实现
连接是从两个关系的笛卡儿积中选择满足连接条件的元组。连接操作是查询处理中最耗时的操作之一,操作本身开销大,并且可能产生很大的中间结果。假设R和S是要被连接的关系,A和B是两个关系中对应的属性或属性组,具有相同的域。下面,对主要的几个连接实现算法进行简单描述。
(1) 嵌套循环法
嵌套循环法是最简单、最直接的连接算法,与选择操作中的顺序扫描法类似,不需要特别的存取路径。算法的基本思想是: 对于关系R(外循环)中的每条元组t,检索关系S(内循环)中的每条元组s,检查这两条元组是否满足连接条件t\[A\]=s\[B\]。如果满足连接条件,则连接两条元组作为结果输出,直到外层循环表中的元组处理完为止。
在嵌套循环法中,选择哪一个关系用于外循环、哪一个关系用于内循环会给连接的性能带来比较大的差异,一般使用较少块的文件作为外循环文件连接代价较小。嵌套循环法适用于任何条件的连接。
(2) 索引嵌套循环法
在嵌套循环法中,如果两个连接属性中的一个属性上存在索引(或散列),可以使用索引扫描代替顺序扫描。例如,在关系S中的属性B上存在索引,则对于R中的每个元组,可以通过S的索引查找满足s\[B\]＝t\[A\]的所有元组,而不必扫描S中的所有元组,以减少扫描时间。在一般情况下,索引嵌套循环法和嵌套循环法相比,查询的代价可以降低很多。
(3) 排序合并法
这种方法可用于自然连接和等值连接。如果关系R和S分别按照属性A和属性B已经排序,在连接属性上具有相同值的元组按照排序连续存放。首先按照连接属性同时对关系R和S进行扫描,匹配A和B上有相同值的元组,把它们连接起来,作为结果输出。在这种情况下,完成连接操作只需要把两个关系各扫描一次,而且可以同步进行。如果关系R和S没有进行排序,可以首先使用排序方法对其进行排序。
(4) 散列连接法
与排序合并法类似,散列连接(Hash Join)法只需要对两个关系各扫描一次,用于实现自然连接和等值连接。在散列连接法中,以R的属性A和S的属性B作为散列键,在这两个属性上使用同一个hash函数,关系R和S中的元组会被划分成一些具有相同散列值的元组的集合。散列函数应当具有随机性和均匀性。关系的划分过程如图52所示。
图52关系的散列划分3. 投影操作的实现
投影操作选取关系的某些列,从垂直的方向减小关系的大小。如果投影操作П<属性列>(R)中的属性列包括了关系R的主键,那么这个操作可以直接执行,操作的结果将与R中的元组个数相同。但是,如果属性列不包含R的主键,还需要消除重复元组。为了消除重复元组,通常的做法是先对操作结果进行排序,这样排序后的元组会连续存放,很容易只留一个元组副本、去掉多余的副本。除了排序的方法外,也可以用散列法来消除重复元组,即把投影结果中的每条元组散列到相应的桶中,然后检查是否与该桶中已存在的元组重复,如果该元组是重复的,则不把这个元组插入桶中,否则把该元组插入桶中。
在介绍SQL语句时,我们知道SQL语句默认的情况下是不消除查询结果集的重复元组的,只有当查询中包含DISTINCT关键字时,才会从查询结果中消除重复元组,就是因为为了消除重复元组,DBMS需要进行额外的操作。
4. 集合运算的实现
传统的集合运算是二元的,包括并、差、交、笛卡儿积四种运算。并、差、交运算要求参加运算的两个关系必须是同类关系,运算的结果也是同类关系。这三种操作的实现方法基本相同,常用方法类似于前面介绍的排序合并法,只不过不是把两个关系排序后将具有相同属性值的元组连接起来,而是对具有相同属性值的元组进行并、差、交运算。具体地,首先对参加运算的两个关系分别按照主键属性排序,排序后只需同时对两个关系执行一次扫描就可以生成计算结果。
笛卡儿积的实现通常使用嵌套循环法,由于笛卡儿积的操作结果中包含了R和S中每个元组的组合,其结果集会比参与运算的关系大得多,所以笛卡儿积操作的代价非常高。
5.2关系数据库系统的查询优化
查询是数据库系统中最基本、最常用的数据操作,必须要考虑查询处理的开销和代价。在关系数据库中,对于相同的查询请求,存在着多种实现策略,系统在执行这些查询策略时所付出的开销是有很大差别的。为了提高查询效率,需要对查询请求获得一个相对高效的查询计划。在查询处理过程中,数据库系统必须能够从查询的多个执行策略中选择合适的执行策略来执行,这种选择的过程就是查询优化。
5.2.1查询优化技术
查询优化是影响关系数据库管理系统性能的关键因素。通常情况下,对于一个具体的查询请求,可以用多种形式的查询语句来表达,而不同的表达会使数据库的响应速度大不相同。因此,在实际应用中需要利用查询优化技术对不同形式的查询语句进行分析,选择高效、合理的查询语句,降低执行查询所需的系统开销,从而提高数据库系统的性能。
按照查询优化的层次的不同,查询优化技术主要分为以下几种:
1. 代数优化
代数优化是指关系代数表达式的优化,即按照一定的规则,改变代数表达式中操作的次序和组合,使查询执行更高效。这类优化的特点是通过对查询的关系代数表达式进行等价变换,根据关系代数表达式的等价变换规则就可以完成优化,减少执行开销,所以也称为规则优化。代数优化只改变查询语句中操作的次序和组合,不涉及底层的存取路径。
2. 基于存取路径的优化
合理选择各种操作的存取路径,可以取得显著的优化效果,这类问题称为基于存取路径的优化。基于存取路径的优化需要考虑数据的物理组织和访问路径,以及底层操作算法的选择,涉及数据文件的组织方法、数据值的分布情况等,所以也称为物理优化。
3. 基于代价估算的优化
对于多个可选的查询策略通过估算执行策略的代价,从中选择代价最小的作为执行策略,这种技术称为代价估算优化。代价估算优化由于需要计算操作执行的代价,开销较大。
此外,还有一种查询优化的方法已经被提出来,称为语义查询优化。这种技术是根据数据库模式上制定的约束,例如唯一属性或其他约束条件,把最初的查询转换成另一个执行效率较高的查询。这里,我们用一个简单的例子来说明。例如,查询那些工资比领导高的员工的姓名。假设,数据表上有约束,要求任何雇员的工资不能比他的直接领导的工资高。这样,一旦语义查询优化器检查到了这个约束条件,就会知道这个查询的结果是空,所以不需要再执行这个查询,这样可以节省相当多的时间。语义查询优化需要解决的一个关键问题是如何降低搜索约束条件的代价,主动规则是一个较好的解决方法。随着数据库系统中具有主动规则功能的实现,将来的数据库管理系统可能会加入语义查询优化的方式。
以上各种查询优化技术都可以在不同程度上减少查询处理的时间。在实际的关系数据库中,查询优化的具体实现不完全相同,但往往都综合运用了这些优化技术,以获得较好的查询优化效果。
查询优化的一般过程是: 首先将查询转换成某种内部表示,通常是语法树,再根据一定的等价变化规则对语法树进行优化,然后,选择底层的操作算法,对于语法树中的每个操作,根据存取路径、数据存储分布、存储数据的聚簇等信息选择具体的执行算法。最后,生成查询计划。查询计划是由一系列内部操作组成的,这些内部操作按照一定的次序构成查询的一个执行方案,通常这样的执行方案有很多,需要对每个执行计划计算代价,从中选择代价最小的一个。
5.2.2查询优化实例
下面结合学生选课数据库的一个查询实例,说明查询优化的必要性。
【例52】查询选修DataBase课程的学生成绩。用SQL表达如下:SELECTSC.Grade
 FROMCourse,SC
 WHERE Course.Cno=SC.Cno AND Course.Cname='DataBase';这个查询语句可以用多种等价的关系代数表达式表达: 
(1) ПGrade (σCourse.Cno =SC.Cno∧Course.Cname='DataBase'(Course×SC))
(2) ПGrade (σCourse.Cname='DataBase'(CourseSC)) 
(3) ПGrade(SCσCourse.Cname='DataBase'(Course))
假设学生选课数据库中SC表有10000个选课记录,Course表有100个课程记录,其中满足条件的元组,即选修DataBase课程的选课记录有100个。下面我们来分析这三个等价的关系代数表达式的查询效率。这里我们只是对查询执行过程进行粗略的估计,主要考虑I/O的代价,而CPU的代价忽略不计。
（1） 估计第一个表达式ПGrade (σCourse.Cno =SC.Cno∧Course.Cname='DataBase'(Course×SC))的查询代价
① 计算广义笛卡儿积 
求笛卡儿积需要把Course中的每个元组和SC的每个元组连接起来,也就是说,对于100个课程记录,每个都要与10000个选课记录连接起来。经过连接后产生的100×10000个元组,需要保存在中间文件中,写回到磁盘。
执行笛卡儿积操作的常用方式是: 内存被划分成若干物理存储块,首先在内存中尽可能多地装入Course表,留出一块存放SC的元组。然后,把SC中的每个元组和Course中的每个元组连接,完成之后,继续读入下一块SC的元组,同样和内存中Course的每个元组连接,依此类推,直到SC表的元组全部处理完毕。接下来,再把Course表中没有装入的元组尽可能多地装入内存,同样逐块装入SC表的元组去做元组的连接,直到Course表的所有元组全部进行完连接。
假设内存被划分为6块,每一个块能装10个Course元组或100个SC元组。每一次在内存中存放5块Course元组和1块SC元组,则读取的总块数由读取的Course表的块数(100/10)和SC表的块数组成,这里SC表被读取多次(100 /(10×5)),每一次读取SC表需要的块数是(10000/100),所以,
读取总块数＝10010＋10010×5×10000100＝10＋2×100 ＝210块
假定每秒读写20块,则总计要花210/20=10.5s 。连接后的元组数为100×10000=106。设每块能装10个元组,则写这些块要用105/20=5000s。
② 选择满足条件的元组 
这一步需要将上一步已经连接好的106个元组重新读入内存,按照选择条件选取满足条件的元组。假定内存处理时间忽略,那么读取中间文件花费的时间与写回中间文件的时间相同,等于5000s。满足条件的元组为100个,可以全部放在内存。
③ 在属性Grade上进行投影操作 
这里,仅需要在第②步的结果集的基础上作属性Sname的投影输出,得到最终结果,仍为100个元组,可以放在内存中,不需要进行I/O操作,同样忽略内存处理时间。 
因此,执行第一个表达式需要的查询时间≈10.5+5000+5000≈104s
(2) 估计第二个表达式ПGrade (σCourse.Cname='DataBase'(CourseSC))的查询代价 
① 作自然连接 
这一步首先需要装入Course和SC表的元组,读取Course和SC表的策略不变,需要花费的时间和代价与前面相同,总的读取块数仍为210块,时间大约10.5s。但是自然连接的结果集比第一种情况大大减少,为10000个元组,将这些元组写回磁盘的时间为104/10/20=50s。
② 选择满足条件的元组 
这一步需要将上一步已经连接好的10000个元组重新读入内存,检查是否满足选择条件,产生一个100个元组的结果集。需要的读取中间文件的时间与写回中间文件的时间相同,等于50s。
③ 在属性Grade上进行投影操作,不需要进行I/O操作
因此,执行第二个表达式需要的查询时间≈10.5+50+50≈110.5s。
（3）  估计第三个表达式ПGrade(SCσCourse.Cname='DataBase'(Course)) 的查询代价
① 做选择运算 
对Course表进行选择运算,需要先装入Course表元组,时间需要大约(100/10)/20＝0.5s,选择满足条件的元组,产生满足条件的结果集为1个,可以放在内存,不必使用中间文件。
② 做自然连接
这一步包括将10000个SC的元组依次读入内存,和内存中的1个Course元组作自然连接。只需读一遍SC表共10000/100=100块,大约花费时间为100/20=5s。
③ 在属性Grade上做投影操作,不需要做I/O操作
因此,执行第三个表达式需要的查询时间≈5+0.5＝5.5s
很明显,第三个表达式执行的效率最高。原因在于: 在第一个表达式中,以笛卡儿积的方式实现两个关系的查询。在第一个表达式基础上,将选择条件Course.Cno = SC.Cno与笛卡儿积组合成连接操作就得到了第二个表达式。将选择条件Course.Cname='DataBase'移到连接操作中的关系Course中,就得到了第三个表达式。每一次变换都使参加连接的元组大大减少,进而提高了查询效率,这就是代数优化。
进一步,数据表的选择操作算法分为顺序扫描和索引扫描两种方法,如果在SC表的Cno属性列上建立了索引,那么在(3)中的第②步里,就不用读取全部的SC元组,而只需要读入与课程名DataBase相对应的课程代码Cno相同的那些元组,那么读入SC的元组数将从10000降到100,这种基于索引扫描的方法能进一步提高查询的性能,这就是物理优化。
这个例子虽然简单,但可以看出,对于等价的关系代数表达式而言,相应的查询效率有着重大差异。它充分说明了查询优化的重要性和必要性,合理优化可以获得较高的查询效率。
5.3代 数 优 化
下面我们介绍基于关系代数等价变化规则的优化方法,即代数优化。代数优化技术与具体系统的存储技术无关,主要思想是对查询的代数表达式进行适当的等价变换,改变相关操作的先后执行顺序,把初始查询树转换成优化后的查询树,完成代数表达式的优化。代数优化的主要依据是关系代数表达式的等价变换规则。
5.3.1关系代数表达式的等价变换规则
代数优化策略是通过对关系代数表达式的等价变换来提高查询效率的。如果两个关系代数表达式用相同的关系代入之后得到的结果相同,则称这两个关系代数表达式是等价的。两个关系表达式E1和E2是等价的,可记为E1≡E2。代数优化的关键就是选择合理的等价表达式。下面给出关系代数中常用的等价变换规则,证明略。
1. 连接、笛卡儿积交换律
设E1和E2是关系代数表达式,F是连接运算的条件,则有
E1×E2≡E2× E1
E1E2≡E2E1
E1FE2≡E2FE1
在关系代数中,连接操作和笛卡儿积是可以交换的。因此,系统就可以自由地选择其中的小关系作为外关系进行连接,提高执行效率。
2. 连接、笛卡儿积的结合律
设E1、E2、E3是关系代数表达式,F1和F2是连接运算的条件,则有
(E1 × E2) × E3≡E1 × (E2 × E3)
(E1E2)E3≡E1(E2E3)
(E1F1E2)F2E3≡E1F1(E2F2E3) 
3. 投影的串接定律
ПA1,A2,…,An (ПB1,B2,…,Bm (E))≡ПA1,A2,…,An (E)
这里,E是关系代数表达式,Ai(i=1,2,…,n),Bj(j=1,2,…,m)是属性名,且{A1,A2,…,An}是{B1,B2,…,Bm}的子集。
这条定律说明如果满足既定的条件,对同一关系代数表达式的多个投影可以转换成其中最小的属性集的投影。
4. 选择的串接定律
设E是关系代数表达式,F1、F2是选择条件,则有
σF1(σF2(E))≡σF1∧F2(E)
这条定律说明对同一关系代数表达式的多个选择可以合并为一个AND连接的选择操作,这样一次选择操作就可以检查全部条件。
5. 选择与投影操作的交换律
设E是关系代数表达式,F是选择条件,并且选择条件F只涉及属性A1,…,An,则有