分解查询的优化方法全面分析

　　第一节中介绍了通过关系代数表达式变换对查询优化的方法。但是我们并不知道每一步变换是否真会得到好处，也就是不知道是否真会使执行查询的代价降低。这一节中我们介绍另一种优化方法。这种方法是把查询分解执行，根据对所付出代价的多少来决定如何分解，如何执行。这套方法是E，Wong等人提出的，他们在实现INGRES中采用了这种方法。
　　为介绍方便，先给出一个例子，我们在整节中都要用到它。
　　
　　* 例12.3
　　关系：供给商 SUPPLIER(S#,SNAME,CITY)
　　零件 PARTS(P#,PNAME,SIZE)
　　项目 PROJECT(J#,JNAME,CITY)
　　库存 INVENTORY(S#,P#,QOH)
　　供货情况 SUPPLY(S#,J#,P#,QU)
　　其中QOH：现有数量　　 QU：要用的数量
　　
　　查询：
　　RANGE OF (S,P,J,V,Y) IS (SUPPLIER, PARTS, PROJECT, INVENTORY, SUPPLY)
　　RETRIEVE (S.SNAME)
　　WHERE (S.S#=V.S#) AND (S.S#=Y.S#) AND (S.CITY=J.CITY)
　　AND (P.P#=V.P#) AND (V.P#=Y.P#) AND (J.J#=Y.J#)
　　AND (V.QOH>Y.QU) AND (P.PNAME='BOLTS')
　　AND (P.SIZE='#6') AND (Y.QO>100)
　　这个查询是找出：所有为同城市中某些项目提供#6螺丝，提供量大于100并且现有量比提供量多的供给者名字。
　　此查询可用图12-4表示。
　　 SNAME ┌─┐　　 CITY　　　┌─┐
　　　　 ←─┤S ├────────┤J │
　　　　　　 └┬┘　　　　　　　　└┬┘
　　　　　　　 │S#　　　　 S#　　　 │J#
　　　　　　　 │　　　　　　　　　　│
　　　　　　 ┌┴┐　　QOH>QU　　┌┴┐ QU>100
　　　　　　 │V ├────────┤Y │←──
　　　　　　 └─┘　　　 P#　　　 └─┘
　　　　　　　　　 P#
　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　│P │←── PNAME='BOLTS'
　　　　　　　　　　　　└─┘　　　 PSIZE=’#6’
　　　　　　　　　图12-4　例12.3的查询示意图
　　　　执行此查询的最笨的方法：
　　　　(1)形式卡氏积S×P×J×V×Y
　　　　(2)从卡氏积中限制筛选出满足限定条件的元组
　　　　(3)在S.SNAME上投影
　　　　若假定各关系的元组数如下：
　　　　┏━━━━━━━━━┯━━━━━━━━━━┓
　　　　┃　　关系　　　　 │　　元组数　　　　　┃
　　　　┠─────────┼──────────┨
　　　　┃　 SUPPLIER　　　│　　　　10　　　　　┃
　　　　┃　 PARTS　　　　 │　　　 100　　　　　┃
　　　　┃　 PROJECT　　　 │　　　　10　　　　　┃
　　　　┃　 INVENTORY　　│　　　 100　　　　　┃
　　　　┃　 SUPPLY　　　　│　　　 400　　　　　┃
　　　　┗━━━━━━━━━┷━━━━━━━━━━┛
　　
　　那么，卡氏积的元组总数为4×108 。这个算法显然是太坏了。
　　另外，我们会注重到此查询涉及到5个变元S,P,J,V,Y,我们把它称为5元查询，涉及一个变元的查询我们称为一元查询。
　　
　　2.1分解
　　前面的例子中所指出的主要问题是当查询涉及到卡氏积时，卡氏积的元组数会组合性地增长。这样不仅需要大量的存贮空间，而且执行查询的时间很长。因此优化应把主要注重力放在，第一，减小组合复杂性上；第二，把一个关系上的一元运算（一元查询）映象为一个存取调用的序列时，应找出存取次数最少的方法。下面讨论这两点，以第一点为主。
　　查询的处理过程分为两步：分解和一元查询处理。分解是动态的，如何分解受到一元查询处理结果的影响。处理的过程如图12-5所示。其中DECOMP负责把查询分解为一些一元查询。此部分的性能可通过它所产生出一元查询的数目多少来大体估计。此部分的第一个目标是要减少产生出一元查询的数目。
　　查询　┌──── ┐　　　┌───────── ┐　　┌───────┐
　　──→│DECOMP ├──→│OVQP(一元查询处理)├─→│AMI(存取接口) │
　　　　　└──── ┘　　　└───────── ┘　　└─┬─┬───┘
　　　　　　　　↑　　　　　　　　　　　　　　　　　　　　　│　│↑
　　　　　　　　└────────────────────　┘　↓│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│　　　│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│存贮的│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│ 数据 │
　　　　　　　　　图12-5　查询处理过程示意图
　　是否每个查询都可分解呢？回答是肯定的。任一n元查询Q(X1 ，X2 ，...,Xn ），其中Xi 的范围是关系Ri 。假如我们从Rn 中取出一元组α代入Xn ，那么得到一个n-1元查询Q(X1 ，X2 ,...，Xn-1 ,α）。假如Rn 有K个元组，则元组代入使Q变为K个n-1元查询。由此可见，无论付出代价如何，通过元组代入总可以把任何查询分解成一些一元查询。
　　另外一个问题是：除了元组代入以外是否还有其它分解方法呢？这里介绍两种：
　　(1)一元子查询提取：Q被替换为一个一元查询Q'和一个在其后执行的查询Q"。
　　Q ──→(Q',Q")
　　(2)化简：Q被替换为两个查询Q'和Q"，Q"在Q'执行后执行，它们只有一个公共变元。
　　X1 ,X2 ,...,Xm , Xm ,...,Xn
　　Q'　　　　 Q"
　　Q'(X1 ,X2 ,...,Xm ),Q"(Xm ,...,Xn )
　　*例12.4　考虑对例12.3的查询分解。
例12.3中的查询可以分出两个一元查询：
　　RETRIEVE PARTS1(P.P#)
　　WHERE (P.PNAME='BOLTS') AND (P.SIZE='#6')
　　和
　　RETRIEVE SUPPLE1(Y.S#,Y.J#,Y.P#,Y.QU)
　　WHERE(Y.QU>100)
　　于是，查询变成：
　　RANGE OF (S,P,J,V,Y) IS (SUPPLIER,PARTS1, PROJECT,
　　INVENTORY,SUPPLY1)
　　RETRIEVE(S.SNAME)
　　WHERE(S.S#=V.S#)AND (S.S#=Y.S#)
　　AND (S.CITY=J.CITY)AND (P.P#=V.P#)
　　AND (V.P#=Y.P#)AND (J.J#=Y.J#)AND (V.QOH>Y.QU)
　　图12-6给出了这个查询的示意图。从图中可以看出，这个查询可以很轻易地化简一个涉及（P,V）的查询和在其后执行的、涉及（S,J,Y,V）的查询。
　　
　　 SNAME ┌─┐　　 CITY　　　┌─┐
　　　　 ←─┤S ├────────┤J │
　　　　　　 └┬┘　　　　　　　　└┬┘
　　　　　　　 │S#　　　　 S#　　　 │J#
　　　　　　　 │　　　　　　　　　　│
　　　　　　 ┌┴┐　　QOH>QU　　┌┴┐
　　　　　　 │V ├────────┤Y1│
　　　　　　 └─┘　　　 P#　　　 └─┘
　　
　　　　　　　　　　 P#
　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　│P1│
　　　　　　　　　　　　└─┘
　　　　　　　　　图12-6　提取一元子查询后的示意图
　　
　　综上所述，在分解中可以采用3种方法：
　　(1)一元子查询提取
　　(2)化简
　　(3)元组代入
　　(1)几乎总会得到好处，因为在关系之间的运算之前尽可能减少关系的体积对减少付出的代价起很大作用。这一点我们在第一节中已经介绍过了。(2)经常会得到好处（但并不是总会得到好处）。(3)则是必须的，但又是我们最不希望采用的方法。当别无其它方法时必须用这种方法来分解。我们在后面要给出综合使用这三种方法分解查询的算法。
　　
　　2.2 一元子查询的提取
　　考虑n元的情况，假定x1 ,x2 ,...,xn 是查询Q的变元，xi 的变换范围是Ri 。一般地说来，Q有两部分，即结果属性表T1 和限定条件C。假定C是合取范式形式的，即
　　C=C1 ∧C2 ∧...∧Ck
　　其中Ci 是析取式，我们称Ci 为限定条件的子句。假定有一些子句Cm+1 ,Cm+2 ,...Ck ，其中每个都只涉及一个变元，那么对应这些变元的那些关系就可以分别被对应的限定条件缩小它们的体积。换句话说，假如限定条件C是合取式，那么就可以用只涉及一个变元的布尔因子作为限定条件来缩减对应的关系。假如只需要关系的某些属性，则在需要的属性上投影也可能会减少关系的元组数（因为去掉了冗余）。对于每个变元，第一个问题是要确定可以做哪些限制筛选、可以做哪些投影。
　　对关系Ri 的限定条件越多，Ri 就会被限制得越少。所以我们应尽可能加上一些限制条件。有时通过传递性可以推导出一些新的限定条件，如：
　　(a=b) AND (b=c) => (a=c)
　　(a>b) AND (b>c) => (a>c)
　　*例12.5　考虑从例12.3的查询推导出新的一元子句。
　　例12.3中的查询的条件子句(V.QOH>Y.QU)和(Y.QU>100)可以推出(V.QOH>100)。推出的子句可以作为一元子句来限制V所对应的关系INVENTORY。
　　一元子查询提取算法：
　　(1)把限定条件变成合取范式。
　　(2)加入所有由传递性推导出的一元子句。
　　(3)对于每个变元Xi ，确定：
　　1)涉及到Xi 的一元子句，
　　2)Ri在结果属性表中涉及到的属性和查询Q中多元子句中所涉及的属性。
　　(4)为每个Xi 形成一个一元查询Qi ，此查询相当于对(3) 2)所确定的那些属性投影用(3) 1)中确定的子句作为限定条件进行限制筛选。假如(3) 1)中没有一元子句并且(3) 2)中确定的属性是Ri 的所有属性，那么就去掉这个Qi 。因为这种情况下的结果就是Ri 。
　　*例12.6 把一元子查询提取算法用于例12.3的查询。
　　对例12.3的查询用此算法的第(3)步结果如下：
　　
　　┏━━━━━━┯━━━┯━━━━━━━━┯━━━━━━━━━━━━┓
　　┃　关系　　　│ 变元 │　一元子句　　 │　　需要的属性　　　　　┃
　　┠──────┼───┼────────┼────────────┨
　　┃SUPPLIER