前言

• 之前經(jīng)歷過從零到一初創(chuàng)項(xiàng)目，也有海量數(shù)據(jù)項(xiàng)目；總體來說當(dāng)項(xiàng)目在逐漸發(fā)展過程中如何構(gòu)建一個(gè)安全可靠，穩(wěn)定的數(shù)據(jù)存儲(chǔ)一直是項(xiàng)目中最核心、最重要、最關(guān)鍵部分，沒有之一
• 接下來我會(huì)體系化輸出存儲(chǔ)系列文章；本篇文章我們先談一下數(shù)據(jù)中一個(gè)最令人頭疼的連接運(yùn)算—JOIN
• JOIN 一直是SQL中的老大難問題。在關(guān)聯(lián)表稍多一點(diǎn)的時(shí)候，代碼書寫就變得很容易出錯(cuò)了且因?yàn)镴OIN語句的復(fù)雜，導(dǎo)致關(guān)聯(lián)查詢也一向是BI軟件的軟肋，幾乎沒有BI軟件能讓業(yè)務(wù)用戶順暢地完成多表關(guān)聯(lián)查詢。對于性能優(yōu)化也是，關(guān)聯(lián)表較多或者數(shù)據(jù)量大時(shí)，JOIN的性能也很難得到提升
• 基于以上，本文將對JOIN運(yùn)算進(jìn)行體系化深入的探討，根據(jù)自己工作經(jīng)驗(yàn)及參考業(yè)界經(jīng)典案例，針對性地提出語法簡化和性能優(yōu)化的方法論，希望對大家有所幫助

一圖總覽

SQL中的JOIN

SQL是如何理解JOIN運(yùn)算

SQL對JOIN的定義

兩個(gè)集合（表）做笛卡爾積后再按某種條件過濾，寫出來的語法就是A JOIN B ON …。

• 理論上講，笛卡爾積的結(jié)果集應(yīng)該是以兩個(gè)集合成員構(gòu)成的二元組作為成員，不過由于SQL中的集合也就是表，其成員總是有字段的記錄，而且也不支持泛型數(shù)據(jù)類型來描述成員為記錄的二元組，所以就簡單地把結(jié)果集處理成兩表記錄的字段合并后構(gòu)成的新記錄的集合。
• 這也是JOIN一詞在英語中的原意（即把兩個(gè)記錄的字段連接起來），并沒有乘法（笛卡爾積）的意思。不過，把笛卡爾積成員理解成二元組還是合并字段的記錄，并不影響我們后續(xù)的討論。

JOIN定義

• JOIN的定義中并沒有約定過濾條件的形式，理論上，只要結(jié)果集是兩個(gè)源集合笛卡爾積的子集，都是合理的JOIN運(yùn)算。
• 例子：假設(shè)集合A={1,2},B={1,2,3}，A JOIN B ON A<B的結(jié)果就是{(1,2),(1,3),(2,3)}；A JOIN B ON A=B的結(jié)果是{(1,1),(2,2)}。

JOIN分類

• 我們把過濾條件為等式的稱為等值JOIN，而不是等值連接的情況則稱為非等值JOIN。這兩個(gè)例子中，前者是非等值JOIN，后者是等值JOIN。

等值JOIN

• 條件可能由多個(gè)有AND關(guān)系的等式構(gòu)成，語法形式A JOIN B ON A.ai=B.bi AND …，其中ai和bi分別是A和B的字段。
• 有經(jīng)驗(yàn)的程序員都知道，現(xiàn)實(shí)中絕大多數(shù)JOIN都是等值JOIN，非等值JOIN要少見得多，而且大多數(shù)情況都可以轉(zhuǎn)換成等值JOIN來處理，所以我們在這里重點(diǎn)討論等值JOIN，并且后續(xù)討論中也主要使用表和記錄而不是集合和成員來舉例。

空值處理規(guī)則下分類

• 根據(jù)對空值的處理規(guī)則，嚴(yán)格的等值JOIN又稱為INNER JOIN，還可以再衍生出LEFT JOIN和FULL JOIN，共有三種情況（RIGHT JOIN可以理解為LEFT JOIN的反向關(guān)聯(lián)，不再單獨(dú)作為一種類型）。
• 談?wù)揓OIN時(shí)一般還會(huì)根據(jù)兩個(gè)表中關(guān)聯(lián)記錄（也就是滿足過濾條件的二元組）的數(shù)量分為一對一、一對多、多對一以及多對多這幾種情況，這些常規(guī)術(shù)語在SQL和數(shù)據(jù)庫資料中都有介紹，這里就不再贅述了。

JOIN的實(shí)現(xiàn)

笨辦法

• 最容易想到的簡單辦法就是按照定義做硬遍歷，不區(qū)分等值JOIN和非等值JOIN。設(shè)表A有n條記錄，B有m條記錄，要計(jì)算A JOIN B ON A.a=B.b時(shí)，硬遍歷的復(fù)雜度會(huì)是nm，即要進(jìn)行nm次過濾條件的計(jì)算。
• 顯然這種算法會(huì)比較慢。不過，支持多數(shù)據(jù)源的報(bào)表工具中有時(shí)就是用這種慢辦法實(shí)現(xiàn)關(guān)聯(lián)的，因?yàn)樵趫?bào)表中數(shù)據(jù)集的關(guān)聯(lián)關(guān)系（也就是JOIN中的過濾條件）會(huì)拆散定義在單元格的運(yùn)算式中，已經(jīng)看不出是多個(gè)數(shù)據(jù)集之間的JOIN運(yùn)算，也就只能用遍歷方法去計(jì)算這些關(guān)聯(lián)表達(dá)式了。

數(shù)據(jù)庫對于JOIN優(yōu)化

• 對于等值JOIN，數(shù)據(jù)庫一般會(huì)采用HASH JOIN算法。即將關(guān)聯(lián)表的記錄按其關(guān)聯(lián)鍵（過濾條件中對應(yīng)相等的字段，即A.a和B.b)的HASH值分成若干組，將相同HASH值的記錄分到一組。如HASH值范圍是1…k，則將A和B表都分成k個(gè)子集A1,…,Ak和B1,…,Bk。Ai中記錄的關(guān)聯(lián)鍵a的HASH值是i，Bi中記錄的關(guān)聯(lián)鍵b的HASH值也是i，然后，只要分別在Ai和Bi之間做遍歷連接就可以了。
• 因?yàn)镠ASH不同時(shí)字段值也必然不同，i!=j時(shí)，Ai中記錄不可能和Bj中記錄發(fā)生關(guān)聯(lián)。如果Ai的記錄數(shù)是ni，Bi的記錄數(shù)是mi，則過濾條件的計(jì)算次數(shù)為SUM(ni*mi)，最平均的情況時(shí)，ni=n/k，mi=m/k，則總的復(fù)雜度只有原始硬遍歷手段的1/k，能有效地提高運(yùn)算性能！
• 所以，多數(shù)據(jù)源關(guān)聯(lián)報(bào)表要提速的話，也需要在數(shù)據(jù)準(zhǔn)備階段做好關(guān)聯(lián)，否則數(shù)據(jù)量稍大時(shí)性能就會(huì)急劇下降。
• 不過，HASH函數(shù)并不總能保證平均分拆，在運(yùn)氣不好的時(shí)候可能會(huì)發(fā)生某一組特別大的情況，那樣性能提升效果就會(huì)差很多。而且還不能使用太復(fù)雜的HASH函數(shù)，否則計(jì)算HASH的時(shí)間又變多了。
• 當(dāng)數(shù)據(jù)量大到超過內(nèi)存時(shí)，數(shù)據(jù)庫會(huì)使用HASH分堆的方法，算是HASH JOIN算法的推廣。遍歷A表和B表，將記錄按關(guān)聯(lián)鍵的HASH值拆分成若干小子集緩存到外存中，稱為分堆。然后再在對應(yīng)的堆之間做內(nèi)存JOIN運(yùn)算。同樣的道理，HASH值不同時(shí)鍵值也必然不同，關(guān)聯(lián)一定發(fā)生在對應(yīng)的堆之間。這樣就把大數(shù)據(jù)的JOIN轉(zhuǎn)換成若干小數(shù)據(jù)的JOIN了。
• 但是類似地，HASH函數(shù)存在運(yùn)氣問題，有可能會(huì)發(fā)生某個(gè)分堆還特別大而無法裝入內(nèi)存，這時(shí)候就可能要進(jìn)行二次HASH分堆，即換一個(gè)HASH函數(shù)對這組太大的分堆再做一次HASH分堆算法。所以，外存JOIN運(yùn)算有可能出現(xiàn)多次緩存的現(xiàn)象，其運(yùn)算性能有一定的不可控性。

