這篇文章主要介紹了MySQL體系化之JOIN運(yùn)算實(shí)例分析的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇Mysql體系化之JOIN運(yùn)算實(shí)例分析文章都會(huì)有所收獲，下面我們一起來(lái)看看吧。

公司主營(yíng)業(yè)務(wù)：網(wǎng)站建設(shè)、網(wǎng)站制作、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶(hù)真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)建站是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶(hù)帶來(lái)驚喜。創(chuàng)新互聯(lián)建站推出海晏免費(fèi)做網(wǎng)站回饋大家。

SQL中的JOIN

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

SQL對(duì)JOIN的定義

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

• 理論上講，笛卡爾積的結(jié)果集應(yīng)該是以?xún)蓚€(gè)集合成員構(gòu)成的二元組作為成員，不過(guò)由于SQL中的集合也就是表，其成員總是有字段的記錄，而且也不支持泛型數(shù)據(jù)類(lèi)型來(lái)描述成員為記錄的二元組，所以就簡(jiǎn)單地把結(jié)果集處理成兩表記錄的字段合并后構(gòu)成的新記錄的集合。

• 這也是JOIN一詞在英語(yǔ)中的原意（即把兩個(gè)記錄的字段連接起來(lái)），并沒(méi)有乘法（笛卡爾積）的意思。不過(guò)，把笛卡爾積成員理解成二元組還是合并字段的記錄，并不影響我們后續(xù)的討論。

JOIN定義

• JOIN的定義中并沒(méi)有約定過(guò)濾條件的形式，理論上，只要結(jié)果集是兩個(gè)源集合笛卡爾積的子集，都是合理的JOIN運(yùn)算。

• 例子：假設(shè)集合A={1,2},B={1,2,3}，A JOIN B ON A

JOIN分類(lèi)

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

等值JOIN

• 條件可能由多個(gè)有AND關(guān)系的等式構(gòu)成，語(yǔ)法形式A JOIN B ON A.ai=B.bi AND …，其中ai和bi分別是A和B的字段。

• 有經(jīng)驗(yàn)的程序員都知道，現(xiàn)實(shí)中絕大多數(shù)JOIN都是等值JOIN，非等值JOIN要少見(jiàn)得多，而且大多數(shù)情況都可以轉(zhuǎn)換成等值JOIN來(lái)處理，所以我們?cè)谶@里重點(diǎn)討論等值JOIN，并且后續(xù)討論中也主要使用表和記錄而不是集合和成員來(lái)舉例。

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

• 根據(jù)對(duì)空值的處理規(guī)則，嚴(yán)格的等值JOIN又稱(chēng)為INNER JOIN，還可以再衍生出LEFT JOIN和FULL JOIN，共有三種情況（RIGHT JOIN可以理解為L(zhǎng)EFT JOIN的反向關(guān)聯(lián)，不再單獨(dú)作為一種類(lèi)型）。

• 談?wù)揓OIN時(shí)一般還會(huì)根據(jù)兩個(gè)表中關(guān)聯(lián)記錄（也就是滿(mǎn)足過(guò)濾條件的二元組）的數(shù)量分為一對(duì)一、一對(duì)多、多對(duì)一以及多對(duì)多這幾種情況，這些常規(guī)術(shù)語(yǔ)在SQL和數(shù)據(jù)庫(kù)資料中都有介紹，這里就不再贅述了。

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

笨辦法

• 最容易想到的簡(jiǎ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次過(guò)濾條件的計(jì)算。

• 顯然這種算法會(huì)比較慢。不過(guò)，支持多數(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中的過(guò)濾條件）會(huì)拆散定義在單元格的運(yùn)算式中，已經(jīng)看不出是多個(gè)數(shù)據(jù)集之間的JOIN運(yùn)算，也就只能用遍歷方法去計(jì)算這些關(guān)聯(lián)表達(dá)式了。

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

• 對(duì)于等值JOIN，數(shù)據(jù)庫(kù)一般會(huì)采用HASH JOIN算法。即將關(guān)聯(lián)表的記錄按其關(guān)聯(lián)鍵（過(guò)濾條件中對(duì)應(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，則過(guò)濾條件的計(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)表要提速的話(huà)，也需要在數(shù)據(jù)準(zhǔn)備階段做好關(guān)聯(lián)，否則數(shù)據(jù)量稍大時(shí)性能就會(huì)急劇下降。

• 不過(guò)，HASH函數(shù)并不總能保證平均分拆，在運(yùn)氣不好的時(shí)候可能會(huì)發(fā)生某一組特別大的情況，那樣性能提升效果就會(huì)差很多。而且還不能使用太復(fù)雜的HASH函數(shù)，否則計(jì)算HASH的時(shí)間又變多了。

• 當(dāng)數(shù)據(jù)量大到超過(guò)內(nèi)存時(shí)，數(shù)據(jù)庫(kù)會(huì)使用HASH分堆的方法，算是HASH JOIN算法的推廣。遍歷A表和B表，將記錄按關(guān)聯(lián)鍵的HASH值拆分成若干小子集緩存到外存中，稱(chēng)為分堆。然后再在對(duì)應(yīng)的堆之間做內(nèi)存JOIN運(yùn)算。同樣的道理，HASH值不同時(shí)鍵值也必然不同，關(guān)聯(lián)一定發(fā)生在對(duì)應(yīng)的堆之間。這樣就把大數(shù)據(jù)的JOIN轉(zhuǎn)換成若干小數(shù)據(jù)的JOIN了。

• 但是類(lèi)似地，HASH函數(shù)存在運(yùn)氣問(wèn)題，有可能會(huì)發(fā)生某個(gè)分堆還特別大而無(wú)法裝入內(nèi)存，這時(shí)候就可能要進(jìn)行二次HASH分堆，即換一個(gè)HASH函數(shù)對(duì)這組太大的分堆再做一次HASH分堆算法。所以，外存JOIN運(yùn)算有可能出現(xiàn)多次緩存的現(xiàn)象，其運(yùn)算性能有一定的不可控性。

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

• 分布式系統(tǒng)下做JOIN也是類(lèi)似的，根據(jù)關(guān)聯(lián)鍵的HASH值將記錄分發(fā)到各個(gè)節(jié)點(diǎn)機(jī)上，稱(chēng)為Shuffle動(dòng)作，然后再分別做單機(jī)的JOIN。

• 當(dāng)節(jié)點(diǎn)比較多的時(shí)候，造成的網(wǎng)絡(luò)傳輸量帶來(lái)的延遲會(huì)抵消多機(jī)分?jǐn)側(cè)蝿?wù)得到的好處，所以分布式數(shù)據(jù)庫(kù)系統(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é)說(shuō)過(guò)的在等值JOIN的過(guò)濾條件中要對(duì)應(yīng)相等的字段）。A表稱(chēng)為事實(shí)表，B表稱(chēng)為維表。A表中與B表主鍵關(guān)聯(lián)的字段稱(chēng)為A指向B的外鍵，B也稱(chēng)為A的外鍵表。

• 這里說(shuō)的主鍵是指邏輯上的主鍵，也就是在表中取值唯一、可以用于唯一某條記錄的字段（組），不一定在數(shù)據(jù)庫(kù)表上建立過(guò)主鍵。

• 外鍵表是多對(duì)一的關(guān)系，且只有JOIN和LEFT JOIN，而FULL JOIN非常罕見(jiàn)。

• 典型案例：商品交易表和商品信息表。

• 顯然，外鍵關(guān)聯(lián)是不對(duì)稱(chēng)的。事實(shí)表和維表的位置不能互換。

同維表

• 表A的主鍵與表B的主鍵關(guān)聯(lián)，A和B互稱(chēng)為同維表。同維表是一對(duì)一的關(guān)系，JOIN、LEFT JOIN和FULL JOIN的情況都會(huì)有，不過(guò)在大多數(shù)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方案中，F(xiàn)ULL JOIN也相對(duì)少見(jiàn)。

• 典型案例：?jiǎn)T工表和經(jīng)理表。

