高錦濤, 李戰(zhàn)懷, 杜洪濤, 劉文潔

(西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710129)

排序合并連接是數(shù)據(jù)庫(kù)系統(tǒng)的一種重要的連接實(shí)現(xiàn)方式[1,2],比哈希連接有著更廣泛的應(yīng)用.分布式環(huán)境下,數(shù)據(jù)量巨大,數(shù)據(jù)分片、分布存儲(chǔ),導(dǎo)致連接過(guò)程中存在大量網(wǎng)絡(luò)代價(jià),因此,高效地進(jìn)行大數(shù)據(jù)量排序合并連接,挑戰(zhàn)巨大.根據(jù)經(jīng)驗(yàn)及實(shí)驗(yàn)可得出,通常情況下,連接數(shù)據(jù)都可能存在無(wú)用數(shù)據(jù)塊,即不需要進(jìn)行連接的數(shù)據(jù).隨著數(shù)據(jù)量增大,無(wú)用數(shù)據(jù)塊比例可能越來(lái)越高,增加額外開(kāi)銷(xiāo),比如分布式環(huán)境下的網(wǎng)絡(luò)開(kāi)銷(xiāo),降低連接效率.

排序合并連接過(guò)程涉及取數(shù)據(jù)、排序、連接等步驟,集中式架構(gòu)下執(zhí)行這些步驟涉及CPU 和IO 代價(jià),分布式環(huán)境下由于數(shù)據(jù)分片、跨域存儲(chǔ),需要額外考慮網(wǎng)絡(luò)傳輸代價(jià).以O(shè)ceanBase 數(shù)據(jù)庫(kù)[3]為例,介紹分布式環(huán)境下集中式處理排序合并連接過(guò)程.OceanBase 中,連接數(shù)據(jù)分布在不同存儲(chǔ)節(jié)點(diǎn),連接之前,將分散的數(shù)據(jù)全部拉取到查詢(xún)節(jié)點(diǎn)本地進(jìn)行排序,排序完畢后進(jìn)行合并連接,這種排序合并連接策略存在如下問(wèn)題:(1)沒(méi)有對(duì)連接數(shù)據(jù)中無(wú)用數(shù)據(jù)塊進(jìn)行剪枝;(2)在查詢(xún)節(jié)點(diǎn)進(jìn)行集中式排序;(3)在查詢(xún)節(jié)點(diǎn)進(jìn)行集中式全局合并連接.在處理大數(shù)據(jù)量連接情況下,這些問(wèn)題造成大量網(wǎng)絡(luò)代價(jià)以及本地CPU 和IO 代價(jià).一些文獻(xiàn)[4-7]針對(duì)問(wèn)題2 和問(wèn)題3 提出了并行排序策略,將連接數(shù)據(jù)進(jìn)行分區(qū),分別遷移到多個(gè)進(jìn)程上進(jìn)行并行排序以及局部連接,最后全局合并連接的策略.但并沒(méi)有針對(duì)第1 個(gè)問(wèn)題給出很好的解決策略.

排序合并連接需要連接數(shù)據(jù)有序,通過(guò)比較兩邊連接數(shù)據(jù)是否符合連接條件決定輸出結(jié)果.在數(shù)據(jù)量大的情況下,兩邊連接數(shù)據(jù)大概率存在多個(gè)無(wú)效數(shù)據(jù)塊,這些數(shù)據(jù)塊不會(huì)產(chǎn)生輸出結(jié)果,但會(huì)產(chǎn)生大量額外代價(jià).如兩個(gè)有序序列A(-1000000,...-1,0,1,2,...,1000)和B(-2000000,...,-1000001,0,1,2,...,1000)進(jìn)行等值合并連接,按照傳統(tǒng)策略,需要至少比較1000000+1000×2 次.但A的子區(qū)間[-1000000,0]和B的子區(qū)間[-2000000,-1000001]無(wú)連接結(jié)果輸出,為無(wú)用數(shù)據(jù)塊,因此對(duì)于此區(qū)間內(nèi)的比較完全沒(méi)有必要,并且分布式環(huán)境下會(huì)增加額外昂貴的網(wǎng)絡(luò)代價(jià).如果能夠?qū)⑦@些無(wú)用數(shù)據(jù)提前進(jìn)行預(yù)處理,將其剪枝掉,將會(huì)大大減少連接代價(jià).圖1 為在OceanBase 中進(jìn)行排序合并連接實(shí)驗(yàn)時(shí)未剪枝(normal)和人工剪枝(prune)前后性能對(duì)比,連接對(duì)象為兩個(gè)數(shù)據(jù)量為1 000 000的字符串序列.其中,重復(fù)度指匹配連接的數(shù)據(jù)占原始數(shù)據(jù)的百分比.

Fig.1 Performance comparation of merge-join between prune and non-prune圖1 未剪枝與剪枝前后合并連接性能對(duì)比

可以看出,將無(wú)用數(shù)據(jù)剪枝后的連接性能遠(yuǎn)遠(yuǎn)優(yōu)于剪枝前的連接性能.而面對(duì)復(fù)雜的數(shù)據(jù)特征,需要成熟的剪枝策略.目前,排序合并連接優(yōu)化策略主要包括將取數(shù)據(jù)和排序過(guò)程由串行變?yōu)椴⑿?或者連接階段將搜索范圍縮小等措施.這些優(yōu)化手段基于參與連接的原始數(shù)據(jù)進(jìn)行后續(xù)處理,并沒(méi)有對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理.本文提出一種分布式數(shù)據(jù)庫(kù)下基于剪枝的并行排序合并連接策略(Pr_PSMJ),針對(duì)數(shù)據(jù)分布信息以及分區(qū)數(shù)據(jù)統(tǒng)計(jì)信息,構(gòu)造一種雙邊鄰接表(bilateral adjacency list,簡(jiǎn)稱(chēng)BAL),用來(lái)對(duì)連接數(shù)據(jù)中無(wú)用數(shù)據(jù)塊進(jìn)行剪枝,并保證最終連接結(jié)果的正確性.面對(duì)分布式環(huán)境,為了避免剪枝階段的數(shù)據(jù)遷移,剪枝不能以整體連接數(shù)據(jù)為單位,而是以連接數(shù)據(jù)涉及的分片為單位;剪枝完成后,利用BAL 計(jì)算出各個(gè)最佳本地連接執(zhí)行點(diǎn),指導(dǎo)分區(qū)數(shù)據(jù)的遷移,使數(shù)據(jù)移動(dòng)量最小;在連接階段,通過(guò)BAL 保證各個(gè)本地連接執(zhí)行節(jié)點(diǎn)的獨(dú)立性,可以輕松并行執(zhí)行整個(gè)連接過(guò)程,并且連接點(diǎn)內(nèi)部能夠利用多核環(huán)境進(jìn)行局部并行排序合并連接.在分布式大數(shù)據(jù)量合并連接情況下,Pr_PSMJ策略能夠有效減少網(wǎng)絡(luò)開(kāi)銷(xiāo),并提高連接效率.

本文的主要貢獻(xiàn)如下.

1)給出一種分布式環(huán)境下基于剪枝的并行排序合并連接策略(Pr_PSMJ),能夠?qū)B接數(shù)據(jù)中無(wú)用數(shù)據(jù)塊提前剪枝,并以最小數(shù)據(jù)遷移量完成本地并行合并連接,提高整體連接效率.

2)給出Pr_PSMJ 內(nèi)容,并給出剪枝功能、本地連接中心以及切分因子構(gòu)造方式.

