一種基于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.