大连理工大学算法分析与设计2014 4章_分布式数据库中的查询处理和优化2014-12-18.ppt

1、1,徐喜荣 （),分布式数据库系统及其应用,2,分布式查询优化概述 分布式查询优化基础知识 分布式查询分类和层次结构 基于关系代数等价变换的查询优化处理 基于半连接算法的查询优化处理 基于直接连接算法的查询优化处理 直接连接操作的常用策略,分布式数据库中的查询处理和优化,第4章,3,查询优化在关系数据库系统中有着非常重要的地位； 查询优化是影响RDBMS 性能的关键因素； 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供执行查询优化的可能性。,4,集中式数据库系统查询优化目标 通过某种代价模型为每一个用户查询计算出各种查询执行策略的 代价，然后选取总代价最小的执行方

2、案。 总代价是以查询处理期间 CPU代价和I/O 代价来衡量。即尽可能降低 I/O 代价，使查询的响应时间最短。 将查询转换为关系代数表达式，从所有等价关系代数表达式中选择最优的代数表达式。 查询优化按照优化的层次分类 ： 代数优化：指关系代数表达式的优化，即按照一定的规则，改变 代数表达式中操作的次序和组合，使查询执行更高效； 物理优化：指存取路径和底层操作算法的选择；,5,分布式数据库系统查询优化目标：两种目标 一种目标是以总代价最小为标准，除考虑CPU代价和I/O代价之外，总代价还包括通过网络在站点之间传输数据或信息的代价，即通信代价。 另一种目标是以每个查询的响应时间最短为标准。因为分

3、布式 数据库系统的数据分布和冗余增加了查询的并行处理的可能性， 可以缩减查询处理的响应时间，加快查询处理速度。 在分布式查询优化中，常同时使用这两种标准，根据系统应用的 不同，一种作为主要标准，另一种作为辅助标准。 可以先找到一个总代价最小的执行方案，然后在总代价不增加的条件下修正方案使得响应时间也尽可能的短。,6,分 布 式 查询优化目 标,总代价最小,响应时间最短,集中式,分布式,CPU代价（相对固定）,I/O代价（可变的，优化的目标）,CPU代价,I/O代价（访问磁盘）,通信代价,数据的分布和冗余增加了查询的并行处理的可能性，可以缩减查询处理的响应时间,主要标准 辅助标准,7,通信费用最

4、低和响应时间最短，即以最小的总代价在 最短响应时间内获得需要的数据。 响应时间和通信时间有关，也与局部处理时间有关。 响应时间是指从接收查询到完成查询所需时间。 通信费用与所传输数据量和通信次数有关，也与分布式数据库系统所基于的通信网络的类型有关。 对不同的通信网络类型有不同的查询处理优化算法。,一、分布式查询优化的准则,8,在远程通讯网络中 局部处理时间可以忽略不计，减少通信费用成为分布式查询优化的主要目标。 通信费用与所传输的数据量成正比。 因此在基于远程通信网的分布式数据库系统的查询处理中常以减少传输的次数和数据量作为优化的重要目标。,二、分布式查询代价分析,9,在高速局域网中 传输时间

5、比局部处理时间要短很多，以响应时间作为 优化目标。 响应时间既与通信时间有关，也与局部处理时间有关，但局部处理时间是关键。 故减少局部处理的时间是问题的主要方面。,二、分布式查询代价分析,10,其它情况 在某些情况下，查询处理同时以减少通信费用与响应 时间作为优化目标。 为减少局部处理时间，除了要考虑CPU和I/O时间外， 在分布式查询中还要考虑如何进行并行查询处理的时间，以便估算各种查询策略的代价。可以使用数据库的统计模型来估算。,二、分布式查询代价分析,11,三、查询代价的估算方法 设一个查询执行的预期代价为QC, 则 在集中式数据库中： QC=I/O代价+CPU代价 在分布式数据库中：

6、QC=I/O代价+CPU代价+通信代价,12,通信代价可用如下公式作粗略估算： TC(X) = C0 + C1 * X= C0 + X/V 其中： X：为传输数据量，通常以bit为单位计算； C0：为两站点通信初始化一次所花费的时间， 它由通信系统确定，近似一个常数， 以秒为单位； C1：为传输率 (传输速度V的倒数)单位为s/b ， 即单位数据传输的时间。,13,在分布式数据库系统中，查询优化包括两个内容： 查询策略优化 局部处理优化 查询策略优化尤为重要。,14,例4.1 在教学数据库中，有 S( s#, sname, age, sex) 104 元组 存放在Site A C( c#, c

7、name, teacher) 105 元组 存放在Site B SC( s#, c#, grade) 106 元组 存放在Site A 假定：若每个元组长度100Bit, 通讯传输速度V为 104 bit/sec, 通讯延迟时间C0为1sec。 问题：要求查出所有选修MATHS课的男学生的学号和姓名。,15,解: 在分片透明性的DDBMS支持下，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+(传输的数

8、据量X/数据传输速度V) = (传输次数*1) + (传输的bit数/104) 为了实现这一查询，可以有六种可能的查询策略。,16,17,18,不同查询策略结果的比较,19,相关表述记号, 设关系模式为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 中去掉

