查询处理和优化PPT学习教案

1、会计学1 查询处理和优化查询处理和优化 例如：12+64+88=？ 查询优化是相对而言的，可能的执行策略 很多，穷尽代价很大，不能片面追求绝对的 最优。 （12+88）+64=164 第1页/共51页 数据库查询语言的处理过程数据库查询语言的处理过程: : （1）解释方式执行）解释方式执行 应用程序 优化占执行时间！ 第2页/共51页 (2)(2)编译方式编译方式 优化不 占执行时间！ 第3页/共51页 对于常见的例行事务，编译方式可提高性对于常见的例行事务，编译方式可提高性 能。能。 对于简短的即时查询，解释方式灵活实用。对于简短的即时查询，解释方式灵活实用。 解释方式和编译方式各适用于什么

2、情况？解释方式和编译方式各适用于什么情况？ 第4页/共51页 第5页/共51页 6.2 6.2 代数优化代数优化 代数优化对查询进行等效变换，以减少执行开代数优化对查询进行等效变换，以减少执行开 销。销。 代数优化的原则是代数优化的原则是尽量减小查询过程中间结果尽量减小查询过程中间结果 的大小的大小。 选择、投影操作通常能够有效地减小关系的大选择、投影操作通常能够有效地减小关系的大 小。小。 连接、迪卡尔乘积和并操作容易生成较大的查询中连接、迪卡尔乘积和并操作容易生成较大的查询中 间结果。间结果。 因此，因此，先做选择、投影先做选择、投影；先做小关系间的连接，先做小关系间的连接， 再做大关系的

3、连接再做大关系的连接；甚至需要先找出查询中的公共甚至需要先找出查询中的公共 表达式表达式，以避免重复运算。，以避免重复运算。 第6页/共51页 ).)(.()( 21 .2 1 RR cncccnANDcANDc 1. )()( 1221 RR cccc 2. n listlistlistlist listlistlist RR n . ),().)(.( 21 1 21 3. ,.,2, 1)( ) )()( ,.,2, 1,.,2, 1 AnAACAttr RR AnAAccAnAA 4. 第7页/共51页 5. R JN S = S JN RR JN S = S JN R Attr(R)

4、Attr(c) S JN (R)(S) JN ( ， cc R 6. )()2(),() 1( ),()() ( 212 1 SAttrcAttrRAttrcAttr SJNRSJNR cccANDc 7. 第8页/共51页 LcAttr SJNRSJNR SAttrBBRAttr BB BmBcAnAcL mn mn )( )()() ( )(,.,),(A,.,A ,.,A,.,AL ,.,1,.,1 11 11 式中 则 其中， 属性集 8. )( )() (,SRSR ccc 则 9. )( )() (,SRSR LLL 则 10. 第9页/共51页 ) (S ) ( , TRTSR

5、JN 则 11. 第10页/共51页 设有设有S(S(供应商供应商) )，P(P(零件零件) )，SP(SP(供应关系供应关系) )三个关系，关系三个关系，关系 模式如下：模式如下： S(SNUM,SNAME,CITY) S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) P(PNUM,PNAME,WEIGHT,SIZE) SP(SNUM,PNUM,DEPT,QUAN) SP(SNUM,PNUM,DEPT,QUAN) 有如下查询有如下查询 Q : Q : SELECTSELECT SNAME SNAME FROMFROM S,P,SP S,P,SP WHE

6、REWHERE 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 10000 AND SP.QUAN 10000 第11页/共51页 第12页/共51页 Q : SELECT SNAME FROM S,P,SP WHERE S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND S.CIT

7、Y = NANJING AND P.PNAME = BOLT AND SP.QUAN 10000 C S p SP SNAME 原始查询树原始查询树 第13页/共51页 SNAME C S p SP PNUMPPNUMSP. SNUMSPSNUMS. .NANJINGCITYS 10000.QUANSP .BOLTPNAMEP SNAME S SP p 选择操作尽量下压选择操作尽量下压 .NANJINGCITYS SNUMSPSNUMS. 10000.QUANSP .BOLTPNAMEP PNUMPPNUMSP. 原始查询树原始查询树 第14页/共51页 先连接小关系先连接小关系 S,P,SP

8、 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 jj+1 else if R(i)AS(j)B then ii+1 else /* R(i)A=S(j)B，输出连接元组输出连接元组*/ 第35页/共51页 输出输出至至T; /*输出输出R(i)和和S中除中除S(j)外外的其他元组所组成的连接元组的其他元组所组成的连接元组 */ lj+1; While(l m)

9、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; 问题：等值匹配对使用排序问题：等值匹配对使用排序 归并法进行连接操作的效率归并法进行连接操作的效率 有什么影响？有什么影响？ 第36页/共51页 p个 q个 R.A 2 S.B 2 2 2 2 2 2 2 . . . . . . 注意等值的扫描次数（假设注意等值的扫描次数（假设p q）：）： 1+

10、( 1+(q-1)+(p-1)+1+(q-2)+(p-2)+q-1)+(p-1)+1+(q-2)+(p-2)+ +1+( +1+(q-p)+(p-p)q-p)+(p-p) =(p+q-1)+(p+q-2q+1)/2=(p+q-1)+(p+q-2q+1)/2* *p p =p=p* *q q O(pq)O(pq) 第37页/共51页 4).4).散列连接法散列连接法 第38页/共51页 关键在于建立一个供连接用的散列文件。关键在于建立一个供连接用的散列文件。 可以在桶（散列文件）中不填入可以在桶（散列文件）中不填入R R、S S的实际元组，的实际元组， 而是代之以元组的而是代之以元组的tidti

