ch.7查询处理与查询优化

第三部分系统篇ch.7查询处理与查询优化查询是数据库系统中使用最频繁、最基本的操作。对于一个给定的查询，通常会有许多种可能的执行策略，查询优化就是从众多策略中找出高效执行策略的处理过程，是DBMS实现的关键技术，对系统性能有很大影响。

1。引言2。代数优化3。物理优化

6/26/20231ch.71.引言1。引言（1)查询处理过程6/26/20232ch.71.引言（2)查询优化分类查询优化大致可分成以下四类：1）规则优化。仅根据一般能提高查询效率的规则，选择执行的策略。例如让选择、投影等一元操作先做，再做连接等二元操作。2）代数优化。先把查询语句转换成某种内部表示，通常是语法树，然后应用等价变换规则进行优化。例如依据已经经过证明的规则交换一元和二元操作的顺序，缩短执行时间。这种查询优化方法仅涉及查询语句本身，而不涉及存取路径，又称独立于存取路径的优化。3）物理优化。合理选择各种操作的存取路径，以取得显著的优化效果。例如考虑如何执行查询，是否存在索引或者其它的物理存取路径、数据值的分布情况等。又称为依赖于存取路径的优化。4）代价估算优化。构造一组查询执行策略，进行代价估算，从中选择一个代价最低的。一般地讲，产生所有的执行策略不太可能，这会造成选择本身代价太大，将产生的策略的数目保持在一定范围内才是比较合理的。6/26/20233ch.71.引言（3)一个启发性的例子例7-1设有Shop(商店)，Customer(顾客)，SC(购物关系)三个关系，关系模式如下： Shop(S#,Sname,Address) Customer(C#,Cname,Address) SC(S#,C#,Item,Quantity,Price) 查询是“给出销售出彩电的商店名称”，用SQL语句表达如下：SELECTSnameFROMShop，SCWHEREShop.S#＝SC.S#ANDItem=’彩电’用关系代数表达式表达这个查询语句：

ΠSname(σShop.S#＝SC.S#∧Item=’彩电’(Shop×SC))选择条件Shop.S#＝SC.S#与笛卡儿积组合成连接操作：

ΠSname(σItem=’彩电’(Shop⋈SC))选择条件Item=’彩电’还可以移到连接中的关系SC前面：

ΠSname(Shop⋈σItem=’彩电’(SC))6/26/20234ch.71.引言假设商店-顾客数据库中有500家商店和10000个销售记录，其中卖出过彩电的销售记录只有50个。可以看到虽然这三个关系代数的表达式是等价的，但是执行的效率却相差很大。执行第一个表达式花费的时间总计约50000秒(13.89小时）执行第二个表达式花费的时间总计约152.5秒（2.54分钟）执行第三个表达式花费的时间总计约7.5秒这个例子充分说明查询优化是必要的，实际中怎样的优化是可能的。例如，可以的情况下，先做选择后做连接，而不是先做连接后做选择。6/26/20235ch.72.代数优化2。代数优化（1）代数优化的基本原则1），选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。它常常可使执行时节约几个数量级，因为选择运算一般使计算的中间结果大大变小。2），在执行连接前对关系适当地预处理。预处理方法主要有两种，在连接属性上建立索引和对关系排序，然后执行连接。第一种称为索引连接方法，第二种称为排序合并（SORT-MERGE）连接方法。3），将投影运算和选择运算同时进行。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完戌所有的这些运算以避免重复扫描关系。6/26/20236ch.72.代数优化4），把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。5），将某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。6），找出公共子表达式。如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读人这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写人中间文件。当查询的是视图时，定义视图的表达式就可成为公共子表达式。公共子表达式并把结果写人中间文件。当查询的是视图时，定义视图的表达式就可成为公共子表达式。6/26/20237ch.72.代数优化（2）代数优化的等价变换规则1)选择的串接σc1(σc2(…(σcn(E))…))≡σc1ANDc2…ANDcn(E)2)选择的交换σc1(σc2(E))≡σc2(σc1(E))3)投影的串接.πL1(πL2(…πLn(E)…))≡πL1(E)4)选择与投影的交换.πL(σC(E))≡σC(πL(E))5)连接／笛卡儿积的交换率E1E2≡E2E1E1×E2≡E2×E16/26/20238ch.72.代数优化6)选择对连接／笛卡儿积的分配率.σc(E1E2)≡(σc(E1))E2σc(E1×E2)≡(σc(E1))×E27)投影对连接／笛卡儿积的分配率.πL1∪L2(E1E2)≡πL1(E1)πL2(E2)πL1∪L2(E1×E2)≡πL1(E1)×πL2(E2)8)选择对∪、∩、－的分配率σc(E1∪E2)≡σc(E1)∪σc(E2)σc(E1∩E2)≡σc(E1)∩σc(E2)σc(E1－E2)≡σc(E1)－σc(E2)9)投影对∪的分配率.πL(E1∪E2)≡πL(E1)∪πL(E2)10)、×、∪、∩的结合率(E1E2)E3≡E1(E2E3)6/26/20239ch.72.代数优化（3）代数优化算法算法7-1：关系代数表达式的优化算法。 输入：一个关系代数表达式的语法树。 输出：经过代数优化后计算该表达式的程序。 方法：主要包括以下基本步骤。①应用7.2.2小节中提到的等价变换规则（1），把形如σc1ANDc2…ANDcn(E)的子表达式转换为σc1(σc2(…(σcn(E))…))。②对每个选择操作，利用涉及选择的规则，尽可能将选择操作下推移向树叶方向。及早执行选择操作可以减少对中间结果进行排序的代价。③对每个投影操作，利用涉及投影的规则，尽可能将投影操作下推移向树叶方向。注意：规则（3）会使某些投影操作消失，规则（4）可能会把一个投影分裂成两个，其中一个有可能移向树的叶端。若一个投影涵盖被投影的表达式的所有属性，则可消去该投影操作。④使用规则（1）（3）（4）将选择和投影串接成单个选择、单个投影或一个选择后跟一个投影。使多个选择、投影能同时执行，或在一次扫描中全部完成。⑤将经过上述步骤得到的语法树的内结点分组。每个二元操作（×，⋈，∪，－）结点和它的直接祖先（不超过别的二元操作结点）的一元操作结点（σ或π）为一组。如果其后代直到叶子结点都是一元操作，则也将它们并入该组。 注意：如果二元操作是笛卡儿积，而且它后面的选择又不能与它结合为等值连接时，选择条件要单独分为一组。⑥最后输出程序，每组结点的计算是程序中的一步。各步的顺序是任意的，但要保证任何一组的计算不会在其后代组之前计算。6/26/202310ch.72.代数优化例7-2设有Shop(商店)，Customer(顾客)，SC(购物关系)三个关系，关系模式如下：Shop(S#,Sname,Address)Customer(C#,Cname,Address)SC(S#,C#,Item,Quantity,Price)查询语句是“找出西安销售给顾客“张立”彩电的商店编号和名称”，用SQL语句表达如下：SELECTS#,SnameFROMShop，Customer，SCWHEREShop.Address=’西安’ANDCname=’张立’ANDItem=’彩电’

ANDShop.S#＝SC.S#ANDCustomer.C#=SC.C#假设该查询变换成的关系代数表达式如下：ΠS#,Sname(σShop.Address=’西安’∧Cname=’张立’∧Item=’彩电’∧Shop.S#＝SC.S#∧Customer.C#=SC.C#(Shop×SC×Customer))6/26/202311ch.72.代数优化原始查询树

6/26/202312ch.72.代数优化选择操作尽量下移6/26/202313ch.72.代数优化投影操作下移6/26/202314ch.72.代数优化连接条件和笛卡儿积组合成连接操作6/26/202315ch.73.物理优化3。物理优化数据库实现的基础是文件，对数据库的任何操作最终都会落实为对文件的操作。关系数据库中，数据和存取路径分离。后者对用户是隐蔽的，可以动态建立、删除，例如顺序扫描、索引、散列等。理论研究和实际应用说明，选择合适的存取路径，能够收到显著的优化效果，应成为优化的重点。然而，前面介绍的代数优化并没有利用存取路径的便利，对各种操作的执行策略进行选择，只是利用一些变换规则来调整和重新安排操作的次序和组合，优化效果也是很有限的。因此，充分考虑存取路径，利用它们进一步改善查询效率，具有非常重要的意义。依赖于存取路径的规则优化，即物理优化，决定如何执行查询，基本策略是将表达式看成是由一系列关系操作（选择、连接、投影、集合运算等）构成，各种操作间保持一定的相互依赖关系。对于每个可能的操作，都具有一组可用的实现技术.（1)选择（2)连接（3)投影（4)集合运算6/26/202316ch.73.物理优化（1)选择选择操作执行策略，与选择条件、可用的存取路径以及选取的元组数在整个关系中所占的比例有关，分成下列几种情况来实现。1）、顺序扫描法(对被选择关系的每个文件块均被扫描，并且按选择条件对所有元组检验，在选中的元组数在关系中占有较大的比例或小关系情况下，值得使用.)2）、使用索引的选择(索引是用得最多的一种存取路径，可以快速、直接、有序地存取元组。索引的建立在一定程度上提高了查询的效率，但在更新时，增加了维护索引的开销，并且带来了访问那些包含索引的物理块的额外代价。因此，要根据应用的要求权衡得失，索引并不是越多越好。)3）、复合选择（由简单选择条件通过AND（合取）、OR（析取）连接而成的复合选择条件。对于合取选择、析取选择分别进行分析，选择最有效的存取路径。）6/26/202317ch.73.物理优化(2)连接连接是从两个关系的笛卡儿积中选择满足连接条件的元组，操作本身开销大，并且可能产生大的中间结果。因此，查询优化研究的一个重点就是提供适合各种情况的连接操作实现方法，从而保证获得好的优化结果。1)、嵌套循环连接算法for(i=1;i<=nR；i++){for(j=1;j<=nS；j++){if(R[i].A=S[j].B)then元组<R[i],S[j]>加到结果集；}}6/26/202318ch.73.物理优化2)、索引嵌套循环连接算法（在特定的环境下，关系上建立的有效索引和嵌套循环法相比，将代价降低很多，如果两个关系都有索引，一般效率较高的方法是把元组较少的关系作为外关系。）3)、排序归并连接算法pR:=1；/*代表排序后关系R的元组序列号*/pS:=1；/*代表排序后关系S的元组序列号*/while（pR≤nRandpS≤nS）do{if(S[pS].B<R[pR].A)thenpS:=pS+1;elseif(S[pS].B=R[pR].A) then{元组<R[pR],S[pS]>加到结果集;/*属性值相等情况进行连接*/v:=pS+1;/*找出关系S中所有属性值相等情况进行连接*/ while（pS≤nSandS[v].B=R[pR].A）do { 元组<R[pR],S[v]>加到结果集; v:=v+1; v:=pR+1;/*找出关系R中所有属性值相等情况进行连接*/ } while（pR≤nRandS[pS].B=R[v].A）do { 元组<R[v],S[pS]>加到结果集; v:=v+1; } pR:=pR+1; } elsepR:=pR+1;}6/26/202319ch.73.物理优化4)、散列连接算法for(i=1;i<=nR；i++)/*对关系R进行划分*/{k:=h(R[i].A);Hrk:=Hrk∪{R[i]}；}for(j=1;j<=nS；j++)/*对关系S进行划分*/{k:=h(S[j].B);Hsk:=Hsk∪{S[j]}；}for(m=0;m<=n-1；m++)/*对每个划分进行连接*/{for(v=1;v<=|Hrm|；v++)/*对集合Hrm、Hsm中每个元组检查能否进行连接*/{ for(w=1;w<=|Hsm|；w++) { if(Hrm[v].A=Hsm[w].B)then元组<Hrm[v],Hsm[w]>加到结果集；}}}6/26/202320ch.73.物理优化(3)投影用散列消除重复元组的投影算法if(主键包含在投影集合中)thenR”:=R’；else{for(i=1;i<=nR’；i++)/*对集合R’每个元组进行划分同时消去重复元组*/{k:=h(R’的某一属性或多个属性值);for(j=0;j<=|Hrk|；j++)/*检查对应的划分集合中是否有相等元组存在*/{if(R’[i]=Hr’k[j]) thenj:=j+1; elseHr’k:=Hr’k∪{R’[i]}；}} R”:=Φ；for(m=0;m<=n-1；m++)/*集合R”相当于全部划分集合的并*/R”:=R”∪Hr’m；}6/26/202321ch.73.物理优化(4)集合运算传统的集合运算是二元的，包括并、差、交、笛卡儿积四种运算。此处给出排序并操作算法、排序交操作算法、排序差操作算法，通常用嵌套循环算法实现笛卡儿积，算法耗时较多，并且结果比参与运算的关系大得多，因此要尽量少用。）

6/26/202322

排序并操作算法pR:=1；/*代表排序后关系R的元组序列号*/pS:=1；/*代表排序后关系R的元组序列号*/while（pR≤nRandpS≤nS）do{if(S[pS]<R[pR])then{元组S[pS]加到结果集；pS:=pS+1;}elseif(S[pS]=R[pR]) then{元组S[pS]加到结果集;/*重复的元组只保留一个*/v:=pS; while（pS≤nSandS[pS]=R[pR]）do pS:=pS+1; while（pR≤nRandS[v]=R[pR]）do pR:=pR+1;

} else{元组R[pR]加到结果集；pR:=pR+1;}

}if(pR≤nR)thenwhile(pR≤nR)do{元组R[pR]加到结果集；pR:=pR+1;}if(pS≤nS)thenwhile(pS≤nS)do{元组R[pS]加到结果集；pS:=pS+1;}6/26/202323ch.73.物理优化排序交操作算法pR:=1；pS:=1；/*分别代表排序后关系R、S的元组序列号*/while（pR≤nRandpS≤nS）do{if(S[pS]<R[p