《数据库系统概论》第5版原版授课-第9章

1、An Introduction to Database System数据库系统概论 An Introduction to Database System中国人民大学信息学院中国人民大学信息学院第九章第九章 关系查询处理关系查询处理 和查询优化和查询优化An Introduction to Database System第三篇第三篇 系统篇系统篇 v讨论数据库管理系统中查询处理和事务管理的基讨论数据库管理系统中查询处理和事务管理的基本概念和基础知识本概念和基础知识n第第9章章 关系查询处理和查询优化关系查询处理和查询优化n第第10章章 数据库恢复技术数据库恢复技术n第第11章章 并发控制并发控制

2、n第第12章章 数据库管理系统数据库管理系统An Introduction to Database System第九章第九章 关系关系查询处理和查询查询处理和查询优化优化9.1 关系数据库系统的查询处理关系数据库系统的查询处理 9.2 关系数据库系统的查询优化关系数据库系统的查询优化 9.3 代数优化代数优化 9.4 物理优化物理优化 *9.5 查询计划的执行查询计划的执行9.6 小小 结结 An Introduction to Database System关系关系查询处理和查询查询处理和查询优化（续）优化（续）v本章内容：本章内容： n关系数据库管理系统的查询处理步骤关系数据库管理系统的查

3、询处理步骤 n查询优化的概念查询优化的概念 n基本方法和技术基本方法和技术 v查询优化分类查询优化分类 ：n代数优化：指关系代数表达式的优化代数优化：指关系代数表达式的优化 n物理优化：指存取路径和底层操作算法的选择物理优化：指存取路径和底层操作算法的选择An Introduction to Database System9.1 关系数据库系统的查询处理关系数据库系统的查询处理9.1.1 查询处理步骤查询处理步骤9.1.2 实现查询操作的算法示例实现查询操作的算法示例 An Introduction to Database System9.1.1 查询处理步骤查询处理步骤v关系数据库管理系统查

4、询处理阶段关系数据库管理系统查询处理阶段 ： 1. 查询分析查询分析2. 查询检查查询检查3. 查询优化查询优化 4. 查询执行查询执行 An Introduction to Database System查询处理步骤（续）查询处理步骤（续）查询计划的执行代码查询计划的执行代码代数优化代数优化物理优化等物理优化等查询语句查询语句词法分析词法分析语法分析语法分析语义分析语义分析符号名转换符号名转换安全性检查安全性检查完整性初步检查完整性初步检查代码生成代码生成查询执行计划查询执行计划查询树查询树(query tree)查询分析查询分析查询检查查询检查查询优化查询优化查询执行查询执行数据库数据库数

5、据字典数据字典An Introduction to Database System 1. 查询分析查询分析v查询分析的任务：对查询语句进行扫描查询分析的任务：对查询语句进行扫描、词法分词法分析析和和语法分析语法分析n词法分析：从查询语句中识别出正确的语言符号词法分析：从查询语句中识别出正确的语言符号 n语法分析：进行语法检查语法分析：进行语法检查An Introduction to Database System 2. 查询检查查询检查 v查询检查的任务查询检查的任务n合法权检查合法权检查n视图转换视图转换n安全性检查安全性检查n完整性初步检查完整性初步检查v根据数据字典中有关的模式定义检查语

6、句中的数根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效据库对象，如关系名、属性名是否存在和有效 v如果是对视图的操作，则要用视图消解方法把对如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作视图的操作转换成对基本表的操作An Introduction to Database System 2. 查询检查查询检查 v根据数据字典中的用户权限和完整性约束定义对根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查用户的存取权限进行检查v检查通过后把检查通过后把SQL查询语句转换成内部表示，即查询语句转换成内部表示，即等价的等价的关

7、系代数表达式关系代数表达式。v关系数据库管理系统一般都用查询树，也称为语关系数据库管理系统一般都用查询树，也称为语法分析树法分析树来表示扩展的关系代数表达式。来表示扩展的关系代数表达式。An Introduction to Database System 3. 查询优化查询优化v查询优化：选择一个高效执行的查询处理策略查询优化：选择一个高效执行的查询处理策略 v查询优化分类查询优化分类 n代数优化代数优化/逻辑优化：指关系代数表达式的优化逻辑优化：指关系代数表达式的优化n物理优化：指存取路径和底层操作算法的选择物理优化：指存取路径和底层操作算法的选择v查询优化的选择依据查询优化的选择依据n基于

