第 查询处理和优化PPT课件

1、数据库查询语言的处理过程数据库查询语言的处理过程: :（1）解释方式执行）解释方式执行应用程序优化占执行时间！第1页/共48页(2)(2)编译方式编译方式优化不占执行时间！第2页/共48页对于常见的例行事务，编译方式可提高性能。对于常见的例行事务，编译方式可提高性能。对于简短的即时查询，解释方式灵活实用。对于简短的即时查询，解释方式灵活实用。解释方式和编译方式各适用于什么情况？解释方式和编译方式各适用于什么情况？第3页/共48页第4页/共48页6.2 6.2 代数优化代数优化 代数优化对查询进行等效变换，以减少执行开销。代数优化对查询进行等效变换，以减少执行开销。 代数优化的原则是代数优化的原

2、则是尽量减小查询过程中间结果的尽量减小查询过程中间结果的大小大小。 选择、投影操作通常能够有效地减小关系的大小。选择、投影操作通常能够有效地减小关系的大小。连接、迪卡尔乘积和并操作容易生成较大的查询中连接、迪卡尔乘积和并操作容易生成较大的查询中间结果。间结果。 因此，因此，先做选择、投影先做选择、投影；先做小关系间的连接，先做小关系间的连接，再做大关系的连接再做大关系的连接；甚至需要先找出查询中的公共表甚至需要先找出查询中的公共表达式达式，以避免重复运算。，以避免重复运算。第5页/共48页常用变换规则常用变换规则).)(.()(21 .2 1RRcncccnANDcANDc1.)()(1221

3、RRcccc2.nlistlistlistlistlistlistlistRRn.),().)(.(211213.,.,2, 1)() )()(,.,2, 1,.,2, 1AnAACAttrRRAnAAccAnAA4.第6页/共48页5.R JN S = S JN RR JN S = S JN RAttr(R)Attr(c)S JN (R)(S) JN (，ccR6.)()2(),() 1(),()() (212 1SAttrcAttrRAttrcAttrSJNRSJNRcccANDc7.第7页/共48页LcAttrSJNRSJNRSAttrBBRAttrBBBmBcAnAcLmnmn)()(

4、)() ()(,.,),(A,.,A,.,A,.,AL,.,1,.,11111式中则其中，属性集8.)( )() (,SRSRccc则9.)( )() (,SRSRLLL则10.第8页/共48页) (S ) (,TRTSRJN则11.第9页/共48页范例范例p118p118例例6-16-1 设有设有S(S(供应商供应商) )，P(P(零件零件) )，SP(SP(供应关系供应关系) )三个关系，关系模三个关系，关系模式如下：式如下： S(SNUM,SNAME,CITY) S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) P(PNUM,PNAME,WEIGH

5、T,SIZE) SP(SNUM,PNUM,DEPT,QUAN) SP(SNUM,PNUM,DEPT,QUAN)有如下查询有如下查询Q : Q : SELECTSELECT SNAME SNAME FROMFROM S,P,SP S,P,SP WHEREWHERE S.SNUM = SP.SNUM S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND SP.PNUM = P.PNUM AND S.CITY = AND S.CITY = NANJINGNANJING AND P.PNAME = AND P.PNAME = BOLTBOLT AND SP.QUAN 10

6、000 AND SP.QUAN 10000 第10页/共48页 SQLSQL语句转化为原始查询树语句转化为原始查询树 Select Select From From Where Where 第11页/共48页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 CSpSPSNAME原始查询树原始查询树第12页/共48页SNAMECSpSPPNUMPPNUMSP.SNUMSPSNUMS.NA

7、NJINGCITYS10000.QUANSP.BOLTPNAMEPSNAMESSPp选择操作尽量下压选择操作尽量下压.NANJINGCITYSSNUMSPSNUMS.10000.QUANSP.BOLTPNAMEPPNUMPPNUMSP.原始查询树原始查询树第13页/共48页先连接小关系先连接小关系 S,P,SP S,P,SP经选择后得经选择后得S S、P P、SPSP，估算大小：估算大小： |S|=|S|/NCITY |P|=|P|/NPNAME |SP|=|SP|(Vmax-10000)/(Vmax-Vmin) 设设| |S S|P|P|, |SP|, |SP|P|,S(j)B then j

8、j+1 else if R(i)AS(j)B then ii+1 else /* R(i)A=S(j)B，输出连接元组输出连接元组*/ 第33页/共48页输出输出至至T;/*输出输出R(i)和和S中除中除S(j)外外的其他元组所组成的连接元组的其他元组所组成的连接元组 */lj+1;While(l m) and (R(i)A=S(l)B) do输出输出至至T; ll+1;/*输出输出S(j)和和R中除中除R(i)外外的其他元组所组成的连接元组的其他元组所组成的连接元组 */ki+1;While(k n) and (R(k)A=S(j)B) do输出输出至至T; kk+1;ii+1,jj+1;

9、第34页/共48页4).4).散列连接法散列连接法第35页/共48页 关键在于建立一个供连接用的散列文件。关键在于建立一个供连接用的散列文件。 可以在桶（散列文件）中不填入可以在桶（散列文件）中不填入R R、S S的实际元组，的实际元组，而是代之以元组的而是代之以元组的tidtid，从而大大的缩小散列文件，从而大大的缩小散列文件，使其有可能在内存中建立，而仅需对使其有可能在内存中建立，而仅需对R R、S S各扫描一次。各扫描一次。 建立散列文件需要对R、S各扫描一次，且关系R和S一般不会对连接属性进行簇集。故而，每向散列文件加入一个元组，都需要一次I/O操作。如何减少I/O次数?第36页/共4