3)給出基于Pr_PSMJ 的合并連接算法,并與經(jīng)典算法在時(shí)間和空間上進(jìn)行對(duì)比,給出算法正確性、效率性以及適應(yīng)性分析,并結(jié)合實(shí)例給出Pr_PSMJ 算法工作過(guò)程.

4)在淘寶開(kāi)源分布式數(shù)據(jù)庫(kù)OceanBase 中實(shí)現(xiàn)Pr_PSMJ 策略,并給出實(shí)驗(yàn)評(píng)估,驗(yàn)證Pr_PSMJ 策略的高效性.

本文第1 節(jié)介紹排序合并連接相關(guān)工作.第2 節(jié)給出并行排序合并的通用框架以及相關(guān)定義.第3 節(jié)給出Pr_PSMJ 策略的內(nèi)容,包括剪枝功能、本地連接中心以及切分因子構(gòu)造.第4 節(jié)給出基于Pr_PSMJ 策略的合并連接算法以及其他兩個(gè)算法.第5 節(jié)給出算法正確性、效率性以及適應(yīng)性的分析,并給出示例.第6 節(jié)給出實(shí)驗(yàn)評(píng)估.第7 節(jié)給出本文的結(jié)論和未來(lái)工作.

1 相關(guān)工作

目前,針對(duì)排序合并連接的研究主要分為非阻塞式合并排序連接、多核環(huán)境下排序合并連接、分布式環(huán)境下排序合并連接.下面給出具體闡述以及相關(guān)討論.

?非阻塞式合并排序連接

排序合并連接是傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù),如Oracle、Sql Server、DB2 等的一項(xiàng)重要連接實(shí)現(xiàn)方式,其在真正執(zhí)行連接前,需要保證連接數(shù)據(jù)有序,但排序阻塞連接執(zhí)行.一些策略[8-10]假設(shè)連接數(shù)據(jù)已經(jīng)準(zhǔn)備好,假設(shè)前提是連接數(shù)據(jù)和連接執(zhí)行都在本地,但面對(duì)大數(shù)據(jù)量或者網(wǎng)絡(luò)應(yīng)用,連接數(shù)據(jù)可能需要耗費(fèi)較多代價(jià)得到.為了提高連接效率,一些文獻(xiàn)提出非阻塞式合并排序連接[11-15].文獻(xiàn)[13]提出一種PMJ(progressive merge join)策略,保證快速給出連接的前幾條數(shù)據(jù),其他數(shù)據(jù)異步排序.文獻(xiàn)[16]提出一種HMJ(hash-merge join)算法,分為兩個(gè)步驟:哈希和合并,哈希階段對(duì)已經(jīng)獲得的數(shù)據(jù)利用內(nèi)存哈希連接算法快速得到連接結(jié)果,如果連接數(shù)據(jù)出現(xiàn)阻塞,利用合并連接產(chǎn)生結(jié)果.其他合并連接策略包括流水線(xiàn)技術(shù)[17]、并行非阻塞連接[18]等.雖然這些策略能夠提高發(fā)生阻塞時(shí)的連接效率,但并沒(méi)有對(duì)連接原始數(shù)據(jù)進(jìn)行剪枝.

?多核環(huán)境下排序合并連接

隨著硬件的快速發(fā)展,多核機(jī)器越來(lái)越普遍.為了充分利用多核環(huán)境下并行的執(zhí)行優(yōu)點(diǎn),一系列并行執(zhí)行策略[4-7]被提出來(lái).文獻(xiàn)[4]提出使用多核(4 096 個(gè)核),利用MPI 進(jìn)行合并連接的實(shí)施環(huán)境,通過(guò)合理規(guī)劃網(wǎng)絡(luò)資源,將排序和連接分離提高連接效率.文獻(xiàn)[5]提出一種P-MPSM 算法,利用多核對(duì)連接數(shù)據(jù)并行排序,并對(duì)左側(cè)連接數(shù)據(jù)分區(qū),并利用直方圖進(jìn)行重分區(qū),處理數(shù)據(jù)傾斜問(wèn)題,利用插補(bǔ)搜索[19,20],縮小連接范圍,但插補(bǔ)搜索假設(shè)搜索的對(duì)象數(shù)據(jù)分布均勻.

?分布式環(huán)境下排序合并連接

大數(shù)據(jù)時(shí)代,分布式數(shù)據(jù)庫(kù)是處理和管理海量數(shù)據(jù)的利器,如Google 的spanner[21]、淘寶的OceanBase 數(shù)據(jù)庫(kù)[3]等.分布式環(huán)境下,數(shù)據(jù)分片、分布存儲(chǔ),排序合并連接在取數(shù)據(jù)、排序、連接各個(gè)階段涉及的數(shù)據(jù)量可能都較大,并且存在昂貴的網(wǎng)絡(luò)傳輸代價(jià),對(duì)于進(jìn)行高效排序合并連接提出更大挑戰(zhàn).淘寶的OceanBase 數(shù)據(jù)庫(kù)中,排序合并連接過(guò)程為:并行獲取連接對(duì)象的分區(qū)數(shù)據(jù),并將分區(qū)數(shù)據(jù)發(fā)送到查詢(xún)節(jié)點(diǎn).雖然采用流水線(xiàn)執(zhí)行方式,但存在單點(diǎn)內(nèi)存全量排序的缺點(diǎn),導(dǎo)致對(duì)于大數(shù)據(jù)量表的等值連接,效率較差(圖1).文獻(xiàn)[22]針對(duì)OceanBase讀寫(xiě)分離引起的數(shù)據(jù)合并代價(jià),提出一種基線(xiàn)與增量數(shù)據(jù)分離架構(gòu)下的排序歸并連接優(yōu)化算法,通過(guò)數(shù)據(jù)遷移達(dá)到連接數(shù)據(jù)的本地排序和連接.

?討論

非阻塞式并行連接能夠減少連接時(shí)等待時(shí)間,但分布式環(huán)境下,網(wǎng)絡(luò)傳輸代價(jià)為主宰代價(jià),因此這些策略本質(zhì)上并沒(méi)有太多提高排序、連接效率.雖然多核環(huán)境和分布式環(huán)境下能夠利用并行策略提高排序合并連接效率,但沒(méi)有對(duì)無(wú)用數(shù)據(jù)塊進(jìn)行預(yù)處理,造成額外代價(jià).本文提出的Pr_PSMJ 策略能夠預(yù)先對(duì)無(wú)用數(shù)據(jù)進(jìn)行剪枝,減少局部連接和全局連接代價(jià),并能夠以最小數(shù)據(jù)移動(dòng)量完成本地并行合并連接,提高整體的執(zhí)行效率.

2 預(yù)備知識(shí)

為了針對(duì)分布式環(huán)境闡述本文提出的Pr_PSMJ 策略,總結(jié)出一種通用的分布式框架,如圖2 所示.

Fig.2 General distributed architecture圖2 通用分布式框架

對(duì)各部分解釋如下.

?Query server(QS):負(fù)責(zé)接收用戶(hù)輸入的SQL 語(yǔ)句,并進(jìn)行語(yǔ)法解析(parser)、邏輯計(jì)劃生成(logical_planner)、物理計(jì)劃生成(physical_planner)、范圍分發(fā)(distribute range)、合并連接(merge join)等功能.合并連接的最終執(zhí)行發(fā)生在QS.

?Metadata server(MS):負(fù)責(zé)提供數(shù)據(jù)分片存儲(chǔ)位置等元數(shù)據(jù)信息.

