面向內(nèi)存計算的連接算法

張 磊， 方祝和， 周敏奇， 黃 嵐

（1.華東師范大學 軟件學院 數(shù)據(jù)科學與工程研究院，上海 200062；2.中國電子科技集團第三十二研究所，上海 200233）

0 引 言

隨著大數(shù)據(jù)時代的來臨，數(shù)據(jù)庫系統(tǒng)在工業(yè)生產(chǎn)中扮演著日漸重要的角色.對于使用非常頻繁的連接操作，它支持了OLAP（聯(lián)機分析處理）中的一些關(guān)鍵查詢，在具體的BI（商業(yè)智能）業(yè)務(wù)中應(yīng)用極其廣泛，支持交互式實時查詢和低延遲的分析任務(wù)以便為業(yè)務(wù)做出決策.例如，在實際應(yīng)用中，交通銀行對于日常歷史數(shù)據(jù)的查詢、上海證券交易所對于股票信息的實時分析以及12306網(wǎng)站對于高并發(fā)量低延時的高要求.這些無一不需要高性能連接算法的支持，而內(nèi)存環(huán)境下的連接算法將會是解決問題的關(guān)鍵技術(shù).

近幾年來，隨著內(nèi)存芯片技術(shù)的快速發(fā)展，1MB內(nèi)存的價格由1980年的1萬美元降低到2010年的0.01美元［1］，單一芯片上的核數(shù)也越來越多.Sun公司預測，到2018年，服務(wù)器將采用含有32到128個內(nèi)核的芯片.由于關(guān)系型數(shù)據(jù)庫中數(shù)據(jù)冗余較少，數(shù)據(jù)精煉，將整個數(shù)據(jù)庫都放在內(nèi)存中并不再是難題.即便一個節(jié)點的內(nèi)存無法容納整個庫的數(shù)據(jù)，利用廉價機器組成的集群也可以解決硬件上的擴展性問題.同時，多核CPU芯片的流行也大大增加了計算帶寬和內(nèi)存帶寬.因此，相比于傳統(tǒng)數(shù)據(jù)庫的研究，合理設(shè)計適應(yīng)新硬件的算法是提升連接操作性能的突破點.

從20世紀80年代到21世紀初，磁盤技術(shù)較內(nèi)存技術(shù)發(fā)展更為迅猛.廉價的大容量磁盤催生了一大批基于磁盤存儲的優(yōu)秀數(shù)據(jù)庫系統(tǒng)，如Oracle、SQL Server、DB2、Mysql，等等.在這些系統(tǒng)中，最經(jīng)典的連接算法有嵌套循環(huán)連接、排序歸并連接和哈希連接.學術(shù)界和工業(yè)界對它的研究也都是在減少磁盤I／O次數(shù)、合理利用索引之上，基于磁盤的連接算法優(yōu)化已經(jīng)做到極致.

內(nèi)存計算環(huán)境下的連接算法與基于磁盤連接算法研究的問題有所不同.單機環(huán)境下，基于內(nèi)存計算的連接算法主要是在針對具體機器體系架構(gòu)，減小Cache缺失和減小TLB缺失和克服內(nèi)存墻問題.在分布式環(huán)境下，基于內(nèi)存計算的分布式連接算法旨在充分利用內(nèi)存快速計算，充分利用網(wǎng)絡(luò)傳輸速度，同時減小網(wǎng)絡(luò)的傳輸數(shù)據(jù)量.

本文的后續(xù)內(nèi)容組織如下：第1節(jié)描述內(nèi)存環(huán)境下連接算法的影響因素；第2、3、4節(jié)分別詳細分析嵌套循環(huán)連接算法、哈希連接算法和排序歸并連接算法的傳統(tǒng)實現(xiàn)，以及在內(nèi)存環(huán)境下的優(yōu)化方法和技術(shù)難點；第5節(jié)分析分布式環(huán)境下在網(wǎng)絡(luò)成為性能瓶頸的情況下的優(yōu)化因素；第6節(jié)將橫向?qū)Ρ葍?nèi)存環(huán)境下兩種高效的連接算法；最后在第7節(jié)總結(jié)全文.

1 連接算法影響因素

1.1 并行策略

并行策略主要分為以多核芯片為基礎(chǔ)的線程級別并行和以SIMD（單指令多數(shù)據(jù)）指令為基礎(chǔ)的數(shù)據(jù)級別并行.連接算法在多個階段能夠?qū)嵤┎⑿校沟盟惴▓?zhí)行成倍加速.

（1）線程級別并行

所謂線程級別并行是指在多核環(huán)境下線程之間的并行，較為流行的多核CPU架構(gòu)有CMP架構(gòu)、SMP架構(gòu)和NUMA架構(gòu).CMP為單個CPU芯片多核架構(gòu)；SMP為對稱多處理器結(jié)構(gòu)，即一組處理器共享內(nèi)存子系統(tǒng)和總線，內(nèi)存子系統(tǒng)可以由多個內(nèi)存節(jié)點構(gòu)成；NUMA被稱為非一致性內(nèi)存訪問，NUMA以獨立節(jié)點存在，并且每個節(jié)點都有單獨的內(nèi)存和CPU.如果CPU處理器支持SMT（同步多線程技術(shù)），運行時能夠并行的最大線程數(shù)將會是CPU核數(shù)的2倍，使性能趨于加倍.