分布式系統(tǒng)下JOIN

• 分布式系統(tǒng)下做JOIN也是類似的，根據(jù)關(guān)聯(lián)鍵的HASH值將記錄分發(fā)到各個(gè)節(jié)點(diǎn)機(jī)上，稱為Shuffle動(dòng)作，然后再分別做單機(jī)的JOIN。
• 當(dāng)節(jié)點(diǎn)比較多的時(shí)候，造成的網(wǎng)絡(luò)傳輸量帶來的延遲會(huì)抵消多機(jī)分?jǐn)側(cè)蝿?wù)得到的好處，所以分布式數(shù)據(jù)庫系統(tǒng)通常有個(gè)節(jié)點(diǎn)數(shù)的極限，達(dá)到極限后，更多的節(jié)點(diǎn)并不能獲得更好的性能。

等值JOIN的剖析

三種等值JOIN：

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

• 表A的某個(gè)字段和表B的主鍵字段關(guān)聯(lián)（所謂字段關(guān)聯(lián)，就是前一節(jié)說過的在等值JOIN的過濾條件中要對應(yīng)相等的字段）。A表稱為事實(shí)表，B表稱為維表。A表中與B表主鍵關(guān)聯(lián)的字段稱為A指向B的外鍵，B也稱為A的外鍵表。
• 這里說的主鍵是指邏輯上的主鍵，也就是在表中取值唯一、可以用于唯一某條記錄的字段（組），不一定在數(shù)據(jù)庫表上建立過主鍵。
• 外鍵表是多對一的關(guān)系，且只有JOIN和LEFT JOIN，而FULL JOIN非常罕見。
• 典型案例：商品交易表和商品信息表。
• 顯然，外鍵關(guān)聯(lián)是不對稱的。事實(shí)表和維表的位置不能互換。

同維表

• 表A的主鍵與表B的主鍵關(guān)聯(lián)，A和B互稱為同維表。同維表是一對一的關(guān)系，JOIN、LEFT JOIN和FULL JOIN的情況都會(huì)有，不過在大多數(shù)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方案中，F(xiàn)ULL JOIN也相對少見。
• 典型案例：員工表和經(jīng)理表。
• 同維表之間是對稱的，兩個(gè)表的地位相同。同維表還構(gòu)成是等價(jià)關(guān)系，A和B是同維表，B和C是同維表，則A和C也是同維表。

主子表

• 表A的主鍵與表B的部分主鍵關(guān)聯(lián)，A稱為主表，B稱為子表。主子表是一對多的關(guān)系，只有JOIN和LEFT JOIN，不會(huì)有FULL JOIN。
• 典型案例：訂單和訂單明細(xì)。
• 主子表也是不對稱的，有明確的方向。
• 在SQL的概念體系中并不區(qū)分外鍵表和主子表，多對一和一對多從SQL的觀點(diǎn)看來只是關(guān)聯(lián)方向不同，本質(zhì)上是一回事。確實(shí)，訂單也可以理解成訂單明細(xì)的外鍵表。但是，我們在這里要把它們區(qū)分開，將來在簡化語法和性能優(yōu)化時(shí)將使用不同的手段。
• 我們說，這三種JOIN已經(jīng)涵蓋了絕大多數(shù)等值JOIN的情況，甚至可以說幾乎全部有業(yè)務(wù)意義的等值JOIN都屬于這三類，把等值JOIN限定在這三種情況之中，幾乎不會(huì)減少其適應(yīng)范圍。
• 仔細(xì)考察這三種JOIN，我們發(fā)現(xiàn)所有關(guān)聯(lián)都涉及主鍵，沒有多對多的情況，是不是可以不考慮這種情況？
• 是的！多對多的等值JOIN幾乎沒有業(yè)務(wù)意義。
• 如果兩個(gè)表JOIN時(shí)的關(guān)聯(lián)字段沒有涉及到任何主鍵，那就會(huì)發(fā)生多對多的情況，而這種情況幾乎一定還會(huì)有一個(gè)規(guī)模更大的表把這兩個(gè)表作為維表關(guān)聯(lián)起來。比如學(xué)生表和科目表在JOIN時(shí)，會(huì)有個(gè)成績表把學(xué)生表和科目表作為維表，單純只有學(xué)生表和科目表的JOIN沒有業(yè)務(wù)意義。
• 當(dāng)寫SQL語句時(shí)發(fā)現(xiàn)多對多的情況，那大概率是這個(gè)語句寫錯(cuò)了！或者數(shù)據(jù)有問題！這條法則用于排除JOIN錯(cuò)誤很有效。
• 不過，我們一直在說“幾乎”，并沒有用完全肯定的說法，也就是說，多對多在非常罕見的情況下也會(huì)業(yè)務(wù)意義?？膳e一例，用SQL實(shí)現(xiàn)矩陣乘法時(shí)會(huì)發(fā)生多對多的等值JOIN，具體寫法讀者可以自行補(bǔ)充。
• 笛卡爾積再過濾這種JOIN定義，確實(shí)非常簡單，而簡單的內(nèi)涵將得到更大的外延，可以把多對多等值JOIN甚至非等值JOIN等都包括進(jìn)來。但是，過于簡單的內(nèi)涵無法充分體現(xiàn)出最常見等值JOIN的運(yùn)算特征。這會(huì)導(dǎo)致編寫代碼和實(shí)現(xiàn)運(yùn)算時(shí)就不能利用這些特征，在運(yùn)算較為復(fù)雜時(shí)（涉及關(guān)聯(lián)表較多以及有嵌套的情況），無論是書寫還是優(yōu)化都非常困難。而充分利用這些特征后，我們就能創(chuàng)造出更簡單的書寫形式并獲得更高效的運(yùn)算性能，后面的內(nèi)容中將會(huì)逐步加以說明。
• 與其為了把罕見情況也被包括進(jìn)來而把運(yùn)算定義為更通用的形式，還不如把這些情況定義成另一種運(yùn)算更為合理。

JOIN的語法簡化

如何利用關(guān)聯(lián)都涉及主鍵這個(gè)特征來簡化JOIN的代碼書寫？

外鍵屬性化

例子，設(shè)有如下兩個(gè)表：

employee 員工表
    id 員工編號(hào)
    name 姓名
    nationality 國籍
    department 所屬部門

department 部門表
    id 部門編號(hào)
    name 部門名稱
    manager 部門經(jīng)理

