第6章查询理和优化

1、第第6 6章章 查询处理和优化查询处理和优化6.1 6.1 引言引言查询处理查询处理查询优化查询优化 查询优化查询优化是是查询处理查询处理中的重要一环，对关系中的重要一环，对关系db尤其如此。尤其如此。 从查询语句出发，到获得查询从查询语句出发，到获得查询结果的处理过程。结果的处理过程。 dbms对描述性语言表达的查对描述性语言表达的查询语句进行分析，为其确定合理、有效的执行询语句进行分析，为其确定合理、有效的执行策略和步骤的过程。策略和步骤的过程。 例如：例如：12+64+88=？ 查询优化是查询优化是相对而言相对而言的，可能的执行策略的，可能的执行策略很多，穷尽代价很大，不能片面追求绝对的

2、很多，穷尽代价很大，不能片面追求绝对的最优。最优。 （12+88）+64=164数据库查询语言的处理过程数据库查询语言的处理过程: :（1）解释方式执行）解释方式执行应用程序应用程序优化占执优化占执行时间！行时间！(2)(2)编译方式编译方式优化不优化不占执行时占执行时间！间！对于常见的例行事务，编译方式可提高性能。对于常见的例行事务，编译方式可提高性能。对于简短的即时查询，解释方式灵活实用。对于简短的即时查询，解释方式灵活实用。解释方式和编译方式各适用于什么情况？解释方式和编译方式各适用于什么情况？6.2 6.2 代数优化代数优化 代数优化对查询进行等效变换，以减少执行开销。代数优化对查询进

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

4、ccnandcandc1.)()(1221rrcccc2.nlistlistlistlistlistlistlistrrn.),().)(.(211213.,.,2, 1)() )()(,.,2, 1,.,2, 1anaacattrrranaaccanaa4.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.lcattrsjnrsjnrsattrbbrattrbbbmbcanaclmnm

5、n)()()() ()(,.,),(a,.,a,.,a,.,al,.,1,.,11111式中则其中，属性集8.)( )() (,srsrccc则9.)( )() (,srsrlll则10.) (s ) (,trtsrjn则11.范例范例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,weight,size) sp(s

6、num,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 10000 and sp.q

7、uan 10000 nsqlsql语句转化为原始查询树语句转化为原始查询树 select select from from where where 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原始查询树原始查询树snamecspsppnumppnumsp.snumspsnums.nanjingcitys10000.quansp.boltpnamepsnames

8、spp选择操作尽量下压选择操作尽量下压.nanjingcityssnumspsnums.10000.quansp.boltpnameppnumppnumsp.原始查询树原始查询树先连接小关系先连接小关系 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 jj+1 else if r(i)as(j)b then ii+1 else /* r(i)a=s(

9、j)b，输出连接元组输出连接元组*/ 输出输出至至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; 问题：等值匹配对使用排序问题：等值匹配对使用排序归并法进行连接操作的效率归并法进行连接操作的效率有什么影响？有什么影

10、响？ p个个 q个个 r.a 2 2s.b 2 2 2 2 2 2 2 2 2 2 2 2 2 2 . . . . . . 注意等值的扫描次数（假设注意等值的扫描次数（假设p q）：）： 1+(q-1)+(p-1)+1+(q-2)+(p-2)+ 1+(q-1)+(p-1)+1+(q-2)+(p-2)+ +1+(q-p)+(p-p) +1+(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)4).4).散列连接法散列连接法 关键在于建立一个供连接用的散列文件。关键在于建立一个供连接用的散列

11、文件。 可以在桶（散列文件）中不填入可以在桶（散列文件）中不填入r r、s s的实际元组，的实际元组，而是代之以元组的而是代之以元组的tidtid，从而大大的缩小散列文件，从而大大的缩小散列文件，使其有可能在内存中建立，而仅需对使其有可能在内存中建立，而仅需对r r、s s各扫描一次。各扫描一次。 建立散列文件需要对建立散列文件需要对r r、s s各扫描一次，且关系各扫描一次，且关系r r和和s s一般不会对连接属性进行簇集。故而，每向散列文一般不会对连接属性进行簇集。故而，每向散列文件加入一个元组，都需要一次件加入一个元组，都需要一次i/oi/o操作。操作。如何减少如何减少i/oi/o次数次