線程級別并行雖然能夠使一些算法成倍加速，但同時也會引入數(shù)據(jù)寫操作沖突的問題，一般采用加鎖機制來同步多線程之間的寫操作.為了平衡加鎖帶來的性能消耗，可采用的方法有2種：一種是控制加鎖粒度，使鎖的粒度盡量小，比如在哈希表的實現(xiàn)中，可以對整個哈希表加鎖，但是更優(yōu)的方法是對哈希表的每個分區(qū)加鎖或者對哈希表的每個桶加鎖；另一種就是利用性能損失更小的鎖，如互斥鎖和自旋鎖.在需要高頻率執(zhí)行寫操作來構(gòu)造哈希表的過程中，使用自旋鎖會取得更好的效果.

算法并行涉及到數(shù)據(jù)分區(qū)操作，會占用部分內(nèi)存，影響執(zhí)行效率.對于連接的3種算法，均可存在分區(qū)階段，較常用的是哈希連接中的哈希分區(qū)和排序歸并連接中的范圍分區(qū).

（2）數(shù)據(jù)級別并行

數(shù)據(jù)級別并行技術(shù)主要是指SIMD技術(shù)，SIMD指令一般是以內(nèi)聯(lián)匯編的形式嵌入到代碼中.使用SIMD技術(shù)要求數(shù)據(jù)必須在內(nèi)存中連續(xù)存放，并且數(shù)據(jù)最好是采用定長數(shù)據(jù)結(jié)構(gòu)存儲.現(xiàn)有許多數(shù)據(jù)庫中的基本操作可以采用SIMD技術(shù)實現(xiàn)，比如順序掃描、scalar聚集、一些連接算法甚至索引［2］.

采用SIMD技術(shù)的同時要注意選擇合適的算法，比如在排序歸并連接算法中，排序的實現(xiàn)可以采用快速排序算法，但快速排序性能雖高，卻不能很好利用SIMD，而采用bitonic排序算法會在利用SIMD的前提下大幅度提升性能［3］，所以會選擇后者.在哈希連接和排序歸并連接的比較中，SIMD隨著其位數(shù)的增多會對排序歸并連接更有利.

1.2 算法調(diào)優(yōu)

（1）數(shù)據(jù)結(jié)構(gòu)選擇

高效的［4］鏈接算法一般是引用元組數(shù)據(jù)的指針，盡量避免將整個元組數(shù)據(jù)都加載到緩存中，這樣就能夠在合理利用內(nèi)存帶寬的同時，減小數(shù)據(jù)復制.

哈希表在數(shù)據(jù)庫系統(tǒng)連接算子和聚集算子中的地位舉足輕重，哈希表的實現(xiàn)直接影響到連接操作和聚集操作的性能.哈希表必須支持高頻率的內(nèi)存讀寫，以及控制哈希表中桶的大小，以減少掃描桶的時間開銷.同時整個哈希表所應(yīng)該占用連續(xù)內(nèi)存，以減少讀取哈希表時TLB缺失，OceanBase［5］中的哈希表采用鏈表存儲，雖然它能較好地支持變長數(shù)據(jù)處理和數(shù)據(jù)庫事務(wù)實現(xiàn)，但是對于哈希連接來說，鏈表存儲并非是個較好的選擇.

（2）線程數(shù)和核數(shù)

線程個數(shù)和核數(shù)的比例會對算法性能產(chǎn)生影響.在每個核中運行的線程會因為同步或者硬件間隔暫停正在處理的操作，此時CPU核處于空轉(zhuǎn)狀態(tài).如果線程數(shù)和核數(shù)相同，CPU核會經(jīng)常處于空閑狀態(tài).通常當線程數(shù)是核數(shù)4倍的時候，CPU核的負載會被充分利用.

（3）硬件參數(shù)優(yōu)化

傳統(tǒng)磁盤環(huán)境下，磁盤帶寬是數(shù)據(jù)庫中一個非常重要的參數(shù)，直接決定了查詢的速度.但是對于將數(shù)據(jù)可以全都存儲在內(nèi)存中來說，磁盤帶寬不再是影響因素，對于硬件的各個參數(shù)，比如各級緩存的大小、TLB的大小、SIMD的寬度、NUMA節(jié)點數(shù)、內(nèi)存帶寬乃至網(wǎng)絡(luò)帶寬，這些硬件參數(shù)都必須作為最終實現(xiàn)算法時的考慮因子；通常是在系統(tǒng)啟動初期，經(jīng)過程序檢測出這些硬件的指標，然后作為參數(shù)傳輸?shù)讲樵儍?yōu)化器中.

1.3 數(shù)據(jù)集

（1）數(shù)據(jù)量

數(shù)據(jù)集的大小對連接性能有影響，Balkesen C在文獻［6］中表述，無分區(qū)哈希連接在build階段表較小的時候確實會有很好性能；但是如果在build階段用稍大的表建立哈希表，無分區(qū)哈希連接的性能將出現(xiàn)大幅下降；不過，radix連接的性能對build階段表的大小并沒有那么敏感.同樣，對于排序歸并連接，當一個表遠大于另一個表的時候，Albutiu M C在文獻［7］提到，如果公用表的大小遠大于私有表，P－MPSM算法比不上B－MPSM算法.

（2）數(shù)據(jù)分布

