茅瀟瀟,段惠超,高明

(華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院,上海200062)

OceanBase中基于布隆過濾器的連接算法

茅瀟瀟,段惠超,高明

(華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院,上海200062)

在大數(shù)據(jù)時代,“去IOE”運動的推進以及“雙11”等活動的興起對分布式數(shù)據(jù)庫系統(tǒng)提出了更高的要求.OceanBase是阿里巴巴集團自主研發(fā)的開源分布式數(shù)據(jù)庫,支持海量數(shù)據(jù)跨行跨表事務(wù),但是對復(fù)雜查詢的處理性能仍有待提高,其中連接操作帶來的網(wǎng)絡(luò)傳輸嚴重影響了數(shù)據(jù)庫的性能.本文提出了一種基于布隆過濾器的連接算法,通過構(gòu)建布隆過濾器對右表數(shù)據(jù)進行過濾,減少了不必要的數(shù)據(jù)傳輸開銷,降低了數(shù)據(jù)處理帶來的內(nèi)存資源的消耗.本文在OceanBase上實現(xiàn)了該算法,并通過實驗證明,該算法極大提高了連接操作的效率.

OceanBase;連接操作;布隆過濾器

0 引言

為了應(yīng)對數(shù)據(jù)規(guī)模和業(yè)務(wù)規(guī)模的爆發(fā)式增長,以阿里巴巴公司為代表的互聯(lián)網(wǎng)行業(yè)開始推進“去IOE”運動,如何選擇數(shù)據(jù)庫產(chǎn)品至關(guān)重要.近幾年來,隨著“雙11”活動的發(fā)展、“秒殺”應(yīng)用的興起、以及云數(shù)據(jù)服務(wù)的推廣,更是對目前開源的分布式數(shù)據(jù)庫系統(tǒng)提出了挑戰(zhàn).為此,阿里巴巴集團自主研發(fā)了支持海量數(shù)據(jù)跨行跨表事務(wù)的分布式數(shù)據(jù)庫OceanBase[1],以低成本、高可擴展性、高可用性和高可靠性著稱,已經(jīng)支持了阿里巴巴集團包括支付寶在內(nèi)的許多業(yè)務(wù).

但是作為主要面向OLTP應(yīng)用的數(shù)據(jù)庫系統(tǒng),OceanBase對于復(fù)雜查詢的處理性能并不高.當數(shù)據(jù)量非常龐大時,連接操作帶來的大量數(shù)據(jù)交互會產(chǎn)生巨大的網(wǎng)絡(luò)傳輸開銷,嚴重影響數(shù)據(jù)庫的性能.因此,對于連接操作的優(yōu)化,就成為OceanBase中查詢優(yōu)化的重點.

迄今為止,大量的研究學(xué)者對分布式數(shù)據(jù)庫中連接操作的查詢優(yōu)化進行了許多研究工作,￠憾的是,分布式查詢優(yōu)化技術(shù)還很不成熟,經(jīng)典的理論不是只局限于某一方面,就是太過復(fù)雜無法應(yīng)用到實際中.OceanBase中采用的是經(jīng)典的排序歸并連接算法,但是它也存在著一些缺陷.假設(shè),我們要對關(guān)系R和關(guān)系S進行連接操作,當我們在存儲關(guān)系R數(shù)據(jù)的節(jié)點上進行操作時,傳統(tǒng)的排序歸并連接算法要求關(guān)系S中的所有元組(或者至少為全部元組的一個垂直子集)被發(fā)送到該節(jié)點上進行計算.但是在實際的連接計算中,我們只需要關(guān)系R和關(guān)系S中可能產(chǎn)生連接結(jié)果的元組,不符合連接條件的數(shù)據(jù)傳輸浪費了不必要的網(wǎng)絡(luò)資源,而且大量數(shù)據(jù)的排序操作需要較大的內(nèi)存資源.因此,只要擁有足夠的信息來判斷關(guān)系S中各條元組是否符合連接條件,通過這些信息對關(guān)系S中的全部元組進行過濾,僅僅把這個符合條件的子集發(fā)送給計算節(jié)點,那么網(wǎng)絡(luò)通訊代價將會大大減少,在過濾后的數(shù)據(jù)集上進行排序操作所消耗的內(nèi)存資源也會下降.為此,布隆過濾器是一個理想的選擇.

