分布式数据库原理与应用课件PPT1第5章

第五章分布式查询策略的优化5.1查询处理策略选择涉及的问题1.确定查询所需片段的物理副本。（1）本场地上的物理副本优先。（2）如果二元运算存在，则尽可能的在本场地上执行。（3）数据量最小的物理关系应优先选中。（4）网络通信代价小的物理副本应优先选中。5.1查询处理策略选择涉及的问题2.选定运算的执行顺序。选定运算的执行顺序，也就是要确定一个较优的连接、半连接和并运算序列，至于其他运算的执行顺序是不难确定的。值得注意的是，在查询变换后所产生的查询树中蕴含地定义了运算的次序，即按照从树叶到树根的顺序进行运算．然而这并不完全确定了优化问题的解法，因为还要求指出在树的同一层上所执行的子表达式的求值顺序。此外，从树叶开始逐步往上运算也不一定就是最好的执行顺序。5.1查询处理策略选择涉及的问题3.选择执行每个操作符的办法。为每个操作符指定合适的物理查询计划，即场地上数据库存取方法的选择，是减少查询执行代价的重要步骤。如尽可能的将统一场地上对统一副本的全部操作，在一次数据库访问后一起执行。5.2基于半连接算法的查询优化考虑到分布式数据库系统中站点的物理分散性以及关系的分片特性，其上的连接操作很复杂。当连接操作关联的两个关系对象位于不同的站点上时，为了完成连接操作不可避免的要在站点间进行数据传输，为了降低通信代价很直观的想法是避免网络上不必要的元组的传输，半连接算法正是基于减少数据传输量的思想而做优化的。5.2.1半连接操作的定义定义：假设关系R和S拥有相同属性a，则关系R和S的半连接为∏R(R∞S)=R∞∏a(S)，记为R∝S，即R∝S=∏R(R∞S)=R∞∏a(S)；关系S和R的半连接为∏S(S∞R)=S∞∏a(R),记为S∝R,即：S∝R=∏S(S∞R)=S∞∏a(R)。5.2.2半连接操作过程和代价估算关系R和关系S的连接可用半连接实现，即:R∞S=(R∞Πa(S))∞S=(R∝S)∞S5.2.2半连接操作过程和代价估算传输代价用T=C0+C1×X估算（1）在站点2计算关系S在属性a上的投影Πa(S)。（2）把Πa(S)的结果从站点2传到站点1，其传输代价为:C0+C1×Length(a)×val(S,a),其中Length(a)表示属性a的长度，val(S,a)表示关系S中属性a的个数。（3）在站点1计算半连接，设其结果为R’´，则R’´=R∝S。实际上，这个操作是执行R∞Πa(S)。5.2.2半连接操作过程和代价估算（4）把R’´从站点1传到站点2，其传输代价为:C0+C1×Length(R)×card(R’´)，其中:Length(R)是R中元组的长度，card(R’´)是R’´的元组数。（5）在站点2执行连接操作(R∞Πa(S))∞S。5.2.2半连接操作过程和代价估算显然，步骤（1）、（3）、（5）无需传输费用，所以执行这样一个半连接程序，总的传输代价为:Tsemi-jion=C0+C1×Length(a)×val(S,a)+C0+C1×Length(R)×card(R’´)=2×C0+C1(Length(a)×val(S,a)+Length(R)×card(R’´))5.3基于直接连接的查询优化算法高速局域网和专线网络中高速的数据传输特性使得此种网络环境更加注重查询响应时间，而不是通信代价，所以在局域网或专线网络中执行连接操作时总是从本地站点传输整个关系到另一个站点，对此所做的优化称为直接连接查询优化。5.3.1直接连接操作的策略直接连接操作依据参与连接的两个关系是否在同一站点而采取不同的操作策略。当两个关系在同一站点时，与集中式数据库一样可采用嵌套循环连接算法和基于排序的连接算法。5.3.1直接连接操作的策略对于不同站点上的关系R和S的连接，除考虑局部代价外还需考虑传输代价。影响传输代价的因素有两个方面：传输方式和连接站点。传输方式有两种：整体传输方式和按需传输方式。选择连接站点的方法有以下三类：（1）将R所在站点作为连接站点；（2）将S所在站点作为连接站点；（3）使用其他站点作为连接站点。5.3.2嵌套循环连接算法嵌套循环连接算法是一种最简单的连接算法，其原理是对连接操作的两个关系对象中的一个仅读取其元组一次，而对另一个关系对象中的元组将重复读取。嵌套循环连接算法的特点是可以用于任何大小的关系间的连接操作，不必受连接操作所分配的内存空间大小的限制。对于嵌套循环连接算法，可根据每次操作的对象大小分为基于元组的嵌套循环连接和基于块(block)的嵌套循环连接。5.3.2嵌套循环连接算法1.基于元组的嵌套循环连接算法：Result=φForeachtuplerinRForeachtuplesinSIfr.B=s.BThenjoinrandsastupletoutputtintoResultEndIfEndForEndForReturnResult5.3.2嵌套循环连接算法2.基于块的嵌套循环连接算法：5.3.2嵌套循环连接算法2.基于块的嵌套循环连接算法：Result=φBuffer=MForeachM-1BlockinBlock(S)ReadM-1BlockofBlock(S)intoBufferForeachBlockinBlock(R)Read1BlockofBlock(R)intoBufferJoinM-1BlockofBlock(S)and1BlockinBlock(R)sinBufferoutputtintoResultEndForEndForReturnResult5.3.2嵌套循环连接算法3.嵌套循环连接算法的代价估计：基于元组的嵌套循环连接方法执行代价为：Card(R)×Card(S)；基于块的嵌套循环连接算法执行代价为：Cjoin=Block(S)/(M-1)×(M-1+Block(R))=Block(S)+Block(S)/(M-1)×Block(R)5.3.3基于排序的连接算法基于排序的连接算法首先将两个关系按照连接属性进行排序，然后按照连接属性的顺序扫描两个关系,同时对两个关系中的元组执行连接操作。由于数据库中关系的大小往往大于连接操作可用内存缓冲区的大小，因此对关系的排序通常采用外存排序算法，即归并排序算法。5.3.3基于排序的连接算法1.归并排序算法简单的归并排序算法的执行可以划分为两个阶段:（1）对关系进行分段排序，即首先将需要排序的关系R划分为大小为M个块的子表，其中M是可用于排序的内存空间的个数，以块为单位，再将每个子表放入内存中采用快速排序等主存排序算法执行排序操作,这样可以获得一组内部已排序的子表。对关系进行分段排序过程如图所示。5.3.3基于排序的连接算法5.3.3基于排序的连接算法1.归并排序算法（2）对关系的子表执行归并操作,即按照顺序从每个排序的子表中读取一个块的内容放入内存中,在内存中统一对这些块中的记录执行归并操作,每次选择最小(最大)的记录放入输出缓冲区中，同时删除子表中相应的记录。当子表在内存中的块被取空时,从子表中顺序读取一个新块放入内存中继续执行归并操作。归并操作的过程如图所示。5.3.3基于排序的连接算法5.3.3基于排序的连接算法2.基于排序的连接算法基于排序的连接算法主要是对已经按照连接属性排序的两个关系，按照顺序读取关系中的块到内存中执行连接操作。基于排序的连接算法执行过程如下图所示,其中先使用内存对关系R和S进行排序,再基于归并方法按顺序依次连接关系中的元组。5.3.3基于排序的连接算法5.3.3基于排序的连接算法3.基于排序的连接算法代价估计在算法排序阶段的执行代价包括：（1）对关系的子表执行排序所需的一次读(读子表数据)和一次写(子表排序结果写入磁盘)的代价,为2(Block(R)+Block(S))；（2）多路归并时读写代价为2(Block(R)+Block(S))。算法排序阶段的执行代价为4(Block(R)+Block(S))在归并连接阶段需要对关系执行一次读操作，因此，基于排序的连接算法的执行代价为5(Block(R)+Block(S))。5.3.4站点依赖算法定义：对于两个关系R1和R2在属性A上的所有分片片段F1i和F2j(i和j代表站点，并且i≠j)，如果满足F1i∞AF2j=φ，则称R1和R2在属性A上站点依赖。那么R1∞AR2=∪(F1s∞AF2s)，其中s=1，⋯．n(1,⋯．n为包含R1、R2片段的所有站点)。5.3.4站点依赖算法推论1：如果Ri和Rj在属性A上站点依赖，则Ri和Rj在任何包含A的属性集B上也站点依赖。推论2：如果Ri和Rj在属性A上站点依赖，另一个属性(或属性组)B函数决定A(即B→A)，且A≠φ，则Ri和Rj在属性(或属性组)B上也站点依赖。5.3.4站点依赖算法推论3：若Ri和Rj在属性A上站点依赖，且Rj和Rk在属性B上站点依赖，则(Ri∞ARj∞BRk)=∪(Fis∞AFjs∞BFks)，其中S为所有包含Ri、Rj和Rk的片段的任一站点。5.3.4站点依赖算法站点依赖算法描述如下：算法主要用到四个集合Q、R、P和S。其中Q是查询操作的关系代数集，R={R1，R2，．．．，Rn}是所有参与查询Q的关系的集合，P是站点依赖信息集(算法中所有的站点依赖信息都是从此集合中得到)，S是一个连接操作可以无数据传送执行的最大关系集合。5.3.4站点依赖算法（1）初始化：S=φ，R={R1，R2，．．．，Rn}。（2）如果能找到一对关系Ri和Rj，使得Ri和Rj在属性A上站点依赖，且Ri∞cRj包含在Q中，其中C包含A，据推论1，则将Ri和Rj放入S中；否则，算法终止执行，返回空集S。5.3.4站点依赖算法（3）对于任意关系Rk，若它满足在R中而不在S中，则可把Rk插入S中，条件是存在S中的关系Rx，它与Rk在属性B上有站点依赖关系，且Rx∞BRk在Q中或可由Q中导出(根据推论1、2、3)。多次循环，直至不能再向S中添加关系为止。5.3.4站点依赖算法可以看到，站点依赖算法利用站点依赖信息判断全局连接查询是否可以零数据传输，如果S=R，则Q可以零数据传输处理。该算法有效利用了局部查询的本地化特征，在一个设计精良的分布式数据库中可以实现全局连接查询的零数据传输处理。5.3.5分片和复制算法如果一个查询不能在无数据传送方式下得到处理，则需要用其它的算法来进行处理。分片和复制算法就是这样一种算法，它的基本思想是：选择一组站点，把查询引用的某个关系的所有片段分布在这些站点上，引用的其余关系则被复制到每一个站点中，然后分别在每一站点上做连接操作，最后合并连接结果。5.3.5分片和复制算法分片和复制算法描述如下：算法主要用到三个集合Q、R和S。其中Q是查询操作的关系代数集，R={R1，R2，．．．，Rn}是所有参与查询Q的关系的集合，S是站点集合。5.3.5分片和复制算法For每个保持分片状态的关系Ri，i=1,2,…..,n{For每个包含关系Ri的一个片段的站点Sj，j=1,2,…..,m{计算在站点sj执行子查询的完成时间FT(Q,sj,Ri)}计算关系Ri保持分片状态下的响应时间Ti=max(FT(Q,S1,Ri),FT(Q,S2,Ri),….,FT(Q,Sm,Ri))}若Tk=min(T1，T2，⋯Tn)，则Rk为保持分片状态的关系。其它关系被复制到有Rk片段的每一个站点中。5.3.6Hash划分算法Hash划分是一种划分方法，它对关系的某一属性或者属性集的元组值应用Hash函数，得到这些元组的Hash值，然后将具有相同Hash值的元组放置到同一个站点。这样经过Hash划分的每一个关系的元组都会根据该元组的Hash值存放到多个不同的站点上而组成相应关系的水平片段，很显然，不同的关系经过同一种Hash划分后是满足站点依赖的。5.4SDD-1算法SDD-1算法有三个重要特征，一是使用半连接作为处理方案；二是所有站点上的关系都是不重复的，也不进行分片；三是在整个算法的代价估算中，不计算到查询发起站点的传输代价。5.4.1SDD-1算法的基本概念定义1：设R和S是两个关系，R和S半连接选择因子记为:ρ(R∝S)=card(ΠA(S))/card(S)，其中card(ΠA(S))是关系S在关系R和S的公共属性A上投影所包含的不同元组的个数，card(S)是关系S的元组个数。5.4.1SDD-1算法的基本概念定义2：设R和S是两个关系，R和S半连接代价公式记为:cost(R∝S)=size(ΠA(S))=card(ΠA(S))×length(A)，其中length(A)是属性A定义的长度(字节数)。定义3：设R和S是两个关系，R和S半连接效益公式记为:benefit(R∝S)=(1-ρ(R∝S))×size(R)，其中size(R)表示关系R的大小(字节数)。5.4.1SDD-1算法的基本概念定义4：设R和S是两个关系，如果benefit(R∝S)-cost(R∝S)>0，则R和S半连接为有益半连接。定义5：在多个半连接中，benefit(R∝S)-cost(R∝S)结果最大的半连接为最有益半连接。5.4.2SDD-1算法SDD-1算法由两部分组成：基本算法和后优化。基本算法根据缩减代价公式来评估各执行策略的费用、收益等多种因素，然后给出所有半连接缩减的程序集，最后选择最有益的执行策略，但这个策略的效率不一定是最理想的。后优化是将基本算法得到的执行结果进行优化修正，以便得到更加合理的执行策略。5.4.2SDD-1算法SDD-1基本算法主要包括四个步骤:（1）初始化:找出所有关系中的半连接，计算这些半连接的选择因子和查询代价，生成有益的半连接集合；（2）选择最有益的半连接:从有益的半连接集合中找出最有益的半连接，将其添加到执行策略ES中（ES表的初始状态为空），并相应地修改被影响关系的统计值(选择因子，关系的大小等)；5.4.2SDD-1算法SDD-1基本算法主要包括四个步骤:（3）循环操作：重复第(1)步，直到所有有益的半连接加入到执行策略ES中。（4）选择组装场地：选择数据量最大的站点作为装配站点，其它的站点都将数据传输到这个装配站点，这样可以使得数据传输量最小，从而达到查询优化。5.4.2SDD-1算法SDD-1算法后优化可对算法进行两种修正：（1）若最后一次半连接缩减关系所在的站点正好是被选中的最终执行站点，那么最后的这次半连接就可以取消。（2）对基本算法的循环所构成的半连接的流程图进行修正。因为一开始的(或某一个)半连接缩减的代价可能很高但是收益评估却是很大的，如果有，这时可将这个关系进行缩减后再执行半连接缩减，这样就可以修正半连接的操作顺序了。5.4.3SDD-1算法案例已知有三个站点S1、S2和S3，这三个站点上分别存放着关系R1、R2和R3，且R1和R2的共同属性为A，R2和R3的共同属性为B，现有应用查询需要多关系连接如图所示。5.4.3SDD-1算法案例表5-2显示了R1、R2和R3三个关系的基本数据情况。表5-3显示了与R1、R2和R3的共同属性A、B有关的选择因子和半连接代价。

