关系查询处理和查询优化复习过程.ppt

《关系查询处理和查询优化复习过程.ppt》由会员分享，可在线阅读，更多相关《关系查询处理和查询优化复习过程.ppt（68页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关系查询处理和查询优化关系查询处理和查询优化内容要求n掌握关系系统查询优化的相关概念掌握关系系统查询优化的相关概念n了解查询优化的一般准则及步骤了解查询优化的一般准则及步骤n能够运用关系代数表达式的优化算法画能够运用关系代数表达式的优化算法画出查询语法树以及优化后的语法树出查询语法树以及优化后的语法树本讲内容一、关系数据库系统的查询处理一、关系数据库系统的查询处理二、关系数据库系统的查询优化二、关系数据库系统的查询优化三、代数优化三、代数优化四、物理优化四、物理优化一、关系数据库系统的查询处理n什么是查询处理？什么是查询处理？从数据库中检索数据的活动。从数据库中检索数据的活动。n查询处理的任务

2、查询处理的任务把用户提交给把用户提交给RDBMSRDBMS的查询语句转换为高效的执的查询语句转换为高效的执行计划。行计划。n查询处理的目标查询处理的目标将高级语言（例如将高级语言（例如SQLSQL）表示的查询转换为正确）表示的查询转换为正确有效的、用低级语言表达的有效的、用低级语言表达的执行策略执行策略，即实现关，即实现关系代数，并通过执行该策略来获取所需的数据。系代数，并通过执行该策略来获取所需的数据。一、关系数据库系统的查询处理1.1.查询处理步骤查询处理步骤2.2.实现查询操作的算法示例实现查询操作的算法示例 1.查询处理步骤nRDBMSRDBMS查询处理过程查询处理过程 ：（1 1）查

3、询分析查询分析（2 2）查询检查查询检查（3 3）查询优化查询优化 （4 4）查询执行查询执行 查询处理步骤（续）查询处理步骤（1）查询分析n对查询语句进行扫描、词法分析和语法对查询语句进行扫描、词法分析和语法分析分析 n从查询语句中识别出语言符号从查询语句中识别出语言符号 n进行语法检查和语法分析进行语法检查和语法分析 （2）查询检查 n根据数据字典对合法的查询语句进行语义检查根据数据字典对合法的查询语句进行语义检查 n根据数据字典中的用户权限和完整性约束定义对根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查用户的存取权限进行检查 n检查通过后把检查通过后把SQLSQL查询语

4、句转换成等价的关系代数查询语句转换成等价的关系代数表达式表达式 nRDBMSRDBMS一般都用查询树一般都用查询树(语法分析树语法分析树)来表示扩展的来表示扩展的关系代数表达式关系代数表达式 n把数据库对象的外部名称转换为内部表示把数据库对象的外部名称转换为内部表示 （3）查询优化n查询优化：选择一个高效执行的查询处理策略查询优化：选择一个高效执行的查询处理策略 n查询优化分类查询优化分类 ：n代数优化：指关系代数表达式的优化代数优化：指关系代数表达式的优化n物理优化：指存取路径和底层操作算法的选择物理优化：指存取路径和底层操作算法的选择n查询优化方法选择的依据：查询优化方法选择的依据：n基于

5、规则基于规则(rule based)(rule based)n基于代价基于代价(cost based)(cost based)n基于语义基于语义(semantic based)(semantic based)（4）查询执行 n依据优化器得到的执行策略生成查询计依据优化器得到的执行策略生成查询计划划n代码生成器代码生成器(code generator)(code generator)生成执行生成执行查询计划的代码查询计划的代码 示例例：用户例：用户U1U1针对学生课程数据库，完成如针对学生课程数据库，完成如下查询：下查询：select student.sno,cno,Gradeselect st

6、udent.sno,cno,Gradefrom student,scfrom student,scwhere student.sno=sc.sno and where student.sno=sc.sno and sdept=CSsdept=CS与之等价的关系代数表达式？优化后的关系代数与之等价的关系代数表达式？优化后的关系代数表达式？表达式？2.实现查询操作的算法示例（1 1）选择操作的实现）选择操作的实现 （2 2）连接操作的实现）连接操作的实现 示例1 选择操作的实现 例例Select*from student where Select*from student where ；考虑考虑

