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

《第3章+分布式数据库中的查询处理和优化课件.ppt》由会员分享，可在线阅读，更多相关《第3章+分布式数据库中的查询处理和优化课件.ppt（92页珍藏版）》请在三一办公上搜索。

1、分布式查询优化概述分布式查询优化基础知识分布式查询分类和层次结构基于关系代数等价变换的查询优化处理基于半连接算法的查询优化处理基于直接连接算法的查询优化处理直接连接操作的常用策略,分布式数据库中的查询处理和优化,第3章,查询处理问题,集中式查询转换为代数表达式从所有等价表达式中选择最优的代数表达式分布式除了集中式问题外，还有站点之间交换数据的操作选择最优的执行站点(分布）数据被传送的方式,目标,总代价最小,响应时间最短,集中式,分布式,CPU代价（相对固定）,I/O代价（优化的目标）,CPU代价,I/O代价（访问磁盘）,通讯代价,数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处

2、理的响应时间,主要标准辅助标准,准则：使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。通讯费用与所传输的数据量和通信次数有关响应时间和通信时间有关，也与局部处理时间有关查询代价分析远程通讯网络 局部处理时间可以忽略不计，减少通讯代价是主要目标高速局域网 传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理时间是关键,例子 S(s#,sname,age,sex)104 元组 Site A C(c#,cname,teacher)105 元组 Site B SC(s#,c#,grade)106 元组 Site A 每个元组长度100bit,通讯传输速度

3、 104 bit/sec,通讯延迟 1sec,查询:所有选修maths 课的男生学号和姓名.SELECT s#,sname FROM S,C,SC WHERE S.s#=SC.s#AND C.c#=SC.c#AND sex=男 AND cname=maths;,代价公式 QC=I/O 代价+CPU 代价+通讯代价 通讯代价 TC=传输延迟时间C0+(传输数据量X/数据传输速率C1)=传输次数*1+传输的bit数*104。,六种查询策略,六种查询策略,相关表述记号,设关系模式为R(A1,A2,An)。它的一个关系设为R。tR表示t是R的一个元组。tAi则表示元组t中相应于属性Ai的一个分量。,若

4、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中 的象集（Images Set）为：Zx=tZ|tR,tX=x 它表示R中属性组X上值为x的诸元组在Z上分量的集合。,传统的集合运算,并运算,设关系R和关系S具有相同的目n（即两个关系都有n个属性），且相应的属性取自同一个域，则关系R与关系S的并由属于

5、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),选择运算是从关系中选取使公

6、式为真的元组。这是从行的角度进行的运算。,在关系R中选择满足给定条件的元组，记做：F(R)=t|t R F(t)=真 F是一个公式，表示形式为由逻辑运算符（,)连接各算术表达式组成。算术表达式的基本形式为：XY.=,=,。,例1 求计算机科学系CS的学生,SD=CS(S),SD=CS(S),选择运算,在关系R中选择满足给定条件的元组，记做：F(R)=t|t R F(t)=真,例2 求计算机科学系CS，年龄不超过21岁的学生。,SD=CS SA21(S),选择运算,投影运算,这是从列的角度进行的运算。,例3 SN,SD(S)即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。,SN,SD(

7、S),关系R上的投影是从R中选择若干属性列组成新的关系。记做：A(R)=tA|t R投影之后不仅取消了某些列，还可能取消某些元组。,连接运算（连接）,S,R,R S,CE,等值连接,例5 设关系R、S如下图：,12,b4,a2,8,b3,a2,6,b2,a1,5,b1,a1,C,B,A,R,连接运算中有两种最为重要也最为常用的连接，,为“”的连接运算称为等值连接:,自然连接,另一种是自然连接。自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。,半连接,在R、S自然连接后仅保留对R的属性的投影，记为：R S,例7 关系R、S的半连接：

