一種基于bloom-filters的半連接查詢優(yōu)化算法

孫中利，戴玉剛，劉戰(zhàn)東

（西北民族大學(xué) 中國民族信息技術(shù)研究院，甘肅 蘭州 730300）

在進(jìn)行分布式數(shù)據(jù)庫查詢優(yōu)化時(shí)，人們關(guān)注的焦點(diǎn)是如何選擇能夠得到提高查詢效率、縮減傳輸費(fèi)用的查詢執(zhí)行策略[1]。查詢執(zhí)行代價(jià)優(yōu)化的目標(biāo)是使查詢執(zhí)行所用的系統(tǒng)資源盡量的少，從而降低系統(tǒng)開銷[2]。但查詢優(yōu)化本質(zhì)上是NP完全問題，所謂最佳方案是很難找到，查詢優(yōu)化只是尋找相對較優(yōu)的操作執(zhí)行步驟而已[3]。

基于半連接查詢，已有多種算法被用于處理海量信息查詢和復(fù)雜查詢領(lǐng)域[4]。比較著名的有AHY，PERF，W等3種算法[5]。Tseng和Chen提出基于哈希-半連接的優(yōu)化算法[6]，這種算法通過用哈希-半連接操作替換部分半連接操作，來得到更有效的查詢執(zhí)行策略。文獻(xiàn)[7]中應(yīng)用了2-way半連接，2-way半連接同時(shí)執(zhí)行了R∝S和S∝R，使得關(guān)系R和S同時(shí)被縮減，這種方法適用于裝配站點(diǎn)為第三站點(diǎn)的情況（除了R、S所在站點(diǎn)）。本文在上述方法的基礎(chǔ)上，以傳輸費(fèi)用最小為目的，提出一種基于bloom-filters新的半連接查詢優(yōu)化算法。

1 算法理論基礎(chǔ)

1.1 半連接及相關(guān)定義

分布式數(shù)據(jù)庫環(huán)境下，關(guān)系R、S、T分別存在于站點(diǎn)1、站點(diǎn)2、站點(diǎn)3上。在介紹基于多關(guān)系半連接的查詢優(yōu)化算法前，首先給出以下定義。

定義 1：對于關(guān)系 R，S，T，本文定義如下：

N（R）：關(guān)系R中元組的個(gè)數(shù)；

L（R，a）：關(guān)系 R中屬性 a定義的長度；

中間連接結(jié)果的數(shù)據(jù)信息稱作中間計(jì)算結(jié)果，記作CRT；把真實(shí)的連接結(jié)果記作RRT；

Πa（R）：關(guān)系R中屬性a上不同值組成的集合；

Card（SR）：關(guān)系S中與關(guān)系R連接時(shí)傳輸?shù)臄?shù)據(jù)代價(jià)；

定義2：兩個(gè)關(guān)系在單個(gè)屬性上進(jìn)行半連接及連接的定義如下：

設(shè)關(guān)系R的屬性a及關(guān)系S的屬性b是公共屬性，并在這個(gè)公共屬性上進(jìn)行連接，定義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是一種基于隨機(jī)數(shù)的數(shù)據(jù)結(jié)構(gòu)，它支持對成員用較少的空間來存儲，卻能得到較高的效率查詢。Bloomfilters原理[8]如下：首先建立一個(gè)容量為m的Bit Array結(jié)構(gòu)（Bit Array的大小和keyword的數(shù)量決定了誤判率），將集合中的每個(gè)keyword通過k個(gè)hash函數(shù)計(jì)算出k個(gè)數(shù)字，將Bit Array中對應(yīng)的位置為1。簡單的說就是將每個(gè)keyword對應(yīng)到Bit Array中的k個(gè)位置上，如圖1所示。

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

當(dāng)需要快速查找某個(gè)keyword時(shí)，只要將其通過同樣的k個(gè)hash函數(shù)運(yùn)算，然后映射到Bit Array中的對應(yīng)位，如果Bit Array中的對應(yīng)位全部是1，那么說明該keyword匹配成功。Bloom-filters是一個(gè)集合的有損編碼，所以它不是一種“保險(xiǎn)”的方案，存在一定的誤判率。