• 同維表之間是對(duì)稱(chēng)的，兩個(gè)表的地位相同。同維表還構(gòu)成是等價(jià)關(guān)系，A和B是同維表，B和C是同維表，則A和C也是同維表。

主子表

• 表A的主鍵與表B的部分主鍵關(guān)聯(lián)，A稱(chēng)為主表，B稱(chēng)為子表。主子表是一對(duì)多的關(guān)系，只有JOIN和LEFT JOIN，不會(huì)有FULL JOIN。

• 典型案例：訂單和訂單明細(xì)。

• 主子表也是不對(duì)稱(chēng)的，有明確的方向。

• 在SQL的概念體系中并不區(qū)分外鍵表和主子表，多對(duì)一和一對(duì)多從SQL的觀點(diǎn)看來(lái)只是關(guān)聯(lián)方向不同，本質(zhì)上是一回事。確實(shí)，訂單也可以理解成訂單明細(xì)的外鍵表。但是，我們?cè)谶@里要把它們區(qū)分開(kāi)，將來(lái)在簡(jiǎn)化語(yǔ)法和性能優(yōu)化時(shí)將使用不同的手段。

• 我們說(shuō)，這三種JOIN已經(jīng)涵蓋了絕大多數(shù)等值JOIN的情況，甚至可以說(shuō)幾乎全部有業(yè)務(wù)意義的等值JOIN都屬于這三類(lèi)，把等值JOIN限定在這三種情況之中，幾乎不會(huì)減少其適應(yīng)范圍。

• 仔細(xì)考察這三種JOIN，我們發(fā)現(xiàn)所有關(guān)聯(lián)都涉及主鍵，沒(méi)有多對(duì)多的情況，是不是可以不考慮這種情況？

• 是的！多對(duì)多的等值JOIN幾乎沒(méi)有業(yè)務(wù)意義。

• 如果兩個(gè)表JOIN時(shí)的關(guān)聯(lián)字段沒(méi)有涉及到任何主鍵，那就會(huì)發(fā)生多對(duì)多的情況，而這種情況幾乎一定還會(huì)有一個(gè)規(guī)模更大的表把這兩個(gè)表作為維表關(guān)聯(lián)起來(lái)。比如學(xué)生表和科目表在JOIN時(shí)，會(huì)有個(gè)成績(jī)表把學(xué)生表和科目表作為維表，單純只有學(xué)生表和科目表的JOIN沒(méi)有業(yè)務(wù)意義。

• 當(dāng)寫(xiě)SQL語(yǔ)句時(shí)發(fā)現(xiàn)多對(duì)多的情況，那大概率是這個(gè)語(yǔ)句寫(xiě)錯(cuò)了！或者數(shù)據(jù)有問(wèn)題！這條法則用于排除JOIN錯(cuò)誤很有效。

• 不過(guò)，我們一直在說(shuō)“幾乎”，并沒(méi)有用完全肯定的說(shuō)法，也就是說(shuō)，多對(duì)多在非常罕見(jiàn)的情況下也會(huì)業(yè)務(wù)意義?？膳e一例，用SQL實(shí)現(xiàn)矩陣乘法時(shí)會(huì)發(fā)生多對(duì)多的等值JOIN，具體寫(xiě)法讀者可以自行補(bǔ)充。

• 笛卡爾積再過(guò)濾這種JOIN定義，確實(shí)非常簡(jiǎn)單，而簡(jiǎn)單的內(nèi)涵將得到更大的外延，可以把多對(duì)多等值JOIN甚至非等值JOIN等都包括進(jìn)來(lái)。但是，過(guò)于簡(jiǎn)單的內(nèi)涵無(wú)法充分體現(xiàn)出最常見(jiàn)等值JOIN的運(yùn)算特征。這會(huì)導(dǎo)致編寫(xiě)代碼和實(shí)現(xiàn)運(yùn)算時(shí)就不能利用這些特征，在運(yùn)算較為復(fù)雜時(shí)（涉及關(guān)聯(lián)表較多以及有嵌套的情況），無(wú)論是書(shū)寫(xiě)還是優(yōu)化都非常困難。而充分利用這些特征后，我們就能創(chuàng)造出更簡(jiǎn)單的書(shū)寫(xiě)形式并獲得更高效的運(yùn)算性能，后面的內(nèi)容中將會(huì)逐步加以說(shuō)明。