• employee表和department表的主鍵都是其中的id字段，employee表的department字段是指向department表的外鍵，department表的manager字段又是指向employee表的外鍵（因?yàn)榻?jīng)理也是個(gè)員工）。這是很常規(guī)的表結(jié)構(gòu)設(shè)計(jì)。
• 現(xiàn)在我們想問一下：哪些美國籍員工有一個(gè)中國籍經(jīng)理？用SQL寫出來是個(gè)三表JOIN的語句：

SELECT A.* 
FROM employee A
JOIN department B ON A.department=B.id
JOIN employee C ON B.manager=C.id
WHERE A.nationality='USA' AND C.nationality='CHN'

• 首先要FROM employee用于獲取員工信息，然后這個(gè)employee表要和department做JOIN獲取員工的部門信息，接著這個(gè)department表還要再和employee表JOIN要獲取經(jīng)理的信息，這樣employee表需要兩次參與JOIN，在SQL語句中要為它起個(gè)別名加以區(qū)分，整個(gè)句子就顯得比較復(fù)雜難懂。
• 如果我們把外鍵字段直接理解成它關(guān)聯(lián)的維表記錄，就可以換一種寫法：

SELECT * FROM employee
WHERE nationality='USA' AND department.manager.nationality='CHN'

當(dāng)然，這不是標(biāo)準(zhǔn)的SQL語句了。

• 第二個(gè)句子中粗體部分表示當(dāng)前員工的“所屬部門的經(jīng)理的國籍”。我們把外鍵字段理解成維表的記錄后，維表的字段被理解為外鍵的屬性，department.manager即是“所屬部門的經(jīng)理”，而這個(gè)字段在department中仍然是個(gè)外鍵，那么它對應(yīng)的維表記錄字段可以繼續(xù)理解為它的屬性，也就會(huì)有department.manager.nationality，即“所屬部門的經(jīng)理的國籍”。
• 外鍵屬性化:這種對象式的理解方式即為外鍵屬性化，顯然比笛卡爾積過濾的理解方式要自然直觀得多。外鍵表JOIN時(shí)并不會(huì)涉及到兩個(gè)表的乘法，外鍵字段只是用于找到維鍵表中對應(yīng)的那條記錄，完全不會(huì)涉及到笛卡爾積這種有乘法特性的運(yùn)算。
• 我們前面約定，外鍵關(guān)聯(lián)時(shí)時(shí)維表中關(guān)聯(lián)鍵必須是主鍵，這樣，事實(shí)表中每一條記錄的外鍵字段關(guān)聯(lián)的維表記錄就是唯一的，也就是說employee表中每一條記錄的department字段唯一關(guān)聯(lián)一條department表中的記錄，而department表中每一條記錄的manager字段也唯一關(guān)聯(lián)一條employee表中的記錄。這就保證了對于employee表中的每一條記錄，department.manager.nationality都有唯一的取值，可以被明確定義。
• 但是，SQL對JOIN的定義中并沒有主鍵的約定，如果基于SQL的規(guī)則，就不能認(rèn)定與事實(shí)表中外鍵關(guān)聯(lián)的維表記錄有唯一性，有可能發(fā)生與多條記錄關(guān)聯(lián)，對于employee表的記錄來講，department.manager.nationality沒有明確定義，就不能使用了。
• 事實(shí)上，這種對象式寫法在高級(jí)語言（如C，Java）中很常見，在這類語言中，數(shù)據(jù)就是按對象方式存儲(chǔ)的。employee表中的department字段取值根本就是一個(gè)對象，而不是編號(hào)。其實(shí)許多表的主鍵取值本身并沒有業(yè)務(wù)意義，僅僅是為了區(qū)分記錄，而外鍵字段也僅僅是為了找到維表中的相應(yīng)記錄，如果外鍵字段直接是對象，就不需要再通過編號(hào)來標(biāo)識(shí)了。不過，SQL不能支持這種存儲(chǔ)機(jī)制，還要借助編號(hào)。
• 我們說過外鍵關(guān)聯(lián)是不對稱的，即事實(shí)表和維表是不對等的，只能基于事實(shí)表去找維表字段，而不會(huì)有倒過來的情況。

同維表等同化

同維表的情況相對簡單，還是從例子開始，設(shè)有兩個(gè)表：

employee 員工表
    id 員工編號(hào)
    name 姓名
    salary 工資
    ...

manager 經(jīng)理表
    id 員工編號(hào)
    allowance 崗位津貼
    ....

• 兩個(gè)表的主鍵都是id，經(jīng)理也是員工，兩表共用同樣的員工編號(hào)，經(jīng)理會(huì)比普通員工多一些屬性，另用一個(gè)經(jīng)理表來保存。
• 現(xiàn)在我們要統(tǒng)計(jì)所有員工（包括經(jīng)理）的總收入（加上津貼）。用SQL寫出來還是會(huì)用到JOIN：

SELECT employee.id, employee.name, employy.salary+manager.allowance
FROM employee
LEFT JOIN manager ON employee.id=manager.id

而對于兩個(gè)一對一的表，我們其實(shí)可以簡單地把它們看成一個(gè)表：

SELECT id,name,salary+allowance
FROM employee

• 類似地，根據(jù)我們的約定，同維表JOIN時(shí)兩個(gè)表都是按主鍵關(guān)聯(lián)的，相應(yīng)記錄是唯一對應(yīng)的，salary+allowance對employee表中每條記錄都是唯一可計(jì)算的，不會(huì)出現(xiàn)歧義。這種簡化方式稱為同維表等同化。
• 同維表之間的關(guān)系是對等的，從任何一個(gè)表都可以引用到其它同維表的字段。

子表集合化

訂單&訂單明細(xì)是典型的主子表：

Orders 訂單表
    id 訂單編號(hào)
    customer 客戶
    date 日期
    ...
OrderDetail 訂單明細(xì)
    id 訂單編號(hào)
    no 序號(hào)
    product 訂購產(chǎn)品
    price 價(jià)格
    ...

Orders表的主鍵是id，OrderDetail表中的主鍵是(id,no)，前者的主鍵是后者的一部分。

現(xiàn)在我們想計(jì)算每張訂單的總金額。用SQL寫出來會(huì)是這樣：

SELECT Orders.id, Orders.customer, SUM(OrderDetail.price)
FROM Orders
JOIN OrderDetail ON Orders.id=OrderDetail.id
GROUP BY Orders.id, Orders.customer

• 要完成這個(gè)運(yùn)算，不僅要用到JOIN，還需要做一次GROUP BY，否則選出來的記錄數(shù)太多。
• 如果我們把子表中與主表相關(guān)的記錄看成主表的一個(gè)字段，那么這個(gè)問題也可以不再使用JOIN以及GROUP BY：

SELECT id, customer, OrderDetail.SUM(price)
FROM Orders

• 與普通字段不同，OrderDetail被看成Orders表的字段時(shí)，其取值將是一個(gè)集合，因?yàn)閮蓚€(gè)表是一對多的關(guān)系。所以要在這里使用聚合運(yùn)算把集合值計(jì)算成單值。這種簡化方式稱為子表集合化。
• 這樣看待主子表關(guān)聯(lián)，不僅理解書寫更為簡單，而且不容易出錯(cuò)。
• 假如Orders表還有一個(gè)子表用于記錄回款情況：

OrderPayment 訂單回款表
    id 訂單編號(hào)
    date 回款日期
    amount 回款金額
    ....