?Storage servers(SS):負(fù)責(zé)存儲(chǔ)、操作(如查詢(xún))數(shù)據(jù).存儲(chǔ)模式為分布式,類(lèi)似于BigTable[23],每一個(gè)分布

式節(jié)點(diǎn)存儲(chǔ)一個(gè)表的部分或全部信息,并部署一個(gè)線(xiàn)程池{Wi},動(dòng)態(tài)地分配所需線(xiàn)程,完成對(duì)應(yīng)任務(wù).以下內(nèi)容針對(duì)連接語(yǔ)義(1)進(jìn)行闡述,即R和S兩個(gè)關(guān)系在連接屬性x上進(jìn)行等值連接.

定義1(數(shù)據(jù)模式).數(shù)據(jù)邏輯上以表為單位,物理上將表進(jìn)行分片,分布存儲(chǔ)在各個(gè)SS上.定義為公式(2).

其中,DS表示數(shù)據(jù)模式;ti表示表;Tj表示表ti的一個(gè)分區(qū),通常,Tj大小固定(Hbase 默認(rèn)64MB);SSk表示Tj的存儲(chǔ)位置;Tj所有數(shù)據(jù)的并集為ti;f表示兩個(gè)分區(qū)的交集,如果按照主鍵進(jìn)行分區(qū),則f為空集.

定義2(排序合并連接[24]).數(shù)據(jù)庫(kù)的一種連接實(shí)現(xiàn)方式,適合自然連接和等值連接.針對(duì)公式(1)中的兩個(gè)關(guān)系R(y,x)和S(x,z),其中,x為兩關(guān)系的連接屬性,y和z分別為其他屬性,形式化定義排序合并連接見(jiàn)公式(3).

其中,MJ表示排序合并連接;Me表示合并操作,即將兩個(gè)有序的序列按照連接條件合并成一個(gè)有序序列;So表示對(duì)連接屬性上的數(shù)據(jù)進(jìn)行排序操作,其輸出為有序數(shù)據(jù),θ為連接條件.

定義3(并行排序合并連接).將定義2 中的So操作以并行方式實(shí)現(xiàn),為圖1 中的{Wi}分配排序任務(wù)以及執(zhí)行排序任務(wù)的線(xiàn)程數(shù).將Me操作改造為并行操作PMe,即首先進(jìn)行局部Me,然后進(jìn)行全局Me.形式化定義為公式(4).

其中,PSo表示將關(guān)系R和關(guān)系S相關(guān)的分區(qū)數(shù)據(jù)中連接屬性x上的排序任務(wù)分別分配ni和nj個(gè)工作線(xiàn)程進(jìn)行并行排序,其中,Wi和Wj分別表示分布式節(jié)點(diǎn)上的線(xiàn)程池,N和M表示R和S相關(guān)分區(qū)數(shù)據(jù)所在的分布式節(jié)點(diǎn)的個(gè)數(shù),Ri和Sj分別表示第i個(gè)節(jié)點(diǎn)和第j個(gè)節(jié)點(diǎn)上R和S的分區(qū)個(gè)數(shù),且num(Ri)=ni,num(Sj)=nj.執(zhí)行PMe的步驟包括:

(1)M1表示將各個(gè)Ri包含的分片遷移到合適的Si所在節(jié)點(diǎn).

(2)M2表示將各個(gè)Sj包含的分片遷移到合適的Ri所在的節(jié)點(diǎn).

(3)如果遷移后的節(jié)點(diǎn)完備(lkis complete),即可開(kāi)始本地合并連接,完備的節(jié)點(diǎn)之間執(zhí)行不阻塞.

問(wèn)題定義.公式(4)中,PSo操作涉及CPU、IO 代價(jià),PMe操作涉及CPU、IO 以及網(wǎng)絡(luò)代價(jià).這兩部分代價(jià)與參與PSo和PMe操作的數(shù)據(jù)量直接相關(guān),并且決定PSMJ的效率.因此,本文需要解決的問(wèn)題為:減少PSo和PMe操作中涉及到的不必要數(shù)據(jù),最小化數(shù)據(jù)移動(dòng),提升PSMJ效率.形式化定義見(jiàn)公式(5).

其中,prune功能將R和S中以塊為單位進(jìn)行無(wú)用數(shù)據(jù)塊剪枝,剪枝后,最小化公式(4)中的M1和M2.

3 基于剪枝的并行排序合并連接策略

分布式數(shù)據(jù)庫(kù)中,數(shù)據(jù)分片、分布存儲(chǔ),在進(jìn)行并行排序合并連接過(guò)程中,首先對(duì)分散的數(shù)據(jù)進(jìn)行局部排序[5]或者全局排序[14],如果數(shù)據(jù)量巨大,將涉及大量網(wǎng)絡(luò)開(kāi)銷(xiāo).為充分利用分散數(shù)據(jù)局部排序得到的有序數(shù)據(jù)范圍,進(jìn)行無(wú)用數(shù)據(jù)塊的剪枝處理,本文提出高效的基于剪枝的并行排序合并連接策略(Pr_PSMJ),目的是解決公式(5)中給出的問(wèn)題.中心思想是,高效構(gòu)造雙邊鄰接表(BAL),實(shí)現(xiàn)對(duì)連接數(shù)據(jù)的剪枝處理(公式(5)中的prune功能),提前去除無(wú)用數(shù)據(jù),并通過(guò)BAL 實(shí)現(xiàn)本地并行合并連接過(guò)程中數(shù)據(jù)遷移量最小(min(M1)和min(M2)).下面就Pr_PSMJ 策略?xún)?nèi)容以及雙邊鄰接表(BAL)進(jìn)行詳細(xì)闡述.

圖3 為基于Pr_PSMJ 策略改造后的處理框架,標(biāo)紅的模塊為新添加部分.改造點(diǎn)包括:(1)添加剪枝(prune)功能模塊,在范圍分發(fā)之前,將多余的范圍剪枝掉,即去除連接執(zhí)行時(shí)多余的數(shù)據(jù)塊;(2)將圖2 中的distribute range 改造為distribute BAL,功能從分發(fā)數(shù)據(jù)范圍改為分發(fā)雙邊鄰接表(BAL);(3)在每一個(gè)SS上構(gòu)建一個(gè)本地連接中心(local_join_center,簡(jiǎn)稱(chēng)LJC),作用是以最小代價(jià)完成一部分連接任務(wù),LJC 的計(jì)算詳見(jiàn)第3.2 節(jié).LJC 包括兩個(gè)子模塊:collector 模塊,根據(jù)prune 模塊生成的雙邊鄰接表收集需要在此SS完成的連接任務(wù)中包括的數(shù)據(jù)塊;allocator 模塊,為需要連接的數(shù)據(jù)塊分配合適的資源以供并行執(zhí)行.

Fig.3 Modified distributed architecture based on Pr_PSMJ strategy圖3 基于Pr_PSMJ 策略改造后的分布式架構(gòu)

定義4.基于定義3 給出基于Pr_PSMJ 的排序合并連接定義,見(jiàn)公式(6).

添加剪枝(prune,簡(jiǎn)稱(chēng)Pr)操作提取R和S對(duì)應(yīng)分區(qū)數(shù)據(jù)的有序序列范圍,建立BAL,利用剪枝策略將無(wú)用數(shù)據(jù)塊預(yù)先去除.并將BAL 中各個(gè)項(xiàng)分發(fā)給對(duì)應(yīng)SS.進(jìn)行本地合并后,由QS完成全局合并.

3.1 剪枝功能

