一种基于bloom-filters的半连接查询优化算法

孙中利，戴玉刚，刘战东

（西北民族大学 中国民族信息技术研究院，甘肃 兰州 730300）

在进行分布式数据库查询优化时，人们关注的焦点是如何选择能够得到提高查询效率、缩减传输费用的查询执行策略[1]。查询执行代价优化的目标是使查询执行所用的系统资源尽量的少，从而降低系统开销[2]。但查询优化本质上是NP完全问题，所谓最佳方案是很难找到，查询优化只是寻找相对较优的操作执行步骤而已[3]。

基于半连接查询，已有多种算法被用于处理海量信息查询和复杂查询领域[4]。比较著名的有AHY，PERF，W等3种算法[5]。Tseng和Chen提出基于哈希-半连接的优化算法[6]，这种算法通过用哈希-半连接操作替换部分半连接操作，来得到更有效的查询执行策略。文献[7]中应用了2-way半连接，2-way半连接同时执行了R∝S和S∝R，使得关系R和S同时被缩减，这种方法适用于装配站点为第三站点的情况（除了R、S所在站点）。本文在上述方法的基础上，以传输费用最小为目的，提出一种基于bloom-filters新的半连接查询优化算法。

1 算法理论基础

1.1 半连接及相关定义

分布式数据库环境下，关系R、S、T分别存在于站点1、站点2、站点3上。在介绍基于多关系半连接的查询优化算法前，首先给出以下定义。

定义 1：对于关系 R，S，T，本文定义如下：

N（R）：关系R中元组的个数；

L（R，a）：关系 R中属性 a定义的长度；

中间连接结果的数据信息称作中间计算结果，记作CRT；把真实的连接结果记作RRT；

Πa（R）：关系R中属性a上不同值组成的集合；

Card（SR）：关系S中与关系R连接时传输的数据代价；

定义2：两个关系在单个属性上进行半连接及连接的定义如下：

设关系R的属性a及关系S的属性b是公共属性，并在这个公共属性上进行连接，定义R半连接S为：R∝a=bS；定义S 半连接 R 为：S∝A=BR，其含义分别是：R∝a=bS=∏b（R∞a=bS）=R∞a=b（∏b（S））

由上可知，半连接操作具有不对称性，采用半连接方法表示连接操作为：

1.2 Bloom-filters原理

Bloom-filters是一种基于随机数的数据结构，它支持对成员用较少的空间来存储，却能得到较高的效率查询。Bloomfilters原理[8]如下：首先建立一个容量为m的Bit Array结构（Bit Array的大小和keyword的数量决定了误判率），将集合中的每个keyword通过k个hash函数计算出k个数字，将Bit Array中对应的位置为1。简单的说就是将每个keyword对应到Bit Array中的k个位置上，如图1所示。

图1 Bloom-filters原理图Fig.1 Bloom-filters schematic

当需要快速查找某个keyword时，只要将其通过同样的k个hash函数运算，然后映射到Bit Array中的对应位，如果Bit Array中的对应位全部是1，那么说明该keyword匹配成功。Bloom-filters是一个集合的有损编码，所以它不是一种“保险”的方案，存在一定的误判率。

在标准的bloom-filters中，对于使用k个哈希函数，向m位长的bloom-filters中装入n个元素后，位向量中的某一仍然为0的概率p为：

则错误率fp为：

错误率fp最小的条件为：p=0.5，即=0.5，因此有

由此可知，bloom filter的参数m，n的比值是已知的，为了保证错误率最小，则要求，此时BFV中某一位为零的概率为 0.5，将式（3）带入式（2）得：

由公式（3）和公式（4）可知，当m和n的比值越大则要求哈希函数个数越大，并且其错误率越小。

2 算法的思想和实现

对查询q，如果最大限度地减少R的大小，则该半连接序列完全缩减关系R[10]。一个半连接序列，如果它对所有的数据库状态都完全缩减数据库中的每一个关系，则该半连接序列是一个完全缩减器。虽然半连接的能力不足以解决任何关系查询，但作为一种预处理手段，可以经常减少查询处理的费用，尤其是在分布式数据库中。

表1，表2，表3是关系R、S、T和它们的站点分布情况（其中 C2，C4，C5分别表示关系 R，S，T的非连接属性， 关系R在站点1，关系 T在站点 2，关系 S在站点 3），由关系 R、S、T可以得到真实的连接结果表如表4，表5所示。

表1 关系RTab.1 relation R

表2 关系STab.2 relation S

表3 关系TTab.3 relation T

表4 关系RTRTab.4 relation RTR

表5 关系RTSTab.5 relation RTS

计算结果表CTR，CTS用有三列属性的表来表示，其中第一列属性为连接属性C1或者C3，属性值是T∝C1R或者T∝C3S；第二、三列属性分别用来描述关系T∝C1R或者T∝C3R的结果信息，第二列记录关系T中相应属性值的个数，第三列记录关系R或者S中相应属性值的个数，中间计算结果如表6和表7所示。

表6 计算结果表CTRTab.6 relation CTR

表7 计算结果表CTSTab.7 relation CTS

