對(duì)于企業(yè)建設(shè)網(wǎng)站來(lái)講，JOIN 一直是數(shù)據(jù)庫(kù)性能優(yōu)化的老大難問(wèn)題，本來(lái)挺快的查詢，一旦涉及了幾個(gè) JOIN，性能就會(huì)陡降。而且，參與 JOIN 的表越大越多，性能就越難提上來(lái)。

其實(shí)，讓 JOIN 跑得快的關(guān)鍵是要對(duì) JOIN 分類(lèi)，分類(lèi)之后，就能利用各種類(lèi)型 JOIN 的特征來(lái)做性能優(yōu)化了。

JOIN 分類(lèi)

有 SQL 開(kāi)發(fā)經(jīng)驗(yàn)的同學(xué)都知道，絕大多數(shù) JOIN 都是等值 JOIN，也就是關(guān)聯(lián)條件為等式的 JOIN。非等值 JOIN 要少見(jiàn)得多，而且多數(shù)情況也可以轉(zhuǎn)換成等值 JOIN 來(lái)處理，所以我們可以只討論等值 JOIN。

等值 JOIN 主要又可以分為兩大類(lèi)：外鍵關(guān)聯(lián)和主鍵關(guān)聯(lián)。

外鍵關(guān)聯(lián)是指用一個(gè)表的非主鍵字段，去關(guān)聯(lián)另一個(gè)表的主鍵，前者稱(chēng)為事實(shí)表，后者為維表。比如下圖中，訂單表是事實(shí)表，客戶表、產(chǎn)品表、雇員表是維表。

外鍵表是多對(duì)一關(guān)系，而且是不對(duì)稱(chēng)的，事實(shí)表和維表的位置不能互換。需要說(shuō)明的是，這里說(shuō)的主鍵是指邏輯上的主鍵，也就是在表中取值唯一、可以用于唯一確定某條記錄的字段（或字段組），不一定在數(shù)據(jù)庫(kù)表上建立過(guò)主鍵。

主鍵關(guān)聯(lián)是指用一個(gè)表的主鍵關(guān)聯(lián)另一個(gè)表的主鍵或部分主鍵。比如下圖中客戶和 VIP 客戶、訂單表和訂單明細(xì)表的關(guān)聯(lián)。

客戶和 VIP 客戶按照主鍵關(guān)聯(lián)，這兩個(gè)表互為同維表。訂單則是用主鍵去關(guān)聯(lián)明細(xì)的部分主鍵，我們稱(chēng)訂單表是主表，明細(xì)表是子表。

同維表是一對(duì)一關(guān)系。且同維表之間是對(duì)稱(chēng)的，兩個(gè)表的地位相同。主子表則是一對(duì)多關(guān)系，而且是不對(duì)稱(chēng)的，有明確的方向。

仔細(xì)觀察會(huì)發(fā)現(xiàn)，這兩類(lèi) JOIN 都涉及到主鍵了。而不涉及主鍵的 JOIN 會(huì)導(dǎo)致多對(duì)多關(guān)系，大多數(shù)情況都沒(méi)有業(yè)務(wù)意義。換句話說(shuō)，上述這兩大類(lèi) JOIN 涵蓋了幾乎全部有業(yè)務(wù)意義的 JOIN。如果我們能利用 JOIN 總會(huì)涉及主鍵這個(gè)特征做性能優(yōu)化，能解決掉這兩大類(lèi) JOIN，其實(shí)也就意味著解決了大部分 JOIN 性能問(wèn)題。

但是，SQL 對(duì) JOIN 的定義并不涉及主鍵，只是兩個(gè)表做笛卡爾積后再按某種條件過(guò)濾。這個(gè)定義很簡(jiǎn)單也很寬泛，幾乎可以描述一切。但是，如果嚴(yán)格按這個(gè)定義去實(shí)現(xiàn) JOIN，也就沒(méi)辦法在性能優(yōu)化時(shí)利用主鍵的特征了。

SPL 改變了 JOIN 的定義，專(zhuān)門(mén)針對(duì)這兩大類(lèi) JOIN 分別處理，利用了主鍵的特征減少運(yùn)算量，從而實(shí)現(xiàn)性能優(yōu)化的目標(biāo)。

下面我們來(lái)看看 SPL 具體是怎么做的。

