第四章 分布式查询优化.ppt

第四章 分布式查询优化 查询操作 选择 SL, 投影 PJ 连接 JN， 并 UN 笛卡尔积CP，差DF, 交等 连接优化方法 基于半连接的连接优化 （SDD-1算法） 基于直接连接的接连优化 半连接 R S= ?R( R S) 半连接使关系简化 R’ = R SJ S ? R 直接SJ成立 R’’= (R SJ (R SJ T)) ? R 多次SJ仍然成立 例子 评价模型 关系的概貌 Card(R) 片段关系R的元组数目 Size(A) 属性A的大小(即字节数) Size(R) 片段关系的大小, 属性大小之和 Val(A[R]) 属性A在R中出现的不同值 代数操作对概貌的影响 选择操作 Card(S)= ρ *Card(R) Size(S)=Size(R) Val(B[S])是Val(B[R]), Card(S), Card(R)的函数 评价模型-续 并操作 Card(T) ? Card(R)+Card(S) Size(T)=Size(R)=Size(S) Val(A[T]) ? Val(A[R])+Val(A[S]) 连接操作 Card(T) =(Card(R)*Card(S))/Val(A[R]) Size(T) = Size(R)+Size(S) Val(A[T]) ? Min(Val(A[R]), Val(B[S])) A 是连接属性 Val(A[T]) ? Val(A[R])+Val(B[S]) A不是连接属性 评价模型-续 半连接 ρ =Val(A[S]) / Val(Dom(A)) Card(T) = ρ *Card(R) Size(T) = 第一个操作数Size Val(A[T]) = ρ *Val(A[R]) 基于半连接操作的连接操作 目标: 减少通讯量 R S ? (R S) S or R (S R) or (R S) (S R) 基于半连接操作的连接操作-续 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’)) Example: R S A B A B A C R S 基于半连接优化 SJ 不对称 (R SJ S) JN S 的费用CSJ ( S SJ R) JN R 的费用C ’SJ CSJ’=2*C0+C1((Size(A)*Val(A[R]) + Size( S)* Card (S’)) 比较CSJ与CSJ’, 取最优者 SDD-1算法 通过考虑SJ程序的得益来计算优化 得益(R SJA=B S)=(1-ρ) *Size(Ｒ)*Card( R)*C1 ρ: SJ 的选择率 SJ的费用(R SJA=B S)=C0+Val(B[S])*Size(B)*C1 SDD-1算法(续) 基础 给定一个优化图G, 对G中出现的关系已经施加了全部本地简化。 循环 a) 给出所有可能的SJ b) 在有益SJ中选择得益最大或者费用最低的SJ，若没有这样的SJ，则中止循环 c) 重新求取受影响的SJ的得益与费用，Goto a) 后优化 选出要求较少传输的site来收集全部关系，在此执行SJ 举例 简化后的关系优化图: 收集: 完成上述p1--p4半连接简化后,考虑最终在哪个site收集元组执行完全连接 选择收集全部关系的site: Cost(site1)=size(supply)*card(supply)+size(dept)*card(dept) = 6*200+5*20=1300 Cost(site2)=size(supplier)*card(supp