8、规则基于规则(rule based)n基于代价基于代价(cost based)n基于语义基于语义(semantic based)An Introduction to Database System 4. 查询执行查询执行 v依据优化器得到的执行策略生成查询执行计划依据优化器得到的执行策略生成查询执行计划v代码生成器代码生成器(code generator)生成执行查询计划生成执行查询计划的代码的代码 v两种执行方法两种执行方法n自顶向下自顶向下n自底向上自底向上An Introduction to Database System9.1 关系数据库系统的查询处理关系数据库系统的查询处理9.1.1

9、 查询处理步骤查询处理步骤9.1.2 实现查询操作的算法示例实现查询操作的算法示例 An Introduction to Database System9.1.2 实现查询操作的算法示例实现查询操作的算法示例 v 选择操作的实现选择操作的实现 v 连接操作的实现连接操作的实现 An Introduction to Database System1.选择操作的实现选择操作的实现v选择操作典型实现方法：选择操作典型实现方法：（1） 全表扫描方法全表扫描方法 (Table Scan)l对查询的基本表顺序扫描，逐一检查每个元组是否满足对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件

10、的元组作为结果输出选择条件，把满足条件的元组作为结果输出 l适合小表，不适合大表适合小表，不适合大表（2）索引扫描方法）索引扫描方法 (Index Scan)l适合于选择条件中的属性上有索引适合于选择条件中的属性上有索引(例如例如B+树索引或树索引或Hash索引索引) l通过索引先找到满足条件的元组主码或元组指针，再通通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组过元组指针直接在查询的基本表中找到元组 An Introduction to Database System选择操作的实现（续）选择操作的实现（续） v例例9.1 SELECT * FROM S

11、tudent WHERE 考虑考虑的几种情况：的几种情况： C1：无条件；：无条件； C2：Sno201215121； C3：Sage20； C4：SdeptCS AND Sage20； An Introduction to Database System选择操作的实现（续）选择操作的实现（续） v全表扫描算法全表扫描算法n假设可以使用的内存为假设可以使用的内存为M块，全表扫描算法思想：块，全表扫描算法思想：按照物理次序读按照物理次序读Student的的M块到内存块到内存检查内存的每个元组检查内存的每个元组t，如果满足选择条件，则输出，如果满足选择条件，则输出t如果如果student还有其他块

12、未被处理，重复和还有其他块未被处理，重复和An Introduction to Database System选择操作的实现（续）选择操作的实现（续）v索引扫描算法索引扫描算法v例例9.1-C2 SELECT * FROM Student WHERE Sno=201215121n假设假设Sno上有索引上有索引(或或Sno是散列码是散列码)n算法：算法：l使用索引使用索引(或散列或散列)得到得到Sno为为201215121 元组的指针元组的指针l通过元组指针在通过元组指针在Student表中检索到该学生表中检索到该学生An Introduction to Database System选择操作的

13、实现（续）选择操作的实现（续）v例例9.1-C3 SELECT * FROM Student WHERE Sage20n假设假设Sage 上有上有B+树索引树索引n算法：算法：l使用使用B+树索引找到树索引找到Sage=20的索引项，以此为入口点在的索引项，以此为入口点在B+树的顺序集上得到树的顺序集上得到Sage20的所有元组指针的所有元组指针l通过这些元组指针到通过这些元组指针到student表中检索到所有年龄大于表中检索到所有年龄大于20的学生。的学生。 An Introduction to Database System选择操作的实现（续）选择操作的实现（续）v例例9.1-C4 SEL

14、ECT * FROM Student WHERE Sdept=CS AND Sage20;n假设假设Sdept和和Sage上都有索引上都有索引n算法一：分别用算法一：分别用Index Scan找到找到SdeptCS的一组元组的一组元组指针和指针和Sage20的另一组元组指针的另一组元组指针l求这两组指针的交集求这两组指针的交集l到到Student表中检索表中检索l得到计算机系年龄大于得到计算机系年龄大于20的学生的学生An Introduction to Database System选择操作的实现（续）选择操作的实现（续）n算法二：找到算法二：找到Sdept=CS的一组元组指针，的一组元组指

15、针，l通过这些元组指针到通过这些元组指针到Student表中检索表中检索l并对得到的元组检查另一些选择条件并对得到的元组检查另一些选择条件(如如Sage20)是否满足是否满足l把满足条件的元组作为结果输出。把满足条件的元组作为结果输出。 An Introduction to Database System2.连接操作的实现连接操作的实现 v连接操作是查询处理中最耗时的操作之一连接操作是查询处理中最耗时的操作之一 v本节只讨论等值连接本节只讨论等值连接(或自然连接或自然连接)最常用的实现最常用的实现算法算法 v例例9.2 SELECT * FROM Student, SC WHERE Stude