如圖3 所示,剪枝功能(prune)作用為預(yù)先將無(wú)用數(shù)據(jù)塊去除,功能包括雙邊鄰接表(BAL)的構(gòu)造(第3.1.1節(jié))、邊界處理(第3.1.2 節(jié))以及負(fù)載均衡(第3.1.3 節(jié)).

3.1.1 BAL 構(gòu)造

雙邊鄰接表(BAL)的作用是完成剪枝功能,并利用BAL 的結(jié)構(gòu)特點(diǎn),以每一個(gè)BAL 項(xiàng)為單位,將整個(gè)分布式排序合并連接分割成獨(dú)立的可并行執(zhí)行的單元,結(jié)構(gòu)如圖4 所示.BAL 分成3 部分:左部、中部、右部.其中,左部關(guān)聯(lián)左連接關(guān)系R相關(guān)的全部數(shù)據(jù)塊范圍集合{r1,...,rm},中部為邊界范圍集合{ra1,...,ran},右部為剪枝后剩余的左連接關(guān)系R和右連接關(guān)系S對(duì)應(yīng)的數(shù)據(jù)塊范圍.BAL 以中部各個(gè)元素作為候選本地連接中心(LJC),剪枝完成后,以中部對(duì)應(yīng)的不為空的右部元素作為分發(fā)BAL 的內(nèi)容.{ra1,...,ran}為邊界范圍集合,{r1,...,rm}為經(jīng)過(guò)定義4 中PSo操作后得到的關(guān)系R中有序數(shù)據(jù)塊的范圍集合.{s1,...,sn}為經(jīng)過(guò)PSo操作后得到的關(guān)系S中的有序數(shù)據(jù)塊范圍集合.{SS1,...,SSk}為圖2 中的存儲(chǔ)節(jié)點(diǎn)集合.{size1,...,sizep}為數(shù)據(jù)塊范圍集合對(duì)應(yīng)的大小.BAL 左部表示關(guān)系R相關(guān)全部數(shù)據(jù)塊的范圍、該范圍所在的位置以及對(duì)應(yīng)數(shù)據(jù)量(根據(jù)直方圖[12]或者樣本估計(jì)[25]等策略得出的估計(jì)值),用三元組(r,l,size)表示.右部表示經(jīng)過(guò)剪枝操作后剩余的集合{r}和集合{s}的部分,用四元組(s,SS,sub({r}),size)表示,其中sub({r})表示與s完成本地連接所需的{r}的子集.注意,每一個(gè){ra}元素并不一定有左部或者右部.

Fig.4 Architecture of BAL圖4 BAL 架構(gòu)

BAL 構(gòu)造包括{ra}構(gòu)造、左部構(gòu)造和右部構(gòu)造這3 個(gè)部分,構(gòu)造完成后的BAL 架構(gòu)如圖4.具體內(nèi)容如下.

?構(gòu)造{ra}:首先獲得R對(duì)應(yīng)的數(shù)據(jù)塊范圍.做法為:在R相關(guān)的SS節(jié)點(diǎn)中進(jìn)行PSo操作后得到有序數(shù)據(jù)塊,同時(shí)獲取其范圍,形成集合{r},根據(jù){r}得出{r}的超集Sr,設(shè)置切分因子q(設(shè)定方法詳見(jiàn)第3.3 節(jié)),將Sr切分成{ra}集合.經(jīng)過(guò)以上處理,形成圖4 中{ra}.

?構(gòu)造左部:將已經(jīng)獲得的{r}映射到{ra}中,即將{r}中的每一個(gè)元素與{ra}元素取交集,如果交集不為空,則說(shuō)明這個(gè)元素屬于當(dāng)前的ra元素.需要滿(mǎn)足{r}中的每一個(gè)元素的全部或者部分(r跨越{ra}某個(gè)元素的邊界)只屬于{ra}中的一個(gè)元素.經(jīng)過(guò)以上處理,形成圖4 的左部,用{l_r}表示,其中每個(gè)元素為由(ri,SSj,sizek)組成的鏈表,每個(gè){l_r}元素隸屬于一個(gè){ra}元素.

?構(gòu)造右部:使用和獲取{r}同樣的方法獲取右連接關(guān)系對(duì)應(yīng)的數(shù)據(jù)塊范圍{s},利用{s}中的每一個(gè)元素s探測(cè)當(dāng)前形成的BAL,形成兩階段探測(cè):

?首次探測(cè){ra},s與{ra}的對(duì)應(yīng)關(guān)系為1 對(duì)多或者1 對(duì)1:如果為前者,則將s進(jìn)行拆分,拆分后的子集映射到對(duì)應(yīng){ra}元素,這個(gè)過(guò)程中會(huì)將s的一部分無(wú)用數(shù)據(jù)舍棄;如果為后者,則直接映射到當(dāng)前ra元素.

?再次探測(cè)s或者其子集在當(dāng)前ra元素中對(duì)應(yīng)的{l_r}中是否有對(duì)應(yīng)的{r}與之相交:如果沒(méi)有,則將這個(gè)s的全部或部分舍棄;如果有,則形成(s,SS,sub({r}),size)四元組;如果有多個(gè),則形成鏈表.整個(gè)右部用{r_s}表示.

構(gòu)造完成的BAL 已經(jīng)對(duì)無(wú)用的{r}和{s}數(shù)據(jù)塊進(jìn)行了剪枝,并且形成了以{r_s}中元素為單位的本地連接執(zhí)行單元.

3.1.2 邊界處理

由于{ra}是對(duì){r}的超集進(jìn)行切割形成的,因此在構(gòu)造左部和右部時(shí),可能存在{r}和{s}的元素跨越{ra}中多個(gè)元素,因此需要處理這種跨邊界問(wèn)題.處理策略為:以{ra}為基準(zhǔn),如果{r}或者{s}中的元素r或者s跨越了某個(gè)或多個(gè){ra},則用{ra}的被跨越元素的邊界值對(duì)r或者s進(jìn)行切分,切分后,各個(gè)部分歸屬于其就近的較小{ra}.

3.1.3 負(fù)載均衡

負(fù)載均衡對(duì)于分布式數(shù)據(jù)庫(kù)連接操作的并行執(zhí)行效率至關(guān)重要,如文獻(xiàn)[16,26,27]提出的并行環(huán)境下的負(fù)載均衡策略,能夠有效處理某些情況,但并不適應(yīng)分布式環(huán)境下的排序合并連接操作.Pr_PSMJ 策略通過(guò)BAL 達(dá)到負(fù)載均衡目的.BAL 右部{r_s}中每一個(gè)元素對(duì)應(yīng)一個(gè)連接執(zhí)行點(diǎn),多個(gè)元素之間并行執(zhí)行,需要保證每個(gè)執(zhí)行點(diǎn)的負(fù)載均衡.策略為選擇合適的切分因子(詳見(jiàn)第3.3 節(jié)),并考慮BAL 的每一個(gè)右部涉及到的數(shù)據(jù)量分布盡量均勻,達(dá)到各個(gè)執(zhí)行節(jié)點(diǎn)的負(fù)載均衡以及降低本地連接時(shí)數(shù)據(jù)移動(dòng)的網(wǎng)絡(luò)代價(jià).

3.2 本地連接中心

