分布式數據庫下基于剪枝的并行合并連接策略?

高錦濤, 李戰懷, 杜洪濤, 劉文潔

(西北工業大學 計算機學院,陜西 西安 710129)

排序合并連接是數據庫系統的一種重要的連接實現方式[1,2],比哈希連接有著更廣泛的應用.分布式環境下,數據量巨大,數據分片、分布存儲,導致連接過程中存在大量網絡代價,因此,高效地進行大數據量排序合并連接,挑戰巨大.根據經驗及實驗可得出,通常情況下,連接數據都可能存在無用數據塊,即不需要進行連接的數據.隨著數據量增大,無用數據塊比例可能越來越高,增加額外開銷,比如分布式環境下的網絡開銷,降低連接效率.

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

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

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

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

本文的主要貢獻如下.

1)給出一種分布式環境下基于剪枝的并行排序合并連接策略(Pr_PSMJ),能夠對連接數據中無用數據塊提前剪枝,并以最小數據遷移量完成本地并行合并連接,提高整體連接效率.

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

3)給出基于Pr_PSMJ 的合并連接算法,并與經典算法在時間和空間上進行對比,給出算法正確性、效率性以及適應性分析,并結合實例給出Pr_PSMJ 算法工作過程.

4)在淘寶開源分布式數據庫OceanBase 中實現Pr_PSMJ 策略,并給出實驗評估,驗證Pr_PSMJ 策略的高效性.

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

1 相關工作

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

?非阻塞式合并排序連接

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

?多核環境下排序合并連接

隨著硬件的快速發展,多核機器越來越普遍.為了充分利用多核環境下并行的執行優點,一系列并行執行策略[4-7]被提出來.文獻[4]提出使用多核(4 096 個核),利用MPI 進行合并連接的實施環境,通過合理規劃網絡資源,將排序和連接分離提高連接效率.文獻[5]提出一種P-MPSM 算法,利用多核對連接數據并行排序,并對左側連接數據分區,并利用直方圖進行重分區,處理數據傾斜問題,利用插補搜索[19,20],縮小連接范圍,但插補搜索假設搜索的對象數據分布均勻.

?分布式環境下排序合并連接

大數據時代,分布式數據庫是處理和管理海量數據的利器,如Google 的spanner[21]、淘寶的OceanBase 數據庫[3]等.分布式環境下,數據分片、分布存儲,排序合并連接在取數據、排序、連接各個階段涉及的數據量可能都較大,并且存在昂貴的網絡傳輸代價,對于進行高效排序合并連接提出更大挑戰.淘寶的OceanBase 數據庫中,排序合并連接過程為:并行獲取連接對象的分區數據,并將分區數據發送到查詢節點.雖然采用流水線執行方式,但存在單點內存全量排序的缺點,導致對于大數據量表的等值連接,效率較差(圖1).文獻[22]針對OceanBase讀寫分離引起的數據合并代價,提出一種基線與增量數據分離架構下的排序歸并連接優化算法,通過數據遷移達到連接數據的本地排序和連接.

?討論

非阻塞式并行連接能夠減少連接時等待時間,但分布式環境下,網絡傳輸代價為主宰代價,因此這些策略本質上并沒有太多提高排序、連接效率.雖然多核環境和分布式環境下能夠利用并行策略提高排序合并連接效率,但沒有對無用數據塊進行預處理,造成額外代價.本文提出的Pr_PSMJ 策略能夠預先對無用數據進行剪枝,減少局部連接和全局連接代價,并能夠以最小數據移動量完成本地并行合并連接,提高整體的執行效率.

2 預備知識

為了針對分布式環境闡述本文提出的Pr_PSMJ 策略,總結出一種通用的分布式框架,如圖2 所示.

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

對各部分解釋如下.

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

?Metadata server(MS):負責提供數據分片存儲位置等元數據信息.

?Storage servers(SS):負責存儲、操作(如查詢)數據.存儲模式為分布式,類似于BigTable[23],每一個分布

式節點存儲一個表的部分或全部信息,并部署一個線程池{Wi},動態地分配所需線程,完成對應任務.以下內容針對連接語義(1)進行闡述,即R和S兩個關系在連接屬性x上進行等值連接.

定義1(數據模式).數據邏輯上以表為單位,物理上將表進行分片,分布存儲在各個SS上.定義為公式(2).

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

定義2(排序合并連接[24]).數據庫的一種連接實現方式,適合自然連接和等值連接.針對公式(1)中的兩個關系R(y,x)和S(x,z),其中,x為兩關系的連接屬性,y和z分別為其他屬性,形式化定義排序合并連接見公式(3).

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

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

其中,PSo表示將關系R和關系S相關的分區數據中連接屬性x上的排序任務分別分配ni和nj個工作線程進行并行排序,其中,Wi和Wj分別表示分布式節點上的線程池,N和M表示R和S相關分區數據所在的分布式節點的個數,Ri和Sj分別表示第i個節點和第j個節點上R和S的分區個數,且num(Ri)=ni,num(Sj)=nj.執行PMe的步驟包括:

(1)M1表示將各個Ri包含的分片遷移到合適的Si所在節點.

(2)M2表示將各個Sj包含的分片遷移到合適的Ri所在的節點.

(3)如果遷移后的節點完備(lkis complete),即可開始本地合并連接,完備的節點之間執行不阻塞.

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

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

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

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

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

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

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

添加剪枝(prune,簡稱Pr)操作提取R和S對應分區數據的有序序列范圍,建立BAL,利用剪枝策略將無用數據塊預先去除.并將BAL 中各個項分發給對應SS.進行本地合并后,由QS完成全局合并.

3.1 剪枝功能

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

3.1.1 BAL 構造

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

Fig.4 Architecture of BAL圖4 BAL 架構

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

?構造{ra}:首先獲得R對應的數據塊范圍.做法為:在R相關的SS節點中進行PSo操作后得到有序數據塊,同時獲取其范圍,形成集合{r},根據{r}得出{r}的超集Sr,設置切分因子q(設定方法詳見第3.3 節),將Sr切分成{ra}集合.經過以上處理,形成圖4 中{ra}.

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

?構造右部:使用和獲取{r}同樣的方法獲取右連接關系對應的數據塊范圍{s},利用{s}中的每一個元素s探測當前形成的BAL,形成兩階段探測:

?首次探測{ra},s與{ra}的對應關系為1 對多或者1 對1:如果為前者,則將s進行拆分,拆分后的子集映射到對應{ra}元素,這個過程中會將s的一部分無用數據舍棄;如果為后者,則直接映射到當前ra元素.

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

構造完成的BAL 已經對無用的{r}和{s}數據塊進行了剪枝,并且形成了以{r_s}中元素為單位的本地連接執行單元.

3.1.2 邊界處理

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

3.1.3 負載均衡

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

3.2 本地連接中心

對連接關系完成剪枝操作后,需要根據形成的BAL 的右部,執行圖3 中的BAL 分發功能(distribute BAL),將右部各個元素發送到對應的存儲節點(SS)上執行本地連接.為了保證連接的完備性,需要消耗網絡代價將一部分數據塊遷移到執行本地連接的SS節點上,這個節點稱為LJC.被選擇為LJC 的SS節點通過collector 模塊,根據接收到的BAL 右部元素對應的各個四元組,將不屬于這個LJC 的四元組對應的R和S的數據塊收集到本地,然后利用allocator 模塊為收集完備的項分配對應的資源完成本地連接.為最小化遷移代價,提出公式(7)來計算LJC.

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

3.3 切分因子構造

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

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

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

?提取{SSr}和{SSs}中每一個存儲位置涉及的{r}和{s}子集以及對應的子集個數,形成{loc:num:range}.

?根據{r}和{s}以及{r_size}和{s_size}計算出range對應的數據量之和,形成{loc:num:sum}.

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

?由于針對分布式環境,因此以減少網絡傳輸代價為首要目標,得出如下q計算公式.

從公式(8)可以看出,如果連接數據分布不均勻,則得出的q會相對較大,使{ra}粒度相對較小,能夠將負載不均衡的節點關聯的負載分攤到其他節點,較好地解決數據傾斜問題.

4 算 法

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

uPr_uLJ 算法.

uPr_uLJ 算法首先獲取連接關系R和S對應的元數據信息(第1 行),然后根據元數據信息并行的獲取到對應的數據塊(第2 行),并將獲取到的數據塊全部發送到查詢節點(第3 行)完成全局排序(第4 行),最后在查詢節點完成全局合并連接,將結果返回(第5 行、第6 行).

uPr_LJ 算法.

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

Pr_LJC 算法.

Pr_LJC 算法的第1 行、第2 行與uPr_LJ 算法的第1 行、第2 行相同.不同的是,需要通過本地并行排序的結果獲取對應數據塊的范圍,并將它們發送到查詢節點(第3 行、第4 行).在查詢節點,根據第3.1.1 節的內容生成BAL(第5 行),根據第3.2 節的內容獲得BAL 右部對應的最佳本地執行點(LJC)(第6 行).將BAL 的右部分發到對應的LJC(第7 行),對于每一個LJC,根據接收到的BAL 右部內容將對應的數據塊拉取到本地,完成本地連接任務(第8 行～第10 行).第11 行、第12 行與uPr_LJ 算法的第9 行、第10 行相同.

5 算法分析

5.1 算法正確性

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

?保證對原始連接數據進行剪枝不影響最終結果的正確性.

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

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

由于每個非空BAL 的連接是獨立且完備的,并且對應的連接數據完全來自基于公式(9)已經證明正確的數據基礎上進行的,并且最終由QS完成全局連接,因此能夠保證在實行本地并行連接后最終連接結果的正確性.

5.2 算法效率性

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

?uPr_uLJ 算法相關的計算代價和存儲代價的計算見公式(10).