• 與其為了把罕見(jiàn)情況也被包括進(jìn)來(lái)而把運(yùn)算定義為更通用的形式，還不如把這些情況定義成另一種運(yùn)算更為合理。

JOIN的語(yǔ)法簡(jiǎn)化

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

外鍵屬性化

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

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

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

• employee表和department表的主鍵都是其中的id字段，employee表的department字段是指向department表的外鍵，department表的manager字段又是指向employee表的外鍵（因?yàn)榻?jīng)理也是個(gè)員工）。這是很常規(guī)的表結(jié)構(gòu)設(shè)計(jì)。

• 現(xiàn)在我們想問(wèn)一下：哪些美國(guó)籍員工有一個(gè)中國(guó)籍經(jīng)理？用SQL寫(xiě)出來(lái)是個(gè)三表JOIN的語(yǔ)句：

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獲取員工的部門(mén)信息，接著這個(gè)department表還要再和employee表JOIN要獲取經(jīng)理的信息，這樣employee表需要兩次參與JOIN，在SQL語(yǔ)句中要為它起個(gè)別名加以區(qū)分，整個(gè)句子就顯得比較復(fù)雜難懂。

• 如果我們把外鍵字段直接理解成它關(guān)聯(lián)的維表記錄，就可以換一種寫(xiě)法：

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

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

• 第二個(gè)句子中粗體部分表示當(dāng)前員工的“所屬部門(mén)的經(jīng)理的國(guó)籍”。我們把外鍵字段理解成維表的記錄后，維表的字段被理解為外鍵的屬性，department.manager即是“所屬部門(mén)的經(jīng)理”，而這個(gè)字段在department中仍然是個(gè)外鍵，那么它對(duì)應(yīng)的維表記錄字段可以繼續(xù)理解為它的屬性，也就會(huì)有department.manager.nationality，即“所屬部門(mén)的經(jīng)理的國(guó)籍”。

• 外鍵屬性化:這種對(duì)象式的理解方式即為外鍵屬性化，顯然比笛卡爾積過(guò)濾的理解方式要自然直觀得多。外鍵表JOIN時(shí)并不會(huì)涉及到兩個(gè)表的乘法，外鍵字段只是用于找到維鍵表中對(duì)應(yīng)的那條記錄，完全不會(huì)涉及到笛卡爾積這種有乘法特性的運(yùn)算。

• 我們前面約定，外鍵關(guān)聯(lián)時(shí)時(shí)維表中關(guān)聯(lián)鍵必須是主鍵，這樣，事實(shí)表中每一條記錄的外鍵字段關(guān)聯(lián)的維表記錄就是唯一的，也就是說(shuō)employee表中每一條記錄的department字段唯一關(guān)聯(lián)一條department表中的記錄，而department表中每一條記錄的manager字段也唯一關(guān)聯(lián)一條employee表中的記錄。這就保證了對(duì)于employee表中的每一條記錄，department.manager.nationality都有唯一的取值，可以被明確定義。

• 但是，SQL對(duì)JOIN的定義中并沒(méi)有主鍵的約定，如果基于SQL的規(guī)則，就不能認(rèn)定與事實(shí)表中外鍵關(guān)聯(lián)的維表記錄有唯一性，有可能發(fā)生與多條記錄關(guān)聯(lián)，對(duì)于employee表的記錄來(lái)講，department.manager.nationality沒(méi)有明確定義，就不能使用了。

• 事實(shí)上，這種對(duì)象式寫(xiě)法在高級(jí)語(yǔ)言（如C，Java）中很常見(jiàn)，在這類(lèi)語(yǔ)言中，數(shù)據(jù)就是按對(duì)象方式存儲(chǔ)的。employee表中的department字段取值根本就是一個(gè)對(duì)象，而不是編號(hào)。其實(shí)許多表的主鍵取值本身并沒(méi)有業(yè)務(wù)意義，僅僅是為了區(qū)分記錄，而外鍵字段也僅僅是為了找到維表中的相應(yīng)記錄，如果外鍵字段直接是對(duì)象，就不需要再通過(guò)編號(hào)來(lái)標(biāo)識(shí)了。不過(guò)，SQL不能支持這種存儲(chǔ)機(jī)制，還要借助編號(hào)。

• 我們說(shuō)過(guò)外鍵關(guān)聯(lián)是不對(duì)稱(chēng)的，即事實(shí)表和維表是不對(duì)等的，只能基于事實(shí)表去找維表字段，而不會(huì)有倒過(guò)來(lái)的情況。

同維表等同化

同維表的情況相對(duì)簡(jiǎn)單，還是從例子開(kāi)始，設(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)理表來(lái)保存。

• 現(xiàn)在我們要統(tǒng)計(jì)所有員工（包括經(jīng)理）的總收入（加上津貼）。用SQL寫(xiě)出來(lái)還是會(huì)用到JOIN：

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

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

SELECT id,name,salary+allowance
FROM employee

• 類(lèi)似地，根據(jù)我們的約定，同維表JOIN時(shí)兩個(gè)表都是按主鍵關(guān)聯(lián)的，相應(yīng)記錄是唯一對(duì)應(yīng)的，salary+allowance對(duì)employee表中每條記錄都是唯一可計(jì)算的，不會(huì)出現(xiàn)歧義。這種簡(jiǎn)化方式稱(chēng)為同維表等同化。

• 同維表之間的關(guān)系是對(duì)等的，從任何一個(gè)表都可以引用到其它同維表的字段。

