第三章分布式数据库中的查询处理和优化发布订阅系统.ppt

第三章 分布式数据库中的查询处理和优化发布/订阅系统,王静 张洪梅 王蕾,主要内容：3.1 分布式查询优化概述3.2 分布式查询优化中的基础知识3.3 分布式查询的分类和层次结构3.4 基于关系代数等价变换的查询优化处理3.5 基于半连接算法的查询优化处理3.6 基于直接连接算法的查询优化处理3.7 直接连接操作的常用策略3.8 小结,3.1 分布式查询优化概述 分布式查询处理是用户与分布式数据库系统的接口，也是分布式数据库研究的主要问题之一。,3.1.1 分布式查询优化的目标总代价最小 集中式CPU,I/O 代价 分布式CPU,I/O通讯代价时间代价 响应时间,3.1.2 分布式查询优化的准则和代价估算1.查询优化的准则 分布式查询优化的准则是使通信费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。2.查询代价分析（1）在远程通信网络中 常常以减少传输的次数和数据量作为优化的重要目标。,（2）在高速局域网中 以响应时间作为优化目标 在某些情况下，查询处理同时以减少通信费用和响应时间为优化目标。,3.查询代价的估算方法设一个查询执行的预期代价为QC，则代价公式集中式:QC=I/O 代价+CPU 代价 分布式：QC=I/O 代价+CPU 代价+通讯代价通信代价（粗略计算）TC(X)=传输延迟时间C0+(数据传输速率C1*传输数据量X),3.1.3分布式查询策略的重要性 在分布式数据库系统中，查询优化包括两个内容：查询策略优化和局部处理优化，而查询策略优化尤为重要。例3.1 在教学数据库里，有 S(S#,SNAME,AGE,SEX)有104个元组，在站点A存放 C(C#,CNAME,TEACHER)有105个元组，在站点B存放 SC(S#,C#，GRADE)有106个元组，在站点A存放假定：若每个元组的长度均为100b 通信系统的传输速度为104 b/s 通信延迟时间为1s问题:要求查出所有选修MATHS课的男同学的学号和姓名。,解：SQL语句是：SELECT S#,SNAME FROM S,C,SC WHERE S.S#=SC.S#AND C.C#=SC.C#(连接条件)AND SEX=男 AND CNAME=MATHS(选择条件)通讯代价的估算公式：T=传输延迟时间C0+(传输数据量X*数据传输速率C1)=(传输次数*1)+(传输的bit数/104)为了实现这一查询，可以有六种可能的查询策略，下面分别对六种策略进行代价估算。,策略1：A 传C B 把关系C传输到A地，在A地处理 查询T1=1+(105*100/104)S,SC 通信1次 C 103秒16.7分钟策略2：A 传S,SC B 把关系S和SC传输到B地，在B地 处理查询T2=2+(104+106)*100/104 S,SC 通信2次 C 10100秒2.8小时策略3：A 问105 B 先在A地求出男学生的成绩元组有 105，再根据C#的值询问B地，核 答105 实是否C=MATHS,T3(2*105*1)S,SC C=2*105秒2.3天,策略4：A 问10 B 先在B地求出MATHS的元组，有10 个，再根据C#的值询问A地的S,SC 答10 的连接，核实是否为选修MATHS的 S,SC C 男生,T4(2*10*1)=20秒策略5：A 传输105 B 先在A地求出男生选课元组，有105 个，再把结果传输到B地，在B地执 S,SC 通信1次 C 行查询，T5=1+(105*100)/104 1000秒=16.7分钟策略6：A 传输10 B 先在B地求出MATHS的元组，有10个，再把结果传输到A地，在A地执行查 S,SC 通信1次 C 询，T6=1+(10*100)/104 1秒,3.2分布式查询优化中的基础知识3.2.1用关系代数表达式和SQL语句表示一个查询 例3.2 三个全局关系：学生信息表：S(S#,SNAME,AGE,SEX)课程设置关系：C(C#,CNAME,TEACHER)选课关系：SC(S#,C#，GRADE)查询选修课程号为C03的学生姓名。SQL语句与关系代数表达式的等价描述SELECT SNAME FROM S,SC WHERE S.S#=SC.S#AND SC.C#=C03;代数描述 E1=sname(s.s#=sc.s#and sc.c#=C03(SSC),SELECT SNAME FROM S WHERE S.S#IN(SELECT SC.S#FROM SC WHERE C#=C03)代数描述 E2=sname(s.s#=sc.s#(S(sc.c#=c03(SC)SELECT SNAME FROM S,(SELECT SC.S#FROM SC WHERE C#=C03)SC WHERE S.S#=SC.S#;代数描述 E3=sname(S(sc.c#=c03(SC)E3的执行效率最好。,3.2.2 查询树 对一个关系代数表达式表示查询，进行语法分析，可以得到一棵语法树。树的叶子是已知的关系，树的各个节点是关系代数操作符，树的根是查询的结果，所以也称操作符树。用语法树来描述一个查询要求，更加清晰、更加直观，且易于分析和调整查询问题的具体操作次序。因此，语法树又称查询树。对于例3.2中的查询要求，对应于三个关系代数表达式的查询树如下图：,用查询树表示的查询要求：,s.s#=sc.s#SC.c#=c03,S,SC,sname,sname,s.s#=SC.s#,S,c#=c03,SC,sname,S,c#=c03,SC,对于E1的查询树,对于E2的查询树,对于E3的查询树,3.2.3等价变换规则的概念和术语1.关系代数表达式的等价 E1E22.一元操作与二元操作一元操作 选择(),投影()二元操作 并(),交（）,差(-),除（），迪卡儿积（），连接（），连接（），半连接（）,3.2.4 等价变换规则空值的变换 R R R-R-R R R R R R R F()其中F为选择条件A()其中A为投影的属性集自身操作的等价R R R R R R R R R一元操作选择的串接：F1(F2(E)F1 F2(E)(R)(R)投影的串接：A1,An(B1,Bm(E)A1,An(E)这里要求A1,An必须是B1,Bm中的属性,一元操作交换律 1(2(R)2(1(R)条件:1 2 是选择操作时总成立 1 2 是投影操作时，要求其属性集合相等 1 与 2 是选择和投影操作符时地交换:A1,An(F(R)F(A1,An(R)的条件是 F中的属性是 A1,.An 的子集二元操作交换律 RBSSBR（B，B为二元操作符）二元操作结合律 RB(SBT)（RBS）BT,一元操作对二元操作的分配律(RBS)(R)B(S)(1)选择对笛卡儿积的分配律 F(RS)F(R)S(F只涉及R中的属性)如果F形为F1 F2,且F1只涉及R的属性，F2只涉及S的属性，那么可以得到下面的定律：F(RS)F1(R)F2(R)如果F形为F1 F2,且F1只涉及R的属性，F2只涉及R和S的属性，那么可以得到下面的定律：F(RS)F2(F1(R)S)(2)选择对并的分配律 F(RS)F(R)F(R)这里要求R和S有相同的属性名，或涉及的关系的属性有对应性。,(3)选择对差的分配律 F(RS)F(R)F(S)这里要求R和S的属性有对应性。(4)选择对自然连接的分配律 F(RS)F(R)F(S)(5)投影对笛卡儿积的分配律 B1,Bm,C1,Ck（RS）B1,Bm(R)C1,Ck(S)这里要求B1,Bm是R中的属性，C1,Ck是S中的属性。(6)投影对并的分配律 A1,An(RS)A1,An(R)A1,An(S)这里要求R和S的属性有对应性。,3.3 分布式查询的分类和层次结构3.3.分布式查询的分类局部查询只涉及本地、单个站点的数据,优化同集中式远程查询也只涉及单个站点的数据,但要远程通讯,选择站点注：为了减少远程查询的通信代价，如果数据是冗余分 配，应尽可能选择距发出查询应用的站点最近的 站点上的数据或数据片断作为查询的对象。全局查询涉及多个站点数据,优化复杂,为了执行全局查询并确定一个好的查询策略，需要做许多判断和计算工作。这些工作大致可归为如下四类：（1）具体化 确定查询使用的物理副本，落实查询对象 非冗余具体化 冗余具体化（2）确定操作执行的次序 主要是确定二元操作连接和并操作的次序（3）确定操作执行的方法 包括把若干个操作连接起来在一次数据库访问中执行，确定可用的访问路径，以及确定某种计算方法等。（4）确定执行站点 主要考虑通信代价和执行效率，一般选择离提供数据的站点较近的站点，而考虑到查询速度的因素，还应尽量选择空闲的站点执行查询操作。,分布查询处理的层次模式,分布式查询问题,查询分解,全局模式,数据本地化,全局优化,局部优化,优化的局部查询,全局查询代数表达式,片段查询,包括通信操作的优化片段上的查询,分片模式,片断统计,局部模式,3.4基于关系代数等价变换的查询优化处理1.基本原理 把查询的问题转变为关系代数表达式，分析得到查询树（语法树），进行全局到片段的变换得到基于片段上的查询树，然后利用关系代数表达式规则的优化算法，尽可能先执行选择和投影操作。关系代数等价变换规则的优化算法:利用关系代数等价变换规则，把查询树中的连接和合并操作尽可能上提（向树根方向移），选择和投影操作尽可能下移（向树叶方向移）到片段的定义处。注：尽可能先执行选择操作和投影操作。,2.实现步骤和方法（1）将一个查询问题转换成关系代数表达式（2）从关系代数表达式到查询树的变换 方法：查询树的根节点是最终的查询结果，叶节点是查询 涉及的所有关系或片断，中间节点是按代数表达式 中的操作顺序组成的一组关系操作符。（3）从全局查询到片段查询的变换 典型方法：把基于全局关系的查询树中的全局关系名，用 其重构该全局关系的各片段名替换，变换成相应片 段上的查询树。（4）利用关系代数等价变换规则的优化算法，对片段上的查询树进行优化处理，最后达到优化查询的目的。,3.4.2 基于关系代数等价变换的查询优化处理举例例3.3 数据库中的全局关系S(s#,sname,age,sex)和SC(s#,c#,grade)被水平分片，如图所示：S SC h hS1:sex=M S2:sex=F SC1:c#20 SC2:c#20男学生全体 女学生全体 课程号20 课程号20 图：3.4全局关系S和SC的水平分片查询问题：查找至少有一门功课的成绩在90分以上的男同学 姓名。SQL语句：SELECT DISTINCT sname FROM S,SC WHERE S.s#=SC.s#AND sex=M AND grade 90,关系代数表达式：sname(sex=M grade90(s.s#=SC.s#(SSC)查询树：图：3.5等价变换规则用于水平分片的情形 sname 变换 S.S#=SC.S#s#,sname grade90 s#,sname grade90 sex=M U sex=M SC U SC1 SC2 S S1 S2 C#C20 C#C20 SEX=M SEX=F a.全局关系上的查询树 b.对应片段上的查询树,sname,sname sname 产生矛盾去掉一只 S.S#=SC.S#S.S#=SC.S#U U s#,sname Us#,sname s#,sname grade90 grade90 S1sex=M sex=M sex=M SC1 SC2 SC1 SC2 C#C20 C#C20 C#C20 C#C20 grade90 grade90 S1 S2sex=M sex=Fc.把投影和选择下移后的查询树 d.简化的查询树,水平分片关系优化的基本思想：首先，尽可能把选择条件下移到分片的限定关系处，再把分片的限定关系与选择条件进行比较，然后去掉它们之间存在矛盾的相应片段。如果最后剩下一个水平片段，则重构全局关系的操作中，就可以去掉“并”操作（至少可以减少“并”操作的次数）。,例3.4有全局关系EMP(emp#,ename,salary,dept#,dname),如果被垂直分片，分成如下两个片段：E1(emp#,dept#，dname)E2(emp#,ename,salary)查询：雇员的姓名和工资情况。SQL语句：SELECT ename,salary FROM EMP关系代数表达式：ename,salary(EMP)它的查询树如下页所示：,图3.6 等价变换规则用于垂直分片的情形ename,salary ename,salary 移植到片段上 EMP E1.EMP#E2.EMP#emp#,dept#,deptname E1 E2:emp#,ename,salary 去掉无关的片段ename,salary ename,salary 去掉连接E2:emp#,ename,salary emp#,ename,salary,垂直分片关系优化的基本思想：把垂直分片所用到的属性集，与查询条件（查询表达式）中的投影操作所涉及的属性集相比较，去掉无关的垂直片段。如果只剩下一个垂直片段与查询有关时，去掉重构全局关系的“连接”操作（至少可减少“连接”操作的次数）。,3.5基于半连接算法的查询优化处理选择、投影和连接是最常用的三种操作。选择：关系（R），如果R是一个全序关系，那么简单地在包 含R的站点上执行选择操作，然后再把结果发送给用 户站点。如果R被分片，那么在每一个包含R片段的站 点上执行选择操作，然后再将这些结果合并得到最后 的结果，发送到用户站点。投影：它与选择操作处理的唯一不同之处在于投影操作所得 到的结果中可能包含重复的元组，需要作删除操作。连接：是常用而且代价较高的一种操作。为了使分布式数据 库系统可以高效的处理连接操作，人们作了大量的研 究，形成了各种不同的算法。,3.5.1 采用半连接操作 1、半连接操作 半连接操作是由投影和连接操作导出的一种关系代数操作。假定有两个关系R和S，在属性R.A=S.B上作半连接操作（这里的“关系”也可以指片段）可表示为：RA=B S=R(RA=BS)=RA=B(B(S)或者 SA=B R=S(SA=BR)=SA=B(A(R)注意：半连接操作不具有对称性，即RS SR 但是，半连接具有可分配性：(R1R2)S=(R1S)(R2S).此式中的操作符用或者是-代替时等式也成立。如果采用半连接方法表示这两个关系R和S，在属性R.A=S.B上作连接操作，则有 RA=BS=（RA=BS）A=BS或者 RA=B S=（SA=BR）A=BR 其中等式右边的括号内称为“半连接”.,举例说明半连接：两个关系R:S:1.RB=BS(等值连接)2.R(RB=BS),2、采用半连接操作方法表示连接操作的操作过程和代价估算当连接用半连接表示时，有 RA=BS=（RA=BS）A=BS=（RA=BB(S)A=BS或者 RA=BS=（SA=BR）A=BR=(SA=BB(R)A=B R采用半连接方法表示连接操作其操作过程如图：站点1 站点2(1)B(S)(2)B(S)(3)R=RA=BS(5)RS(4)R=RA=BS,R,网 络,S,代价可用下式估算：(1)在站点2上作关系R和S公共属性值B上的投影B(S);(2)把B(S)结果送到站点1，代价为 C0+C1*size(B)*val(Bs)其中size(B)为属性B的长度，val（Bs）为关系S中属性B上不同值的各个数。(3)在站点1上作半连接，设其结果为R,则R=RA=BS；(4)把R从站点1送到站点2的代价是：C0+C1*size(R)*card(R)其中card(R)为R的元组数(5)在站点2上执行连接操作：RA=BS；采用半连接方案的总代价为：T半R=2 C0+C1*（size(B)*val(Bs)+size(R)*card(R)）或者 T半s=2 C0+C1*（size(A)*val(AR)+size(S)*card(S)）传输代价计算公式：T=C0+C1*X,3.5.2 采用半连接算法优化连接操作的基本原理和步骤 T全=C0+C1*size(B)*card(R)基本原理：采用半连接实现连接操作需要两次数据传输：连接属性投影结果和半连接结果，但在通常情况下，这两次数据传输的总量要远远小于传输一个整个关系的数据量，因此，一般地有T半T全 得益：当card(R)card(R)时，可以减少站点间的数据 传输量。损失：传输B(S)=C0+C1*size(B)*val(Bs),由此，得到基本原理：经半连接操作，可减少操作关系的数据量，从而减少站点间数据的传输量。在从一个站点传送关系到另一个站点作连接之前，先除去那些与连接无关的数据，减少作连接操作的关系中的数据量，从而减少传输的代价2.采用半连接算法优化连接查询的步骤：(1)计算每种可用的半连接方案代价，并从中选择一个最佳的方案，作为T半(2)选择传输代价最小的站点，计算采用全连接的方案的代价(3)比较两种方案，确定最优的方案。,3.6基于直接连接算法的查询优化处理,-连接操作的查询优化算法的选择：传输费用是主要的-半连接 局部处理是主要的-直接连接-四种处理直接连接查询优化的算法：利用站点依赖信息的算法 分片和复制算法 站点依赖和数据复制结合 Hash划分算法,关系R1和R在属性A上的自然连接,已知关系 分片情况例子,s1,s2,3.6.1利用站点依赖信息的算法,站点依赖：两个片断关系Ri和Rj，在属性A上满足条件FisFjt=,其中St,则称Ri和Rj在属性A上站点依赖。根据站点依赖可以得到：R1R2=（F11F21）（F12F22）,从站点依赖的定义可以得到如下观察：（1）、如果 Ri和Rj在A上站点依赖，则Ri和Rj在任何包含A的属性集B上也站点依赖。元组减少（2）、如果 Ri和Rj在A上站点依赖，另一个属性（或属性组）B函数决定A（即B-A）,且A，则Ri和Rj在B上也站点依赖。元组减少（3）、若Ri和Rj有站点依赖A，而且Ri和Rj有站点依赖B，则 RiARjBRk=(FisFjsFks），其中s为所有包含Ri,Rj和Rk的片断的任一个站点。或者说，所有的连接操作可以在本地完成而没有数据传递。,（4）、查询RiARjBRk连接操作能够以无数据传输方式处理。需要满足的条件：A查询Q:RiARjBRk B子查询Q：RiARj Q中的连接可以无数据传输的方式执行 C Rj和Rk有站点依赖B 则查询Q就可以实现无数据传输。解释：RiARj是取Ri，Rj在属性值A上相等的元组。对于Rj说必然是只取一部分，令连接的最后结果是R。由于Rj和Rk有站点依赖B，故R 与Rk也必然站点依赖B,故R BRk也可以在无数据传递的方式下进行。,站点依赖算法：Placement_Dependency(Q,P,S)其中：R=R1,R2,.Rn是一个查询Q引用的一组关系，P是站点依赖信息 S是一个连接操作可以无数据传送执行的最大关系集合初态：S是空集，R=R1,R2,.Rn终态：如S=R，则Q可以无数据传送执行。,1）初始化：S=；R=R1,R2,.Rn。2)如果能找到一对关系Ri和Rj，使得Ri和Rj在属性A上站点依赖，且RicRj包含在Q中，其中C包含A，那么把Ri和Rj放入S；否则，算法终止，返回空集S。3）只要存在R中而不在S中的关系Rk满足如下特性，就循环作：把Rk插入S。特性如下：有S中的关系，比如Rj，与Rk在属性集B上有站点依赖关系，且Rj BRk在Q中或可以由Q中导出，则Rk可被包含入S中。4）如果S=R，则Q可以无数据传送处理。,例子：有查询（R1AR2BR3 CR4）,假定R1和R2在属性上A站点依赖，R2和R3在属性B上站点依赖,R3和R4在属性C上站点依赖.开始时，S为空；在执行了第2）步之后，两个关系比如R1和R2将被放入S；接下来R3由于和R2在属性B上站点依赖及R2和R3之间的连接条件（R2BR3），也被加入到S；最后，R4由于和R3在属性C上站点依赖及有连接条件，也被加入到S中。这样S=R1，R2，R3，R4，查询引用的所有关系都包含进S中，因此查询可无数据传送处理。,3.6.2 分片和复制算法,连接操作在本地站点执行，合并得到最后连接结果用于处理查询不能在无数据传输的方式下进行连接的算法。选择一组站点，把查询引用的某个关系的所有分片分布在这些站点上，其余被引用的关系则复制到每一个选定站点中。例子：得到：R1R2=i（F1i R2）其中的并操作遍取每一个有Ri分片的站点Si,如何确定哪个关系让它保持分片状态?,原理：如上图，有两种策略R1或R2处于分片状态。对每一个策略，计算预期的响应时间即完成查询处理的响应时间，从中选择具有最短响应时间的策略。假设让R1保持分片状态，则站点S1上的时间代价：A.F22到S1的数据传送时间 C0+C1*|F22|B.F22 和F21进行合并，形成S1上R2副本的时间 C.F11和S1上R2之间进行连接运算的时间,如何确定哪个关系让它保持分片状态?,把以上时间的总和称为：完成时间,记为FT（Q，S1，R1），表示在站点S1 上处理的总时间的估值，同样可以得到FT（Q，S2，R1），由于不同的站点之间操作可以并行处理，因此，在R1 保持分片状态下，整个查询时间由Max FT（Q，S1，R1）,FT（Q，S2，R1）给出。把这个值与Max FT（Q，S1，R2）,FT（Q，S2，R2）作比较，拥有最小响应时间估值的关系别保留作分片状态。这一原理可以推广到多个站点，多个分片和多个关系查询中。,如何确定哪个关系让它保持分片状态?,例3.6 比较简单，其中两个直接给出结果的完成时间计算式子如下：FT（Q，S1，R2）=50+2*(50+50)+5*(100+100)=1250FT（Q，S2，R2）=50+2*(50+50)+5*(200+100)=1750,启发式算法,在实际应用中，不同的站点有不同的处理速度，以及某些站点的某些关系可能存在快速存取路径或索引，而另外一些则没有，因此查询优化也要考虑这些类型的信息，以获得一个有效的执行策略。（1）、任意选择一个关系Ri，让它保持分片状态，且用包含Ri的各片断的站点作为处理站点。这些站点之一，比如Sj具有最大的估计完成时间。（2）、对每一个站点St(包含初始的处理站点及不含Ri片断的站点)，如果片断Fij由站点Sj移动到St，估计在站点St处理子查询的完成时间,启发式算法,（3）、如果存在一些站点St，其估计完成时间低于站点Sj，则选择具有最小估计完成时间的站点St0，把片断Fij由站点Sj移动到St0。（4）、对Ri的每一个分片重复这样的操作，直到这种改变不能进一步降低单个站点的完成时间。（5）、分别使每个不同的关系保持分片并重复以上处理过程，通过启发式方式跟踪每一个关系保持分片时的最小相应时间估值，这些关系中具有最小相应时间估值者将保持分片状态。,3.6.3 站点依赖和数据复制结合,可以通过结合站点依赖信息和数据复制信息，使得特定查询以无数据传送的方式进行 如图：（数据分布）假定R1和R2在属性A上站点依赖，且有R1AR2BR3，第一个连接因站点依赖可以无数据传输，第二个连接因R3的副本可以无数据传输。,连接依赖：如果1）关系 Ri和Rj 在属性A上站点依赖，或者2）关系Ri复制在关系Rj各片段的站点上，或者3）关系Rj复制在关系Ri各片段的站点上,则称关系Ri 和Rj在属性A上连接依赖。对此我们可以把站点依赖算法Placement_Dependency(Q,P,S)做以改进得到连接依赖算法Join_Dependency(Q,P,S)：对算法中的2)和3)，如果两个关系满足站点依赖就加入集合S改为满足连接依赖。很多时候，数据分布不满足连接依赖，这个时候就需要利用分片和复制算法使其满足条件，可以实现无数据传递。,3.6.4 Hash划分算法（一种处理不满足连接依赖的查询算法）,例子：假定在属性A上作连接且A只取整数值，作Hash函数h(a):如果a是奇数，h(a)=1，发送到站点S1；如a是偶数，h(a)=0，发送到站点S2，如下图：,利用hash函数处理后数据分布变化（R1）：这样A（F11）和A（F21）没有公共值，前者都是奇数，后者为偶数。因此F11 F21=，即R1和R2在新组建的片断下在属性A上站点依赖，所以R1R2=（F11 F21）（F21F22）,s1,s2,s1,s2,s2,s1,考虑R1，R2，R3的连接，假定这些关系在两个站点上，有两种情况：R1A R2 A R3使用上面的hash函数，就可以使得新分片在属性A上满足站点依赖。R1A R2 B R3 R1 中的属性A的值是奇数-S1 R3 中的属性B的值是奇数-S1 问题：R2中的某些元组在A上有奇数值，在B上有偶数值，这些元组中的每个元组被映射到不同的站点。,一种解决的方法：允许这些元组在两个站点中重复出现。如下：另一种：每次执行一个连接。（效率？）,3.6.5 不同方法的比较,假定两个同等大小的关系R1 和R2，并认为每一个片断同等大小，记为R/2,其中R是每个关系的大小。（1）、站点依赖算法特性 A无数据传递 B可利用索引信息做本地连接 C每个站点的连接数据量总是R,因为每一个是R/2，每个站点有两个片断。,（2）、片断和复制算法的特性如下：A数据传送总量是R,因为要复制的关系的所有分片都要传送到其他的站点 B数据传送后，过去的索引可能要重建或不能使用 C每个站点的连接数据量是（3/2）R，因为每个站点包含一个全关系和一个片断。,（3）、Hash划分算法的特性（假定在连接属性下数据是均匀分布的）如下：A数据传送总量是R,因为每一个站点的一半都要传送到别的站点。B在使用索引方面，Hash算法比片断复制算法的效率更低，因为数据传送后，两个关系的索引可能都不能用了 C每个站点的连接数据量同站点依赖算法。,3.7 直接连接操作的常用策略,1、两个关系在同一个站点（1）、嵌套循环法 对外层的关系R每一元组扫描内层关系S,查找符合条件的结果。（2）、排序扫描法 把两个关系按照连接属性排序，根据属性值的顺序扫描这两个关系，使得匹配的元组成为结果的一部分,增加了排序的代价。,2、两个关系在不同的站点 除了考虑局部代价外，还需要考虑传输代价。影响传输代价有两个因素：选择不同的传输方式和站点进行连接。（1）、有两种传输方式 1）整体传输：如连接RS，称R为外层，称S为内层。A如果传输S，则保存S（因为它将被多次扫描，但传输量少）；B如果传输R，则S可直接使用一次来到的R元组，不保存R（传输量大）,2）、按需传输：只传输所需连接的元组，一次一个元组，无需临时存储器。因为每次提取都要求交换一次信息，所以传输代价高，只有在高速局部网络中才是合理的。（2）、三种选择连接站点的方法：1）、在R所在的站点 2）、在S所在的站点 3）、在第三站点,3.7.2 利用并行性的直接连接操作策略,有效的操作间并行分类：流水线并行：查询表达式中，一个操作A的输出元组作为第二个操作B的输入，在第一个操作尚未产生全部输出元组集合之前，第二个操作就可以在它的输入上进行工作了。独立的并行：查询表达式中，那些相互之间没有依赖关系的操作可以并行的执行。,例子：R1 R2 R3R4假定Ri存储在Si上，连接结果必须在S1上给出 两种并行的结合：R1-S2上并在S2上计算R1 R2-S1上 R3-S4上并在S4上计算R3 R4-S1上 计算最后连接操作因此，站点S1上 最终连接结果的计算可以同S2上 R1 R2 的计算及S4上R3 R4计算并行进行。,3.8总结3.1 分布式查询优化概述3.2 分布式查询优化中的基础知识3.3 分布式查询的分类和层次结构3.4 基于关系代数等价变换的查询优化处理3.5 基于半连接算法的查询优化处理3.6 基于直接连接算法的查询优化处理3.7 直接连接操作的常用策略3.8 小结,谢谢！,