我們再來看同維表和主子表的JOIN，這兩種情況的優化提速手段是一樣的。

設兩個關聯表的規模(記錄數)分別是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)。歸并算法的細節有很多材料介紹，這里就不再贅述了。

但是，外鍵JOIN時不能使用這個辦法，因為事實表上可能有多個要參與關聯的外鍵字段，不可能讓同一個事實表同時針對多個字段都有序。

同維表和主子表卻可以!

因為同維表和主子表總是針對主鍵或主鍵的一部分關聯，我們可以事先把這些關聯表的數據按其主鍵排序。排序的成本雖然較高，但是一次性的。一旦完成了排序，以后就可以總是使用歸并算法實現JOIN，效率能提高很多。

一

有序歸并的意義還在于大數據的情況。象訂單及其明細這種主子表是不斷增長的事實表，時間長了常常會積累得非常大。

當要JOIN的兩個表都大到內存無法放下的時候，關系數據庫仍然是使用HASH分段的技術。根據關聯字段的HASH值，將數據分成若干段，每段都足夠小到能裝入內存再實施內存的HASH分段算法。但這會發生外存倒換的問題，數據需要先分段寫出再讀入，多出一寫一讀，外存讀本來就不快，寫就更慢，這樣性能會差出很多。運氣不好時，一次HASH分段時可能會發生某段仍然太大而無法裝入內存，這時就需要二次HASH，進一步加劇這個問題。而且，HASH分段算法在處理每一段時需要把整段讀入內存，為了減少分段數量，就會根據內存大小盡量讓分段變大，這樣會用光所有內存，有并發運算時就會嚴重影響其它任務的性能。

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

二

SQL采用笛卡爾積定義的JOIN運算不區分JOIN類型，不假定某些JOIN總是針對主鍵的，就沒辦法從算法層面上利用這一特點，只能在工程層面進行優化。有些數據庫會檢查數據表在物理存儲上是否針對關聯字段有序，如果有序則采用歸并算法，但基于無序集合概念的關系數據庫不會刻意保證數據的物理有序性，許多操作都會破壞歸并算法的實施條件。使用索引可以實現數據的邏輯有序，但物理無序時的遍歷效率還是會大打折扣。

有序歸并的前提是將數據按主鍵排序，而這類數據常常會不斷追加，原則上每次追加后就要再次排序，而我們知道大數據排序成本通常很高，這是否會導致追加數據難度很大呢?其實，追加數據再加入的過程也是個有序歸并，把新增數據單獨排序后和已有序的歷史數據歸并，復雜度是線性的，相當于把所有數據重寫一次，而不象常規的大數據排序需要緩存式寫出再讀入。在工程上做些優化動作還可以做到不必每次都全部重寫，進一步提高維護效率。

三

有序歸并的好處還在于易于分段并行。

現代計算機的都有多核CPU，SSD硬盤也有較強的并發能力，使用多進程(或線程)并行計算就能夠顯著提高性能。但傳統的HASH分段技術很難實現并行，多進程做HASH分段時需要同時向某個分段寫出數據，造成共享資源沖突;而計算某一段又會幾乎耗光所有內存，其它并行任務就無法實施。

使用有序歸并實現并行計算時需要把數據分成多段，單個表分段比較簡單，但兩個關聯表分段時必須同步對齊，否則歸并時兩個表數據錯位了，就無法得出正確的計算結果，而數據有序就可以保證高性能的同步對齊分段。

先按主表(同維表則取較大的即可，其它討論不影響)分段(如何能夠較平均地分段且支持數據追加，我們以后會撰文解釋)，讀出每段***條記錄的主鍵值，然后用這些鍵值到子表用二分法尋找定位(是否可以執行二分法和數據存儲格式相關，后續文章也會談到)，從而獲得子表的分段點。這樣可以保證主子表的分段是同步對齊的。

因為鍵值有序，所以主表每段的記錄鍵值都屬于某個連續區間，鍵值在區間外的記錄不會在這一段，鍵值在區間內的記錄一定在這一段，子表對應分段的記錄鍵值也有這個特性，所以不會發生錯位情況;而同樣因為鍵值有序，才可以在子表中執行高效的二分查找迅速定位出分段點。即數據有序保證了分段的合理性及高效性，這樣就可以放心地執行并行算法了。