在具體應(yīng)用中，做連接的2張表的數(shù)據(jù)發(fā)生傾斜的情況十分常見.數(shù)據(jù)傾斜一般分為2種，分區(qū)之后的數(shù)據(jù)傾斜和數(shù)據(jù)本身在某個屬性上的數(shù)據(jù)傾斜.各種算法在數(shù)據(jù)傾斜的情況下會做不同的處理，文獻［8］指出，無分區(qū)哈希連接比其他的復雜算法更具優(yōu)勢，因為它可以充分利用硬件處理數(shù)據(jù)傾斜的優(yōu)化方法.但是，在radix連接［9］為代表的一類算法中，數(shù)據(jù)傾斜會使得算法的復雜度提升，當數(shù)據(jù)傾斜度較大的時候，哈希連接會接近退化為嵌套循環(huán)連接.一般情況下，當發(fā)生數(shù)據(jù)本身在某個屬性上發(fā)生傾斜的時候，采用排序歸并連接可以減小性能開銷.同樣地，排序歸并連接算法也受數(shù)據(jù)分布的影響.

處理數(shù)據(jù)傾斜的方式.NUMA架構(gòu)下，在連接算法的各階段，一般處理傾斜是在分區(qū)階段完成的，一旦決定用加入分區(qū)階段，就必須解決數(shù)據(jù)傾斜導致的負載不均衡問題，結(jié)合NUMA架構(gòu)下多核的特點，解決數(shù)據(jù)傾斜一般采用直方圖統(tǒng)計的方法.

WBS(work breakdown structure,工作分解結(jié)構(gòu))是項目管理中的重要手段，在現(xiàn)有的項目管理中得到廣泛應(yīng)用[8].WBS是一種對項目工作進行拆解的方法，以整個項目為基礎(chǔ)，按照此工程項目的施工步驟及方法進行層層分解，直至將項目工程分解為一個個合適的相對易于管理的單元格.這些單元格是WBS分解中的最底級工作包(work package)，以此作為風險管理中風險識別的基本單元.

2 嵌套循環(huán)連接

即2張表的每條記錄在連接屬性上兩兩匹配做連接.傳統(tǒng)磁盤環(huán)境下，嵌套循環(huán)連接一般分為2種：塊嵌套循環(huán)連接和索引嵌套循環(huán)連接.塊嵌套循環(huán)連接減少磁盤I／O的次數(shù)，索引嵌套循環(huán)連接減小對表數(shù)據(jù)的掃描代價.嵌套循環(huán)連接一般選擇數(shù)據(jù)量較小的表或者輸出集較小的表作為驅(qū)動表，用于外層循環(huán)，另一張表則用于內(nèi)層循環(huán).內(nèi)存計算環(huán)境下，磁盤I／O次數(shù)可以忽略，在緩存預取和新硬件調(diào)優(yōu)方面，嵌套循環(huán)連接仍有很大的優(yōu)化空間.

在內(nèi)存計算環(huán)境下，可以從減少緩存缺失和充分利用SIMD技術(shù)兩方面對嵌套循環(huán)連接進行優(yōu)化.文獻［10］驗證了基于塊的嵌套循環(huán)連接比基本嵌套循環(huán)連接產(chǎn)生更少的緩存缺失，原因在于：基本嵌套循環(huán)算法的內(nèi)層循環(huán)在每次讀取一條記錄與外層循環(huán)記錄作比較時很可能發(fā)生緩存缺失；而基于塊的嵌套循環(huán)連接，可以利用塊中數(shù)據(jù)的局部特性將整塊數(shù)據(jù)置于緩存中，避免內(nèi)層循環(huán)每次訪問一條記錄時發(fā)生緩存缺失的情況.SIMD技術(shù)可以對嵌套循環(huán)連接做優(yōu)化.Zhou J在文獻［2］中提出了，采用SIMD技術(shù)優(yōu)化嵌套循環(huán)連接的3種方式：復制外層循環(huán)、復制內(nèi)存循環(huán)和旋轉(zhuǎn)方式.現(xiàn)假設(shè)SIMD的位數(shù)為128位，連接屬性為32位整型數(shù)據(jù)，第1種方式將外層循環(huán)中的一條整形記錄復制成4份，采用SIMD指令與內(nèi)存循環(huán)中相鄰的4條記錄同時比較.同理，第2種方式將內(nèi)層循環(huán)中的一條整型記錄復制成4份，采用SIMD指令與外層中循環(huán)相鄰的4條記錄同時比較.旋轉(zhuǎn)方式無需復制，而是將外層循環(huán)中的4條記錄旋轉(zhuǎn)4次，每次旋轉(zhuǎn)之后，再與內(nèi)層循環(huán)的4條記錄同時比較.旋轉(zhuǎn)方式的比較次數(shù)和復制方式相同，但旋轉(zhuǎn)方式省略了復制的代價，達到理論最優(yōu)，Zhou J在實驗中證明了這點.

對于嵌套循環(huán)連接算法來講，兩個表中的每條記錄兩兩之間都必須做比較，不可能像哈希連接和排序歸并連接一樣利用切分來減少比較的次數(shù).嵌套循環(huán)連接往往采用廣播小表的方式并行，即每個大表分片均與整張小表連接，從而提高連接效率.

3 哈希連接

在基于磁盤的傳統(tǒng)數(shù)據(jù)庫系統(tǒng)中，哈希連接分為build階段和probe階段：build階段利用數(shù)據(jù)量較小的表建立哈希表，probe階段利用另一張表和哈希表匹配.當哈希表無法完全放置于內(nèi)存中時，必須有分區(qū)階段，但此時哈希連接的性能急劇下降.基于內(nèi)存計算的哈希連接算法包括分區(qū)階段、build階段和probe階段；其中分區(qū)階段的有無對不同背景下的算法性能會產(chǎn)生較大影響.如果沒有分區(qū)階段，其優(yōu)點在于：（1）對于查詢優(yōu)化器的傳參有利，只需傳遞少量的調(diào)優(yōu)參數(shù)；（2）對硬件預取沒有任何干預，有利于處理傾斜數(shù)據(jù)集［8］.但有分區(qū)階段的哈希連接算法在性能方面更加穩(wěn)定.對于存在分區(qū)階段的哈希連接算法來講，又分為多種類型，總體上，它的優(yōu)勢在于：可以根據(jù)硬件參數(shù)設(shè)定輸入到分區(qū)階段的參數(shù)，比如TLB的大小，緩存的大小，以致于降低分區(qū)階段的緩存缺失和TLB缺失，使后續(xù)build階段的性能變高.

