徐石磊,王雷,胡卉芪,錢衛(wèi)寧,周傲英

(華東師范大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院,上海200062)

基于分布式系統(tǒng)OceanBase的并行連接

徐石磊,王雷,胡卉芪,錢衛(wèi)寧,周傲英

(華東師范大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院,上海200062)

隨著應(yīng)用數(shù)據(jù)的飛速增長以及分布式數(shù)據(jù)庫系統(tǒng)的不斷涌現(xiàn),數(shù)據(jù)存儲(chǔ)在物理獨(dú)立的節(jié)點(diǎn)已經(jīng)成為一種趨勢(shì).在這種情況下,當(dāng)應(yīng)用需要進(jìn)行復(fù)雜join查詢時(shí),就會(huì)不可避免地產(chǎn)生非常多的網(wǎng)絡(luò)傳輸代價(jià).所以,如何提高分布式系統(tǒng)中join查詢的效率成為研究熱點(diǎn).本文在分析分布式數(shù)據(jù)庫系統(tǒng)OceanBase執(zhí)行nested loop join、Hash join、semi-join等算法的基礎(chǔ)上,提出了合理利用硬件資源采用多線程并行執(zhí)行join操作的優(yōu)化思想,并在OceanBase數(shù)據(jù)庫中分別對(duì)nested loop join、Hash join、semi-join等算法進(jìn)行了并行改造.實(shí)驗(yàn)結(jié)果表明,在一定線程數(shù)內(nèi)join算法執(zhí)行效率與并行度呈正相關(guān).

查詢;semi-join;OceanBase;并行連接

0 引言

OceanBase[1]是阿里巴巴公司開發(fā)的分布式數(shù)據(jù)庫,其設(shè)計(jì)目標(biāo)是支持?jǐn)?shù)百TB的數(shù)據(jù)量以及數(shù)十萬TPS、數(shù)百萬QPS的訪問量.因此,如何實(shí)現(xiàn)對(duì)如此龐大數(shù)據(jù)的快速查詢服務(wù),給我們的工作提出了一個(gè)巨大的挑戰(zhàn).

通過對(duì)分布式數(shù)據(jù)庫系統(tǒng)OceanBase的架構(gòu)分析,可以知道,雖然OceanBase有多個(gè)數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)和多個(gè)查詢處理節(jié)點(diǎn),但是,目前各個(gè)查詢處理節(jié)點(diǎn)在處理join(連接)工作時(shí)尚且無法實(shí)現(xiàn)協(xié)同工作.因此,無法通過將任務(wù)分解給多個(gè)查詢節(jié)點(diǎn)協(xié)同工作的方式實(shí)現(xiàn)高效快速查詢.此外,在查詢處理節(jié)點(diǎn)中,對(duì)于join查詢操作,OceanBase只是簡(jiǎn)單地實(shí)現(xiàn)了串行化執(zhí)行,并沒有合理利用硬件資源和數(shù)據(jù)冗余存儲(chǔ)的特性,由此給查詢帶來了極大的網(wǎng)絡(luò)傳輸和join時(shí)間,導(dǎo)致系統(tǒng)在處理大表數(shù)據(jù)join查詢時(shí)效率非常低下.針對(duì)這一缺點(diǎn),我們提出了一種即時(shí)有效地并行連接優(yōu)化方案:將數(shù)據(jù)進(jìn)行范圍切分,根據(jù)數(shù)據(jù)多重備份特性,設(shè)置多線程讀取數(shù)據(jù);每個(gè)線程獨(dú)立讀取數(shù)據(jù),數(shù)據(jù)達(dá)到后獨(dú)立執(zhí)行join操作.從而實(shí)現(xiàn)了各個(gè)查詢節(jié)點(diǎn)中join操作的并行化執(zhí)行,極大地提高了OceanBase做復(fù)雜join查詢的效率.本文的研究重點(diǎn)是nested loop join、Hash join、semi-join等join算法的并行化設(shè)計(jì)以及數(shù)據(jù)分片的切分方式.