針對這一問題,本文在OceanBase中實現(xiàn)了一種基于布隆過濾器的連接優(yōu)化算法.該算法并不將右表的全部數(shù)據(jù)發(fā)送到計算節(jié)點,而是使用布隆過濾器對右表數(shù)據(jù)進行過濾,再對過濾后的數(shù)據(jù)進行排序歸并連接.本文的貢獻點如下:

(1)在開源的分布式數(shù)據(jù)庫OceanBase上實現(xiàn)了該算法;

(2)通過一系列測試證明了該算法的高效性;

(3)提供了一種在OceanBase中提高連接操作性能的思路.

本文第1節(jié)介紹了三種傳統(tǒng)的連接算法及其在分布式數(shù)據(jù)庫中的優(yōu)化技術(shù);第2節(jié)形式化定義了該算法所解決的問題,提出了算法的整體設(shè)計并對性能進行了分析;第3節(jié)介紹了該算法在開源數(shù)據(jù)庫OceanBase上的詳細實現(xiàn);第4節(jié)通過一系列實驗驗證了該算法的性能;第5節(jié)總結(jié)了論文所做的工作并闡述了未來研究的方向.

1 相關(guān)工作

傳統(tǒng)的連接算法主要有三種:嵌套循環(huán)連接算法、排序歸并連接算法和哈希連接算法,這三種算法有著各自的特點和使用場景.隨著分布式數(shù)據(jù)庫的產(chǎn)生和發(fā)展,對這三種傳統(tǒng)連接算法在分布式數(shù)據(jù)庫中的應(yīng)用優(yōu)化技術(shù)也被逐漸提出.下面簡要介紹一下這三種連接算法及優(yōu)化技術(shù).

1.1 嵌套循環(huán)連接算法

1977年,Blasgen提出了嵌套循環(huán)連接算法[2].嵌套循環(huán)連接算法是一種較簡單、穩(wěn)定的連接算法.它使用兩層嵌套循環(huán),對于被驅(qū)動表的每一行記錄,驅(qū)動表的所有記錄都會與其進行比較,最終得到連接結(jié)果.該算法適用于兩表的數(shù)據(jù)量較小并且內(nèi)存可以存放的情況,但如果數(shù)據(jù)量超過內(nèi)存大小,則驅(qū)動表就需要進行多次掃描,掃描的次數(shù)為被驅(qū)動表大小與可用內(nèi)存大小的比值.因此當兩表的數(shù)據(jù)量較大時,嵌套循環(huán)連接算法的效率較為低下.

1.2 排序歸并連接算法

針對嵌套循環(huán)連接算法的這一缺點,Blasgen還提出了排序歸并連接算法[2].在排序歸并連接算法中,兩表先根據(jù)連接列進行排序,然后進行順序掃描,在掃描的過程中將滿足連接條件的元組合并得到最終結(jié)果.該算法適用于大數(shù)據(jù)量的情況,曾經(jīng)被認為是最好的連接算法[3],但是由于需要對兩表進行排序,排序過程中數(shù)據(jù)對比操作時間較長,內(nèi)存資源消耗也較大.隨著哈希連接算法的提出,證明排序歸并連接算法的優(yōu)勢不一定成立.

1.3 哈希連接算法

第一個以哈希函數(shù)為基礎(chǔ)的連接算法在1979年被E.Babb提出[4].簡單的哈希連接算法的流程如下:首先選擇一張小表作為驅(qū)動表,對小表的連接列使用特定的哈希函數(shù)進行計算,并在內(nèi)存里產(chǎn)生一張哈希表.然后,使用相同的哈希函數(shù)對大表(即被驅(qū)動表)的連接列進行計算,將計算的結(jié)果在哈希表中進行探測.如果探測成功,則一條新的記錄將被創(chuàng)建.在大多數(shù)情況下,哈希連接算法比其他連接算法(如排序歸并連接算法)的性能要好[5].