3.1 無分區(qū)的哈希連接算法

多核環(huán)境下基于內(nèi)存計算的無分區(qū)哈希連接算法采用線程并行.如圖1所示，存在R和S 2張表，假設(shè)4線程并發(fā)，在build階段中，4個線程同時讀取R表的數(shù)據(jù)分片，采用相同的哈希函數(shù)h計算R表中每條記錄的連接屬性對應(yīng)的哈希值，存儲到由b1，b2，b3，…，bn構(gòu)成的全局哈希表中.當build階段所有線程都結(jié)束后，進入probe階段，4個線程并發(fā)讀取S表中的數(shù)據(jù)分片，利用與build階段相同的哈希函數(shù)h，計算出S表中每條記錄的連接屬性的哈希值并與全局哈希表做匹配.

圖1 無分區(qū)哈希連接Fig.1 No partition hash join

無分區(qū)哈希連接算法無需考慮硬件參數(shù)，且無需向查詢優(yōu)化器傳遞這些參數(shù)［8］.但由于CPU核中的Cache大小往往較小，無法將整個哈希表存進Cache；又因為哈希的隨機性，無分區(qū)哈希連接算法在build階段會產(chǎn)生大量Cache缺失，使得build階段的性能急劇下降.

3.2 有分區(qū)的哈希連接算法

有分區(qū)階段的哈希連接算法分為分區(qū)哈希連接、radix連接和并行radix連接.旨在通過減少Cache缺失和TLB缺失克服內(nèi)存墻問題，從而達到優(yōu)化連接的目的.

（1）分區(qū)哈希連接

為了避免無分區(qū)哈希連接算法中大量的Cache缺失，Shatdal A于1994年提出Cache感知的分區(qū)哈希連接算法［10］.如圖2所示，存在R和S 2張表，在分區(qū)階段，R表被哈希函數(shù)h1切分為r1，r2，r3，r44個分區(qū)，此處分區(qū)的數(shù)量和Cache大小有關(guān)，目的是使針對于每個分區(qū)建立的哈希表能夠存入CPU的Cache中以減小build階段Cache缺失的次數(shù).與圖1中生成整張全局哈希表不同，分區(qū)哈希連接算法的每個分區(qū)都存在一張局部哈希表.每個分區(qū)中每條記錄的連接屬性經(jīng)過哈希函數(shù)h2計算出哈希值，即哈希桶的編號，然后存入相應(yīng)桶中.在probe階段，采用相同的哈希函數(shù)h1先將S表分區(qū)，然后再采用相同的哈希函數(shù)h2對每條記錄連接屬性計算哈希值去哈希表的桶中匹配.

圖2 分區(qū)哈希連接Fig.2 Partitioned hash join

（2）Radix連接

Linux操作系統(tǒng)采用虛擬內(nèi)存管理，TLB是CPU頻繁訪問的硬件，存儲著經(jīng)常訪問的內(nèi)存頁的虛擬地址到物理地址的映射.分區(qū)哈希連接雖然能夠減少Cache缺失，但可能產(chǎn)生大量的TLB缺失.避免TLB缺失的方法是將分區(qū)階段切分的分區(qū)個數(shù)控制在小于TLB中entry的個數(shù)的范圍之內(nèi).因此，Radix連接算法［9］采用多路切分的策略.如圖3所示，存在R和S兩張表做連接，R根據(jù)表建立哈希表，R表分區(qū)階段分為兩步，第1步，利用哈希函數(shù)h1，1將R切分為若干個分區(qū)；第2步，利用哈希函數(shù)h1，2將第1步切分的每個分區(qū)再次切分為若干個小分區(qū)，兩次切分使最終切分成的分區(qū)大小小于Cache容量的同時，保證了每個分區(qū)再次切分之后的分區(qū)數(shù)目都少于TLB中entry的數(shù)目.build階段利用第2步生成的分區(qū)建立哈希表.對于S表，采用相同的切分策略，然后做probe階段的匹配.

Radix連接需要向查詢優(yōu)化器傳遞較多硬件參數(shù)，比如TLB大小和cache容量，這些參數(shù)在不同的機器中有區(qū)別，在系統(tǒng)啟動時需要利用程序?qū)ｉT計算出這些參數(shù)再傳入內(nèi)存中.Radix連接能夠針對具體硬件最大限度地調(diào)優(yōu)，充分發(fā)揮硬件的優(yōu)勢.

（3）并行Radix連接

以上含有分區(qū)階段的2種算法均在一個CPU核內(nèi)討論，如果分區(qū)階段利用多線程對表進行切分會得到更高的性能，但同時會產(chǎn)生新的同步問題.由于多個線程可能將哈希過后的鍵值保存到同一個哈希表的桶中，因此每個桶可能在2個線程所在的核中加載，在多個核共享3級緩存的情況下，2個核將通過第3級緩存同步，此時將發(fā)生緩存一致性缺失.