論文的內(nèi)容組織如下:第1節(jié)簡(jiǎn)要介紹OceanBase數(shù)據(jù)庫的整體結(jié)構(gòu)及傳統(tǒng)的nested loop join,merge sort join、Hash join等join算法和semi-join、分布式j(luò)oin算法;第2節(jié)介紹OceanBase中傳統(tǒng)join算法的查詢?cè)砗突趕emi-join的傳統(tǒng)join算法查詢?cè)?第3節(jié)介紹在OceanBase中對(duì)nested loop join、Hash join、semi-join等join算法的并行優(yōu)化設(shè)計(jì);第4節(jié)從并行度對(duì)查詢效率的影響、并行度對(duì)各join算法執(zhí)行效率的影響,以及并行度對(duì)基于semi-join算法的各join算法執(zhí)行效率的影響等3方面進(jìn)行全面的實(shí)驗(yàn)驗(yàn)證;第5節(jié)對(duì)本文進(jìn)行總結(jié).

1 相關(guān)工作

OceanBase分布式數(shù)據(jù)庫整體架構(gòu)主要分為4個(gè)模塊:主控服務(wù)器RootServer(以下簡(jiǎn)稱為RS)、數(shù)據(jù)存儲(chǔ)服務(wù)器ChunkServer(以下簡(jiǎn)稱為CS)、增量數(shù)據(jù)服務(wù)器Update-Server(以下簡(jiǎn)稱UPS)以及查詢處理服務(wù)器MergeServer(以下簡(jiǎn)稱為MS).RS負(fù)責(zé)管理集群中的所有服務(wù)器,一般設(shè)置一主一備兩個(gè)RS;UPS主要負(fù)責(zé)處理系統(tǒng)的增量數(shù)據(jù)更新,一般也設(shè)置一主一備兩個(gè)UPS;MS則負(fù)責(zé)接收和解析用戶的SQL請(qǐng)求,經(jīng)過詞法分析、語法分析、查詢優(yōu)化等一系列操作后轉(zhuǎn)發(fā)給相應(yīng)的CS或者UPS;CS主要負(fù)責(zé)存儲(chǔ)系統(tǒng)的基準(zhǔn)數(shù)據(jù),基準(zhǔn)數(shù)據(jù)一般存儲(chǔ)兩到三份,可配置.

傳統(tǒng)的連接算法有嵌套循環(huán)連接(nested loop join)算法、歸并排序連接(merge sort join)算法以及哈希連接(Hash join)算法.這3種算法的提出都有特定的問題背景和適用情況.伴隨著分布式數(shù)據(jù)庫的發(fā)展和普及,Bernstein等[2]又提出了semi-join(半連接)算法,此算法可大幅減少join過程中數(shù)據(jù)的傳輸代價(jià).此外,在分布式系統(tǒng)中,伴隨著MapReduce、Spark等系統(tǒng)的發(fā)展,越來越多的分布式系統(tǒng)開始采用類似Map/Reduce[3]的計(jì)算模型,這類系統(tǒng)旨在通過任務(wù)分解的方式,減小join計(jì)算代價(jià).下面簡(jiǎn)要介紹這些算法的特點(diǎn)以及研究發(fā)展情況.

1.1 nested loop join算法

Blasgen等[4]在1977年提出了nested loop join算法.該算法適合于兩表數(shù)據(jù)量較小并且內(nèi)存可以存放的情況.后來,在共享內(nèi)存架構(gòu)下,Zhou等[5]又提出了利用SIMD技術(shù)優(yōu)化嵌套循環(huán)連接的3種方式:復(fù)制外層循環(huán);復(fù)制內(nèi)層循環(huán);旋轉(zhuǎn)方式.在無共享架構(gòu)下,Spark結(jié)構(gòu)中采用廣播形式將數(shù)據(jù)傳到其他節(jié)點(diǎn)上[6].

1.2 merge sort join算法