9、 Ai1, Ai2, , Aik 后剩余的属性组。,20,相关表述记号, 给定一个关系R(X,Z)，X和Z为属性组。我们定义，当tX=x时，x在R中 的象集（Images Set）为： Zx= tZ | tR , tX=x 它表示R中属性组X上值为x的诸元组在Z上分量的集合。,21,传统的集合运算,并运算,设关系R和关系S具有相同的目n（即两个关系都有n个属性），且相应 的属性取自同一个域，则关系R与关系S的并由属于R或属于S的元组组成。 其结果关系仍为n目关系。记作：RS= t | tRtS ,22,差运算,设关系R和关系S具有相同的目n，且相应的属性取自同一个域，则关系R与关系S的差由属于

10、R而不属于S的所有元组组成。其结果关系仍为n目关系。记作：RS=t|tRt S,传统的集合运算,23,交运算,R1R2,设关系R和关系S具有相同的目n，且相应的属性取自同一个域， 则关系R与关系S的交由既属于R又属于S的元组组成。其结果关系仍 为n目关系。记作： RS=t|tRtS,传统的集合运算,24,两个分别为n目和m目的关系R和S的广义笛卡尔积是一个(n+m)列的元组 的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。若 R有k1个元组，S有k2个元组，则R和S的广义笛卡尔积有k1k2个元组。记作：,广义笛卡尔积,25,专门的关系运算,S ( S#, SN, SD, SA

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

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

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

14、：,36,关系代数表达式,设教学数据库中有三个关系： 学生关系S（S#，SNAME，SD， AGE ） 课程关系C（C#，CN, CP#） 学习关系SC（S#，C#，GRADE）,例1 检索学习课程号为C2的学生学号与成绩,S# ,GRADE( C# =C2 (SC), C# =C2 (SC),37,例2 检索学习课程号为C2的学生学号和姓名,S# ,SNAME(S C# =C2 SC),S# ,SNAME( C# =C2 ( S SC ),38,例3 求选修数据库原理这门课程的学生名和所在系。,（ S、C、SC ）,例4 检索学习课程号为C2或C3的学生学号和所在系,SN ,SD( (CN=

15、数据库原理(C) ),S SC ,S# ,SD( s S# (C# =C2C#=C3(SC) ),39,例3.2 在教学数据库中，有三个全局关系： 学生信息表： S( S#, SNAME, AGE, SEX ) 课程设置关系： C( C#, CNAME, TEACHER ) 选课关系： SC( S#, C#, GRADE ) 查询选修课程号C#为“C03”的学生姓名。,40,关系代数表达式E1 SQL语句1: SELECT SNAME FROM S, SC WHERE S.s#=SC.s# and SC.c#=c03; 关系代数表达式描述： sname(S.s#=SC.s# and SC.c#

16、=c03(SSC),SQL语句与关系代数表达式的等价描述,41,关系代数表达式E2 SELECT SNAME FROM S WHERE S.s# in ( SELECT SC.s# FROM SC WHERE c#=c03); 关系代数表达式描述： sname( s.s#=SC.s# (S SC.c#=c03SC) ),SQL语句与关系代数表达式的等价描述,42,关系代数表达式E3 SQL语句 SELECT SNAME FROM S , ( SELECT SC.s# FROM SC WHERE c#=c03) SCC WHERE S.s# = SCC.s# ; 关系代数表达式描述： sname