1.4 分布式連接優(yōu)化技術(shù)

分布式查詢優(yōu)化的一個重要目標是減少節(jié)點間的數(shù)據(jù)傳輸代價.盡管傳統(tǒng)的連接算法的有效性已經(jīng)在集中式數(shù)據(jù)庫中得到了驗證,但是在分布式環(huán)境下,節(jié)點間的數(shù)據(jù)傳輸代價是制約查詢性能的重要因素.傳統(tǒng)的連接算法在分布式數(shù)據(jù)庫中的應(yīng)用和優(yōu)化成為了研究熱點.

一種典型的優(yōu)化方案是采用半連接策略[6]來減少網(wǎng)絡(luò)傳輸代價,降低通信開銷.但是,半連接需要將驅(qū)動表中連接列的值全部傳送到被驅(qū)動表所在節(jié)點,并且需要在該節(jié)點上執(zhí)行一次額外的連接.

針對以上問題,Chen等人把布隆過濾器[7]的思想應(yīng)用到連接算法中[8].基于布隆過濾器的連接算法進行了兩方面的優(yōu)化:首先將驅(qū)動表中連接列的值根據(jù)不同哈希函數(shù)映射到位數(shù)組中,僅將這個位數(shù)組進行傳輸;其次在被驅(qū)動表上執(zhí)行無序掃描,不再需要連接操作.L. F.Mackert等人在論文中指出,基于布隆過濾器的連接算法比基本的半連接算法性能更為優(yōu)秀[9].因此本文使用了基于布隆過濾器的連接算法,更好地提高了分布式數(shù)據(jù)庫OceanBase連接操作的處理性能.

2 問題定義和算法設(shè)計

2.1 問題定′

現(xiàn)有S表存儲在節(jié)點Snodei(i=1,2,···,x),R表存儲在節(jié)點Rnodej(j=1,2,···,y).現(xiàn)將S表和R表在連接屬性a上做自然連接:select*from S inner join R on S.a=R.a.

2.2 算法設(shè)計

本算法基于分布式架構(gòu),使用布隆過濾器對傳統(tǒng)的連接算法進行了優(yōu)化.優(yōu)化后的算法流程如下:

(1)將S表的全部數(shù)據(jù)從節(jié)點Snode1,Snode2,···,Snodex發(fā)送到計算節(jié)點M;

(2)根據(jù)S表連接列上的數(shù)據(jù)構(gòu)建布隆過濾器BFS,并將BFS分別發(fā)送到R表數(shù)據(jù)所在的節(jié)點Rnode1,Rnode2,···,Rnodey;

(3)在Rnode1,Rnode2,···,Rnodey每個節(jié)點上對R表的數(shù)據(jù)進行過濾,并把R表中經(jīng)過過濾的數(shù)據(jù)發(fā)送到計算節(jié)點;

(4)在計算節(jié)點上對兩表的數(shù)據(jù)進行排序歸并連接,并把最終結(jié)果返回給客戶端.

2.3 性能分析

與傳統(tǒng)的排序歸并連接算法相比,基于布隆過濾器的連接算法極大地提高了連接效率.

假設(shè)S表中元組數(shù)為card(S),元組的長度為size(S),R表中元組的個數(shù)為card(R),元組的長度為size(R),則可得到傳統(tǒng)的排序歸并連接算法下的網(wǎng)絡(luò)傳輸開銷T為:

假設(shè)布隆過濾器BFS包含k個相互獨立的哈希函數(shù)和一個m位長的位向量.布隆過濾器在判斷一個元素是否屬于它所代表的集合時會存在誤判:由于存在哈希沖突,某一個對應(yīng)于元素a的哈希位可能由于元素b的插入被設(shè)置為1,因此減小誤稱率是非常重要的.可以通過公式推導(dǎo)得出誤稱率perr最小的條件為:

此時,假設(shè)連接選擇率為α,R表經(jīng)過布隆過濾器過濾后縮減為R′表,基于布隆過濾器的連接算法下的網(wǎng)絡(luò)傳輸開銷T為:

由于布隆過濾器中位向量的大小m相比于Tnew中的其他兩項,可以忽略不計,從公式(3)可以看出,基于布隆過濾器的連接算法的網(wǎng)絡(luò)傳輸開銷明顯小于傳統(tǒng)的排序歸并連接算法下的網(wǎng)絡(luò)傳輸開銷,并且連接選擇率α越小,基于布隆過濾器的連接算法節(jié)省的網(wǎng)絡(luò)傳輸代價越大.

3 算法實現(xiàn)

3.1 OceanBase架構(gòu)

Oceanbase系統(tǒng)架構(gòu)由四種類型的節(jié)點服務(wù)器組成:

·RootServer:主控服務(wù)器,負責(zé)數(shù)據(jù)的負載均衡以及集群節(jié)點狀態(tài)管理等.

·ChunkServer:基線數(shù)據(jù)服務(wù)器,提供分布式數(shù)據(jù)存儲服務(wù),負責(zé)存儲基線數(shù)據(jù).

·UpdateServer:更新服務(wù)器,實現(xiàn)事務(wù)處理,負責(zé)存儲一段時間內(nèi)的增量數(shù)據(jù).

·MergeServer:查詢處理服務(wù)器,負責(zé)接收和解析SQL請求、生成和執(zhí)行查詢計劃以及

將所有節(jié)點的查詢結(jié)果合并并返回給客戶端.

本算法實際分為四個階段:

(1)將左表即S表的所有數(shù)據(jù)發(fā)送到一臺MergerServer上,其中Q包括ChunkServer存儲的基線數(shù)據(jù)又包括UpdateServer存儲的增量數(shù)據(jù);

(2)在MergerServer上根據(jù)S表的數(shù)據(jù)在連接屬性S.a上生成布隆過濾器BFS,并將該布隆過濾器BFS傳入右表即R表所在的ChunkServer;

(3)R表所在的ChunkServer通過合并UpdateServer上的增量數(shù)據(jù)獲得R表的全部數(shù)據(jù)后,使用BFS對數(shù)據(jù)進行過濾,并將過濾后的數(shù)據(jù)發(fā)送到MergerServer;

(4)MergerServer對兩張表的數(shù)據(jù)根據(jù)連接類型進行等值連接操作,再根據(jù)不等值條件進行過濾,并把最終結(jié)果返回給客戶端.

3.2 布隆過濾器構(gòu)建

在算法的第二階段,S表的數(shù)據(jù)全部發(fā)送到MergerServer后,MergerServer會根據(jù)這些數(shù)據(jù)構(gòu)建一個能夠表示S表所有元組的布隆過濾器BFS.通過公式,我們可以根據(jù)設(shè)定的誤稱率和數(shù)據(jù)量的大小計算出BFS中位數(shù)組的大小和哈希函數(shù)的個數(shù).

布隆過濾器的一個重要問題在于如何使用正確的哈希函數(shù)來確保過濾器生效.在哈希函數(shù)的選擇方面,本算法采用了MurmurHash函數(shù)來提高布隆過濾器的性能和效率. MurmurHash由Austin Appleby于2008年創(chuàng)立,是一種非加密型哈希函數(shù),適用于一般的哈希檢索操作,具有高運算性能和低碰撞率的特點.在Google的Guava開源項目[10]和LevelDB高效鍵值數(shù)據(jù)庫[11]中,BloomFilter(布隆過濾器)類就是基于MurmurHash函數(shù)來實現(xiàn)的.它的好處在于,不需要根據(jù)計算得出的k的大小來確定具體的哈希函數(shù),僅需要對一個哈希函數(shù)迭代k次,就能獲得有效的布隆過濾器.布隆過濾器的構(gòu)建算法如下:

算法1布隆過濾器構(gòu)建算法輸入：S表元組集合S,|S|=n輸出：布隆過濾器BFS1根據(jù)誤稱率perr和元素個數(shù)n計算MurmurHash函數(shù)的迭代次數(shù)k和位數(shù)組大小m 2生成一個m位的位數(shù)組BFS,并將每一位初始化為0 3for讀取S表的一條記錄s do 4if s不為空then 5 for i from 1 to k step 1 do 6將s代入MurmurHash函數(shù),計算hi(s)的值Vi; 7將BFS位數(shù)組的Vi位設(shè)為1; 8 end for 9end if 10end for 11布隆過濾器構(gòu)建結(jié)束

如第1行所示,先根據(jù)設(shè)定的誤稱率perr和元素個數(shù)n,計算布隆過濾器所需位數(shù)組的大小m以及MurmurHash函數(shù)的迭代次數(shù)k;然后如第3行至第10行所示,對S表的每一條記錄s依次作判斷,如果s不為空,則如第5行至第8行所示,將s依次代入MurmurHash函數(shù)迭代k次,h1(s),h2(s),···,hk(s)得到k個值V1,V2,···,Vk;再將BFS位數(shù)組的V1,V2,···,Vk位設(shè)為1,其余位維持初始化的0狀態(tài).當把S表的所有記錄遍歷過后,布隆過濾器的構(gòu)建完成. 3.3布隆過濾器查找

當算法進行到第三階段,R表所在ChunkServer上的基線數(shù)據(jù)經(jīng)過與UpdateServer上的增量數(shù)據(jù)合并獲得R表的全部數(shù)據(jù)后,需要使用BFS對數(shù)據(jù)進行過濾,找出有可能符合等值連接條件的記錄.布隆過濾器的查找算法如下:

算法2布隆過濾器查找算法輸入：R表元組集合R,布隆過濾器BFS輸出：符合等值條件的R表記錄集合R′1生成空集R′2對于R表中的每一條記錄,執(zhí)行如下流程3for讀取R表的一條記錄r do 4if r不為空then 5 for i from 1 to k step 1 do 6將r代入MurmurHash函數(shù),計算hi(r)的值Vi; 7檢查BFS位數(shù)組的Vi位是否為1; 8 end for 9 if BFS位數(shù)組的V1位至Vk位均為1 then 10R′=R′∪{r} 11end if 12end if 13 end for 14布隆過濾器查找結(jié)束

如第3行至第13行所示,依次讀取R表的一條記錄r,如果r不為空,則如第5行至第8行所示,將r依次帶入MurmurHash函數(shù)迭代k次,h1(r),h2(r),···,hk(r)得到k個值V1,V2,···, Vk,再檢查BFS位數(shù)組的V1,V2,···,Vk位是否為1,如第9行至第11行所示,如果全部k個位都為1,則將記錄r添加到集合R′中.當遍歷完R表的所有記錄后,輸出符合等值條件的R表記錄集合R′.

3.4 等值連接

在算法的最后一個階段,將經(jīng)過布隆過濾器BFS過濾的R表記錄集合R′發(fā)送到Merge-Server后,由于布隆過濾器存在誤判,因此這時獲得的R表數(shù)據(jù)是R表最終可以進行等值連接操作的元組集合的超集,所以MergeServer還必須對數(shù)據(jù)進行一次過濾,以獲得最終結(jié)果集.本算法選擇使用經(jīng)典的排序歸并連接算法,在MergeServer的內(nèi)存里對兩張表的數(shù)據(jù)根據(jù)連接列排序,然后對排完序的結(jié)果做歸并連接,最后再根據(jù)其余不等值條件進行過濾,并把最終結(jié)果返回給客戶端.

4 實驗評估

為了驗證本算法的效率,本文設(shè)計了三組實驗,從選擇率、連接列和數(shù)據(jù)分布對性能的影響三個方面,通過觀察對相同查詢語句的處理時間,分析了基于布隆過濾器的連接算法的性能,并得出了結(jié)論.

4.1 實驗環(huán)境