針對(duì)嵌套循環(huán)連接處理大數(shù)據(jù)時(shí)效率低的問題,Blasgen等[4]提出了merge sort join算法.該算法首先對(duì)兩張表排序,然后進(jìn)行順序掃描;當(dāng)其中一張表掃描結(jié)束后,算法也立即結(jié)束.這曾經(jīng)被認(rèn)為是最好的連接算法[7].在之后對(duì)歸并排序連接算法的研究中,Kim等[8]指出了歸并排序連接算法的效率與SIMD寬度有關(guān).

1.3 Hash join算法

Babb[9]在1979年第一次提出了以哈希(Hash)函數(shù)為基礎(chǔ)的連接算法.當(dāng)小表數(shù)據(jù)量較小可放在內(nèi)存中且小表的連接列具有非常好的選擇性時(shí),效率很好.隨著硬件技術(shù)的更新?lián)Q代,Boncz等[10]提出了Radix連接算法,算法充分利用了硬件資源,極大地優(yōu)化了連接算法在內(nèi)存中的Cache缺失和TLB缺失.

1.4 semi-join算法

Bernstein在1981年提出了semi-join算法.該算法針對(duì)一張小表和一張超大表的內(nèi)連接,目的在于利用小表的連接列對(duì)大表進(jìn)行過濾.但是semi-join算法需要構(gòu)建過濾表達(dá)式以及一次額外的數(shù)據(jù)傳輸——將過濾表達(dá)式傳到大表所在存儲(chǔ)節(jié)點(diǎn).因此,其適應(yīng)于大表數(shù)據(jù)過濾后只有少量數(shù)據(jù)的情況.

1.5 分布式j(luò)oin算法

相比傳統(tǒng)數(shù)據(jù)庫處理join查詢,分布式數(shù)據(jù)庫處理復(fù)雜join查詢時(shí),可將join操作分解為多個(gè)join任務(wù)分配給多臺(tái)機(jī)器獨(dú)立執(zhí)行,最后再將各部分join結(jié)果匯總.例如,文獻(xiàn)[3]研究了如何將join操作分解成多個(gè)任務(wù)在Map/Reduce模型中執(zhí)行.這類分布式j(luò)oin算法原理都是將一個(gè)完整的join操作分解成多個(gè)小的join操作,放在多個(gè)查詢節(jié)點(diǎn)上并行執(zhí)行,最終將網(wǎng)絡(luò)傳輸代價(jià)、join計(jì)算代價(jià)分?jǐn)偨o多個(gè)查詢處理節(jié)點(diǎn).

2 分布式系統(tǒng)OceanBase中join算法的工作原理

2.1 nested loop join、merge sort join、Hash join算法工作原理

圖1為nested loop join、merge sort join、Hash join流程圖,其中,R表作為驅(qū)動(dòng)表,S作為被驅(qū)動(dòng)表,MS是查詢處理節(jié)點(diǎn),CS是數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn).

join操作符左右各有一個(gè)Sort操作符和一個(gè)RpcScan操作符,其中RpcScan負(fù)責(zé)向CS存儲(chǔ)節(jié)點(diǎn)請(qǐng)求數(shù)據(jù).在存儲(chǔ)節(jié)點(diǎn)CS上的Project、Filter操作符,用于過濾存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù).當(dāng)join查詢產(chǎn)生時(shí),join算法的左右兩個(gè)子操作符RpcScan同時(shí)向CS請(qǐng)求數(shù)據(jù),如果表數(shù)據(jù)量很大且沒有附帶充分的過濾條件,將會(huì)產(chǎn)生非常大的數(shù)據(jù)網(wǎng)絡(luò)傳輸代價(jià).請(qǐng)求得到的數(shù)據(jù)在join算子處進(jìn)行逐行join操作.

2.2 基于semi-join的join工作原理

圖2為基于semi-join的join流程圖,其中,R表作為驅(qū)動(dòng)表,S作為被驅(qū)動(dòng)表,MS是查詢處理節(jié)點(diǎn),CS是數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn).