• 我們現(xiàn)在想知道那些訂單還在欠錢，也就是累計(jì)回款金額小于訂單總金額的訂單。
• 簡單地把這三個(gè)表JOIN起來是不對的，OrderDetail和OrderPayment會(huì)發(fā)生多對多的關(guān)系，這就錯(cuò)了（回憶前面提過的多對多大概率錯(cuò)誤的說法）。這兩個(gè)子表要分別先做GROUP，再一起與Orders表JOIN起來才能得到正確結(jié)果，會(huì)寫成子查詢的形式：

SELECT Orders.id, Orders.customer,A.x,B.y
FROM Orders
LEFT JOIN ( SELECT id,SUM(price) x FROM OrderDetail GROUP BY id ) A 
    ON Orders.id=A.id
LEFT JOIN ( SELECT id,SUM(amount) y FROM OrderPayment GROUP BY id ) B
    ON Orders.id=B.id
WHERE A.x>B.y 

如果我們繼續(xù)把子表看成主表的集合字段，那就很簡單了：

SELECT id,customer,OrderDetail.SUM(price) x,OrderPayment.SUM(amount) y
FROM Orders WHERE x>y

• 這種寫法也不容易發(fā)生多對多的錯(cuò)誤。
• 主子表關(guān)系是不對等的，不過兩個(gè)方向的引用都有意義，上面談了從主表引用子表的情況，從子表引用主表則和外鍵表類似。
• 我們改變對JOIN運(yùn)算的看法，摒棄笛卡爾積的思路，把多表關(guān)聯(lián)運(yùn)算看成是稍復(fù)雜些的單表運(yùn)算。這樣，相當(dāng)于把最常見的等值JOIN運(yùn)算的關(guān)聯(lián)消除了，甚至在語法中取消了JOIN關(guān)鍵字，書寫和理解都要簡單很多。

維度對齊語法

我們再回顧前面的雙子表例子的SQL：

SELECT Orders.id, Orders.customer, A.x, B.y
FROM Orders
LEFT JOIN (SELECT id,SUM(price) x FROM OrderDetail GROUP BY id ) A 
    ON Orders.id=A.id
LEFT JOIN (SELECT id,SUM(amount) y FROM OrderPayment GROUP BY id ) B
    ON Orders.id=B.id
WHERE A.x > B.y

• 那么問題來了，這顯然是個(gè)有業(yè)務(wù)意義的JOIN，它算是前面所說的哪一類呢？
• 這個(gè)JOIN涉及了表Orders和子查詢A與B，仔細(xì)觀察會(huì)發(fā)現(xiàn)，子查詢帶有GROUP BY id的子句，顯然，其結(jié)果集將以id為主鍵。這樣，JOIN涉及的三個(gè)表（子查詢也算作是個(gè)臨時(shí)表）的主鍵是相同的，它們是一對一的同維表，仍然在前述的范圍內(nèi)。
• 但是，這個(gè)同維表JOIN卻不能用前面說的寫法簡化，子查詢A,B都不能省略不寫。
• 可以簡化書寫的原因：我們假定事先知道數(shù)據(jù)結(jié)構(gòu)中這些表之間的關(guān)聯(lián)關(guān)系。用技術(shù)術(shù)語的說法，就是知道數(shù)據(jù)庫的元數(shù)據(jù)（metadata）。而對于臨時(shí)產(chǎn)生的子查詢，顯然不可能事先定義在元數(shù)據(jù)中了，這時(shí)候就必須明確指定要JOIN的表（子查詢）。
• 不過，雖然JOIN的表（子查詢）不能省略，但關(guān)聯(lián)字段總是主鍵。子查詢的主鍵總是由GROUP BY產(chǎn)生，而GROUP BY的字段一定要被選出用于做外層JOIN；并且這幾個(gè)子查詢涉及的子表是互相獨(dú)立的，它們之間不會(huì)再有關(guān)聯(lián)計(jì)算了，我們就可以把GROUP動(dòng)作以及聚合式直接放到主句中，從而消除一層子查詢：

SELECT Orders.id, Orders.customer, OrderDetail.SUM(price) x, OrderParyment.SUM(amount) y
FROM Orders 
LEFT JOIN OrderDetail GROUP BY id 
LEFT JOIN OrderPayment GROUP BY id
WHERE A.x > B.y

• 這里的JOIN和SQL定義的JOIN運(yùn)算已經(jīng)差別很大，完全沒有笛卡爾積的意思了。而且，也不同于SQL的JOIN運(yùn)算將定義在任何兩個(gè)表之間，這里的JOIN，OrderDetail和OrderPayment以及Orders都是向一個(gè)共同的主鍵id對齊，即所有表都向某一套基準(zhǔn)維度對齊。而由于各表的維度（主鍵）不同，對齊時(shí)可能會(huì)有GROUP BY，在引用該表字段時(shí)就會(huì)相應(yīng)地出現(xiàn)聚合運(yùn)算。OrderDetail和OrderPayment甚至Orders之間都不直接發(fā)生關(guān)聯(lián)，在書寫運(yùn)算時(shí)當(dāng)然就不用關(guān)心它們之間的關(guān)系，甚至不必關(guān)心另一個(gè)表是否存在。而SQL那種笛卡爾積式的JOIN則總要找一個(gè)甚至多個(gè)表來定義關(guān)聯(lián)，一旦減少或修改表時(shí)就要同時(shí)考慮關(guān)聯(lián)表，增大理解難度。
• 維度對齊：這種JOIN稱即為維度對齊，它并不超出我們前面說過的三種JOIN范圍，但確實(shí)在語法描述上會(huì)有不同，這里的JOIN不象SQL中是個(gè)動(dòng)詞，卻更象個(gè)連詞。而且，和前面三種基本JOIN中不會(huì)或很少發(fā)生FULL JOIN的情況不同，維度對齊的場景下FULL JOIN并不是很罕見的情況。
• 雖然我們從主子表的例子抽象出維度對齊，但這種JOIN并不要求JOIN的表是主子表（事實(shí)上從前面的語法可知，主子表運(yùn)算還不用寫這么麻煩），任何多個(gè)表都可以這么關(guān)聯(lián)，而且關(guān)聯(lián)字段也完全不必要是主鍵或主鍵的部分。
• 設(shè)有合同表，回款表和發(fā)票表：

Contract 合同表
    id 合同編號(hào)
    date 簽訂日期
    customer 客戶
    price 合同金額
    ...

Payment 回款表
    seq 回款序號(hào)
    date 回款日期
    source 回款來源
    amount 金額
    ...

Invoice 發(fā)票表
    code 發(fā)票編號(hào)
    date 開票日期
    customer 客戶
    amount 開票金額
    ...

現(xiàn)在想統(tǒng)計(jì)每一天的合同額、回款額以及發(fā)票額，就可以寫成：

SELECT Contract.SUM(price), Payment.SUM(amount), Invoice.SUM(amount) ON date
FROM Contract GROUP BY date
FULL JOIN Payment GROUP BY date
FULL JOIN Invoice GROUP BY date

• 這里需要把date在SELECT后單獨(dú)列出來表示結(jié)果集按日期對齊。
• 這種寫法，不必關(guān)心這三個(gè)表之間的關(guān)聯(lián)關(guān)系，各自寫各自有關(guān)的部分就行，似乎這幾個(gè)表就沒有關(guān)聯(lián)關(guān)系，把它們連到一起的就是那個(gè)要共同對齊的維度（這里是date）。
• 這幾種JOIN情況還可能混合出現(xiàn)。
• 繼續(xù)舉例，延用上面的合同表，再有客戶表和銷售員表

Customer 客戶表
    id 客戶編號(hào)
    name 客戶名稱
    area 所在地區(qū)
    ...

