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

設兩個關聯(lián)表的規(guī)模(記錄數(shù))分別是N和M，則HASH分段技術的計算復雜度(關聯(lián)字段的比較次數(shù))大概是SUM(Ni*Mi)，其中Ni和Mi分別是HASH值為i的兩表記錄數(shù)，滿足N=SUM(Ni)和M=SUM(Mi)，這大概率會比完全遍歷時的復雜度N*M要小很多(運氣較好的時候會小K倍，K是HASH值的取值范圍)。

如果這兩個表針對關聯(lián)鍵都有序，那么我們就可以使用歸并算法來處理關聯(lián)，這時的復雜度是N+M;在N和M都較大的時候(一般都會遠大于K)，這個數(shù)會遠小于剛才那個SUM(Ni*Mi)。歸并算法的細節(jié)有很多材料介紹，這里就不再贅述了。

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

同維表和主子表卻可以!

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

一

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

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

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

二

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

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

三

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

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

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

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

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