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

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

0 引 言

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

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

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

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

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

1 連接算法影響因素

1.1 并行策略

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

（1）線程級(jí)別并行

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

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

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

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

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

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

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

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

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

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

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

線程個(gè)數(shù)和核數(shù)的比例會(huì)對(duì)算法性能產(chǎn)生影響.在每個(gè)核中運(yùn)行的線程會(huì)因?yàn)橥交蛘哂布g隔暫停正在處理的操作，此時(shí)CPU核處于空轉(zhuǎn)狀態(tài).如果線程數(shù)和核數(shù)相同，CPU核會(huì)經(jīng)常處于空閑狀態(tài).通常當(dāng)線程數(shù)是核數(shù)4倍的時(shí)候，CPU核的負(fù)載會(huì)被充分利用.

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

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

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

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

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

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

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

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

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

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

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

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

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

3 哈希連接

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

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

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

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

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

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

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

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

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

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

（2）Radix連接

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

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

（3）并行Radix連接

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

圖3 radix連接Fig.3 Radix join

4 排序歸并連接

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

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

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

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

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

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

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

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

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

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

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

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

5 分布式連接

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

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

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

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

5.1 并行度

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

5.2 負(fù)載均衡

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

5.3 優(yōu)化瓶頸

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

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

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

6 連接算法比較

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

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

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

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

7 總 結(jié)

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

［1］ 普拉特納H，蔡爾A.內(nèi)存數(shù)據(jù)管理［M］.SAP譯.1版.北京：清華大學(xué)出版社，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ī)模分布式存儲(chǔ)系統(tǒng)：原理解析與架構(gòu)實(shí)戰(zhàn)［M］.1版.北京：機(jī)械工業(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版.北京：清華大學(xué)出版社，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.