基于半连接的分布式数据库查询优化研究.

基于半连接的分布式数据库查询优化研究 余 弋 (安徽工程大学计算机与信息学院,芜湖 241000 关键词:分布式数据库;查询优化;半连接操作 收稿日期:2010-06-23 修稿日期:2010-07-23 作者简介:余弋(1985-,女,安徽芜湖人,硕士研究生,研究方向为分布式数据库 分布式数据库系统的分布和冗余使查询处理复杂化,因此分布式查询处理的优化显得尤为

重要。半连接操作是查询技术中的非常有效和重要的技术。分析分布式数据库中半连接操作的过程以及执行代价,比较两种半连接操作的执行代价评估,介绍SDD-1算法。

摘 要:0引言 分布式数据库是把数据分布在不同的站点上,但 这些数据片是建立在统一的逻辑框架上的,并有高级的数据库管理系统进行统一控制,它是统一性与自治性的完美结合。分布式查询处理是用户和分布式数据库的接口,是分布式数据库的一项关键技术。由于数据的分布使得分布式数据库系统中的查询问题比集中式数据库要复杂得多。不同的查询处理方法可能导致不同的通 信费用、并行时间以及响应时间。要获得最小的查询开销,就要对数据进行合理分布、查询优化。

1分布式查询优化目标 在集中式数据库系统中,由于系统大都运行在单个 处理器的计算机上,所以查询总代价为CPU 代价+I/O 代价,查询优化的目标是磁盘存取数,即要求产生最小磁盘数的查询执行计划。

在分布式数据库系统中,由于数据的分布和冗余,使得查询处理除了考虑CPU 代价和I/O 代价之外,还需要考虑在网络上传输数据的时间开销以及多个节点并行执行带来性能的提高,总代价=CPU 代价+I/O 代价+通信代价,查询执行时使其通信代价最省是分布式数据库查询优化的目标之一,另一种目标是以每个查询的相应时间最短为标准。

在分布式查询优化中经常同时使用这两个标准。根据系统应用的不同,一种作为主要标准,一种作为次

要标准。 2半连接查询优化的基本方法 在分布式数据库中,查询优化包括两个方面:查询 策略优化和局部处理优化,而分布式查询策略优化尤为重要。在分布式数据库中,查询的执行策略有很多种,不同的执行策略,系统资源耗费和响应时间也不同。

查询优化有两种基本方法:①查询转化,即以不同顺序执行关系操作;②查询映射,以一系列高效算法访问各种设备和实现关系操作。目前,对查询处理出现了许多优化算法,例如适用于多站点连接的基于半连接的优化算法和基于直接连接的优化算法等。 2.1基本原理 采用半连接操作,在网络中只传输参与连接的数据,数据在网络中传输时,都是以整个关系(也可以是片段传输,显然这是一种冗余的方法。在一个关系传输到另一场地后,并非每个数据都参与连接操作或都有用。因此,不参与连接的数据或无用的数据不必在网络中来回传输。

用半连接技术实现连接操作的程序,即用一组具有半连接与连接的操作映射出具有与等连接相同结果的过程。

2.2操作过程 (1半连接操作 半连接操作是由投影和连接操作导出的一种关系代数操作。假定有两个关系R 和S ,在属性R.A=S.B 上做半连接操作可表示为:

R ∝S=∏R (R ∞S (1R ∝S=R ∞(∏B (S (2 (2采用半连接操作表示连接操作的过程

图1半连接方法表示连接操作过程 (1在站点2作关系S 在R 和S 公共属性集B 上的投影∏B (S ; (2把∏B (S 结果送到站点1,代价为C 0+C 1×size (B ×val (B[s]; (3在站点1上计算半连接,设置其结果为R',则 R'=R ∝A=B S ; (4把R'从站点1送到站点2的代价是:C 0+C 1×size (R'×card (R'; (5在站点2上执行连接操作:R'∝A=B S 2.3费用估计 基于半连接程序的查询优化的主要目标是减少站点间的通信代价。通信代价与分布式数据库所依附的计算机网络模型及其性能有关。对于不同的计算机网络应该根据实际情况,设计对应的费用估计侧率和方法。

如果假设网络中站点之间传递相同信息量的数据所花费的代价是相同并且忽略站点之间的差异以及路由选择等费用,那么一个站点发送X 个字节的信息到另一个站点所花费的费用可以描述为C[X]=C 0+C 1×X,其中C 0和C 1是网络性能相关的参数。

利用这个公式可以估计各种查询方案对应的传输费用。例如,对于全连接操作R ∞A=B S ,假如现在用下面的三种方案来解决。

(1采用S ∞A=B (R ∝A=B (∏B S 对应的半连接程序,费用有: ①在本地把S 投影到B :假设∏B S 结果为X B 个字节,投影费用为P B ; ②把X B 个字节发送给R 所在站点:费用为C B =C 0+C 1×X B ; ③和R 执行半连接运算:假设结果为X RB 个字节,半连接费用为S B ; ④把X RB 个字节送到S 所在的站点:费用为C RB = C 0+C 1×X RB ; ⑤和S 执行连接运算:假设连接费用为J SRB ,那么总的费用为:COST 1=P B +C B +S B +C RB +J SRB =(P B +S B +J SRB +

(2C 0+C 1×(X B +X RB =COST 11+COST 12。 其中COST 11为本地运算费用,COST 12为站点传输费用。 (2采用R ∞A=B (S ∝A=B (∏B R 对应的半连接程序,费用有: ①在本地把R 投影到A :假设∏A R 结果为X A 个字节,投影费用为P A ; ②把X A 个字节发送给S 所在站点:费用为C A =C 0+C 1×X A ; ③和S 执行半连接运算:假设结果为X SA 个字节,半连接费用为S A ; ④把X SA 个字节送到R 所在的站点:费用为C SA =C 0+C 1×X SA ; ⑤和S 执行连接运算:假设连接费用为J SRB ,那么总的费用为:COST 2=P A +C A +S A +J RSA =(P A +S A +J RSA +(2C 0+

C 1×(X A +X SA =COST 21+COST 22。 其中COST 21为本地运算费用,COST 22为站点传输费用。 (3直接采用全连接R ∞A=B S 连接程序,一种可能解决办法和费用如下。 ①把R 全部发送给S 所在站点:假设R 为X R 个字节,费用C R =C 0+C 1×X R ; ②和S 执行连接运算:假设连接费用为J RS ,那么,总的费用为COST 3=C R +J RS =J RS +(C 0+C 1×X R =COST 31+

COST 32。 其中COST 31为本地运算费用,COST 32为站点传输费用。 另外一种可能的方案是把S 全部发送给R 所在的站点并和R 进行全连接,那么对应费用为COST 4=J SR +(C 0×X S =COST 41+COST 42,其中COST 41为本地运算费用,

,,,,,,,,, ,,,,,,, ,,,,Á,,,,,,,Á COST42为站点传输费用。 比较上面的COST1、COST2、COST3和COST4,可以选取代价最小的加以执行。

点之间传递相同信息量的数据所花费的代价是相同的,这个假设在站点之间的距离和发送/接收性能相当的情况下是合理的。如果站点之间以及路由选择等费用差异很大时,需要重新考虑相关因素的影响因子,缺点合理的费用评估方法。

2.4SDD-1算法 SDD-1算法有两部分组成:一是基本算法,根据评估缩减程序的费用、效益、收益估算几个因素,给出全部的半连接缩减程序集,决定一个最有益的(收益的执行策略,但效率不一定高;另一个是后优化,将基本算法得到的解进行修正,以得到更合理的执行策略。

(1基本算法 ①基础:已有了从查询数转换的优化模型且所有关系已完成局部缩减。 ②方法: ●根据已得到的缩减关系的静态特性表,构造可能的半连接缩减程序; ●按半连接缩减程序的静态特性表分别计算其费用和收益,从一组可能的静态特性表中选取一个半连接程序,设为M;

●以M完成缩减后,又将产生一组新的静态特性表再进行计算,再从一组可取的静态特性表中选一个半连接程序,但是每个半连接程序只做一次(避免导致缩减程序太长,效率不高; ●反复直到无半连接缩减程序为止。 ③结束:以若干次迭代以后的最后缩减关系的静态特性表为基础,进行场地选择(费用计算,决定执行查询的场地(可能与原查询要求的场地不同。

(2后优化 在基本算法中,每次迭代时只考虑本次迭代时的改善,这种改善不一定最好。后优化有两种修正:

①若最后一次半连接程序缩减关系的所在场地恰好是被选中的查询执行场地,则最后一次半连接可以取消;

②对基本算法的主迭代所构成的半连接程序的流程图进行修正。因为一开始的(或某一个半连接缩减程序的代价很高,例如有R+S。这时可以把S缩减后在进行半连接缩减,即可修正半连接的操作程序。

3结语 本文重点讨论基于半连接的查询优化技术在分布式数据库中的应用,证明了查询策略的好坏将直接影响计算机网络资源的耗费。但分布式数据库系统的建立环境和技术内容复杂,对于查询优化技术,还有许多问题有待进一步研究和解决。相信随着计算机网络技术的飞速发展,分布式数据库技术也必将迅猛发展,并日趋完善。

参考文献 [1]陈建荣,严隽永,叶天荣.布式数据库设计导论(第一版 [M].清华大学出版社,2002:20~78

[2]Bell D,Crimson J.Distributed Database System[M].New Jer-sey:Addison Wesley Publishing,2004:5~79

[3]邵佩英.布式数据库系统及其应用[M].科学出版社2006, 1:3~41