圖1 nested loop join、merge sort join、Hash join執(zhí)行計(jì)劃Fig.1 Nested loop join,merge sort join,Hash join execution plan

圖2 基于semi-join的join執(zhí)行計(jì)劃Fig.2 Execution plan of join based on semi-join

基于semi-join的join算法步驟如下.

(1)向R表所在的CS并行發(fā)出請(qǐng)求,獲得數(shù)據(jù),這里獲得的數(shù)據(jù)是經(jīng)過Project和Filter過濾的、連接列上的、符合條件的數(shù)據(jù).

(2)將(1)中所得到的數(shù)據(jù)構(gòu)造成過濾表達(dá)式發(fā)送給S表所在的CS,之后會(huì)在S表所在的Server上執(zhí)行這個(gè)過濾操作,過濾掉S表中不符合條件的數(shù)據(jù).

(3)右表的RpcScan操作符開始拉去過濾后的S表數(shù)據(jù).

(4)R表和S表過濾后的數(shù)據(jù)到達(dá)join操作符后,進(jìn)行串行化逐行join.

3 并行優(yōu)化設(shè)計(jì)

基于第2節(jié)描述的串行化逐行join情況,我們提出并行join優(yōu)化方案.下面我們將對(duì)OceanBase數(shù)據(jù)庫中的Hash join、nested loop join及semi-join進(jìn)行并行優(yōu)化設(shè)計(jì).

3.1 Hash join的并行優(yōu)化設(shè)計(jì)

首先,分配線程分別對(duì)兩張表的數(shù)據(jù)調(diào)用Hash函數(shù)進(jìn)行分區(qū);然后根據(jù)分片數(shù)申請(qǐng)?zhí)幚砭€程,每個(gè)線程讀取一組對(duì)應(yīng)分片數(shù)據(jù)后做連接操作;隨后將輸出結(jié)果發(fā)送給連接算子.具體流程如圖3所示.

圖3 Hash join的并行設(shè)計(jì)Fig.3 Parallel design of Hash join

1.首先分配兩個(gè)線程,線程a和線程b,使用相同的Hash函數(shù),并行地對(duì)R表和S表數(shù)據(jù)根據(jù)連接列進(jìn)行分區(qū)處理,將R表分區(qū)成R1,R2,R3,…,Rn等多個(gè)結(jié)果集,同樣將S表分成S1,S2,S3,…,S n,分區(qū)個(gè)數(shù)取決于具體的Hash函數(shù).由于R表與S表的數(shù)據(jù)集大小不同,分區(qū)執(zhí)行的時(shí)間也不同.因此,要等到兩個(gè)線程分區(qū)工作都完成才能繼續(xù).如果出現(xiàn)兩張表大小相差很大時(shí),可以進(jìn)一步分配多個(gè)線程對(duì)大表進(jìn)行分區(qū).這樣,可以有效減少分區(qū)時(shí)間.

2.由于使用的Hash函數(shù)相同,對(duì)于分區(qū)后的結(jié)果集,我們將R1與S1對(duì)應(yīng),R2與S2對(duì)應(yīng),其他類似.

3.并行模塊設(shè)置多個(gè)處理線程,線程1,線程2,線程3,…,線程n,分別對(duì)應(yīng)2中的一組分區(qū).每個(gè)線程并行地去各個(gè)存儲(chǔ)節(jié)點(diǎn)拉取對(duì)應(yīng)范圍數(shù)據(jù),隨后進(jìn)行join處理,例如,線程1負(fù)責(zé)〈R1,S1〉.多個(gè)線程同步執(zhí)行,可以極大減少處理時(shí)間.處理線程具體步驟如下,以線程1為例.

(1)對(duì)R1分區(qū)的連接屬性列,使用Hash函數(shù)構(gòu)造Hash表T.