17、( S SC.c#=c03SC ),SQL语句与关系代数表达式的等价描述,43,对一个关系代数表达式表示的查询，进行语法分析， 可以得到一棵语法树。 树的叶子是已知的关系，树的各个节点是关系代数 操作符，树的根是查询结果，所以也称操作符树。 用语法树描述一个查询要求，更加清晰、更加直观， 且易于分析和调整查询问题的具体操作次序。 因此，语法树又称查询树。,44,中间节点表示一个一元或二元操作符,叶子表示已知关系,树根表示查询结果,sname(S.s#=SC.s# and SC.c#=c03(SSC),sname( s.s#=SC.s# (S SC.c#=c03SC) ),sname( S SC

18、.c#=c03SC ),45,所谓两个关系代数表达式E1和E2等价是指： 用相同的关系代替两个表达式中相应的关系时，所得 到的结果一样的。称此两个关系代数表达式E1和E2等价， 记作： E1E2.,一、关系代数表达式的等价,46,二、 一元操作和二元操作 一元操作：涉及一个操作对象的操作。 关系代数操作中一元操作符有： 选择 (SL) 和 投影 (PJ)。 二元操作：涉及两个操作对象的操作。 关系代数操作中二元操作符有： 并， 交， 差，除，笛卡尔积 , 连接， 连接, 半连接。,47,一元操作等幂律 (R) = (R) (为一元操作符) (1) 选择的串接： F1 (F2(R) = F1 F

19、2(R) (2)投影的串接： A1,An(B1,Bm(R) = A1,An (R) 自身操作的等价变换规则 R R = R R R = R R R = R,要求：A1,An必须是B1,Bn中的属性,48,一元操作交换律： U 1 (U 2 (R) = U 2 (U 1 (R)，U 1 ，U 2是一元操作。 (1) U 1 与 U 2 是选择操作时总成立； (2) U 1 与 U 2 是投影操作时要求其属性集合相等； (3) U 1 与 U 2 是投影和选择操作时： A1,An( F(R) = F ( A1,An (R) 其中 F中的属性是 A1, . An 的子集。,49,二元操作交换律： R

20、 S = S R R S = S R R S = S R R S = S R R S S R R - S S - R,50,二元操作结合律 R B ( S B T ) = ( R B S ) B T B是二元操作。 对于二元操作： （JN）, （CP）, （UN）, 结合律总成立； 但是半连接（SJ）有问题。,51,对于选择操作 满足的分配律如下： （1）若F1有R属性, F2有S属性, F = F1 F2则 F(R S) = F1 (R) F2 (S) 若F1只有R属性, F2有R与S属性, 则 F(R S) = F2 ( F1 (R) S) （2） F(R S) = F(R) F (S)

21、（3） F(R - S ) = F(R) - F (S) （4） F(R S ) = F(R) F (S),52,对于投影操作 满足的分配律如下： （1） B1,Bm,C1,Ck (R S) = B1,Bm (R) C1,Ck (S) （2） B1,Bm,C1,Ck (R S) = B1,Bm (R) C1,Ck (S) （3） B1,Bm,C1,Ck (R - S) = B1,Bm (R) - C1,Ck (S) （4） B1,Bm,C1,Ck (R S) = B1,Bm (R) C1,Ck (S) （5）B1,Bm (R S) = B1,Bm ( B1,Bm,C1,Ck (R) C1,Ck

22、 (S) 其中B1,Bm 是关系R属性, C1,Ck是关系S属性.,53,局部查询： 指在本站点上执行查询，即查询本站点存放的数据。可以使用集中式查询处理的技术。 远程查询： 指在某个站点上执行查询，即查询在网络上另一个站点上存放的数据。 全局查询： 涉及多个站点数据, 优化复杂。,分布式环境下，查询可分为三种类型：局部查询、远程查询和全局查询。主要讨论远程查询和全局查询处理。这两类查询中，由于涉及远程站点 或多个站点上数据，必须进行站点间数据的传递，需要一定的通信费用。,54,局部查询只涉及本地，单个站点的数据, 所以查询优化技术与集中式 数据库查询所采取的优化技术相同，如分解查询、关系代数

23、表达式的等价变换、基于代价的估算等。 局部查询一般策略有： 选择和投影运算应尽可能先做，可以使中间结果数据大大减少。 在执行连接前对数据库数据进行适当的预处理，如对数据按连接 属性排序和在连接属性上建立索引，以减少扫描次数，提高连接 速度。 同时执行一串投影和选择操作，且尽可能把它们与其前后的二元 操作结合起来，以避免重复扫描关系和减少中间数据。 找出公共子表达式等。,局部查询,55,远程查询只涉及单个站点的数据, 所以它的局部处理的优化策略与本地查询所采取的优化策略相同。 远程查询还涉及远程站点的选择，即选择哪个远程站点上的数据或数据片段作为查询的对象。 为了减少远程查询的通信代价，如果数据

24、是冗余分配，应尽可能选择距发出查询应用的站点最近的站点上的数据或数据片段作为查询的对象。,远程查询,56,全局查询涉及多个站点上的数据，因此查询处理和优化技术 要复杂得多。为执行全局查询并确定一个好的查询策略，需要 做许多判断和计算工作。这些工作大致可归为如下四类： 确定执行查询的物理片段（具体化）； 确定操作的执行顺序； 确定操作的执行方法； 确定执行的站点。,全局查询,57,对查询进行分解，确定查询使用的物理副本，落实查询对象，为该 查询所要访问的每一个数据或数据片段，认定其一个或多个副本。 如果一个查询所要访问的每一个数据或数据片段，都只有一个副本，则称为非冗余具体化，否则称为冗余具体化

25、。 对冗余具体化就要研究如何为每一个数据或数据片段选择它的哪个 副本，才能使通信代价最小，从而使查询代价最小且结果正确。 冗余具体化的目标：通过冗余数据提高处理并行性和减少通信费用。不仅需要考虑副本选择问题，还需研究在冗余具体化情况下，如何 提高处理的并行性等优化查询策略。,确定执行查询物理片段,58,在分布式数据库系统中确定二元操作连接操作和并操作的次序。可供选择的策略通常有两种： 一种是先执行所有连接操作，再执行并操作 另一种是先执行部分并操作，再执行连接操作。 选择哪种策略与其代价有关，先估算各种策略代价， 从中选出代价最小的形成执行方案。 其它操作次序，选择和投影尽可能早执行。,确定操

26、作执行的顺序,59,连接方法在查询优化中起着重要作用，是查询中最费时的操作。 因此连接的执行方法是研究查询优化中操作执行方法的重点。 把若干个操作连接起来在一次数据库访问中，确定可用的访问路径 (如选择索引)，以及确定某种计算方法等。,确定操作执行的方法,60,确定执行的站点 全局查询执行站点不一定是发出查询的站点，全局查询 原则上可以在网络上的任意站点上执行，然后将结果传 送到发出查询的站点。 确定执行站点主要考虑通信代价和执行效率，一般选择 离提供数据的站点较近的站点。 考虑查询速度，尽量选择较空闲的站点执行查询操作。,61,为了找到一个查询的最优策略，就要确定执行查询的物理 片段，也必须

27、确定查询中各操作执行的次序和执行站点， 而这又依赖于每个操作的执行方法。 这四个问题联系不是单向的或线性的，而是相互制约的。 要根据应用统筹考虑。 但无论如何，连接和合并操作是引起远程通信的主要原因，连接操作还是最费时间、空间的操作。 因此连接操作的优化成为分布式查询优化的首要任务。,全局查询,62,分布式查询处理按不同层次结构执行，符合分布式DBMS 的体系结构。分布式查询处理可分为四个层次： 查询分解； 数据本地化； 全局优化； 局部优化。,63,查询分解,数据本地化,全局优化,局部优化,分布式查询问题,全局查询代数表达式,片段关系查询表达,考虑通信代价的片段查询优化,优化的局部查询表达,

28、全局模式,分片模式,片段统计数据,局部模式,控制站点,本地站点,分布查询的层次,64,查询分解 将查询问题（SQL语句）转换成一个定义在全局关系上的关系代数表达式。 本层转换所需要的信息从全局概念模式中获得。,65,数据本地化 把一个在全局关系上的查询具体化，落实到合适的(使尽可能做到本地化或近地化)片段上的查询。即将全局关系的关系代数表达式变换为相应片段上的关系代数表达式。 这一变换所需要的信息在分片模式和片段的分配模式中获得。,66,全局优化 全局优化即是找出分片查询的最佳操作次序，使得代价函数最小。 代价函数一般是I/O、CPU和通信代价之和。 全局优化的一个重要方面是关于连接操作的优化

29、。 输入的是分片查询，查询优化目标是寻找一个近于最优 的执行策略。 全局优化处理层输出是一个优化的、片段上的关系代数查询。,67,局部优化 局部查询优化由拥有与查询有关的片段的各个站点执行。在每个站点上执行的子查询被称为局部查询。 由该站点上的DBMS进行优化，采用集中式数据库系统 中查询优化的算法。 所需信息取自局部模式。,68,基本原理 把查询问题转化为关系代数表达式； 分析得到查询树； 进行全局到片段的变换得到基于片段的查询树； 利用关系代数等价变换规则的优化算法，尽可能先执行 选择和投影操作，后执行连接和合并操作； 对该查询树进行优化，从而达到查询优化的目的。,69,优化算法 连接操作

30、和合并操作尽可能上提（树根方向）； 选择操作和投影操作尽可能下移（叶子方向）； 尽可能先执行选择和投影操作，后执行连接和合并操作。 经过选择和投影操作不但可以减少其后操作量，还可以减少操作次数。,70,实现步骤和方法 将一个查询问题转换成关系代数表达式。 从关系代数表达式到查询树的变换：对一个关系代数表达式进行 语法分析，可以得到一棵语法树 (或查询树)，即查询树根节点是 最终的查询结果，叶子节点是查询涉及的所有关系或片段，中间 节点是按关系代数表达式中的操作顺序组成的一组关系操作符。 从全局查询到片段查询的变换：把基于全局关系的查询树中的全 局关系名，用其重构该全局关系的各个片段名替换，变换

31、成相应 片段上的查询树。 利用关系代数等价变换规则优化算法，对片段的查询树进行优化 处理，最后达到优化查询目的。,71,例3.3 对于教学数据库全局关系 S(S#, SNAME, AGE, SEX)和SC(S#, C#, GRADE)被水平分片。,查询问题：查找至少有一门功课成绩在90分以上的男生姓名。,72,查询问题：查找至少有一门功课成绩在90分以上的男生姓名。 （1）这个查询问题的SQL语句是： Select Distinct sname From S, SC Where S.s#=SC.s# AND sex=M AND grade90,（2）它的关系代数表达式是： SNAME(SEX=

32、M and GRADE90(S.S #=SC.S# (SSC),73,S.S#=SC.S#,SEX=MGRADE90,SNAME,S,SC,(a)全局关系上的查询树,变换,74,75,76,水平分片关系查询优化的基本思想： 1. 尽量把选择条件下移到分片的限定关系处； 2. 再把分片的限定关系与选择条件进行比较； 3. 去掉它们之间存在矛盾的相应片段； 4. 如果最后剩下一个水平片段，则重构全局关系的操作中 就可去掉“并”操作（至少可以减少“并”操作的次数）。,77,例3.4 有全局关系 EMP(EMP#, ENAME, SALARY, DEPT#, DNAME) 如果被垂直分片，分成如下两个

33、片段： E1 ( EMP#, DEPT#, DNAME ) E2 ( EMP#, ENAME, SALARY ),查询问题：雇员的姓名和工资情况。 这个查询的SQL语句： Select ENAME, SALARY From EMP 相应关系代数表达式： ENAME,SALARY(EMP),78,79,垂直分片关系优化的基本思想： 把垂直分片所用到的属性集，与查询条件(查询表达式) 中的投影操作所涉及的属性集相比较，去掉无关的垂直 片段； 如果最后只剩下一个垂直片段与查询有关时，去掉重构 全局关系的“连接”操作（至少可以减少“连接”操作 的次数）。,80,半连接(semi-join)操作是由投影

34、和连接操作导出的一种关系代数操作。 假定有两个关系R和S，在属性 R.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),81,注意：半连接操作不具有对称性，即RSSR。 但半连接操作具有可分配性： ( R1R2)S= (R1S)(R2S) 式中的操作符“”用“” 或“ ”代替时等式亦成立。,82,例1: R S,AB, A (R) = 2,10,25,30,R S,SR =,A C 10 y 25 w,A=A,A=A,A C,S,R,AB,83,例子2：半连

35、接简化,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,减少一个元组,84,R=R T,S=S R,T=T S,减少两个元组,R=R T = 减少三个元组,一般：简化程序长度随着关系的元组数目增长线性增长。 对R的另一个简化程序： R=R S T = T R S = S T （练习）,R=R T,T=T S,S=S R,85,若采用半连接方法表示两个关系R和S在属性R.A=S.B上 做的连接操作，则有： RA=BS = ( R A=B S ) A=B S = ( R A=B B (S) ) A=B S 或 RA=BS

36、= ( S A=B R ) A=B R = ( S A=B A (R) ) A=B R 其中等式右边的括号内称为“半连接”。,86,(1) B(S),(3) R=RA=BS= RA=BB(S) (2) B(S) (4) R=R A=BB(S) (5) RA=BS,当连接操作采用半连接方法表示时，有： RA=BS =(RA=B S)A=B S = (RA=B B(S)A=BS 或 RA=BS =(SA=B R)A=BR = (S A=B A(R)A=BR 采用半连接方法表示连接操作其操作过程如图所示：,87,关系的概貌 Card(R) 片段关系R的元组数目 Size(A) 属性A的大小(即字节数

37、) Size(R) 片段关系R的属性大小之和 Val(AR) 属性A在R中出现的不同值的个数,88,代数操作对关系概貌的影响 选择操作 S= F（R） Card(S)= *Card(R) Size(S)=Size(R)(S属性大小之和) 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),89,代数操作对关系概貌的影响 连接操作： T=RS Card(T) =(Card(R)*Card(S)/Val(AR) Si

38、ze(T) = Size(R)+Size(S) Size(A) Val(AT) Min(Val(AR), Val(BS) A 是连接属性 Val(AT) Val(AR)+Val(BS) A不是连接属性 半连接： T=RS =Val(AS) / Val(Dom(A) A 是连接属性 Card(T) = *Card(R) Size(T) = 第一个操作数Size(R) Val(AT) = *Val(AR),90,传输代价估算公式：T=C0+C1*X (C1为传输率, X传输量) 在站点2上做关系S在R和S公共属性集B上的投影B (S) 把B (S)传到站点1上代价为：C0+C1* X =C0+C1

39、* size (B)* val( BS) 其中：Size(B)为B属性的长度，即B属性所占字节数。 val(BS)为关系S中属性B上不同值个数，与属性B的域取值范围有关。 3. 在站点1上计算半连接，设其结果为R, 则有 R=R A=B S 4. 把R从站点1传到站点2的代价为： C0+C1* X= C0+C1* size (R)* card( R) 其中： size(R)为关系R的属性大小之和, card(R)为R 的元组数。 5. 在站点2上执行连接操作：R A=BS,91,采用半连接的传输总代价为： T半R = 2C0+C1*(size (B)*val(BS) +size (R)*car

40、d( R) 和 T半S = 2C0+C1*(size (A)*val(AR) +size (S)*card( S) 比较T半R 与T半S, 取最优者。,92,基本原理：如果不采用半连接，而是直接把R送到站点2上执行连接操作(假定R的数据量小于S的数据量)的代价为： T全 =C0+C1* size (B)* card(R) 虽然半连接操作不具有对称性，各个半连接方案的代价不同，但其中总 有一个方案是最优的，选作采用半连接的代价，记为T半。 由采用半连接方法表示连接操作的操作过程可知： 采用半连接实现连接操作需要两次传输：连接属性投影和半连接结果。 但这两次数据传输的总量要远远小于传输一个整个关系

41、的数据量，一般有： T半T全。 半连接的得益：Benefit1(RS )=(1-)*Size(R)*Card(R)*C1 (为选择度) 半连接的损失：传输B (S) =C0+C1* size (B)* val( BS),93,基本原理 采用半连接操作的分布式查询处理是在从一个站点 传送关系到另一个站点做连接之前，先除去那些与 连接无关的数据，减少做连接操作的关系中的数据量，减少站点间数据的传输量，减少传输的代价。 如果只需要一个关系中一小部分元组参与和另一个 关系连接的话，这是一个使数据传输量最小化的非 常有效的方案。此时有 T半 T全，采用半连接方案 是合适的。 在分布式数据库的查询优化中，

42、这是常用的方法之一。,94,采用半连接优化算法的步骤 计算每种半连接方案的代价，并从中选择一种最佳 方案； 选择最得益的站点或传输代价最小的站点计算采用 全连接方案的代价； 比较两种方案，确定最优方案。,95,例题：设有关系R,S,T,如图所示， （1）计算连接RST （2）计算半连接RS, SR, S T, TR,RT, TS （3）三个关系R,S,T分别位于三个不同的站点X,Y,Z. 若采用基于半连接算法计算连接RST ，请选择使得传输代价最少的连接执行的站点和确定半连接序列。,R,S,T,96,解：,（1）RST,（2）RS,SR,S T,TR 为空 RT 为空 TS,97,（3）假设每

43、个属性域长度均为1B，C0=0,C1=1,考虑所有的半连接,P1方案： =4/6=2/3 P2方案： =3/6=1/2 P3方案： =4/6=2/3 P4方案： =2/4=1/2,计算T=RS 选择度公式： =Card(T)/Card(R),P1方案：Benefit1(RS )=(1-)*Size(R)*Card(R)*C1=1/3*3*6 P2方案： Benefit2(SR )=(1-)*Size(S)*Card(S)*C1=1/2*3*6 P3方案： Benefit3(ST )=(1-)*Size(S)*Card(S)*C1= 1/3*3*6 P4方案： Benefit4(TS )=(1-

44、)*Size(T)*Card(T)*C1=1/2*3*4,计算RS收益公式：Benefit1(RS )=(1-)*Size(R)*Card(R)*C1,计算RS代价公式：Cost(RS )= C0+C1*size (B)*val(BS),P1方案：Cost1(RS )=2*5 P2方案： Cost2(SR )=2*4 P3方案： Cost3(ST )=1*3 P4方案： Cost4(TS )=1*4,98,a) 选择得益最高的P2进行优化，得到新的R,S,T，并对受到影响的的方案 重新计算得益和费用。新的R, S, T如下：,对受到影响的的方案重新计算得益和费用,99,b)选择得益最高的P4进

45、行优化，得到新的R,S,T，并对受到影响的方案重新 计算得益和费用。 新的R, S, T如下：,对受到影响的的方案重新计算得益和费用,100,c) 选择得益最高的P1进行优化，得到新的R,S,T，并对受到影响的方案重新计算得益和费用。 新的R, S, T如下：,对受到影响的的方案重新计算得益和费用,101,d) 选择得益最高的P3进行优化，得到X,Y,Z站点上最终的R,S,T。 X,Y,Z站点上最终的R,S,T如下：,所以选择各站点做连接的代价为： X站点代价=2*3+2*3=12 Y站点代价=4*3+2*3=18 Z站点代价=4*3+2*3=18 故选择X站点作为收集站点代价最低。,由简化过

46、程得知半连接过程为： 1. S = SR 2. 将S传送给T,做半连接TS得到T = TS 3. 将S传送给R,做半连接RS得到R= RS 4. 将T传送给S,做半连接ST得到S= ST 即: (R(SR)(SR) (T(SR)(T(SR),102,半连接算法和直接连接算法区别 取决于数据传输和局部处理的相对费用； 如果传输费用是主要的，采用半连接方案处理策略比较 有利。例如 SDD-1(美国计算机公司1976至1978年推出的第一个分布式数据库管理系统)是基于低速窄带广域网设计的采用半连接作为查询处理策略的分布式数据库系统。 如果认为局部处理费用是主要的，则采用直接连接方案 处理策略比较有利

47、。美国的System R*(IBM公司San Jose研究室研制)就是一个采用直接连接作为查询处理策略的分布式数据库系统。,103,两个关系在同一个站点 算法与集中式数据库相同。根据扫描顺序，RS中称外层关系为R, 内层关系为S。有两种方法可供选择： 嵌套循环法 顺序扫描外层关系R，对于R的每一元组扫描内层关系S； 查找在连接属性上一致的元组，把匹配的元组组合起来构成 结果的一部分； 需要扫描一次关系R和扫描 Card(R) 次关系S，以查找匹配的 元组。,一、直接连接的一般常用策略,104,两个关系在同一个站点 排序扫描法 先把两个关系按照连接属性进行排序； 然后按照连接属性值的顺序扫描这两

48、个关系，使匹配的元组 成为结果的一部分； 对两个关系都扫描一次，但增加了排序代价。对内层循环中 具有相同连接属性值的元组，应缓冲起来，以便再用时不用 重新扫描该数据页面。,一、直接连接的一般常用策略,105,两个关系在不同站点 对存储在不同站点上的关系R和关系S的连接，除考虑局部代价外还需要考虑 传输代价。影响传输代价有两个因素：选择不同的传输方式和站点进行连接。 两种传输方式 整体传输：若连接操作RS，称R为外层，称S为内层。 如果传输内层S，则保存S（被多次扫描，传输量少） 如果传输外层R，则S可直接使用依次来到的R元组，不保存R(但传输量大） 按需传输 只传输需要连接的元组，一次一个元组

49、，无需临时存储器。 每次提取都要交换一次信息，传输代价高，只在高速局域网中才是合理的。 三种选择连接站点的方法：在R所在站点；在S所在站点；在第三个站点。,一、直接连接的一般常用策略,106,在分布式数据库系统中，通过重新分布元组来实现操作内并行性，通常认为是不可行的，但操作间的并行，包括流水线并行和独立的并行，是可以在分布式系统中发挥作用的。 流水线并行 在查询表达式中，一个操作A的输出元组作为第二个操作B的输入； 在第一个操作尚未产生全部的输出元组集合之前，第二个操作就 可以在它的输入上进行工作； 可以在不同的站点上运行A和B，在A产生部分结果元组的同时， B来使用它们。 独立的并行 查询

50、表达式中，那些相互之间没有依赖关系的操作可以并行地执行。,二、利用并行性的直接连接的策略,107,例子：考虑一个四个关系(或片段)的连接：R1 R2 R3 R4 假定：关系Ri存储在站点Si上，连接的结果必须在站点S1上给出。 可以利用流水线并行和独立的并行结合起来的策略： 把R1送到S2并在S2上计算R1 R2，同时把R3送到S4上计算R3 R4 。 在站点S2上计算R1 R2的过程中，就可以把已经计算出来的元组送到站点S1，而不必等到整个连接计算完成。 同样，在站点S4上计算R3 R4的过程中，就可以把已经计算出来的元组送到站点S1，而不必等到整个连接计算完成。 一旦（R1 R2）和（R3

51、 R4）的元组到达站点S1, 在S1上就可以开始计算（R1 R2）（ R3 R4 ）。 也即站点S1上最终连接的结果的计算可以同S2上R1 R2 的计算以及S4上的R3 R4计算并行地进行。,108,四种基于直接连接的优化算法 （考虑关系分片情况） 利用站点依赖信息的算法； 分片与复制算法； 站点依赖和数据复制结合算法； Hash划分算法。,109,考虑两个关系R1和R2在属性A上的连接操作问题R1AR2 。假定R1和R2都进行了分片，其初始分布如下图所示。 考虑本问题处理策略：在同一站点上做片段的连接操作，然后合并连接结果，即做 R1R2=(F11AF21) U (F12AF22)。,110

52、,站点依赖定义： 设两个片段关系Ri分片为Fi1和Fi2, Rj分片为Fj1和Fj2 关系Ri和Rj在属性A上满足条件： Fis A Fjt= , 其中s t , 则称Ri和Rj在属性A上站点依赖。 也就是说: Ri A Rj = Us (Fis A Fjs) 对于包含着两个关系的片段的每个站点S 都成立。 此时关系的连接操作无站点之间数据传输。,111,Ri,Rj,本地连接,Result,A,f(A),f(A),Ri,Rj,112,从站点依赖的定义，可得如下推论： 推论1：若Ri和Rj在属性A上站点依赖，则Ri和Rj在任何包含A的属性集B (即A是B的子集)上也是 站点依赖。(把原来按属性A

53、划分的片段根据属性组B划分成更细的片段) 推论2：若Ri和Rj在属性A上站点依赖，另一属性(或属性组)B函数决定A (即BA)，且A ，则Ri和Rj在属性B 上也站点依赖。,113,从站点依赖的定义，可得如下推论： 推论3：若Ri和Rj在属性A上站点依赖，且若 Rj和Rk在属性B上站点依赖，则 ( Ri ARj B Rk ) = U s (Fis A Fjs B Fks) 其中s为所有包含Ri ,Rj 和Rk的片段的任一个站点。或者说，所有的连接操作可以在本地完成而无需数据传送。,114,从站点依赖的定义，可得如下推论： 推论4：假定有查询Q及其子查询Q和一个连接RjBRk，其中Rj是被子查询

54、Q引用的一个关系，子查询Q 并不引用Rk。设若子查询Q中的连接 操作可无数据传送执行，且Rj和Rk在 B 或 B 的 子集上站点依赖，则整个查询Q就能无数据传送执行。,115,例如，设查询Q为: RiARjBRk ， 子查询Q为 RiARj 可以无数据传送， RjBRk在B或B的子集上站点依赖， 根据推论1，B的一个子集就可以做到无数据传送。 则整个查询Q就能够以无数据传输的方式处理。,116,基于上述推论,可以构造一个算法，利用站点依赖信息P确定一个查询是否能够无数据传送执行。 Placement_Dependency (Q, P, S)，其中： /* R=R1，R2，R3，Rn是查询Q引用

55、的一组关系 P是站点依赖信息 S是一个连接操作可以无数据传送的执行的最大关系 集合 开始时S是空集。 算法结束时，若S=R， 则Q可以无数据传输执行 */,117,算法Placement_Dependency (Q, P, S)步骤： 初始化S= ， R=R1，R2，R3，,，Rn。 若能找到一对关系Ri和Rj在属性A上站点依赖，且Ri C Rj 包含 在Q中，其中C包含A，那么把Ri和Rj 放到S中，否则算法终止，返回空集S。 只要存在R中而不在S中的关系Rk满足下面的特性， 就循环做：把Rk插入 S中。可被S包含的关系Rk应该满足的特性是：有 S中的关系比如 Rj 与Rk在属性B上有站点依

56、赖关系，且Rj BRk 在Q中 或者可以由Q导出，根据推论3，则Rk可被包含在S中。 如果S=R，则Q可以无数据传送处理。,118,例：有查询Q为(R1AR2 BR3CR4), 假定R1和R2在属性A上站点依赖， R2和R3在属性B上站点依赖，R3和R4在属性C上站点依赖，则本查询 可无数据传送处理。 算法步骤： 初始化S= ，R=R1,R2,R3,R4； 找到一对关系R1和R2在属性A上站点依赖，所以将R1和R2放入S； 接下来，由于R3与R2在属性B上站点依赖且R2 BR3在查询Q中， 根据推论3，则R3被加入到S中； 最后，R4由于与R3在属性C上的站点依赖关系及连接条件，也被加入到S中

57、。 这样，S=R1,R2,R3,R4= R, 查询引用的所有关系都包含进S中，因此本查询Q可无数据传送处理。,119,如果一个查询不能在无数据传送方式下得到处理，则可以采用“片段和 复制算法”来处理查询。 在该算法中，选择一组站点，把查询引用的某个关系的所有片段分布在 这些站点上，其余被引用的关系则复制到每一个选定站点中去。 考察R1中的一个元组t，它在F11或F12中。如果t在F11中，那么它将与站点S1中R2的副本得以连接；如果 t 在F12中，那么它将与站点S2中R2的副本 连接。所以有 (R1R2)=Ui (F1i R2), 其中的并操作取遍每个有 R1片段的站点Si。在每个站点 Si , 发生一个F1i 和R2的连接，这些连接可并行执行。,120,本算法可应用于涉及两个或两个以上的关系的查询： 其中一个关系在选定站点中保持分片状态，其余关系都将被复制。 被复制的那些关系可先连接形成一个关系T，并在包含 保持分片状态关系的各片段站点上复制T的副本，然后 在每个站点中，T的副本与相应的片段连接。 由于这与双关系的情形是等