對(duì)連接關(guān)系完成剪枝操作后,需要根據(jù)形成的BAL 的右部,執(zhí)行圖3 中的BAL 分發(fā)功能(distribute BAL),將右部各個(gè)元素發(fā)送到對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn)(SS)上執(zhí)行本地連接.為了保證連接的完備性,需要消耗網(wǎng)絡(luò)代價(jià)將一部分?jǐn)?shù)據(jù)塊遷移到執(zhí)行本地連接的SS節(jié)點(diǎn)上,這個(gè)節(jié)點(diǎn)稱(chēng)為L(zhǎng)JC.被選擇為L(zhǎng)JC 的SS節(jié)點(diǎn)通過(guò)collector 模塊,根據(jù)接收到的BAL 右部元素對(duì)應(yīng)的各個(gè)四元組,將不屬于這個(gè)LJC 的四元組對(duì)應(yīng)的R和S的數(shù)據(jù)塊收集到本地,然后利用allocator 模塊為收集完備的項(xiàng)分配對(duì)應(yīng)的資源完成本地連接.為最小化遷移代價(jià),提出公式(7)來(lái)計(jì)算LJC.

公式(7)目的為選擇本地參與連接的R和S數(shù)據(jù)塊大小之和最大,其中,x為第k個(gè)右部元素中所有四元組中涉及的執(zhí)行節(jié)點(diǎn)的個(gè)數(shù),subi({s})和subi({r})分別表示第k個(gè)右部元素中關(guān)聯(lián)的執(zhí)行節(jié)點(diǎn)中關(guān)于關(guān)系R和S本地的的數(shù)據(jù)塊個(gè)數(shù).利用公式(7)依次計(jì)算出所有{ra}相關(guān)的執(zhí)行節(jié)點(diǎn),并由圖3 中BAL 分發(fā)功能從QS分發(fā)到各個(gè)執(zhí)行節(jié)點(diǎn)執(zhí)行本地連接,發(fā)送過(guò)程和執(zhí)行過(guò)程異步進(jìn)行.

3.3 切分因子構(gòu)造

切分因子作用為構(gòu)造BAL 中的{ra}部分進(jìn)而限制{r}在BAL 左部的分布({l_r})以及BAL 右部{r_s}的形成,一定程度上決定了并行執(zhí)行合并連接的節(jié)點(diǎn)數(shù)、負(fù)載均衡以及數(shù)據(jù)遷移量.圖5 闡述切分因子(q)在BAL 關(guān)聯(lián)的限制鏈(即鏈中前驅(qū)元素決定后繼元素)中的位置,其作用范圍為{ra}和{l_r}兩個(gè)節(jié)點(diǎn),但間接作用于其他后繼節(jié)點(diǎn).下面詳細(xì)闡述切分因子的構(gòu)造方法.

Fig.5 Restriction chain in BAL圖5 BAL 限制鏈

構(gòu)造切分因子所需參數(shù)包括{r}:{SSr}:{r_size},{s}:{SSs}:{s_size},其中,{SSr},{SSs}分別表示{r}和{s}對(duì)應(yīng)的存儲(chǔ)位置,{r_size}和{s_size}分別表示{r}和{s}中的每一個(gè)元素對(duì)應(yīng)的數(shù)據(jù)量大小.這些參數(shù)在構(gòu)造q之前已經(jīng)具備.圖5 可以看出,q的選擇最終決定了{(lán)r_s}的構(gòu)造,并且在使用BAL 指導(dǎo)數(shù)據(jù)遷移時(shí),根據(jù)公式(7),選擇的是{r_s}中每一個(gè)元素所包含的所有{r}和{s}子集中在某一個(gè)執(zhí)行節(jié)點(diǎn)里數(shù)據(jù)量最多的一個(gè).由于構(gòu)造{r_s}是在選擇q之后進(jìn)行的,因此為盡量最大化公式(7)并減少數(shù)據(jù)遷移,進(jìn)行如下步驟選擇q.

?提取{SSr}和{SSs}中每一個(gè)存儲(chǔ)位置涉及的{r}和{s}子集以及對(duì)應(yīng)的子集個(gè)數(shù),形成{loc:num:range}.

?根據(jù){r}和{s}以及{r_size}和{s_size}計(jì)算出range對(duì)應(yīng)的數(shù)據(jù)量之和,形成{loc:num:sum}.

?計(jì)算avgnum=avg(num)以及avgsum=avg(sum).

?由于針對(duì)分布式環(huán)境,因此以減少網(wǎng)絡(luò)傳輸代價(jià)為首要目標(biāo),得出如下q計(jì)算公式.

從公式(8)可以看出,如果連接數(shù)據(jù)分布不均勻,則得出的q會(huì)相對(duì)較大,使{ra}粒度相對(duì)較小,能夠?qū)⒇?fù)載不均衡的節(jié)點(diǎn)關(guān)聯(lián)的負(fù)載分?jǐn)偟狡渌?jié)點(diǎn),較好地解決數(shù)據(jù)傾斜問(wèn)題.

4 算 法

傳統(tǒng)的排序合并連接優(yōu)化策略基于連接對(duì)象關(guān)聯(lián)的原始連接數(shù)據(jù)進(jìn)行取數(shù)據(jù)、排序、連接等操作的優(yōu)化,而忽略原始連接數(shù)據(jù)本身存在的無(wú)用數(shù)據(jù)塊.在分布式環(huán)境下進(jìn)行大數(shù)據(jù)量排序合并連接時(shí),這些無(wú)用數(shù)據(jù)塊將造成大量額外不必要代價(jià).本文提出的基于剪枝的并行排序合并連接策略(Pr_PSMJ)通過(guò)構(gòu)造雙邊鄰接表(BAL),能夠?qū)υ歼B接數(shù)據(jù)進(jìn)行高效剪枝,提前去除無(wú)用數(shù)據(jù)塊,并通過(guò)公式(7)選擇合適的LJC,最小化數(shù)據(jù)遷移代價(jià).為了顯示Pr_PSMJ 算法的優(yōu)勢(shì),闡述3 種算法進(jìn)行對(duì)比,包括:uPr_uLJ(無(wú)剪枝無(wú)本地連接)算法,如OceanBase[3]中的排序合并連接算法;uPr_LJ(無(wú)剪枝有本地連接),如文獻(xiàn)[5]提出的B-MPSM 算法以及本文提出的Pr_LJC(有剪枝基于LJC 的本地連接)算法.下面分別進(jìn)行介紹.

uPr_uLJ 算法.

uPr_uLJ 算法首先獲取連接關(guān)系R和S對(duì)應(yīng)的元數(shù)據(jù)信息(第1 行),然后根據(jù)元數(shù)據(jù)信息并行的獲取到對(duì)應(yīng)的數(shù)據(jù)塊(第2 行),并將獲取到的數(shù)據(jù)塊全部發(fā)送到查詢(xún)節(jié)點(diǎn)(第3 行)完成全局排序(第4 行),最后在查詢(xún)節(jié)點(diǎn)完成全局合并連接,將結(jié)果返回(第5 行、第6 行).

uPr_LJ 算法.

uPr_LJ 算法的第1 行、第2 行與uPr_uLJ 算法相同.為完成本地連接,在并行獲取到數(shù)據(jù)塊后,為關(guān)系R對(duì)應(yīng)的每一個(gè)數(shù)據(jù)塊分配一個(gè)工作線(xiàn)程(第3 行),個(gè)數(shù)取決于較大的數(shù)據(jù)塊個(gè)數(shù),然后將關(guān)系S中的每一個(gè)數(shù)據(jù)塊依次發(fā)送到工作線(xiàn)程中(第4 行).對(duì)于每一個(gè)工作線(xiàn)程,為完成其本地連接,需要將此線(xiàn)程內(nèi)DR需要連接的所有SR數(shù)據(jù)塊遷移到本地完成本地連接(第5 行～第7 行).第8 行、第9 行與uPr_uLJ 算法的第5 行、第6 行相同.