8、,R,左外连接:对R中任意元组，若S中找不到匹配的元组，则S用空元组与之对应。R的信息在左外连接的结果中都得到保留。,左外连接,在R、S自然连接时对不匹配的元组用空值来匹配。有左外连接、右外连接和全外连接之分,例8 关系EMP、SAL的左外连结：,右外连结:对S中任意元组，若R中找不到匹配的元组，则R用空元组与之对应。S的信息在右外连接的结果中都得到保留。,右外连接,例9 关系EMP、SAL的右外连结：,全外连接:对R或S中所有不匹配的元组，均用空元组分别匹配。R、S的信息在全外连接的结果中都得到保留。,全外连接,例10 关系EMP、SAL的全外连结：,除运算,给定关系R(X,Y)和S(Y,Z

9、)，其中X,Y,Z为属性组。R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。R与S的除运算得到一个新的关系P(X)，P是R中满足下列条件的元组在X属性列上的投影：元组在X上分量值x的象集Yx包含S在Y上投影的集合。记作：RS=tX|tR Yx Y(S)其中Yx为x在R中的象集，x=tX。,Z,X,除运算,S在B、C上的投影,（b1,c2），（b2,c3），（b2,c1）,RS=tX|tR Yx Y(S),RS a1,关系代数表达式,设教学数据库中有三个关系：学生关系S（S#，SNAME，SD，AGE）课程关系C（C#，CN,CP#）学习关系SC（S#，C#，GRADE）,例1 检索

10、学习课程号为C2的学生学号与成绩,S#,GRADE(C#=C2(SC),C#=C2(SC),例2 检索学习课程号为C2的学生学号和姓名,S#,SNAME(S C#=C2 SC),S#,SNAME(C#=C2(S SC),例3 求选修数据库原理这门课程的学生名和所在系。,（S、C、SC）,例4 检索学习课程号为C2或C3的学生学号和所在系,SN,SD(CN=数据库原理(C),S SC,S#,SD(s S#(C#=C2C#=C3(SC),例5 求至少选修C2和C3这两门课程的学生名。,SN(S(S#,C#(SC)K),SN(S(S#,C#(SC)C#(C#=C2C#=C3(C),K C#(S#=S

11、2(SC),（S、C、SC）,例7 求选修全部课程的学生名。,例8 求至少选修了学生编号为S2 所选课程的学生名。,S#(SC)S#(C#=C2(SC),例6 求不学C2这门课程的学生名。,S#(S)S#(C#=C2(SC),SN(S(C#,S#(SC)C),SN(S(C#,S#(SC)C#(S#=S2(SC),SQL与代数的等价描述E1SELECT sname FROM S,SC WHERE S.s#=SC.s#and SC.c#=c03;代数描述 sname(s.s#=SC.s#and SC.c#=c03(SSC),关系代数基本操作：并（）、交（）、笛卡尔积（）、选择（）、投影（）关系代数

12、导出操作：差（）、除（）、连接（）、自然连接（）、半连接（）,E2SELECT sname FROM S WHERE S.s#in(SELECT SC.s#FROM SC WHER c#=c03);代数描述 sname(s.s#=SC.s#(S SC.c#=c03 SC)E3SELECT sname FROM S,(SELECT SC.s#FROM SC WHER c#=c03)SCC WHERE S.s#=SCC.s#;代数描述 sname(S SC.c#=c03 SC),节点表示一个一元或二元操作符,叶子表示已知关系,树根表示查询结果,一元操作：只涉及一个操作对象(SL),(PJ)二元操作