16、nt.Sno=SC.Sno; An Introduction to Database System连接操作的实现（续）连接操作的实现（续）（1）嵌套循环算法）嵌套循环算法(nested loop join) （2）排序）排序-合并算法合并算法(sort-merge join 或或merge join)（3）索引连接）索引连接(index join)算法算法 （4）Hash Join算法算法 An Introduction to Database System连接操作的实现（续）连接操作的实现（续）（1）嵌套循环算法）嵌套循环算法(nested loop join)n对外层循环对外层循环(Stu

17、dent表表)的每一个元组的每一个元组(s)，检索内层循，检索内层循环环(SC表表)中的每一个元组中的每一个元组(sc)n检查这两个元组在连接属性检查这两个元组在连接属性(Sno)上是否相等上是否相等n如果满足连接条件，则串接后作为结果输出，直到外如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。层循环表中的元组处理完为止。v参见爱课程网参见爱课程网9.1节动画节动画连接操作的实现连接操作的实现(1)-嵌嵌套循环套循环An Introduction to Database System连接操作的实现（续）连接操作的实现（续）（2）排序）排序-合并算法合并算法(sort-

18、merge join 或或merge join) n如果连接的表没有排好序，先对如果连接的表没有排好序，先对Student表和表和SC表按表按连接属性连接属性Sno排序排序 n取取Student表中第一个表中第一个Sno，依次扫描，依次扫描SC表中具有相表中具有相同同Sno的元组的元组 n当扫描到当扫描到Sno不相同的第一个不相同的第一个SC元组时，返回元组时，返回Student表扫描它的下一个元组，再扫描表扫描它的下一个元组，再扫描SC表中具有表中具有相同相同Sno的元组，把它们连接起来的元组，把它们连接起来 n重复上述步骤直到重复上述步骤直到Student 表扫描完表扫描完An Intro

19、duction to Database System连接操作的实现（续）连接操作的实现（续）201215121 201215122 201215123 201215125 .201215121 1 92201215121 2 85201215121 3 88201215122 2 90201215122 3 80.图图9.2 排序排序-合并连接方法示意图合并连接方法示意图An Introduction to Database System连接操作的实现（续）连接操作的实现（续）vStudent表和表和SC表都只要扫描一遍表都只要扫描一遍v如果两个表原来无序，执行时间要加上对两个表如果两个表原来

20、无序，执行时间要加上对两个表的排序时间的排序时间v对于大表，先排序后使用排序对于大表，先排序后使用排序-合并连接算法执行合并连接算法执行连接，总的时间一般仍会减少连接，总的时间一般仍会减少 v参见爱课程网参见爱课程网9.1节动画节动画连接操作的实现（连接操作的实现（2）-排序合并排序合并 An Introduction to Database System连接操作的实现（续）连接操作的实现（续）（3）索引连接）索引连接(index join)算法算法n步骤：步骤： 在在SC表上已经建立属性表上已经建立属性Sno的索引。的索引。 对对Student中每一个元组，由中每一个元组，由Sno值通过值通

21、过SC的索引查的索引查找相应的找相应的SC元组。元组。 把这些把这些SC元组和元组和Student元组连接起来元组连接起来 循环执行，直到循环执行，直到Student表中的元组处理完为止表中的元组处理完为止 v参见爱课程网参见爱课程网9.1节动画节动画连接操作的实现连接操作的实现(4)- 索引连接索引连接 An Introduction to Database System连接操作的实现（续）连接操作的实现（续）（4）Hash Join算法算法 n 把连接属性作为把连接属性作为hash码，用同一个码，用同一个hash函数把函数把Student表和表和SC表表中的元组散列到中的元组散列到hash

22、表中。表中。n 划分阶段划分阶段(building phase, 也称为也称为partitioning phase)l对包含较少元组的表对包含较少元组的表(如如Student表表)进行一遍处理进行一遍处理l把它的元组按把它的元组按hash函数分散到函数分散到hash表的桶中表的桶中n 试探阶段试探阶段(probing phase,也称为连接阶段也称为连接阶段join phase) l对另一个表对另一个表(SC表表)进行一遍处理进行一遍处理l把把SC表的元组也按同一个表的元组也按同一个hash函数（函数（hash码是连接属性）进码是连接属性）进行散列行散列l把把SC元组与桶中来自元组与桶中来自S

23、tudent表并与之相匹配的元组连接起来表并与之相匹配的元组连接起来An Introduction to Database System连接操作的实现（续）连接操作的实现（续）v上面上面hash join算法前提：假设两个表中较小的表算法前提：假设两个表中较小的表在第一阶段后可以完全放入内存的在第一阶段后可以完全放入内存的hash桶中桶中 v参见爱课程网参见爱课程网9.1节动画节动画连接操作的实现连接操作的实现(3)-散散列连接列连接 An Introduction to Database System第九章第九章 关系关系查询处理和查询查询处理和查询优化优化9.1 关系数据库系统的查询处理关

