一、 問題背景與適用場景

在以前的文章中我們介紹過，關係資料庫在進行表間關聯時是使用HASH分段技術。設兩個關聯表的規模（記錄數）分別是 N 和 M，則 HASH 分段技術的計算複雜度（關聯欄位的比較次數）大概是 SUM(Ni*Mi)，其中 Ni 和 Mi 分別是 HASH 值為 i 的兩表記錄數，滿足 N=SUM(Ni) 和 M=SUM(Mi)，這大機率會比完全遍歷時的複雜度 N*M 要小很多（運氣較好的時候會小 K 倍，K 是 HASH 值的取值範圍）。

如果這兩個錶針對關聯鍵都有序，那麼我們就可以使用歸併演算法來處理關聯，這時的複雜度是 N+M；在 N 和 M 都較大的時候（一般都會遠大於 K），這個數會遠小於剛才那個 SUM(Ni*Mi)。因此有序歸併關聯的計算速度會比HASH分段關聯快很多。

在實際應用中，因為同維表和主子表總是針對主鍵或主鍵的一部分關聯，我們可以事先把這些關聯表的資料按其主鍵排序，以後就可以總是使用歸併演算法實現關聯，效率能提高很多。SPL即採用了這樣的演算法。

下面我們就用集算器SPL與關係資料庫Oracle作個對比，來測試一下有序歸併關聯的效率。

二、 測試環境

1、小資料全記憶體測試

測試機有兩個Intel2670 CPU，主頻2.6G，共16核，記憶體128G，SSD固態硬碟。

採用TPCH標準生成的50G資料，主表是orders，子表是orderdetail(由lineitem表資料記錄減少後生成)。兩表中記錄分別按O_ORDERKEY、L_ORDERKEY升序排列。

Oracle和SPL均使用單執行緒測試。

2、大資料外存測試

採用前述測試機中的虛擬機器，記憶體16G，SSD固態硬碟。

採用TPCH標準生成的200G資料，主表是orders，子表是lineitem。兩表中記錄分別按O_ORDERKEY、L_ORDERKEY升序排列。

因資料量比較大，Oracle和SPL均使用8執行緒並行測試。

三、 小資料全記憶體測試1. Oracle測試

（1）無關聯測試

測試的SQL語句如下：

select

l_year,

sum(volume) as revenu,

sum(l_quantity) as quantity

from

(

select

extract(year from l_shipdate) as l_year,

(l_extendedprice * (1 - l_discount) ) as volume,

l_quantity

from

orderdetail

)

group by

l_year

union all

select

2019 as l_year,

count(o_orderkey) as revenu,

count(o_totalprice) as quantity

from

orders;

（2）有關聯測試

測試的SQL語句如下：

select

l_year,

sum(volume) as revenu,

sum(l_quantity) as quantity

from

(

select

extract(year from l_shipdate) as l_year,

(l_extendedprice * (1 - l_discount) ) as volume,

l_quantity

from

orders,

orderdetail

where

o_orderkey = l_orderkey

and l_quantity>0

)

group by

l_year;

查詢條件 l_quantity>0 始終為真，沒有過濾資料，是為了確保會讀取這一列資料。

2. SPL測試

（1）無關聯測試

編寫SPL指令碼如下：

（2）有關聯測試

編寫SPL指令碼如下：

A6中的joinx就是有序歸併關聯函式，要求關聯欄位都按升序排列。

3. 測試結果及分析

測試結果列表如下(單位：秒)：

每種測試結果都是多次執行、資料充分快取以後，取最快的一次。

分析兩句SQL，無關聯測試中對orders表讀出O_ORDERKEY、O_TOTALPRICE兩列並統計記錄數，對orderdetail表讀出L_ORDERKEY、L_EXTENDEDPRICE、L_DISCOUNT、L_SHIPDATE、L_QUANTITY 五列，並對銷售價格求和、對L_QUANTITY求和。而在有關聯測試中，對orders和orderdetail表的讀取量相同，同時對關聯後的銷售價格求和、對L_QUANTITY求和。兩種情況下的讀取和計算量基本是相當的，多出的操作就是兩表間的關聯，所以兩者的執行時間差就是關聯操作用時。同理，SPL也是如此。

在同樣的硬體裝置和資料規模下，SPL關聯用時18秒，Oracle關聯用時51秒，幾乎是前者的3倍，而且SPL是Java編寫的程式，而Oracle是C++實現的，這充分驗證了有序歸併關聯能夠極大地提高關聯效率。SPL有關聯比無關聯時速度慢了2.3倍，Oracle慢了4.2倍，說明有序歸併計算與普通計算速度相當，而HASH關聯比普通計算要慢很多。

四、 大資料外存測試

當要 JOIN 的兩個表都大到記憶體無法放下的時候，關係資料庫仍然是使用 HASH 分段的技術。根據關聯欄位的 HASH 值，將資料分成若干段，每段都足夠小到能裝入記憶體再實施記憶體的 HASH 分段演算法。但這會發生外存倒換的問題，資料需要先分段寫出再讀入，多出一寫一讀，外存讀本來就不快，寫就更慢，這樣效能會差出很多。

有序歸併關聯則沒有這個問題，兩個表的資料都只要遍歷一次就行了，不僅是 CPU 的計算量減少，外存的 IO 量也大幅下降。而且，執行歸併演算法需要的記憶體很少，只要在記憶體中為每個表保持數條快取記錄就可以了，幾乎不會影響其它併發任務對記憶體的需求。

1. Oracle測試

（1）無關聯測試

測試的SQL語句與小資料測試相同，只需把orderdetail表改成lineitem表，另在第一個select後新增“ /*+ parallel(8) */”使用8執行緒並行。

（2）有關聯測試

測試的SQL語句與小資料測試相同，只需把orderdetail表改成lineitem表，另在第一個select後新增“ /*+ parallel(8) */”使用8執行緒並行。

2. SPL測試

（1）無關聯測試

編寫SPL指令碼如下：

資料量大，A2和A4都使用8路並行遊標讀數。

（2）有關聯測試

編寫SPL指令碼如下：

A3中生成遊標時用了A2作為引數，表示與主表orders的主鍵同步分段讀取。

A4中的joinx就是有序歸併關聯函式，要求關聯欄位都按升序排列。

3. 測試結果及分析

測試結果列表如下(單位：秒)：

計算量分析及關聯用時計算與小資料測試同理。

在同樣的硬體裝置和資料規模下，SPL關聯用時31秒，Oracle關聯用時598秒，是前者的19倍，更進一步驗證了有序歸併關聯能夠極大地提高關聯效率。與小資料測試時相比，倍數大大增加，說明資料量越大，有序歸併關聯比HASH關聯的效能提升優勢越明顯。

有關聯比無關聯變慢的倍數也可以得出與小資料測試時同樣的結論，不過這裡比小資料測試時多了讀取資料的時間(小資料時資料全部快取到記憶體了)，所以無關聯測試時的時間基數變大了，變慢倍數看起來反而比小資料測試時減小了。