基于分布式数据库的半连接查询计划选择算法

夏斌

摘 要 为了提高分布式数据库系统的查询效率，采用新的代价模型在执行半连接计划之前评估和传输执行与优化代价。由于剔除与连接无关的数据，有效减少连接操作关系中的无用数据，选择执行代价更小的执行方法。首先对分布式数据库查询执行代价模型进行分析，然后对半连接中的连接运算方式、连接关系的传输方法和执行场地等问题进行研究，并计算其评估方法的执行代价，给出一种可行的查询计划选择算法，最终确定执行的场地、连接的方法和传输方法。

【关键词】半连接查询 分布式数据库 查询优化 代价模型

基于直接连接算法的查询优化处理，针对执行场地的不同，针对连接方式的不同，以及针对传输方法的不同的查询优化已有不少研究。而基于半连接算法的查询优化处理在这三个方面的综合评估和代价分析研究还较少。因此本文重点研究基于半连接的实现方法，综合考虑局部代价和传输代价的相对费用，计算所有评估方法的执行代价，选择其中执行代价较小的执行方法，最终确定执行的场地、连接的方法和传输的方法。

1 分布式查询代价模型

分布式数据库的查询执行代价中主要由以下3部分组成：

（1）访问辅助存储器的代价（简称I/O代价）；

（2）计算代价（简称CPU代价）；

（3）传输代价。分布式数据库中，传输代价是总代价的重要组成部分。

1.1 CPU代价

由于在实际运算环境中，传输代价与I/O代价远远超过连接操作的代价，在具体计算中可忽略不计。

1.2 I/O代价

目前，使用较多的辅助存储器主要是磁盘，其一次访问的所需的代价可表示为

CIO=D0+D1*X

其中：X为存取数据的大小；D0为与X无关的I/O代价，包括寻道时间和等待时间；D1为单位数据的传输时间。

一般地D0>>D1*X，故CIO≈D0，I/0代价≈I/0次数*D0。

由于不同算法在I/O代价上没有明显的差异，因此不作深究，在计算中用常数Ti替代。

1.3 传输代价

分布式数据库系统中的传输代价与网络的类型有关，通常可以近似地表示为

Cconvey（X）=C0+C1*X

其中：X为传输数据的大小；C0为传输一次数据所必需的初始代价；C1为单位数据的传输代价（代价系数）；C0、C1一般随网络的类型而变化，对于某一具体的网络，其值为常数；Cconvey（X）一下简称Cc（X）。

2 半连接查询算法

基于半连接（Semi-Join）算法优化查询，其基本思想是经过半连接操作减少操作关系，从而减少站点间数据的传输量。

2.1 半连接算法的关系代数

假定站点1上的关系A与站点2上的关系B在属性A.x=B.x上进行等值连接，采用半连接方法表示这一操作为：

A∞A.x=B.xB=（A∝A.x=B.xB） ∞A.x=B.xB

其中，∝符号为半连接操作符。

一次完整的半连接方法的连接操作过程关系代数可表示为

A∞A.x=B.xB=（A∞A.x=B.x（πB.x（B））） ∞B （1）

其中，∝代表半连接操作，∞代表连接操作，π代表投影操作。

2.2 半连接算法的连接过程

针对公式（1），半连接的连接过程可分为五步。

（1）在站点2上将B在属性B.x上进行投影获得B'=πB.x（B）；

（2）将B'传送到站点1；

（3）在站点1上计算A'=A∞B'的半连接结果；

（4）将站点1上的A'与站点2上的B传送到发起查询请求的站点3上；

（5）在站点3上进行连接操作。

2.3 半连接算法代价估计

查询发起请求站点3有3种情况：设站点3=站点1的Site（A）；设站点3=站点2的Site（B），等价于Site（A），不予讨论；或者其他场地Site（other）。根据查询地点的不同，则传送的数据量和传输费用会不同。

为了准确描述代价的计算，作如下定义：

（1）一个关系A的元组数，表示为size（A）；

（2）每个属性xi的长度表示为length（A.xi），并将所有属性大小的总和，即一个元组的大小表示为length（A）。

3 半连接查询优化

由于代价模型已知，因此在查询开始前如果进行查询计划的选择，可以保证连接代价的优化。

3.1 当查询发起站点包含其中一个表时

4 结束语

本文研究了分布式数据库中以总代价最小为半连接查询优化准侧，着重考虑了传输代价，分析了半连接算法实现过程中影响执行总代价的三方面因素：连接运算的方法、连接关系的传输方法、执行场地，给出了半连接算法可能的实施方案并评估了不同条件下各种方案的执行代价，并给出了一种可行的优化算法以实现查询计划方法。

参考文献

[1]Shao Peiying.Distributed database system and its application[M].Science Press，2005

[2]Bassiliades N，Vlahavas I.Hierarchical query execution in a parallel object-oriented database system[J].Parallel Computing，2000，22（07）：1017-1048.

[3Li Xuefeng.The use of distributed hash table to build a copy of the checkpoint[J].small and micro computer systems，2011，32（08）：1548-1552.

作者單位

南京航空航天大学 江苏省南京市 210000