外鍵關(guān)聯(lián)

如果事實(shí)表和維表都不太大，可以全部裝入內(nèi)存，SPL 提供了外鍵地址化方法：先把事實(shí)表中的外鍵字段值轉(zhuǎn)換為對(duì)應(yīng)維表記錄的地址，之后引用維表字段時(shí)，就可以用地址直接取出了。

以前面的訂單表、雇員表為例，假定這兩個(gè)表已經(jīng)被讀入內(nèi)存。外鍵地址化的工作機(jī)制是這樣的：對(duì)于訂單表某記錄 r 的 eid 字段，到雇員表中找到這個(gè) eid 字段值對(duì)應(yīng)的記錄，得到其內(nèi)存地址 a，再將 r 的 eid 字段值替換成 a。對(duì)訂單表的所有記錄都做好這樣的轉(zhuǎn)換，就完成了外鍵地址化。這時(shí)候，訂單表記錄 r 要引用雇員表字段時(shí)，直接用 eid 字段存儲(chǔ)的地址 a 取出雇員表記錄和字段就可以了，相當(dāng)于常數(shù)時(shí)間內(nèi)就能取得雇員表的字段，不需要再到雇員表做查找。

可以在系統(tǒng)啟動(dòng)時(shí)把事實(shí)表和維表讀入內(nèi)存，并一次性做好外鍵地址化，即預(yù)關(guān)聯(lián)。這樣，在后續(xù)關(guān)聯(lián)計(jì)算時(shí)就能直接用事實(shí)表外鍵字段中的地址去取維表記錄，完成高性能的 JOIN 計(jì)算。

SQL 通常使用 HASH 算法來(lái)做內(nèi)存連接，需要計(jì)算 HASH 值和比對(duì)，性能會(huì)比直接用地址讀取差很多。

SPL 之所以能實(shí)現(xiàn)外鍵地址化，是利用了維表的關(guān)聯(lián)字段是主鍵這一特征。上面例子中，關(guān)聯(lián)字段 eid 是雇員表的主鍵，具有唯一性。訂單表中的每個(gè) eid 只會(huì)唯一對(duì)應(yīng)一條雇員記錄，所以才能把每個(gè) eid 轉(zhuǎn)換成它唯一對(duì)應(yīng)的那條雇員記錄的地址。

而 SQL 對(duì) JOIN 的定義中沒(méi)有主鍵的約定，就不能認(rèn)定與事實(shí)表中外鍵關(guān)聯(lián)的維表記錄有唯一性，有可能發(fā)生與多條記錄關(guān)聯(lián)的情況。對(duì)于訂單表的記錄來(lái)講，eid 值沒(méi)有辦法唯一對(duì)應(yīng)一條雇員記錄，就無(wú)法做到外鍵地址化了。而且 SQL 也沒(méi)有記錄地址這種數(shù)據(jù)類(lèi)型，結(jié)果會(huì)導(dǎo)致每次關(guān)聯(lián)時(shí)還是要計(jì)算 HASH 值并比對(duì)。

只是兩個(gè)表 JOIN 時(shí)，外鍵地址化和 HASH 關(guān)聯(lián)的差別還不是非常明顯。這是因?yàn)?JOIN 并不是最終目的，JOIN 之后還會(huì)有其它很多運(yùn)算，JOIN 本身運(yùn)算消耗時(shí)間的占比相對(duì)不大。但事實(shí)表常常會(huì)有多個(gè)維表，甚至維表還會(huì)有很多層。比如訂單關(guān)聯(lián)產(chǎn)品，產(chǎn)品關(guān)聯(lián)供應(yīng)商，供應(yīng)商關(guān)聯(lián)城市，城市關(guān)聯(lián)國(guó)家等等。在關(guān)聯(lián)表很多時(shí)，外鍵地址化的性能優(yōu)勢(shì)會(huì)更明顯。

下面的測(cè)試，在關(guān)聯(lián)表個(gè)數(shù)不同的情況下對(duì)比 SPL 與 Oracle 的性能差異，可以看出在表很多時(shí)，外鍵地址化的優(yōu)勢(shì)相當(dāng)明顯：