12、数? ? 扫描扫描r r和和s s时，取出时，取出 a a(r)(r)、 b b(s)(s)，附在相应的，附在相应的tidtid后，连接时以桶为单位，按后，连接时以桶为单位，按 a a(r)=(r)= b b(s)(s)找出匹配元组找出匹配元组的的tidtid对。对。 问题：问题：似乎多此一举！匹配元组的似乎多此一举！匹配元组的tidtid一定在同一一定在同一桶中！为什么还要按桶中！为什么还要按 a a(r)=(r)= b b(s)(s)找出匹配元组？这找出匹配元组？这么做有必要么？么做有必要么？ 注意：注意：a=b a=b h(a)=h(b) h(a)=h(b)，但不一定有：，但不一定有：

13、h(a)=h(b) h(a)=h(b) a=b a=b 在取实际元组时，为减少物理块访问，可将各在取实际元组时，为减少物理块访问，可将各桶中，匹配元组的桶中，匹配元组的tidtid按块分类，一次集中取出同按块分类，一次集中取出同一块中所需的所有元组，当然这需要较大的内存一块中所需的所有元组，当然这需要较大的内存开销。开销。用排序法消除重复元组用排序法消除重复元组 对关系对关系r r的每个元组的每个元组t t，生成，生成tt，并，并存于存于t t中；中；/ /* * t t 是未消除重复元组的投影结果是未消除重复元组的投影结果* */ /if if 含有含有r r的主键的主键 then tthe

14、n tt t elset elset按所有属性排序；按所有属性排序； i i1,j1,j2;2; while(i while(i n)n) do do输出元组输出元组t t(i)(i)到到t;t; while twhile t(i)= t(i)= t(j) do j(j) do jj+1;j+1;/ /* *消除重复元组，设有伪元组消除重复元组，设有伪元组t tn+1n+1 t tnn* */ /i ij,jj,ji+1;i+1; 常用集合操作：笛卡尔乘积、并、交、差等。常用集合操作：笛卡尔乘积、并、交、差等。 设关系设关系r、s并兼容，对并兼容，对r、s进行并（交、差）操作，进行并（交、差）

15、操作，可以先将可以先将r和和s按同一属性（通常选用主键）排序，然后按同一属性（通常选用主键）排序，然后扫描两个关系，选出所需的元组。扫描两个关系，选出所需的元组。 笛卡尔乘积将两个关系的元组无条件地互相拼接，笛卡尔乘积将两个关系的元组无条件地互相拼接，一一般用嵌套循环法实现，做起来很费时，结果要比参与运般用嵌套循环法实现，做起来很费时，结果要比参与运算的关系大的多。应尽量少用！算的关系大的多。应尽量少用！ 散列是上述并交差操作的另一种求解方法散列是上述并交差操作的另一种求解方法： 将关系将关系r散列到一个散列文件中，再将散列到一个散列文件中，再将s散列到同一文散列到同一文件中。同时检查桶中有无

16、重复元组。对于并，不再插入件中。同时检查桶中有无重复元组。对于并，不再插入重复元组；对于交，选取重复元组；对于差，从桶中取重复元组；对于交，选取重复元组；对于差，从桶中取消与消与s重复的元组。重复的元组。 有时，多个操作组合起来同时进行，如投影和选择操有时，多个操作组合起来同时进行，如投影和选择操作组合起来执行（消除重复元组另外单独进行），可提作组合起来执行（消除重复元组另外单独进行），可提高效益。高效益。 还可以在更大范围内，将多个操作组合起来执行。还可以在更大范围内，将多个操作组合起来执行。rs1212 假设连接用嵌套循环法，假设连接用嵌套循环法，r为外关系，为外关系，s为内关系，为内关系，r的选择、投影可在扫描的选择、投影可在扫描r时执行，时执行，s的选择、投影可的选择、投影可在首次扫描在首次扫描s时执行，并将选择、投影的结果存入临时执行，并将选择、投影的结果存入临时文件，之后各轮只需扫描临时文件即可。时文件，之后各轮只需扫描临时文件即可。 最后一个投影操作，可在生成连接结果的同时进最后一个投影操作，可在生成连接结果的同时进行。行。 在执行前进行优化称为在执行前进行优化称为静态优化静态优化，只能