分布式数据库查询优化的

点赞:30229 浏览:142030 近期更新时间:2024-03-14 作者:网友分享原创网站原创

摘 要

分布式数据库性能受查询策略的影响.一个查询的处理代价通常由进行通信的信息量来决定.通过半连接的查询优化算法、站点依赖优化算法和哈希划分算法可以大大降低查询代价.

【关 键 词】分布式数据库查询优化半连接站点依赖哈希划分

分布式数据库的产生是由于计算机网络通信的迅速发展以及地理上分散的公司、团体、和组织对数据库更为广泛的应用需求.为了提高分布式数据库系统的性能,我们需要找到影响分布式数据库系统查询代价的关键因素并能够以此为基础提出一些针对分布式数据库的查询优化的方案.

1分布式数据库查询代价

在分布式数据库中,对于查询代价我们必须考虑:

(1)数据在网络上的传输代价

(2)通过在几个站点上并行处理查询的一部分而可能得到性能提升

本文将通信代价作为查询过程中查询代价的一个首要因素,主要是因为通信代价通常是数据传输量的函数,便于估算.为了衡量通信代价,我们给出了如下的估算公式:

分布式数据库查询优化的参考属性评定
有关论文范文主题研究: 关于数据库的论文范文文献 大学生适用: 学术论文、学院论文
相关参考文献下载数量: 11 写作解决问题: 怎么写
毕业论文开题报告: 标准论文格式、论文前言 职称论文适用: 论文发表、中级职称
所属大学生专业类别: 怎么写 论文题目推荐度: 优秀选题

TC(X)等于C0+X*C1

TC代表通信代价,X代表数据传输量,C0代表两节点之间初始化以此传输所花费的时间,它近似一个常数,C1为单位数据的传输代价.

2基于半连接查询优化策略

分布式数据库中提出了半连接的方法.基于半连接的优化方法基本原理就是尽量在传输中只传输参与连接的数据,从而降低不必要的通信开销.

设A,B是两个关系,α、β分别是A、B上两个属性.

定义:

(1)A、B半连接表示为ASjB.(Sj是semi-join缩写).

(2)Size(β)表示β属性的长度,Count(A)表示A元素数,Val(α[B])表示属性α在关系B上不同值个数.

现在要做关系A与B上的连接操作,连接条件为α等于β.A,B分别存放在M,N两个节点上:

(1)在N节点做投影操作πα(B)

(2)将πα(B)传送给节点M,通信代价为:C0+C1*Size(β)*Val(β[N])

(3)节点M计算半连接,结果为A'

(4)将计算结果送往N.通信代价:C0+C1*Size(A)*Count(A')

(5)在节点N执行连接操作.

仅考虑通信代价,采用上述半连接查询的总代价为:

Csj等于2C0+C1*(Size(β)*Val(β[B])+Size(A)*Count(A’))(1)

若不采用半连接,直接把A送到N节点,通信代价为:

C等于C0+C1*Size(A)*Count(A)(2)

当Csj

3基于站点依赖算法的查询优化

半连接查询优化方法并不总是好的,因为半连接会导致通信次数的增加.因此有时候我们也就需要基于直接连接的方案.

定义:如果两个片段关系Ri和Rj满足在属性a上的等值连接为空集,且Ri和Rj在不同站点上,则称Ri和Rj在属性a上站点依赖.

条件:Place_Dependency(Q,P,S)

其中Q为查询,R等于{R1,R2,,Rn}为查询Q引用的一组关系,P为站点依赖信息.S是一个连接操作可以无数据传送执行的最大关系集合.

算法初始化时,S是空集.R等于{R1,R2,,Rn}.算法结束时S等于R,Q可以无数据传送执行.下面是详细的算法步骤:

(1)S等于ф,R等于{R1,R2,,Rn}

(2)如果能找到Ri和Rj在属性a上站点依赖,且在属性组A上也站点依赖,且A包含a,则将Ri和Rj放入S中.如果找不到,算法终止.

(3)对于任意关系Rk,若它在R中而不在S中,S中存在关系Rx,它与Rk在属性B上有站点依赖关系,且Rx和Rk在属性B上站点依赖Q中或可由Q中导出,则可把Rk插入S中.此步骤多次循环,直至不能再向S中添加关系为止.

(4)判断S是否等于R,若相等则说明可以在不发生站点数据传送的情况下执行连接操作.

4哈希划分算法

哈希划分算法的基本思想是在某个属性或者属性集上应用一定的哈希函数获得元组的哈希值,将相同哈希值的元组放在同一个站点上.

Site等于hash(Relation.attribute)

显然,不同的关系经过相同的哈希函数划分后,在连接时保持站点依赖.

现在考察三个关系R1,R2,R3的连接,检测设这三个关系存放在两个站点上,且所有关系没有被复制.讨论分两种情况:

(1)在同一属性a上的连接,R1,R2,R3在属性a上以同一哈希函数进行划分,因此满足站点依赖,两个站点在属性a上的连接操作可以并行执行.此过程除了最后合并结果需要发生微量通信,其他过程几乎不发生通信.

(2)在不同属性上的连接.比如R1和R2在属性a上连接,然后将中间结果R与R3在属性b上进行连接.这时,应该是R1和R2在a上应用同样的哈希函数进行划分,而在R3应用不同哈希函数划分.

R1和R2在属性a上连接依然满足站点依赖,而将中间结果与R3在属性b上的连接需要对中间结果R进行重哈希划分,以满足在属性b上和R3有相同的哈希划分.这样做需要花费相当大的通信代价.DeWitt等人关于在Tera(1ata机器上对两个关系的三组数据得出的实验结果表明,进行重划分并没有提高查询效率,因此应该尽量避免进行重划分.

5结束语

查询优化算法是分布式数据库研究的主要问题之一,本文主要通过分析了几种典型的分布式查询优化算法,给出了影响分布式查询优化的主要影响因素.由于分布式数据库建立环境复杂,技术内容丰富,对查询优化的许多内容需要进一步研究和解决.