對(duì)于只有維表能裝入內(nèi)存，而事實(shí)表很大需要外存的情況，SPL 提供了外鍵序號(hào)化方法：預(yù)先將事實(shí)表中的外鍵字段值轉(zhuǎn)換為維表對(duì)應(yīng)記錄的序號(hào)。關(guān)聯(lián)計(jì)算時(shí)，分批讀入新事實(shí)表記錄，再用序號(hào)取出對(duì)應(yīng)維表記錄。

對(duì)于網(wǎng)站建設(shè)公司來(lái)講，以上述訂單表、產(chǎn)品表為例，假定產(chǎn)品表已經(jīng)裝入內(nèi)存，訂單表存儲(chǔ)在外存中。外鍵序號(hào)化的過(guò)程是這樣：先讀入一批訂單數(shù)據(jù)，設(shè)其中某記錄 r 中的 pid 對(duì)應(yīng)的是內(nèi)存中產(chǎn)品表的第 i 條記錄。我們要將 r 中的 pid 字段值轉(zhuǎn)換為 i。對(duì)這批訂單記錄都完成這樣的轉(zhuǎn)換后，再做關(guān)聯(lián)計(jì)算時(shí)，從外存中分批讀入訂單數(shù)據(jù)。對(duì)于其中的記錄 r，就可以直接根據(jù) pid 值，去內(nèi)存中的產(chǎn)品表里用位置取出相應(yīng)的記錄，也避免了查找動(dòng)作。

數(shù)據(jù)庫(kù)通常會(huì)把小表讀入內(nèi)存，再分批讀入大表數(shù)據(jù)，用哈希算法做內(nèi)存連接，需要計(jì)算哈希值和比對(duì)。而 SPL 使用序號(hào)定位是直接讀取，不需要進(jìn)行任何比對(duì)，性能優(yōu)勢(shì)比較明顯。雖然預(yù)先把事實(shí)表的外鍵字段轉(zhuǎn)換成序號(hào)需要一定成本，但這個(gè)預(yù)計(jì)算只需要做一次，而且可以在多次外鍵關(guān)聯(lián)中得到復(fù)用。

企業(yè)網(wǎng)站設(shè)計(jì)，SPL 外鍵序號(hào)化同樣利用了維表關(guān)聯(lián)字段是主鍵的特征。如前所述，SQL 對(duì) JOIN 的定義沒(méi)有主鍵的約定，無(wú)法利用這一特征做到外鍵序號(hào)化。另外，SQL 使用無(wú)序集合的概念，即使我們事先把外鍵序號(hào)化了，數(shù)據(jù)庫(kù)也無(wú)法利用這個(gè)特點(diǎn)，不能在無(wú)序集合上使用序號(hào)快速定位的機(jī)制，最快也就是用索引查找。而且，數(shù)據(jù)庫(kù)并不知道外鍵被序號(hào)化了，仍然會(huì)去計(jì)算 HASH 值和比對(duì)。

下面這個(gè)測(cè)試，在不同并行數(shù)情況下，對(duì)比 SPL 和 Oracle 完成大事實(shí)表、小維表關(guān)聯(lián)計(jì)算的速度，SPL 跑的比 Oracle 快 3 到 8 倍。測(cè)試結(jié)果見(jiàn)下圖：

如果維表很大也需要外存，而事實(shí)表較小能裝入內(nèi)存，SPL 則提供了大維表查找機(jī)制。如果維表和事實(shí)表都很大，SPL 則使用單邊分堆算法。對(duì)于維表過(guò)濾后再關(guān)聯(lián)的情況，SPL 提供了索引復(fù)用方法及對(duì)位序列等方法。

數(shù)據(jù)量大到需要分布式計(jì)算時(shí)，如果維表較小，SPL 采用復(fù)寫(xiě)維表機(jī)制，將維表在集群節(jié)點(diǎn)上復(fù)制多份；如果維表很大，則采用集群維表方法以保證隨機(jī)訪問(wèn)。這兩種方法都可以有效的避免 Shuffle 動(dòng)作。相比而言，SQL 體系下不能區(qū)分出維表，HASH 拆分方法要將兩個(gè)表都做 Shuffle 動(dòng)作，網(wǎng)絡(luò)傳輸量要大得多。

主鍵關(guān)聯(lián)

