第3章+分布式数据库中的查询处理和优化.ppt

分布式查询优化概述分布式查询优化基础知识分布式查询分类和层次结构基于关系代数等价变换的查询优化处理基于半连接算法的查询优化处理基于直接连接算法的查询优化处理直接连接操作的常用策略,分布式数据库中的查询处理和优化,第3章,查询处理问题,集中式查询转换为代数表达式从所有等价表达式中选择最优的代数表达式分布式除了集中式问题外，还有站点之间交换数据的操作选择最优的执行站点(分布）数据被传送的方式,目标,总代价最小,响应时间最短,集中式,分布式,CPU代价（相对固定）,I/O代价（优化的目标）,CPU代价,I/O代价（访问磁盘）,通讯代价,数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间,主要标准辅助标准,准则：使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。通讯费用与所传输的数据量和通信次数有关响应时间和通信时间有关，也与局部处理时间有关查询代价分析远程通讯网络局部处理时间可以忽略不计，减少通讯代价是主要目标高速局域网传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理时间是关键,例子S(s#,sname,age,sex)104元组SiteAC(c#,cname,teacher)105元组SiteBSC(s#,c#,grade)106元组SiteA每个元组长度100bit,通讯传输速度104bit/sec,通讯延迟1sec,查询:所有选修maths课的男生学号和姓名.SELECTs#,snameFROMS,C,SCWHERES.s#=SC.s#ANDC.c#=SC.c#ANDsex=男ANDcname=maths;,代价公式QC=I/O代价+CPU代价+通讯代价通讯代价TC=传输延迟时间C0+(传输数据量X/数据传输速率C1)=传输次数*1+传输的bit数*104。,六种查询策略,六种查询策略,相关表述记号,设关系模式为R(A1,A2,An)。它的一个关系设为R。tR表示t是R的一个元组。tAi则表示元组t中相应于属性Ai的一个分量。,若A=Ai1,Ai2,Aik，其中Ai1,Ai2,Aik是A1,A2,An中的一部分，则A称为属性列或域列。tA=(tAi1,tAi2,tAik)表示元组t在属性列A上诸分量的集合。则表示A1,A2,An中去掉Ai1,Ai2,Aik后剩余的属性组。,相关表述记号,给定一个关系R(X,Z)，X和Z为属性组。我们定义，当tX=x时，x在R中的象集（ImagesSet）为：Zx=tZ|tR,tX=x它表示R中属性组X上值为x的诸元组在Z上分量的集合。,传统的集合运算,并运算,设关系R和关系S具有相同的目n（即两个关系都有n个属性），且相应的属性取自同一个域，则关系R与关系S的并由属于R或属于S的元组组成。其结果关系仍为n目关系。记作：RS=t|tRtS,差运算,传统的集合运算,交运算,R1R2,设关系R和关系S具有相同的目n，且相应的属性取自同一个域，则关系R与关系S的交由既属于R又属于S的元组组成。其结果关系仍为n目关系。记作：RS=t|tRtS,传统的集合运算,两个分别为n目和m目的关系R和S的广义笛卡尔积是一个(n+m)列的元组的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。若R有k1个元组，S有k2个元组，则关系R和关系S的广义笛卡尔积有k1k2个元组。记作：,广义笛卡尔积,专门的关系运算,S(S#,SN,SD,SA),选择运算是从关系中选取使公式为真的元组。这是从行的角度进行的运算。,在关系R中选择满足给定条件的元组，记做：F(R)=t|tRF(t)=真F是一个公式，表示形式为由逻辑运算符（,)连接各算术表达式组成。算术表达式的基本形式为：XY.=,card（R），可减少站点间的数据传输量半连接的损失：传输B(S)=C0+C1*size(B)*val(BS)基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价采用半连接优化算法的步骤计算每种半连接方案的代价，并从中选择一种最佳方案选择传输代价最小的站点，计算采用全连接的方案的代价比较两种方案，确定最优方案,半连接算法和直接连接算法区别取决于数据传输和局部处理的相对费用如果传输费用是主要的，采用半连接，SDD-1如果本地费用是主要的，采用直接连接,SystemR*四种基于直接连接的优化算法（考虑关系分段）利用站点依赖信息的算法分片与复制算法站点依赖和数据复制结合算法Hash划分算法,R1R2,站点依赖设关系Ri分片Fi1和Fi2,Rj分片Fj1和Fj2关系Ri和Rj在属性A上满足条件FisAFjt=,其中st,则称Ri和Rj在属性A上站点依赖也就是说:RiARj=U(FisAFjs),对于包含着两个关系的片段的每个站点s都成立此时关系的连接操作无站点间数据传输,Ri,Rj,本地连接,Result,A,f(A),f(A),Ri,Rj,推论若Ri和Rj在属性A上站点依赖，则Ri和Rj在任何包含A的属性集B上也站点依赖。若Ri和Rj在属性A上站点依赖，另一属性（或属性组）B函数决定A，且A，则Ri和Rj在B上也站点依赖。若Ri和Rj在属性A上站点依赖，且若Rj和Rk在属性B上站点依赖，则（RiARjBRk）=（FisAFjsBFks)查询RiARjBRk的连接操作能够以无数据传输的方式处理。,算法描述Placement_Dependency(Q,P,S)，其中：R=R1,R2,R3,Rn是查询Q引用的一组关系P是站点依赖信息S是一个连接操作可以无数据传输的执行的最大关系集合开始时S是空集。算法结束时，若S=R,则Q可以无数据传输执行算法步骤初始化S=，R=R1,R2,R3,Rn若能找到一对关系Ri和Rj在属性A上站点依赖，且RiCRj包含在Q中，其中C包含A,那么把Ri和Rj放到S中，否则算法终止，返回空集S。只要存在R中而不在S中的关系Rk满足下面的特性，就把其放入S中：有S中的关系比如Rj，与Rk在属性B上有站点依赖关系，且RjBRk在Q中或者可以由Q导出，根据推论3，则Rk可被包含在S中。,查询引用的某个关系的所有片段分布在这些站点上,其余被引用的关系复制到每一个选定的站点R1R2=Ui(F1iR2)算法可应用到涉及两个或两个以上的关系的查询其中一个关系保持分片状态其他关系可先连接起来，再被复制到各个站点在各个站点上，其他关系副本与相应的第一个关系的片断连接,R1,R21,R22,本地连接,Result,fpartition,union,R1,R2,如何确定保持分片关系的关系，以使得查询具有最短的时间估算各种策略的响应时间，选择时间最短的策略，S1站点上响应时间(完成时间，FT(Q,S1,R1)）包括三部分，以P.85图为例：F22到S1的数据传输时间F22和F21进行合并形成S1上的R2副本的时间F11和S1上的R2副本之间连接的时间比较MaxFT(Q,S1,R1),FT(Q,S2,R1),MaxFT(Q,S1,R2),FT(Q,S2,R2)，找出响应时间小的保持分片关系算法忽略了把结果传送到要求答案的用户站点的代价，和将部分结果组装成最终结果的代价，认为它们不大重要，或者采用其他算法时这些部分没有太大差别。,Fragmentation_and_replicate(Q,R,S)For每个保持分片状态的关系RiFor每个包含关系Ri的一个片段的站点Sj计算在站点Sj执行子查询的完成时间FT(Q,Sj,Ri)计算关系Ri保持分片状态下的响应时间Ti=maxj(FT(Q,Sj,Ri)选择Rk=mini(Ti)为保持分片状态的关系,R1,R2,R2,R2,F11,F13,F21,F22,本地连接,Result,fpartition,union,R1,R2,F12,举例已知R1分段F11和F12的大小为:|F11|=|F12|=50R2分段F21和F22的大小为:|F21|=100|F22|=200设数据通讯C0=0,C1=1,本地连接Cost=J(x1,x2)=5*(x1+x2)并操作Cost=U(x1,x2)=2*(x1+x2)令R1保持分片状态,则:站点S1的完成时间FT(Q,S1,R1)=200+2*(100+200)+5*(50+300)=2550同理:FT(Q,S2,R1)=100+2*(100+200)+5*(50+300)=2450因此,查询响应时间在R1保持分片状态为2550.,令R2保持分片状态,则:站点S1的完成时间FT(Q,S1,R2)=50+2*(50+50)+5*(100+100)=1250同理:FT(Q,S2,R2)=50+2*(50+50)+5*(200+100)=1750因此,查询响应时间在R2保持分片状态为1750.因为:R1保持分片状态的响应时间R2保持分片状态的响应时间所以:选择R2保持分片计算查询,站点,关系,R1,R2,R3,设R1和R2在属性A上站点依赖,查询R1AR2BR3,设R1和R2在属性A上站点依赖,查询R1R2R3第一个连接因为站点依赖，无传输处理第二个连接因为存在R3的副本,也没有传输处理保证查询无传输的方法是R1和R2连接执行后，形成一个关系R4，它有两个片断：一个由F11F21给出一个由F12F22给出最后由R4和R3的副本连接得到最后的结果,连接依赖定义：如果Ri和Rj在属性A上站点依赖或者关系Ri复制在关系Rj各片断的站点上或者关系Rj复制在关系Ri各片断的站点上有了此定义，站点依赖算法可理解为：利用站点依赖和复制信息来确定一个查询中的连接能否无数据传送处理。,利用Hash函数对分片关系上的连接属性作站点依赖计算,再据此分片,以获取站点依赖的连接算法例如,运用Hash函数1若a是奇数0若a是偶数对R中每个元组,h(a)为1送入站点S1,h(a)为0送入站点S2.于是片段关系R被划分为Ro和ReR1R2=(R1oR2o)U(R1eR2e),h(a),=,利用Hash函数对分片关系上的连接属性作站点依赖计算,再据此分片,以获取站点依赖的JN算法例如,运用Hash函数1若a是奇数0若a是偶数片断F11按属性A的值为奇和偶数划分成F11o和F11e，片断F12划分成F12o和F12e站点S2上F12=F11eF12e，站点S1上F11=F11oF12o显然A(F11)和A(F12)没有公共值,前面是奇数值后面是偶数值F12F11是空集，这说明R1和R2在新组成的片断下在属性A上站点依赖。R1R2=（F11F21）U（F12F22）,h(a),=,考察三个关系R1，R2和R3,它们在两个站点上，有两种情况：在同一属性A上连接，R1AR2AR3在三个关系的片断上应用Hash函数使用新组建的片断，三个关系在属性A上将满足站点依赖经这种划分和数据传送之后，两个站点上的片断在属性A上的连接就可以并行进行，合并执行结果给出答案在不同属性上连接，R1AR2BR3,在不同属性上连接，R1AR2BR3在属性A上应用同样的Hash函数，在属性B上也应用同样的Hash函数，可能得不到希望的站点依赖因R1中属性A的值是奇数的发往S1，R3中属性B是奇数的元组发往S1.但R2中某些元组可能在A上有奇数值，而在B上有偶数值解决方法是允许这些元组在两个站点上都存在。,R1AR2BR3若R1与R2在A上有相同的Hash函数,R2与R3在属性B上有相同的Hash函数,站点依赖算法无数据传递可利用索引做本地连接每个站点连接数据总量是R，两个片段分片和复制算法数据传输总量是R数据传送后,可能要重新创建索引每个站点的连接数据量是(3/2)R,一个全关系和一个片断Hash划分算法数据传送量是R索引方面,比片段复制算法效率更低（因为数据传送后，两个关系的索引可能都不能使用了）每个站点的连接数据量同站点依赖,假定每个片段的大小是R大小的一半R/2,两个关系在同一个站点，RS，称外层关系为R,内层关系为S嵌套循环法顺序扫描外层关系R，对于R的每一元组扫描内层关系S查找在连接属性上一致的元组，组合起来构成结果的一部分需要扫描一次关系R和Card（R）次关系S排序扫描法先把两个关系按照连接属性进行排序然后按照连接属性值的顺序扫描这两个关系，使匹配的元组成为结果的一部分对两个关系都扫描一次，但增加了排序代价,两个关系在不同站点，关系R和关系S两种传输方式整体传输如果传输S,则保存S（被多次扫描，传输量少）如果传输R，则S可直接使用一次来到的R元组，不保存R(但传输量大）按需传输只传输需要连接的元组，一次一个元组，无需临时存储器每次提取都要交换一次信息，传输代价高，只在高速局域网中才是合理的三种选择连接站点的方法R站点S站点其他站点,一个操作内的并行一般是不可行的多个操作间的并行是可行的流水线并行在查询表达式中，一个操作A的输出元组作为第二个操作B的输入在第一个操作尚未产生全部的输出元组集合之前，第二个操作就可以在它的输入上进行工作可以在不同的站点上运行A和B，在A产生部分结果元组的同时，B来使用它们独立的并行查询表达式中，那些相互之间没有依赖关系的操作可以并行地执行,例子：R1R2R3R4有很多策略，其中一个是两种并行方法结合使用：把R1送到S2并在S2上计算R1R2，同时把R3送到S4上计算R3R4在站点S2上计算R1R2的过程中，就