圖3 radix連接Fig.3 Radix join

4 排序歸并連接

排序歸并連接是數(shù)據(jù)庫系統(tǒng)中的經(jīng)典連接算法.在傳統(tǒng)磁盤數(shù)據(jù)庫中該算法主要采用外部排序?qū)崿F(xiàn)，對內(nèi)存大小并無限制，與嵌套循環(huán)連接算法一樣，減少磁盤I／O次數(shù)是算法的優(yōu)化目標.而在內(nèi)存數(shù)據(jù)庫中，排序歸并連接算法主要研究在NUMA［11］和SIMD等硬件環(huán)境下的調(diào)優(yōu).

在介紹基于內(nèi)存的排序歸并連接算法之前，首先介紹NUMA架構(gòu)下內(nèi)存訪問的3條規(guī)則：（1）不要隨機寫相鄰內(nèi)存節(jié)點；（2）不要隨機讀相鄰內(nèi)存節(jié)點；（3）不要和相鄰內(nèi)存節(jié)點做同步.實驗證明，違反此3條規(guī)則會使性能急劇下降.

對于NUMA架構(gòu)下的并行排序歸并連接算法，可以分為排序階段、分區(qū)階段和連接階段.其中分區(qū)階段為范圍分區(qū)，且該階段并非必須存在.

4.1 無分區(qū)排序歸并連接

圖4是無分區(qū)階段的排序歸并連接算法示意圖.圖中4個NUMA節(jié)點，在2張表的數(shù)據(jù)經(jīng)過排序之后，將S表中所有的數(shù)據(jù)都傳送到含有R表分片的節(jié)點，然后進行匹配，最后輸出結(jié)果.由于沒有分區(qū)階段，該算法在連接階段采用順序讀取的方式獲取遠程內(nèi)存節(jié)點上的數(shù)據(jù)，而非采用隨機讀的方式，所以并沒有違反NUMA的第2條規(guī)則.

圖4 無分區(qū)排序歸并連接Fig.4 No partition sort merge join

4.2 有分區(qū)排序歸并連接

圖5是有分區(qū)階段的排序歸并算法示意圖.如圖所示，首先在每張表的各個節(jié)點中進行排序，然后每張表采用相同的范圍分區(qū)方法將數(shù)據(jù)重新分配到各個節(jié)點，接著各個節(jié)點內(nèi)進行排序，最后將位于同一個節(jié)點上的2張表的數(shù)據(jù)進行連接.其中分區(qū)階段涉及到對遠程內(nèi)存進行讀寫，依然采用順序讀寫方式，因此沒有違反NUMA的前兩條規(guī)則.

圖5 分區(qū)排序歸并連接Fig.5 Partitioned sort merge join

NUMA架構(gòu)下利用多CPU來運行排序歸并算法，最理想的情況是該算法性能隨著CPU核數(shù)的增多得到最大限度的提升.Albutiu在文獻［7］中提出了MPSM算法，基本的BMPSM（multi－core parallel sort merge join）算法分3個階段，第1階段排序公有表S的數(shù)據(jù)，第2階段排序私有表R的分區(qū)數(shù)據(jù)，第3階段連接2個已排序的表.B－MPSM算法的時間復雜度是｜S｜／T＊log（｜S｜／T）＋｜R｜／T＊log（｜R｜／T）＋｜R｜＋｜S｜，在線程數(shù)目增多的情況下，｜R｜＋｜S｜不會改變，因此擴展性欠佳.在基于B－MPSM的改進版P－MPSM算法中，將私有表R的數(shù)據(jù)做范圍分區(qū)，時間復雜度將變?yōu)椋黃｜／T＊log（｜S｜／T）＋｜R｜／T＊log（｜R｜／T）＋｜R｜＋｜S｜／T＋｜R｜／T，可見P－MPSM 算法依賴數(shù)據(jù)集的大小和分布.其中當｜R｜遠大于｜S｜時，P－MPSM算法的性能將不及B－MPSM算法.另外一張表內(nèi)的數(shù)據(jù)經(jīng)過范圍分區(qū)之后可能產(chǎn)生數(shù)據(jù)傾斜，直接利用靜態(tài)邊界無法保證數(shù)據(jù)被平均切分，所以在范圍分區(qū)之前需要對數(shù)據(jù)做直方圖統(tǒng)計以確定范圍分區(qū)的邊界，然后用確定的邊界切分數(shù)據(jù).

排序是排序歸并連接算法中的重要階段，并行排序是多CPU內(nèi)存環(huán)境下提升排序性能的重要方法.由于NUMA3條規(guī)則的影響，排序一般在單個內(nèi)存節(jié)點中進行，排序的性能受排序算法和硬件的影響.合理采用SIMD指令可以提升排序性能.Bitonic排序［12］作為一種常見的采用SIMD指令做優(yōu)化的排序算法，其核心內(nèi)容為雙調(diào)排序然后雙調(diào)歸并.該算法較好的利用了SIMD指令，使得一條比較指令可以作用在內(nèi)存中連續(xù)存放的記錄上，從而達到并行效果.時間復雜度為O（N）的Radix排序算法也可以并行，文獻［13］中將Radix排序放在多核機器上實現(xiàn)，文獻［14］中講述了用分區(qū)的方式使得Radix排序算法并行，文獻［15］更是強調(diào)了Radix排序在并行環(huán)境下如何做負載均衡.另外，CellSort［16］算法支持特定硬件環(huán)境下的3個層次的并行排序，分別為SIMD級、CPU級和內(nèi)存級.AAsort算法［17］能夠消除不對齊的內(nèi)存訪問帶來SIMD效率降低的情況，并證明了該算法在核數(shù)增多的情況下具有良好的擴展性.此外，由于排序算法對CPU計算能力和內(nèi)存帶寬要求較高，利用GPU這種商業(yè)處理器來處理數(shù)據(jù)的研究在近幾年也開始進行，現(xiàn)代GPU的性能比CPU的內(nèi)存帶寬和處理能力快10倍左右，主要用于線性代數(shù)計算、科學計算和幾何計算.當然GPU也可以當做協(xié)同處理器來加速數(shù)據(jù)庫查詢.