(2)對(duì)S1分區(qū)中的每一個(gè)連接列數(shù)據(jù),使用相同的Hash函數(shù)對(duì)(1)中生成的Hash表T進(jìn)行檢測(cè).

(3)如果S1分區(qū)中的連接列數(shù)據(jù)落在Hash表T中,則將對(duì)應(yīng)行數(shù)據(jù)進(jìn)行連接操作,生成中間結(jié)果集,并將結(jié)果集發(fā)送給連接算子操作符.

(4)處理線程結(jié)束,釋放內(nèi)存資源,清空環(huán)境信息,并重新掛起線程.

4.連接算子操作符接收處理線程發(fā)送過來的中間結(jié)果集,存在操作符內(nèi)部的緩存區(qū).直到所有數(shù)據(jù)集全部處理完,并接收到所有中間結(jié)果集,然后發(fā)送給客戶端.

以上為Hash join的并行實(shí)現(xiàn)流程.并行設(shè)計(jì)體現(xiàn)在:首先,對(duì)于連接表數(shù)據(jù)讀取進(jìn)行并行操作;然后處理線程并行執(zhí)行連接操作.

3.2 nested loop join的并行優(yōu)化設(shè)計(jì)

與Hash類似,首先,分配線程對(duì)R表的數(shù)據(jù)進(jìn)行切分;然后根據(jù)分片數(shù)申請(qǐng)線程,每個(gè)線程分別讀取數(shù)據(jù)后將數(shù)據(jù)與S表做連接操作;隨后將輸出結(jié)果發(fā)送給連接算子.與Hashjoin的區(qū)別在于無需對(duì)S表進(jìn)行切分.具體流程如圖4所示.

圖4 nested loop join的并行設(shè)計(jì)Fig.4 Parallel design of nested loop join

1.首先分配一個(gè)線程,將R表分為等分的多個(gè)部分R1,R2,R3,…,Rn,具體分為多少部分由R的結(jié)果集和可用的線程數(shù)確定.

2.將1中R表等分產(chǎn)生的R1,R2,R3,…,Rn分別與S對(duì)應(yīng)起來,例如〈R1,S〉,〈R2,S〉.

3.并行模塊設(shè)置多個(gè)線程R1,R2,R3,…,Rn,分別對(duì)應(yīng)2中的一組分區(qū).每個(gè)線程并行地去各個(gè)存儲(chǔ)節(jié)點(diǎn)拉取對(duì)應(yīng)范圍數(shù)據(jù),隨后進(jìn)行join處理,例如,線程1負(fù)責(zé)〈R1,S〉,多線程同步執(zhí)行.處理線程具體步驟如下,以線程1為例.

(1)R1作為外層循環(huán)表,S表作為內(nèi)層循環(huán)表.

(2)將R1中的記錄逐一與S表中的所有記錄對(duì)比.如果對(duì)應(yīng)連接列值匹配,則生成新的元祖作為中間結(jié)果集,執(zhí)行這一操作,直到R1表中數(shù)據(jù)全部遍歷完,并將結(jié)果集發(fā)給連接算子操作符.

(3)處理線程結(jié)束,釋放內(nèi)存資源,清空系統(tǒng)環(huán)境,重新掛起線程.

4.處理算子操作符接收處理線程發(fā)送過來的中間結(jié)果集,存在操作符內(nèi)部的緩存區(qū).直到所有數(shù)據(jù)集全部處理完,并接收到所有中間結(jié)果集,然后發(fā)送給客戶端.

以上為nested loop join的并行實(shí)現(xiàn)流程.并行設(shè)計(jì)體現(xiàn)在:首先,多個(gè)線程并行地從存儲(chǔ)節(jié)點(diǎn)讀取相應(yīng)范圍的數(shù)據(jù);然后處理線程并行執(zhí)行連接操作.

3.3 semi-join的并行優(yōu)化設(shè)計(jì)