子表集合化

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

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

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

現(xiàn)在我們想計(jì)算每張訂單的總金額。用SQL寫(xiě)出來(lái)會(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，否則選出來(lái)的記錄數(shù)太多。

• 如果我們把子表中與主表相關(guān)的記錄看成主表的一個(gè)字段，那么這個(gè)問(wèn)題也可以不再使用JOIN以及GROUP BY：

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

• 與普通字段不同，OrderDetail被看成Orders表的字段時(shí)，其取值將是一個(gè)集合，因?yàn)閮蓚€(gè)表是一對(duì)多的關(guān)系。所以要在這里使用聚合運(yùn)算把集合值計(jì)算成單值。這種簡(jiǎn)化方式稱(chēng)為子表集合化。

• 這樣看待主子表關(guān)聯(lián)，不僅理解書(shū)寫(xiě)更為簡(jiǎn)單，而且不容易出錯(cuò)。

• 假如Orders表還有一個(gè)子表用于記錄回款情況：

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

• 我們現(xiàn)在想知道那些訂單還在欠錢(qián)，也就是累計(jì)回款金額小于訂單總金額的訂單。

• 簡(jiǎn)單地把這三個(gè)表JOIN起來(lái)是不對(duì)的，OrderDetail和OrderPayment會(huì)發(fā)生多對(duì)多的關(guān)系，這就錯(cuò)了（回憶前面提過(guò)的多對(duì)多大概率錯(cuò)誤的說(shuō)法）。這兩個(gè)子表要分別先做GROUP，再一起與Orders表JOIN起來(lái)才能得到正確結(jié)果，會(huì)寫(xiě)成子查詢(xún)的形式：

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ù)把子表看成主表的集合字段，那就很簡(jiǎn)單了：

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

• 這種寫(xiě)法也不容易發(fā)生多對(duì)多的錯(cuò)誤。

• 主子表關(guān)系是不對(duì)等的，不過(guò)兩個(gè)方向的引用都有意義，上面談了從主表引用子表的情況，從子表引用主表則和外鍵表類(lèi)似。

• 我們改變對(duì)JOIN運(yùn)算的看法，摒棄笛卡爾積的思路，把多表關(guān)聯(lián)運(yùn)算看成是稍復(fù)雜些的單表運(yùn)算。這樣，相當(dāng)于把最常見(jiàn)的等值JOIN運(yùn)算的關(guān)聯(lián)消除了，甚至在語(yǔ)法中取消了JOIN關(guān)鍵字，書(shū)寫(xiě)和理解都要簡(jiǎn)單很多。

維度對(duì)齊語(yǔ)法

我們?cè)倩仡櫱懊娴碾p子表例子的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

• 那么問(wèn)題來(lái)了，這顯然是個(gè)有業(yè)務(wù)意義的JOIN，它算是前面所說(shuō)的哪一類(lèi)呢？

• 這個(gè)JOIN涉及了表Orders和子查詢(xún)A與B，仔細(xì)觀察會(huì)發(fā)現(xiàn)，子查詢(xún)帶有GROUP BY id的子句，顯然，其結(jié)果集將以id為主鍵。這樣，JOIN涉及的三個(gè)表（子查詢(xún)也算作是個(gè)臨時(shí)表）的主鍵是相同的，它們是一對(duì)一的同維表，仍然在前述的范圍內(nèi)。

• 但是，這個(gè)同維表JOIN卻不能用前面說(shuō)的寫(xiě)法簡(jiǎn)化，子查詢(xún)A,B都不能省略不寫(xiě)。

• 可以簡(jiǎn)化書(shū)寫(xiě)的原因：我們假定事先知道數(shù)據(jù)結(jié)構(gòu)中這些表之間的關(guān)聯(lián)關(guān)系。用技術(shù)術(shù)語(yǔ)的說(shuō)法，就是知道數(shù)據(jù)庫(kù)的元數(shù)據(jù)（metadata）。而對(duì)于臨時(shí)產(chǎn)生的子查詢(xún)，顯然不可能事先定義在元數(shù)據(jù)中了，這時(shí)候就必須明確指定要JOIN的表（子查詢(xún)）。

• 不過(guò)，雖然JOIN的表（子查詢(xún)）不能省略，但關(guān)聯(lián)字段總是主鍵。子查詢(xún)的主鍵總是由GROUP BY產(chǎn)生，而GROUP BY的字段一定要被選出用于做外層JOIN；并且這幾個(gè)子查詢(xún)涉及的子表是互相獨(dú)立的，它們之間不會(huì)再有關(guān)聯(lián)計(jì)算了，我們就可以把GROUP動(dòng)作以及聚合式直接放到主句中，從而消除一層子查詢(xún)：

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)差別很大，完全沒(méi)有笛卡爾積的意思了。而且，也不同于SQL的JOIN運(yùn)算將定義在任何兩個(gè)表之間，這里的JOIN，OrderDetail和OrderPayment以及Orders都是向一個(gè)共同的主鍵id對(duì)齊，即所有表都向某一套基準(zhǔn)維度對(duì)齊。而由于各表的維度（主鍵）不同，對(duì)齊時(shí)可能會(huì)有GROUP BY，在引用該表字段時(shí)就會(huì)相應(yīng)地出現(xiàn)聚合運(yùn)算。OrderDetail和OrderPayment甚至Orders之間都不直接發(fā)生關(guān)聯(lián)，在書(shū)寫(xiě)運(yùn)算時(shí)當(dāng)然就不用關(guān)心它們之間的關(guān)系，甚至不必關(guān)心另一個(gè)表是否存在。而SQL那種笛卡爾積式的JOIN則總要找一個(gè)甚至多個(gè)表來(lái)定義關(guān)聯(lián)，一旦減少或修改表時(shí)就要同時(shí)考慮關(guān)聯(lián)表，增大理解難度。