表5-2基本数据表5-3选择因子和半连接代价关系基数元组大小关系大小R130501500R2100303000R31038380属性选择因子半连接代价R1.A0.336R2.A0.8320R2.B1.0600R3.B0.4805.4.3SDD-1算法案例设有益半连接运算存储在BS表中，执行策略存储在ES表中,其中ES初始状态为空。第一轮循环:ES表(ExecutionStrategy):空BS表(benificalsemi_join):5.4.3SDD-1算法案例P1:R2∝R1benefit(R2∝R1)=(1-ρ(R2∝R1))×size(R2)=(1-0.3)×3000=2100；cost(R2∝R1)=36；benefit(R2∝R1)-cost(R2∝R1)=2100-36=2064>0；所以P1是有益半连接。5.4.3SDD-1算法案例P2:R2∝R3

benefit(R2∝R3)=(1-ρ(R2∝R3))×size(R2)=(1-0.4)×3000=1800；cost(R2∝R3)=80；benefit(R2∝R3)-cost(R2∝R3)=1800-80=1720>0；所以P2是有益半连接。5.4.3SDD-1算法案例P3:R1∝R2benefit(R1∝R2)=(1-ρ(R1∝R2))×size(R1)=(1-0.8)×1500=300；cost(R1∝R2)=320；benefit(R1∝R2)-cost(R1∝R2)=300-320=-20<0；所以P3是非有益半连接，舍去。5.4.3SDD-1算法案例P4:R3∝R2