Pr_LJC 算法.

Pr_LJC 算法的第1 行、第2 行與uPr_LJ 算法的第1 行、第2 行相同.不同的是,需要通過(guò)本地并行排序的結(jié)果獲取對(duì)應(yīng)數(shù)據(jù)塊的范圍,并將它們發(fā)送到查詢(xún)節(jié)點(diǎn)(第3 行、第4 行).在查詢(xún)節(jié)點(diǎn),根據(jù)第3.1.1 節(jié)的內(nèi)容生成BAL(第5 行),根據(jù)第3.2 節(jié)的內(nèi)容獲得BAL 右部對(duì)應(yīng)的最佳本地執(zhí)行點(diǎn)(LJC)(第6 行).將BAL 的右部分發(fā)到對(duì)應(yīng)的LJC(第7 行),對(duì)于每一個(gè)LJC,根據(jù)接收到的BAL 右部?jī)?nèi)容將對(duì)應(yīng)的數(shù)據(jù)塊拉取到本地,完成本地連接任務(wù)(第8 行～第10 行).第11 行、第12 行與uPr_LJ 算法的第9 行、第10 行相同.

5 算法分析

5.1 算法正確性

對(duì)于非剪枝、非局部連接算法(uPr_uLJ)以及非剪枝局部連接算法(uPr_LJ),其連接策略為:將連接的兩表根據(jù)連接屬性將參與連接的數(shù)據(jù)全部拉取到QS 本地或者部分SS 本地,進(jìn)行全局或者局部排序,然后進(jìn)行全局或者局部合并連接,最后由QS 進(jìn)行合并連接.兩種算法涉及的數(shù)據(jù)來(lái)自原始連接數(shù)據(jù),能夠保證連接正確性.對(duì)于基于Pr_PSMJ 策略的Pr_LJC 算法,為了保證連接效率,通過(guò)剪枝去除連接數(shù)據(jù)中無(wú)用數(shù)據(jù)塊,通過(guò)基于LJC 的本地并行連接提高連接效率.在這個(gè)過(guò)程中,算法通過(guò)如下的細(xì)節(jié)保證連接的正確性.

?保證對(duì)原始連接數(shù)據(jù)進(jìn)行剪枝不影響最終結(jié)果的正確性.

兩表原始連接數(shù)據(jù)分片范圍分別為{r}和{s},通過(guò)各自范圍內(nèi)數(shù)據(jù)的并集能夠得到原始連接數(shù)據(jù).根據(jù)構(gòu)造的BAL(構(gòu)造過(guò)程見(jiàn)第3.1.1 節(jié))對(duì){r}和{s}進(jìn)行剪枝操作,剪枝過(guò)程為:首先將{r}合并后得到的范圍根據(jù)切分因子(見(jiàn)第3.3 節(jié))進(jìn)行劃分,得到{ra};然后將{r}中的元素映射到對(duì)應(yīng){ra}內(nèi),用{s}中的某個(gè)元素s首先對(duì){ra}進(jìn)行匹配,如果匹配到,則進(jìn)一步匹配其中的{r}元素,如果也匹配到,則保留s.如果這兩次匹配中任何一個(gè)不成立,則舍棄s.當(dāng)某一個(gè)BAL 右部不再增長(zhǎng)時(shí),說(shuō)明此右部對(duì)應(yīng)的范圍內(nèi)的數(shù)據(jù)已經(jīng)完備,剩余的{r}和{s}為該范圍內(nèi)進(jìn)行局部連接的數(shù)據(jù).基于公式(9),其中N為{ra}內(nèi)元素個(gè)數(shù),可以得到在每一個(gè){ra}元素內(nèi)進(jìn)行的利用{s}中的元素對(duì){ra}元素內(nèi)的{r}元素進(jìn)行剪枝是互相獨(dú)立的;同理,對(duì)于每一個(gè){ra}元素內(nèi)的剪枝活動(dòng),去除的{r}元素和{s}元素相對(duì)于其他{ra}元素也是獨(dú)立的,并且每一個(gè){ra}內(nèi)的{r}元素是完全的且獨(dú)立的,剪枝掉的數(shù)據(jù)塊確實(shí)為無(wú)用數(shù)據(jù)塊,因此整個(gè)剪枝活動(dòng)對(duì)于排序連接的正確性沒(méi)有影響.

?保證剪枝后的本地并行連接的正確性.

由于每個(gè)非空BAL 的連接是獨(dú)立且完備的,并且對(duì)應(yīng)的連接數(shù)據(jù)完全來(lái)自基于公式(9)已經(jīng)證明正確的數(shù)據(jù)基礎(chǔ)上進(jìn)行的,并且最終由QS完成全局連接,因此能夠保證在實(shí)行本地并行連接后最終連接結(jié)果的正確性.

5.2 算法效率性

針對(duì)3 種算法進(jìn)行計(jì)算和存儲(chǔ)方面的效率評(píng)估.uPr_uLJ 算法涉及的連接步驟包括取數(shù)據(jù)(fetch data,簡(jiǎn)稱(chēng)fd)、全局排序(global sort,簡(jiǎn)稱(chēng)gs)以及全局合并連接(global merge join,簡(jiǎn)稱(chēng)gmj),uPr_LJ 算法涉及的連接步驟包括取數(shù)據(jù)(fd)、局部并行排序(local parallel sort,簡(jiǎn)稱(chēng)lps)、本地連接(local merge join,簡(jiǎn)稱(chēng)lmj)、全局結(jié)果合并(global result merge,簡(jiǎn)稱(chēng)grm),Pr_LJC 算法涉及的連接步驟包括取數(shù)據(jù)(fd)、局部并行排序(lps)、剪枝(prune,簡(jiǎn)稱(chēng)pr)、基于LJC 的本地連接(local merge join based on LJC,簡(jiǎn)稱(chēng)lmjLJC)、全局結(jié)果合并(grm).3 種算法涉及的執(zhí)行場(chǎng)地包括QS和SS,涉及的資源包括QS本地CPU(QS_CPU)、內(nèi)存(QS_Mem)、IO(QS_IO)、SS本地CPU(SS_CPU)、內(nèi)存(SS_Mem)、IO(SS_IO)以及QS和SS之間的一次網(wǎng)絡(luò)通信代價(jià)(C_Net).下面分別給出3 種算法對(duì)應(yīng)的代價(jià)計(jì)算公式.

?uPr_uLJ 算法相關(guān)的計(jì)算代價(jià)和存儲(chǔ)代價(jià)的計(jì)算見(jiàn)公式(10).

?uPr_LJ 算法相關(guān)的計(jì)算代價(jià)和存儲(chǔ)代價(jià)的計(jì)算見(jiàn)公式(11).

?Pr_LJC 算法相關(guān)的計(jì)算代價(jià)和存儲(chǔ)代價(jià)的計(jì)算見(jiàn)公式(12).