• 維度對(duì)齊：這種JOIN稱(chēng)即為維度對(duì)齊，它并不超出我們前面說(shuō)過(guò)的三種JOIN范圍，但確實(shí)在語(yǔ)法描述上會(huì)有不同，這里的JOIN不象SQL中是個(gè)動(dòng)詞，卻更象個(gè)連詞。而且，和前面三種基本JOIN中不會(huì)或很少發(fā)生FULL JOIN的情況不同，維度對(duì)齊的場(chǎng)景下FULL JOIN并不是很罕見(jiàn)的情況。

• 雖然我們從主子表的例子抽象出維度對(duì)齊，但這種JOIN并不要求JOIN的表是主子表（事實(shí)上從前面的語(yǔ)法可知，主子表運(yùn)算還不用寫(xiě)這么麻煩），任何多個(gè)表都可以這么關(guān)聯(lián)，而且關(guān)聯(lián)字段也完全不必要是主鍵或主鍵的部分。

• 設(shè)有合同表，回款表和發(fā)票表：

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

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

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

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

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ú)列出來(lái)表示結(jié)果集按日期對(duì)齊。

• 這種寫(xiě)法，不必關(guān)心這三個(gè)表之間的關(guān)聯(lián)關(guān)系，各自寫(xiě)各自有關(guān)的部分就行，似乎這幾個(gè)表就沒(méi)有關(guān)聯(lián)關(guān)系，把它們連到一起的就是那個(gè)要共同對(duì)齊的維度（這里是date）。

• 這幾種JOIN情況還可能混合出現(xiàn)。

• 繼續(xù)舉例，延用上面的合同表，再有客戶(hù)表和銷(xiāo)售員表

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

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

• 其中Contract表中customer字段是指向Customer表的外鍵。

• 現(xiàn)在我們想統(tǒng)計(jì)每個(gè)地區(qū)的銷(xiāo)售員數(shù)量及合同額：

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

• 維度對(duì)齊可以和外鍵屬性化的寫(xiě)法配合合作。

• 這些例子中，最終的JOIN都是同維表。事實(shí)上，維度對(duì)齊還有主子表對(duì)齊的情況，不過(guò)相對(duì)罕見(jiàn)，我們這里就不深入討論了。

• 另外，目前這些簡(jiǎn)化語(yǔ)法仍然是示意性，需要在嚴(yán)格定義維度概念之后才能相應(yīng)地形式化，成為可以解釋執(zhí)行的句子。

• 我們把這種簡(jiǎn)化的語(yǔ)法稱(chēng)為DQL（Dimensional Query Languange），DQL是以維度為核心的查詢(xún)語(yǔ)言。我們已經(jīng)將DQL在工程上做了實(shí)現(xiàn)，并作為潤(rùn)乾報(bào)表的DQL服務(wù)器發(fā)布出來(lái)，它能將DQL語(yǔ)句翻譯成SQL語(yǔ)句執(zhí)行，也就是可以在任何關(guān)系數(shù)據(jù)庫(kù)上運(yùn)行。

• 對(duì)DQL理論和應(yīng)用感興趣的讀者可以關(guān)注乾學(xué)院上發(fā)布的論文和相關(guān)文章。

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

多表JOIN問(wèn)題

• 我們知道，SQL允許用WHERE來(lái)寫(xiě)JOIN運(yùn)算的過(guò)濾條件（回顧原始的笛卡爾積式的定義），很多程序員也習(xí)慣于這么寫(xiě)。

• 當(dāng)JOIN表只有兩三個(gè)的時(shí)候，那問(wèn)題還不大，但如果JOIN表有七八個(gè)甚至十幾個(gè)的時(shí)候，漏寫(xiě)一個(gè)JOIN條件是很有可能的。而漏寫(xiě)了JOIN條件意味著將發(fā)生多對(duì)多的完全叉乘，而這個(gè)SQL卻可以正常執(zhí)行，會(huì)有以下兩點(diǎn)危害：

• 一方面計(jì)算結(jié)果會(huì)出錯(cuò):回憶一下以前說(shuō)過(guò)的，發(fā)生多對(duì)多JOIN時(shí)，大概率是語(yǔ)句寫(xiě)錯(cuò)了

• 另一方面，如果漏寫(xiě)條件的表很大，笛卡爾積的規(guī)模將是平方級(jí)的，這極有可能把數(shù)據(jù)庫(kù)直接“跑死”！

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

• 一個(gè)直接的效果顯然是讓語(yǔ)句書(shū)寫(xiě)和理解更容易

• 外鍵屬性化、同維表等同化和子表集合化方案直接消除了顯式的關(guān)聯(lián)運(yùn)算，也更符合自然思維

• 維度對(duì)齊則可讓程序員不再關(guān)心表間關(guān)系，降低語(yǔ)句的復(fù)雜度

• 簡(jiǎn)化JOIN語(yǔ)法的好處不僅在于此，還能夠降低出錯(cuò)率，采用簡(jiǎn)化后的JOIN語(yǔ)法，就不可能發(fā)生漏寫(xiě)JOIN條件的情況了。因?yàn)閷?duì)JOIN的理解不再是以笛卡爾積為基礎(chǔ)，而且設(shè)計(jì)這些語(yǔ)法時(shí)已經(jīng)假定了多對(duì)多關(guān)聯(lián)沒(méi)有業(yè)務(wù)意義，這個(gè)規(guī)則下寫(xiě)不出完全叉乘的運(yùn)算。

• 對(duì)于多個(gè)子表分組后與主表對(duì)齊的運(yùn)算，在SQL中要寫(xiě)成多個(gè)子查詢(xún)的形式。但如果只有一個(gè)子表時(shí)，可以先JOIN再GROUP，這時(shí)不需要子查詢(xún)。有些程序員沒(méi)有仔細(xì)分析，會(huì)把這種寫(xiě)法推廣到多個(gè)子表的情況，也先JOIN再GROUP，可以避免使用子查詢(xún)，但計(jì)算結(jié)果是錯(cuò)誤的。