7、的几种情况：的几种情况：C1 C1：无条件；：无条件；C2 C2：SnoSno200215121200215121；C3 C3：Sage20Sage20；C4 C4：SdeptSdeptCS AND Sage20CS AND Sage20；选择操作的实现（续）1 1）简单的全表扫描方法）简单的全表扫描方法 对查询的基本表顺序扫描，逐一检查每个元组是否对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出满足选择条件，把满足条件的元组作为结果输出 适合小表，不适合大表适合小表，不适合大表2 2）索引）索引(或散列或散列)扫描方法扫描方法 适合选择条件中的属性上有索

8、引适合选择条件中的属性上有索引(例如例如B+B+树索引或树索引或HashHash索引索引)通过索引先找到满足条件的元组主码或元组指针，通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组再通过元组指针直接在查询的基本表中找到元组 选择操作的实现（续）例例1-C21-C2 以以C2C2为例，为例，SnoSno200215121200215121，并且，并且SnoSno上上有索引有索引(或或SnoSno是散列码是散列码)n使用索引使用索引(或散列或散列)得到得到SnoSno为为200215121 200215121 元组的指元组的指针针n通过元组指针在通过元组指针

9、在studentstudent表中检索到该学生表中检索到该学生例例1-C31-C3 以以C3C3为例，为例，Sage20Sage20，并且，并且Sage Sage 上有上有B+B+树树索引索引n使用使用B+B+树索引找到树索引找到SageSage2020的索引项，以此为入口点的索引项，以此为入口点在在B+B+树的顺序集上得到树的顺序集上得到Sage20Sage20的所有元组指针的所有元组指针n通过这些元组指针到通过这些元组指针到studentstudent表中检索到所有年龄大于表中检索到所有年龄大于2020的学生。的学生。选择操作的实现（续）例例1-C41-C4 以以C4C4为例，为例，Sde

10、ptSdeptCS AND Sage20CS AND Sage20，如如果果SdeptSdept和和SageSage上都有索引：上都有索引：算法一：分别用上面两种方法分别找到算法一：分别用上面两种方法分别找到SdeptSdeptCSCS的的一一组元组指针和组元组指针和Sage20Sage20的另一组元组指针的另一组元组指针求这求这2 2组指针的交集组指针的交集到到studentstudent表中检索表中检索得到计算机系年龄大于得到计算机系年龄大于2020的学生的学生算法二：找到算法二：找到SdeptSdeptCSCS的一组元组指针，的一组元组指针，通过这些元组指针到通过这些元组指针到stude

11、ntstudent表中检索表中检索对得到的元组检查另一些选择条件对得到的元组检查另一些选择条件(如如Sage20)Sage20)是是否满足否满足把满足条件的元组作为结果输出。把满足条件的元组作为结果输出。（2）连接操作的实现 n连接操作是查询处理中最耗时的操作之一连接操作是查询处理中最耗时的操作之一 n本节只讨论等值连接本节只讨论等值连接(或自然连接或自然连接)最常用的实最常用的实现算法现算法 例例2 2 SELECT*SELECT*FROM Student FROM Student，SC SC WHERE Student.Sno=SC.Sno WHERE Student.Sno=SC.Sno

12、；连接操作的实现（续）1 1）嵌套循环方法嵌套循环方法(nested loop)(nested loop)2 2）排序排序-合并方法合并方法(sort-merge join(sort-merge join 或或merge merge join)join)3 3）索引连接索引连接(index join)(index join)方法方法 4 4）Hash Join Hash Join方法方法 1）嵌套循环方法）嵌套循环方法(nested loop)n对外层循环对外层循环(Student)(Student)的每一个元组的每一个元组(s)(s)，检索内层循环检索内层循环(SC)(SC)中的每一个元组中

13、的每一个元组(sc)(sc)n检查这两个元组在连接属性检查这两个元组在连接属性(sno)(sno)上是否相上是否相等等n如果满足连接条件，则串接后作为结果输如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止出，直到外层循环表中的元组处理完为止 SnoSnameSsexSageSdept200215121李勇李勇男男20CS200215122刘晨刘晨女女19IS200215123王敏王敏女女18MA200215125张立张立男男19IS学学 号号课课 程程 号号成成 绩绩SnoCnoGrade20021512119220021512128520021512138820021

