关系查询处理和查询优化.ppt

第九章第九章 关系关系查询处理和理和查询优化化1-查询处查询处理与理与优优化化 n如何以有效的方式如何以有效的方式处处理用理用户查询户查询是是RDBMS有效有效实现实现的关的关键问题键问题之一之一n数据数据库库的更新运算要么是的更新运算要么是简单简单的（如插入一个元的（如插入一个元组组），要么与一个），要么与一个复复杂杂的更新条件相关的更新条件相关联联（如（如删删除除满满足某些条件的元足某些条件的元组组）n复复杂杂的更新首先需要找到要更新的元的更新首先需要找到要更新的元组组，然后才能，然后才能进进行更新。因此，行更新。因此，只有能只有能够够有效地有效地处处理理查询查询，才能有效地，才能有效地实现实现更新更新n查询处查询处理的中心任理的中心任务务是把使用是把使用诸诸如如SQL这样这样的的说说明性明性语语言表达的用言表达的用户查户查询转换询转换成一系列能成一系列能够够在物理文件上在物理文件上执执行的操作，并行的操作，并执执行行这这些操作得到些操作得到查查询结询结果果n查询优查询优化是化是查询处查询处理的关理的关键键步步骤骤，它从众多的，它从众多的查询执查询执行方案中行方案中选择选择最有最有效的效的执执行方案行方案 2-关系关系查询处理和理和查询优化化n9.1 关系数据关系数据库系系统的的查询处理理n9.2 关系数据关系数据库系系统的的查询优化化n9.3 代数代数优化化n9.4 物理物理优化化n9.5 小小结3-9.1 关系数据关系数据库系系统的的查询处理理n9.1.1 查询处理步理步骤n9.1.2 实现查询操作的算法示例操作的算法示例4-9.1.1 查询处理步理步骤nRDBMS查询处理理过程程n查询分析分析n查询检查n查询优化化n查询执行行图9.1 查询处理步理步骤5-9.1.1 查询处理步理步骤（续）n查询分析分析：进进行行词词法分析、法分析、语语法分析和法分析和语义语义分析分析 n词词法分析法分析n从从查询语查询语句中句中识别识别出出语语言符号，如言符号，如SQL的保留字、关系名、属性的保留字、关系名、属性名和各种运算符等其他符号名和各种运算符等其他符号n语语法分析法分析n检查检查用用户查询语户查询语句的句的语语法格式，确保法格式，确保查询语查询语句句语语法上的正确性法上的正确性n语义语义分析分析n可以与可以与语语法分析同法分析同时进时进行，将行，将查询转换查询转换成更适合成更适合进进一步一步处处理的内理的内部表示部表示 6-9.1.1 查询处理步理步骤（续）n查询检查n根据数据字典根据数据字典对合法的合法的查询语句句进行行语义检查n根据数据字典中的用根据数据字典中的用户权限和完整性限和完整性约束定束定义对用用户的存取的存取权限限进行行检查n检查通通过后把后把SQL查询语句句转换成等价的关系代数成等价的关系代数nRDBMS一般都用一般都用查询树，也称，也称语法分析法分析树，来表示，来表示扩展的关系代数展的关系代数表达式表达式n把数据把数据库对象的外部名称象的外部名称转换成内部表示成内部表示7-9.1.1 查询处理步理步骤（续）n查询检查查询树n例例9.1 找出提供了找出提供了P001号零件的供号零件的供应应商名称商名称SELECT SnameFROM Suppliers,SPWHERE Suppliers.Sno=SP.Sno AND Pno=P001;n转换转换成成下下图图9.2所示的所示的语语法法树树，或者，或者转换转换成如下关系代数表达式：成如下关系代数表达式：Q1：Sname(Suppliers.Sno=SP.Sno Pno=P001(SuppliersSP)Suppliers.Sno=SP.Sno Pno=P001 SuppliersSP Sname图图9.2 一棵一棵语语法分析法分析树树8-9.1.1 查询处理步理步骤（续）n查询优化化n一个一个给给定的定的查询查询有多种可能的有多种可能的执执行策略行策略n例如，例例如，例9.1的的查询查询也可以用如下关系代数表达式也可以用如下关系代数表达式计计算：算：Q2：Sname(Pno=P001(Suppliers SP)Q3：Sname(Suppliers Pno=P001(SP)n每个基本运算也可以有多种不同的每个基本运算也可以有多种不同的实现实现算法算法n一个一个查询执查询执行行计计划包括划包括计计算算查询查询的关系代数表达式和其中每个基本运算的关系代数表达式和其中每个基本运算的的实现实现算法算法n查询优查询优化就是从多种可能的化就是从多种可能的查询执查询执行方案中行方案中选择选择一种最有效一种最有效执执行的行的查询查询执执行行计计划的划的过过程程n对对于相同的于相同的查询查询，不同的，不同的查询执查询执行行计计划的划的时间时间开开销销可能相差几个数量可能相差几个数量级级n例如，使用例如，使用Q1计计算例算例9.1的的查询查询的的I/O开开销销大大约约是使用是使用Q3的的2000倍倍 9-9.1.1 查询处理步理步骤（续）n按照按照优化化层次分次分为代数代数优化和物理化和物理优化化n代数代数优优化化vs物理物理优优化化n代数代数优优化：找到一个与化：找到一个与给给定的定的查询查询表达式等价、但表达式等价、但执执行起来更加有行起来更加有效的关系代数表达式效的关系代数表达式n物理物理优优化：化：为为关系代数表达式关系代数表达式选择选择一个一个详细详细的策略，包括的策略，包括为为特定的特定的操作操作选择选择可用的算法可用的算法（底（底层操作算法）操作算法），选择选择可用的索引可用的索引（存取路（存取路径）径）等等 n基于基于规则规则的的优优化化vs基于代价的基于代价的优优化化n基于基于规则规则的的优优化：根据某些启化：根据某些启发发式式规则规则，通，通过过关系代数的等价关系代数的等价变换变换，得到更有效的关系代数表达式；或者根据某些启得到更有效的关系代数表达式；或者根据某些启发发式式规则选择实现规则选择实现基本运算的算法基本运算的算法n基于代价的基于代价的优优化：利用元数据中的化：利用元数据中的统计统计信息，估信息，估计计不同的不同的查询执查询执行行计计划的开划的开销销，从中，从中选择选择最最优优方案方案 10-9.1.1 查询处理步理步骤（续）n 查询执查询执行行n执执行引擎依据行引擎依据优优化器得到的化器得到的查询执查询执行行计计划生成划生成执执行行查询计查询计划的代划的代码码，执执行行该该代代码产码产生生查询结查询结果，并以适当的形式提交用果，并以适当的形式提交用户户n查询执查询执行之前行之前还还要要进进行安全性行安全性检查检查，确保，确保执执行行查询查询的用的用户户必必须须具有具有相相应应的的访问权访问权限。任何限。任何违违反安全性限制的反安全性限制的查询查询都将被拒都将被拒绝绝n对对于数据于数据库库的更新操作，除了安全性的更新操作，除了安全性检查检查之外，之外，还还需要需要进进行完整性行完整性检查检查 11-9.1.1 查询处理步理步骤（续）n查询查询代价的估代价的估计计n为为了了优优化化查询查询，优优化器必化器必须须知道每个基本运算的代价，知道每个基本运算的代价，进进而估而估计查计查询执询执行行计计划的代价划的代价n精确地估精确地估计计代价是困代价是困难难的，但是粗略的估的，但是粗略的估计计是可能的，并且是可能的，并且这这种粗种粗略估略估计计可以很好地反映不同可以很好地反映不同查询计查询计划的相划的相对优对优劣劣n查询查询代价包括代价包括CPU代价、代价、I/O代价和内存代价代价和内存代价n在分布式数据在分布式数据库库系系统统或并行数据或并行数据库库系系统统中，中，查询查询代价代价还还包括通信代包括通信代价价n本章，我本章，我们们只考只考虑虑集中式系集中式系统统n内存代价内存代价n用用查询处查询处理所需的内存量度量理所需的内存量度量 n最坏的情况：内存最坏的情况：内存缓缓冲区只能容冲区只能容纳纳数目不多的数据数目不多的数据块块大大约约每个每个关系一关系一块块或几或几块块 12-9.1.1 查询处理步理步骤（续）nCPU代价代价n用用查询查询所需的所需的CPU时间时间度量度量n磁磁盘盘存取比内存操作慢，并且随着硬件技存取比内存操作慢，并且随着硬件技术术的的发发展，展，CPU速度的提速度的提高也比磁高也比磁盘盘速度的提高快得多速度的提高快得多n因此磁因此磁盘盘I/O一直是制一直是制约查询处约查询处理速度提高的瓶理速度提高的瓶颈颈n通常，通常，I/O代价被代价被认为认为是估是估计查询处计查询处理代价的合理度量理代价的合理度量 nI/O代价代价n包括磁包括磁盘寻盘寻道道时间时间、旋、旋转转延延迟时间迟时间和和实际实际的数据的数据传输时间传输时间 n磁磁盘寻盘寻道道时间时间和旋和旋转转延延迟时间迟时间依依赖赖于磁于磁头头的当前位置，的当前位置，难难以精确估以精确估计计n可以假定每个磁可以假定每个磁盘块盘块的的读读写大致需要相同的平均写大致需要相同的平均寻寻道道时间时间和旋和旋转转延延迟时间迟时间nI/O代价可以用磁代价可以用磁盘读盘读写写块块数近似地估数近似地估计计 13-9.1.1 查询处理步理步骤（续）n表达式表达式计计算代价算代价评评估的估的统计统计信息信息nDBMS的数据字典中存的数据字典中存储储并并维护维护了关于数据了关于数据库库关系的如下关系的如下统计统计信息信息 nnr：关系：关系r的元的元组组数数nbr：包含关系：包含关系r的的块块数数nlr：关系：关系r的元的元组长组长度（字度（字节节数）数）nV(r,A)：关系：关系r在属性在属性A上的不同上的不同值值数目数目n在在查询查询中中经经常同常同时时出出现现的属性集上，也有的属性集上，也有类类似的似的统计统计量量nfr：关系：关系r的的块块因子，即一因子，即一块块能能够够容容纳纳关系关系r的元的元组组数数n当当r存存储储在一个物理文件中在一个物理文件中时时，br=nr/fr n关系关系r的哪些属性（集）上建立了索引，哪种索引（的哪些属性（集）上建立了索引，哪种索引（B+树树索引、索引、Hash索引、聚集索引索引、聚集索引nB+树树索引包括索引包括n属性属性A上上B+树树高度高度h(r,A)nB+树树叶叶节节点数点数l(r,A)等信息等信息 14-9.1 关系数据关系数据库系系统的的查询处理理n9.1.1 查询处理步理步骤n9.1.2 实现查询操作的算法示例操作的算法示例15-9.1.2 实现查询操作的算法示例操作的算法示例n查询查询最常用的运算是最常用的运算是选择选择、投影和、投影和连连接接 n投影运算的投影运算的实现实现是是简单简单的的 n通常投影可以并入其他步通常投影可以并入其他步骤骤n重点重点讨论讨论选择选择与与连连接接16-选择操作的操作的实现n例例1select*from student where：n考考虑的几种情况：的几种情况：nC1：无条件；：无条件；nC2：sno=200215121；nC3：sage20;nC4:sdept=CS AND sage2017-选择操作的操作的实现（续）n选择操作典型的操作典型的实现方法方法n1.简单的全表的全表扫描方法描方法n对查询的基本表的基本表顺序序扫描，逐一描，逐一检查每个元每个元组是否是否满足足选择条件，条件，把把满足条件的元祖作足条件的元祖作为结果果输出出n适合小表，或者适合小表，或者满满足足选择选择条件的元条件的元组组所占比例所占比例较较大大n2.索引（散列）索引（散列）扫描方法描方法n适合适合选择条件中属性有索引（例如条件中属性有索引（例如B+树索引或者索引或者hash索引）索引）n通通过索引先找到索引先找到满足条件的元足条件的元组主主码或元或元组指指针，再通，再通过元元组指指针直接在直接在查询的基本表中找到元的基本表中找到元组18-选择操作的操作的实现（续）n例例1-C2以以C2为例，例，sno=200215121，并且在，并且在sno上有索引（或上有索引（或sno是散是散列列码），），则可以使用索引（或散列可以使用索引（或散列码）得到）得到sno为200215121元元组的指的指针，然后通，然后通过元元组指指针在在student表中表中检索到索到该学生学生n例例1-C3以以C3为例，例，sage20，并且在，并且在sage上有上有B+树索引，索引，则可以使用可以使用B+树索引找到索引找到sage=20的索引的索引项，以此，以此为入口点在入口点在B+树的的顺序集上得到序集上得到sage20的所有元的所有元组指指针，然后通，然后通过这些元些元组指指针到到student表中表中检索到索到所有年所有年龄大于大于20的学生的学生n例例1-C4以以C4为例，例，sdept=CSand sage20，如果，如果sdept和和sage上都有索上都有索引，那么其中一种算法是：分引，那么其中一种算法是：分别用上面两种方法分用上面两种方法分别找到找到sdept=CS的的一一组元元组指指针和和sage20的另一的另一组元元组指指针，求，求这2组指指针的交集，再到的交集，再到student表中表中检索，就得到索，就得到计算机系年算机系年龄大于大于20的学生；另一种算法：找的学生；另一种算法：找到到sdept=CS的一的一组元元组指指针，通，通过这些元些元组指指针到到student表中表中检索，索，并并对得到的元得到的元组检查另一些另一些选择条件（如条件（如sage20）是否）是否满足，将足，将满足足条件的元条件的元组作作为结果果输出出19-连接操作的接操作的实现n连接操作是接操作是查询处理中最耗理中最耗时的操作之一的操作之一n本章只本章只讨论等等值连接（或自然接（或自然连接）最常用的接）最常用的实现算法算法n例例2 SELECT*FROM Student,SCnWHERE Student.Sno=SC.Snon1.嵌套循嵌套循环方法（方法（nested loop）n2.排序排序-合并方法（合并方法（sort-merge join或或merge join）n3.索引索引连接（接（index join）方法）方法n4.Hash Join方法方法20-连接操作的接操作的实现（续）n1.嵌套循嵌套循环方法方法n对外外层循循环（Student）的每一个元）的每一个元组（s），），检索内索内层循循环（SC）中的没一个元）中的没一个元组（sc）n检查这两个元两个元组在在连接属性（接属性（sno）上是否相等）上是否相等n如果如果满足足连接条件，接条件，则串接后作串接后作为结果果输出，直到外出，直到外层循循环表中的表中的元元组处理完理完为止止21-连接操作的接操作的实现（续）n2.排序排序-合并方法（合并方法（sort-merge join或或merge join）n如果如果进进行行连连接的两个关系接的两个关系r和和s在在连连接属性上是有序的，接属性上是有序的，则则可以使用可以使用归归并并连连接接n与两个有序文件与两个有序文件归归并并类类似似n排序排序-合并合并连接方法的步接方法的步骤：n1.如果如果连接的表没有排好序，首先接的表没有排好序，首先对Student表和表和SC表按表按连接属性接属性Sno排序排序n2.取取Student表中第一个表中第一个Sno，依次，依次扫描描SC表中具有相同的表中具有相同的Sno的元的元组；把它把它们连接起来（如接起来（如图所示）所示）n3.当当扫描到描到Sno不同的第一个不同的第一个SC元元组时，返回，返回Student表表扫描它的下描它的下一个元一个元组，再，再扫描描SC表中具有相同的表中具有相同的Sno元元组，把它，把它们连接起来接起来n重复上述步重复上述步骤直到直到Student表表扫描完描完22-连接操作的接操作的实现（续）200215121200215122200215123200215124.200215121 1 92200215121 2 85200215121 3 88200215122 2 90200215122 3 80.排序排序-合并合并连连接方法示意接方法示意图图23-连接操作的接操作的实现（续）nStudent表和表和SC表都只需要表都只需要扫描一遍描一遍n如果如果2个表原来无序，个表原来无序，执行行时间要加上要加上对两个表的排序两个表的排序时间n对于两个大表，先排序后使用于两个大表，先排序后使用sort-merge join方法方法执行行连接，接，总的的执行行时间一般仍会大大地减少一般仍会大大地减少24-连接操作的接操作的实现（续）n3.索引索引连接（接（index join）方法）方法n步步骤：n1.在在SC表上建立属性表上建立属性Sno索引，如果原来没有的索引，如果原来没有的话n2.对Student中每一个元中每一个元组，由，由Sno值通通过SC的索引的索引查找相找相应的的SC元元组n3.把把这些些SC元元组和和Student连接起来接起来n循循环执行行2、3步，直到步，直到Student表中的元表中的元组处理完理完为止止25-连接操作的接操作的实现（续）n4.Hash Join方法方法n把把连接属性作接属性作为hash码，用同一个，用同一个hash函数把函数把R和和S中的元中的元组散列到同散列到同一个一个hash文件中文件中n步步骤：n划分划分阶段（段（partitioning phase）：）：n对包含包含较少元少元组的表（比如的表（比如R）进行一遍行一遍处理理n把它的元把它的元组按按hash函数分散到函数分散到hash表的桶中表的桶中n试探探阶段（段（probing phase）：也称）：也称为连接接阶段（段（join phase）n对另一个表（另一个表（S）进行一遍行一遍处理理n把把S的元的元组散列到适当散列到适当hash桶中桶中n并把元并把元组与桶中所有来自与桶中所有来自R并与之相匹配的元并与之相匹配的元组连接起来接起来n该算法的前提是假算法的前提是假设这两个表中两个表中较小的表在第一小的表在第一阶段后可以完全放入内段后可以完全放入内存的存的hash桶中桶中n该算法思想可以推广到更加一般的多个表的算法思想可以推广到更加一般的多个表的连接算法上接算法上26-关系关系查询处理和理和查询优化化n9.1 关系数据关系数据库系系统的的查询处理理n9.2 关系数据关系数据库系系统的的查询优化化n9.3 代数代数优化化n9.4 物理物理优化化n9.5 小小结27-9.2 关系数据关系数据库系系统的的查询优化化n查询优查询优化在关系数据化在关系数据库库系系统统中有着非常重要的地位，是影响中有着非常重要的地位，是影响RDBMS性性能的关能的关键键因素因素 n非关系系非关系系统统n用用户户使用使用过过程化的程化的语语言表达言表达查询查询要求要求n执执行何种操作，以及操作的序列都是由用行何种操作，以及操作的序列都是由用户户来决定的来决定的n系系统为统为用用户户提供提供选择选择存取路径的手段，而用存取路径的手段，而用户户必必须须了解存取路径，了解存取路径，为为自己的自己的查询选择查询选择合适的存取路径合适的存取路径 n对对于关系数据于关系数据库库系系统统，查询优查询优化是机遇，也是挑化是机遇，也是挑战战 n用用户户只需要只需要说说明做什么，而不必明做什么，而不必说说明怎么做。明怎么做。这这就就为查询优为查询优化提供化提供了更大的空了更大的空间间，使得系，使得系统统可以分析可以分析查询语义查询语义，选择选择最佳的最佳的查询处查询处理理方案方案 n为为了使了使查询处查询处理速度达到用理速度达到用户户可以接受的水平，可以接受的水平，RDBMS必必须须使用使用优优化技化技术术，并且，并且为查询选择为查询选择一种最佳的一种最佳的执执行方案也并非一件易事行方案也并非一件易事 28-9.2 关系数据关系数据库系系统的的查询优化（化（续）n9.2.1 查询优化概述化概述n9.2.2 一个一个实例例29-9.2.1 查询优化概述化概述n查询优化的化的优点不点不仅在于用在于用户不必考不必考虑如何最好地表达如何最好地表达查询以以获得得较好好的效率，而且在于系的效率，而且在于系统可以比用可以比用户程序的程序的“优化化”做的更好，原因：做的更好，原因：n1.优化器可以从数据字典中化器可以从数据字典中获取取许多多统计信息，例如：每个关系表信息，例如：每个关系表中的元中的元组数、关系中每个属性数、关系中每个属性值的分布情况、哪些属性上已的分布情况、哪些属性上已经建立建立了索引等。了索引等。优化器可以根据化器可以根据这些信息作出正确的估算，些信息作出正确的估算，选择高效的高效的执行行计划，而用划，而用户程序程序则难以以获得得这些信息些信息n2.如果数据如果数据库的物理的物理统计信息改信息改变了，系了，系统可以自可以自动对查询进行重行重新新优化以化以选择相适相适应的的执行行计划。在非关系系划。在非关系系统中必中必须重写程序，重写程序，而重写程序在而重写程序在实际应用中往往是不太可能的用中往往是不太可能的30-9.2.1 查询优化概述（化概述（续）n3.优化器可以考化器可以考虑数百种不同的数百种不同的执行行计划，而程序划，而程序员一般只能考一般只能考虑有限的几种可能性有限的几种可能性n4.优化器中包括了很多复化器中包括了很多复杂的的优化技化技术，这些些优化技化技术往往只有最往往只有最好的程序好的程序员才能掌握。系才能掌握。系统的自的自动优化相当于使得所有人都化相当于使得所有人都拥有有这些些优化技化技术n查询优化的化的总目目标：n选择有效的策略有效的策略n求得求得给定关系表达式的定关系表达式的值n使得使得查询代价最小（代价最小（实际上是上是较小）小）31-9.2 关系数据关系数据库系系统的的查询优化（化（续）n9.2.1 查询优化概述化概述n9.2.2 一个一个实例例32-9.2.2 一个一个实例例n例例3求求选修修2号号课程的学生姓名，用程的学生姓名，用SQL表达：表达：nSELECT Student.SnamenFROM Student，SCnWHERE Student.Sno=SC.Sno AND SC.Cno=2n假定学生假定学生-课程数据程数据库中有中有1000个学生个学生记录，10000个个选课记录n其中其中选修修2号号课程的程的选课记录为50个个33-9.2.2 一个一个实例例(续)n系系统可以用多种等价的关系代数表达式完成可以用多种等价的关系代数表达式完成这一一查询nQ1=Sname(Student.Sno=SC.SnoSc.Cno=2(StudentSC)nQ2=Sname(Sc.Cno=2(Student SC)nQ3=Sname(Student Sc.Cno=2(SC)34-9.2.2 一个一个实例例(续)n一、第一种情况一、第一种情况Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 StudentSC)n1.计算广算广义笛卡笛卡尔积n把把Student和和SC的每个元的每个元组连接起来的做法是：接起来的做法是：n在内存中尽可能多地装入某个表在内存中尽可能多地装入某个表(如如Student表表)的若干的若干块块，留出一，留出一块块存放另存放另一个表一个表(如如SC表表)的元的元组组n把把SC中的每个元中的每个元组组和和Student中每个元中每个元组连组连接，接，连连接后的元接后的元组组装装满满一一块块后就后就写到中写到中间间文件上文件上n从从SC中中读读入一入一块块和内存中的和内存中的Student元元组连组连接，直到接，直到SC表表处处理完理完n再再读读入若干入若干块块Student元元组组，读读入一入一块块SC元元组组n重复上述重复上述处处理理过过程，直到把程，直到把Student表表处处理完理完35-9.2.2 一个一个实例例(续)n设设一个一个块块能装能装10个个Student元元组组或或100个个SC元元组组，在内存中存放，在内存中存放5块块Student元元组组和和1块块SC元元组组，则读则读取取总块总块数数为为 读读取取总块总块数数=读读Student表表块块数数+读读SC表遍数表遍数*每遍每遍块块数数 n其中，其中，读读Student表表100块块。读读SC表表20遍，每遍遍，每遍100块块。若每秒。若每秒读读写写20块块，则总计则总计要花要花105s n连连接后的元接后的元组组数数为为103104=107。设设每每块块能装能装10个元个元组组，则则写出写出这这些些块块要要用用106/20=5104s 36-9.2.2 一个一个实例例(续)n2.作作选择操作操作n依次依次读读入入连连接后的元接后的元组组，按照，按照选择选择条件条件选选取取满满足要求的足要求的记录记录 n假定内存假定内存处处理理时间时间忽略。忽略。读读取中取中间间文件花文件花费费的的时间时间(同写中同写中间间文件一文件一样样)需需5104s n满满足条件的元足条件的元组组假假设仅设仅50个，均可放在内存个，均可放在内存 n3.作投影操作作投影操作n把第把第2步的步的结果在果在Sname上作投影上作投影输出，得到最出，得到最终结果果 n第一种情况下第一种情况下执行行查询的的总时间105+25104105sn所有内存所有内存处理理时间均忽略不均忽略不计37-9.2.2 一个一个实例例(续)n二、第二种情况二、第二种情况Q2=Sname(Sc.Cno=2(Student SC)1.计计算自然算自然连连接接 执执行自然行自然连连接，接，读读取取Student和和SC表的策略不表的策略不变变，总总的的读读取取块块数数仍仍为为2100块块花花费费105 s 自然自然连连接的接的结结果比第一种情况大大减少，果比第一种情况大大减少，为为104个个 写出写出这这些元些元组时间为组时间为104/10/20=50s，为为第一种情况的千分之一第一种情况的千分之一 2.读读取中取中间间文件文件块块，执执行行选择选择运算，花运算，花费时间费时间也也为为50s。3.把第把第2步步结结果投影果投影输输出出。第二种情况第二种情况总总的的执执行行时间时间105+50+50205s 38-9.2.2 一个一个实例例(续)n三、三、第三种情况第三种情况 Q3=Sname(Student Sc.Cno=2(SC)1.先先对对SC表作表作选择选择运算运算，只需，只需读读一遍一遍SC表，存取表，存取100块块花花费时间为费时间为5s，因，因为满为满足条件的元足条件的元组仅组仅50个，不必使用中个，不必使用中间间文件。文件。2.读读取取Student表表，把，把读读入的入的Student元元组组和内存中的和内存中的SC元元组组作作连连接。接。也只需也只需读读一遍一遍Student表共表共100块块，花，花费时间为费时间为5s。3.把把连连接接结结果投影果投影输输出出 第三种情况第三种情况总总的的执执行行时间时间5+510s 39-9.2.2 一个一个实例例(续)n假如假如SC表的表的Cno字段上有索引字段上有索引n第一步就不必第一步就不必读读取所有的取所有的SC元元组组而只需而只需读读取取Cno=2的那些元的那些元组组(50个个)n存取的索引存取的索引块块和和SC中中满满足条件的数据足条件的数据块块大大约总约总共共34块块n若若Student表在表在Sno上也有索引上也有索引n第二步也不必第二步也不必读读取所有的取所有的Student元元组组n因因为满为满足条件的足条件的SC记录仅记录仅50个，涉及最多个，涉及最多50个个Student记录记录n读读取取Student表的表的块块数也可大大减少数也可大大减少 n总总的存取的存取时间时间将将进进一步减少到数秒一步减少到数秒 40-9.2.2 一个一个实例例(续)n把代数表达式把代数表达式Q1变换为变换为Q2、Q3，n即有即有选择选择和和连连接操作接操作时时，先做先做选择选择操作操作，这样这样参加参加连连接的元接的元组组就可就可以大大减少，以大大减少，这这是代数是代数优优化化n在在Q3中中nSC表的表的选择选择操作算法有全表操作算法有全表扫扫描和索引描和索引扫扫描描2种方法，种方法，经过经过初步估初步估算，索引算，索引扫扫描方法描方法较优较优 n对对于于Student和和SC表的表的连连接，利用接，利用Student表上的索引，采用表上的索引，采用index join代价也代价也较较小，小，这这就是物理就是物理优优化化 41-关系关系查询处理和理和查询优化化n9.1 关系数据关系数据库系系统的的查询处理理n9.2 关系数据关系数据库系系统的的查询优化化n9.3 代数代数优化化n9.4 物理物理优化化n9.5 小小结42-9.3 代数代数优化化n9.3.1 关系代数表达式等价关系代数表达式等价变换规则n9.3.2查询树的启的启发式式优化化43-9.3.1 关系代数表达式等价关系代数表达式等价变化化规则n代数代数优优化策略：通化策略：通过对过对关系代数表达式的等价关系代数表达式的等价变换变换来提高来提高查询查询效率效率n关系代数表达式的等价：指用相同的关系代替两个表达式中相关系代数表达式的等价：指用相同的关系代替两个表达式中相应应的关系的关系所得到的所得到的结结果是相同的果是相同的n两个关系表达式两个关系表达式E1和和E2是等价的，可是等价的，可记为记为E1E2 44-9.3.1 关系代数表达式等价关系代数表达式等价变化化规则（续）n常用的等价常用的等价变换规则变换规则：1.连连接、笛卡接、笛卡尔尔积积交交换换律律2.连连接、笛卡接、笛卡尔尔积积的的结结合律合律3.投影的串接定律投影的串接定律4.选择选择的串接定律的串接定律5.选择选择与投影操作的交与投影操作的交换换律律6.选择选择与笛卡与笛卡尔尔积积的交的交换换律律7.选择选择与并的分配律与并的分配律8.选择选择与差运算的分配律与差运算的分配律9.选择对选择对自然自然连连接的分配律接的分配律10.投影与笛卡投影与笛卡尔尔积积的分配律的分配律11.投影与并的分配律投影与并的分配律45-9.3.2 查询树的启的启发式式优化化n典型的启典型的启发发式式规则规则：1.选择选择运算运算应应尽可能先做尽可能先做。在。在优优化策略中化策略中这这是最重要、最基本的一条是最重要、最基本的一条。它常常可使。它常常可使执行行时节约几个数量几个数量级，因，因为选择运算一般使运算一般使计算的中算的中间结果大大果大大变小小2.把投影运算和把投影运算和选择选择运算同运算同时进时进行行。如有若干投影和如有若干投影和选择操作，并且它操作，并且它们都都对同一个关同一个关系操作，系操作，则可以在可以在扫描此关系的同描此关系的同时完成所有的完成所有的这些运算以避免重复些运算以避免重复扫描关系描关系3.把投影同其前或其后的双目运算把投影同其前或其后的双目运算结结合起来合起来，没有必要，没有必要为了去掉某些字段而了去掉某些字段而扫描一遍关描一遍关系系4.把某些把某些选择选择同在它前面要同在它前面要执执行的笛卡行的笛卡尔尔积结积结合起来成合起来成为为一个一个连连接运算接运算，连接特接特别是等是等值连接运算要比同接运算要比同样关系上的笛卡关系上的笛卡尔积节省很多省很多时间5.找出公共子表达式找出公共子表达式。如果。如果这种重复出种重复出现的子表达式的的子表达式的结果不是很大的关系，并且从外果不是很大的关系，并且从外存中存中读入入这个关系比个关系比计算算该子表达式的子表达式的时间少得多，少得多，则先先计算一次公共子表达式并把算一次公共子表达式并把结果写入中果写入中间文件是合算的。当文件是合算的。当查询的是的是视图时，定，定义视图的表达式就是公共子表达的表达式就是公共子表达式的情况式的情况46-9.3.2 查询树的启的启发式式优化（化（续）例例4 下面下面给给出例出例3中中 SQL语语句的代数句的代数优优化示例。化示例。(1)把把SQL语语句句转换转换成成查询树查询树，如下，如下图图所示所示图9.3 查询树47-9.3.2 查询树的启的启发式式优化（化（续）n为为了使用关系代数表达式的了使用关系代数表达式的优优化法，假化法，假设设内部表示是关系代数内部表示是关系代数语语法法树树，则则上面的上面的查询树查询树如下如下图图所示。所示。图9.4 关系代数关系代数语语法法树树 48-9.3.2 查询树的启的启发式式优化（化（续）n(2)对查询树进对查询树进行行优优化化n利用利用规则规则4、6把把选择选择SC.Cno=2移到叶端，移到叶端，查询树查询树便便转换转换成下成下图图所示所示的的优优化的化的查询树查询树。这这就是就是9.2.2节节中中Q3的的查询树查询树表示表示图9.4 优化后的化后的查询树49-关系关系查询处理和理和查询优化化n9.1 关系数据关系数据库系系统的的查询处理理n9.2 关系数据关系数据库系系统的的查询优化化n9.3 代数代数优化化n9.4 物理物理优化化n9.5 小小结50-9.4 物理物理优化化n代数代数优优化改化改变查询语变查询语句中操作的次序和句中操作的次序和组组合，不涉及底合，不涉及底层层的存取路径的存取路径n对对于一个于一个查询语查询语句有句有许许多存取方案，它多存取方案，它们们的的执执行效率不同，行效率不同，仅仅进仅仅进行行代数代数优优化是不化是不够够的的 n物理物理优优化就是要化就是要选择选择高效合理的操作算法或存取路径，求得高效合理的操作算法或存取路径，求得优优化的化的查询查询计计划划 n选择选择的方法可以是：的方法可以是：n基于基于规则规则的启的启发发式式优优化；化；n基于代价估算的基于代价估算的优优化；化；n两者两者结结合合51-9.4 物理物理优化化n9.4.1 基于启基于启发式式规则存取路径存取路径选择优化化n9.4.2 基于代价的基于代价的优化化52-9.4.1 基于启基于启发式式规则的存取路径的存取路径选择优化化n一、一、选择操作的启操作的启发式式规则有：有：n1.对于于小小关系，使用关系，使用全表全表顺序序扫描描，即使，即使选择列上有索引列上有索引对于大关系，启于大关系，启发式式规则有：有：n2.对于于选择条件是主条件是主码=值的的查询，查询结果最多是一个元果最多是一个元组，可以，可以选择主主码索引，一般的索引，一般的RDBMS会自会自动建立主建立主码索引索引n3.对于于选择条件是非主属性条件是非主属性=值的的查询，并且，并且选择列上有索引，列上有索引，则要估要估算算查询结果的元果的元组数目，如果比例数目，如果比例较小（小（10%）可以使用索引）可以使用索引扫描方描方法，否法，否则还是使用全表是使用全表顺序序扫描描53-9.4.1 基于启基于启发式式规则的存取路径的存取路径选择优化（化（续）n4.对于于选择条件是属性上的非等条件是属性上的非等值查询或者范或者范围查询，并且，并且选择列上有列上有索引，同索引，同样要估算要估算查询结果的元果的元组数目，如果比例数目，如果比例较小（小（,=,=操作，假操作，假设有一半的元有一半的元组满足条件，那么足条件，那么就要存取一半的叶就要存取一半的叶节点，并通点，并通过索引索引访问一半的表存一半的表存储块。所以。所以cost=L+Y/2+B/2。如果可以。如果可以获得更准确的得更准确的选择基数，可以基数，可以进一步修一步修正正Y/2与与B/259-9.4.2 基于代价的基于代价的优化（化（续）n3.嵌套循嵌套循环连接算法的代价估算公式接算法的代价估算公式n在在9.4.1中已中已经讨论过了嵌套循了嵌套循环连接算法的代价接算法的代价cost=Br+（Br/K-1)Bsn如果需要把如果需要把连接接结果写回磁果写回磁盘，则cost=Br+Br Bs/(K-1)+（Frs*Nr*Ns）/Mrs，其中，其中Frs为连接接选择性，表示性，表示连接接结果元果元组数的比例，数的比例，Mrs是存放是存放连接接结果的果的块因子，表示每因子，表示每块中可以存放中可以存放结果元果元组数目数目n4.排序排序合并合并连接算法的代价估算公式接算法的代价估算公式n如果如果连接表已接表已经按照按照连接属性排好接属性排好顺序，序，则cost=Br+Bs+（Frs*Nr*Ns）/Mrsn如果必如果必