• 使用維度對(duì)齊的寫(xiě)法就不容易發(fā)生這種錯(cuò)誤了，無(wú)論多少個(gè)子表，都不需要子查詢(xún)，一個(gè)子表和多個(gè)子表的寫(xiě)法完全相同。

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

• 重新看待JOIN運(yùn)算，最關(guān)鍵的作用在于實(shí)現(xiàn)關(guān)聯(lián)查詢(xún)。

• 當(dāng)前BI產(chǎn)品是個(gè)熱門(mén)，各家產(chǎn)品都宣稱(chēng)能夠讓業(yè)務(wù)人員拖拖拽拽就完成想要的查詢(xún)報(bào)表。但實(shí)際應(yīng)用效果會(huì)遠(yuǎn)不如人意，業(yè)務(wù)人員仍然要經(jīng)常求助于IT部門(mén)。造成這個(gè)現(xiàn)象的主要原因在于大多數(shù)業(yè)務(wù)查詢(xún)都是有過(guò)程的計(jì)算，本來(lái)也不可能拖拽完成。但是，也有一部分業(yè)務(wù)查詢(xún)并不涉及多步過(guò)程，而業(yè)務(wù)人員仍然難以完成。

• 這就是關(guān)聯(lián)查詢(xún)，也是大多數(shù)BI產(chǎn)品的軟肋。在之前的文章中已經(jīng)講過(guò)為什么關(guān)聯(lián)查詢(xún)很難做，其根本原因就在于SQL對(duì)JOIN的定義過(guò)于簡(jiǎn)單。

• 結(jié)果，BI產(chǎn)品的工作模式就變成先由技術(shù)人員構(gòu)建模型，再由業(yè)務(wù)人員基于模型進(jìn)行查詢(xún)。而所謂建模，就是生成一個(gè)邏輯上或物理上的寬表。也就是說(shuō)，建模要針對(duì)不同的關(guān)聯(lián)需求分別實(shí)現(xiàn)，我們稱(chēng)之為按需建模，這時(shí)候的BI也就失去敏捷性了。

• 但是，如果我們改變了對(duì)JOIN運(yùn)算的看法，關(guān)聯(lián)查詢(xún)可以從根本上得到解決?；貞浨懊嬷v過(guò)的三種JOIN及其簡(jiǎn)化手段，我們事實(shí)上把這幾種情況的多表關(guān)聯(lián)都轉(zhuǎn)化成了單表查詢(xún)，而業(yè)務(wù)用戶(hù)對(duì)于單表查詢(xún)并沒(méi)有理解障礙。無(wú)非就是表的屬性（字段）稍復(fù)雜了一些：可能有子屬性（外鍵字段指向的維表并引用其字段），子屬性可能還有子屬性（多層的維表），有些字段取值是集合而非單值（子表看作為主表的字段）。發(fā)生互相關(guān)聯(lián)甚至自我關(guān)聯(lián)也不會(huì)影響理解（前面的中國(guó)經(jīng)理的美國(guó)員工例子就是互關(guān)聯(lián)），同表有相同維度當(dāng)然更不礙事（各自有各自的子屬性）。

• 在這種關(guān)聯(lián)機(jī)制下，技術(shù)人員只要一次性把數(shù)據(jù)結(jié)構(gòu)（元數(shù)據(jù)）定義好，在合適的界面下（把表的字段列成有層次的樹(shù)狀而不是常規(guī)的線(xiàn)狀），就可以由業(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)

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

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

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

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

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

• 其中orders表中的custkey是指向customer表中key字段的外鍵，key是customer表的主鍵。

• 現(xiàn)在我們各個(gè)城市的訂單總額（為簡(jiǎn)化討論，就不再設(shè)定條件了），用SQL寫(xiě)出來(lái)：

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

• 數(shù)據(jù)庫(kù)一般會(huì)使用HASH JOIN算法，需要分別兩個(gè)表中關(guān)聯(lián)鍵的HASH值并比對(duì)。

• 我們用前述的簡(jiǎn)化的JOIN語(yǔ)法（DQL）寫(xiě)出這個(gè)運(yùn)算：

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

• 這個(gè)寫(xiě)法其實(shí)也就預(yù)示了它還可以有更好的優(yōu)化方案，下面來(lái)看看怎樣實(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無(wú)法描述這個(gè)運(yùn)算的細(xì)節(jié)過(guò)程，我們使用SPL來(lái)描述、并用文件作為數(shù)據(jù)源來(lái)說(shuō)明計(jì)算過(guò)程：

• A1讀出客戶(hù)表，A2為客戶(hù)表設(shè)置主鍵并建立索引。

• A3讀出訂單表，A4的動(dòng)作是將A3的外鍵字段custkey轉(zhuǎn)換成對(duì)應(yīng)的A1的記錄，執(zhí)行完后，訂單表字段custkey將變成客戶(hù)表的某條記錄。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)作即稱(chēng)為外鍵地址化。這時(shí)候引用維表字段時(shí)，可以直接取出，而不需要再用外鍵值在A1中查找，相當(dāng)于在常數(shù)時(shí)間內(nèi)就能取到維表的字段，避免了HASH值計(jì)算和比對(duì)。

• 不過(guò)，A2建主鍵索引一般也會(huì)用HASH辦法，對(duì)key計(jì)算HASH值，A4轉(zhuǎn)換地址時(shí)也是計(jì)算custkey的HASH值與A2的HASH索引表對(duì)比。如果只做一次關(guān)聯(lián)運(yùn)算，地址化的方案和傳統(tǒng)HASH分段方案的計(jì)算量基本上一樣，沒(méi)有根本優(yōu)勢(shì)。

• 但不同的是，如果數(shù)據(jù)能在內(nèi)存中放下，這個(gè)地址一旦轉(zhuǎn)換之后可以復(fù)用，也就是說(shuō)A1到A4只要做一次，下次再做關(guān)于這兩個(gè)字段的關(guān)聯(lián)運(yùn)算時(shí)就不必再計(jì)算HASH值和比對(duì)了，性能就能大幅提高。