?uPr_LJ 算法相關的計算代價和存儲代價的計算見公式(11).

?Pr_LJC 算法相關的計算代價和存儲代價的計算見公式(12).

分析.從公式(10)可以看出,uPr_uLJ 算法沒有經過局部排序以及局部連接提升連接效率以及降低QS的壓力,在數據量較大情況下,QS會成為系統瓶頸.uPr_LJ 算法采用了局部排序以及本地連接的策略,從公式(11)可以看出,取數據以及排序所耗費的計算代價和存儲代價較uPr_uLJ 算法都有所減少,并且由于采用并行本地連接策略,因此在提升連接效率的同時,減少了在QS合并的數據量,降低了QS的計算和存儲的壓力.但uPr_LJ 算法在執行本地連接之前并沒有將無用的數據塊去除,導致增加額外的計算和存儲代價.本文提出的Pr_LJC 算法增加了高效剪枝功能,提前將無用數據塊去除,并且采用基于LJC 的本地連接策略,最小化數據遷移帶來的網絡代價,使性能整體上優于uPr_uLJ 算法和uPr_LJ 算法.3 種算法的比較過程見公式(13)、公式(14).

5.3 算法適應性

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

5.4 基于Pr_PSMJ連接過程舉例

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

Table 1 Instance of {r} and {s}表1 {r}和{s}實例

從{r}和{s}對應的存儲位置{SSr}和{SSs}中提取{loc:num},對應的存儲位置見表2.其中,k 和w 分別是千行和萬行的單位,并且假設每一行大小基本相等.

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

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

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

?BAL 左部構造:根據第3.1.1 節的左部構造策略,利用{r}對{ra}元素進行探測,得到BAL 左部,如圖6所示.

Fig.6 Instance of left part of BAL圖6 BAL 左部實例

?BAL 右部構造:根據第3.1.1 節BAL 構造策略進行右部的構造.首先,利用獲得的右連接關系R的數據范圍集合{s},探測{ra},將{s}中的元素映射到{ra}集合中;然后,以{ra}中的元素為單位,在將對應的{s}元素與ra元素對應的{r}元素進行比較,得到BAL 右部,如圖7 所示.

Fig.7 Instance of right part of BAL圖7 BAL 右部實例

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

6 實驗評估

6.1 實驗環境

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

Fig.8 Architecture of OceanBase圖8 OceanBase 架構

6.2 實驗數據

本文實驗數據由tpch_2_17_0 工具生成,SF 設置為30,選取PART 表作為實驗數據來源,PART 表數據量為600 萬行,大小為699 兆.在OceanBase 數據庫中建立兩張表作為連接測試表,分別為l_part和r_part,并通過設置TABLET_MAX_SIZE參數指定表對應分塊大小為20MB.這兩張表的結構和tpch 生成的PART 表結構一致.利用OceanBase 的import 工具將生成的數據分別導入到l_part和r_part中.

6.3 評估與結果分析

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

測試1.

這里規定重復率為表數據量的0.1%,即6 000 行,采用Query 1 進行測試,其中,謂詞A,B,C,D用來控制兩表的連接數據量以及保證重復度為0.1%,這里使用如下策略實現(其中,wl 表示單位:萬行):

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),...}.

上述策略能夠保證在重復度為0.1%的前提下,不斷增加連接數據量.測試結果如圖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 中可以看出,在重復度不變的情況下,隨著連接數據量的增加,Pr_LJC 算法的執行時間基本不變;而uPr_uLJ 算法和uPr_LJ 算法隨數據量增加,執行時間顯著增長.原因是:由于Pr_LJC 算法的剪枝(prune)策略,將重復度以外的無用數據塊提前去除,其他兩種算法完全基于原始數據進行操作.

Fig.9 Result of execution efficient comparison of different algorithms under situation of fixing overlap degree and increasing data size圖9 固定重復度,隨著數據量的增加,不同算法執行效率的對比結果

測試2.

這里規定測試的數據量為250.6wl,限定重復度以步長0.6wl 增長.測試語句采用Query 1,采用與測試1 類似策略,保證在連接數據量不變的情況下,逐漸增加重復度:

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

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

上述策略能夠保證在數據量為250.6wl 的前提下,逐漸增加重復度.測試結果如圖10 所示.

Fig.10 Result of execution efficient comparison of different algorithms under situation of fixing data size and increasing overlap degree圖10 數據量固定,隨著重復度的增加,不同算法執行效率的對比結果

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

測試3 和測試4.

通過在程序中添加時間函數,對Pr_LJC 中的剪枝功能進行執行效率測試.測試結果如圖11 和圖12 所示.

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

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

分析.從圖11 和圖12 可以看出,在測試1 和測試2 兩種測試環境下,Pr_LJC 中的剪枝(prune)功能的執行效率對于Pr_LJC 策略本身來說可以忽略.原因是剪枝功能的實現(詳見第3.1.1 節)完全在內存中進行,并且數據只涉及多個表示區間的數據,因此數據量可以忽略.

7 結論和展望

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