14、51222902002151223802）排序）排序-合并方法合并方法n适合连接的诸表已经排好序的情况适合连接的诸表已经排好序的情况 n排序合并连接方法的步骤：排序合并连接方法的步骤：如果连接的表没有排好序，先对如果连接的表没有排好序，先对StudentStudent表和表和SCSC表按表按连接属性连接属性SnoSno排序排序 取取StudentStudent表中第一个表中第一个SnoSno，依次扫描，依次扫描SCSC表中具有相同表中具有相同SnoSno的元组的元组 2）排序）排序-合并方法合并方法（续）200215121200215122200215123200215124.20021512

15、1 1 92200215121 2 85200215121 3 88200215122 2 90200215122 3 80.排序-合并连接方法示意图2）排序）排序-合并方法合并方法（续）n排序合并连接方法的步骤（续）：排序合并连接方法的步骤（续）：当扫描到当扫描到SnoSno不相同的第一个不相同的第一个SCSC元组时，返回元组时，返回StudentStudent表扫描它的下一个元组，再扫描表扫描它的下一个元组，再扫描SCSC表中表中具有相同具有相同SnoSno的元组，把它们连接起来的元组，把它们连接起来 重复上述步骤直到重复上述步骤直到Student Student 表扫描完表扫描完3）索引

16、连接索引连接(index join)方法方法n步骤：步骤：在在SCSC表上建立属性表上建立属性SnoSno的索引，如果原来没的索引，如果原来没有该索引。有该索引。对对StudentStudent中每一个元组，由中每一个元组，由SnoSno值通过值通过SCSC的索引查找相应的的索引查找相应的SCSC元组。元组。把这些把这些SCSC元组和元组和StudentStudent元组连接起来元组连接起来 循环执行循环执行，直到，直到StudentStudent表中的元组处理表中的元组处理完为止。完为止。4）Hash Join方法方法n把连接属性作为把连接属性作为hashhash码，用同一个码，用同一个ha

17、shhash函数把函数把R R和和S S中的元组散列到同一个中的元组散列到同一个hashhash文件中。文件中。n第一步，划分阶段。第一步，划分阶段。对包含较少元组的表（如对包含较少元组的表（如R R表）进行一遍处理，把它表）进行一遍处理，把它的元组按的元组按hashhash函数分散到函数分散到hashhash表的桶中。表的桶中。n第二步，试探阶段，也称连接阶段。第二步，试探阶段，也称连接阶段。对另一个表（对另一个表（S S）进行一遍处理，把）进行一遍处理，把S S的元组散列到适的元组散列到适当的当的hashhash桶中，并把元组与桶中所有来自桶中，并把元组与桶中所有来自R R并与之相匹并与之

18、相匹配的元组连接起来。配的元组连接起来。二、关系数据库系统的查询优化n为什么提出来查询优化？为什么提出来查询优化？这是由关系数据库系统的特点决定的，系统应该考虑这是由关系数据库系统的特点决定的，系统应该考虑采用什么样的查询才能做到执行起来既省时间，又省采用什么样的查询才能做到执行起来既省时间，又省空间，而且效率也比较高。空间，而且效率也比较高。n什么是查询优化？什么是查询优化？选择有效的执行策略执行查询的活动。选择有效的执行策略执行查询的活动。n查询优化的目标查询优化的目标对于同一个高级查询有许多等价变换，对于同一个高级查询有许多等价变换，RDBMSRDBMS选择占选择占用资源最小的一种。这就

19、是查询优化的目标。用资源最小的一种。这就是查询优化的目标。二、关系数据库系统的查询优化1.1.查询优化的重要性查询优化的重要性2.2.查询优化的可能性查询优化的可能性3.3.查询优化的必要性查询优化的必要性1.查询优化的重要性n关系系统的关系系统的查询优化即是查询优化即是RDBMSRDBMS实现的关键技实现的关键技术又是关系系统的优点所在。术又是关系系统的优点所在。它减轻了用户选它减轻了用户选择存取路径的负担。用户只要提出择存取路径的负担。用户只要提出“干什么干什么”，不必指出，不必指出“怎么干怎么干”。n查询优化的优点不仅在于用户不必考虑如何最查询优化的优点不仅在于用户不必考虑如何最好地表达