分析.從公式(10)可以看出,uPr_uLJ 算法沒(méi)有經(jīng)過(guò)局部排序以及局部連接提升連接效率以及降低QS的壓力,在數(shù)據(jù)量較大情況下,QS會(huì)成為系統(tǒng)瓶頸.uPr_LJ 算法采用了局部排序以及本地連接的策略,從公式(11)可以看出,取數(shù)據(jù)以及排序所耗費(fèi)的計(jì)算代價(jià)和存儲(chǔ)代價(jià)較uPr_uLJ 算法都有所減少,并且由于采用并行本地連接策略,因此在提升連接效率的同時(shí),減少了在QS合并的數(shù)據(jù)量,降低了QS的計(jì)算和存儲(chǔ)的壓力.但uPr_LJ 算法在執(zhí)行本地連接之前并沒(méi)有將無(wú)用的數(shù)據(jù)塊去除,導(dǎo)致增加額外的計(jì)算和存儲(chǔ)代價(jià).本文提出的Pr_LJC 算法增加了高效剪枝功能,提前將無(wú)用數(shù)據(jù)塊去除,并且采用基于LJC 的本地連接策略,最小化數(shù)據(jù)遷移帶來(lái)的網(wǎng)絡(luò)代價(jià),使性能整體上優(yōu)于uPr_uLJ 算法和uPr_LJ 算法.3 種算法的比較過(guò)程見(jiàn)公式(13)、公式(14).

5.3 算法適應(yīng)性

對(duì)于任何排序合并算法,都需要經(jīng)歷取數(shù)據(jù)、排序、合并的過(guò)程.在大數(shù)據(jù)時(shí)代,連接數(shù)據(jù)通常數(shù)據(jù)量巨大,并且分片存儲(chǔ)(無(wú)論是集中式還是分布式).無(wú)論采取什么連接策略,處理對(duì)象基本都是排序后的原始連接數(shù)據(jù),因此通過(guò)Pr_PSMJ 對(duì)排序后的數(shù)據(jù)進(jìn)行剪枝,勢(shì)必會(huì)提高后續(xù)的合并效率,進(jìn)而提高整體的連接效率,這在分布式數(shù)據(jù)庫(kù)中尤為明顯.由于剪枝策略主要涉及很少數(shù)據(jù)量的網(wǎng)絡(luò)傳輸代價(jià),與其提升的性能相比可忽略不計(jì),即使通過(guò)BAL 沒(méi)有剪枝掉任何數(shù)據(jù)塊或者剪枝掉少量數(shù)據(jù)塊,但BAL 最小化數(shù)據(jù)遷移量能夠節(jié)省網(wǎng)絡(luò)開(kāi)銷(xiāo),提升整體連接效率,因此適應(yīng)各種不同的排序合并連接策略.

5.4 基于Pr_PSMJ連接過(guò)程舉例

為了便于理解基于Pr_PSMJ 策略的排序合并連接過(guò)程,以如下過(guò)程進(jìn)行講解.為敘述方便,將定義1 中的數(shù)據(jù)模式簡(jiǎn)化,規(guī)定ti包括兩表{R,S},兩表在各自屬性x上進(jìn)行等值排序合并連接.經(jīng)過(guò)并行本地排序后,得到R和S在x上的{r}和{s},見(jiàn)表1.

Table 1 Instance of {r} and {s}表1 {r}和{s}實(shí)例

從{r}和{s}對(duì)應(yīng)的存儲(chǔ)位置{SSr}和{SSs}中提取{loc:num},對(duì)應(yīng)的存儲(chǔ)位置見(jiàn)表2.其中,k 和w 分別是千行和萬(wàn)行的單位,并且假設(shè)每一行大小基本相等.

Table 2 Storage location of {r} and {s}表2 {r}和{s}存儲(chǔ)位置

?切分因子q的構(gòu)造:根據(jù)表2 可得出,LJC 分別為(SS1:8:17k),(SS2:6:21k),(SS3:8:44k);依據(jù)第3.3 節(jié)可得出q=4.

?{ra}構(gòu)造:根據(jù)第3.1.1 節(jié)以及切分因子q構(gòu)造{ra},首先,針對(duì){r}構(gòu)造其超集Sr=[1,8000];然后,根據(jù)切分因子對(duì)Sr進(jìn)行切分,得到{ra}={[1,2000),[2000,4000),[4000,6000),[6000,8000]}.

?BAL 左部構(gòu)造:根據(jù)第3.1.1 節(jié)的左部構(gòu)造策略,利用{r}對(duì){ra}元素進(jìn)行探測(cè),得到BAL 左部,如圖6所示.

Fig.6 Instance of left part of BAL圖6 BAL 左部實(shí)例

?BAL 右部構(gòu)造:根據(jù)第3.1.1 節(jié)BAL 構(gòu)造策略進(jìn)行右部的構(gòu)造.首先,利用獲得的右連接關(guān)系R的數(shù)據(jù)范圍集合{s},探測(cè){ra},將{s}中的元素映射到{ra}集合中;然后,以{ra}中的元素為單位,在將對(duì)應(yīng)的{s}元素與ra元素對(duì)應(yīng)的{r}元素進(jìn)行比較,得到BAL 右部,如圖7 所示.

Fig.7 Instance of right part of BAL圖7 BAL 右部實(shí)例

經(jīng)過(guò)BAL 的過(guò)濾,可將{r3,r4,r7,r10,r11,r12}和{s1,s5,s7,s9,s10}無(wú)用數(shù)據(jù)過(guò)濾掉,節(jié)省大量網(wǎng)絡(luò)代價(jià)以及SS和QS的本地IO、CPU 代價(jià)和內(nèi)存空間.再根據(jù)BAL 進(jìn)行局部合并階段,依據(jù)公式(7)確定每一個(gè)非空右部對(duì)應(yīng)的{ra}中的每一行所在的執(zhí)行節(jié)點(diǎn)位置,可得{ra1,l1},{ra2,l2},{ra3,l1},根據(jù)計(jì)算的位置進(jìn)行數(shù)據(jù)遷移,保證本地連接的完備性.每個(gè)節(jié)點(diǎn)在遷移完畢后,由本地節(jié)點(diǎn)的線(xiàn)程池分配等于{ra}元素對(duì)應(yīng)的右部中鏈表個(gè)數(shù)的線(xiàn)程數(shù)以供局部并行連接,線(xiàn)程數(shù)分別為(2,1,1).局部連接完成后,將本地合并結(jié)果發(fā)送到QS,完成全局合并,將合并結(jié)果返回給客戶(hù)端.

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

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

本文實(shí)驗(yàn)使用8 個(gè)計(jì)算節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)配置為:主頻為1400MHz 的AMD Opteron(TM)處理器和16GB 內(nèi)存,物理CPU 個(gè)數(shù)為2,物理核數(shù)8,邏輯核數(shù)16;操作系統(tǒng)為Red Hat 6.2.所有算法均由C++實(shí)現(xiàn),算法實(shí)現(xiàn)平臺(tái)為淘寶的開(kāi)源分布式數(shù)據(jù)庫(kù)OceanBase 0.4 版本[28],系統(tǒng)架構(gòu)如圖8 所示,其中,RootServer 提供元數(shù)據(jù)服務(wù),主要包括數(shù)據(jù)分布信息;UpdateServer 提供OceanBase 唯一的更新入口;MergeServer 提供對(duì)SQL 語(yǔ)句的解析、邏輯計(jì)劃生成、物理計(jì)劃生成、計(jì)劃分發(fā)、結(jié)果合并等功能;ChunkServer 提供數(shù)據(jù)的存儲(chǔ)和查詢(xún)等服務(wù).OceanBase具體描述請(qǐng)參見(jiàn)文獻(xiàn)[3].圖2 與OceanBase 模塊的對(duì)應(yīng)關(guān)系為:MetadataServer 對(duì)應(yīng)RootServer,QueryServer 對(duì)應(yīng)MergeServer,StorageServer 對(duì)應(yīng)ChunkServer.

Fig.8 Architecture of OceanBase圖8 OceanBase 架構(gòu)

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