• 能夠這樣做，正是利用了前面說(shuō)過(guò)的外鍵關(guān)聯(lián)在維表這一方具有的唯一性，一個(gè)外鍵字段值只會(huì)唯一對(duì)應(yīng)一條維表記錄，可以把每個(gè)custkey轉(zhuǎn)換成它唯一對(duì)應(yīng)的那條A1的記錄。而延用SQL中對(duì)JOIN的定義，就不能假定外鍵指向記錄的唯一性，無(wú)法使用這種表示法。而且SQL也沒(méi)有記錄地址這種數(shù)據(jù)類(lèi)型，結(jié)果會(huì)導(dǎo)致每次關(guān)聯(lián)時(shí)都要計(jì)算HASH值并比對(duì)。

• 而且，如果事實(shí)表中有多個(gè)外鍵分別指向多個(gè)維表，傳統(tǒng)的HASH分段JOIN方案每次只能解析掉一個(gè)，有多個(gè)JOIN要執(zhí)行多遍動(dòng)作，每次關(guān)聯(lián)后都需要保持中間結(jié)果供下一輪使用，計(jì)算過(guò)程復(fù)雜得多，數(shù)據(jù)也會(huì)被遍歷多次。而外鍵地址化方案在面對(duì)多個(gè)外鍵時(shí)，只要對(duì)事實(shí)表遍歷一次，沒(méi)有中間結(jié)果，計(jì)算過(guò)程要清晰很多。

• 還有一點(diǎn)，內(nèi)存本來(lái)是很適合并行計(jì)算的，但HASH分段JOIN算法卻不容易并行。即使把數(shù)據(jù)分段并行計(jì)算HASH值，但要把相同HASH值的記錄歸聚到一起供下一輪比對(duì)，還會(huì)發(fā)生共享資源搶占的事情，這將犧牲很多并行計(jì)算的優(yōu)勢(shì)。而外鍵式JOIN模型下，關(guān)聯(lián)兩表的地位不對(duì)等，明確區(qū)分出維表和事實(shí)表后，只要簡(jiǎn)單地將事實(shí)表分段就可以并行計(jì)算。

• 將HASH分段技術(shù)參照外鍵屬性方案進(jìn)行改造后，也能一定程度地改善多外鍵一次解析和并行能力，有些數(shù)據(jù)庫(kù)能在工程層面上實(shí)施這種優(yōu)化。不過(guò)，這種優(yōu)化在只有兩個(gè)表JOIN時(shí)問(wèn)題不大，在有很多表及各種JOIN混在一起時(shí)，數(shù)據(jù)庫(kù)并不容易識(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é)果集并無(wú)顯著增大）。而從JOIN模型上引入外鍵概念后，將這種JOIN專(zhuān)門(mén)處理時(shí)，就總能分清事實(shí)表和維表，更多的JOIN表只會(huì)導(dǎo)致性能的線(xiàn)性下降。

• 內(nèi)存數(shù)據(jù)庫(kù)是當(dāng)前比較火熱的技術(shù)，但上述分析表明，采用SQL模型的內(nèi)存數(shù)據(jù)庫(kù)在JOIN運(yùn)算上是很難快起來(lái)的！

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

• 我們繼續(xù)討論外鍵JOIN，并延用上一節(jié)的例子。

• 當(dāng)數(shù)據(jù)量大到無(wú)法全部放進(jìn)內(nèi)存時(shí)，前述的地址化方法就不再有效了，因?yàn)樵谕獯鏌o(wú)法保存事先算好的地址。

• 一般來(lái)講，外鍵指向的維表容量較小，而不斷增長(zhǎng)的事實(shí)表要大得多。如果內(nèi)存還能把維表放下的話(huà)，我們可以采用臨時(shí)指向的方法來(lái)處理外鍵。

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

外鍵序號(hào)化

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

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

• 維表主鍵是序號(hào)時(shí)就不需要再做原來(lái)建HASH索引的第2步了。

• 外鍵序號(hào)化本質(zhì)上相當(dāng)于在外存實(shí)現(xiàn)地址化。這種方案需要把事實(shí)表中的外鍵字段轉(zhuǎn)換成序號(hào)，這類(lèi)似在全內(nèi)存運(yùn)算時(shí)地址化的過(guò)程，這個(gè)預(yù)計(jì)算也可以得到復(fù)用。需要注意的是，維表發(fā)生重大變化時(shí)，需要同步整理事實(shí)表的外鍵字段，否則可能對(duì)應(yīng)錯(cuò)位。不過(guò)一般維表變化頻度低，而且大多數(shù)動(dòng)作是追加和修改而非刪除，需要重整事實(shí)表的情況并不多。工程上的細(xì)節(jié)處理也可以再參考乾學(xué)院中的資料。

• SQL使用了無(wú)序集合的概念，即使我們事先把外鍵序號(hào)化了，數(shù)據(jù)庫(kù)也無(wú)法利用這個(gè)特點(diǎn)，不能在無(wú)序集合上使用序號(hào)快速定位的機(jī)制，只能使用索引查找，而且數(shù)據(jù)庫(kù)并不知道外鍵被序號(hào)化了，仍然會(huì)去計(jì)算HASH值和比對(duì)。

• 如果維表也大到內(nèi)存裝不下呢？

• 我們仔細(xì)分析上面的算法會(huì)發(fā)現(xiàn)，過(guò)程中對(duì)于事實(shí)表的訪問(wèn)是連續(xù)的，但對(duì)于維表的訪問(wèn)則是隨機(jī)的。我們以前討論硬盤(pán)的性能特征時(shí)談到過(guò)，外存不適合隨機(jī)訪問(wèn)，所以外存中的維表不能再使用上述算法了。

• 外存中的維表可以事先按主鍵排序存儲(chǔ)，這樣我們就可以繼續(xù)利用維表關(guān)聯(lián)鍵是主鍵的特征來(lái)優(yōu)化性能。