24、系数据库系统的查询处理 9.2 关系数据库系统的查询优化关系数据库系统的查询优化 9.3 代数优化代数优化 9.4 物理优化物理优化 *9.5 查询计划的执行查询计划的执行9.6 小小 结结 An Introduction to Database System9.2 关系数据库系统的查询优化关系数据库系统的查询优化v查询优化在关系数据库系统中有着非常重要的地位查询优化在关系数据库系统中有着非常重要的地位 v关系查询优化是影响关系数据库管理系统性能的关关系查询优化是影响关系数据库管理系统性能的关键因素键因素 v由于关系表达式的语义级别很高，使关系系统可以由于关系表达式的语义级别很高，使关系系统可

25、以从关系表达式中分析查询语义，提供了执行查询优从关系表达式中分析查询语义，提供了执行查询优化的可能性化的可能性 An Introduction to Database System9.2 关系数据库系统的查询优化关系数据库系统的查询优化9.2.1查询优化概述查询优化概述9.2.2一个实例一个实例An Introduction to Database System9.2.1 查询优化概述查询优化概述v关系系统的查询优化关系系统的查询优化n是关系数据库管理系统实现的关键技术又是关系系统是关系数据库管理系统实现的关键技术又是关系系统的优点所在的优点所在n减轻了用户选择存取路径的负担减轻了用户选择存取

26、路径的负担 An Introduction to Database System查询优化概述（续）查询优化概述（续）v非关系系统非关系系统n用户使用过程化的语言表达查询要求，执行何种记录用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户来决定的级的操作，以及操作的序列是由用户来决定的 n用户必须了解存取路径，系统要提供用户选择存取路用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定径的手段，查询效率由用户的存取策略决定n如果用户做了不当的选择，系统是无法对此加以改进如果用户做了不当的选择，系统是无法对此加以改进的的An Introd

27、uction to Database System查询优化概述查询优化概述v查询优化的优点查询优化的优点n用户不必考虑如何最好地表达查询以获得较好的效率用户不必考虑如何最好地表达查询以获得较好的效率n系统可以比用户程序的系统可以比用户程序的“优化优化”做得更好做得更好 （1） 优化器可以从数据字典中获取许多统计信息，而用优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。户程序则难以获得这些信息。（2）如果数据库的物理统计信息改变了，系统可以自动）如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统对查询重新优化以选择相适应的执行计划

28、。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可中必须重写程序，而重写程序在实际应用中往往是不太可能的。能的。An Introduction to Database System查询优化概述（续）查询优化概述（续）（3）优化器可以考虑数百种不同的执行计划，程序员一）优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。般只能考虑有限的几种可能性。（4）优化器中包括了很多复杂的优化技术，这些优化技）优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些

29、优化技术。于使得所有人都拥有这些优化技术。An Introduction to Database System查询优化概述（续）查询优化概述（续）v关系数据库管理系统通过某种代价模型计算出各关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小种查询执行策略的执行代价，然后选取代价最小的执行方案的执行方案n集中式数据库集中式数据库l执行开销主要包括执行开销主要包括磁盘存取块数磁盘存取块数(I/O代价代价)处理机时间处理机时间(CPU代价代价)查询的内存开销查询的内存开销 lI/O代价是最主要的代价是最主要的 n分布式数据库分布式数据库l总代价总代价=I/O代价代价

30、+CPU代价代价+内存代价通信代价内存代价通信代价 An Introduction to Database System查询优化概述（续）查询优化概述（续）v查询优化的总目标查询优化的总目标n选择有效的策略选择有效的策略n求得给定关系表达式的值求得给定关系表达式的值n使得查询代价最小使得查询代价最小(实际上是较小实际上是较小) An Introduction to Database System9.2 关系数据库系统的查询优化关系数据库系统的查询优化9.2.1查询优化概述查询优化概述9.2.2一个实例一个实例An Introduction to Database System9.2.2 一个实

31、例一个实例v一个关系查询可以对应不同的执行方案，其效率一个关系查询可以对应不同的执行方案，其效率可能相差非常大。可能相差非常大。v例例9.3 求选修了求选修了2号课程的学生姓名。号课程的学生姓名。 用用SQL表达：表达： SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.Sno AND SC.Cno=2 n假定学生假定学生-课程数据库中有课程数据库中有1000个学生记录，个学生记录，10000个个选课记录选课记录n选修选修2号课程的选课记录为号课程的选课记录为50个个 An Introduction to Database Sys