20、查询以获得较好的效率，而且在于系好地表达查询以获得较好的效率，而且在于系统可以比用户程序的统可以比用户程序的“优化优化”做得更好。做得更好。n思考：查询优化由谁来完成？思考：查询优化由谁来完成？2.查询优化的可能性(1)(1)优化器可以从数据字典中获取许多统计信息，优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息而用户程序则难以获得这些信息(2)(2)如果数据库的物理统计信息改变了，系统可以自如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用关系系统中

21、必须重写程序，而重写程序在实际应用中往往是不太可能的。中往往是不太可能的。2.查询优化的可能性(3)(3)优化器可以考虑数百种不同的执行计划，程序优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。员一般只能考虑有限的几种可能性。(4)(4)优化器中包括了很多复杂的优化技术，这些优优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化的自动优化相当于使得所有人都拥有这些优化技术。技术。查询时间开销nRDBMSRDBMS通通过过某某种种代代价价模模型型计计算算出出各各种种

22、查查询询执执行行策策略略的的执执行代价，然后选取代价最小的执行方案行代价，然后选取代价最小的执行方案n集中式数据库集中式数据库执行开销主要包括：执行开销主要包括：n磁盘存取块数磁盘存取块数(I/O(I/O代价代价)n处理机时间处理机时间(CPU(CPU代价代价)n查询的内存开销查询的内存开销 I/OI/O代价是最主要的代价是最主要的 n分布式数据库分布式数据库总代价总代价=I/O=I/O代价代价+CPU+CPU代价代价+内存代价内存代价通信代价通信代价 查询优化的总目标n选择有效的策略选择有效的策略n求得给定关系表达式的值求得给定关系表达式的值n使得查询代价最小使得查询代价最小(实际上是较小实

23、际上是较小)示例查询优化的必要性 例例3 3 求选修了求选修了2 2号课程的学生姓名。用号课程的学生姓名。用SQLSQL表达：表达：SELECT Student.SnameSELECT Student.Sname FROM Student FROM Student，SCSC WHERE Student.Sno=SC.Sno AND WHERE Student.Sno=SC.Sno AND SC.Cno=2 SC.Cno=2；n假定学生假定学生-课程数据库中有课程数据库中有10001000个学生记录，个学生记录，1000010000个选课记录个选课记录n其中选修其中选修2 2号课程的选课记录为号

24、课程的选课记录为5050个个 查询优化的必要性（续）n系统可以用多种等价的关系代数表达式系统可以用多种等价的关系代数表达式来完成这一查询来完成这一查询Q Q1 1=SnameSname(Student.Sno=SC.SnoSc.Cno=2Student.Sno=SC.SnoSc.Cno=2 (StudentSC)(StudentSC)Q Q2 2=SnameSname(Sc.Cno=2Sc.Cno=2(Student SC)(Student SC)Q Q3 3=SnameSname(Student (Student Sc.Cno=2Sc.Cno=2(SC)(SC)查询优化的必要性（续）（1 1

25、）第一种情况）第一种情况 Q Q1 1=SnameSname(Student.Sno=SC.SnoSc.Cno=2Student.Sno=SC.SnoSc.Cno=2(StudentSC)(StudentSC)1)1)计算广义笛卡尔积计算广义笛卡尔积 n把把StudentStudent和和SCSC的每个元组连接起来的做法：的每个元组连接起来的做法：n在内存中尽可能多地装入某个表在内存中尽可能多地装入某个表(如如StudentStudent表表)的若干块，留出一的若干块，留出一块存放另一个表块存放另一个表(如如SCSC表表)的元组。的元组。n把把SCSC中的每个元组和中的每个元组和Student

26、Student中每个元组连接，连接后的元组装满中每个元组连接，连接后的元组装满一块后就写到中间文件上一块后就写到中间文件上n从从SCSC中读入一块和内存中的中读入一块和内存中的StudentStudent元组连接，直到元组连接，直到SCSC表处理完。表处理完。n再读入若干块再读入若干块StudentStudent元组，读入一块元组，读入一块SCSC元组元组n重复上述处理过程，直到把重复上述处理过程，直到把StudentStudent表处理完表处理完查询优化的必要性（续）n设一个块能装设一个块能装1010个个StudentStudent元组或元组或100100个个SCSC元组，在内存元组，在内存

27、中存放中存放5 5块块StudentStudent元组和元组和1 1块块SCSC元组，则读取总块数为元组，则读取总块数为 =100+20100=2100 =100+20100=2100块块n其中，读其中，读StudentStudent表表100100块。读块。读SCSC表表2020遍，每遍遍，每遍100100块。若块。若每秒读写每秒读写2020块，则总计要花块，则总计要花105s 105s n连接后的元组数为连接后的元组数为10103 310104 4=10=107 7。设每块能装。设每块能装1010个元组，个元组，则写出这些块要用则写出这些块要用10106 6/20=510/20=5104

28、4s s 查询优化的必要性（续）2)2)作选择操作作选择操作 n依次读入连接后的元组，按照选择条件选取依次读入连接后的元组，按照选择条件选取满足要求的记录满足要求的记录 n假定内存处理时间忽略。读取中间文件花费假定内存处理时间忽略。读取中间文件花费的时间的时间(同写中间文件一样同写中间文件一样)需需5105104 4s s n满足条件的元组假设仅满足条件的元组假设仅5050个，均可放在内存个，均可放在内存 查询优化的必要性（续）3)3)作投影操作作投影操作 n把第把第2 2步的结果在步的结果在SnameSname上作投影输出，得到上作投影输出，得到最终结果最终结果 n第一种情况下执行查询的总时

29、间第一种情况下执行查询的总时间105+2510105+25104 410105 5s sn所有内存处理时间均忽略不计所有内存处理时间均忽略不计 查询优化的必要性（续）(2)(2)第二种情况第二种情况 Q Q2 2=SnameSname(Sc.Cno=2Sc.Cno=2(Student SC)(Student SC)1)1)计算自然连接计算自然连接 执行自然连接，读取执行自然连接，读取StudentStudent和和SCSC表的策略不变，总的表的策略不变，总的读取块数仍为读取块数仍为21002100块花费块花费105 s 105 s 自然连接的结果比第一种情况大大减少，为自然连接的结果比第一种情