首先,分配線程對(duì)R表的數(shù)據(jù)進(jìn)行切分;然后根據(jù)分片信息申請(qǐng)線程,每個(gè)線程分別讀取數(shù)據(jù)并構(gòu)造過濾表達(dá)式,隨后將輸出結(jié)果發(fā)送給半連接算子.具體流程如圖5所示.

圖5 semi-jion并行設(shè)計(jì)Fig.5 Parallel design of semi-join

1.將R表結(jié)果集連接屬性列等分為R1,R2,R3,…,Rn,具體分為多少份取決于系統(tǒng)資源以及R表結(jié)果集大小.

2.并行模塊為R表結(jié)果集每個(gè)分片提供一個(gè)線程,各個(gè)處理線程分別拉取對(duì)應(yīng)范圍數(shù)據(jù),并根據(jù)連接屬性列信息并行執(zhí)行過濾操作.此時(shí)的輸出并非join結(jié)果集,而是S表中符合過濾條件的元組.隨后提交給半連接操作符.處理線程具體步驟如下.

(1)根據(jù)輸入R表分片信息構(gòu)造過濾表達(dá)式.這里可以根據(jù)數(shù)據(jù)輸入的R表結(jié)果集大小考慮構(gòu)造In表達(dá)式或者Between表達(dá)式,具體構(gòu)造哪種表達(dá)式取決于R表輸入信息.

(2)將過濾表達(dá)式發(fā)送給S表所在存儲(chǔ)節(jié)點(diǎn).S表所在存儲(chǔ)節(jié)點(diǎn)用過濾表達(dá)式根據(jù)連接屬性列過濾S表數(shù)據(jù).

(3)S表所在存儲(chǔ)節(jié)點(diǎn)將符合條件的數(shù)據(jù)作為輸出結(jié)果集發(fā)送到半連接操作符.

3.半連接接收處理線程陸續(xù)發(fā)來的結(jié)果集,并將結(jié)果集存在操作符內(nèi)部的緩存區(qū).當(dāng)所有數(shù)據(jù)處理結(jié)束后,半連接算子操作符將緩存中的數(shù)據(jù)發(fā)送給連接算子操作符.此后,連接算子操作符才開始真正的join操作.

以上為semi-join的并行設(shè)計(jì)方案.并行設(shè)計(jì)體現(xiàn)在:根據(jù)R表輸入并行構(gòu)造過濾表達(dá)式;多線程并行讀取各分片對(duì)應(yīng)過濾表達(dá)式信息,隨后并行用過濾表達(dá)式過濾S表數(shù)據(jù);各連接算子并行做join操作.

4 實(shí)驗(yàn)分析

首先,測(cè)試不同并行度下,單表讀取數(shù)據(jù)的效率;其次,測(cè)試在不同并行度下傳統(tǒng)join算法的執(zhí)行效率;最后,測(cè)試不同并行度下基于semi-join算法的傳統(tǒng)join算法執(zhí)行效率.

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

本文選擇OceanBase系統(tǒng)作為實(shí)驗(yàn)系統(tǒng)環(huán)境.實(shí)驗(yàn)使用5臺(tái)服務(wù)器,OceanBase的實(shí)驗(yàn)版本為0.4.2,其中主控節(jié)點(diǎn)RS與UPS共用一臺(tái)服務(wù)器,其余4臺(tái)服務(wù)器分別部署CS與MS.整個(gè)OceanBase數(shù)據(jù)庫集群中3臺(tái)CS,1臺(tái)MS.實(shí)驗(yàn)環(huán)境的OceanBase集群物理拓?fù)淙鐖D6所示.

圖6 OceanBase實(shí)驗(yàn)環(huán)境物理拓?fù)銯ig.6 Physical topology of OceanBase experimental environment

4.2 實(shí)驗(yàn)硬件環(huán)境

本文測(cè)試所用硬件環(huán)境如表1所示,其中磁盤為SSD(Solid State Drive).

表1 集群服務(wù)器配置Tab.1 The cluster server conf i guration

4.3 實(shí)驗(yàn)數(shù)據(jù)集