• 如果事實(shí)表很小，可以在內(nèi)存裝放下，那么用外鍵去關(guān)聯(lián)維表記錄實(shí)際上會(huì)變成一個(gè)（批量）外存查找動(dòng)作。只要維表上針對(duì)主鍵建有索引，也可以很快地查找，這樣可以避免遍歷大維表，獲得更好的性能。這種算法也可以同時(shí)解析多個(gè)外鍵。SQL不區(qū)分維表和事實(shí)表，面對(duì)一大一小兩個(gè)表時(shí)，優(yōu)化過(guò)的HASH JOIN不會(huì)再做分堆緩存，通常會(huì)把小表讀入內(nèi)存而去遍歷大表，這樣仍然會(huì)有遍歷大維表的動(dòng)作，性能會(huì)比剛才說(shuō)的外存查找算法差得多。

• 如果事實(shí)表也很大，則可以使用單邊分堆的算法。因?yàn)榫S表已經(jīng)按關(guān)聯(lián)鍵（即主鍵）有序，可以方便地邏輯上分成若干段并取出每一段的邊界值（每一段主鍵的最大最小值），然后將事實(shí)表按這些邊界值做分堆，每一堆分別和維表的每一段再做關(guān)聯(lián)就可以了。過(guò)程中只需要對(duì)事實(shí)表單邊做物理分堆緩存，維表不需要再做物理分堆緩存，而且不使用HASH函數(shù)，直接用分段，不可能會(huì)出現(xiàn)HASH函數(shù)運(yùn)氣不好導(dǎo)致二次分堆，性能是可控的。而數(shù)據(jù)庫(kù)的HASH分堆算法會(huì)將兩個(gè)大表都做物理分堆緩存，也就是雙邊分堆，還可能出現(xiàn)HASH函數(shù)運(yùn)氣不好導(dǎo)致二次分堆的現(xiàn)象，性能要比單邊分堆差得多，還不可控。

借助集群的力量解決大維表問(wèn)題。

• 一臺(tái)機(jī)器的內(nèi)存裝不下，可以多搞幾臺(tái)機(jī)器來(lái)裝下，把維表按主鍵值分段存放在多臺(tái)機(jī)器上形成集群維表，然后就可以繼續(xù)使用上面針對(duì)內(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ù)雜，這里限于篇幅無(wú)法詳細(xì)解釋?zhuān)信d趣的讀者可以去乾學(xué)院的資料查閱。

有序歸并

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

• 我們前面討論過(guò)，HASH JOIN算法的計(jì)算復(fù)雜度（即關(guān)聯(lián)鍵的比較次數(shù)）是SUM(nimi)，比全遍歷的復(fù)雜度nm要小很多，不過(guò)要看HASH函數(shù)的運(yùn)氣。

• 如果這兩個(gè)表都對(duì)關(guān)聯(lián)鍵有序，那么我們就可以使用歸并算法來(lái)處理關(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í)針對(duì)多個(gè)字段都有序。

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

• 這還是利用了關(guān)聯(lián)鍵是主鍵（及其部分）的特征。

• 有序歸并對(duì)于大數(shù)據(jù)特別有效。像訂單及其明細(xì)這種主子表是不斷增長(zhǎng)的事實(shí)表，時(shí)間長(zhǎng)了常常會(huì)積累得非常大，很容易超出內(nèi)存容量。

• 外存大數(shù)據(jù)的HASH分堆算法需要產(chǎn)生很多緩存，數(shù)據(jù)在外存中被讀兩次寫(xiě)一次，IO開(kāi)銷(xiāo)很大。而歸并算法時(shí)，兩個(gè)表的數(shù)據(jù)都只要讀一次就行了，沒(méi)有寫(xiě)。不僅是CPU的計(jì)算量減少，外存的IO量也大幅下降。而且，執(zhí)行歸并算法需要的內(nèi)存很少，只要在內(nèi)存中為每個(gè)表保持?jǐn)?shù)條緩存記錄就可以了，幾乎不會(huì)影響其它并發(fā)任務(wù)對(duì)內(nèi)存的需求。而HASH分堆需要較大內(nèi)存，每次讀出更多數(shù)據(jù)，以減少分堆的次數(shù)。

• 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ù)效率。這些在乾學(xué)院上都有介紹。

分段并行

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

• 現(xiàn)代計(jì)算機(jī)的都有多核CPU，SSD硬盤(pán)也有較強(qiáng)的并發(fā)能力，使用多線(xiàn)程并行計(jì)算就能夠顯著提高性能。但傳統(tǒng)的HASH分堆技術(shù)實(shí)現(xiàn)并行比較困難，多線(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í)現(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ì)齊分段。

• 先把主表（同維表則取較大的即可，其它討論不影響）平均分成若干段，讀出每段第一條記錄的主鍵值，然后用這些鍵值到子表中用二分法尋找定位（因?yàn)橐灿行颍?，從而獲得子表的分段點(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í)行并行算法了。

• 主子表這種主鍵關(guān)聯(lián)的關(guān)系還有一個(gè)特征，就是子表只會(huì)和一個(gè)主表在主鍵上關(guān)聯(lián)（其實(shí)同維表也有，但用主子表容易解釋?zhuān)粫?huì)有多個(gè)相互無(wú)關(guān)的主表（可能有主表的主表）。這時(shí)候，還可以使用一體化存儲(chǔ)的機(jī)制，把子表記錄作為主表的字段值去存儲(chǔ)。這樣，一方面減少了存儲(chǔ)量（關(guān)聯(lián)鍵只要存儲(chǔ)一次），又相當(dāng)于預(yù)先做好了關(guān)聯(lián)，不需要再做比對(duì)了。對(duì)于大數(shù)據(jù)，就能獲得更好的性能。

關(guān)于“Mysql體系化之JOIN運(yùn)算實(shí)例分析”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“Mysql體系化之JOIN運(yùn)算實(shí)例分析”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。