nullnull分布式查询优化概述
分布式查询优化基础知识
分布式查询分类和层次结构
基于关系代数等价变换的查询优化处理
基于半连接算法的查询优化处理
基于直接连接算法的查询优化处理
直接连接操作的常用策略分布式数据库中的查询处理和优化 第3章查询处理问题查询处理问题集中式
查询转换为代数表达式
从所有等价表达式中选择最优的代数表达式
分布式
除了集中式问题外，还有
站点之间交换数据的操作
选择最优的执行站点(分布）
数据被传送的方式null目标总代价最小响应时间最短集中式分布式CPU代价（相对固定）I/O代价（优化的目标）CPU代价I/O代价（访问磁盘）通讯代价数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间
主要标准
辅助标准null准则：
使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。
通讯费用与所传输的数据量和通信次数有关
响应时间和通信时间有关，也与局部处理时间有关
查询代价分析
远程通讯网络
局部处理时间可以忽略不计，减少通讯代价是主要目标
高速局域网
传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理时间是关键null例子
S(s#, sname, age, sex) 104 元组 Site A
C(c#, cname, teacher) 105 元组 Site B
SC(s#, c#, grade) 106 元组 Site A
每个元组长度100bit, 通讯传输速度 104 bit/sec, 通讯延迟 1secnull查询: 所有选修maths 课的男生学号和姓名.
SELECT s#, sname
FROM S, C, SC
WHERE S.s#=SC.s# AND
C.c#=SC.c# AND
sex=‘男’ AND cname=‘maths’;null代价公式
QC = I/O 代价 + CPU 代价 + 通讯代价
通讯代价
TC = 传输延迟时间C0
+ (传输数据量X /数据传输速率C1)
=传输次数*1+传输的bit数*104。
null六种查询策略null六种查询策略null相关表述记号⒈ 设关系模式为R(A1, A2, …, An)。它的一个关系设为R。
t∈R表示t是R的一个元组。t[Ai]则表示元组t中相应于属性Ai的一个分量 。 ⒉ 若A={Ai1, Ai2, …, Aik}，其中Ai1, Ai2, …, Aik是A1, A2, …, An中的一部分，
则A称为属性列或域列。 t[A]=(t[Ai1], t[Ai2], …, t[Aik])表示元组 t 在属性
列A上诸分量的集合。则 表示{A1, A2, …, An}中去掉
{Ai1, Ai2, …, Aik} 后剩余的属性组。null相关表述记号⒋ 给定一个关系R(X,Z)，X和Z为属性组。我们定义，当t[X]=x时，x在R中
的象集（Images Set）为： Zx={ t[Z]|t∈R, t[X]=x }
它表示R中属性组X上值为x的诸元组在Z上分量的集合。 传统的集合运算传统的集合运算 并运算 设关系R和关系S具有相同的目n（即两个关系都有n个属性），且相应
的属性取自同一个域，则关系R与关系S的并由属于R或属于S的元组组成。
其结果关系仍为n目关系。记作： R∪S={ t | t∈R∨t∈S } 传统的集合运算传统的集合运算 差运算传统的集合运算传统的集合运算 交运算R1∩R2 设关系R和关系S具有相同的目n，且相应的属性取自同一个域，
则关系R与关系S的交由既属于R又属于S的元组组成。其结果关系仍
为n目关系。记作： R∩S={t|t∈R∧t∈S} 广义笛卡尔积 广义笛卡尔积专门的关系运算专门的关系运算S(S#,SN,SD,SA) 选择运算 选择运算选择运算是从关系中选取使公式为真的元组。这是从行的角度进行的运算。 在关系R中选择满足给定条件的元组，记做：
σF (R) ={ t | t ∈R Λ F(t)=‘真’ }
F是一个公式，表示形式为由逻辑运算符（∧,∨,٦)连接各算术表达式组成。
算术表达式的基本形式为：XθY. θ ={>, ≥ ,<, ≤ ,=, ≠} 。例1 求计算机科学系CS的学生σ SD=‘CS’ (S)σ SD=‘CS’ (S) 选择运算 选择运算 在关系R中选择满足给定条件的元组，记做：
σF (R) ={ t | t ∈R Λ F(t)=‘真’ }例2 求计算机科学系CS，年龄不超过21岁的学生。σ SD=‘CS’ ∧SA≤21 (S) 投影运算 投影运算 这是从列的角度进行的运算。例3 πSN,SD (S) 即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。πSN,SD (S) 关系R上的投影是从R中选择若干属性列组成新的关系。记做：
πA (R) ={ t[A] | t ∈R}
投影之后不仅取消了某些列，还可能取消某些元组。 连接运算（θ连接） 连接运算（θ连接）SRR S ∞
C90(S.S #=SC.C# (S×SC)))nullnullnull水平分片的查询优化的基本思想：
尽量把选择条件下移到分片的限定关系处
再把分片的限定关系与选择条件进行比较
去掉它们之间存在矛盾的相应片断
如果最后剩下一个水平片断，则重构全局关系的操作中，就可去掉“并”操作（至少可以减少“并”操作的次数）
null全局关系
EMP(EMP#, ENAME, SALARY,DEPT#,DNAME)
垂直分片：E1 (EMP#,DEPT#,DNAME)
EMP2(EMP#, ENAME, SALARY)查询问题：雇员的姓名和工资情况
ENAME,SALARY(EMP)nullnull垂直分片的查询优化的基本思想：
把垂直分片所用到的属性集，与查询条件中的投影操作所涉及的属性相比较，去掉无关的垂直片断
如果最后只剩下一个垂直片断与查询有关时，去掉重构全局关系的“连接”操作（至少可以减少“连接”操作的次数）
null假定有两个关系R,S,在属性R.A=S.B上做半连接操作，可表示为：
R∝A=B S= R( R ∞A=B S)=R ∞A=B (B (S))
S∝A=B R= S( S ∞A=B R)=S ∞A=B (A (R))
用半连接表示连接操作
R∞A=BS= ( R∝A=B S)∞A=BS
= （R ∞A=B (B (S)) ∞A=BS
R∞A=BS = ( S∝A=B R)∞A=BR
=(S ∞A=B (A (R) )∞A=BR例子1: R ∝ S例子1: R ∝ S A B A (R) = [2,10,25,30]
R ∝ SS∝R =A C
10 y
25 wA=AA=AA CSR A B null例子2：半连接简化 RSTRSTB=BC=CA=AR,S,T的循环连接图对R的充分简化R’=R ∝ TS’=S ∝ R’T’=T ∝ S’减少一个元组nullR’’=R’ ∝ T’S’’=S’ ∝ R’’T’’=T’ ∝ S’’减两个元组R’’’=R’’ ∝T’’ = 减少三个元组一般：简化程序长度随着关系的元组数目增长线性增长。
对R的另一个简化程序：
R’=R ∝ S T’ = T ∝ R’ S’ = S ∝ T’ （练习）
nullRS网络 站点1 站点2 (1) B(S)(3) R’= R∝A=BB(S) (2) B(S)
(4) R’= R∝A=B B(S) (5) R’∞A=BS
R∞A=BS= ( R∝A=B S)∞A=BS= （R ∞A=B (B (S)) ∞A=BSnull关系的概貌
Card(R) 片段关系R的元组数目
Size(A) 属性A的大小(即字节数)
Size(R) 片段关系的大小, 属性大小之和
Val(A[R]) 属性A在R中出现的不同值的个数null代数操作对关系概貌的影响
选择操作
S= F（R）
Card(S)= ρ *Card(R) Size(S)=Size(R)
Val(B[S])是Val(B[R]), Card(S), Card(R)的函数
并操作
T=R∪S
Card(T) Card(R)+Card(S)
Size(T)=Size(R)=Size(S)
Val(A[T]) Val(A[R])+Val([AS])
null代价公式：T=C0+C1*X
在站点2上做投影B (S)
把B (S)传到站点1上，代价为：
C0+C1* size (B)* val( B[S])
在站点1上计算半连接，R’=R ∝A=B S
把R’从站点1传到站点2的代价为：
C0+C1* size (R’)* card( R’)
在站点2上执行连接操作：R’ ∞A=BS
采用半连接的总代价
T半R= 2C0+C1* (size (R’)* card( R’) +size (B)* val( B[S]))
T半S= 2C0+C1* (size (S’)* card( S’) +size (A)* val( A[R]))
比较T半R 与T半S, 取最优者null基本原理
通常有两次传输
但是传输的数据量和传输整个关系相比，要远远少
一般有：T半<>card（R’），可减少站点间的数据传输量
半连接的损失：传输B (S) =C0+C1* size (B)* val( B[S])
基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价
采用半连接优化算法的步骤
计算每种半连接方案的代价，并从中选择一种最佳方案
选择传输代价最小的站点，计算采用全连接的方案的代价
比较两种方案，确定最优方案null半连接算法和直接连接算法区别
取决于数据传输和局部处理的相对费用
如果传输费用是主要的，采用半连接，SDD-1
如果本地费用是主要的，采用直接连接,System R*
四种基于直接连接的优化算法 （考虑关系分段）
利用站点依赖信息的算法
分片与复制算法
站点依赖和数据复制结合算法
Hash划分算法null
R1
R2
∪∞∞null站点依赖
设关系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都成立
此时关系的连接操作无站点间数据传输nullRiRj本地连接ResultAf(A)f(A)RiRj∞null推论
若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的连接操作能够以无数据传输的方式处理。 null算法描述
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上站点依赖，且Ri ∞ CRj 包含在Q中，其中C包含A,那么把Ri和Rj放到S中，否则算法终止，返回空集S。
只要存在R中而不在S中的关系Rk满足下面的特性，就把其放入S中：有S中的关系比如Rj ，与Rk在属性B上有站点依赖关系，且Rj ∞ BRk在Q中或者可以由Q导出，根据推论3，则Rk可被包含在S中。
nullnull查询引用的某个关系的所有片段分布在这些站点上,其余被引用的关系复制到每一个选定的站点
R1 ∞ R2 = Ui (F1i ∞ R2)
算法可应用到涉及两个或两个以上的关系的查询
其中一个关系保持分片状态
其他关系可先连接起来，再被复制到各个站点
在各个站点上，其他关系副本与相应的第一个关系的片断连接nullR1R21R22本地连接Resultf
partitionunionR1R2∞null如何确定保持分片关系的关系，以使得查询具有最短的时间
估算各种策略的响应时间，选择时间最短的策略，S1站点上响应时间(完成时间，FT(Q,S1,R1)）包括三部分，以P.85图为例：
F22到S1的数据传输时间
F22和F21进行合并形成S1上的R2副本的时间
F11和S1上的R2副本之间连接的时间
比较Max{FT(Q,S1,R1), FT(Q,S2 ,,R1)}, Max{FT(Q,S1,R2), FT(Q,S2 ,,R2)}，找出响应时间小的保持分片关系
算法忽略了把结果传送到要求答案的用户站点的代价，和将部分结果组装成最终结果的代价，认为它们不大重要，或者采用其他算法时这些部分没有太大差别。null
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)为保持分片状态的关系nullR1R2R2R2F11F13F21F22本地连接Resultf
partitionunionR1R2F12∞null举例
已知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)=2450
因此, 查询响应时间在R1保持分片状态为 2550.null令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保持分片计算查询
null站 点关
系R1R2R3设R1和R2在属性A上站点依赖, 查询R1 ∞A R2 ∞B R3null设R1和R2在属性A上站点依赖, 查询R1 ∞ R2 ∞ R3
第一个连接因为站点依赖，无传输处理
第二个连接因为存在R3的副本,也没有传输处理
保证查询无传输的方法是R1和R2连接执行后，形成一个关系R4，它有两个片断：
一个由F11 ∞ F21给出
一个由F12 ∞ F22给出
最后由R4和R3的副本连接得到最后的结果
null连接依赖定义：
如果Ri 和Rj 在属性A上站点依赖
或者关系Ri复制在关系Rj各片断的站点上
或者关系Rj复制在关系 Ri各片断的站点上
有了此定义，站点依赖算法可理解为：利用站点依赖和复制信息来确定一个查询中的连接能否无数据传送处理。
null利用Hash函数对分片关系上的连接属性作站点依赖计算, 再据此分片, 以获取站点依赖的连接算法
例如, 运用Hash函数
1 若a 是奇数
0 若a 是偶数
对R中每个元组, h(a)为1送入站点S1, h(a)为0送入站点S2. 于是片段关系R被划分为Ro和Re
R1 ∞ R2 = (R1o ∞ R2o) U (R1e ∞ R2e)h(a)=null利用Hash函数对分片关系上的连接属性作站点依赖计算, 再据此分片, 以获取站点依赖的JN算法
例如, 运用Hash函数
1 若a 是奇数
0 若a 是偶数
片断F11按属性A的值为奇和偶数划分成F11o和F11e，片断F12划分成F12o和F12e
站点S2上F12’=F11e∪F12e，站点S1上F11’=F11o∪F12o
显然A ( F11 ’ )和A(F12’)没有公共值,前面是奇数值后面是偶数值
F12’∞ F11’是空集，这说明R1和R2在新组成的片断下在属性A上站点依赖。
R1 ∞ R2 = （F11’∞ F21’） U （F12’∞ F22’） h(a)=null考察三个关系R1，R2和R3 ,它们在两个站点上，有两种情况：
在同一属性A上连接，R1∞A R2 ∞AR3
在三个关系的片断上应用Hash函数
使用新组建的片断，三个关系在属性A上将满足站点依赖
经这种划分和数据传送之后，两个站点上的片断在属性A上的连接就可以并行进行，合并执行结果给出答案
在不同属性上连接， R1∞A R2 ∞BR3
null在不同属性上连接， R1∞A R2 ∞BR3
在属性A上应用同样的Hash函数，在属性B上也应用同样的Hash函数，可能得不到希望的站点依赖
因R1中属性A的值是奇数的发往S1，R3中属性B是奇数的元组发往S1.但R2中某些元组可能在A上有奇数值，而在B上有偶数值
解决方法是允许这些元组在两个站点上都存在。
nullR1 ∞ A R2 ∞ B R3
若R1与R2在A上有相同的Hash函数, R2与R3在属性B上有相同的Hash函数null站点依赖算法
无数据传递
可利用索引做本地连接
每个站点连接数据总量是R，两个片段
分片和复制算法
数据传输总量是R
数据传送后,可能要重新创建索引
每个站点的连接数据量是(3/2)R,一个全关系和一个片断
Hash划分算法
数据传送量是R
索引方面, 比片段复制算法效率更低（因为数据传送后，两个关系的索引可能都不能使用了）
每个站点的连接数据量同站点依赖假定每个片段的大小是R大小的一半R/2null两个关系在同一个站点，
R∞S，称外层关系为R,内层关系为S
嵌套循环法
顺序扫描外层关系R，对于R的每一元组扫描内层关系S
查找在连接属性上一致的元组，组合起来构成结果的一部分
需要扫描一次关系R和Card（R）次关系S
排序扫描法
先把两个关系按照连接属性进行排序
然后按照连接属性值的顺序扫描这两个关系，使匹配的元组成为结果的一部分
对两个关系都扫描一次，但增加了排序代价
null两个关系在不同站点，关系R和关系S
两种传输方式
整体传输
如果传输S,则保存S（被多次扫描，传输量少）
如果传输R，则S可直接使用一次来到的R元组，不保存R(但传输量大）
按需传输
只传输需要连接的元组，一次一个元组，无需临时存储器
每次提取都要交换一次信息，传输代价高，只在高速局域网中才是合理的
三种选择连接站点的方法
R站点
S站点
其他站点null一个操作内的并行一般是不可行的
多个操作间的并行是可行的
流水线并行
在查询表达式中，一个操作A的输出元组作为第二个操作B的输入
在第一个操作尚未产生全部的输出元组集合之前，第二个操作就可以在它的输入上进行工作
可以在不同的站点上运行A和B，在A产生部分结果元组的同时，B来使用它们
独立的并行
查询表达式中，那些相互之间没有依赖关系的操作可以并行地执行null例子：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计算并行地进行。
总 结总 结 分布式查询优化概述（目标、准则和代价估算）
基础知识
关系代数回顾
等价变换规则
分布式查询分类和层次结构
基于关系代数等价变换的查询优化
基于半连接算法的查询优化处理
基于直接连接算法的查询优化处理（四类算法）
本文档为【第3章 分布式数据库中的查询处理和优化】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483