本文測(cè)試用到的所有數(shù)據(jù)表的模式如表2所示.

表2 測(cè)試表的模式Tab.2 The schema of the test table

所有實(shí)驗(yàn)數(shù)據(jù)都是由Sysbench的數(shù)據(jù)生成器生成.實(shí)驗(yàn)一共涉及7張表,數(shù)據(jù)分布以及數(shù)據(jù)量如表3所示.

表3 測(cè)試數(shù)據(jù)表信息Tab.3 Test data table information

以R1為例,數(shù)據(jù)分布的連續(xù)性是指R1表的主鍵列ID的數(shù)據(jù)是按照升序排列的.

4.4 不同并行度下的連接查詢響應(yīng)時(shí)間

實(shí)驗(yàn)?zāi)康?單表情況下并行度以及數(shù)據(jù)過濾方式對(duì)查詢響應(yīng)時(shí)間的影響.

數(shù)據(jù)設(shè)置:使用表R2作為測(cè)試表,結(jié)果集為100萬,并發(fā)度分別為1、5、15、20、25、30、35,數(shù)據(jù)過濾方式為主鍵定位、In表達(dá)式、Between表達(dá)式.

實(shí)驗(yàn)結(jié)果如圖7所示.

圖7 不同并行度單表數(shù)據(jù)查詢的響應(yīng)時(shí)間Fig.7 Response time for single table query with di ff erent parallel number

從實(shí)驗(yàn)結(jié)果可以得出,隨著并行度的增加,響應(yīng)時(shí)間總體呈下降趨勢(shì).因此通過并行的方式來提高數(shù)據(jù)的過濾速度,對(duì)減少連接查詢的響應(yīng)時(shí)間是有效的.

4.5 連接算子的執(zhí)行效率

圖8所示為在不同的并行度下,各連接算法的執(zhí)行效率.在并行度為1的情況下,nested loop join在處理100萬條數(shù)據(jù)的連接計(jì)算時(shí)花費(fèi)的時(shí)間在78 s左右.由于與其他連接算子的響應(yīng)時(shí)間相差太大,因此沒有在圖中完全顯示.隨著并行度的增加,各連接算子的響應(yīng)時(shí)間都有所降低.

圖8 不同并行度下連接算法的執(zhí)行效率Fig.8 Execution effi ciency of join algorithms with dif f erent parallel number

圖9 不同并行度下基于semi-join的join執(zhí)行效率Fig.9 Execution effi ciency of join based on semi-join in dif f erent parallel number

4.6 semi-join下各join算法的查詢效率

如圖9所示,隨著并行度的提高,Hash join、nested loop join的響應(yīng)時(shí)間都在逐漸降低.特別地,當(dāng)結(jié)果集不斷變大時(shí)響應(yīng)時(shí)間的下降速度也隨之加快.但是當(dāng)并行度超過20后,響應(yīng)時(shí)間的變化就變得不是非常明顯,原因在于數(shù)據(jù)庫系統(tǒng)的計(jì)算能力受制于服務(wù)器CPU的核心數(shù)目;而用于本文實(shí)驗(yàn)的服務(wù)器,在采用超線程技術(shù)后,可用的核心數(shù)目為24個(gè),當(dāng)并行度超過20后就有明顯的調(diào)度以及資源爭(zhēng)用問題,原因是,一方面受CPU核心數(shù)目的限制,另一方面本文也沒有將任務(wù)線程與相應(yīng)的CPU核心進(jìn)行綁定,因此可能出現(xiàn)多個(gè)任務(wù)線程共用一個(gè)核心的情況.

5 總結(jié)

