第6-查询处理和优化

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,#,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,例如：,12+64+88=？,查询优化是,相对而言,的，可能的执行策略很多，穷尽代价很大，不能片面追求绝对的最优。,（12+88）+64=164,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,数据库查询语言的处理过程,:,（1）解释方式执行,解释执行,查询语句,DBMS,BEGIN TRAN,查询语句,END,应用程序,查询请求,查询结果,优化占执行时间！,查询语句,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,(2)编译方式,BEGIN TRAN,查询语句,END,应用程序,CALL AM(,参数),AM,依赖因素,访问模块,AM,预编译,编译和连接,目标码,执行,优化不,占执行时间！,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,对于常见的例行事务，编译方式可提高性能。,对于简短的即时查询，解释方式灵活实用。,解释方式和编译方式各适用于什么情况？,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,代数优化,对查询语句进行变换不涉及存取路径,物理优化,根据存取路径选择合理的存取策略进行优化,规则优化,仅根据启发式规则选择执行的策略进行优化,代价估算优化,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,6.2 代数优化,代数优化对查询进行等效变换，以减少执行开销。,代数优化的原则是,尽量减小查询过程中间结果的大小,。,选择、投影操作通常能够有效地减小关系的大小。,连接、迪卡尔乘积和并操作容易生成较大的查询中间结果。,因此，,先做选择、投影,；,先做小关系间的连接，再做大关系的连接,；,甚至需要先找出查询中的公共表达式,，以避免重复运算。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,常用变换规则,1.,2.,3.,4.,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,5.,R JN S=S JN R,6.,7.,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,8.,9.,10.,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,注意：规则11中,，,对于连接运算，可能出现,S,与,T,之间无连接条件的情况，此时的连接运算成为迪卡尔乘积。,例如：(,R JN,c1,S)JN,c2,T,式中，,Attr.(c1),Attr.(R),Attr.(S),Attr.(c2),Attr.(R),Attr.(T),而,S,和,T,之间没有连接条件。可改写为：,R JN,c1 AND c2,(,S,T),11.,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,范例,p118,例6-1,设有,S(,供应商)，,P(,零件)，,SP(,供应关系)三个关系，关系模式如下：,S(SNUM,SNAME,CITY),P(PNUM,PNAME,WEIGHT,SIZE),SP(SNUM,PNUM,DEPT,QUAN),有如下查询,Q:,SELECT,SNAME,FROM,S,P,SP,WHERE,S.SNUM=SP.SNUM,AND SP.PNUM=P.PNUM,AND S.CITY=,NANJING,AND P.PNAME=,BOLT,AND SP.QUAN 10000,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,SQL,语句转化为原始查询树,Select,From,Where,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,Q,可用右图所示的原始查询树表示：,Q:,SELECT,SNAME,FROM,S,P,SP,WHERE,S.SNUM=SP.SNUM,AND SP.PNUM=P.PNUM,AND S.CITY=NANJING,AND P.PNAME=BOLT,AND SP.QUAN 10000,原始查询树,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,选择操作下压,选择操作尽量下压,原始查询树,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,先连接小关系,S,P,SP,经选择后得,S,、P,、SP,，,估算大小：,|,S,|=|S|/,N,CITY,|P,|=|P|/,N,PNAME,|SP,|=|SP|,(,V,max,-10000)/(,V,max,-,V,min,),设|,S,|P,|,|SP,|,集合,IN,EXISTS,NOT EXISTS,复合,AND,OR,选择操作的执行策略与选择条件、可用的存取路径以及选取的元组数在整个关系中所占的比例有关。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,实现方法：顺序扫描、尽量利用散列索引等方法。,选择操作选择存取路径的启发式规则：,（1）对于小关系，,顺序扫描,。,（2）若无索引、散列等存取路径可用，或估计选取的元组数占关系的比例较大（大于20%）且有关属性上无簇集索引，,顺序扫描,。,（3）对于主键的等值选择，优先选用主键的索引或散列。,（4）对于非主键的等值选择，若选取的元组数占关系的比例较小（小于20%），可以用无序索引；,否则只能用簇集索引或顺序扫描,。（,为什么？,）,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,（5）.对于范围条件，先通过索引找到范围的边界，再通过索引的顺序集沿相应方向搜索，,如中选的元组数在关系中所占比例较大，宜采用簇集索引或顺序扫描,。,（6）对于用,AND,连接的合取选择条件：,优先选用多属性索引,若有多个可用的次索引，可用预查找处理，最后做其余条件检查,个别条件可用（3）（4）（5）之一，求得相应组，再将这些元组用其它条件筛选,顺序扫描,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,（7）用,OR,连接的析取选择条件，尚无好的方法。只能按其中各个条件分别选出一个元组集，再求这些元组集的并。,在,OR,连接的诸条件中，只要有一个条件无合适的存取路径，就只能用顺序扫描！,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,6.3.2,连接操作的实现和优化,连接开销较大，为查询优化的重点，这里主要讨论二元连接（,Two Way Join）。,实现方法,1.嵌套循环法（,nested loop）,2.,利用索引或散列寻找匹配元组法,3.排序归并,4.,散列连接法,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,1).嵌套循环,关系,R,与,S,进行连接操作，最原始的办法是取,R,的一个元组，与,S,的所有元组比较，凡是满足连接条件的元组就进行连接并且作为结果输出。然后再取,R,的下一个元组，和,S,的所有元组比较，直到,R,的所有元组比较完为止。,R,S,R.A=S.B,R(n,个),S(m,个),i,j,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,嵌套循环算法,/*设,R,有,n,个元组，,S,有,m,个元组*/,i:=1,j:=1;,while(in),dowhile(jm),doif R(i)A=S(j)B,then,输出,至,T;,j:=j+1,j:=1,i:=i+1,T,为,R,和,S,连接的结果,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,R,为外关系（,outer relation,）,S,为内关系（,inner relation,）。,事实上，,关系是以物理块为单位取到内存,，设,R,和,S,各有一缓冲块,，,P,R,为,R,的块因子（每块中所含的元组数）。则,R,每次,I/O,取,P,R,个元组，可改进上述算法，使,S,扫描一次可以与,R,的,P,R,个元组比较，那么,S,的扫描次数为,b,R,=n/P,R,。,R,S,物理块,物理块,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,假设，,b,R,和,b,S,分别为,关系,R,和关系,S,占用,物理块的数目(,b,R,=n/P,R,)，,n,B,为可供连接使用的缓冲块数。,若将其中的,n,B,-1,块作为外关系缓冲块，1块作为内关系缓冲块,。,则以,R,为外关系、,S,为内关系，用嵌套循环法进行连接所需访问的物理块数为,b,R,+b,R,/(n,B,-1)*b,S,，,对应最小,I/O,值,。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,2).,利用索引或散列寻找匹配元组法,在嵌套循环法中，内关系上要做多次顺序扫描，,若内关系上有合适的存取路径（连接属性上的索引散列等）,，可以避免内关系上的顺序扫描，以减少,I/O,次数。,当每次循环所选的匹配元组数在内关系中占有较大比例（例如超过,15%）,时，用无序索引甚至还不如用顺序扫描的方法。,内关系的连接属性上有簇集索引时，索引对减少连接所需,I/O,次数的作用最明显。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,3).排序归并,如果,R,和,S,按连接属性排序，可按序比较,R.A,和,S.B,以找出匹配元组。,跳过,R.A,2,S.B,1,3,2,3,3,5,3,7,6,8,7,跳过,跳过,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,算法：,R,按属性,A,排序 /*设,R,有,n,个元组*/,S,按属性,B,排序/*设,S,有,m,个元组*/,i,1,j,1;,While(i,n,)and(j,m,),doif R(i)AS(j)B,then j,j+,1,else if R(i)AS(j)B,then i,i+,1,else,/*R(i)A=S(j)B,，,输出连接元组,*/,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,输出至,T;,/*,输出,R(i),和,S,中除,S(j),外,的其他元组所组成的连接元组*/,lj+,1;,While(l,m,)and(R(i)A=S(l)B),do,输出至,T;,l,l+1;,/*,输出,S(j),和,R,中除,R(i),外,的其他元组所组成的连接元组*/,ki+,1;,While(k,n,)and(R(k)A=S(j)B),do,输出至,T;,k,k,+1;,i,i+1,j,j+1;,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,4).,散列连接法,连接属性,R.A,和,S.B,应具有相同的值域，用相同的散列函数，把,R,和,S,散列到同一散列文件中。符合连接条件的元组必然在同一通中（,注意：同一桶中的元组未必都满足连接条件,）。只需把桶中的匹配元组取出即可获得连接结果。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,关键在于建立一个供连接用的散列文件。,可以在桶（散列文件）中不填入,R、S,的实际元组，而是代之以元组的,tid,，从而大大的缩小散列文件，使其有可能在内存中建立，而仅需对,R、S,各扫描一次。,建立散列文件需要对,R、S,各扫描一次，且关系,R,和,S,一般不会对连接属性进行簇集。故而，每向散列文件加入一个元组，都需要一次,I/O,操作。,如何减少,I/O,次数?,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,扫描,R,和,S,时，取出,A,(R),、,B,(S)，,附在相应的,tid,后，连接时以桶为单位，按,A,(R),=,B,(S),找出匹配元组的,tid,对。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,在取实际元组时，为减少物理块访问，可将各桶中，匹配元组的,tid,按块分类，一次集中取出同一块中所需的所有元组，当然这需要较大的内存开销。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,连接方法的启发式规则,1）两个关系都已按连接属性排序，则优先用排序归并法；,两个关系中已有一个关系按连接属性排序，另一个关系较,小，也可先对未排序关系按连接属性排序，再用排序归并,法。,2）两个关系中有一个关系在连接属性上有索引（特别是,簇集索引）或散列，可以另一关系为外关系，顺序扫描，,并利用内