benefit(R3∝R2)=(1-ρ(R3∝R2))×size(R3)=(1-1.0)×380=0cost(R3∝R2)=600benefit(R3∝R2)-cost(R3∝R2)=0-600=-600<0；所以P4是非有益半连接，舍去。5.4.3SDD-1算法案例第一轮循环所有半连接的cost、benefit等如表所示。在第一轮循环中最有益半连接为P1，将其从BS表中删除，加入ES表。调整统计数据，R2的有关数据如基数、关系大小、选择因子和代价得到调整。半连接benefitcostbenefit-cost是否有益半连接P12100362064是P21800801720是P3300320-20否P40400-600否5.4.3SDD-1算法案例设R2’´=R2∝R1，表5-5所示为进行R2’´=R2∝R1调整后的基本数据情况，表5-6所示为进行R2’´=R2∝R1调整后有关的选择因子和半连接代价。表5-5R2’=R2∝R1调整后的基本数据情况关系基数元组大小关系大小R130501500R2’3030900R310383805.4.3SDD-1算法案例表5-6R2’´=R2∝R1调整后的选择因子和半连接代价属性选择因子半连接代价R1.A0.336R2´.A0.2496R2´.B1.0600R3.B0.4805.4.3SDD-1算法案例第二轮循环：ES表：P1:R2∝R1BS表:P2:R2’´∝R3benefit(R2’´∝R3)=(1-ρ(R2’´∝R3)×size(R2’´)=(1-0.4)×900=540；cost(R2’´∝R3)=80；benefit(R2’´∝R3)-cost(R2’´∝R3)=540-80=460>0；所以P2是有益半连接。5.4.3SDD-1算法案例P3:R1∝R2’´benefit(R1∝R2’´)=(1-ρ(R1∝R2’´))×size(R1)==(1-0.24)×1500=1140；cost(R1∝R2’´)=96；benefit(R1∝R2’´)-cost(R1∝R2’´)=1140-96=1044>0；所以P3是有益半连接。5.4.3SDD-1算法案例P4:R3∝R2’´benefit(R3∝R2’´)=(1-ρ(R3∝R2’´))×size(R3)=(1-1.0)×380=0cost(R3∝R2’´)=600benefit(R3∝R2’´)-cost(R3∝R2’´)=0-600=-600<0；所以P4是非有益半连接，舍去。5.4.3SDD-1算法案例第二轮循环所有半连接的cost、benefit等如表5-7所示。表5-7第二轮循环所有半连接信息表第二轮循环中选择最有益半连接为P3，将其从BS表中删除，加入ES表中。调整统计数据，R1的有关数据如基数、关系大小、选择因子和代价得到调整。半连接benefitcostbenefit-cost是否有益半连接P254080460是P31140961044是P40400-600否5.4.3SDD-1算法案例设R1’´=R1∝R2’´，表5-8所示为进行R1’´=R1∝R2’´调整后的基本数据情况，表5-9所示为进行R1’´=R1∝R2’´调整后有关的选择因子和半连接代价。5.4.3SDD-1算法案例表5-8R1’´=R1∝R2’´调整后的基本数据情况表5-9R1’´=R1∝R2’´调整后的选择因子和半连接代价关系基数元组大小关系大小R1´7.250360R2’3030900R31038380属性选择因子半连接代价R1´.A0.0728.64R2´.A0.2496R2´.B1.0600R3.B0.4805.4.3SDD-1算法案例第三轮循环：ES表P1:R2∝R1；P3:R1∝R2’´；BS表:P2:R2’´∝R3benefit(R2’´∝R3)=(1-ρ(R2’´∝R3))×size(R2’´)=(1-0.4)×900=540；cost(R2’´∝R3)=80；benefit(R2’´∝R3)-cost(R2’´∝R3)=540-80=460>0；所以P2是有益半连接。5.4.3SDD-1算法案例P4:R3∝R2’´benefit(R3∝R2’´)=(1-ρ(R3∝R2’´))×size(R3)=(1-1.0)×380=0cost(R3∝R2’´)=600benefit(R3∝R2’´)-cost(R3∝R2’´)=0-600=-600<0；所以P4是非有益半连接，舍去。5.4.3SDD-1算法案例第三轮循环所有半连接的cost、benefit等如表5-10所示。表5-10第三轮循环所有半连接信息表第三轮循环中选择最有益半连接为P2，将其从BS表中删除，加入ES表中。调整统计数据，R2’´的有关数据如基数、关系大小、选择因子和代价得到调整。半连接benefitcostbenefit-cost是否有益半连接P254080460是P40400-600否5.4.3SDD-1算法案例设R2’’=R2’´∝R3，表5-11所示为进行R2’’=R2’´∝R3调整后的基本数据情况，表5-12所示为进行R2’’´=R2’´∝R3调整后有关的选择因子和半连接代价。表5-11R2’’=R2’´∝R3调整后的基本数据情况关系基数元组大小关系大小R1´7.250360R2´´1230360R310383805.4.3SDD-1算法案例表5-12R2’’=R2’´∝R3调整后的选择因子和半连接代价属性选择因子半连接代价R1´.A0.0728.64R2´´.A0.2496R2´´.B0.4240R3.B0.4805.4.3SDD-1算法案例第四轮循环：ES表P1:R2∝R1；P3:R1∝R2’´；P2:R2’∝R3；BS表:P4:R3∝R2’’´´benefit(R3∝R2’’´´)=(1-ρ(R3∝R2’’´´))×size(R3)=(1-0.4)×380=228；cost(R3∝R2’’´´)=240；benefit(R3∝R2’’´´)-cost(R3∝R2’’´´)=228-240=-12<0；所以P4是非有益半连接。5.4.3SDD-1算法案例到此为止，所