實驗使用的OceanBase集群測試環(huán)境是在OceanBase開源的0.4.2版本上實現(xiàn)上述算法經(jīng)過優(yōu)化的版本,本文使用4臺虛擬機組成的集群作為測試環(huán)境,每臺虛擬機的配置相同,包括4核1.2 GHz主頻CPU、100 GB內(nèi)存、3 000 GB磁盤,虛擬機上安裝了CentOS release 6.5系統(tǒng),相互之間通過千兆以太網(wǎng)連接.集群中的一臺虛擬機被配置為RootServer、MergeServer和UpdateServer,另外三臺虛擬機被配置為ChunkServer.實驗采用的數(shù)據(jù)是使用數(shù)據(jù)生成器隨機生成的數(shù)據(jù).

4.2 實驗結(jié)果

4.2.1 選擇率對性能的影響

該實驗對比查詢語句中連接列的選擇率對OceanBase中傳統(tǒng)的排序歸并連接算法與基于布隆過濾器的連接算法的性能影響.測試左表包含10萬條記錄,右表的數(shù)據(jù)量從10萬到1 000萬條記錄不等,兩表連接列均為［1,MAX］的整數(shù),MAX為記錄數(shù).

圖1 選擇率對性能的影響結(jié)果Fig.1Effect of the selectivity on performance

從圖1中可以看出,當右表的數(shù)據(jù)量較小,即左表對右表的選擇率較高時,布隆過濾器的構(gòu)建和查找增加了計算開銷,右表數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)開銷降低得并不明顯,基于布隆過濾器的連接算法的處理時間比傳統(tǒng)的排序歸并連接算法的處理時間要多.但是當右表的數(shù)據(jù)量達到100萬行以上,即左表對右表的選擇率越來越低時,傳統(tǒng)的排序歸并連接算法的處理時間大大增加,而使用布隆過濾器的連接算法的處理時間則呈近似線性增長.這是因為在選擇率較小時,數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)代價將會占查詢處理時間的主要部分.布隆過濾器以極低的計算代價,極大地降低了網(wǎng)絡(luò)開銷,提高了連接操作的性能.

4.2.2 連接列對性能的影響

該實驗對比查詢語句中連接列的個數(shù)對OceanBase中傳統(tǒng)的排序歸并連接算法和基于布隆過濾器的連接算法的性能影響.測試左表包含100萬條記錄,右表包含1 000萬條記錄,連接列的個數(shù)從1到7個不等,兩表連接列均為［1,MAX］的整數(shù),MAX為記錄數(shù).

圖2 連接列對性能的影響結(jié)果Fig.2Effect of the number of join columns on performance

圖2表明,查詢語句中的連接列個數(shù)增多時,基于布隆過濾器的連接算法優(yōu)勢更加明顯.布隆過濾器將多個連接列映射到一組對應(yīng)的位數(shù)組,隨著連接列的增多,布隆過濾器對數(shù)據(jù)的描述更加準確,對數(shù)據(jù)的過濾也更加有效.

4.2.3 不同數(shù)據(jù)分布對性能的影響

該實驗對比連接列中數(shù)據(jù)不同的分布情況對基于布隆過濾器的連接算法的性能影響.測試左表包含10萬條記錄,右表的數(shù)據(jù)量從10萬到1 000萬條記錄不等.為避免數(shù)據(jù)分布情況對兩表連接結(jié)果的大小產(chǎn)生影響,控制三種數(shù)據(jù)分布下兩表連接的結(jié)果集大小相等.

圖3 不同數(shù)據(jù)分布對性能的影響結(jié)果Fig.3Effect of the data distribution on performance

如圖3所示,數(shù)據(jù)的分布情況對布隆過濾器的性能幾乎沒有影響.布隆過濾器構(gòu)建和查找的性能主要由前表和后表的元組數(shù)決定,因此在不同的數(shù)據(jù)分布下,布隆過濾器的性能是較為穩(wěn)定的.

通過以上實驗得出,改進后的連接算法極大地減少了OceanBase對連接操作的處理時間,并且隨著選擇率的降低和連接列個數(shù)的增加,性能的提高也更加明顯.

5 總結(jié)