Sales 銷售員表
    id 員工編號(hào)
    name 姓名
    area 負(fù)責(zé)地區(qū)
    ...

• 其中Contract表中customer字段是指向Customer表的外鍵。
• 現(xiàn)在我們想統(tǒng)計(jì)每個(gè)地區(qū)的銷售員數(shù)量及合同額：

SELECT Sales.COUNT(1), Contract.SUM(price) ON area
FROM Sales GROUP BY area
FULL JOIN Contract GROUP BY customer.area

• 維度對齊可以和外鍵屬性化的寫法配合合作。
• 這些例子中，最終的JOIN都是同維表。事實(shí)上，維度對齊還有主子表對齊的情況，不過相對罕見，我們這里就不深入討論了。
• 另外，目前這些簡化語法仍然是示意性，需要在嚴(yán)格定義維度概念之后才能相應(yīng)地形式化，成為可以解釋執(zhí)行的句子。
• 我們把這種簡化的語法稱為DQL（Dimensional Query Languange），DQL是以維度為核心的查詢語言。我們已經(jīng)將DQL在工程上做了實(shí)現(xiàn)，并作為潤乾報(bào)表的DQL服務(wù)器發(fā)布出來，它能將DQL語句翻譯成SQL語句執(zhí)行，也就是可以在任何關(guān)系數(shù)據(jù)庫上運(yùn)行。
• 對DQL理論和應(yīng)用感興趣的讀者可以關(guān)注乾學(xué)院上發(fā)布的論文和相關(guān)文章。

解決關(guān)聯(lián)查詢

多表JOIN問題

• 我們知道，SQL允許用WHERE來寫JOIN運(yùn)算的過濾條件（回顧原始的笛卡爾積式的定義），很多程序員也習(xí)慣于這么寫。
• 當(dāng)JOIN表只有兩三個(gè)的時(shí)候，那問題還不大，但如果JOIN表有七八個(gè)甚至十幾個(gè)的時(shí)候，漏寫一個(gè)JOIN條件是很有可能的。而漏寫了JOIN條件意味著將發(fā)生多對多的完全叉乘，而這個(gè)SQL卻可以正常執(zhí)行，會(huì)有以下兩點(diǎn)危害：
  • 一方面計(jì)算結(jié)果會(huì)出錯(cuò):回憶一下以前說過的，發(fā)生多對多JOIN時(shí)，大概率是語句寫錯(cuò)了
  • 另一方面，如果漏寫條件的表很大，笛卡爾積的規(guī)模將是平方級(jí)的，這極有可能把數(shù)據(jù)庫直接“跑死”！

簡化JOIN運(yùn)算好處：

• 一個(gè)直接的效果顯然是讓語句書寫和理解更容易
• 外鍵屬性化、同維表等同化和子表集合化方案直接消除了顯式的關(guān)聯(lián)運(yùn)算，也更符合自然思維
• 維度對齊則可讓程序員不再關(guān)心表間關(guān)系，降低語句的復(fù)雜度
• 簡化JOIN語法的好處不僅在于此，還能夠降低出錯(cuò)率，采用簡化后的JOIN語法，就不可能發(fā)生漏寫JOIN條件的情況了。因?yàn)閷OIN的理解不再是以笛卡爾積為基礎(chǔ)，而且設(shè)計(jì)這些語法時(shí)已經(jīng)假定了多對多關(guān)聯(lián)沒有業(yè)務(wù)意義，這個(gè)規(guī)則下寫不出完全叉乘的運(yùn)算。
• 對于多個(gè)子表分組后與主表對齊的運(yùn)算，在SQL中要寫成多個(gè)子查詢的形式。但如果只有一個(gè)子表時(shí)，可以先JOIN再GROUP，這時(shí)不需要子查詢。有些程序員沒有仔細(xì)分析，會(huì)把這種寫法推廣到多個(gè)子表的情況，也先JOIN再GROUP，可以避免使用子查詢，但計(jì)算結(jié)果是錯(cuò)誤的。
• 使用維度對齊的寫法就不容易發(fā)生這種錯(cuò)誤了，無論多少個(gè)子表，都不需要子查詢，一個(gè)子表和多個(gè)子表的寫法完全相同。

關(guān)聯(lián)查詢

• 重新看待JOIN運(yùn)算，最關(guān)鍵的作用在于實(shí)現(xiàn)關(guān)聯(lián)查詢。
• 當(dāng)前BI產(chǎn)品是個(gè)熱門，各家產(chǎn)品都宣稱能夠讓業(yè)務(wù)人員拖拖拽拽就完成想要的查詢報(bào)表。但實(shí)際應(yīng)用效果會(huì)遠(yuǎn)不如人意，業(yè)務(wù)人員仍然要經(jīng)常求助于IT部門。造成這個(gè)現(xiàn)象的主要原因在于大多數(shù)業(yè)務(wù)查詢都是有過程的計(jì)算，本來也不可能拖拽完成。但是，也有一部分業(yè)務(wù)查詢并不涉及多步過程，而業(yè)務(wù)人員仍然難以完成。
• 這就是關(guān)聯(lián)查詢，也是大多數(shù)BI產(chǎn)品的軟肋。在之前的文章中已經(jīng)講過為什么關(guān)聯(lián)查詢很難做，其根本原因就在于SQL對JOIN的定義過于簡單。
• 結(jié)果，BI產(chǎn)品的工作模式就變成先由技術(shù)人員構(gòu)建模型，再由業(yè)務(wù)人員基于模型進(jìn)行查詢。而所謂建模，就是生成一個(gè)邏輯上或物理上的寬表。也就是說，建模要針對不同的關(guān)聯(lián)需求分別實(shí)現(xiàn)，我們稱之為按需建模，這時(shí)候的BI也就失去敏捷性了。
• 但是，如果我們改變了對JOIN運(yùn)算的看法，關(guān)聯(lián)查詢可以從根本上得到解決?；貞浨懊嬷v過的三種JOIN及其簡化手段，我們事實(shí)上把這幾種情況的多表關(guān)聯(lián)都轉(zhuǎn)化成了單表查詢，而業(yè)務(wù)用戶對于單表查詢并沒有理解障礙。無非就是表的屬性（字段）稍復(fù)雜了一些：可能有子屬性（外鍵字段指向的維表并引用其字段），子屬性可能還有子屬性（多層的維表），有些字段取值是集合而非單值（子表看作為主表的字段）。發(fā)生互相關(guān)聯(lián)甚至自我關(guān)聯(lián)也不會(huì)影響理解（前面的中國經(jīng)理的美國員工例子就是互關(guān)聯(lián)），同表有相同維度當(dāng)然更不礙事（各自有各自的子屬性）。
• 在這種關(guān)聯(lián)機(jī)制下，技術(shù)人員只要一次性把數(shù)據(jù)結(jié)構(gòu)（元數(shù)據(jù)）定義好，在合適的界面下（把表的字段列成有層次的樹狀而不是常規(guī)的線狀），就可以由業(yè)務(wù)人員自己實(shí)現(xiàn)JOIN運(yùn)算，不再需要技術(shù)人員的參與。數(shù)據(jù)建模只發(fā)生于數(shù)據(jù)結(jié)構(gòu)改變的時(shí)刻，而不需要為新的關(guān)聯(lián)需求建模，這也就是非按需建模，在這種機(jī)制支持下的BI才能擁有足夠的敏捷性。

外鍵預(yù)關(guān)聯(lián)