30、况大大减少，为10104 4个个 写出这些元组时间为写出这些元组时间为10104 4/10/20=50s/10/20=50s，为第一种情况的，为第一种情况的千分之一千分之一 2)2)读取中间文件块，执行选择运算，花费时间也为读取中间文件块，执行选择运算，花费时间也为50s50s。3)3)把第把第2 2步结果投影输出。步结果投影输出。第二种情况总的执行时间第二种情况总的执行时间105+50+50205s 105+50+50205s 查询优化的必要性（续）(3)(3)第三种情况第三种情况 Q Q3 3=SnameSname(Student (Student Sc.Cno=2Sc.Cno=2(SC)

31、(SC)1)1)先对先对SCSC表作选择运算，只需读一遍表作选择运算，只需读一遍SCSC表，存取表，存取100100块块花费时间为花费时间为5s5s，因为满足条件的元组仅，因为满足条件的元组仅5050个，不必使个，不必使用中间文件。用中间文件。2)2)读取读取StudentStudent表，把读入的表，把读入的StudentStudent元组和内存中的元组和内存中的SCSC元组作连接。也只需读一遍元组作连接。也只需读一遍StudentStudent表共表共100100块，花费块，花费时间为时间为5s5s。3)3)把连接结果投影输出把连接结果投影输出 第三种情况总的执行时间第三种情况总的执行时间