本文實現(xiàn)了一種分布式數(shù)據(jù)庫中基于布隆過濾器的連接算法,并在開源數(shù)據(jù)庫OceanBase上進行了實驗驗證.該算法充分利用了布隆過濾器低空間代價和快速響應(yīng)的特點,通過對右表數(shù)據(jù)使用布隆過濾器進行過濾,減少了分布式環(huán)境下不必要數(shù)據(jù)的網(wǎng)絡(luò)傳輸代價,降低了數(shù)據(jù)操作帶來的內(nèi)存資源的消耗,在連接列的選擇率較低的情況下顯著提高了連接操作的處理性能.

本文基于目前OceanBase數(shù)據(jù)庫的架構(gòu),使用了布隆過濾器對連接算法進行了優(yōu)化,但該算法仍有優(yōu)化空間.如何對傳統(tǒng)的布隆過濾器模型進行拓展,如何進一步使用MPP架構(gòu),將布隆過濾器的計算和數(shù)據(jù)的連接任務(wù)并行地分散到多個節(jié)點上,以及如何根據(jù)統(tǒng)計信息選擇具體的連接算法,都是以后對連接優(yōu)化算法研究工作的重點.

［1］楊傳輝.大規(guī)模分布式存儲系統(tǒng):原理解析與架構(gòu)實戰(zhàn)[M].北京:機械工業(yè)出版社,2013.

［2］BLASGEN M W,ESWARAN K P.Storage and access in relational data bases[J].IBM Systems Journal,1977, 16(4):363-377.

［3］MERRETT T H.Why sort-merge gives the best implementation of the natural join[J].ACM SIGMOD Record, 1983,13(2):39-51.

［4］BABB E.Implementing a relational database by means of specialized hardware[J].ACM Transactions on Database Systems,1979,4(1):1-29.

［5］SCHNEIDER D A,DEWITT D J.A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment[C]//Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data.ACM,1989:110-121.

［6］BERNSTEIN P A,GOODMAN N,WONG E,et al.Query processing in a system for distributed databases (SDD-1)[J].ACM Transactions on Database Systems,1981,6(4):602-625.

［7］BLOOM B H.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM,1970, 13(7):422-426.［8］CHEN M S,HSIAO H I,YU P S.On applying hash filters to improving the execution of multi-join queries[J]. The VLDB journal,1997,6(2):121-131.

［9］MACKERTLF,LohmanGM.R*optimizer validationandperformance evaluationfordistributed queries[C]//Proceedings of the 12th International Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publishers Inc,1986:149-159.

［10］BACON D F,STROM R E,TARAFDAR A.Guava:A dialect of Java without data races[C]//Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming,Systems,Languages,and Applications. 2000:382-400.

［11］GHEMAWAT S,DEAN J.Level DB[DB/OL].[2011-5-12].http://code.google.com/p/leveldb/.

(責(zé)任編輯:林磊)

A join algorithm based on bloom filter in OceanBase

MAO Xiao-xiao,DUAN Hui-chao,GAO Ming
(Institute for Data Science and Engineering,East China Normal University, Shanghai200062,China)

In the era of big data,the movement of“de-IOE”campaign and the development of activities such as Double 11 have put forward higher request of the performance of distributed database.OceanBase is an open sourced distributed database implemented by Alibaba.It supports for cross-table relational query of massive data but the performance for complex queries remains to be improved.The network transmission overheads caused by join operator seriously influenced the performance of distributed database.This paper proposes a join algorithm based on bloom filter.It filters the data of the right table by constructing a bloom filter on the join column of the left table.The key point of this algorithm is that it reduces the overhead of unnecessary data transmission and the consumption of memory resources by data processing.We implement this algorithm in OceanBase and the experiment results show that the algorithm can greatly improve the efficiency of join operator.

OceanBase;join operation;bloom filter

TP311

A

10.3969/j.issn.1000-5641.2016.05.008

1000-5641(2016)05-0067-08

2016-05

國家863計劃項目(2015AA015307)

茅瀟瀟,女,碩士研究生,研究方向為分布式數(shù)據(jù)庫.E-mail:jsntmxx@gmail.com.

高明,男,副教授,研究方向為高可用事務(wù)處理優(yōu)化、數(shù)據(jù)挖掘等. E-mail:mgao@sei.ecnu.edu.cn.