• 我們再來研究如何利用JOIN的特征實(shí)現(xiàn)性能優(yōu)化，這些內(nèi)容的細(xì)節(jié)較多，我們挑一些易于理解的情況來舉例，更完善的連接提速算法可以參考乾學(xué)院上的《性能優(yōu)化》圖書和SPL學(xué)習(xí)資料中的性能優(yōu)化專題文章。

全內(nèi)存下外鍵關(guān)聯(lián)情況

設(shè)有兩個(gè)表：

customer 客戶信息表
    key 編號(hào)
    name 名稱
    city 城市
    ...

orders 訂單表
    seq 序號(hào)
    date 日期
    custkey 客戶編號(hào)
    amount 金額
    ...

• 其中orders表中的custkey是指向customer表中key字段的外鍵，key是customer表的主鍵。
• 現(xiàn)在我們各個(gè)城市的訂單總額（為簡化討論，就不再設(shè)定條件了），用SQL寫出來：

SELECT customer.city, SUM(orders.amount)
FROM orders
JOIN customer ON orders.custkey=customer.key
GROUP BY customer.city

• 數(shù)據(jù)庫一般會(huì)使用HASH JOIN算法，需要分別兩個(gè)表中關(guān)聯(lián)鍵的HASH值并比對。
• 我們用前述的簡化的JOIN語法（DQL）寫出這個(gè)運(yùn)算：

SELECT custkey.city, SUM(amount)
FROM orders
GROUP BY custkey.city

• 這個(gè)寫法其實(shí)也就預(yù)示了它還可以有更好的優(yōu)化方案，下面來看看怎樣實(shí)現(xiàn)。
• 如果所有數(shù)據(jù)都能夠裝入內(nèi)存，我們可以實(shí)現(xiàn)外鍵地址化。
• 將事實(shí)表orders中的外鍵字段custkey，轉(zhuǎn)換成維表customer中關(guān)聯(lián)記錄的地址，即orders表的custkey的取值已經(jīng)是某個(gè)customer表中的記錄，那么就可以直接引用記錄的字段進(jìn)行計(jì)算了。
• 用SQL無法描述這個(gè)運(yùn)算的細(xì)節(jié)過程，我們使用SPL來描述、并用文件作為數(shù)據(jù)源來說明計(jì)算過程：

• A1讀出客戶表，A2為客戶表設(shè)置主鍵并建立索引。
• A3讀出訂單表，A4的動(dòng)作是將A3的外鍵字段custkey轉(zhuǎn)換成對應(yīng)的A1的記錄，執(zhí)行完后，訂單表字段custkey將變成客戶表的某條記錄。A2建了索引能讓switch更快，因?yàn)橥ǔＪ聦?shí)表遠(yuǎn)大于維表，這個(gè)索引能被復(fù)用很多次。
• A5就可以執(zhí)行分組匯總了，遍歷訂單表時(shí)，由于custkey字段取值現(xiàn)在已經(jīng)是一條記錄，那么可以直接用.操作符引用其字段了，custkey.city就可以正常執(zhí)行。
• 完成A4中的switch動(dòng)作之后，內(nèi)存中事實(shí)表A3的custkey字段存儲(chǔ)內(nèi)容已經(jīng)是維表A1的某條記錄的地址，這個(gè)動(dòng)作即稱為外鍵地址化。這時(shí)候引用維表字段時(shí)，可以直接取出，而不需要再用外鍵值在A1中查找，相當(dāng)于在常數(shù)時(shí)間內(nèi)就能取到維表的字段，避免了HASH值計(jì)算和比對。
• 不過，A2建主鍵索引一般也會(huì)用HASH辦法，對key計(jì)算HASH值，A4轉(zhuǎn)換地址時(shí)也是計(jì)算custkey的HASH值與A2的HASH索引表對比。如果只做一次關(guān)聯(lián)運(yùn)算，地址化的方案和傳統(tǒng)HASH分段方案的計(jì)算量基本上一樣，沒有根本優(yōu)勢。
• 但不同的是，如果數(shù)據(jù)能在內(nèi)存中放下，這個(gè)地址一旦轉(zhuǎn)換之后可以復(fù)用，也就是說A1到A4只要做一次，下次再做關(guān)于這兩個(gè)字段的關(guān)聯(lián)運(yùn)算時(shí)就不必再計(jì)算HASH值和比對了，性能就能大幅提高。
• 能夠這樣做，正是利用了前面說過的外鍵關(guān)聯(lián)在維表這一方具有的唯一性，一個(gè)外鍵字段值只會(huì)唯一對應(yīng)一條維表記錄，可以把每個(gè)custkey轉(zhuǎn)換成它唯一對應(yīng)的那條A1的記錄。而延用SQL中對JOIN的定義，就不能假定外鍵指向記錄的唯一性，無法使用這種表示法。而且SQL也沒有記錄地址這種數(shù)據(jù)類型，結(jié)果會(huì)導(dǎo)致每次關(guān)聯(lián)時(shí)都要計(jì)算HASH值并比對。
• 而且，如果事實(shí)表中有多個(gè)外鍵分別指向多個(gè)維表，傳統(tǒng)的HASH分段JOIN方案每次只能解析掉一個(gè)，有多個(gè)JOIN要執(zhí)行多遍動(dòng)作，每次關(guān)聯(lián)后都需要保持中間結(jié)果供下一輪使用，計(jì)算過程復(fù)雜得多，數(shù)據(jù)也會(huì)被遍歷多次。而外鍵地址化方案在面對多個(gè)外鍵時(shí)，只要對事實(shí)表遍歷一次，沒有中間結(jié)果，計(jì)算過程要清晰很多。
• 還有一點(diǎn)，內(nèi)存本來是很適合并行計(jì)算的，但HASH分段JOIN算法卻不容易并行。即使把數(shù)據(jù)分段并行計(jì)算HASH值，但要把相同HASH值的記錄歸聚到一起供下一輪比對，還會(huì)發(fā)生共享資源搶占的事情，這將犧牲很多并行計(jì)算的優(yōu)勢。而外鍵式JOIN模型下，關(guān)聯(lián)兩表的地位不對等，明確區(qū)分出維表和事實(shí)表后，只要簡單地將事實(shí)表分段就可以并行計(jì)算。
• 將HASH分段技術(shù)參照外鍵屬性方案進(jìn)行改造后，也能一定程度地改善多外鍵一次解析和并行能力，有些數(shù)據(jù)庫能在工程層面上實(shí)施這種優(yōu)化。不過，這種優(yōu)化在只有兩個(gè)表JOIN時(shí)問題不大，在有很多表及各種JOIN混在一起時(shí)，數(shù)據(jù)庫并不容易識(shí)別出應(yīng)當(dāng)把哪個(gè)表當(dāng)作事實(shí)表去并行遍歷、而把其它表當(dāng)作維表建立HASH索引，這時(shí)優(yōu)化并不總是有效的。所以我們經(jīng)常會(huì)發(fā)現(xiàn)當(dāng)JOIN的表變多時(shí)性能會(huì)急劇下降的現(xiàn)象（常常到四五個(gè)表時(shí)就會(huì)發(fā)生，結(jié)果集并無顯著增大）。而從JOIN模型上引入外鍵概念后，將這種JOIN專門處理時(shí)，就總能分清事實(shí)表和維表，更多的JOIN表只會(huì)導(dǎo)致性能的線性下降。
• 內(nèi)存數(shù)據(jù)庫是當(dāng)前比較火熱的技術(shù)，但上述分析表明，采用SQL模型的內(nèi)存數(shù)據(jù)庫在JOIN運(yùn)算上是很難快起來的！

進(jìn)一步的外鍵關(guān)聯(lián)