10、8页 扫描R和S时，取出A(R)、B(S)，附在相应的tid后，连接时以桶为单位，按A(R)=B(S)找出匹配元组的tid对。第37页/共48页 在取实际元组时，为减少物理块访问，可将各桶中，匹配元组的tid按块分类，一次集中取出同一块中所需的所有元组，当然这需要较大的内存开销。第38页/共48页第39页/共48页第40页/共48页用排序法消除重复元组用排序法消除重复元组 对关系对关系R R的每个元组的每个元组t t，生成生成tt，并，并存于存于T T中；中；/ /* * T T 是未消除重复元组的投影结果是未消除重复元组的投影结果* */ /If If 含有含有R R的主键的主键 then

11、Tthen TT T elseT elseT按所有属性排序；按所有属性排序； i i1,j1,j2;2; while(i while(i n)n) do do输出元组输出元组T T(i)(i)到到T;T; 第41页/共48页while T(i)= T(j) do jj+1;/*消除重复元组，设有伪元组Tn+1Tn*/ij,ji+1; 第42页/共48页常用集合操作：笛卡尔乘积、并、交、差等。常用集合操作：笛卡尔乘积、并、交、差等。 设关系设关系R、S并兼容，对并兼容，对R、S进行并（交、差）操作，进行并（交、差）操作，可以先将可以先将R和和S按同一属性（通常选用主键）排序，然后按同一属性（通常

12、选用主键）排序，然后扫描两个关系，选出所需的元组。扫描两个关系，选出所需的元组。 笛卡尔乘积将两个关系的元组无条件地互相拼接，笛卡尔乘积将两个关系的元组无条件地互相拼接，一一般用嵌套循环法实现，做起来很费时，结果要比参与运般用嵌套循环法实现，做起来很费时，结果要比参与运算的关系大的多。应尽量少用！算的关系大的多。应尽量少用！第43页/共48页 散列是上述并交差操作的另一种求解方法散列是上述并交差操作的另一种求解方法： 将关系将关系R散列到一个散列文件中，再将散列到一个散列文件中，再将S散列到同一文散列到同一文件中。同时检查桶中有无重复元组。对于并，不再插入件中。同时检查桶中有无重复元组。对于并

13、，不再插入重复元组；对于交，选取重复元组；对于差，从桶中取重复元组；对于交，选取重复元组；对于差，从桶中取消与消与S重复的元组。重复的元组。第44页/共48页 有时，多个操作组合起来同时进行，如投影和选择操有时，多个操作组合起来同时进行，如投影和选择操作组合起来执行（消除重复元组另外单独进行），可提作组合起来执行（消除重复元组另外单独进行），可提高效益。高效益。 还可以在更大范围内，将多个操作组合起来执行。还可以在更大范围内，将多个操作组合起来执行。RS1212第45页/共48页 假设连接用嵌套循环法，假设连接用嵌套循环法，R为外关系，为外关系，S为内关系，为内关系，R的选择、投影可在扫描的选择、投影可在扫描R时执行，时执行，S的选择、投影可的选择、投影可在首次扫描在首次扫描S时执行，并将选择、投影的结果存入临时执行，并将选择、投影的结果存入临时文件，之后各轮只需扫描临时文件即可。时文件，之后各轮只需扫描临时文件即可。 最后一个投影操作，可在生成连接结果的同时进最后一个投影操作，可在生成连接结果的同时进行。行。第46页/共48页 在执行前进行优化称为在执行前进行优化称为静态优化静态优化，只能利用统计，只能利用统计数据，有时不一定准。数据，有时不一定准。 在查询执行时进行优化称为在查询执行时进行优化称为动态优化动态优化，用实际执，用实际执行结果估算代价，比较符合实际，但每次执行都