與哈希連接類似，排序歸并連接也需要考慮緩存的作用.在Jiménez－González的論文［18］中，因為Radix排序?qū)?shù)據(jù)的緩存局部性并沒有較好的支持，因此CC－sort將數(shù)據(jù)切分為可以放在緩存中的小塊，然后在每小塊數(shù)據(jù)上做排序，這樣最大限度地避免在排序的時候產(chǎn)生緩存缺失.而在最近的論文［6］中，Balkesen C將Bitonic算法改造成緩存感知的多層次并行算法，其在3個層次上充分利用了并行.Chhugani J在文獻［19］中優(yōu)化了歸并排序算法，使其獲得很好的擴展性，但是Chhugani J的論文無法排序元組，只能對單個的key排序.而Kim C在文獻［20］中對Chhugani J的排序算法進行優(yōu)化，使其可以排序元組.

5 分布式連接

分布式計算在Google發(fā)表MapReduce論文［21］之后，得到了較快的發(fā)展.Hadoop［22］系統(tǒng)作為對MapReduce編程框架的一種開源實現(xiàn)，已經(jīng)被學術(shù)界和工業(yè)界廣泛使用.與此同時，以阿里巴巴為首的許多國內(nèi)公司正在進行去IOE（IBM的小型機，Oracle的數(shù)據(jù)庫和EMC的存儲服務(wù)）運動，在高可擴展、高可用性的分布式系統(tǒng)軟件保證下，利用普通的PC服務(wù)器組成生產(chǎn)集群，這大大降低了生產(chǎn)成本.近幾年來，基于內(nèi)存計算的分布式系統(tǒng)開始嶄露頭角，以Spark為代表的內(nèi)存計算系統(tǒng)［23］開始被重視.分布式環(huán)境下基于內(nèi)存的連接算法也開始成為研究的熱點.

分布式環(huán)境下基于內(nèi)存計算的哈希連接算法根據(jù)MapReduce框架理論分為Map連接和Shuffle連接［24］.Map連接算法適用于小表連接大表，在連接操作啟動時，將小表通過分布式緩存廣播發(fā)送到含有大表分片數(shù)據(jù)的節(jié)點，在Map端完成連接，避免MapReduce中Shuffle階段對性能的消耗.Shuffle連接適用于大表，對2張表的連接屬性采用相同的哈希函數(shù)將兩張表哈希值相等的記錄傳輸?shù)较嗤?jié)點上做連接，以此達到節(jié)點間并行，Shuffle連接包含Map階段和Reduce階段.

分布式環(huán)境下基于內(nèi)存計算的排序歸并連接算法分單節(jié)點和多節(jié)點.單節(jié)點排序歸并連接即每個Map節(jié)點先進行局部排序，然后一個Reduce節(jié)點拉取2張表所有局部排序過的數(shù)據(jù)進行全局排序.多節(jié)點排序算法采用范圍分區(qū)函數(shù)將Map節(jié)點的本地數(shù)據(jù)范圍切分然后分別排序，最終將2張表相應(yīng)分區(qū)的數(shù)據(jù)傳輸?shù)綄?yīng)的Reduce節(jié)點上做歸并然后連接.

對于分布式環(huán)境下基于內(nèi)存計算的連接算法，除了單個節(jié)點內(nèi)的性能優(yōu)化，還需要考慮的因素有并行度，負載均衡和網(wǎng)絡(luò)傳輸量.此三者對分布式內(nèi)存連接算法執(zhí)行的性能有較大影響.

5.1 并行度

由于基于內(nèi)存計算處理數(shù)據(jù)的速率比基于磁盤快2個數(shù)量級，因此數(shù)據(jù)分布并非越平鋪越好，適當增大單個節(jié)點內(nèi)存中要處理的數(shù)據(jù)量，可以使系統(tǒng)調(diào)度任務(wù)的時間降低，內(nèi)存處理數(shù)據(jù)的時間比例最大化.

5.2 負載均衡

分布式連接的執(zhí)行往往隨著最后一個連接節(jié)點處理數(shù)據(jù)的結(jié)束而結(jié)束，可以通過統(tǒng)計數(shù)據(jù)的直方圖進行分區(qū)策略的選擇來使連接節(jié)點處理相同大小的數(shù)據(jù).比如CloudRamSort算法［20］首先對單個節(jié)點的數(shù)據(jù)做直方圖統(tǒng)計，然后將每個節(jié)點上的數(shù)據(jù)統(tǒng)計直方圖發(fā)送到主節(jié)點上做全局統(tǒng)計，最后決定采用什么樣的范圍分區(qū)策略來將數(shù)據(jù)分區(qū)，以達到滿足負載均衡的要求.

5.3 優(yōu)化瓶頸