• 我們繼續(xù)討論外鍵JOIN，并延用上一節(jié)的例子。
• 當(dāng)數(shù)據(jù)量大到無法全部放進(jìn)內(nèi)存時(shí)，前述的地址化方法就不再有效了，因?yàn)樵谕獯鏌o法保存事先算好的地址。
• 一般來講，外鍵指向的維表容量較小，而不斷增長的事實(shí)表要大得多。如果內(nèi)存還能把維表放下的話，我們可以采用臨時(shí)指向的方法來處理外鍵。

• 前兩步與全內(nèi)存時(shí)相同，第4步的地址轉(zhuǎn)換是邊讀入邊進(jìn)行的，而且轉(zhuǎn)換結(jié)果無法保留復(fù)用，下次再做關(guān)聯(lián)時(shí)還要再計(jì)算HASH和比對，性能要比全內(nèi)存的方案差。計(jì)算量方面，比HASH JOIN算法少了一次維表的HASH值計(jì)算，這個(gè)維表如果經(jīng)常被復(fù)用時(shí)會(huì)占些便宜，但因?yàn)榫S表相對較小，總體優(yōu)勢并不算大。不過，這個(gè)算法同樣具有全內(nèi)存算法可以一次解析全部外鍵以及易于并行的特點(diǎn)，在實(shí)際場景下比HASH JOIN算法仍有較大的性能優(yōu)勢。

外鍵序號(hào)化

在這個(gè)算法基礎(chǔ)上，我們還可以做個(gè)變種：外鍵序號(hào)化。

如果我們能把維表的主鍵都轉(zhuǎn)換成從1開始的自然數(shù)，那么我們就可以用序號(hào)直接定位維表記錄，就不需要計(jì)算和比對HASH值，這樣就可以獲得類似全內(nèi)存下地址化的性能了。

• 維表主鍵是序號(hào)時(shí)就不需要再做原來建HASH索引的第2步了。
• 外鍵序號(hào)化本質(zhì)上相當(dāng)于在外存實(shí)現(xiàn)地址化。這種方案需要把事實(shí)表中的外鍵字段轉(zhuǎn)換成序號(hào)，這類似在全內(nèi)存運(yùn)算時(shí)地址化的過程，這個(gè)預(yù)計(jì)算也可以得到復(fù)用。需要注意的是，維表發(fā)生重大變化時(shí)，需要同步整理事實(shí)表的外鍵字段，否則可能對應(yīng)錯(cuò)位。不過一般維表變化頻度低，而且大多數(shù)動(dòng)作是追加和修改而非刪除，需要重整事實(shí)表的情況并不多。工程上的細(xì)節(jié)處理也可以再參考乾學(xué)院中的資料。
• SQL使用了無序集合的概念，即使我們事先把外鍵序號(hào)化了，數(shù)據(jù)庫也無法利用這個(gè)特點(diǎn)，不能在無序集合上使用序號(hào)快速定位的機(jī)制，只能使用索引查找，而且數(shù)據(jù)庫并不知道外鍵被序號(hào)化了，仍然會(huì)去計(jì)算HASH值和比對。
• 如果維表也大到內(nèi)存裝不下呢？
• 我們仔細(xì)分析上面的算法會(huì)發(fā)現(xiàn)，過程中對于事實(shí)表的訪問是連續(xù)的，但對于維表的訪問則是隨機(jī)的。我們以前討論硬盤的性能特征時(shí)談到過，外存不適合隨機(jī)訪問，所以外存中的維表不能再使用上述算法了。
• 外存中的維表可以事先按主鍵排序存儲(chǔ)，這樣我們就可以繼續(xù)利用維表關(guān)聯(lián)鍵是主鍵的特征來優(yōu)化性能。
• 如果事實(shí)表很小，可以在內(nèi)存裝放下，那么用外鍵去關(guān)聯(lián)維表記錄實(shí)際上會(huì)變成一個(gè)（批量）外存查找動(dòng)作。只要維表上針對主鍵建有索引，也可以很快地查找，這樣可以避免遍歷大維表，獲得更好的性能。這種算法也可以同時(shí)解析多個(gè)外鍵。SQL不區(qū)分維表和事實(shí)表，面對一大一小兩個(gè)表時(shí)，優(yōu)化過的HASH JOIN不會(huì)再做分堆緩存，通常會(huì)把小表讀入內(nèi)存而去遍歷大表，這樣仍然會(huì)有遍歷大維表的動(dòng)作，性能會(huì)比剛才說的外存查找算法差得多。
• 如果事實(shí)表也很大，則可以使用單邊分堆的算法。因?yàn)榫S表已經(jīng)按關(guān)聯(lián)鍵（即主鍵）有序，可以方便地邏輯上分成若干段并取出每一段的邊界值（每一段主鍵的最大最小值），然后將事實(shí)表按這些邊界值做分堆，每一堆分別和維表的每一段再做關(guān)聯(lián)就可以了。過程中只需要對事實(shí)表單邊做物理分堆緩存，維表不需要再做物理分堆緩存，而且不使用HASH函數(shù)，直接用分段，不可能會(huì)出現(xiàn)HASH函數(shù)運(yùn)氣不好導(dǎo)致二次分堆，性能是可控的。而數(shù)據(jù)庫的HASH分堆算法會(huì)將兩個(gè)大表都做物理分堆緩存，也就是雙邊分堆，還可能出現(xiàn)HASH函數(shù)運(yùn)氣不好導(dǎo)致二次分堆的現(xiàn)象，性能要比單邊分堆差得多，還不可控。

借助集群的力量解決大維表問題。

• 一臺(tái)機(jī)器的內(nèi)存裝不下，可以多搞幾臺(tái)機(jī)器來裝下，把維表按主鍵值分段存放在多臺(tái)機(jī)器上形成集群維表，然后就可以繼續(xù)使用上面針對內(nèi)存維表的算法了，也能獲得一次解析多個(gè)外鍵和易于并行的好處。同樣地，集群維表也可以使用序號(hào)化的技術(shù)。這種算法下，事實(shí)表不需要被傳輸，產(chǎn)生的網(wǎng)絡(luò)傳輸量并不大，也不需要節(jié)點(diǎn)本地緩存數(shù)據(jù)。而SQL體系下不能區(qū)分出維表，HASH拆分方法要將兩個(gè)表都做Shuffle動(dòng)作，網(wǎng)絡(luò)傳播量要大得多。
• 這些算法的細(xì)節(jié)仍有些復(fù)雜，這里限于篇幅無法詳細(xì)解釋，有興趣的讀者可以去乾學(xué)院的資料查閱。

有序歸并

同維表&主子表的JOIN優(yōu)化提速手段

