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

茅瀟瀟,段惠超,高明

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

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

茅瀟瀟,段惠超,高明

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

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

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

0 引言

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

1.2 排序歸并連接算法

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

1.3 哈希連接算法

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

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

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

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

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

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

2.1 問題定′

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

2.2 算法設(shè)計(jì)

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

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

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

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

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

2.3 性能分析

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

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

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

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

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

3 算法實(shí)現(xiàn)

3.1 OceanBase架構(gòu)

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

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

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

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

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

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

本算法實(shí)際分為四個(gè)階段:

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

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

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

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

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

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

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

算法1布隆過濾器構(gòu)建算法輸入：S表元組集合S,|S|=n輸出：布隆過濾器BFS1根據(jù)誤稱率perr和元素個(gè)數(shù)n計(jì)算MurmurHash函數(shù)的迭代次數(shù)k和位數(shù)組大小m 2生成一個(gè)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ù),計(jì)算hi(s)的值Vi; 7將BFS位數(shù)組的Vi位設(shè)為1; 8 end for 9end if 10end for 11布隆過濾器構(gòu)建結(jié)束

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

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

算法2布隆過濾器查找算法輸入：R表元組集合R,布隆過濾器BFS輸出：符合等值條件的R表記錄集合R′1生成空集R′2對(duì)于R表中的每一條記錄,執(zhí)行如下流程3for讀取R表的一條記錄r do 4if r不為空then 5 for i from 1 to k step 1 do 6將r代入MurmurHash函數(shù),計(jì)算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個(gè)值V1,V2,···, Vk,再檢查BFS位數(shù)組的V1,V2,···,Vk位是否為1,如第9行至第11行所示,如果全部k個(gè)位都為1,則將記錄r添加到集合R′中.當(dāng)遍歷完R表的所有記錄后,輸出符合等值條件的R表記錄集合R′.

3.4 等值連接

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

4 實(shí)驗(yàn)評(píng)估

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

4.1 實(shí)驗(yàn)環(huán)境

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

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 選擇率對(duì)性能的影響

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

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

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

4.2.2 連接列對(duì)性能的影響

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

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

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

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

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

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

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

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

5 總結(jié)

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

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

［1］楊傳輝.大規(guī)模分布式存儲(chǔ)系統(tǒng):原理解析與架構(gòu)實(shí)戰(zhàn)[M].北京:機(jī)械工業(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

國(guó)家863計(jì)劃項(xiàng)目(2015AA015307)

茅瀟瀟,女,碩士研究生,研究方向?yàn)榉植际綌?shù)據(jù)庫.E-mail:jsntmxx@gmail.com.

高明,男,副教授,研究方向?yàn)楦呖捎檬聞?wù)處理優(yōu)化、數(shù)據(jù)挖掘等. E-mail:mgao@sei.ecnu.edu.cn.