最新数据库原理与技术课件PPT.ppt 95页

'数据库原理与技术 6.1查询处理概述查询处理是指从数据库中提取数据的一系列活动。主要包括：将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式为优化查询而进行各种转换查询的实际执行输入：SQL语句输出：满足查询条件的数据 6.1查询处理概述（2）查询处理的基本步骤：1语法分析与翻译2优化3执行语法分析与翻译关系代数表达式执行计划优化器查询语句执行引擎查询结果有关数据的统计值数据 6.2代价估算6.2.1用于估计代价的目录信息6.2.2查询代价的度量 6.2.1用于估计代价的目录信息有关关系的统计信息nr：关系r中的元组数目br：含有关系r的元组的块数目sr：关系r中一个元组的大小fr：关系r的块因子，即一个块中能存放的关系r的元组数若假定关系r的元组物理上存于同一文件中，则：br=nr/fr 6.2.1用于估计代价的目录信息（2）有关关系的统计信息（续）V(A,r)：关系r中属性A所具有的不同值的数目。V(A,r)等于ПA（r）的大小若A为关系r的码，则V(A,r)=nrSC(A,r)：关系r的属性A的选择基数。表示关系r中满足属性A上的一个等值条件的平均元组数。若A为r的码属性，则SC(A,r)＝1若A为非码属性，并假定V(A,r)个不同的值在元组上均匀分布，则SC(A,r)＝(nr/V(A,r))。说明：V(A,r)与SC(A,r)中的A可以是属性组。 6.2.1用于估计代价的目录信息（3）有关索引的统计信息：fi：树形结构(如B＋树)索引i的内部结点的平均扇出。HTi：索引i的层数。对于关系r的属性A上所建的平衡树索引（如B＋树），HTi＝logfi(V(A,r))对于散列索引，HTi＝1LBi：索引i中最低层索引块数目，即索引叶层的块数。对于散列索引，Lbi就是索引中的块数。算法A的代价估计记为EA。 6.2.2查询代价的度量查询代价：查询处理对各种资源的使用情况磁盘存取（简化为磁盘块传送数）CPU时间通信开销一个重要的影响因素：主存中缓冲区的大小M＊最好的情形，所有的数据可以读入到缓冲区中＊最坏的情形，缓冲区只能容纳数目不多的数据块——大约每个关系一块。 6.3基本运算的实现每一个基本的代数运算都有多种不同的实现算法。•适用于不同的情况等值条件，范围条件数据是聚集的，数据是非聚集的相关属性上有索引，相关属性上没有索引•执行代价不同 6.3基本运算的实现（2）6.3.1选择运算6.3.2排序运算6.3.3连接运算6.3.4其他运算 6.3.1选择运算全表扫描方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。代价：E=br缺点：效率低优点：对关系的存储方式没有要求，不需要索引。适用于任何选择条件。 6.3.1选择运算（2）索引扫描条件：表在选择条件的属性上建有索引。方法：访问索引，根据索引项的指示去访问数据元组。无序索引：访问满足等值条件的元组有序索引：访问满足范围查找条件的一系列元组。 6.3.1选择运算.（3）代价：利用主索引，等值比较：E=HTi+SC(A，r)/fr利用辅助索引，等值比较：E=HTi+SC（A，r）利用主索引，非等值比较：E=HTi+br/2（假设大约一半的元组满足比较条件）利用辅助索引，非等值比较：E=HTi+LBi/2+nr/2 6.3.1选择运算（4）复杂条件的选择合取：σθ1∧θ2∧…∧θn（r）析取：σθ1∨θ2∨…∨θn（r）方法：利用一个索引进行合取选择。利用组合索引进行合取选择。利用多维索引进行合取选择。通过标识符的交集进行合取选择。通过标识符的并集进行析取选择。 6.3.2排序运算排序运算在数据库中的重要意义：SQL查询可能要求有序的查询结果。事先对于作为运算对象的关系进行排序，可以提高某些关系运算（例如连接）的执行效率。内排序：文件较小，整个排序过程都能在内存中进行。外排序：文件较大，排序过程需要使用外存。 6.3.2排序运算（2）外部排序-归并算法：（设内存中用于排序的缓冲区页面数为M）第一阶段，建立多个已排序的子表。每次读入M块，进行内排序，将长度为M块的已排序子表（共br/M个）写到外存中。第二阶段，对已排序子表进行归并（可能需进行若干趟）。 6.3.2排序运算（3）第二阶段，对已排序子表进行归并。第一趟：将头M-1个已排序子表的各块逐步读入内存，归并并输出。将下M-1个已排序子表的各块逐步读入内存，归并并输出。……已排序子表数目减少到原来的1/（M-1）第二趟：以第一趟的输出作为输入，重复过程。第三趟：以第二趟的输出作为输入，重复归并过程……直至归并为一个已排序文件。 6.3.2排序运算（4）第二阶段第一趟：将头M-1个已排序子表的每一个的第一块读入内存的一个缓冲页repeat在所有缓冲页中的第一个元组中挑选排序码值最小的元组；把该元组写到第M个缓冲页，并将其从原缓冲页中删除；if任何一个归并段文件Ri的缓冲页为空并且没有到达Ri末尾then读入Ri的下一块到相应的缓冲页；if第M个缓冲页满then将第M个缓冲页写到磁盘，并清空该缓冲页；until所有的缓冲页均空将下M-1个已排序子表的每一个的第一块读入内存，归并。……. 6.3.2排序运算（5）初始关系归并段文件归并段文件排序结果第一阶段第二阶段第二阶段创建归并段文件第一趟归并第二趟归并 6.3.2排序运算（6）代价估算：趟数=logM-1(br/M)E=br(2logM-1(br/M)+1) 6.3.3连接运算二元运算，涉及两个关系。r|><|s,r|><|s重要的运算，多种不同的实现算法。 6.3.3连接运算（2）自然连接结果集大小的估计：基于主码、外码连接的情况：结果集的元组数等于外码所在关系的元组数。一般情况：（假设连接属性A的每个值在关系的元组中等概率出现），结果集的元组数为：nr*(ns/V(A,s))或ns*(nr/V(A,r))说明：当V(A,s)与V(A,r)不同时，取两个估计值中较小者。若两个关系中的元组在连接属性上的取值能匹配上的很少时，上述估计值太高。但实际上这种情况很少发生。 6.3.3连接运算（3）嵌套循环连接块嵌套循环连接索引嵌套循环连接排序-归并连接散列连接复杂连接的实现 6.3.3连接运算（4）嵌套循环连接foreach元组trinrdobeginforeach元组tsinsdobegin测试元组对(tr,ts)是否满足连接条件θ如果满足，把trts加到结果中endend 6.3.3连接运算（5）嵌套循环连接（续）优点：对参加运算的关系没有要求，适合于任何连接条件。代价：最坏情况（缓冲区只能够容纳每个关系的一个块）：nrbs+br或nsbr+bs最好情况（内层关系s能完全放在内存中）：bs+br 6.3.3连接运算（6）块嵌套循环连接：以块的方式循环，以减少块读写次数。foreach块Brofrdobeginforeach块Bsofsdobeginforeach元组trinBrdobeginforeach元组tsinBsdobegin测试元组对(tr,ts)是否满足连接条件θ如果满足，把trts加到结果中endendendend 6.3.3连接运算（7）块嵌套循环连接（续）优点：对参加运算的关系没有要求，适合于任何连接条件。代价：最坏情况（缓冲区只能够容纳每个关系的一个块）：br*bs+br或bs*br+bs最好情况（内层关系s能完全放在内存中）：bs+br 6.3.3连接运算（8）块嵌套循环连接（续）一些改进：连接属性是内层关系的码时，内层循环可中途跳出。内层循环轮流做正、反向扫描，重用缓冲区中的数据，以减少磁盘读取。内层循环利用索引。 6.3.3连接运算（9）索引嵌套循环连接：在内层循环中利用连接属性上的索引。foreach元组trinrdobeginforeach与元组tr满足连接条件的索引项ins关系在连接属性上的索引dobegin利用索引取到相应的ts把trts加到结果中endend 6.3.3连接运算（10）索引嵌套循环连接（续）代价：最坏情况（缓冲区只能够容纳关系r的一个块和索引的一个块）：br+nr*c或bs+ns*c最好情况不必考虑，因为不必采用索引嵌套循环连接方法。对关系S使用连接条件利用索引进行选择操作的代价 6.3.3连接运算（11）排序-归并连接类似于外排序的归并算法的思路，进行连接运算。前提：两个关系的元组都已按连接属性排好序。适用于自然连接和等值连接。a3b1d8d13f7m5q6aAaGcLdNmBrsa1a2a1a3在归并连接中使用的已排序关系rs 6.3.3连接运算（12）pr:=r的第一个元组的地址ps:=s的第一个元组的地址；while(ps≠nullandpr≠null)dobegints:=ps所指向的元组；Ss:={ts}；让ps指向关系s的下一个元组；done:=false;while(notdoneandps≠null)dobegints’:=ps所指向的元组；if(ts’[JoinAttrs]=ts[JoinAttrs])thenbeginSs:=Ss∪{ts’}；让ps指向关系s的下一个元组；endelsedone:=true；end在连接属性上具有相同值的S元组被加入到了Ss中。Ps指向在连接属性上具有另一个值的S元组。 6.3.3连接运算（13）tr:=pr所指向的元组；while(pr≠nullandtr[JoinAttrs]M2时，关系的划分不可能一趟完成，需要递归划分。当对于某个i，Hsi中的元组数大于内存容量时，需要进行溢出处理，想办法使Hsi变小。改进：混合散列连接当M2>>bs时，充分利用内存空间，减少磁盘I/O的方法。前提：读每个关系一遍就能完成散列划分，构造用输入关系的每一个分划都能完全放入内存。 6.3.3连接运算（23）复杂连接的实现合取式：r|><|1∧2∧…∧ns用一种高效技术计算某一条件下的连接r|><|1s，在生成结果元组时测试其他条件。析取式：r|><|1∨2∨…∨ns==>r|><|1sr|><|2s…r|><|ns 6.3.4其他运算消除重复投影并、交、差外连接聚集 6.3.4其他运算（2）消除重复用排序的方法用散列的方法投影投影，消除重复并、交、差排序的方法散列的方法 6.3.4其他运算（3）外连接计算连接，然后将适当的元组加到结果中。例r]><|θs计算r|><|θS==>q1计算r-∏R(q1)，在s对应的分量填上空值，加到q1中。 6.3.4其他运算（4）外连接（续）修改连接算法修改嵌套循环连接算法进行左外连接、右外连接。修改排序-归并连接算法进行全外连接、左外连接、右外连接。修改散列连接算法进行全外连接、左外连接、右外连接。 6.3.4其他运算（5）聚集排序的方法散列的方法 6.4表达式计算例Пcustomer_name（σbalance<2500(account)|><|customer）Пcustomer_nameσbalance<2500customeraccount|><| 6.4表达式计算（2）实体化的方法—建立临时关系代价：各个运算的代价加上中间结果写到磁盘的代价。(nr/fr)流水线的方法—不建临时关系，一个操作的结果传给下一个操作作为输入。 6.4表达式计算（3）流水线的实现：需求驱动—在操作树的顶端将数据往上拉。生产者驱动—将数据从操作树的底层往上推需求驱动的流水线方法比生产者驱动的流水线方法使用更广泛，因为它更容易实现。 6.4表达式计算（4）说明：流水线技术限制了实现操作的可用算法。例若连接运算的左端输入来自流水线，则不可用排序-归并连接算法，可用索引嵌套循环连接算法。若连接运算的两端输入均来自流水线，则限制更大。并非所有情况下都是流水线方法的代价小于实体化方法的代价，因为流水线方法对于运算的实现算法有限制。 6.5关系表达式转换查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。查询优化的过程：代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。 6.5.1表达式的等价性两个表达式等价：产生的结果关系具有相同的属性集和相同的元组集。例Пcustomer_name(σbranch-city=”Brooklyn”(branch|><|(account|><|depositor)))等价于Пcustomer_name((σbranch-city=”Brooklyn”(branch))|><|(account|><|depositor)) 6.5.1表达式的等价性（2）Пcustomer_nameσbranch_city=”Brooklyn”branchaccountdepositorПcustomer_nameσbranch_city=”Brooklyn”branchaccountdepositor 6.5.2等价规则等价规则将一个表达式转换为与之等价的另一个表达式的规则。符号：θ、θ1、θ2等表示谓词，L1、L2、L3等表示属性列表，E、E1、E2等表示关系代数表达式。关系名r是关系代数表达式的特例，在E可以出现的地方它就可以出现。 6.5.2等价规则（2）1.选择运算的级联：合取选择运算可分解为单个选择运算的序列。σθ1∧θ2(E)=σθ1(σθ2(E))2.选择运算满足交换律σθ1(σθ2(E))=σθ2(σθ1(E))3.投影运算的级联：投影运算序列中只有最后一个运算是需要的，其余的可省略。∏L1(∏L2(…(∏Ln(E))…))=∏L1(E) 6.5.2等价规则（3）4.选择与笛卡尔积以及theta连接相结合a.σθ(E1×E2)=E1|><|θE2b.σθ1(E1|><|θ2E2)=E1|><|θ1∧θ2E25.theta连接运算满足交换律：E1|><|θE2=E2|><|θE1自然连接也满足交换律E1|><|E2=E2|><|E1 6.5.2等价规则（4）6.连接运算的结合律a.自然连接运算满足结合律：(E1|><|E2)|><|E3=E1|><|(E2|><|E3)b.theta连接具有以下方式的结合律：(E1|><|θ1E2)|><|θ2∧θ3E3=E1|><|θ1∧θ3(E2|><|θ2E3)其中θ2只涉及E2与E3的属性。由于任意一个条件都可为空，因此笛卡尔积运算也具有结合律。 6.5.2等价规则（5）7.选择运算在下面两个条件下对theta连接运算具有分配律：a.当选择条件θ0的所有属性只涉及参与连接运算的表达式之一(E1)时：σθ0(E1|><|θE2)=(σθ0(E1))|><|θE2b.当选择条件θ1只涉及E1的属性，选择条件θ2只涉及E2的属性时：σθ1∧θ2(E1|><|θE2)=(σθ1(E1))|><|θ(σθ2(E2)) 6.5.2等价规则（6）8.投影运算对theta连接运算具有分配律：a.令L1、L2分别是E1、E2的属性。假设连接条件θ只涉及L1∪L2中的属性，则：∏L1∪L2(E1|><|θE2)=(∏L1(E1))|><|θ(∏L2(E2))b.考虑连接E1|><|θE2。令L1、L2分别是E1、E2的属性；令L3是E1中出现在连接条件θ中但不在L1∪L2中的属性；令L4是E2中出现在连接条件θ中但不在L1∪L2中的属性。那么：∏L1∪L2(E1|><|θE2)=∏L1∪L2((∏L1∪L3(E1))|><|θ(∏L2∪L4(E2))) 6.5.2等价规则（7）9.集合运算并与交满足交换律E1∪E2=E2∪E1E1∩E2=E2∩E1集合差运算不满足交换律10.集合运算并与交满足结合律(E1∪E2)∪E3=E1∪(E2∪E3)(E1∩E2)∩E3=E1∩(E2∩E3)集合差运算不满足结合律 6.5.2等价规则（8）11.选择运算对并、交、差运算具有分配律：σp（E1-E2）=σp（E1）-σp（E2）σp（E1∪E2）=σp（E1）∪σp（E2）σp（E1∩E2）=σp（E1）∩σp（E2）进一步有：σp（E1-E2）=σp（E1）-E2σp（E1∩E2）=σp（E1）∩E2但对于∪不成立。 6.5.2等价规则（9）12.投影运算对并运算具有分配律∏L(E1∪E2)=(∏L(E1))∪(∏L(E2))最小的等价规则集：若一个等价规则集中的任何一条规则都不能由其它规则结合起来导出，则称该等价规则集为最小的等价规则集。 6.5.2等价规则（10）例Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000(branch|><|(account|><|depositor)))规则6a==>Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000((branch|><|account)|><|depositor))规则7a==>Пcustomer-name((σbranch_city=”Brooklyn”∧balance>1000(branch|><|account))|><|depositor) 6.5.2等价规则（11）Пcustomer-name((σbranch-city=”Brooklyn”∧balance>1000(branch|><|account))|><|depositor)规则7b==>Пcustomer-name((σbranch-city=”Brooklyn”(branch)|><|σbalance>1000(account))|><|depositor)规则8b==>Пcustomer-name(Пaccount-number(σbranch-city=”Brooklyn”(branch)|><|σbalance>1000(account))|><|depositor) 6.5.2等价规则（12）说明：规则只说明两个表达式等价，并不说明哪一个更好。连接的次序很重要，好的连接次序序列产生小的中间结果。规则的使用会产生大量的等价表达式，优化器要采用适当的技术来减少所产生的表达式的数量。 6.6选择执行计划关系代数表达式的基础上，执行计划进一步说明：每个运算的实现算法各运算的执行顺序是否采用流水线技术注意：每个运算的最小代价算法组合起来不一定是整个表达式的最佳算法，必须考虑各个运算之间的相互作用。 6.6选择执行计划（2）两类主要的优化算法：基于代价的方法启发式方法 6.6.1基于代价的优化通过使用等价规则为给定的查询语句产生一系列查询执行计划，并选择其中代价最小或接近最小的。等价于给定查询的不同查询计划可能很多，因此优化的代价太大，所以：采用一些巧妙的技术来减少需要考虑的表达式的数目。采用启发式方法来减少需考虑的表达式的数目。 6.6.1基于代价的优化（2）减少需要考虑的表达式数目的技术只考虑左深连接次序r1r2r3r4r5左深连接树r1r2r3r4r5非左深连接树 6.6.1基于代价的优化（3）找多个关系的最佳连接顺序时，不是简单地考虑所有的可能顺序，而是为每个子集找出最佳连接顺序，这样能大大减少需要检查的连接顺序的总数。如果检查一个表达式的某部分后发现这一部分的最小代价已经比先前已检查过的整个表达式的执行计划的最小代价要大，则可以终止对这个表达式的检查。如果发现计算一个子表达式的代价最小的方法所用的代价比先前已检查过的整个表达式的最小代价执行计划所需代价还大，则没有必要对包含该子表达式的任何完整表达式进行检查。 6.6.2启发式优化运用启发式规则，对关系代数表达式进行等价变换。常用的规则：尽早进行选择运算尽早进行投影运算避免进行笛卡尔积运算……….. 6.6.2启发式优化（2）启发式优化的步骤:1.将合取选择分解为单个选择运算的序列。这有助于将选择运算往查询树下层移。2.把选择运算在查询树上下推到最早可能执行的地方。例如，尽可能将σθ(r|><|s)转换成σθ(r)|><|s或r|><|σθ(s)3.通过使用|><|的结合律，重新组织查询树，使得具有限制比较严格的选择运算的叶结点关系首先执行。4.将跟有选择条件的笛卡尔积运算替换成连接运算。5.将投影属性加以分解并在查询树上尽可能往下推。必要时可以引入新的投影运算。6.识别那些可用流水方式执行其运算的子树，并采用流水线方法执行之。 6.6.3嵌套子查询的优化复杂嵌套子查询的优化相当困难，许多优化器对于嵌套子查询的优化仅做了少量的工作。例selectcustomer-namefromborrowerwhereexists(select*fromdepositorwheredepositor.customer-name=borrower.customer-name)SQL概念上按以下方式执行查询：计算外层查询的from子句中的关系的笛卡尔积，然后对该笛卡尔积的每个元组用位于where子句中的谓词进行测试。本例中，即测试子查询运算结果是否为空。 6.6.3嵌套子查询的优化（2）相关执行:概念上将位于where子句中的嵌套子查询处理成获取参数并且返回单独值或值的集合（可能为空集）的函数。参数是嵌套子查询中用到的外层查询的变量（称作相关变量）。相关执行效率不高，因为对于外层查询的每一个元组都要进行一次内层子查询的运算，从而可能导致大量的随机磁盘I/O操作。去除相关：用一个具有连接的查询（可能使用临时关系）去替代嵌套子查询。有效的连接算法有助于避免昂贵的随机I/O操作。 6.6.3嵌套子查询的优化（3）例selectcustomer-namefromborrowerwhereexists(select*fromdepositorwheredepositor.customer-name=borrower.customer-name)selectcustomer-namefromborrower,depositorwheredepositor.customer-name=borrower.customer-name 6.6.3嵌套子查询的优化（4）更复杂的情况：不能将嵌套子查询关系直接移入外层查询的from子句里，需要先建立一个包含嵌套查询结果（但没有用取自外层查询的相关变量进行选择操作）的临时关系，然后将这个临时表与外层查询进行连接。 6.6.3嵌套子查询的优化（5）例selectcustomer-namefromborrowerwhereloan-number>1000andexists(select*fromdepositorwheredepositor.customer-name=borrower.customer-nameandaccount-number<1000)==〉createtablet1asselectdistinctcustomer-namefromdepositorwhereaccount-number<1000selectcustomer-nameformborrower,t1whereloan-number>1000andt1.customer-name=borrower.customer-name 6.6.3嵌套子查询的优化（6）当嵌套子查询使用聚集、或嵌套子查询的结果用于等值测试、或嵌套子查询与外部查询的关联条件是notexists时，去除相关操作会更复杂。 课程实习目的：1.了解数据库管理系统底层的存储管理与数据管理部件，它所提供的接口。2.进行查询处理系统设计与实现的实际训练。任务：1.设计与实现一个简化的查询处理系统，对SQL语句进行分析处理，优化，产生执行结果。2.分析、比较不同的查询执行计划的执行性能。 课程实习（2）基础环境：COBASE核心——存储管理和数据管理子系统SQL语言翻译处理存储管理与数据管理单元组接口SQL语句 课程实习（3）说明：1．二至三人一组，自由结合。2．适当控制系统的规模和难度，只处理有限形式的SQL查询。3．集中做与查询处理密切相关的工作，简化其他部分。4．注意中间结果，和比较、分析结果的输出，充分展示你的工作的特色。 课程实习（4）提交：1．查询处理系统规格定义2．设计说明书3．使用说明书4．比较分析和总结报告5．可运行的系统 图上画的是什么时候，什么地点，有哪些人？图上的每个同学干得怎么样，动作如何，心情又是怎样的呢？他们可能会想些什么，做完之后，结果怎样呢？ 他们干得可认真了！有的……有的……还有的……有的在擦黑板，有的在扫地，有的在擦桌子。 1、只见×××————，黑板被擦得—————。形容干净的词语：干干净净一尘不染亮洁如新焕然一新 2、你看，×××小朋友在扫地，他—————，累得—————。形容劳累的词语：大汗淋漓满头大汗汗流浃背气喘吁吁 3、×××小朋友在————地擦桌子，她——————。形容做事认真的词语：认认真真仔仔细细全神贯注专心致志一心一意 今天是个阳光灿烂的好天气，我们学校进行了一次大扫除。大扫除开始了，小朋友干得热火朝天，有的小朋友在拖地，有的朋友在擦黑板，还有的小朋友在擦桌子。只见小刚手拿抹布使劲得擦着黑板，黑板被擦得焕然一新了。你看，小明弯着腰，拿着扫把用力地扫着地，他累得满头大汗、气喘吁吁，但仍不肯休息。还有小英拿着抹布在擦桌子，她干得可真仔细呀！在小朋友的共同努力下，教室被打扫得干干净净、一尘不染。 写话要求：1、为图画起一个题目。2、开头空两格。3、标点符号单独占一格。4、写字工整，句子通顺。'