本文實(shí)驗(yàn)數(shù)據(jù)由tpch_2_17_0 工具生成,SF 設(shè)置為30,選取PART 表作為實(shí)驗(yàn)數(shù)據(jù)來(lái)源,PART 表數(shù)據(jù)量為600 萬(wàn)行,大小為699 兆.在OceanBase 數(shù)據(jù)庫(kù)中建立兩張表作為連接測(cè)試表,分別為l_part和r_part,并通過(guò)設(shè)置TABLET_MAX_SIZE參數(shù)指定表對(duì)應(yīng)分塊大小為20MB.這兩張表的結(jié)構(gòu)和tpch 生成的PART 表結(jié)構(gòu)一致.利用OceanBase 的import 工具將生成的數(shù)據(jù)分別導(dǎo)入到l_part和r_part中.

6.3 評(píng)估與結(jié)果分析

本文設(shè)計(jì)了4 組實(shí)驗(yàn),分別為:(1)測(cè)試在重復(fù)率不變的情況下,隨著連接數(shù)據(jù)量的增加,3 種算法的執(zhí)行效率;(2)測(cè)試在連接數(shù)據(jù)量不變的情況下,隨著重復(fù)率的增加,3 種算法的執(zhí)行效率;(3)測(cè)試在測(cè)試1 中,Pr_LJC算法中剪枝功能的執(zhí)行效率;(4)測(cè)試在測(cè)試2 中,Pr_LJC 算法中剪枝功能的執(zhí)行效率.

測(cè)試1.

這里規(guī)定重復(fù)率為表數(shù)據(jù)量的0.1%,即6 000 行,采用Query 1 進(jìn)行測(cè)試,其中,謂詞A,B,C,D用來(lái)控制兩表的連接數(shù)據(jù)量以及保證重復(fù)度為0.1%,這里使用如下策略實(shí)現(xiàn)(其中,wl 表示單位:萬(wàn)行):

l_part:(A,B)→{(0,10.6wl),(0,20.6wl),(0,50.6wl),…}

r_part:(C,D)→{(10wl,20.6wl),(20wl,40.6wl),(50wl,100.6wl),...}.

上述策略能夠保證在重復(fù)度為0.1%的前提下,不斷增加連接數(shù)據(jù)量.測(cè)試結(jié)果如圖9 所示.

Query 1:selectcount(*)froml_partinner joinr_partonl_part.P_PARTKEY=r_part.P_PARTKEY

wherel_part.P_PARTKEY>Aandl_part.P_PARTKEY

r_part.P_PARTKEY>Candr_part.P_PARTKEY

分析.從圖9 中可以看出,在重復(fù)度不變的情況下,隨著連接數(shù)據(jù)量的增加,Pr_LJC 算法的執(zhí)行時(shí)間基本不變;而uPr_uLJ 算法和uPr_LJ 算法隨數(shù)據(jù)量增加,執(zhí)行時(shí)間顯著增長(zhǎng).原因是:由于Pr_LJC 算法的剪枝(prune)策略,將重復(fù)度以外的無(wú)用數(shù)據(jù)塊提前去除,其他兩種算法完全基于原始數(shù)據(jù)進(jìn)行操作.

Fig.9 Result of execution efficient comparison of different algorithms under situation of fixing overlap degree and increasing data size圖9 固定重復(fù)度,隨著數(shù)據(jù)量的增加,不同算法執(zhí)行效率的對(duì)比結(jié)果

測(cè)試2.

這里規(guī)定測(cè)試的數(shù)據(jù)量為250.6wl,限定重復(fù)度以步長(zhǎng)0.6wl 增長(zhǎng).測(cè)試語(yǔ)句采用Query 1,采用與測(cè)試1 類(lèi)似策略,保證在連接數(shù)據(jù)量不變的情況下,逐漸增加重復(fù)度:

l_part:(A,B)→{(0,250.6wl),(0.6,251.2wl),(1.2,251.8wl),…}

r_part:(C,D)→(250wl,500.6wl).

上述策略能夠保證在數(shù)據(jù)量為250.6wl 的前提下,逐漸增加重復(fù)度.測(cè)試結(jié)果如圖10 所示.

Fig.10 Result of execution efficient comparison of different algorithms under situation of fixing data size and increasing overlap degree圖10 數(shù)據(jù)量固定,隨著重復(fù)度的增加,不同算法執(zhí)行效率的對(duì)比結(jié)果

分析.從圖10 可以看出,在連接數(shù)據(jù)量固定的情況下,隨著重復(fù)度的增加,Pr_LJC 算法的執(zhí)行效率緩慢增加,原因是需要執(zhí)行連接操作的數(shù)據(jù)量逐漸增加;uPr_uLJ 算法和uPr_LJ 算法始終保持較高的執(zhí)行時(shí)間,原因是這兩種算法的執(zhí)行時(shí)間不僅與重復(fù)度相關(guān),而且依賴(lài)于原始連接數(shù)據(jù)量.

測(cè)試3 和測(cè)試4.

通過(guò)在程序中添加時(shí)間函數(shù),對(duì)Pr_LJC 中的剪枝功能進(jìn)行執(zhí)行效率測(cè)試.測(cè)試結(jié)果如圖11 和圖12 所示.

Fig.11 Fixing overlap degree and testing execution efficient of prune in Pr_LJC as the increasing of data size圖11 固定重復(fù)度,測(cè)試Pr_LJC 算法中,prune 功能隨數(shù)據(jù)量增加的執(zhí)行效率

Fig.12 Fixing data size and testing execution efficient of prune in Pr_LJC as the increasing of overlap degree圖12 固定數(shù)據(jù)量,測(cè)試Pr_LJC 算法中,prune 功能隨重復(fù)度增加的執(zhí)行效率

分析.從圖11 和圖12 可以看出,在測(cè)試1 和測(cè)試2 兩種測(cè)試環(huán)境下,Pr_LJC 中的剪枝(prune)功能的執(zhí)行效率對(duì)于Pr_LJC 策略本身來(lái)說(shuō)可以忽略.原因是剪枝功能的實(shí)現(xiàn)(詳見(jiàn)第3.1.1 節(jié))完全在內(nèi)存中進(jìn)行,并且數(shù)據(jù)只涉及多個(gè)表示區(qū)間的數(shù)據(jù),因此數(shù)據(jù)量可以忽略.

7 結(jié)論和展望

排序合并連接是數(shù)據(jù)庫(kù)系統(tǒng)的一種重要連接方式,大數(shù)據(jù)時(shí)代,由于連接數(shù)據(jù)量的巨大,特別是分布式環(huán)境下,需要考慮網(wǎng)絡(luò)代價(jià),造成提升連接效率挑戰(zhàn)巨大.本文提出了Pr_PSMJ 策略,在進(jìn)行實(shí)際連接之前,通過(guò)構(gòu)造雙邊鄰接表(BAL)對(duì)連接數(shù)據(jù)進(jìn)行剪枝,提前去除無(wú)用數(shù)據(jù)塊,降低本地代價(jià)和網(wǎng)絡(luò)代價(jià);并通過(guò)BAL 指導(dǎo)本地并行合并連接,最小化數(shù)據(jù)移動(dòng)量,有效提升整體連接效率.Pr_PSMJ 策略適應(yīng)目前大多數(shù)合并連接策略.未來(lái)需要對(duì)切分因子(q)進(jìn)行更細(xì)致的求解,并且對(duì)合并區(qū)間進(jìn)行細(xì)化,做到更徹底的剪枝以及更健壯的負(fù)載均衡;同時(shí),對(duì)其他連接策略,如非阻塞式合并排序連接方法等方法進(jìn)行進(jìn)一步的研究與優(yōu)化.