本文提出了一種在分布式數(shù)據(jù)庫系統(tǒng)OceanBase中對(duì)傳統(tǒng)Hash join、nested loop join等算法以及semi-join算法的并行連接優(yōu)化方案,并且在OceanBase中進(jìn)行了實(shí)驗(yàn)驗(yàn)證.該優(yōu)化方案充分利用了分布式數(shù)據(jù)庫多數(shù)據(jù)節(jié)點(diǎn)和服務(wù)器多核的特點(diǎn).實(shí)驗(yàn)結(jié)果驗(yàn)證了并行連接優(yōu)化的有效性:在服務(wù)器線程總數(shù)內(nèi),傳統(tǒng)join算法和基于semi-join的傳統(tǒng)join算法執(zhí)行效率都有所提高.但是本文方案還有進(jìn)一步優(yōu)化的空間.如何根據(jù)數(shù)據(jù)分布信息動(dòng)態(tài)選擇使用何種join算法、如何實(shí)現(xiàn)線程資源的極大化利用、如何實(shí)現(xiàn)不同查詢處理節(jié)點(diǎn)間的交互、如何實(shí)現(xiàn)多個(gè)查詢處理節(jié)點(diǎn)間的協(xié)同工作,這些都將是以后研究的重點(diǎn).

[1]楊傳輝.大規(guī)模分布式存儲(chǔ)系統(tǒng)[M].北京:機(jī)械工業(yè)出版社,2013.

[2]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.

[3]ZHANG X F,CHEN L,WANG M.Effi cient multi-way theta-join processing using MapReduce[J].Proceedings of the VLDB Endowment,2012,11(5):1184-1195.

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

[5]ZHOU J R,ROSS K A.Implementing database operations using SIMD instructions[C]//Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data.2002:145-156.

[6]ZAHARIA M,CHOWDHURY M,FRANKLIN M J,et al.Spark:Cluster computing with working sets[C/OL]//Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.(2010-06-25)[2017-04-01].https://www.usenix.org/legacy/events/hotcloud10/tech/full papers/Zaharia.pdf?CFID=973306186& CFTOKEN=67460167.

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

[8]KIM C,PARK J,SATISH N,et al.CloudRAMSort:Fast and effi cient large-scale distributed RAM sort on shared-nothing cluster[C]//ACM SIGMOD International Conference on Management of Data.ACM,2012: 841-850.

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

[10]BONCZ P A,ZUKOWSKI M,NES N.MonetDB/X100:Hyper-pipelining query execution[C/OL]//Proceedings of the 2005 CIDR Conference on Innovative Data Systems Research.2005:225-237[2017-04-01]. https://www.researchgate.net/publication/45338800 MonetDBX 100 Hyper-Pipelining Query Execution.

(責(zé)任編輯:李藝)

Parallel join based on distributed system OceanBase

XU Shi-lei,WANG Lei,HU Hui-qi,QIAN Wei-ning,ZHOU Ao-ying
(School of Computer Science and Software Engineering,East China Normal University, Shanghai 200062,China)

With the rapid growth of application data and the continued development of distributed database systems,data storage in physical independent nodes has become a trend.In this trend,when the application needs to perform complex join queries,it inevitably generates a lot of network traffi c.Therefore,improving the effi ciency of join query in distributed system is a hot topic.Based on the analysis of the nested loop join, Hash join,semi-join in the OceanBase,this paper puts forward the optimization idea of using hardware resources reasonably and using multithread to execute join operations in parallel.We implement experiment on OceanBase with nested loop join algorithm,Hash join algorithm,semi-join algorithm respectively.The experimental results conf i rm that the effi ciency of join algorithm is positively related to parallelism in a certain number of threads.

query;semi-join;OceanBase;parallel join

TP392

A

10.3969/j.issn.1000-5641.2017.05.001

1000-5641(2017)05-0001-10

2017-06-19

2017年上海市青年科技英才揚(yáng)帆計(jì)劃(17YF1427800)

徐石磊,男,碩士研究生,研究方向?yàn)閿?shù)據(jù)存儲(chǔ)與數(shù)據(jù)挖掘.E-mail:xsl118857@sina.com.

胡卉芪,男,助理研究員,研究方向?yàn)閿?shù)據(jù)庫.E-mail:hqhu@dase.ecnu.edu.cn.