分布式查询优化.ppt

文档介绍：四分布式查询优化
查询操作
选择 SL, 投影 PJ
连接 JN, 并 UN

笛卡尔积CP,差DF, 交等
连接优化方法
基于半连接的连接优化(SDD-1算法)
基于直接连接的接连优化
半连接(Semi_Join)
R S= R( R S)
半连接使关系简化
R’= R SJ S  R 直接SJ成立
R’’= (R SJ (R SJ T))  R 多次SJ仍然成立
例子
R
S
T
R
S
T
B=B
C=C
A=A
R,S,T的循环连接图
对R的充分简化
R’=R SJ T
S’=S SJ R’
T’=T SJ S’
减一个元组
R’’=R’ SJ T’
S’’=S’ SJ R’’
T’’=T’ SJ S’’
减两个元组
R’’’=R’’ SJ T’’= 减少三个元组
一般:简化程序长度随着关系的元组数目增长线性增长。
评价模型
关系的概貌
Card(R) 片段关系R的元组数目
Size(A) 属性A的大小(即字节数)
Size(R) 片段关系的大小, 属性大小之和
Val(A[R]) 属性A在R中出现的不同值
目标: 减少通讯量
R S (R S) S or
R (S R) or
(R S) (S R)
A=B
A=B
A=B
A=B
A=B
A=B
A=B
A=B
基于半连接操作的连接操作
基于半连接操作的连接操作-续
R S = (R S) S
执行步骤如下:
发送B S 到site r
Cost = C0+C1*Size(B)*Val(B[S])
在r站点执行SJ, 费用为零, 令R’=R SJA=B S
发送R’到site s, 费用
Cost = C0+C1*Size( R )*Card (R’)
在r站点计算JN,费用为零。
总费用
CSJ=2*C0+C1*((Size(B)*Val(B[S]) + Size( R)* Card (R’))
A=B
A=B
A=B
Example: R S
A B
2 a
10 b
25 c
30 d
25 w
3 x
10 y
15 z
32 x
A R = [2,10,25,30]
R S
S R =
A C
10 y
25 w
A=A
A=A
A C
S
R
10 b
25 c
A B