在標(biāo)準(zhǔn)的bloom-filters中，對于使用k個(gè)哈希函數(shù)，向m位長的bloom-filters中裝入n個(gè)元素后，位向量中的某一仍然為0的概率p為：

則錯(cuò)誤率fp為：

錯(cuò)誤率fp最小的條件為：p=0.5，即=0.5，因此有

由此可知，bloom filter的參數(shù)m，n的比值是已知的，為了保證錯(cuò)誤率最小，則要求，此時(shí)BFV中某一位為零的概率為 0.5，將式（3）帶入式（2）得：

由公式（3）和公式（4）可知，當(dāng)m和n的比值越大則要求哈希函數(shù)個(gè)數(shù)越大，并且其錯(cuò)誤率越小。

2 算法的思想和實(shí)現(xiàn)

對查詢q，如果最大限度地減少R的大小，則該半連接序列完全縮減關(guān)系R[10]。一個(gè)半連接序列，如果它對所有的數(shù)據(jù)庫狀態(tài)都完全縮減數(shù)據(jù)庫中的每一個(gè)關(guān)系，則該半連接序列是一個(gè)完全縮減器。雖然半連接的能力不足以解決任何關(guān)系查詢，但作為一種預(yù)處理手段，可以經(jīng)常減少查詢處理的費(fèi)用，尤其是在分布式數(shù)據(jù)庫中。

表1，表2，表3是關(guān)系R、S、T和它們的站點(diǎn)分布情況（其中 C2，C4，C5分別表示關(guān)系 R，S，T的非連接屬性， 關(guān)系R在站點(diǎn)1，關(guān)系 T在站點(diǎn) 2，關(guān)系 S在站點(diǎn) 3），由關(guān)系 R、S、T可以得到真實(shí)的連接結(jié)果表如表4，表5所示。

表1 關(guān)系RTab.1 relation R

表2 關(guān)系STab.2 relation S

表3 關(guān)系TTab.3 relation T

表4 關(guān)系RTRTab.4 relation RTR

表5 關(guān)系RTSTab.5 relation RTS

計(jì)算結(jié)果表CTR，CTS用有三列屬性的表來表示，其中第一列屬性為連接屬性C1或者C3，屬性值是T∝C1R或者T∝C3S；第二、三列屬性分別用來描述關(guān)系T∝C1R或者T∝C3R的結(jié)果信息，第二列記錄關(guān)系T中相應(yīng)屬性值的個(gè)數(shù)，第三列記錄關(guān)系R或者S中相應(yīng)屬性值的個(gè)數(shù)，中間計(jì)算結(jié)果如表6和表7所示。

表6 計(jì)算結(jié)果表CTRTab.6 relation CTR

表7 計(jì)算結(jié)果表CTSTab.7 relation CTS

由表6和表7可以得到關(guān)系T中屬性C1、C3的取值。T的連接屬性可能取值如表8所示，將Vc1c3與關(guān)系T比較得到的值如表9所示。

表8 可能取值表Vclc3

表9 實(shí)際取值表Rclc3Tab.9 Rclc3

由VC1C3，RC1C3可知，C1的屬性值 2，C3的屬性值 c， 不參與連接。可以從計(jì)算結(jié)果表CTR，CTS中刪除，所以修改計(jì)算結(jié)果表 CTR，CTS可以縮減如表10，表11所示。

表10 縮減后的CTRTab.10 CTR

表11 縮減后的CTSTab.11 CTS

將修改后的計(jì)算結(jié)果表CTR和表CTS分別傳到關(guān)系R、S和關(guān)系R、T所在站點(diǎn)，計(jì)算各表最終結(jié)果有用的數(shù)據(jù)大小，從而確定傳輸費(fèi)用最小的執(zhí)行計(jì)劃。

這種查詢優(yōu)化算法的關(guān)鍵是如何有效地獲得計(jì)算結(jié)果表CTR，如果建立CTR的代價(jià)太高，那么該算法對傳輸費(fèi)用的減少是無益的，所以引入bloom-filters來減少計(jì)算結(jié)果表的代價(jià)。下面介紹建立CTR的步驟[11]：1）以屬性C1為關(guān)鍵字，對關(guān)系T、R應(yīng)用哈希函數(shù)，建立相應(yīng)的bloom-filters；2）關(guān)系 T、R相互發(fā)送bloom-filters，過濾掉對最終結(jié)果無用的元組；3）取得過濾后的C1的不同屬性值個(gè)數(shù)，并在關(guān)系T、R間交換；4）這時(shí)在站點(diǎn)1和站點(diǎn)2都可以得到計(jì)算結(jié)果表CTR；

