db_chapter09查询优化（精品）

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据库系统概论,*,普通高等教育十五规划教材,数据库系统概论,主讲：张中军,第,9,章 查询处理与优化,查询处理与优化,如何以,有效的方式处理用户查询,是,RDBMS,有效实现的关键问题之一,数据库的更新运算,要么是简单,的（如插入一个元组），,要么与一个复杂的更新条件相关联,（如删除满足某些条件的元组）,这些复杂的更新首先需要,找到,要更新的元组，然后才能进行,更新,。因此，只有能够有效地处理查询，才能有效地实现更新,查询处理的中心任务是把使用诸如,SQL,这样的说明性语言表达的用户查询,转换,成一系列能够在物理文件上,执行,的操作，并执行这些操作得到查询结果,查询优化是查询处理的关键步骤，它从众多的查询执行方案中选择最有效的执行方案。,11/28/2024,3,数据库系统概论,第,9,章 查询处理与优化,9.1,查询处理概述,9.2,选择运算的实现,9.3,连接运算的实现,9.4,查询优化概述,9.5,代数优化,9.6,物理优化,9.7,小结,11/28/2024,4,数据库系统概论,查询处理概述,查询处理的过程,查询,语法分析,与翻译器,查询的内部表示,优化器,查询执行计划,执行引擎,查询结果,数据库,图,9.1,查询处理步骤,元数据,11/28/2024,5,数据库系统概论,查询处理概述,(,续,),1.,语法分析与翻译,进行词法分析、语法分析和语义分析，并将查询翻译成内部表示,词法分析,从查询语句中识别出语言符号，如,SQL,的保留字、关系名、属性名和各种运算符等其他符号,语法分析,检查用户查询语句的语法格式，确保查询语句语法上的正确性,语义分析,可以与语法分析同时进行，将查询转换成更适合进一步处理的内部表示,查询的内部表示用,查询树,（语法分析树）或,关系代数表达式,涉及视图的查询还需要先将定义视图的查询表达式转换成内部表示,11/28/2024,6,数据库系统概论,查询处理概述,(,续,),例,9.1,查询,SELECT,Sname,FROM Suppliers, SP,WHERE,Suppliers.Sno,=,SP.Sno,AND,Pno,=P001;,找出提供了,P001,号零件的供应商名称。它将被转换成图,9.2,所示的语法树，或者转换成如下关系代数表达式：,Q,1,：,Sname,(,Suppliers.Sno,=,SP.Sno,Pno,=P001,(,SuppliersSP,),Suppliers.Sno,=,SP.Sno,Pno,=P001,Suppliers,SP,Sname,图,9.2,一棵语法分析树,11/28/2024,7,数据库系统概论,查询处理概述,(,续,),语义分析中包含了对查询语句合法性的检查，即查询检查,根据数据字典对合法的查询语句进行语义检查,根据数据字典中的,用户权限,和,完整性约束定义,对用户的存取权限进行检查,检查通过后把,SQL,查询语句转换成等价的关系代数表达式,RDBMS,一般都用,查询树,(,语法分析树,),来表示扩展的关系代数表达式,把数据库对象的外部名称转换为内部表示,11/28/2024,8,数据库系统概论,查询处理概述,(,续,),2.,查询优化,对于一个给定的查询，通常由多种可能的,执行策略,例如，例,9.1,的查询也可以用如下关系代数表达式计算：,Q,2,：,Sname,(,Pno,=P001,(Suppliers SP),Q,3,：,Sname,(Suppliers,Pno,=P001,(SP),每个关系代数表达式的每个基本运算也可以有多种不同的实现算法,一个查询执行计划包括计算查询的关系代数表达式和其中每个基本运算的实现算法,11/28/2024,9,数据库系统概论,查询处理概述,(,续,),查询优化就是,从多种可能的查询执行方案中选择一种最有效的查询执行计划的过程,对于相同的查询，不同的查询执行计划的时间开销可能相差几个数量级。,例如，使用,Q,1,计算例,9.1,的查询的,I/O,开销大约是使用,Q,3,的,2000,倍,代数优化,vs.,物理优化,代数优化,旨在找到一个与给定的查询表达式等价、但执行起来更加有效的关系代数表达式,物理优化,旨在为关系代数表达式选择一个详细的策略，包括为特定的操作选择可用的算法，选择可用的索引等,11/28/2024,10,数据库系统概论,查询处理概述,(,续,),基于规则的优化,vs.,基于代价的优化,基于规则的优化根据某些启发式规则，通过关系代数的,等价变换,，,得到更有效的关系代数表达式,；或者根据某些启发式规则选择实现基本运算的算法,基于代价的优化利用元数据中的统计信息，,估计不同的查询执行计划的开销,，从中,选择最优,方案,11/28/2024,11,数据库系统概论,查询处理概述,(,续,),3.,查询执行,执行引擎依据优化器得到的查询执行计划,生成执行查询计划的代码,，,执行该代码产生查询结果,，并以适当的形式提交用户。,查询执行之前还要进行安全性检查，确保执行查询的用户必须具有相应的访问权限。任何违反安全性限制的查询都将被拒绝,对于数据库的更新操作，除了安全性检查之外，还需要进行完整性检查,11/28/2024,12,数据库系统概论,查询处理概述,(,续,),4.,查询代价的估计,为了优化查询，优化器必须知道每个基本运算的代价，进而估计查询执行计划的代价,精确地估计代价比较困难，但是可以粗略的估计。,查询代价包括,CPU,代价,、,I/O,代价,和,内存代价,分布式数据库系统或并行系统中，查询代价还包括,通信代价,。,本章，我们只考虑集中式系统,内存代价,用查询处理所需的内存量度量,最坏的情况：内存缓冲区只能容纳数目不多的数据块,大约每个关系一块或几块,11/28/2024,13,数据库系统概论,查询处理概述,(,续,),CPU,代价,用查询所需的,CPU,时间度量,磁盘存取比内存操作慢，并且随着硬件技术的发展，,CPU,速度的提高也比磁盘速度的提高快得多,因此磁盘,I/O,一直是制约查询处理速度提高的瓶颈,通常，,I/O,代价被认为是估计查询处理代价的合理度量,I/O,代价包括：磁盘寻道时间、旋转延迟时间和实际的数据传输时间,磁盘寻道时间和旋转延迟时间依赖于磁头的当前位置，难以精确估计,可以假定每个磁盘块的读写大致需要相同的平均寻道时间和旋转延迟时间,I/O,代价可以用磁盘读写块数近似地估计,11/28/2024,14,数据库系统概论,查询处理概述,(,续,),5.,表达式计算代价评估的统计信息,DBMS,的数据字典中存储并维护了关于数据库关系的如下统计信息,n,r,：关系,r,的元组数。,b,r,：,包含关系,r,的块数。,l,r,：关系,r,的元组长度（字节数）。,V,(,r,A,),：关系,r,在属性,A,上的不同值数目,在查询中经常同时出现的属性集上，也有类似的统计量。,f,r,：关系,r,的块因子，即一块能够容纳关系,r,的元组数。,当,r,存储在一个物理文件中时，,b,r,=,n,r,/,f,r,。,关系,r,的哪些属性（集）上建立了索引，哪种索引（,B+,树索引、,Hash,索引、聚集索引），并且对每个,B+,树索引包括属性,A,上,B+,树高度,h,(,r,A,),，,B+,树叶节点数,l,(,r,A,),等信息,11/28/2024,15,数据库系统概论,9.2,选择运算的实现,选择运算的实现,查询最常用的运算是,选择,、,投影,和,连接,假设选择在关系,r,上进行，而,r,的元组存储在一个文件中，具有,br,个物理块。在考虑索引时，除非特别声明，否则假定索引是,B+,树索引,基本算法,1.,线性搜索,线性搜索又称,顺序扫描,，它逐一扫描文件的每个物理块，检查每个元组是否满足选择条件，并输出满足条件的元组。,线性搜索的,I/O,开销是读,b,r,个物理块,当选择是主码上的等值选择时，线性搜索的平均开销是读,b,r,/2,个物理块，而最坏情况仍为,b,r,11/28/2024,17,数据库系统概论,选择运算的实现,(,续,),线性搜索适用于任意条件的选择运算，并且对存储,r,的文件不做任何假定,当存储,r,的文件不大，或者满足选择条件的元组所占比例较大时，线性搜索是一种较好的方法,2.,二分法搜索,如果存储,r,的文件在某属性,A,上是,有序,的，并且选择是在该属性上做,等值比较,，则可以使用二分法搜索确定满足选择条件的元组。,为确定满足选择条件元组的位置，二分搜索需要读,log,2,b,r,个物理块。如果满足选择条件的元组多于一个，则还需要读连续的物理块，得到其他满足选择条件的元组,11/28/2024,18,数据库系统概论,选择运算的实现,(,续,),假设属性,A,上的值均匀分布，则满足选择条件的元组大约占,b,r,/,V,(,r,A,),个，其中,V,(,r,A,),是,r,在属性,A,上的不同值数目。这样，二分法搜索的,I/O,开销为,log,2,b,r,+,b,r,/,V,(,r,A,),1,。,稍加修改，二分法搜索也可以用于大于等于和大于比较,当文件在选择属性上有序时，小于和小于等于比较可以使用线性搜索，可以提前终止扫描。,二分法搜索十分有效，但是要求存储,r,的文件在选择属性上有序,11/28/2024,19,数据库系统概论,选择运算的实现,(,续,),使用索引的选择,聚簇索引,vs.,一般索引,1.,聚簇索引、等值选择,先通过索引找到指向满足选择条件的元组指针，确定结果元组所在物理块，读取这些物理块就可得到查询结果。,假设聚簇索引建立在属性,A,上，则检索,B+,树索引需要读取的物理块数等于,B+,树的高度,h,(,r,A,),主索引建立在码上：满足条件的元组只有一个，再读取一个物理块就能得到选择结果,非码主索引：满足条件的元组可能有多个，但存储在连续的物理块中。大约需要读取,b,r,/,V,(,r,A,),个物理块，而整个选择的,I/O,开销大约为,h,(,r,A,)+,b,r,/,V,(,r,A,),11/28/2024,20,数据库系统概论,选择运算的实现,(,续,),使用索引的选择,(,续,),2.,聚簇索引、比较选择,选择条件是大于等于和大于比较,：,使用索引可以确定满足条件的第一个元组的位置,。然后读取其后的物理块，就可以得到查询结果,此时，选择运算的,I/O,开销为,h,(,r,A,),加上读取结果元组的开销（通常比线性搜索快）。,当,选择条件是小于和小于等于比较时，最好的方法是使用线性搜索（可以提前终止搜索），,而不是利用主索引,对于涉及非等值比较的选择，如果只有辅助索引，则使用索引一般不如使用线性搜索,11/28/2024,21,数据库系统概论,选择运算的实现,(,续,),复杂选择的实现,对于复杂选择，总可以用线性搜索的方法实现,。然而，在某些情况下，如果存在可用的索引，则利用索引可以更有效地实现复杂选择,1.,利用单个属性上的索引的合取选择,选择条件涉及多个属性上比较的合取,如果单个属性上存在索引，则考虑该属性上的简单条件，并按前面的方法利用该索引得到满足该条件的元组，然后检查它们是否满足其余条件,其,I/O,开销等于单个属性上选择的,I/O,开销。,11/28/2024,22,数据库系统概论,选择运算的实现,(,续,),例如，假设查询“找出信息工程学院的教授”。该查询：,Dno,= IE,Title= ,教授,(Teachers),如果,Teachers,在,Dno,上存在聚簇索引，则可以用聚簇索引等值选择的方法，首先找出满足条件,Dno,= IE,的元组；然后检查它们是否满足条件,Title= ,教授就可以得到查询的回答,2.,通过记录标识符的交实现合取选择,选择条件涉及多个属性上比较的合取，并且每个属性上都存在索引,分别考虑每个属性上的简单选择条件，利用相应索引得到满足单个条件的元组指针集,11/28/2024,23,数据库系统概论,选择运算的实现,(,续,),再求这些指针集的,交,，得到指向满足合取条件的指针,最后使用这些指针读取对应的物理块，得到查询结果,如果并非所有属性都存在索引，则需要检查检索到的元组是否满足剩余条件,I/O,开销大约为,h,(,r,Ai,),加上读取结果元组的开销，其中,h,(,r,Ai,),是合取选择涉及的属性上,B+,树的高度。,例：“找出信息工程学院的教授”,如果,Teachers,在,Dno,和,Title,上都存在索引，则可以分别利用它们得到指向满足条件,Dno,= IE,的指针集合满足条件,Title= ,教授的指针集,求这两组指针的交集，读取,Teachers,中相应的物理块，得到信息工程学院的教授,11/28/2024,24,数据库系统概论,9.3,连接运算的实现,基本算法,考虑关系,r,和,s,的连接,r,F,s,，其中,F,是连接条件，,r,和,s,的元组分别存储在两个文件中，分别具有,br,和,bs,个物理块,1.,嵌套循环连接,for (,r,的每个元组,tr,) do,for (,s,的每个元组,ts,) do,if (,元组对,(,tr,ts,),满足连接条件,F,) then,把,tr,.,ts,添加到结果中,其中,tr,.,ts,是元组,tr,和,ts,的串接；如果是自然连接，则需要删除重复属性,11/28/2024,26,数据库系统概论,基本算法,(,续,),关系,r,称为连接的外层关系，而,s,称为连接的内层关系。,嵌套循环的开销很大，因为对关系,r,的每个元组，必须扫描,s,一次,嵌套循环的开销是读,br,+,nr,bs,个物理块，其中,nr,是关系,r,的元组数目,在最好情况下，两个关系都能装入内存，只需要读,br,+,bs,个物理块,11/28/2024,27,数据库系统概论,排序,-,归并连接,对于自然连接或等值连接，如果进行连接的两个关系,r,和,s,在连接属性上是有序的，则可以使用归并连接,与两个有序文件归并类似,如果两个关系,r,和,s,中的一个或两个在连接属性上无序，可以先将它们在连接属性上排序，然后使用归并连接,与两个无序文件归并成一个有序文件类似,设,JoinAttrs,为,r,和,s,的公共属性，,r,和,s,在,JoinAttrs,上是有序的，则归并连接的伪代码如下：,11/28/2024,28,数据库系统概论,11/28/2024,29,数据库系统概论,排序,-,归并连接,(,续,),该算法之所以称为归并连接是因为它类似于文件归并排序,排序,-,归并连接的一个,优点,是连接的结果在连接属性上有序,I/O,开销,如果,S,s,可以放在内存，当两个关系,r,和,s,在连接属性上有序时，排序,-,归并连接的,I/O,开销是,br,+,bs,如果两个关系,r,和,s,中的一个或两个在连接属性上无序，则还需要加上排序的开销,如果内存可以存放,M,块，对关系,r,进行归并排序的,I/O,开销为,br,(2,logM,1(,br,/,M,)+1,，,M,是排序可用的内存块数目,对于两个很大的关系，先排序后使用排序,-,归并连接方法进行连接，总的时间一般仍会少于嵌套循环连接。,11/28/2024,30,数据库系统概论,索引连接,索引连接,当内层关系在连接属性上有索引时，可以用内层关系上的索引查找代替文件扫描,对于外层关系,r,的每个元组,tr,，在,s,中查找满足连接条件的元组相当于在,s,上做选择运算。,使用,s,上的索引进行选择，得到的每个元组,ts,都可以与,tr,串接成为结果元组。,索引嵌套连接的开销为,br,+,nr,c,，其中,c,是使用连接条件对,s,进行单个选择的开销,11/28/2024,31,数据库系统概论,散列连接,对于等值连接和自然连接，还可以使用散列连接方法,设,JoinAttrs,为,r,和,s,的公共属性,散列连接分两个阶段：,划分阶段和连接阶段，每个阶段使用不同的散列函数,1.,划分阶段,设,h,1,是将,JoinAttrs,值映射到,0, 1, .,n,的散列函数,使用,h,1,将关系,r,划分成,n,个分区,r,0,r,1, ,r,n,，其中元组,t,r,r,被放入分区,r,i,中，如果,h,1,(,t,r,JoinAttrs,),=i,使用,h,1,将关系,s,划分成,n,个分区,s,0,s,1, ,s,n,，其中元组,t,s,s,被放入分区,s,i,中，如果,h,1,(,t,s,JoinAttrs,),=i,划分阶段的,I/O,开销为读写,2(,br,+,bs,),块,11/28/2024,32,数据库系统概论,散列连接,(,续,),r,i,中的,r,元组只需与,s,i,中的,s,元组比较,而不必与其他分区中的元组,s,进行比较,因为,:,满足连接条件的,r,元组和,s,元组在连接属性上具有相同的值,.,若该值被映射到某值,i,则,r,元组会在,r,i,中,并且,s,元组在,s,i,中,r,的划分,s,的划分,r,和,s,的散列划分,11/28/2024,33,数据库系统概论,散列连接,(,续,),2.,连接阶段,使用不同的散列函数对,si,散列,for (,i,= 1;,i,+;,n,) do ,/*,对,s,i,建立内存散列索引 *,/,for (,s,i,的每个元组,t,s,) do ,i,=,h,2,(,ts,JoinAttrs,),；,将,t,s,划分到桶,H,i,中；,/*,进行连接 *,/,for (,r,i,中的每个元组,t,r,) do ,i,=,h,2,(,t,r,JoinAttrs,),；,for (,Hi,中每个元组,ts,) do,if (,t,s,JoinAttrs,=,t,r,JoinAttrs,) then,把,t,r,.,t,s,添加到结果中；,11/28/2024,34,数据库系统概论,9.4,查询优化概述,查询优化概述,查询优化在关系数据库系统中有着非常重要的地位，是影响,RDBMS,性能的关键因素,非关系系统,用户使用过程化的语言表达查询要求,执行何种操作，以及操作的序列都是由用户来决定的,系统为用户提供选择存取路径的手段，而用户必须了解存取路径，为自己的查询选择合适的存取路径,11/28/2024,36,数据库系统概论,查询优化概述（续）,对于关系数据库系统，查询优化是机遇，也是挑战,用户只需要说明做什么（查询什么、在什么关系上查询和查询结果满足的条件），而不必说明怎么做。这就为查询优化提供了更大的空间，使得系统可以分析查询语义，选择最佳的查询处理方案,为了使查询处理速度达到用户可以接受的水平，,RDBMS,必须使用优化技术，并且为查询选择一种最佳的执行方案也并非一件易事,11/28/2024,37,数据库系统概论,查询优化的必要性,1.,查询优化的必要性,(,续,),例,9.2,：例,9.1,的 “查询提供了,P001,号零件的供应商名称”可以用如下关系代数表达式计算：,Q,1,：,Sname,(,Suppliers.Sno,=,SP.Sno,Pno,=P001,(,SuppliersSP,),Q,2,：,Sname,(,Pno,=P001,(Suppliers SP),Q,3,：,Sname,(Suppliers,Pno,=P001,(SP),假设,数据库中有,100,个,Suppliers,（供应商）记录，,10000,个,SP,（发货）记录，其中涉及产品,P001,的发货记录为,50,个,一个块能放,10,个,Suppliers,元组或,100,个,SP,元组，则,b,Suppliers,= 10,块，,b,SP,=100,块,分配给该查询处理的内存空间可以存放,7,块。,11/28/2024,38,数据库系统概论,查询优化的必要性,(1),使用,Q,1,首先计算笛卡尔积,SuppliersSP,可以用块嵌套循环连接的类似做法。使用,5,个内存块存放,Suppliers,元组，,1,块存放,SP,元组，,1,块用于缓存结果元组，则读取块数为,b,Suppliers,+,b,Suppliers,/5,b,SP,= 10 +,10/5,100 = 210 (,块,),笛卡儿积将产生,10010000 = 1000000,个中间结果元组，不能存放在内存。假设每块可以存放,10,个中间结果元组，则需要写,100000,块。,选择运算,读入笛卡儿积的结果，按照选择条件,Suppliers.Sno,=,SP.Sno,Pno,=P001,选取满足选择条件的元组。这需要读入,100000,块，而满足条件的元组仅,50,个，可以放在内存,最后，进行投影运算，直接在内存进行。,使用,Q,1,计算该查询的,I/O,开销为读写,200210,块。,11/28/2024,39,数据库系统概论,查询优化的必要性,(,续,),(2),使用,Q,2,首先计算自然连接,Suppliers SP,用块嵌套循环连接，与,(1),类似，需要读,210,块。但是，自然连接只产生,10000,个元组，需要写,1000,块（假定每块,10,个元组）,然后，读入这,1000,块，按条件,Pno,=P001,进行选择，得到的,50,个元组可以放在内存,最后，将这,50,个元组直接投影到,Sname,上，得到查询结果。,使用,Q,2,计算该查询的,I/O,开销为读写,2210,块，大约是,Q,1,的,1/100,。,11/28/2024,40,数据库系统概论,查询优化的必要性,(,续,),(3),使用,Q,3,首先计算选择,Pno,=P001,(SP),用线性搜索也只需要读入,SP,的,100,块，便能得到选择结果。结果元组只有,50,个，可以放在内存,然后，计算,Suppliers,与选择结果的自然连接,这只需要扫描,Suppliers,的每一块，读入,10,块,自然连接的结果只有,50,个元组，可以放在内存,最后的投影可以直接在内存进行。,使用,Q,3,计算该查询的,I/O,开销为读,110,块，大约是,Q,2,的,1/20,，是,Q,1,的,1/2000,11/28/2024,41,数据库系统概论,查询优化的必要性,(,续,),例,9.2,表明了选取合适的查询处理策略的必要性,Q,2,只是将,Q,1,中的选择条件,Suppliers.Sno,=,SP.Sno,与笛卡尔积结合成自然连接,自然连接并未减少读入的,I/O,开销，但是自然连接产生的元组数目远小于笛卡尔积,Q,3,进一步将,Q,2,的选择“推进”到自然连接之前,由于满足选择条件,Pno,=P001,的,SP,元组数目远小于,SP,，使得下一步的自然连接可以更有效地进行,例,9.2,只是讨论了简单的代数优化,使用更有效的关系代数表达式提高查询处理效率,采用表达式计算的流水线技术，或者为每个基本运算选择合适的存取路径，,Q,1,、,Q,2,和,Q,3,都可进一步优化。,11/28/2024,42,数据库系统概论,系统进行优化的优点,2.,系统进行优化的优点,优化减轻了用户选择存取路径的负担，使得用户可以将注意力放在如何正确地表达查询请求上，而不必考虑如何最有效地表达查询,系统进行查询优化还可以比用户做得更好,(1),优化器可以从数据字典中获取许多统计信息,，如每个关系的当前元组数目、每个属性上的不同值个数、有哪些索引等。,这些信息对于选择高效的执行策略是重要的，但是用户难以获得这些信息,(2),当数据库的统计信息改变时，可能需要改变执行策略。,优化器可以自动对查询重新进行优化，以选择相适应的执行策略,11/28/2024,43,数据库系统概论,查询优化概述,(3),优化器可以更全面地考虑，考察数百种不同的执行计划，从中确定最佳的执行计划,。而用户一般只能考虑有限的几种,(4),优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握,查询优化的根本目的,提高查询处理的效率,在计算实际的查询处理代价时必须考虑优化本身的时间和空间开销,如果选择最佳处理方案的开销太大，则可能得不偿失,实际上，查询优化要在合理的优化处理开销下，寻找较好的处理方案，而不一定是最佳方案,11/28/2024,44,数据库系统概论,9.5,代数优化,代数优化,代数,优化,利用一些启发式规则，通过对关系代数表达式的等价变换，得到更有效的计算查询的关系代数表达式，进而提高查询效率,关系代数表达式的等价性,设,E,和,E,是关系代数表达式，涉及一组相同的关系,R,1,R,2, ,R,k,。如果对于关系,R,i,的任意给定当前值,r,i,（,1,i,k,），,E,和,E,将产生相同的计算结果，则称关系代数表达式,E,和,E,等价，记作,E,E,关系代数表达式的等价变换规则如下：,11/28/2024,46,数据库系统概论,等价变换规则,(,续,),(1),笛卡尔积、连接、自然连接的交换律,设,E,1,和,E,2,是关系代数表达式。不考虑结果属性的次序，则笛卡尔积、连接和自然连接都满足交换律：,(2),笛卡尔积、连接、自然连接的结合律,设,E,1,，,E,2,和,E,3,是关系代数表达式，则,(,E,1,E,2,),E,3,E,1,(,E,2,E,3,),11/28/2024,47,数据库系统概论,等价变换规则,(,续,),如果连接条件,F,1,只涉及,E,1,和,E,2,的属性，,F,2,只涉及,E,2,和,E,3,的属性，则,如果,E,1,和,E,2,具有公共属性，,E,2,和,E,3,具有公共属性，则,笛卡尔积（连接、自然连接）的交换律和结合律表明,相继的笛卡儿积可以以任意次序计算,在满足规则要求的条件下，相继的连接和自然连接也可以以任意次序计算,11/28/2024,48,数据库系统概论,等价变换规则,(,续,),(3),投影的串接律,设,E,是关系代数表达式，,A,i,(,i,= 1, 2, ,k,),B,j,(,j,= 1, 2, ,m,),是属性名，并且,A,1,A,2, ,A,k,是,B,1,B,2, ,B,m,的子集，则,该规则表明,相继的投影，只有最后一次投影需要，其余可以省略,反过来，只要保证,B,1,B,2, ,B,m,包含,A,1,A,2, ,A,k,，我们可以先将,E,投影到属性,B,1,B,2, ,B,m,上，然后再投影到属性,A,1,A,2, ,A,k,上,这样做的好处是：可以利用投影对二目运算的分配律，将投影推进到,E,中（参见规则,1215,）,11/28/2024,49,数据库系统概论,等价变换规则,(,续,),(4),选择的串接律,设,E,是关系代数表达式，,F,1,和,F,2,是选择条件，则,该规则表明,选择条件可以合并，这样一次可以检查全部条件,另一方面，合取选择可以分解成相继选择，使得某些选择条件可以推进到表达式,E,中（参见规则,811,）,(5),选择的交换律,设,E,是关系代数表达式，,F,1,和,F,2,是选择条件，则,11/28/2024,50,数据库系统概论,等价变换规则,(,续,),(6),选择与笛卡尔积合并为连接,设,E,1,和,E,2,是关系代数表达式，,F,涉及,E,1,和,E,2,的属性比较，则,(7),选择与投影的交换律,其中，选择条件,F,只涉及属性,A,1,A,k,如果,F,中有不属于,A,1,A,k,的属性,B,1, ,B,m,，则有如下更一般的规则,11/28/2024,51,数据库系统概论,等价变换规则,(,续,),设,E,1,和,E,2,是关系代数表达式，如果,F,1,只涉及,E,1,中的属性，,F,2,只涉及,E,2,中的属性,(8),选择对笛卡尔积的分配律,其特例是,F,1,和,F,2,之一（例如，,F,2,）为,TRUE,。此时：,(9),选择对连接的分配律,其特例是,F,1,和,F,2,之一（例如，,F,2,）为,TRUE,。此时：,11/28/2024,52,数据库系统概论,等价变换规则,(,续,),(10),选择对自然连接的分配律,设,E,1,和,E,2,是关系代数表达式，如果,F,1,只涉及,E,1,中的属性，,F,2,只涉及,E,2,中的属性：,其特例是,F,1,和,F,2,之一（例如，,F,2,）为,TRUE,。此时，我们有：,11/28/2024,53,数据库系统概论,等价变换规则,(,续,),(11),选择对并、交、差的分配律,设,E,1,和,E,2,是关系代数表达式，具有相同的属性，则,对于交和差运算，我们只需要在,E,1,上做选择，即,类似的规则对于并运算不成立,11/28/2024,54,数据库系统概论,等价变换规则,(,续,),选择对二目运算的分配律（规则,811,）使得选择可以推进到二目运算之前进行,这是实现启发式优化策略“选择尽可能先做”的基础,(12),投影对笛卡尔积的分配律,设,E,1,和,E,2,是两个关系表达式，,A,1, ,A,j,是,E,1,的属性，,B,1, ,B,k,是,E,2,的属性，则,11/28/2024,55,数据库系统概论,等价变换规则,(,续,),(13),投影对连接的分配律,设,E,1,和,E,2,是两个关系表达式，,A,1, ,A,j,是,E,1,的属性，,B,1, ,B,k,是,E,2,的属性。如果连接条件,F,只涉及,A,1, ,A,j, B,1, ,B,k,中的属性，则,(14),投影对自然连接的分配律,设,E,1,和,E,2,是两个关系表达式，,A,1, ,A,j,是,E,1,的属性，,B,1, ,B,k,是,E,2,的属性。如果,E,1,和,E,2,的共同属性都在,A,1, ,A,j, B,1, ,B,k,中，则,11/28/2024,56,数据库系统概论,等价变换规则,(,续,),(15),投影对并、交、差的分配律,设,E,1,和,E,2,是关系代数表达式，具有相同的属性，则,投影对二目运算的分配律（规则,1215,）使得投影可以推进到二目运算之前进行,这可以尽早删除不必要的属性，有利于缩短中间结果元组的长度，降低下一步运算的复杂性,11/28/2024,57,数据库系统概论,语法树,语法树可以递归地定义如下：,(1),如果关系代数表达式,E,是关系和常量关系（显式给出的元组集合），则,E,的语法树是以,E,为树叶的树。,(2),如果关系代数表达式,E,形如,F,(,E,1,),，其中,E,1,是关系代数表达式，则,E,的语法树以,F,为根，并且根节点有一个子女，它是一棵由,E,1,的语法树构成的子树。,11/28/2024,58,数据库系统概论,语法树,(3),如果关系代数表达式,E,形如,L,(,E,1),，其中,E,1,是关系代数表达式，,L,是,E,1,中的属性列表，则,E,的语法树以,L,为根，并且根节点有一个子女，它是一棵由,E,1,的语法树构成的子树。,(4),如果关系代数表达式,E,形如,E,1,E,2,（,E,1,E,2,、,E,1,E,2,、,E,1,E,2,、,E,1,E,2,、,E,1,F,E,2,、,E,1,E,2,），其中,E,1,和,E,2,是关系代数表达式，则,E,的语法树以,（,、,、,、,、,F,、）为根，并且根节点有两个子女，其左子女是一棵由,E,1,的语法树构成的子树，其右子女是一棵由,E,2,的语法树构成的子树。,11/28/2024,59,数据库系统概论,语法树,(,续,),11/28/2024,60,数据库系统概论,代数优化的启发式方法,得到最佳表达式的“笨”办法：,对于对给定的查询表达式，使用关系代数表达式的等价变换规则系统地产生等价的表达式，评估每个表达式的执行代价，从中选取最佳的,这种处理方式无论时间还是空间的代价都很大，因而不切实际,一些简单的启发式规则可以帮助我们使用变换规则，得到更有效的等价表达式,规则是启发式的，因为该规则通常能够降低查询求值开销，但并非总是如此,11/28/2024,61,数据库系统概论,代数优化的启发式方法,(,续,),(1),选择运算应当尽可能先做,在优化策略中，这是最重要、最基本的一条,该优化策略又称“推进选择”,将选择运算推进到二目运算之前进行。用语法树的术语：选择尽可能下移,通常，尽管一个关系很大，但是满足某种选择条件的元组的数量却相对较小，并且选择条件越强，满足条件的元组越少,尽早进行选择能够大幅度减少下一步参与运算的元组数目，使得其后的运算可以更加有效的进行,例如，在例,9.2,中，,Q,3,将,Q,2,中的选择推进到自然连接之前进行，其,I/O,大约是,Q,2,的,1/20,11/28/2024,62,数据库系统概论,代数优化的启发式方法,(,续,),如何使用该规则,使用选择的串接律把复杂的合取选择分解成简单选择,利用选择的交换律和选择对二目运算的分配律（,等价变换规则,811,），可以将某些选择推进到二目运算之前,启发式规则,通常能够降低查询求值开销，但并非总是如此,例如， 考虑,F,(,r s,),如果,F,只涉及,s,的属性，用,r,F,(,s,),计算一般更有效,然而，如果,r,和,s,都很小，并且,s,在连接属性上有索引，而在,F,涉及的属性上没有索引，则直接计算,F,(,r s,),可能更有效,其他启发式规则也有类似情况,11/28/2024,63,数据库系统概论,代数优化的启发式方法,(,续,),(2),投影运算应当尽可能先做,与选择尽可能先做类似，投影运算也要尽可能先做,投影可以去掉一些属性，缩短结果元组的长度，使得其后的运算更加有效,如何使用该规则,考虑 ，其中,op,是二目运算,利用投影的串接律（等价变换规则,3,），先将,E,投影到包含,A,1,A,2, ,A,k,和二目运算需要的属性,B,1,B,2, ,B,m,上,然后再利用投影对二目运算的分配律（规则,1215,），可以将某些投影推进到二目运算之前,11/28/2024,64,数据库系统概论,代数优化的启发式方法,(,续,),(3),尽量避免笛卡尔积运算,考虑形如,F,(,E,1,E,2,),表达式,选择条件,F,是,E,1,和,E,2,的属性之间的等值比较时，可以将它转换成连接,E,1,F,E,2,当,F,是,E,1,和,E,2,的公共属性上的等值比较时，忽略重复属性，该连接还可进一步可以转换成自然连接,E,1,E,2,这种特殊情况在实践中经常出现，因为大部分涉及多个关系的查询实际上都涉及这些关系的自然连接。,在例,9.2,中，,Q,2,将,Q,1,中的选择与笛卡尔积结合成自然连接，其,I/O,开销大致降低到,Q,1,的,1%,11/28/2024,65,数据库系统概论,其他启发式优化技术,(1),提取公共子表达式,如果某个子表达式重复出现，并且该子表达式的结果不是很大的关系，从外存中读入它比计算该子表达式所需的时间少得多，则可以采取提取公共子表达式的方法减少子表达式的重复计算,当查询的是视图时，定义视图的表达式就是公共子表达式的情况,(2),流水线技术,所谓流水线计算是指将多个关系运算合并成一个运算流水线，其中前一个运算的输出直接作为下一个运算的输入传送到下一个运算,流水线运算可以减少中间临时文件的产生数量，减少写出和读入临时文件的,I/O,开销，从而提高表达式计算效率,11/28/2024,66,数据库系统概论,其他启发式优化技术,(,续,),流水线容易实现的情况,(1),相继的选择和投影运算同时进行,基本表上的相继选择和投影,一次扫描基本表同时进行选择和投影,整个开销与选择相当,二目运算结果上的相继的选择和投影,直接去掉二目运算结果中不满足选择条件的元组和多余属性,I/O,开销相当于二目运算开销,11/28/2024,67,数据库系统概论,其他启发式优化技术,(,续,),例,9.3,考虑表达式,Q,2,=,Sname,(,Pno,=P001,(Suppliers SP),在做自然连接时，丢弃不满足选择条件,Pno,=P001,的元组，并对满足选择条件的元组直接取属性,Sname,上的值作为结果元组,由于不需要输出和读入自然连接的结果，计算,Q,2,的,I/O,开销从读写,2210,块降低到读,210,块，降低了一个数量级,11/28/2024,68,数据库系统概论,其他启发式优化技术,(,续,),(2),二目运算之前、之后的一目运算和二目运算同时进行,设,E,是形如,E,1,op,E,2,的二目运算构成的表达式，其中,op,是笛卡尔积、连接、自然连接等二目运算符,如果,E,i,是形如,F,(,E,i,),或,L,(,E,i,),的表达式，则,F,(,E,i,),或,L,(,E,i,),和二目运算合并成一个运算流水线,如果还需要对,E,做选择和,/,或投影运算，则选择和,/,或投影运算也并入该运算流水线,11/28/2024,69,数据库系统概论,查询优化的启发式算法,算法,9.1,：查询优化的启发式算法,输入：查询的语法树,输出：优化后的语法树,方法：,(1),分解合取选择：利用选择的串接律，把形如 的合取选择分解成形如 的相继选择,(2),选择下移：利用选择的交换率、选择和投影的交换律、选择对二目运算的分配律，将每个简单选择尽可能向语法树的叶端移动,(3),笛卡尔积转换成连接或自然连接：把笛卡尔积运算和其上方的选择运算合并成连接或自然连接运算,11/28/2024,70,数据库系统概论,查询优化的启发式算法,(,续,),(4),投影下移（添加投影）：反向使用投影的串接律，引进新的投影（参见等价变换规则,3,），并利用投影对二目运算的分配律，将投影尽可能向语法树的叶端移动。,(5),合并相继的选择和投影：相继的投影和选择合并成单个投影和单个合取选择。,(6),建立流水线运算：按照前面介绍的方法，对相继的选择投影建立流水线运算，并对每个二目运算建立流水线。在语法树的相应边上标记流水线,11/28/2024,71,数据库系统概论,查询优化的启发式算法,(,续,),列出,2009001,号学生的成绩,SELECT Grade FROM SC WHERE,Sno,=2009001,语法树如下：,11/28/2024,72,数据库系统概论,查询优化的启发式算法,(,续,),列出每个学生的姓名及其课程成绩,SELECT,Sname, Grade,FROM Student , SC,WHERE,Student.Sno,=,SC.Sno,初始语法树如下：,11/28/2024,73,数据库系统概论,查询优化的启发式算法,(,续,),11/28/2024,74,数据库系统概论,查询优化的启发式算法,(,续,),选择下移，笛卡尔积转换成连接或自然连接,选择,Student.Sno,=,SC.Sno,与其下面的笛卡儿积结合成自然连接，得到下图,11/28/2024,75,数据库系统概论,查询优化的启发式算法,(,续,),因为在上图中，,Sname,只涉及,Student,表，,Grade,只涉及,SC,表，所以根据投影对自然连接的分配率可将上图转换为下图：,注意：为什么在此处又加上了,Sno,？,11/28/2024,76,数据库系统概论,查询优化的启发式算法,(,续,),例,9.5,查询信息工程学院学生选修的所有课程的课程号和课程名可以用如下,SQL,语句：,SELECT DISTINCT,C.Cno,C.Cname,FROM Courses C, SC, Students S,WHERE,C.Cno,=,SC.Cno,AND,SC.Sno,=,S.Sno,AND,S.Dno,=IE,初始语法树如图,9.4(a),所示，其中,S,代表,Students,，,C,代表,Courses,11/28/2024,77,数据库系统概论,查询优化的启发式算法,(,续,),11/28/2024,78,数据库系统概论,查询优化的启发式算法,(,续,),分解合取选择，将初始语法树转换成图,9.3(b),所示的语法树,11/28/2024,79,数据库系统概论,查询优化的启发式算法,(,续,),选择下移,选择条件,SC.Sno,=,C.Sno,不能下移,选择条件,C.Cno,=,SC.Cno,只涉及,Courses,和,SC,中的属性，它可以移到,Courses,和,SC,的笛卡尔积之上,选择条件,S.Dno,=IE,只涉及,Students,的属性，可以下移到,Students,上方,得到的语法树在图,9.4(c),中,11/28/2024,80,数据库系统概论,查询优化的启发式算法,(,续,),11/28/2024,81,数据库系统概论,查询优化的启发式算法,(,续,),笛卡尔积转换成连接或自然连接,选择,C.Cno,=,SC.Cno,和,SC.Sno,=,S.Sno,分别与其下面的笛卡儿积结合成自然连接，得到图,9.4(d),的语法树,11/28/2024,82,数据库系统概论,查询优化的启发式算法,(,续,),添加投影,只有上面的运算需要的属性才是必要的,对于,Courses,和,SC,，自然连接之前将,Courses,投影到,Cno,、,Cname,上，将,SC,投影到,Sno,和,Cno,上,对于,Students,，按,S.Dno,=IE,选择之后只有属性,Sno,是必要的（上面的自然连接需要），我们可以在,S.Dno,=IE,上方投影去掉其它属性。结果在图,9.4(e),中,11/28/2024,83,数据库系统概论,查询优化的启发式算法,(,续,),11/28/2024,84,数据库系统概论,9.6,物理优化,物理优化,物理优化利用元数据中的统计信息，为每个基本运算或流水线运算确定求值算法，产生最终的查询执行计划,涉及底层的存取路径，因此称之为物理优化,基于代价的,vs.,基于启发式规则的物理优化,基于代价的优化估算不同执行策略的代价，并选出具有最小代价的执行计划,基于启发式规则的优化根据某些经验规则，选取较好的执行策略,混合方法,先使用启发式规则，选取若干较优的候选方案，然后估计这些候选方案的执行代价，选出最终的优化方案,11/28/2024,86,数据库系统概论,基于代价的优化,对每个基本运算和流水线运算，考虑所有可能的执行算法，形成多种执行计划，评估每种执行计划的代价，并从中选择最佳的执行计划,代价估计需要的统计量,n,r,：关系,r,的元组数,b,r,：包含关系,r,的块数,l,r,：关系,r,的元组长度（字节数）,V,(,r,A,),：关系,r,在属性,A,上的不同值数目。在查询中经常同时出现的属性集上，也有类似的统计量,f,r,：关系,r,的块因子，即一块能够容纳关系,r,的元组数。当,r,存储在一个物理文件中时，,b,r,=,n,r,/,f,r,min(,r,A,),：关系,r,在属性,A,上的最小值,max(,r,A,),：关系,r,在属性,A,上的最大值,11/28/2024,87,数据库系统概论,基于代价的优化,(,续,),1.,笛卡尔积运算结果的估计,关系,r,和,s,笛卡尔积的元组数,nr,ns,，每个元组长度,l,r,+,l,s,。,2.,选择运算结果的估计,选择运算,F,(,r,),的结果元组长度仍然是,l,r,结果元组的数目依赖于选择条件,(1),A,=,v,(,r,),：结果元组的数目用,n,r,/,V,(,r,A,),估计,(2),A,v,(,r,),如果,v,min(,r,A,),，则结果元组的数目为,0,如果,v,max(,r,A,),，则结果元组的数目为,n,r,否则结果元组的数目可以用下式估计：,11/28/2024,88,数据库系统概论,基于代价的优化,(,续,),(3),合取选择,其中,F,i,（,i,= 1,k,）是上述简单选择条件之一,设,的结果元组的数目为,s,i,，则合取选择的结果元组的数目可以用下式估计,(4),析取选择,其中,F,i,s,i,同上,析取选择的结果元组的数目可以用下式估计,11/28/2024,89,数据库系统概论,基于代价的优化,(,续,),3.,连接运算结果的估计,连接,r,F,s,结果元组长度为,l,r,+,l,s,连接结果的元组数目：由于,r,F,s,=,F,(,r,s,),，因此连接结果的元组数目可以用估计笛卡尔积和估计选择相结合的方法估计,自然连接,r,s,如果公共属性所占的比例不大，其结果元组长度可以保守地用,lr,+,ls,估计，否则需要减去公共属性的长度,结果元组数目,(1),r,和,s,不含公共属性,r s,实际上是,r,和,s,的笛卡儿积，因此其元组数目为,n,r,n,s,11/28/2024,90,数据库系统概论,基于代价的优化,(,续,),(2),一般情况,:,设,r,和,s,的公共属性为,A,对于,r,的一个元组,t,r,在平均情况下,大约可以在,s,中找到,n,s,/,V,(,s,A,),个元组,t,s,满足,t,r,A,=,t,s,A,，因此大约可以产生,n,s,/,V,(,r,A,),个结果元组,这样，,r s,中的元组数目大约为,n,r,n,s,/,V,(,s,A,),。,