主鍵關(guān)聯(lián)涉及的表一般都比較大，需要存儲(chǔ)在外存中。SPL 為此提供了有序歸并方法：預(yù)先將外存表按照主鍵有序存儲(chǔ)，關(guān)聯(lián)時(shí)順序取出數(shù)據(jù)做歸并計(jì)算。

以客戶和 VIP 客戶兩個(gè)表做內(nèi)連接為例，假設(shè)已經(jīng)預(yù)先將兩個(gè)表按照主鍵 cid 有序存儲(chǔ)在外存中。關(guān)聯(lián)時(shí)，從兩個(gè)表的游標(biāo)中讀取記錄，逐條比較 cid 值。如果 cid 相等，則將兩表的記錄合并成結(jié)果游標(biāo)的一條記錄返回。如果不相等，則 cid 小的那個(gè)游標(biāo)再讀取記錄，繼續(xù)判斷。重復(fù)這些動(dòng)作直到任何一個(gè)表的數(shù)據(jù)被取完，返回的游標(biāo)就是 JOIN 的結(jié)果。

對(duì)于兩個(gè)大表關(guān)聯(lián)，數(shù)據(jù)庫(kù)通常使用哈希分堆算法，復(fù)雜度是乘法級(jí)的。而有序歸并算法復(fù)雜度是加法級(jí)，性能會(huì)好很多。而且，數(shù)據(jù)庫(kù)做大數(shù)據(jù)的外存運(yùn)算時(shí)，哈希分堆會(huì)產(chǎn)生緩存文件的讀寫(xiě)動(dòng)作。有序歸并算法則只需要對(duì)兩個(gè)表依次遍歷，不必借助外存緩存，可以大幅降低 IO 量，有巨大的性能優(yōu)勢(shì)。

預(yù)先按照主鍵排序的成本雖高，但是一次性做好即可，以后就總能使用歸并算法實(shí)現(xiàn) JOIN，性能可以提高很多。同時(shí)，SPL 也提供了在有追加數(shù)據(jù)時(shí)仍然保持?jǐn)?shù)據(jù)整體有序的方案。

這類(lèi) JOIN 的特征在于關(guān)聯(lián)字段是主鍵或部分主鍵，有序歸并算法正是根據(jù)這個(gè)特征來(lái)設(shè)計(jì)的。因?yàn)椴还苁峭S表還是主子表，關(guān)聯(lián)字段都不會(huì)是主鍵之外的其他字段，所以我們將關(guān)聯(lián)表按照主鍵有序這一種方式排序存儲(chǔ)就可以了，不會(huì)出現(xiàn)冗余。而外鍵關(guān)聯(lián)就不具備這個(gè)特征，不能使用有序歸并。具體來(lái)說(shuō)，是因?yàn)槭聦?shí)表的關(guān)聯(lián)字段不是主鍵，會(huì)存在多個(gè)要參與關(guān)聯(lián)的外鍵字段，我們不可能讓同一個(gè)事實(shí)表同時(shí)按多個(gè)字段都有序。

SQL 對(duì) JOIN 的定義不區(qū)分 JOIN 類(lèi)型，不假定某些 JOIN 總是針對(duì)主鍵的，就沒(méi)辦法從算法層面上利用主鍵關(guān)聯(lián)的特征。而且，前面說(shuō)過(guò) SQL 基于無(wú)序集合概念，數(shù)據(jù)庫(kù)不會(huì)刻意保證數(shù)據(jù)的物理有序性，很難實(shí)施有序歸并算法。

有序歸并算法的優(yōu)勢(shì)還在于易于分段并行。以訂單和訂單明細(xì)按 oid 關(guān)聯(lián)為例，假如將兩表都按照記錄數(shù)大致平均分為 4 段，訂單第 2 段的 oid 有可能會(huì)出現(xiàn)在明細(xì)第 3 段，類(lèi)似的錯(cuò)位會(huì)導(dǎo)致錯(cuò)誤的計(jì)算結(jié)果。SPL 再次利用主鍵 oid 的有序性，提供同步分段機(jī)制，解決了這個(gè)問(wèn)題：先將有序的訂單表分為 4 段，再找到每一段起止記錄的 oid 值形成 4 個(gè)區(qū)間，將明細(xì)表也分成同步的 4 段。這樣，在并行計(jì)算時(shí)兩表對(duì)應(yīng)分段就不會(huì)出現(xiàn)錯(cuò)位了。由于明細(xì)表也對(duì) oid 有序，可以迅速地按照起止 oid 定位，不會(huì)降低有序歸并的性能。