32、5+55+510s 10s 查询优化的必要性（续）n假如假如SCSC表的表的CnoCno字段上有索引字段上有索引n第一步就不必读取所有的第一步就不必读取所有的SCSC元组而只需读取元组而只需读取Cno=2Cno=2的那些元组的那些元组(50(50个个)n存取的索引块和存取的索引块和SCSC中满足条件的数据块大约总共中满足条件的数据块大约总共3 34 4块块n若若StudentStudent表在表在SnoSno上也有索引上也有索引n第二步也不必读取所有的第二步也不必读取所有的StudentStudent元组元组n因为满足条件的因为满足条件的SCSC记录仅记录仅5050个，涉及最多个，涉及最多50

33、50个个StudentStudent记录记录n读取读取StudentStudent表的块数也可大大减少表的块数也可大大减少 n总的存取时间将进一步减少到数秒总的存取时间将进一步减少到数秒 查询优化的必要性（续）n把代数表达式把代数表达式Q Q1 1变换为变换为Q Q2 2、Q Q3 3，n即有选择和连接操作时，先做选择操作，这样参加连即有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是代数优化接的元组就可以大大减少，这是代数优化n在在Q Q3 3中中nSCSC表的选择操作算法有全表扫描和索引扫描表的选择操作算法有全表扫描和索引扫描2 2种方法，种方法，经过初步估算，索引扫

34、描方法较优经过初步估算，索引扫描方法较优 n对于对于StudentStudent和和SCSC表的连接，利用表的连接，利用StudentStudent表上的索引，表上的索引，采用采用index joinindex join代价也较小，这就是物理优化代价也较小，这就是物理优化 三、代数优化1.1.关系代数表达式等价变换规则关系代数表达式等价变换规则 2.2.查询树的启发式优化查询树的启发式优化 1.关系代数表达式等价变换规则 n代数优化策略：通过对关系代数表达式的等价代数优化策略：通过对关系代数表达式的等价变换来提高查询效率变换来提高查询效率 n关系代数表达式的等价：指用相同的关系代替关系代数表达

35、式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同两个表达式中相应的关系所得到的结果是相同的的 n两个关系表达式两个关系表达式E E1 1和和E E2 2是等价的，可记为是等价的，可记为E E1 1E E2 2 常用的等价变换规则：(1)(1)连接、笛卡尔积交换律连接、笛卡尔积交换律 设设E E1 1和和E E2 2是关系代数表达式，是关系代数表达式，F F是连接运算的条件，则有是连接运算的条件，则有 E E1 1 E E2 2E E2 2 E E1 1 E E1 1 E E2 2E E2 2 E E1 1 E E1 1 E E2 2E E2 2 E E1 1(2)(2)连接

36、、笛卡尔积的结合律连接、笛卡尔积的结合律 设设E E1 1，E E2 2，E E3 3是关系代数表达式，是关系代数表达式，F F1 1和和F F2 2是连接运算的条件，是连接运算的条件，则有则有 (E E1 1 E E2 2)E E3 3E E1 1 (E E2 2 E E3 3)(E E1 1 E E2 2)E E3 3E E1 1 (E E2 2 E E3 3)(E E1 1 E E2 2)E E3 3E E1 1 (E E2 2 E E3 3)常用的等价变换规则：(3)(3)投影的串接定律投影的串接定律 (E E)()(E E)这里，这里，E E是关系代数表达式，是关系代数表达式，A A

37、i i(i i=1=1，2 2，n n)，B Bj j(j j=1=1，2 2，m m)是属性名且是属性名且 A A1 1，A A2 2，A An n 构成构成 B B1 1，B B2 2，B Bm m 的子集。的子集。(4)(4)选择的串接定律选择的串接定律 (E E)()(E E)这里，这里，E E是关系代数表达式，是关系代数表达式，F F1 1、F F2 2是选择条件。是选择条件。选择的串接律说明选择条件可以合并。这样一次就可检选择的串接律说明选择条件可以合并。这样一次就可检查全部条件。查全部条件。常用的等价变换规则：(5)(5)选择与投影操作的交换律选择与投影操作的交换律 F F(E

38、E)()(F F(E E)选择条件选择条件F F只涉及属性只涉及属性A A1 1，A An n。若若F F中有不属于中有不属于A A1 1，A An n的属性的属性B B1 1，B Bm m则有更一则有更一般的规则：般的规则：(F F(E E)(F F(E E)常用的等价变换规则：(6)(6)选择与笛卡尔积的交换律选择与笛卡尔积的交换律如果如果F F中涉及的属性都是中涉及的属性都是E E1 1中的属性，则中的属性，则 (E E1 1E E2 2)()(E E1 1)E E2 2如果如果F=FF=F1 1FF2 2，并且，并且F F1 1只涉及只涉及E E1 1中的属性，中的属性，F F2 2只

39、涉及只涉及E E2 2中的属性，则由上面的等价变换规则中的属性，则由上面的等价变换规则1 1，4 4，6 6可推出：可推出：(E E1 1E E2 2)()(E E1 1)()(E E2 2)若若F F1 1只涉及只涉及E E1 1中的属性，中的属性，F F2 2涉及涉及E E1 1和和E E2 2两者的属性，则两者的属性，则仍有仍有 (E E1 1E E2 2)()(E E1 1)E E2 2)它使部分选择在笛卡尔积前先做。它使部分选择在笛卡尔积前先做。常用的等价变换规则：(7)(7)选择与并的分配律选择与并的分配律设设E E=E E1 1E E2 2，E E1 1，E E2 2有相同的属性

40、名，则有相同的属性名，则 F F(E E1 1E E2 2)F F(E E1 1)F F(E E2 2)(8)(8)选择与差运算的分配律选择与差运算的分配律若若E E1 1与与E E2 2有相同的属性名，则有相同的属性名，则 F F(E E1 1-E E2 2)F F(E E1 1)-)-F F(E E2 2)(9)(9)选择对自然连接的分配律选择对自然连接的分配律 F F(E E1 1 E E2 2)F F(E E1 1)F F(E E2 2)F F只涉及只涉及E E1 1与与E E2 2的公共属性的公共属性 常用的等价变换规则：(10)(10)投影与笛卡尔积的分配律投影与笛卡尔积的分配律设

41、设E E1 1和和E E2 2是两个关系表达式，是两个关系表达式，A A1 1，A An n是是E E1 1的属性，的属性，B B1 1，B Bm m是是E E2 2的属性，则的属性，则 (E E1 1E E2 2)()(E E1 1)()(E E2 2)(11)(11)投影与并的分配律投影与并的分配律设设E E1 1和和E E2 2有相同的属性名，则有相同的属性名，则 (E E1 1E E2 2)()(E E1 1)()(E E2 2)2.查询树的启发式优化 n典型的启发式规则：典型的启发式规则：(1)(1)选择运算应尽可能先做。选择运算应尽可能先做。在优化策略中这是最在优化策略中这是最重要

42、、最基本的一条重要、最基本的一条(2)(2)把投影运算和选择运算同时进行把投影运算和选择运算同时进行如有若干投影和选择运算，并且它们都对同一个关系操如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系避免重复扫描关系查询树的启发式优化（续）(3)(3)把投影同其前或其后的双目运算结合起来把投影同其前或其后的双目运算结合起来(4)(4)把某些选择同在它前面要执行的笛卡尔积结合起来把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算成为一个连接运算(5)(5)找出公共子表达式找出公共

43、子表达式如果这种重复出现的子表达式的结果不是很大的关如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的写入中间文件是合算的当查询的是视图时，定义视图的表达式就是公共子当查询的是视图时，定义视图的表达式就是公共子表达式的情况表达式的情况关系表达式的优化算法n遵循这些启发式规则，应用遵循这些启发式规则，应用9.3.19.3.1的等价变换公式来优的等价变换公式来优化关系表达式的算法。化关系表达式的算法。算法：关系

44、表达式的优化算法：关系表达式的优化输入：一个关系表达式的查询树输入：一个关系表达式的查询树输出：优化的查询树输出：优化的查询树方法：方法：(1)(1)利用等价变换规则利用等价变换规则4 4把形如把形如F1F2FnF1F2Fn(E)(E)变换为变换为F1F1(F2F2(FnFn(E)(E)。(2)(2)对每一个选择，利用等价变换规则对每一个选择，利用等价变换规则4 49 9尽可能把尽可能把它移到树的叶端。它移到树的叶端。查询树的启发式优化（续）(3)(3)对每一个投影利用等价变换规则对每一个投影利用等价变换规则3 3，5 5，1010，1111中中的一般形式尽可能把它移向树的叶端。的一般形式尽可

45、能把它移向树的叶端。n注意：注意：等价变换规则等价变换规则3 3使一些投影消失使一些投影消失规则规则5 5把一个投影分裂为两个，其中一个有可能把一个投影分裂为两个，其中一个有可能被移向树的叶端被移向树的叶端 (4)(4)利用等价变换规则利用等价变换规则3 35 5把选择和投影的串接合并把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完多个选择或投影能同时执行，或在一次扫描中全部完成成 查询树的启发式优化（续）(5)(5)把上述得到的语法树的内节点分组。每一双目运把上述得到的语法树的内节

46、点分组。每一双目运算算(，-)-)和它所有的直接祖先为一组和它所有的直接祖先为一组(这些直接这些直接祖先是祖先是(，运算运算)。n如果其后代直到叶子全是单目运算，则也将它们并如果其后代直到叶子全是单目运算，则也将它们并入该组入该组n但当双目运算是笛卡尔积但当双目运算是笛卡尔积()()，而且后面不是与它，而且后面不是与它组成等值连接的选择时，则不能把选择与这个双目组成等值连接的选择时，则不能把选择与这个双目运算组成同一组，把这些单目运算单独分为一组运算组成同一组，把这些单目运算单独分为一组 示例查询树的启发式优化例例4 4 下面给出例下面给出例3 3（查询选修了（查询选修了2 2号课程的学生号课

47、程的学生姓名）中姓名）中SQLSQL语句的代数优化示例。语句的代数优化示例。(1)(1)把把SQLSQL语句转换成查询树，如下图所示语句转换成查询树，如下图所示 查询树查询树的启发式优化（续）为了使用关系代数表达式的优化法，假设内部表示是为了使用关系代数表达式的优化法，假设内部表示是关系代数语法树，则上面的查询树如下图所示。关系代数语法树，则上面的查询树如下图所示。关系代数语法树 查询树的启发式优化（续）(2)(2)对查询树进行优化对查询树进行优化利用规则利用规则4 4、6 6把选择把选择SC.CnoSC.Cno=2=2移到叶端，查询树便移到叶端，查询树便转换转换成下图所示的优化的查询树。这就

48、是成下图所示的优化的查询树。这就是9.2.29.2.2节中节中Q Q3 3的查询的查询树表示树表示优化后的查询树 四、物理优化n代数优化改变查询语句中操作的次序和组合，代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径不涉及底层的存取路径n对于一个查询语句有许多存取方案，它们的执对于一个查询语句有许多存取方案，它们的执行效率不同，行效率不同，仅仅进行代数优化是不够的仅仅进行代数优化是不够的 n物理优化就是要选择高效合理的操作算法或存物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划取路径，求得优化的查询计划 物理优化（续）n选择的方法：选择的方法：n基于启发式规则的存

49、取路径选择优化基于启发式规则的存取路径选择优化n基于代价估算的优化基于代价估算的优化n两者结合的优化方法两者结合的优化方法基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化n选择操作的启发式规则有：选择操作的启发式规则有：n对于小关系，使用全表顺序扫描对于小关系，使用全表顺序扫描n对于大关系对于大关系n选择条件是主码选择条件是主码=值，可以选择主码索引值，可以选择主码索引n选择条件是非主属性选择条件是非主属性=值的查询，并且选择列上值的查询，并且选择列上有索引，则要估算查询结果的元组数目，如果比有索引，则要估算查询结果的元组数目，如果比例较小（例较小（10%10%）可以使用索引扫

50、描方法，否则还）可以使用索引扫描方法，否则还是使用全表顺序扫描。是使用全表顺序扫描。n选择条件是属性上的非等值查询或范围查询，同选择条件是属性上的非等值查询或范围查询，同上。上。n对于对于andand连接的选择条件，可优先采用组合索引连接的选择条件，可优先采用组合索引扫描方法。扫描方法。连接操作的启发式规则n如果如果2 2个表都已经按照连接属性排序，则选用个表都已经按照连接属性排序，则选用排序排序-合并方法合并方法n如果一个表在连接属性上有索引，则可以选用如果一个表在连接属性上有索引，则可以选用索引连接方法。索引连接方法。n如果上面如果上面2 2个规则都不适用，其中一个表较小，个规则都不适用，