分布式環(huán)境下的網(wǎng)絡(luò)傳輸是性能瓶頸［25］，當2張表數(shù)據(jù)量均非常大的時候，網(wǎng)絡(luò)滿負載是理想狀態(tài)，分布式環(huán)境下Shuffle階段不持久化數(shù)據(jù)可以使傳輸速度達到千兆網(wǎng)交換機的極限帶寬.實驗證明，數(shù)據(jù)不持久化到磁盤上的傳輸速度約為120 M／s，接近極限帶寬125 M／s，但是Shuffle中的數(shù)據(jù)如果先持久化到磁盤再傳輸，傳輸速度為30～40 M／s.可以通過省略持久化數(shù)據(jù)的方式使網(wǎng)絡(luò)傳輸速度達到允許條件下的最大值，同時也可以利用算法減少需要網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，從兩個方面控制連接算法的瓶頸.

5.4 分布式連接算法＠Claims系統(tǒng)

Claims系統(tǒng)是一個分布式環(huán)境下基于內(nèi)存計算的OLAP系統(tǒng)，它旨在利用內(nèi)存高效處理數(shù)據(jù)，并克服由于低速的網(wǎng)絡(luò)帶寬帶來的影響.基于Claims系統(tǒng)的分布式連接算法在充分利用高效的內(nèi)存計算的同時盡量減少網(wǎng)絡(luò)數(shù)據(jù)傳輸量.算法首先對每個表連接屬性的數(shù)據(jù)分布進行精確統(tǒng)計，結(jié)合并行度和計算負載均衡因素，進而建立代價模型來衡量不同調(diào)度策略下的時間開銷，并求出最優(yōu)的調(diào)度策略.實驗結(jié)果表明，Claims中的分布式連接算法大大降低了網(wǎng)絡(luò)傳輸代價，大幅度減少了響應(yīng)時間，比起當前流行的Hive和Shark等系統(tǒng)有明顯的性能提升.

6 連接算法比較

在數(shù)據(jù)庫系統(tǒng)實現(xiàn)中，對以上討論的3種連接算法均有實現(xiàn)，對于單個涉及連接的查詢來說，如何選擇連接算法，是嵌套循環(huán)連接、哈希連接還是排序歸并連接，基本要素可以分為兩點：可行性和性能.

在存在非等值連接條件的情況下，應(yīng)該采用嵌套循環(huán)連接算法及其變種，因為另外2種等值連接算法均不滿足兩表中記錄兩兩之間比較.所以出現(xiàn)諸如anti－連接，theta－連接等連接條件時，數(shù)據(jù)庫系統(tǒng)［26］的實現(xiàn)都會在嵌套循環(huán)連接的基礎(chǔ)上利用連接條件進行過濾.

兩種等值連接算法在性能方面的比較一直是學術(shù)界和工業(yè)界研究的熱點問題.當哈希連接算法出現(xiàn)之前，排序歸并連接算法已作為最優(yōu)的連接算法廣泛被采用［27］，并且是已完成排序的2張表之間連接的必然選擇.當表數(shù)據(jù)沒有排序的情況下，排序歸并連接需要即時排序，由于排序占用絕大多數(shù)性能消耗且性能并不能隨著并行度線性降低，后來提出的哈希連接算法逐漸成為性能最好的排序算法，圍繞哈希連接算法也提出了各種哈希連接變種，較出名的有Radix連接，在近幾年，內(nèi)存中的哈希連接算法更是被深入研究，很多工作都圍繞這個主題展開.近幾年來，隨著新硬件的出現(xiàn)，對這兩種算法的比較再次成為焦點.2篇近期發(fā)表的論文［6］和［28］在新硬件環(huán)境下從多個角度進行了比較.Kim C在論文［6］提出了在SIMD寬度達到256位的硬件下，其實現(xiàn)的排序歸并連接算法能夠比同樣硬件環(huán)境下哈希連接算法最優(yōu)實現(xiàn)的性能好，但是Albutiu M C在論文中加強了這一觀點，Albutiu M C實現(xiàn)了在NUMA感知的硬件環(huán)境下，排序歸并連接算法的性能比Radix連接的算法好.但是Balkesen C在其論文中表明前面兩者均沒有將文獻［6］和［8］中一些最新的哈希連接算法實現(xiàn)考慮進去，他的論文實驗表明，排序歸并在數(shù)據(jù)量比較大的時候和哈希連接更有可比性，但是大多數(shù)情況下，哈希連接算法還是占有較大優(yōu)勢，此外其實現(xiàn)的排序歸并連接算法比已有的算法都快2～3倍.

對于連接算法的選擇還有一些因素，比如傳入到查詢優(yōu)化器中的參數(shù)的個數(shù).對于這個影響因素，Blanas S在論文中提出，由于硬件調(diào)優(yōu)需要向查詢優(yōu)化器傳入較多的參數(shù)，增大查詢優(yōu)化的復雜度，反而無分區(qū)哈希連接這種對傳參沒有多少要求的算法，可以很好的避免傳輸許多參數(shù)來提升查詢優(yōu)化的性能，同時Blanas S在論文中提出無分區(qū)夠簡潔，而且其性能并不比其他的Radix連接算法的實現(xiàn)差.

7 總 結(jié)

本文分析了單機環(huán)境下的3種經(jīng)典連接算法在內(nèi)存計算環(huán)境中的熱點研究問題，也分析了當今非常流行的內(nèi)存計算的分布式系統(tǒng)中的經(jīng)典連接算法，然后討論了內(nèi)存環(huán)境中哈希連接算法和排序歸并連接算法的比較.最后簡單介紹了基于自己開發(fā)的Claims原型系統(tǒng)之上的分布式連接算法.

