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

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

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

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

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

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

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

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

0 引言

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

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

論文的內(nèi)容組織如下:第1節(jié)簡要介紹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算法的查詢原理和基于semi-join的傳統(tǒng)join算法查詢原理;第3節(jié)介紹在OceanBase中對nested loop join、Hash join、semi-join等join算法的并行優(yōu)化設(shè)計;第4節(jié)從并行度對查詢效率的影響、并行度對各join算法執(zhí)行效率的影響,以及并行度對基于semi-join算法的各join算法執(zhí)行效率的影響等3方面進行全面的實驗驗證;第5節(jié)對本文進行總結(jié).

1 相關(guān)工作

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

傳統(tǒng)的連接算法有嵌套循環(huán)連接(nested loop join)算法、歸并排序連接(merge sort join)算法以及哈希連接(Hash join)算法.這3種算法的提出都有特定的問題背景和適用情況.伴隨著分布式數(shù)據(jù)庫的發(fā)展和普及,Bernstein等[2]又提出了semi-join(半連接)算法,此算法可大幅減少join過程中數(shù)據(jù)的傳輸代價.此外,在分布式系統(tǒng)中,伴隨著MapReduce、Spark等系統(tǒng)的發(fā)展,越來越多的分布式系統(tǒng)開始采用類似Map/Reduce[3]的計算模型,這類系統(tǒng)旨在通過任務(wù)分解的方式,減小join計算代價.下面簡要介紹這些算法的特點以及研究發(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種方式:復制外層循環(huán);復制內(nèi)層循環(huán);旋轉(zhuǎn)方式.在無共享架構(gòu)下,Spark結(jié)構(gòu)中采用廣播形式將數(shù)據(jù)傳到其他節(jié)點上[6].

1.2 merge sort join算法

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

1.3 Hash join算法

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

1.4 semi-join算法

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

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

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

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ū)動表,S作為被驅(qū)動表,MS是查詢處理節(jié)點,CS是數(shù)據(jù)存儲節(jié)點.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)將R1中的記錄逐一與S表中的所有記錄對比.如果對應(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的并行實現(xiàn)流程.并行設(shè)計體現(xiàn)在:首先,多個線程并行地從存儲節(jié)點讀取相應(yīng)范圍的數(shù)據(jù);然后處理線程并行執(zhí)行連接操作.

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

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

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

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

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

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

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

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

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

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

4 實驗分析

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

4.1 實驗軟件環(huán)境

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

圖6 OceanBase實驗環(huán)境物理拓撲Fig.6 Physical topology of OceanBase experimental environment

4.2 實驗硬件環(huán)境

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

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

4.3 實驗數(shù)據(jù)集

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

表2 測試表的模式Tab.2 The schema of the test table

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

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

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

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

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

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

實驗結(jié)果如圖7所示.

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

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

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

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

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

5 總結(jié)

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

[1]楊傳輝.大規(guī)模分布式存儲系統(tǒng)[M].北京:機械工業(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.

(責任編輯:李藝)

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年上海市青年科技英才揚帆計劃(17YF1427800)

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

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