32、tem一个一个实例实例（续）（续）v可以用多种等价的关系代数表达式来完成这一查询可以用多种等价的关系代数表达式来完成这一查询nQ1=Sname(Student.Sno=SC.SnoSC.Cno=2 (StudentSC)nQ2=Sname(SC.Cno=2 (Student SC)nQ3=Sname(Student SC.Cno=2(SC) An Introduction to Database System一个实例（续）一个实例（续）1.第一种情况第一种情况nQ1=Sname(Student.Sno=SC.SnoSC.Cno=2 (StudentSC)An Introduction to D

33、atabase System一个实例（续）一个实例（续）（1） 计算广义笛卡尔积计算广义笛卡尔积 v算法：算法：n在内存中尽可能多地装入某个表在内存中尽可能多地装入某个表(如如Student表表)的若干的若干块，留出一块存放另一个表块，留出一块存放另一个表(如如SC表表)的元组。的元组。n把把SC中的每个元组和中的每个元组和Student中每个元组连接，连接中每个元组连接，连接后的元组装满一块后就写到中间文件上后的元组装满一块后就写到中间文件上n从从SC中读入一块和内存中的中读入一块和内存中的Student元组连接，直到元组连接，直到SC表处理完。表处理完。n再读入若干块再读入若干块Stude

34、nt元组，读入一块元组，读入一块SC元组元组n重复上述处理过程，直到把重复上述处理过程，直到把Student表处理完表处理完 An Introduction to Database System一个实例（续）一个实例（续）v设一个块能装设一个块能装10个个Student元组或元组或100个个SC元组元组，在内存中存放，在内存中存放5块块Student元组和元组和1块块SC元组，元组，则读取总块数为则读取总块数为 =100+20100=2100块块n读读Student表表100块，读块，读SC表表20遍，每遍遍，每遍100块，则总块，则总计要读取计要读取2100数据块。数据块。n连接后的元组数为

35、连接后的元组数为103104=107。设每块能装。设每块能装10个元个元组，则写出组，则写出106 块。块。101000510100010010000An Introduction to Database System一个实例（续）一个实例（续）（2）作选择操作）作选择操作 n依次读入连接后的元组，按照选择条件选取满足要求依次读入连接后的元组，按照选择条件选取满足要求的记录的记录n假定内存处理时间忽略。读取中间文件花费的时间假定内存处理时间忽略。读取中间文件花费的时间(同同写中间文件一样写中间文件一样)需读入需读入106块。块。 n若满足条件的元组假设仅若满足条件的元组假设仅50个，均可放在内

36、存。个，均可放在内存。 An Introduction to Database System一个实例（续）一个实例（续）（3）作投影操作）作投影操作 n把第（把第（2）步的结果在）步的结果在Sname上作投影输出，得到最终上作投影输出，得到最终结果结果 v第一种情况下执行查询的总读写数据块第一种情况下执行查询的总读写数据块=2100+106 +106An Introduction to Database System一个实例（续）一个实例（续）2.第二种情况第二种情况 Q2=Sname(Sc.Cno=2 (Student SC)（1）计算自然连接）计算自然连接 l执行自然连接，读取执行自然连接

37、，读取Student和和SC表的策略不变，总的读表的策略不变，总的读取块数仍为取块数仍为2100块块l自然连接的结果比第一种情况大大减少，为自然连接的结果比第一种情况大大减少，为104个元组个元组l写出数据块写出数据块= 103 块块 An Introduction to Database System一个实例（续）一个实例（续）2.第二种情况（续）第二种情况（续）（2）读取中间文件块，执行选择运算，读取的数据块）读取中间文件块，执行选择运算，读取的数据块= 103 块块（3）把第）把第2步结果投影输出。步结果投影输出。n第二种情况下执行查询的总读写数据块第二种情况下执行查询的总读写数据块=2

38、100+ 103 +103n其执行代价大约是第一种情况的其执行代价大约是第一种情况的488分之一分之一 An Introduction to Database System一个实例（续）一个实例（续）3.第三种情况第三种情况Q3=Sname(Student SC.Cno=2(SC)（1）先对）先对SC表作选择运算，只需读一遍表作选择运算，只需读一遍SC表，存取表，存取 100块，因为满足条件的元组仅块，因为满足条件的元组仅50个，不必使用中个，不必使用中 间文件。间文件。（2）读取）读取Student表，把读入的表，把读入的Student元组和内存中元组和内存中 的的SC元组作连接。也只需读一

39、遍元组作连接。也只需读一遍Student表共表共100 块。块。（3）把连接结果投影输出）把连接结果投影输出 An Introduction to Database System一个实例（续）一个实例（续）3.第三种情况（续）第三种情况（续）n第三种情况总的读写数据块第三种情况总的读写数据块=100+100n其执行代价大约是第一种情况的万分之一，是第二种其执行代价大约是第一种情况的万分之一，是第二种情况的情况的20分之一分之一An Introduction to Database System一个实例（续）一个实例（续）v假如假如SC表的表的Cno字段上有索引字段上有索引n第一步就不必读取所有

40、的第一步就不必读取所有的SC元组而只需读取元组而只需读取Cno=2的那些元组的那些元组(50个个)n存取的索引块和存取的索引块和SC中满足条件的数据块大约总共中满足条件的数据块大约总共34块块v若若Student表在表在Sno上也有索引上也有索引n不必读取所有的不必读取所有的Student元组元组n因为满足条件的因为满足条件的SC记录仅记录仅50个，涉及最多个，涉及最多50个个Student记录记录n读取读取Student表的块数也可大大减少表的块数也可大大减少 An Introduction to Database System一个实例（续）一个实例（续）v把代数表达式把代数表达式Q1变换为

41、变换为Q2、 Q3Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)Q2=Sname(Sc.Cno=2 (Student SC)Q3=Sname(Student SC.Cno=2(SC)n 有选择和连接操作时，先做选择操作，这样参加连接的元组有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是就可以大大减少，这是代数优化代数优化 An Introduction to Database System实例实例: 小结小结v在在Q3中中nSC表的选择操作算法有全表扫描或索引扫描，经过初步表的选择操作算法有全表扫描或索引扫描，经过初步估算

42、，索引扫描方法较优。估算，索引扫描方法较优。n对于对于Student和和SC表的连接，利用表的连接，利用Student表上的索引，表上的索引，采用索引连接代价也较小，这就是采用索引连接代价也较小，这就是物理优化物理优化。An Introduction to Database System第九章第九章 关系关系查询处理和查询查询处理和查询优化优化9.1 关系数据库系统的查询处理关系数据库系统的查询处理 9.2 关系数据库系统的查询优化关系数据库系统的查询优化 9.3 代数优化代数优化 9.4 物理优化物理优化 *9.5 查询计划的执行查询计划的执行9.6 小小 结结 An Introductio

43、n to Database System9.3 代代 数数 优优 化化9.3.1 关系代数表达式等价变换规则关系代数表达式等价变换规则 9.3.2 查询树的启发式优化查询树的启发式优化 An Introduction to Database System9.3.1 关系代数表达式等价变换规则关系代数表达式等价变换规则 v代数优化策略：通过对关系代数表达式的等价变代数优化策略：通过对关系代数表达式的等价变换来提高查询效率换来提高查询效率 v关系代数表达式的等价：指用相同的关系代替两关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的个表达式中相应的关系所得到的结果是

44、相同的v两个关系表达式两个关系表达式E1和和E2是等价的，可记为是等价的，可记为E1E2 An Introduction to Database System*关系代数表达式等价变换规则（续）关系代数表达式等价变换规则（续）v常用的等价变换规则：常用的等价变换规则：1.连接、笛卡尔积交换律连接、笛卡尔积交换律 设设E1和和E2是关系代数表达式，是关系代数表达式，F是连接运算的条件，则有是连接运算的条件，则有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12.连接、笛卡尔积的结合律连接、笛卡尔积的结合律 设设E1，E2，E3是关系代数表达式，是关系代数表达式，F1和和F2是连接

45、运算的条件是连接运算的条件 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) F1FF2F2F2F An Introduction to Database System*关系代数表达式等价变换规则（续）关系代数表达式等价变换规则（续）3.投影的串接定律投影的串接定律 ( (E) (E)n E是关系代数表达式是关系代数表达式n Ai(i=1，2，n)，Bj(j=1，2，m)是属性名是属性名n A1，A2，An构成构成B1，B2，Bm的子集的子集4.选择的串接定律选择的串接定律 ( (E ) (E)n E是关系代数表达式，

46、是关系代数表达式，F1、F2是选择条件是选择条件n 选择的串接律说明选择条件可以合并选择的串接律说明选择条件可以合并,这样一次就可检查全这样一次就可检查全部条件部条件nAAA,21mBBB,21nAAA,211F2F21FF An Introduction to Database System*关系代数表达式等价变换规则（续）关系代数表达式等价变换规则（续）5.选择与投影操作的交换律选择与投影操作的交换律 F( (E) (F(E)n 选择条件选择条件F只涉及属性只涉及属性A1，An。n 若若F中有不属于中有不属于A1，An的属性的属性B1，Bm有更一般规有更一般规则：则： (F(E ) (F

47、( (E)nAAA,21nAAA,21nAAA,21nAAA,21mnBBBAAA,2121An Introduction to Database System*关系代数表达式等价变换规则（续）关系代数表达式等价变换规则（续）6. 选择与笛卡尔积的交换律选择与笛卡尔积的交换律n如果如果F中涉及的属性都是中涉及的属性都是E1中的属性，则中的属性，则 F(E1E2)F(E1)E2n如果如果F=F1F2，并且，并且F1只涉及只涉及E1中的属性，中的属性，F2只涉及只涉及E2中的属性，则由上面的等价变换规则中的属性，则由上面的等价变换规则1，4，6可推出：可推出： F(E1E2) (E1) (E2)n

48、若若F1只涉及只涉及E1中的属性，中的属性，F2涉及涉及E1和和E2两者的属性，则两者的属性，则仍有仍有 F(E1E2) ( (E1)E2) 它使部分选择在笛卡尔积前先做。它使部分选择在笛卡尔积前先做。 1F2F2F1FAn Introduction to Database System*关系代数表达式等价变换规则（续）关系代数表达式等价变换规则（续）7. 选择与并的分配律选择与并的分配律 设设E=E1E2，E1，E2有相同的属性名，则有相同的属性名，则 F(E1E2)F(E1)F(E2)8. 选择与差运算的分配律选择与差运算的分配律 若若E1与与E2有相同的属性名，则有相同的属性名，则 F(

49、E1-E2)F(E1)-F(E2)9. 选择对自然连接的分配律选择对自然连接的分配律 F(E1 E2)F(E1) F(E2) F只涉及只涉及E1与与E2的公共属性的公共属性 An Introduction to Database System*关系代数表达式等价变换规则（续）关系代数表达式等价变换规则（续）10. 投影与笛卡尔积的分配律投影与笛卡尔积的分配律 设设E1和和E2是两个关系表达式，是两个关系表达式，A1，An是是E1的属性，的属性， B1，Bm是是E2的属性，则的属性，则 (E1E2) (E1) (E2)11. 投影与并的分配律投影与并的分配律 设设E1和和E2有相同的属性名，则有

50、相同的属性名，则 (E1E2) (E1) (E2)mnBBBAAA,2121nAAA,21mBBB,21nAAA,21nAAA,21nAAA,21An Introduction to Database System9.3 代代 数数 优优 化化9.3.1 关系代数表达式等价变换规则关系代数表达式等价变换规则 9.3.2 查询树的启发式优化查询树的启发式优化 An Introduction to Database System9.3.2 查询树的启发式优化查询树的启发式优化 v典型的启发式规则典型的启发式规则（1）选择运算应尽可能先做）选择运算应尽可能先做 在优化策略中这是最重要、最基本的一条。

51、在优化策略中这是最重要、最基本的一条。（2）把投影运算和选择运算同时进行）把投影运算和选择运算同时进行如有若干投影和选择运算，并且它们都对同一个关系如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。算以避免重复扫描关系。An Introduction to Database System查询树的启发式优化（续）查询树的启发式优化（续）（3） 把投影同其前或其后的双目运算结合起来，没有把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。必要为了去掉某些字段而扫描

52、一遍关系。（4） 把某些选择同在它前面要执行的笛卡尔积结合起把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。同样关系上的笛卡尔积省很多时间。 An Introduction to Database System查询树的启发式优化（续）查询树的启发式优化（续）（5） 找出公共子表达式找出公共子表达式l如果这种重复出现的子表达式的结果不是很大的关系如果这种重复出现的子表达式的结果不是很大的关系l并且从外存中读入这个关系比计算该子表达式的时间少并且从外存中读入这个关系比计算该子表达式

53、的时间少得多得多l则先计算一次公共子表达式并把结果写入中间文件是合则先计算一次公共子表达式并把结果写入中间文件是合算的。算的。l当查询的是视图时，定义视图的表达式就是公共子表达当查询的是视图时，定义视图的表达式就是公共子表达式的情况式的情况An Introduction to Database System*查询树的启发式优化（续）查询树的启发式优化（续）v遵循这些启发式规则，应用遵循这些启发式规则，应用9.3.1的等价变换公式的等价变换公式来优化关系表达式的算法。来优化关系表达式的算法。算法：关系表达式的优化算法：关系表达式的优化输入输入：一个关系表达式的查询树：一个关系表达式的查询树输出输

54、出：优化的查询树：优化的查询树方法：方法：（1）利用等价变换规则）利用等价变换规则4把形如把形如F1F2Fn(E)变换为变换为 F1(F2(Fn(E)。（2）对每一个选择，利用等价变换规则）对每一个选择，利用等价变换规则49尽可能把它尽可能把它 移到树的叶端。移到树的叶端。规则规则4： 合并或分解选择运算合并或分解选择运算规则规则5-9： 选择运算与其他运算交换选择运算与其他运算交换规则规则4: 选择的串接定律选择的串接定律 ( (E) (E)1F2F21FF An Introduction to Database System*查询树的启发式优化（续）查询树的启发式优化（续）（3）对每一个投

55、影利用等价变换规则）对每一个投影利用等价变换规则3，5，10，11中的中的一般形式尽可能把它移向树的叶端。一般形式尽可能把它移向树的叶端。n注意：注意： l等价变换规则等价变换规则3使一些投影消失或使一些投影出现使一些投影消失或使一些投影出现l规则规则5把一个投影分裂为两个，其中一个有可能被移向树把一个投影分裂为两个，其中一个有可能被移向树的叶端的叶端 （4）利用等价变换规则）利用等价变换规则35，把选择和投影的串接合并，把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影，使多个成单个选择、单个投影或一个选择后跟一个投影，使多个选择或投影能同时执行，或在一次扫描中全部完成选择或投

56、影能同时执行，或在一次扫描中全部完成规则规则3： 合并或分解投影运算合并或分解投影运算规则规则5,10,11：投影运算与其他运算交换：投影运算与其他运算交换规则规则3：合并或分解投影运算：合并或分解投影运算规则规则4：合并或分解选择运算：合并或分解选择运算规则规则5：投影运算与选择运算交换：投影运算与选择运算交换An Introduction to Database System查询树的启发式优化（续）查询树的启发式优化（续） （5）把上述得到的语法树的内节点分组。）把上述得到的语法树的内节点分组。n每一双目运算每一双目运算(， ，-)和它所有的直接祖先为一和它所有的直接祖先为一组组(这些直接

57、祖先是这些直接祖先是(，运算运算)。n如果其后代直到叶子全是单目运算，则也将它们并入如果其后代直到叶子全是单目运算，则也将它们并入该组该组n但当双目运算是笛卡尔积但当双目运算是笛卡尔积()，而且后面不是与它组成，而且后面不是与它组成等值连接的选择时，则不能把选择与这个双目运算组等值连接的选择时，则不能把选择与这个双目运算组成同一组成同一组 An Introduction to Database System查询树的启发式优化（续）查询树的启发式优化（续）v例例9.4下面给出下面给出例例9.3中中 SQL语句的代数优化示例语句的代数优化示例 （1）把）把SQL语句转换成查询树，如下图所示语句转换

58、成查询树，如下图所示图图9.3 查询树图查询树图An Introduction to Database System查询树的启发式优化（续）查询树的启发式优化（续）为了使用关系代数表达式的优化法，假设内部表示是关为了使用关系代数表达式的优化法，假设内部表示是关系代数语法树，则上面的查询树如图系代数语法树，则上面的查询树如图9.4所示。所示。 图图9.4 关系代数语法树图关系代数语法树图 An Introduction to Database System查询树的启发式优化（续）查询树的启发式优化（续）（2 ）对查询树进行优化）对查询树进行优化n利用规则利用规则4、6把选择把选择SC.Cno=2

59、移到叶端，图移到叶端，图9.4查询树查询树便转换成下图优化的查询树。这就是便转换成下图优化的查询树。这就是9.2.2节中节中Q3的查的查询树表示。询树表示。v参见爱课程网参见爱课程网9.3节动画节动画查询树的启发式优化查询树的启发式优化 An Introduction to Database System第九章第九章 关系关系查询处理和查询查询处理和查询优化优化9.1 关系数据库系统的查询处理关系数据库系统的查询处理 9.2 关系数据库系统的查询优化关系数据库系统的查询优化 9.3 代数优化代数优化 9.4 物理优化物理优化 *9.5 查询计划的执行查询计划的执行9.6 小小 结结 An In

60、troduction to Database System9.4 物理优化物理优化v代数优化改变查询语句中操作的次序和组合，不代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径涉及底层的存取路径v对于一个查询语句有许多存取方案，它们的执行对于一个查询语句有许多存取方案，它们的执行效率不同，效率不同， 仅仅进行代数优化是不够的仅仅进行代数优化是不够的 v物理优化就是要物理优化就是要选择高效合理的操作算法或存取选择高效合理的操作算法或存取路径路径，求得优化的查询计划，求得优化的查询计划 An Introduction to Database System物理优化（续）物理优化（续）v物理