［1］ 普拉特納H，蔡爾A.內(nèi)存數(shù)據(jù)管理［M］.SAP譯.1版.北京：清華大學出版社，2013.

［2］ ZHOU J，ROSS K A.Implementing database operations using SIMD instructions［C］／／Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data.ACM，2002：145－156.

［3］ BALKESEN C，ALONSO G，OZSU M.Multi－core，main－memory joins：Sort vs.hash revisited［J］.Proceedings of the VLDB Endowment，2013，7（1）：85－96.

［4］ NYBERG C，BARCLAY T，CVETANOVIC Z，et al.AlphaSort：A RISC machine sort［C］／／ACM SIGMOD Record.ACM，1994，23（2）：233－242.

［5］ 楊傳輝.大規(guī)模分布式存儲系統(tǒng)：原理解析與架構(gòu)實戰(zhàn)［M］.1版.北京：機械工業(yè)出版社，2013.

［6］ BALKESEN C，TEUBNER J，ALONSO G，et al.Main－memory hash joins on multi－core CPUs：Tuning to the underlying hardware［C］／／2013 IEEE 29th International Conference on data Engineering （ICDE）IEEE，2013：362－373.

［7］ ALBUTIU M C，KEMPER A，NEUMANN T.Massively parallel sort－merge joins in main memory multi－core database systems［J］.Proceedings of the VLDB Endowment，2012，5（10）：1064－1075.

［8］ BLANAS S，LI Y，PATELJ M.Design and evaluation of main memory hash join algorithms for multi－core CPUs［C］／／Proceedings of the 2011 ACM SIGMOD International Conference on Management of data.ACM，2011：37－48.

［9］ MANEGOLD S，BONCZ P A，KERSTEN M L.Optimizing database architecture for the new bottleneck：memory access［J］.VLDB Journal，2000，9（3）：231－246.

［10］ SHATDAL A，KANT C，NAUGHTON J F.cache conscious algorithms for relational query processing［C］／／Proceedings of the 20th VLDB Conference.Santiago：［s.n.］，1994.

［11］ LI Y，PANDIS I，MüLLER R，et al.NUMA－aware algorithms：the case of data shuffling［C］／／CIDR’B.Asilomar，California：［s.n.］，2013.

［12］ IVIKIPEDIA.Bitonic sorter［EB／OL］.［2014－08－31］.http：／／en.wikipedia.org／wiki／Bitonic＿sorter.

［13］ ZAGHA M，BLELLOCH G E.Radix sort for vector multiprocessors［C］／／Proceedings of the 1991 ACM／IEEE conference on Supercomputing.ACM，1991：712－721.

［14］ INOUE H，MORIYAMA T，KOMATSU H，et al.AA－sort：A new parallel sorting algorithm for multi－core SIMD processors［C］／／Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques.IEEE Computer Society，2007：189－198.

［15］ SOHN A，KODAMA Y.Load balanced parallel radix sort［C］／／Proceedings of the 12th International Conference on Supercomputing.ACM，1998：305－312.

［16］ GEDIK B，BORDAWEKAR R R，YU P S.CellSort：High performance sorting on the cell processor［C］／／Proceedings of the 33rd International Conference on Very Large Data Bases.VLDB Endowment，2007：1286－1297.

［17］ LEE S J，JEON M，KIM D，et al.Partitioned parallel radix sort［J］.Journal of Parallel and Distributed Computing，2002，62（4）：656－668.

［18］ JIMéNEZ－GONZáLEZ D，NAVARRO J J，LARRIBA－PEY J L.CC－radix：a cache conscious sorting based on radix sort［C］／／Parallel，Distributed and Network－Based Processing，2003.Proceedings.Eleventh Euromicro Conference on.IEEE，2003：101－108.

［19］ CHHUGANI J，NGUYEN A D，LEE V W，et al.Efficient implementation of sorting on multi－core SIMD CPU architecture［J］.Proceedings of the VLDB Endowment，2008，1（2）：1313－1324.

［20］ DEAN J，GHEMAWAT S.MapReduce：simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107－113.

［21］ 懷特T.Hadoop權(quán)威指南［M］.周敏奇，王曉玲，等譯.2版.北京：清華大學出版社，2011.

［22］ ZAHARIA M，CHOWDHURY M，DAS T，et al.Resilient distributed datasets：A fault－tolerant abstraction for in－memory cluster computing［C］／／Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation.USENIX Association，2012：2－2.

［23］ XIN R S，ROSEN J，ZAHARIA M，et al.Shark：SQL and rich analytics at scale［C］／／Proceedings of the 2013 international Conference on Management of Data.ACM，2013：13－24.

［24］ KIM C，PARK J，SATISH N，et al.CloudRAMSort：fast and efficient large－scale distributed RAM sort on shared－nothing cluster［C］／／Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM，2012：841－850.

［25］ R?DIGER W，MüHLBAUER T，UNTERBRUNNER P，et al.Locality－sensitive operators for parallel mainmemory database clusters［C］／／30th IEEE International Conference on Data Engineering.ICDE，2014：48.

［26］ MONETOB.Source RPMs for Fedora［DB／OL］.［2014－08－01］.https：／／www.monetdb.org／downloads／Fedora／source.

［27］ MERRETT T H.Why sort－merge gives the best implementation of the natural join［J］.ACM SIGMOD Record，1983，13（2）：39－51.

［28］ KIM C，KALDEWEY T，LEE V W，et al.Sort vs.hash revisited：fast join implementation on modern multi－core CPUs［J］.Proceedings of the VLDB Endowment，2009，2（2）：1378－1389.