13、：涉及两个操作对象(UN),（）,(DF),(CP),（），(JN),(SJ),等价变换规则,空值的变换 R=R R=R=R=-R=R-=R R=R=()=()=自身操作的等价R R=R R R=R R R=R一元操作F1(F2(R)=F1and F2(R)(R)=(R)A1,An(B1,Bm(R)=A1,An(R),有条件:A必须是B的属性,交换律1(2(R)=2(1(R)条件:1 2 是 选择操作 时总成立1 2 是 投影操作时要求其属性集合相等1 与 2 是投影和选择操作时:A1,An(F(R)=F(A1,An(R)的条件是 F中的属性是 A1,.An 的子集R S=S R R S=S

14、RR S=S R R S=S RR S S R R-S S-R,结合律 R B(S B T)=(R B S)B T)B:二元操作（JN）,（CP）,（UN）,等总成立（SJ）有问题,分配率U(R B S)=U(R)B U(S)U:一元操作 F(R S)其中F=F1 and F2,若F1有R属性,F2有S属性,则 F(RS)=F1(R)F2(S)若F1只有R属性,F2有R与S属性,则 F(R S)=F2(F1(R)S)F(R S)=F(R)F(S)F(R-S)=F(R)-F(S)F(R S)=F(R)F(S),B1,Bm,C1,Ck(R S)=B1,Bm(R)C1,Ck(S)B1,Bm 是R属性

15、,C1,Ck是S属性 B1,Bm,C1,Ck(R S)=B1,Bm(R)C1,Ck(S)B1,Bm,C1,Ck(R-S)=B1,Bm(R)-C1,Ck(S)B1,Bm,C1,Ck(R S)=B1,Bm(R)C1,Ck(S)PJB1,Bm(R S)=B1,Bm(B1,Bm,C1,Ck(R)C1,Ck(S),局部查询：只涉及本地.单个站点的数据,优化同集中式选择和投影早做，中间结果大大减少连接前进行预处理（属性排序、属性索引）同时执行一串投影和选择操作远程查询：也只涉及单个站点的数据,但还要远程通讯,选择站点选择查询应用最近的冗余分配站点全局查询：涉及多个站点数据,优化复杂,全局查询具体化对查询进

16、行分解，确定查询使用的物理副本，落实查询对象非冗余具体化，所有要访问对象只有一个副本冗余具体化，多个副本，研究如何选择副本，使通信代价最小确定操作执行的顺序确定二元操作连接和并操作的顺序先执行所有连接操作，再执行并操作先执行部分并操作，再执行连接操作选择和投影尽可能早进行确定操作执行的方法把若干个操作连接起来在一次数据库访问中连接方法在查询优化中起着重要作用确定执行的站点执行站点不一定是发出查询的站点考虑通讯费用和执行效率,查询分解,数据本地化,全局优化,局部优化,分布关系上的查询表达,分布关系上的代数表达,分段关系查询表达,带有通讯操作的段查询优化,优化的局部查询表达,全局模式,段模式,段的

17、统计数据,局部模式,控制站点,本地站点,分布查询的层次,查询分解将查询问题（SQL）转换成一个定义在全局关系上的关系代数表达式需要从全局概念模式中获得转换所需要的信息数据本地化具体化全局关系上的查询，落实到合适的片段上的查询即将全局关系上的关系代数表达式变换为相应片段上的关系代数表达式全局优化输入的是分片查询，优化目标是寻找一个近于最优的执行策略（操作次序）输出是一个优化的、片段上的关系代数查询局部优化输入是局部模式它由该站点上的DBMS进行优化,基本原理查询问题关系代数表达式分析得到查询树进行全局到片段的变换得到基于片段的查询树利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作优

18、化算法连接和合并尽可能上提（树根方向）选择和投影操作尽可能下移（叶子方向）,实现步骤和方法转换一：查询问题关系代数表达式转换二：关系代数表达式查询树转换三：全局查询树分拆成片段查询树优化：利用关系代数等价变换规则的优化算法，优化查询树，进而优化查询,全局关系S(S#,SNAME,AGE,SEX)和SC(S#,C#,GRADE)被水平分片,查询问题：查找至少有一门功课成绩在90分以上的男生姓名SNAME(SEX=M and GRADE90(S.S#=SC.C#(SSC),水平分片的查询优化的基本思想：尽量把选择条件下移到分片的限定关系处再把分片的限定关系与选择条件进行比较去掉它们之间存在矛盾的相

19、应片断如果最后剩下一个水平片断，则重构全局关系的操作中，就可去掉“并”操作（至少可以减少“并”操作的次数）,全局关系EMP(EMP#,ENAME,SALARY,DEPT#,DNAME)垂直分片：E1(EMP#,DEPT#,DNAME)EMP2(EMP#,ENAME,SALARY),查询问题：雇员的姓名和工资情况ENAME,SALARY(EMP),垂直分片的查询优化的基本思想：把垂直分片所用到的属性集，与查询条件中的投影操作所涉及的属性相比较，去掉无关的垂直片断如果最后只剩下一个垂直片断与查询有关时，去掉重构全局关系的“连接”操作（至少可以减少“连接”操作的次数）,假定有两个关系R,S,在属性R

20、.A=S.B上做半连接操作，可表示为：RA=B S=R(R A=B S)=R A=B(B(S)SA=B R=S(S A=B R)=S A=B(A(R)用半连接表示连接操作RA=BS=(RA=B S)A=BS=（R A=B(B(S)A=BSRA=BS=(SA=B R)A=BR=(S A=B(A(R)A=BR,例子1:R S,AB,A(R)=2,10,25,30,R S,SR=,A C10 y25 w,A=A,A=A,A C,S,R,AB,例子2：半连接简化,R,S,T,R,S,T,B=B,C=C,A=A,R,S,T的循环连接图,对R的充分简化,R=R T,S=S R,T=T S,减少一个元组,R

21、=R T,S=S R,T=T S,减两个元组,R=R T=减少三个元组,一般：简化程序长度随着关系的元组数目增长线性增长。对R的另一个简化程序：R=R S T=T R S=S T（练习）,R,S,网络,站点1 站点2,(1)B(S),(3)R=RA=BB(S)(2)B(S)(4)R=RA=B B(S)(5)RA=BS,RA=BS=(RA=B S)A=BS=（R A=B(B(S)A=BS,关系的概貌Card(R)片段关系R的元组数目Size(A)属性A的大小(即字节数)Size(R)片段关系的大小,属性大小之和Val(AR)属性A在R中出现的不同值的个数,代数操作对关系概貌的影响选择操作 S=F

22、（R）Card(S)=*Card(R)Size(S)=Size(R)Val(BS)是Val(BR),Card(S),Card(R)的函数并操作 T=RS Card(T)Card(R)+Card(S)Size(T)=Size(R)=Size(S)Val(AT)Val(AR)+Val(AS),代价公式：T=C0+C1*X在站点2上做投影B(S)把B(S)传到站点1上，代价为：C0+C1*size(B)*val(BS)在站点1上计算半连接，R=R A=B S把R从站点1传到站点2的代价为：C0+C1*size(R)*card(R)在站点2上执行连接操作：R A=BS采用半连接的总代价T半R=2C0+

23、C1*(size(R)*card(R)+size(B)*val(BS)T半S=2C0+C1*(size(S)*card(S)+size(A)*val(AR)比较T半R 与T半S,取最优者,基本原理通常有两次传输但是传输的数据量和传输整个关系相比，要远远少一般有：T半card（R），可减少站点间的数据传输量半连接的损失：传输B(S)=C0+C1*size(B)*val(BS)基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价采用半连接优化算法的步骤计算每种半连接方案的代价，并从中选择一种最佳方案选择传输代价最小的站点，计算采用全连接的方案的代价比较

24、两种方案，确定最优方案,半连接算法和直接连接算法区别取决于数据传输和局部处理的相对费用如果传输费用是主要的，采用半连接，SDD-1如果本地费用是主要的，采用直接连接,System R*四种基于直接连接的优化算法（考虑关系分段）利用站点依赖信息的算法分片与复制算法站点依赖和数据复制结合算法Hash划分算法,R1 R2,站点依赖设关系Ri分片Fi1和Fi2,Rj分片Fj1和Fj2关系Ri和Rj在属性A上满足条件 Fis A Fjt=,其中s t,则称Ri和Rj在属性A上站点依赖也就是说:Ri A Rj=U(Fis A Fjs),对于包含着两个关系的片段的每个站点s都成立此时关系的连接操作无站点间数

25、据传输,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上站点依赖，则（Ri ARj B Rk）=（Fis A Fjs B Fks)查询Ri A Rj B Rk的连接操作能够以无数据传输的方式处理。,算法描述Placement_Dependency(Q,P,S)，其中：R=R1,R2,R3,Rn是查询Q引用的一组关系P是站点依赖信息S

26、是一个连接操作可以无数据传输的执行的最大关系集合开始时S是空集。算法结束时，若S=R,则Q可以无数据传输执行算法步骤初始化S=，R=R1,R2,R3,Rn若能找到一对关系Ri和Rj在属性A上站点依赖，且Ri CRj 包含在Q中，其中C包含A,那么把Ri和Rj放到S中，否则算法终止，返回空集S。只要存在R中而不在S中的关系Rk满足下面的特性，就把其放入S中：有S中的关系比如Rj，与Rk在属性B上有站点依赖关系，且Rj BRk在Q中或者可以由Q导出，根据推论3，则Rk可被包含在S中。,查询引用的某个关系的所有片段分布在这些站点上,其余被引用的关系复制到每一个选定的站点 R1 R2=Ui(F1i R

27、2)算法可应用到涉及两个或两个以上的关系的查询其中一个关系保持分片状态其他关系可先连接起来，再被复制到各个站点在各个站点上，其他关系副本与相应的第一个关系的片断连接,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,

28、R1),MaxFT(Q,S1,R2),FT(Q,S2,R2)，找出响应时间小的保持分片关系算法忽略了把结果传送到要求答案的用户站点的代价，和将部分结果组装成最终结果的代价，认为它们不大重要，或者采用其他算法时这些部分没有太大差别。,Fragmentation_and_replicate(Q,R,S)For 每个保持分片状态的关系Ri For 每个包含关系Ri的一个片段的站点Sj 计算在站点Sj执行子查询的完成时间 FT(Q,Sj,Ri)计算关系Ri保持分片状态下的响应时间 Ti=maxj(FT(Q,Sj,Ri)选择Rk=mini(Ti)为保持分片状态的关系,R1,R2,R2,R2,F11,F1

29、3,F21,F22,本地连接,Result,fpartition,union,R1,R2,F12,举例 已知R1分段F11和F12的大小为:|F11|=|F12|=50 R2分段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)=245

30、0 因此,查询响应时间在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上站点依赖,查询R1 A R2 B R3,设R1和R2在属性A上站点依赖,查询R1 R2 R3第一个连接因为站点依赖，无传输处理第二

31、个连接因为存在R3的副本,也没有传输处理保证查询无传输的方法是R1和R2连接执行后，形成一个关系R4，它有两个片断：一个由F11 F21给出一个由F12 F22给出最后由R4和R3的副本连接得到最后的结果,连接依赖定义：如果Ri 和Rj 在属性A上站点依赖或者关系Ri复制在关系Rj各片断的站点上或者关系Rj复制在关系 Ri各片断的站点上有了此定义，站点依赖算法可理解为：利用站点依赖和复制信息来确定一个查询中的连接能否无数据传送处理。,利用Hash函数对分片关系上的连接属性作站点依赖计算,再据此分片,以获取站点依赖的连接算法例如,运用Hash函数 1 若a 是奇数 0 若a 是偶数 对R中每个元

32、组,h(a)为1送入站点S1,h(a)为0送入站点S2.于是片段关系R被划分为Ro和ReR1 R2=(R1o R2o)U(R1e R2e),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)没有公共值,前面是奇数值后面是偶数值F12 F11是空集，这说明R1和R2在新组成的片断下在属性A上站点依

33、赖。R1 R2=（F11 F21）U（F12 F22）,h(a),=,考察三个关系R1，R2和R3,它们在两个站点上，有两种情况：在同一属性A上连接，R1A R2 AR3在三个关系的片断上应用Hash函数使用新组建的片断，三个关系在属性A上将满足站点依赖经这种划分和数据传送之后，两个站点上的片断在属性A上的连接就可以并行进行，合并执行结果给出答案在不同属性上连接，R1A R2 BR3,在不同属性上连接，R1A R2 BR3在属性A上应用同样的Hash函数，在属性B上也应用同样的Hash函数，可能得不到希望的站点依赖因R1中属性A的值是奇数的发往S1，R3中属性B是奇数的元组发往S1.但R2中某

34、些元组可能在A上有奇数值，而在B上有偶数值解决方法是允许这些元组在两个站点上都存在。,R1 A R2 B R3 若R1与R2在A上有相同的Hash函数,R2与R3在属性B上有相同的Hash函数,站点依赖算法无数据传递可利用索引做本地连接每个站点连接数据总量是R，两个片段分片和复制算法数据传输总量是R数据传送后,可能要重新创建索引每个站点的连接数据量是(3/2)R,一个全关系和一个片断Hash划分算法数据传送量是R索引方面,比片段复制算法效率更低（因为数据传送后，两个关系的索引可能都不能使用了）每个站点的连接数据量同站点依赖,假定每个片段的大小是R大小的一半R/2,两个关系在同一个站点，RS，称

35、外层关系为R,内层关系为S嵌套循环法顺序扫描外层关系R，对于R的每一元组扫描内层关系S查找在连接属性上一致的元组，组合起来构成结果的一部分需要扫描一次关系R和Card（R）次关系S排序扫描法先把两个关系按照连接属性进行排序然后按照连接属性值的顺序扫描这两个关系，使匹配的元组成为结果的一部分对两个关系都扫描一次，但增加了排序代价,两个关系在不同站点，关系R和关系S两种传输方式整体传输如果传输S,则保存S（被多次扫描，传输量少）如果传输R，则S可直接使用一次来到的R元组，不保存R(但传输量大）按需传输只传输需要连接的元组，一次一个元组，无需临时存储器每次提取都要交换一次信息，传输代价高，只在高速局

36、域网中才是合理的三种选择连接站点的方法R站点S站点其他站点,一个操作内的并行一般是不可行的多个操作间的并行是可行的流水线并行在查询表达式中，一个操作A的输出元组作为第二个操作B的输入在第一个操作尚未产生全部的输出元组集合之前，第二个操作就可以在它的输入上进行工作可以在不同的站点上运行A和B，在A产生部分结果元组的同时，B来使用它们独立的并行查询表达式中，那些相互之间没有依赖关系的操作可以并行地执行,例子：R1 R2 R3 R4有很多策略，其中一个是两种并行方法结合使用：把R1送到S2并在S2上计算R1 R2，同时把R3送到S4上计算R3 R4 在站点S2上计算R1 R2的过程中，就可以把已经计算出来的元组送到站点S1，而不必等到整个连接计算完成同样，在站点S4上计算R3 R4的过程中，就可以把已经计算出来的元组送到站点S1，而不必等到整个连接计算完成。一旦（R1 R2）和（R3 R4）的元组到达站点S1,在S1上就可以开始计算（R1 R2）（R3 R4）。也就是说，站点S1上最终连接的结果的计算可以同S2上R1 R2 的计算以及S4上的R3 R4计算并行地进行。,总 结,分布式查询优化概述（目标、准则和代价估算）基础知识关系代数回顾等价变换规则分布式查询分类和层次结构基于关系代数等价变换的查询优化基于半连接算法的查询优化处理基于直接连接算法的查询优化处理（四类算法）,