11、d，从而大大的缩小散列文件，从而大大的缩小散列文件， 使其有可能在内存中建立，而仅需对使其有可能在内存中建立，而仅需对R R、S S各扫描一次。各扫描一次。 建立散列文件需要对R、S各扫描一次，且关系R和S一般不会对连接属性进行簇集。故而，每向散列文件加入一个元组，都需要一次I/O操作。 如何减少I/O次数? 第39页/共51页 扫描R和S时，取出A(R)、B(S)，附在相应的tid后，连接时以桶为单位，按A(R)=B(S)找出匹配元组的tid对。 问题：似乎多此一举！匹配元组的tid一定在同一桶中！为什么还要按A(R)=B(S)找出匹配元组？这么做有必要么？ 注意：A=B h(A)=h(B)

12、，但不一定有： h(A)=h(B) A=B 第40页/共51页 在取实际元组时，为减少物理块访问，可将各桶中，匹配元组的tid按块分类，一次集中取出同一块中所需的所有元组，当然这需要较大的内存开销。 第41页/共51页 第42页/共51页 第43页/共51页 用排序法消除重复元组用排序法消除重复元组 对关系对关系R R的每个元组的每个元组t t，生成生成tt，并，并 存于存于T T中；中；/ /* * T T 是未消除重复元组的投影结果是未消除重复元组的投影结果* */ / If If 含有含有R R的主键的主键 then Tthen TT T elseT elseT按所有属性排序；按所有属性

13、排序； i i1,j1,j2;2; while(i while(i n)n) do do输出元组输出元组T T(i)(i)到到T;T; 第44页/共51页 while T(i)= T(j) do jj+1; /*消除重复元组，设有伪元组Tn+1Tn*/ ij,ji+1; 第45页/共51页 设关系设关系R、S并兼容，对并兼容，对R、S进行并（交、差）操作，进行并（交、差）操作， 可以先将可以先将R和和S按同一属性（通常选用主键）排序，然后按同一属性（通常选用主键）排序，然后 扫描两个关系，选出所需的元组。扫描两个关系，选出所需的元组。 笛卡尔乘积将两个关系的元组无条件地互相拼接，笛卡尔乘积将两

14、个关系的元组无条件地互相拼接，一一 般用嵌套循环法实现，做起来很费时，结果要比参与运般用嵌套循环法实现，做起来很费时，结果要比参与运 算的关系大的多。应尽量少用！算的关系大的多。应尽量少用！ 第46页/共51页 散列是上述并交差操作的另一种求解方法散列是上述并交差操作的另一种求解方法： 将关系将关系R散列到一个散列文件中，再将散列到一个散列文件中，再将S散列到同一文散列到同一文 件中。同时检查桶中有无重复元组。对于并，不再插入件中。同时检查桶中有无重复元组。对于并，不再插入 重复元组；对于交，选取重复元组；对于差，从桶中取重复元组；对于交，选取重复元组；对于差，从桶中取 消与消与S重复的元组。

15、重复的元组。 第47页/共51页 有时，多个操作组合起来同时进行，如投影和选择操有时，多个操作组合起来同时进行，如投影和选择操 作组合起来执行（消除重复元组另外单独进行），可提作组合起来执行（消除重复元组另外单独进行），可提 高效益。高效益。 还可以在更大范围内，将多个操作组合起来执行。还可以在更大范围内，将多个操作组合起来执行。 RS 12 1 2 第48页/共51页 假设连接用嵌套循环法，假设连接用嵌套循环法，R为外关系，为外关系，S为内关系，为内关系， R的选择、投影可在扫描的选择、投影可在扫描R时执行，时执行，S的选择、投影可的选择、投影可 在首次扫描在首次扫描S时执行，并将选择、投影的结果存入临时执行，并将选择、投影的结果存入临 时文件，之后各轮只需扫描临时文件即可。时文件，之后各轮只需扫描临时文件即可。 最后一个投影操作，可在生成连接结果的同时进最后一个投影操作，可在生成连接结果的同时进 行。行。 第49页/共51页 在执行前进行优化称为在执行前进行优化称为静态优化静态优化，只能利用统，只能利用统 计数据，有时不一定准。计数据，有时不一定准。 在