由表6和表7可以得到关系T中属性C1、C3的取值。T的连接属性可能取值如表8所示，将Vc1c3与关系T比较得到的值如表9所示。

表8 可能取值表Vclc3

表9 实际取值表Rclc3Tab.9 Rclc3

由VC1C3，RC1C3可知，C1的属性值 2，C3的属性值 c， 不参与连接。可以从计算结果表CTR，CTS中删除，所以修改计算结果表 CTR，CTS可以缩减如表10，表11所示。

表10 缩减后的CTRTab.10 CTR

表11 缩减后的CTSTab.11 CTS

将修改后的计算结果表CTR和表CTS分别传到关系R、S和关系R、T所在站点，计算各表最终结果有用的数据大小，从而确定传输费用最小的执行计划。

这种查询优化算法的关键是如何有效地获得计算结果表CTR，如果建立CTR的代价太高，那么该算法对传输费用的减少是无益的，所以引入bloom-filters来减少计算结果表的代价。下面介绍建立CTR的步骤[11]：1）以属性C1为关键字，对关系T、R应用哈希函数，建立相应的bloom-filters；2）关系 T、R相互发送bloom-filters，过滤掉对最终结果无用的元组；3）取得过滤后的C1的不同属性值个数，并在关系T、R间交换；4）这时在站点1和站点2都可以得到计算结果表CTR；

查询优化算法步骤（假设在各站点已通过上面的方法得到相应计算结果表）：5）在中间连接站点，根据计算结果表得到中间关系的连接属性可能取值表，与过滤后的关系作比较，得到关系的连接属性实际取值表；6）如果连接属性取值有变化，则转向4）修改相应的计算结果表，如果连接属性取值没有变化则继续下一步；7）判断是否所有的中间连接关系都得到连接属性实际取值表，是则执行下一步，否则转向5）；8）根据计算结果表和关系的宽度计算传输费用，得到传输代价最小的执行计划；如果有多个传输代价最小的的执行计划，则可以并行执行这些计划，设置一个浮动动参数X，当|Card（other）-Card（）min|＜X 时，这些计划都可以并行执行。

在上面的例子中假设 L（R，C1）=L（S，C3）=10，L（R，C2）=1 000，L（S，C4）=500，L（T，C5）=100，Card（SR）表示关系 S 中与关系 R 连接时传输的代价，Card（RS）、Card（TR）、Card（RT）的定义同上。通过计算可以得出：

所以TR和TS的传输费用最小，将TR，TS添加到执行计划表中，再根据计算结果表CST，CRT计算中间连接结果：

通过计算结果可知S（TR）的传输费用最小，得到执行计划为：先将过滤后的关系T传到站点2，与过滤后的关系R连接，然后将过滤后的S传到站点1，与TR连接后的结果连接得到最终结果。

3 结束语

本文提出的基于bloom-filters的半连接优化策略，可以大量地筛选掉无用的元组，新的查询优化算法可靠性强；它根据计算结果表得到中间连接结果的大小，这种方法的准确性比估算连接结果高，能较准确地做出下一步的连接决定；所以新的查询优化算法能有效地得到连接操作的执行计划，并能减少传输费用。

[1]邓曦，卢正鼎，张巍，等.多数据库系统查询优化算法的研究[J].小型微型计算机系统，2004，25（3）:452－454.DENG Xi， LU Zheng-ding， ZHANG Wei，et al.Multidatabase query optimization algorithm for the system[J].Mini-micro Systems ， 2004，25（3）:452－454.

[2]贾焰，王志英，韩伟红，等.分布式数据库技术[M].北京:国防工业出版社，2001.

[3]邵佩英.分布式数据库系统及其应用[M].2版.北京:科学出版社，2005.

[4]于秀霞，宋雅娟.分布式数据库半连接查询优化算法的研究[J].长春理工大学学报，2006，29（4）:69－72.YU Xiu-xia，SONG Ya-juan.Semijoin distributed database query optimization algorithm [J].Journal of Changchun University of Sicience and Technology， 2006，29（4）:69－72.

[5]Apers P M G，Hevner A R.Optimization algorithfns for distributedqueries[J].IEEE Trans.on Soft.Eng，1983，9（1）:57－68.

[6]Tseng J，Chen A P.Improving distributed query processing by hash-semijoins[J].Journal of Information Science and Engineering，1992，8（4）:525－540.

[7]Roussopoulos N，Kang H.A pipeline n-way join algorithm based on the 2-way semi-join program [J].IEEE Trans.on Knowledge and Data Engineering，1991，3（4）:486－495.

[8]Broder A，Mitzenmacher M.Network applications of bloom filters:a survey[J].Internet Mathematics， 2005，1（4）:485－509.

[9]Mitzenmacher M.Compressed bloom filters[J].IEEE/ACM transactions on networking， 2002，10（5）:604－612.

[10]陈建荣，严隽永，叶天荣.分布式数据库设计导论[M].北京:清华大学出版社，1992.

[11]石小艳.分布式数据库查询优化机制研究[D].东营:中国石油大学，2007.