• 我們前面討論過，HASH JOIN算法的計(jì)算復(fù)雜度（即關(guān)聯(lián)鍵的比較次數(shù)）是SUM(nimi)，比全遍歷的復(fù)雜度nm要小很多，不過要看HASH函數(shù)的運(yùn)氣。
• 如果這兩個(gè)表都對關(guān)聯(lián)鍵有序，那么我們就可以使用歸并算法來處理關(guān)聯(lián)，這時(shí)的復(fù)雜度是n+m；在n和m都較大的時(shí)候（一般都會(huì)遠(yuǎn)大于HASH函數(shù)的取值范圍），這個(gè)數(shù)也會(huì)遠(yuǎn)小于HASH JOIN算法的復(fù)雜度。歸并算法的細(xì)節(jié)有很多材料介紹，這里就不再贅述了。
• 但是，外鍵JOIN時(shí)不能使用這個(gè)辦法，因?yàn)槭聦?shí)表上可能有多個(gè)要參與關(guān)聯(lián)的外鍵字段，不可能讓同一個(gè)事實(shí)表同時(shí)針對多個(gè)字段都有序。
• 同維表和主子表卻可以！因?yàn)橥S表和主子表總是針對主鍵或主鍵的一部分關(guān)聯(lián)，我們可以事先把這些關(guān)聯(lián)表的數(shù)據(jù)按其主鍵排序。排序的成本雖然較高，但是一次性的。一旦完成了排序，以后就可以總是使用歸并算法實(shí)現(xiàn)JOIN，性能可以提高很多。
• 這還是利用了關(guān)聯(lián)鍵是主鍵（及其部分）的特征。
• 有序歸并對于大數(shù)據(jù)特別有效。像訂單及其明細(xì)這種主子表是不斷增長的事實(shí)表，時(shí)間長了常常會(huì)積累得非常大，很容易超出內(nèi)存容量。
• 外存大數(shù)據(jù)的HASH分堆算法需要產(chǎn)生很多緩存，數(shù)據(jù)在外存中被讀兩次寫一次，IO開銷很大。而歸并算法時(shí)，兩個(gè)表的數(shù)據(jù)都只要讀一次就行了，沒有寫。不僅是CPU的計(jì)算量減少，外存的IO量也大幅下降。而且，執(zhí)行歸并算法需要的內(nèi)存很少，只要在內(nèi)存中為每個(gè)表保持?jǐn)?shù)條緩存記錄就可以了，幾乎不會(huì)影響其它并發(fā)任務(wù)對內(nèi)存的需求。而HASH分堆需要較大內(nèi)存，每次讀出更多數(shù)據(jù)，以減少分堆的次數(shù)。
• SQL采用笛卡爾積定義的JOIN運(yùn)算不區(qū)分JOIN類型，不假定某些JOIN總是針對主鍵的，就沒辦法從算法層面上利用這一特點(diǎn)，只能在工程層面進(jìn)行優(yōu)化。有些數(shù)據(jù)庫會(huì)檢查數(shù)據(jù)表在物理存儲(chǔ)上是否針對關(guān)聯(lián)字段有序，如果有序則采用歸并算法，但基于無序集合概念的關(guān)系數(shù)據(jù)庫不會(huì)刻意保證數(shù)據(jù)的物理有序性，許多操作都會(huì)破壞歸并算法的實(shí)施條件。使用索引可以實(shí)現(xiàn)數(shù)據(jù)的邏輯有序，但物理無序時(shí)的遍歷效率還是會(huì)大打折扣。
• 有序歸并的前提是將數(shù)據(jù)按主鍵排序，而這類數(shù)據(jù)常常會(huì)不斷追加，原則上每次追加后就要再次排序，而我們知道大數(shù)據(jù)排序成本通常很高，這是否會(huì)導(dǎo)致追加數(shù)據(jù)難度很大呢？其實(shí)，追加數(shù)據(jù)再加入的過程也是個(gè)有序歸并，把新增數(shù)據(jù)單獨(dú)排序后和已有序的歷史數(shù)據(jù)歸并，復(fù)雜度是線性的，相當(dāng)于把所有數(shù)據(jù)重寫一次，而不像常規(guī)的大數(shù)據(jù)排序需要緩存式寫出再讀入。在工程上做些優(yōu)化動(dòng)作還可以做到不必每次都全部重寫，進(jìn)一步提高維護(hù)效率。這些在乾學(xué)院上都有介紹。

分段并行

• 有序歸并的好處還在于易于分段并行。
• 現(xiàn)代計(jì)算機(jī)的都有多核CPU，SSD硬盤也有較強(qiáng)的并發(fā)能力，使用多線程并行計(jì)算就能夠顯著提高性能。但傳統(tǒng)的HASH分堆技術(shù)實(shí)現(xiàn)并行比較困難，多線程做HASH分堆時(shí)需要同時(shí)向某個(gè)分堆寫出數(shù)據(jù)，造成共享資源沖突；而第二步實(shí)現(xiàn)某組分堆關(guān)聯(lián)時(shí)又會(huì)消費(fèi)大量內(nèi)存，無法讓實(shí)施較大的并行數(shù)量。
• 使用有序歸并實(shí)現(xiàn)并行計(jì)算時(shí)需要把數(shù)據(jù)分成多段，單個(gè)表分段比較簡單，但兩個(gè)關(guān)聯(lián)表分段時(shí)必須同步對齊，否則歸并時(shí)兩個(gè)表數(shù)據(jù)錯(cuò)位了，就無法得出正確的計(jì)算結(jié)果，而數(shù)據(jù)有序就可以保證高性能的同步對齊分段。
• 先把主表（同維表則取較大的即可，其它討論不影響）平均分成若干段，讀出每段第一條記錄的主鍵值，然后用這些鍵值到子表中用二分法尋找定位（因?yàn)橐灿行颍?，從而獲得子表的分段點(diǎn)。這樣可以保證主子表的分段是同步對齊的。
• 因?yàn)殒I值有序，所以主表每段的記錄鍵值都屬于某個(gè)連續(xù)區(qū)間，鍵值在區(qū)間外的記錄不會(huì)在這一段，鍵值在區(qū)間內(nèi)的記錄一定在這一段，子表對應(yīng)分段的記錄鍵值也有這個(gè)特性，所以不會(huì)發(fā)生錯(cuò)位情況；而同樣因?yàn)殒I值有序，才可以在子表中執(zhí)行高效的二分查找迅速定位出分段點(diǎn)。即數(shù)據(jù)有序保證了分段的合理性及高效性，這樣就可以放心地執(zhí)行并行算法了。
• 主子表這種主鍵關(guān)聯(lián)的關(guān)系還有一個(gè)特征，就是子表只會(huì)和一個(gè)主表在主鍵上關(guān)聯(lián)（其實(shí)同維表也有，但用主子表容易解釋），它不會(huì)有多個(gè)相互無關(guān)的主表（可能有主表的主表）。這時(shí)候，還可以使用一體化存儲(chǔ)的機(jī)制，把子表記錄作為主表的字段值去存儲(chǔ)。這樣，一方面減少了存儲(chǔ)量（關(guān)聯(lián)鍵只要存儲(chǔ)一次），又相當(dāng)于預(yù)先做好了關(guān)聯(lián)，不需要再做比對了。對于大數(shù)據(jù)，就能獲得更好的性能。
• 我們已經(jīng)將上述這些性能優(yōu)化手段在集算器SPL中實(shí)現(xiàn)并在實(shí)際場景用得到了應(yīng)用，也取得了非常好的效果。SPL目前已經(jīng)開源，讀者可以去數(shù)速公司或潤乾公司官網(wǎng)及論壇下載并獲得更多資料。

總結(jié)

程序員是一個(gè)特別依賴個(gè)人技術(shù)能力的職業(yè)，不同的程序員之間，技術(shù)能力的差別也非常大，不斷地深挖技術(shù)，補(bǔ)充自己的知識(shí)體系，是一個(gè)技術(shù)人成長的必要條件之一

JOIN運(yùn)算確實(shí)是數(shù)據(jù)庫中最復(fù)雜的運(yùn)算，本文對JOIN運(yùn)算進(jìn)行了深入的剖析整理，篇幅已經(jīng)不小，但仍然也沒有完全窮盡所有方面。

SPL資料

SPL官網(wǎng)

SPL下載

SPL源代碼

到此這篇關(guān)于體系化探討令人頭疼的JOIN運(yùn)算的文章就介紹到這了,更多相關(guān)JOIN運(yùn)算內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！