傳統(tǒng)的 HASH 分堆技術(shù)實(shí)現(xiàn)并行就比較困難了，多線程做 HASH 分堆時(shí)需要同時(shí)向某個(gè)分堆寫(xiě)出數(shù)據(jù)，造成共享資源沖突；而下一步實(shí)現(xiàn)某組分堆關(guān)聯(lián)時(shí)又會(huì)消費(fèi)大量?jī)?nèi)存，無(wú)法實(shí)施較大的并行數(shù)量。

實(shí)際測(cè)試證明，在相同情況下，我們對(duì)兩個(gè)大表做主鍵關(guān)聯(lián)測(cè)試，結(jié)果是 SPL 比 Oracle 快了近 3 倍：

除了有序歸并，SPL 還提供了很多高性能算法，全面提高主鍵關(guān)聯(lián) JOIN 的計(jì)算速度。包括：附表機(jī)制，可以將多表一體化存儲(chǔ)，減少存儲(chǔ)數(shù)據(jù)量的同時(shí)，還相當(dāng)于預(yù)先完成了關(guān)聯(lián)，不需要再比對(duì)了；關(guān)聯(lián)定位算法，實(shí)現(xiàn)先過(guò)濾再關(guān)聯(lián)，可以避免全表遍歷，獲得更好的性能等等。

當(dāng)數(shù)據(jù)量繼續(xù)增加，需要多臺(tái)服務(wù)器集群時(shí)，SPL 提供復(fù)組表機(jī)制，將需要關(guān)聯(lián)的大表按照主鍵分布到集群節(jié)點(diǎn)上。相同主鍵的數(shù)據(jù)在同一節(jié)點(diǎn)，避免分機(jī)之間的數(shù)據(jù)傳輸，也不會(huì)出現(xiàn) Shuffle 動(dòng)作。

回顧與總結(jié)

回顧上面兩大類(lèi)、各場(chǎng)景 JOIN，采用 SPL 分情況提供的高性能算法，可以利用不同類(lèi)型 JOIN 的特征提速，讓 JOIN 跑得更快。SQL 對(duì)上述這么多種 JOIN 場(chǎng)景籠統(tǒng)的處理，就沒(méi)辦法針對(duì)不同 JOIN 的特征來(lái)實(shí)施這些高性能算法。比如：事實(shí)表和維表都裝入內(nèi)存時(shí)，SQL 只能按照鍵值計(jì)算 HASH 和比對(duì)，無(wú)法利用地址直接對(duì)應(yīng)；SQL 數(shù)據(jù)表無(wú)序，在大表按照主鍵關(guān)聯(lián)時(shí)無(wú)法做到有序歸并，只能使用 HASH 分堆，有可能會(huì)出現(xiàn)多次緩存的現(xiàn)象，性能有一定的不可控性。

并行計(jì)算方面，SQL 單表計(jì)算時(shí)還容易做到分段并行，多表關(guān)聯(lián)運(yùn)算時(shí)一般就只能事先做好固定分段，很難做到同步動(dòng)態(tài)分段，這就難以根據(jù)機(jī)器的負(fù)載臨時(shí)決定并行數(shù)量。

對(duì)于集群運(yùn)算也是這樣，SQL 在理論上不區(qū)分維表和事實(shí)表，要實(shí)現(xiàn)大表 JOIN 就會(huì)不可避免地產(chǎn)生占用大量網(wǎng)絡(luò)資源的 HASH Shuffle 動(dòng)作，在集群節(jié)點(diǎn)數(shù)太多時(shí)，網(wǎng)絡(luò)傳輸造成的延遲會(huì)超過(guò)節(jié)點(diǎn)多帶來(lái)的好處。

SPL 設(shè)計(jì)并應(yīng)用了新的運(yùn)算和存儲(chǔ)模型，可以在原理和實(shí)現(xiàn)上解決 SQL 的這些問(wèn)題。對(duì)于 JOIN 的不同分類(lèi)和場(chǎng)景，程序員有針對(duì)性的采取上述高性能算法，就能獲得更快的計(jì)算速度，讓 JOIN 跑得更快。