我們?cè)賮?lái)看同維表和主子表的JOIN，這兩種情況的優(yōu)化提速手段是一樣的。

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

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

但是，外鍵JOIN時(shí)不能使用這個(gè)辦法，因?yàn)槭聦?shí)表上可能有多個(gè)要參與關(guān)聯(lián)的外鍵字段，不可能讓同一個(gè)事實(shí)表同時(shí)針對(duì)多個(gè)字段都有序。

同維表和主子表卻可以!

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

一

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

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

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

二

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

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

三

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

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

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

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

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