查詢優(yōu)化算法步驟（假設(shè)在各站點(diǎn)已通過上面的方法得到相應(yīng)計(jì)算結(jié)果表）：5）在中間連接站點(diǎn)，根據(jù)計(jì)算結(jié)果表得到中間關(guān)系的連接屬性可能取值表，與過濾后的關(guān)系作比較，得到關(guān)系的連接屬性實(shí)際取值表；6）如果連接屬性取值有變化，則轉(zhuǎn)向4）修改相應(yīng)的計(jì)算結(jié)果表，如果連接屬性取值沒有變化則繼續(xù)下一步；7）判斷是否所有的中間連接關(guān)系都得到連接屬性實(shí)際取值表，是則執(zhí)行下一步，否則轉(zhuǎn)向5）；8）根據(jù)計(jì)算結(jié)果表和關(guān)系的寬度計(jì)算傳輸費(fèi)用，得到傳輸代價(jià)最小的執(zhí)行計(jì)劃；如果有多個(gè)傳輸代價(jià)最小的的執(zhí)行計(jì)劃，則可以并行執(zhí)行這些計(jì)劃，設(shè)置一個(gè)浮動(dòng)動(dòng)參數(shù)X，當(dāng)|Card（other）-Card（）min|＜X 時(shí)，這些計(jì)劃都可以并行執(zhí)行。

在上面的例子中假設(shè) L（R，C1）=L（S，C3）=10，L（R，C2）=1 000，L（S，C4）=500，L（T，C5）=100，Card（SR）表示關(guān)系 S 中與關(guān)系 R 連接時(shí)傳輸?shù)拇鷥r(jià)，Card（RS）、Card（TR）、Card（RT）的定義同上。通過計(jì)算可以得出：

所以TR和TS的傳輸費(fèi)用最小，將TR，TS添加到執(zhí)行計(jì)劃表中，再根據(jù)計(jì)算結(jié)果表CST，CRT計(jì)算中間連接結(jié)果：

通過計(jì)算結(jié)果可知S（TR）的傳輸費(fèi)用最小，得到執(zhí)行計(jì)劃為：先將過濾后的關(guān)系T傳到站點(diǎn)2，與過濾后的關(guān)系R連接，然后將過濾后的S傳到站點(diǎn)1，與TR連接后的結(jié)果連接得到最終結(jié)果。

3 結(jié)束語

本文提出的基于bloom-filters的半連接優(yōu)化策略，可以大量地篩選掉無用的元組，新的查詢優(yōu)化算法可靠性強(qiáng)；它根據(jù)計(jì)算結(jié)果表得到中間連接結(jié)果的大小，這種方法的準(zhǔn)確性比估算連接結(jié)果高，能較準(zhǔn)確地做出下一步的連接決定；所以新的查詢優(yōu)化算法能有效地得到連接操作的執(zhí)行計(jì)劃，并能減少傳輸費(fèi)用。

[1]鄧曦，盧正鼎，張巍，等.多數(shù)據(jù)庫系統(tǒng)查詢優(yōu)化算法的研究[J].小型微型計(jì)算機(jī)系統(tǒng)，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]賈焰，王志英，韓偉紅，等.分布式數(shù)據(jù)庫技術(shù)[M].北京:國防工業(yè)出版社，2001.

[3]邵佩英.分布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用[M].2版.北京:科學(xué)出版社，2005.

[4]于秀霞，宋雅娟.分布式數(shù)據(jù)庫半連接查詢優(yōu)化算法的研究[J].長春理工大學(xué)學(xué)報(bào)，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]陳建榮，嚴(yán)雋永，葉天榮.分布式數(shù)據(jù)庫設(shè)計(jì)導(dǎo)論[M].北京:清華大學(xué)出版社，1992.

[11]石小艷.分布式數(shù)據(jù)庫查詢優(yōu)化機(jī)制研究[D].東營:中國石油大學(xué)，2007.