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

AnIntroductiontoDatabaseSystem数据库系统概论AnIntroductiontoDatabaseSystem中国人民大学信息学院第九章关系查询处理和查询优化AnIntroductiontoDatabaseSystem第三篇系统篇讨论数据库管理系统中查询处理和事务管理的基本概念和基础知识第9章关系查询处理和查询优化第10章数据库恢复技术第11章并发控制第12章数据库管理系统AnIntroductiontoDatabaseSystem第九章关系查询处理和查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化*9.5查询计划的执行9.6小结AnIntroductiontoDatabaseSystem关系查询处理和查询优化（续）本章内容：关系数据库管理系统的查询处理步骤查询优化的概念基本方法和技术查询优化分类：代数优化：指关系代数表达式的优化物理优化：指存取路径和底层操作算法的选择AnIntroductiontoDatabaseSystem9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例AnIntroductiontoDatabaseSystem9.1.1查询处理步骤关系数据库管理系统查询处理阶段：1.查询分析2.查询检查3.查询优化4.查询执行AnIntroductiontoDatabaseSystem查询处理步骤（续）查询计划的执行代码代数优化物理优化等查询语句词法分析语法分析语义分析符号名转换安全性检查完整性初步检查代码生成查询执行计划查询树(querytree)查询分析查询检查查询优化查询执行数据库数据字典AnIntroductiontoDatabaseSystem1.查询分析查询分析的任务：对查询语句进行扫描、词法分析和语法分析词法分析：从查询语句中识别出正确的语言符号语法分析：进行语法检查AnIntroductiontoDatabaseSystem2.查询检查查询检查的任务合法权检查视图转换安全性检查完整性初步检查根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作AnIntroductiontoDatabaseSystem2.查询检查根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查检查通过后把SQL查询语句转换成内部表示，即等价的关系代数表达式。关系数据库管理系统一般都用查询树，也称为语法分析树来表示扩展的关系代数表达式。AnIntroductiontoDatabaseSystem3.查询优化查询优化：选择一个高效执行的查询处理策略查询优化分类代数优化/逻辑优化：指关系代数表达式的优化物理优化：指存取路径和底层操作算法的选择查询优化的选择依据基于规则(rulebased)基于代价(costbased)基于语义(semanticbased)AnIntroductiontoDatabaseSystem4.查询执行依据优化器得到的执行策略生成查询执行计划代码生成器(codegenerator)生成执行查询计划的代码两种执行方法自顶向下自底向上AnIntroductiontoDatabaseSystem9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例1.选择操作的实现2.连接操作的实现AnIntroductiontoDatabaseSystem1.选择操作的实现选择操作典型实现方法：（1）全表扫描方法(TableScan)对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出适合小表，不适合大表（2）索引扫描方法(IndexScan)适合于选择条件中的属性上有索引(例如B+树索引或Hash索引)通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组AnIntroductiontoDatabaseSystem选择操作的实现（续）[例9.1]SELECT*FROMStudentWHERE条件表达式考虑条件表达式的几种情况：C1：无条件；C2：Sno＝'201215121'；C3：Sage20；C4：Sdept＝'CS'ANDSage20；AnIntroductiontoDatabaseSystem选择操作的实现（续）全表扫描算法假设可以使用的内存为M块，全表扫描算法思想：①按照物理次序读Student的M块到内存②检查内存的每个元组t，如果满足选择条件，则输出t③如果student还有其他块未被处理，重复①和②AnIntroductiontoDatabaseSystem选择操作的实现（续）索引扫描算法[例9.1-C2]SELECT*FROMStudentWHERESno='201215121'假设Sno上有索引(或Sno是散列码)算法：使用索引(或散列)得到Sno为‘201215121’元组的指针通过元组指针在Student表中检索到该学生AnIntroductiontoDatabaseSystem选择操作的实现（续）[例9.1-C3]SELECT*FROMStudentWHERESage20假设Sage上有B+树索引算法：使用B+树索引找到Sage=20的索引项，以此为入口点在B+树的顺序集上得到Sage20的所有元组指针通过这些元组指针到student表中检索到所有年龄大于20的学生。AnIntroductiontoDatabaseSystem选择操作的实现（续）[例9.1-C4]SELECT*FROMStudentWHERESdept='CS'ANDSage20;假设Sdept和Sage上都有索引算法一：分别用IndexScan找到Sdept＝’CS’的一组元组指针和Sage20的另一组元组指针求这两组指针的交集到Student表中检索得到计算机系年龄大于20的学生AnIntroductiontoDatabaseSystem选择操作的实现（续）算法二：找到Sdept=’CS’的一组元组指针，通过这些元组指针到Student表中检索并对得到的元组检查另一些选择条件(如Sage20)是否满足把满足条件的元组作为结果输出。AnIntroductiontoDatabaseSystem2.连接操作的实现连接操作是查询处理中最耗时的操作之一本节只讨论等值连接(或自然连接)最常用的实现算法[例9.2]SELECT*FROMStudent,SCWHEREStudent.Sno=SC.Sno;AnIntroductiontoDatabaseSystem连接操作的实现（续）（1）嵌套循环算法(nestedloopjoin)（2）排序-合并算法(sort-mergejoin或mergejoin)（3）索引连接(indexjoin)算法（4）HashJoin算法AnIntroductiontoDatabaseSystem连接操作的实现（续）（1）嵌套循环算法(nestedloopjoin)对外层循环(Student表)的每一个元组(s)，检索内层循环(SC表)中的每一个元组(sc)检查这两个元组在连接属性(Sno)上是否相等如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。参见爱课程网9.1节动画《连接操作的实现(1)--嵌套循环》AnIntroductiontoDatabaseSystem连接操作的实现（续）（2）排序-合并算法(sort-mergejoin或mergejoin)如果连接的表没有排好序，先对Student表和SC表按连接属性Sno排序取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来重复上述步骤直到Student表扫描完AnIntroductiontoDatabaseSystem连接操作的实现（续）201215121…201215122…201215123…201215125…...201215121192201215121285201215121388201215122290201215122380...图9.2排序-合并连接方法示意图AnIntroductiontoDatabaseSystem连接操作的实现（续）Student表和SC表都只要扫描一遍如果两个表原来无序，执行时间要加上对两个表的排序时间对于大表，先排序后使用排序-合并连接算法执行连接，总的时间一般仍会减少参见爱课程网9.1节动画《连接操作的实现（2）--排序合并》AnIntroductiontoDatabaseSystem连接操作的实现（续）（3）索引连接(indexjoin)算法步骤：①在SC表上已经建立属性Sno的索引。②对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组。③把这些SC元组和Student元组连接起来循环执行②③，直到Student表中的元组处理完为止参见爱课程网9.1节动画《连接操作的实现(4)--索引连接》AnIntroductiontoDatabaseSystem连接操作的实现（续）（4）HashJoin算法把连接属性作为hash码，用同一个hash函数把Student表和SC表中的元组散列到hash表中。划分阶段(buildingphase,也称为partitioningphase)对包含较少元组的表(如Student表)进行一遍处理把它的元组按hash函数分散到hash表的桶中试探阶段(probingphase,也称为连接阶段joinphase)对另一个表(SC表)进行一遍处理把SC表的元组也按同一个hash函数（hash码是连接属性）进行散列把SC元组与桶中来自Student表并与之相匹配的元组连接起来AnIntroductiontoDatabaseSystem连接操作的实现（续）上面hashjoin算法前提：假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中参见爱课程网9.1节动画《连接操作的实现(3)--散列连接》AnIntroductiontoDatabaseSystem第九章关系查询处理和查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化*9.5查询计划的执行9.6小结AnIntroductiontoDatabaseSystem9.2关系数据库系统的查询优化查询优化在关系数据库系统中有着非常重要的地位关系查询优化是影响关系数据库管理系统性能的关键因素由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性AnIntroductiontoDatabaseSystem9.2关系数据库系统的查询优化9.2.1查询优化概述9.2.2一个实例AnIntroductiontoDatabaseSystem9.2.1查询优化概述关系系统的查询优化是关系数据库管理系统实现的关键技术又是关系系统的优点所在减轻了用户选择存取路径的负担AnIntroductiontoDatabaseSystem查询优化概述（续）非关系系统用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户来决定的用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定如果用户做了不当的选择，系统是无法对此加以改进的AnIntroductiontoDatabaseSystem查询优化概述