Mysql體系化探討令人頭疼的JOIN運算

2022-07-14 18:03:31

前言

之前經歷過從零到一初創專案，也有海量資料專案；總體來說當專案在逐漸發展過程中如何構建一個安全可靠，穩定的資料儲存一直是專案中最核心、最重要、最關鍵部分，沒有之一
接下來我會體系化輸出儲存系列文章；本篇文章我們先談一下資料中一個最令人頭疼的連線運算—JOIN
JOIN 一直是SQL中的老大難問題。在關聯表稍多一點的時候，程式碼書寫就變得很容易出錯了且因為JOIN語句的複雜，導致關聯查詢也一向是BI軟體的軟肋，幾乎沒有BI軟體能讓業務使用者順暢地完成多表關聯查詢。對於效能優化也是，關聯表較多或者資料量大時，JOIN的效能也很難得到提升
基於以上，本文將對JOIN運算進行體系化深入的探討，根據自己工作經驗及參考業界經典案例，針對性地提出語法簡化和效能優化的方法論，希望對大家有所幫助

一圖總覽

SQL中的JOIN

SQL是如何理解JOIN運算

SQL對JOIN的定義

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

理論上講，笛卡爾積的結果集應該是以兩個集合成員構成的二元組作為成員，不過由於SQL中的集合也就是表，其成員總是有欄位的記錄，而且也不支援泛型資料型別來描述成員為記錄的二元組，所以就簡單地把結果集處理成兩表記錄的欄位合併後構成的新記錄的集合。
這也是JOIN一詞在英語中的原意（即把兩個記錄的欄位連線起來），並沒有乘法（笛卡爾積）的意思。不過，把笛卡爾積成員理解成二元組還是合併欄位的記錄，並不影響我們後續的討論。

JOIN定義

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

JOIN分類

我們把過濾條件為等式的稱為等值JOIN，而不是等值連線的情況則稱為非等值JOIN。這兩個例子中，前者是非等值JOIN，後者是等值JOIN。

等值JOIN

條件可能由多個有AND關係的等式構成，語法形式A JOIN B ON A.ai=B.bi AND …，其中ai和bi分別是A和B的欄位。
有經驗的程式設計師都知道，現實中絕大多數JOIN都是等值JOIN，非等值JOIN要少見得多，而且大多數情況都可以轉換成等值JOIN來處理，所以我們在這裡重點討論等值JOIN，並且後續討論中也主要使用表和記錄而不是集合和成員來舉例。

空值處理規則下分類

根據對空值的處理規則，嚴格的等值JOIN又稱為INNER JOIN，還可以再衍生出LEFT JOIN和FULL JOIN，共有三種情況（RIGHT JOIN可以理解為LEFT JOIN的反向關聯，不再單獨作為一種型別）。
談論JOIN時一般還會根據兩個表中關聯記錄（也就是滿足過濾條件的二元組）的數量分為一對一、一對多、多對一以及多對多這幾種情況，這些常規術語在SQL和資料庫資料中都有介紹，這裡就不再贅述了。

JOIN的實現

笨辦法

最容易想到的簡單辦法就是按照定義做硬遍歷，不區分等值JOIN和非等值JOIN。設表A有n條記錄，B有m條記錄，要計算A JOIN B ON A.a=B.b時，硬遍歷的複雜度會是nm，即要進行nm次過濾條件的計算。
顯然這種演演算法會比較慢。不過，支援多資料來源的報表工具中有時就是用這種慢辦法實現關聯的，因為在報表中資料集的關聯關係（也就是JOIN中的過濾條件）會拆散定義在單元格的運算式中，已經看不出是多個資料集之間的JOIN運算，也就只能用遍歷方法去計算這些關聯表示式了。

資料庫對於JOIN優化

對於等值JOIN，資料庫一般會採用HASH JOIN演演算法。即將關聯表的記錄按其關聯鍵（過濾條件中對應相等的欄位，即A.a和B.b)的HASH值分成若干組，將相同HASH值的記錄分到一組。如HASH值範圍是1…k，則將A和B表都分成k個子集A1,…,Ak和B1,…,Bk。Ai中記錄的關聯鍵a的HASH值是i，Bi中記錄的關聯鍵b的HASH值也是i，然後，只要分別在Ai和Bi之間做遍歷連線就可以了。
因為HASH不同時欄位值也必然不同，i!=j時，Ai中記錄不可能和Bj中記錄發生關聯。如果Ai的記錄數是ni，Bi的記錄數是mi，則過濾條件的計算次數為SUM(ni*mi)，最平均的情況時，ni=n/k，mi=m/k，則總的複雜度只有原始硬遍歷手段的1/k，能有效地提高運算效能！
所以，多資料來源關聯報表要提速的話，也需要在資料準備階段做好關聯，否則資料量稍大時效能就會急劇下降。
不過，HASH函數並不總能保證平均分拆，在運氣不好的時候可能會發生某一組特別大的情況，那樣效能提升效果就會差很多。而且還不能使用太複雜的HASH函數，否則計算HASH的時間又變多了。
當資料量大到超過記憶體時，資料庫會使用HASH分堆的方法，算是HASH JOIN演演算法的推廣。遍歷A表和B表，將記錄按關聯鍵的HASH值拆分成若干小子集快取到外存中，稱為分堆。然後再在對應的堆之間做記憶體JOIN運算。同樣的道理，HASH值不同時鍵值也必然不同，關聯一定發生在對應的堆之間。這樣就把巨量資料的JOIN轉換成若干小資料的JOIN了。
但是類似地，HASH函數存在運氣問題，有可能會發生某個分堆還特別大而無法裝入記憶體，這時候就可能要進行二次HASH分堆，即換一個HASH函數對這組太大的分堆再做一次HASH分堆演演算法。所以，外存JOIN運算有可能出現多次快取的現象，其運算效能有一定的不可控性。

分散式系統下JOIN

分散式系統下做JOIN也是類似的，根據關聯鍵的HASH值將記錄分發到各個節點機上，稱為Shuffle動作，然後再分別做單機的JOIN。
當節點比較多的時候，造成的網路傳輸量帶來的延遲會抵消多機分攤任務得到的好處，所以分散式資料庫系統通常有個節點數的極限，達到極限後，更多的節點並不能獲得更好的效能。

等值JOIN的剖析

三種等值JOIN：

外來鍵關聯

表A的某個欄位和表B的主鍵欄位關聯（所謂欄位關聯，就是前一節說過的在等值JOIN的過濾條件中要對應相等的欄位）。A表稱為事實表，B表稱為維表。A表中與B表主鍵關聯的欄位稱為A指向B的外來鍵，B也稱為A的外來鍵表。
這裡說的主鍵是指邏輯上的主鍵，也就是在表中取值唯一、可以用於唯一某條記錄的欄位（組），不一定在資料庫表上建立過主鍵。
外來鍵表是多對一的關係，且只有JOIN和LEFT JOIN，而FULL JOIN非常罕見。
典型案例：商品交易表和商品資訊表。
顯然，外來鍵關聯是不對稱的。事實表和維表的位置不能互換。

同維表

表A的主鍵與表B的主鍵關聯，A和B互稱為同維表。同維表是一對一的關係，JOIN、LEFT JOIN和FULL JOIN的情況都會有，不過在大多數資料結構設計方案中，FULL JOIN也相對少見。
典型案例：員工表和經理表。
同維表之間是對稱的，兩個表的地位相同。同維表還構成是等價關係，A和B是同維表，B和C是同維表，則A和C也是同維表。

主子表

表A的主鍵與表B的部分主鍵關聯，A稱為主表，B稱為子表。主子表是一對多的關係，只有JOIN和LEFT JOIN，不會有FULL JOIN。
典型案例：訂單和訂單明細。
主子表也是不對稱的，有明確的方向。
在SQL的概念體系中並不區分外來鍵表和主子表，多對一和一對多從SQL的觀點看來只是關聯方向不同，本質上是一回事。確實，訂單也可以理解成訂單明細的外來鍵表。但是，我們在這裡要把它們區分開，將來在簡化語法和效能優化時將使用不同的手段。
我們說，這三種JOIN已經涵蓋了絕大多數等值JOIN的情況，甚至可以說幾乎全部有業務意義的等值JOIN都屬於這三類，把等值JOIN限定在這三種情況之中，幾乎不會減少其適應範圍。
仔細考察這三種JOIN，我們發現所有關聯都涉及主鍵，沒有多對多的情況，是不是可以不考慮這種情況？
是的！多對多的等值JOIN幾乎沒有業務意義。
如果兩個表JOIN時的關聯欄位沒有涉及到任何主鍵，那就會發生多對多的情況，而這種情況幾乎一定還會有一個規模更大的表把這兩個表作為維表關聯起來。比如學生表和科目表在JOIN時，會有個成績表把學生表和科目表作為維表，單純只有學生表和科目表的JOIN沒有業務意義。
當寫SQL語句時發現多對多的情況，那大概率是這個語句寫錯了！或者資料有問題！這條法則用於排除JOIN錯誤很有效。
不過，我們一直在說“幾乎”，並沒有用完全肯定的說法，也就是說，多對多在非常罕見的情況下也會業務意義。可舉一例，用SQL實現矩陣乘法時會發生多對多的等值JOIN，具體寫法讀者可以自行補充。
笛卡爾積再過濾這種JOIN定義，確實非常簡單，而簡單的內涵將得到更大的外延，可以把多對多等值JOIN甚至非等值JOIN等都包括進來。但是，過於簡單的內涵無法充分體現出最常見等值JOIN的運算特徵。這會導致編寫程式碼和實現運算時就不能利用這些特徵，在運算較為複雜時（涉及關聯表較多以及有巢狀的情況），無論是書寫還是優化都非常困難。而充分利用這些特徵後，我們就能創造出更簡單的書寫形式並獲得更高效的運算效能，後面的內容中將會逐步加以說明。
與其為了把罕見情況也被包括進來而把運算定義為更通用的形式，還不如把這些情況定義成另一種運算更為合理。

JOIN的語法簡化

如何利用關聯都涉及主鍵這個特徵來簡化JOIN的程式碼書寫？

外來鍵屬性化

例子，設有如下兩個表：

employee 員工表
    id 員工編號
    name 姓名
    nationality 國籍
    department 所屬部門

department 部門表
    id 部門編號
    name 部門名稱
    manager 部門經理

employee表和department表的主鍵都是其中的id欄位，employee表的department欄位是指向department表的外來鍵，department表的manager欄位又是指向employee表的外來鍵（因為經理也是個員工）。這是很常規的表結構設計。
現在我們想問一下：哪些美國籍員工有一箇中國籍經理？用SQL寫出來是個三表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用於獲取員工資訊，然後這個employee表要和department做JOIN獲取員工的部門資訊，接著這個department表還要再和employee表JOIN要獲取經理的資訊，這樣employee表需要兩次參與JOIN，在SQL語句中要為它起個別名加以區分，整個句子就顯得比較複雜難懂。
如果我們把外來鍵欄位直接理解成它關聯的維表記錄，就可以換一種寫法：

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

當然，這不是標準的SQL語句了。

第二個句子中粗體部分表示當前員工的“所屬部門的經理的國籍”。我們把外來鍵欄位理解成維表的記錄後，維表的欄位被理解為外來鍵的屬性，department.manager即是“所屬部門的經理”，而這個欄位在department中仍然是個外來鍵，那麼它對應的維表記錄欄位可以繼續理解為它的屬性，也就會有department.manager.nationality，即“所屬部門的經理的國籍”。
外來鍵屬性化:這種物件式的理解方式即為外來鍵屬性化，顯然比笛卡爾積過濾的理解方式要自然直觀得多。外來鍵表JOIN時並不會涉及到兩個表的乘法，外來鍵欄位只是用於找到維鍵表中對應的那條記錄，完全不會涉及到笛卡爾積這種有乘法特性的運算。
我們前面約定，外來鍵關聯時時維表中關聯鍵必須是主鍵，這樣，事實表中每一條記錄的外來鍵欄位關聯的維表記錄就是唯一的，也就是說employee表中每一條記錄的department欄位唯一關聯一條department表中的記錄，而department表中每一條記錄的manager欄位也唯一關聯一條employee表中的記錄。這就保證了對於employee表中的每一條記錄，department.manager.nationality都有唯一的取值，可以被明確定義。
但是，SQL對JOIN的定義中並沒有主鍵的約定，如果基於SQL的規則，就不能認定與事實表中外來鍵關聯的維表記錄有唯一性，有可能發生與多條記錄關聯，對於employee表的記錄來講，department.manager.nationality沒有明確定義，就不能使用了。
事實上，這種物件式寫法在高階語言（如C，Java）中很常見，在這類語言中，資料就是按物件方式儲存的。employee表中的department欄位取值根本就是一個物件，而不是編號。其實許多表的主鍵取值本身並沒有業務意義，僅僅是為了區分記錄，而外來鍵欄位也僅僅是為了找到維表中的相應記錄，如果外來鍵欄位直接是物件，就不需要再通過編號來標識了。不過，SQL不能支援這種儲存機制，還要藉助編號。
我們說過外來鍵關聯是不對稱的，即事實表和維表是不對等的，只能基於事實表去找維表欄位，而不會有倒過來的情況。

同維表等同化

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

employee 員工表
    id 員工編號
    name 姓名
    salary 工資
    ...

manager 經理表
    id 員工編號
    allowance 崗位津貼
    ....

兩個表的主鍵都是id，經理也是員工，兩表共用同樣的員工編號，經理會比普通員工多一些屬性，另用一個經理表來儲存。
現在我們要統計所有員工（包括經理）的總收入（加上津貼）。用SQL寫出來還是會用到JOIN：

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

而對於兩個一對一的表，我們其實可以簡單地把它們看成一個表：

SELECT id,name,salary+allowance
FROM employee

類似地，根據我們的約定，同維表JOIN時兩個表都是按主鍵關聯的，相應記錄是唯一對應的，salary+allowance對employee表中每條記錄都是唯一可計算的，不會出現歧義。這種簡化方式稱為同維表等同化。
同維表之間的關係是對等的，從任何一個表都可以參照到其它同維表的欄位。

子表集合化

訂單&訂單明細是典型的主子表：

Orders 訂單表
    id 訂單編號
    customer 客戶
    date 日期
    ...
OrderDetail 訂單明細
    id 訂單編號
    no 序號
    product 訂購產品
    price 價格
    ...

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

現在我們想計算每張訂單的總金額。用SQL寫出來會是這樣：

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

要完成這個運算，不僅要用到JOIN，還需要做一次GROUP BY，否則選出來的記錄數太多。
如果我們把子表中與主表相關的記錄看成主表的一個欄位，那麼這個問題也可以不再使用JOIN以及GROUP BY：

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

與普通欄位不同，OrderDetail被看成Orders表的欄位時，其取值將是一個集合，因為兩個表是一對多的關係。所以要在這裡使用聚合運算把集合值計算成單值。這種簡化方式稱為子表集合化。
這樣看待主子表關聯，不僅理解書寫更為簡單，而且不容易出錯。
假如Orders表還有一個子表用於記錄回款情況：

OrderPayment 訂單回款表
    id 訂單編號
    date 回款日期
    amount 回款金額
    ....

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

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

如果我們繼續把子表看成主表的集合欄位，那就很簡單了：

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

這種寫法也不容易發生多對多的錯誤。
主子表關係是不對等的，不過兩個方向的參照都有意義，上面談了從主表參照子表的情況，從子表參照主表則和外來鍵表類似。
我們改變對JOIN運算的看法，摒棄笛卡爾積的思路，把多表關聯運算看成是稍複雜些的單表運算。這樣，相當於把最常見的等值JOIN運算的關聯消除了，甚至在語法中取消了JOIN關鍵字，書寫和理解都要簡單很多。

維度對齊語法

我們再回顧前面的雙子表例子的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

那麼問題來了，這顯然是個有業務意義的JOIN，它算是前面所說的哪一類呢？
這個JOIN涉及了表Orders和子查詢A與B，仔細觀察會發現，子查詢帶有GROUP BY id的子句，顯然，其結果集將以id為主鍵。這樣，JOIN涉及的三個表（子查詢也算作是個臨時表）的主鍵是相同的，它們是一對一的同維表，仍然在前述的範圍內。
但是，這個同維表JOIN卻不能用前面說的寫法簡化，子查詢A,B都不能省略不寫。
可以簡化書寫的原因：我們假定事先知道資料結構中這些表之間的關聯關係。用技術術語的說法，就是知道資料庫的後設資料（metadata）。而對於臨時產生的子查詢，顯然不可能事先定義在後設資料中了，這時候就必須明確指定要JOIN的表（子查詢）。
不過，雖然JOIN的表（子查詢）不能省略，但關聯欄位總是主鍵。子查詢的主鍵總是由GROUP BY產生，而GROUP BY的欄位一定要被選出用於做外層JOIN；並且這幾個子查詢涉及的子表是互相獨立的，它們之間不會再有關聯計算了，我們就可以把GROUP動作以及聚合式直接放到主句中，從而消除一層子查詢：

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運算已經差別很大，完全沒有笛卡爾積的意思了。而且，也不同於SQL的JOIN運算將定義在任何兩個表之間，這裡的JOIN，OrderDetail和OrderPayment以及Orders都是向一個共同的主鍵id對齊，即所有表都向某一套基準維度對齊。而由於各表的維度（主鍵）不同，對齊時可能會有GROUP BY，在參照該表欄位時就會相應地出現聚合運算。OrderDetail和OrderPayment甚至Orders之間都不直接發生關聯，在書寫運算時當然就不用關心它們之間的關係，甚至不必關心另一個表是否存在。而SQL那種笛卡爾積式的JOIN則總要找一個甚至多個表來定義關聯，一旦減少或修改表時就要同時考慮關聯表，增大理解難度。
維度對齊：這種JOIN稱即為維度對齊，它並不超出我們前面說過的三種JOIN範圍，但確實在語法描述上會有不同，這裡的JOIN不象SQL中是個動詞，卻更象個連詞。而且，和前面三種基本JOIN中不會或很少發生FULL JOIN的情況不同，維度對齊的場景下FULL JOIN並不是很罕見的情況。
雖然我們從主子表的例子抽象出維度對齊，但這種JOIN並不要求JOIN的表是主子表（事實上從前面的語法可知，主子表運算還不用寫這麼麻煩），任何多個表都可以這麼關聯，而且關聯欄位也完全不必要是主鍵或主鍵的部分。
設有合同表，回款表和發票表：

Contract 合同表
    id 合同編號
    date 簽訂日期
    customer 客戶
    price 合同金額
    ...

Payment 回款表
    seq 回款序號
    date 回款日期
    source 回款來源
    amount 金額
    ...

Invoice 發票表
    code 發票編號
    date 開票日期
    customer 客戶
    amount 開票金額
    ...

現在想統計每一天的合同額、回款額以及發票額，就可以寫成：

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後單獨列出來表示結果集按日期對齊。
這種寫法，不必關心這三個表之間的關聯關係，各自寫各自有關的部分就行，似乎這幾個表就沒有關聯關係，把它們連到一起的就是那個要共同對齊的維度（這裡是date）。
這幾種JOIN情況還可能混合出現。
繼續舉例，延用上面的合同表，再有客戶表和銷售員表

Customer 客戶表
    id 客戶編號
    name 客戶名稱
    area 所在地區
    ...

Sales 銷售員表
    id 員工編號
    name 姓名
    area 負責地區
    ...

其中Contract表中customer欄位是指向Customer表的外來鍵。
現在我們想統計每個地區的銷售員數量及合同額：

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

維度對齊可以和外來鍵屬性化的寫法配合合作。
這些例子中，最終的JOIN都是同維表。事實上，維度對齊還有主子表對齊的情況，不過相對罕見，我們這裡就不深入討論了。
另外，目前這些簡化語法仍然是示意性，需要在嚴格定義維度概念之後才能相應地形式化，成為可以解釋執行的句子。
我們把這種簡化的語法稱為DQL（Dimensional Query Languange），DQL是以維度為核心的查詢語言。我們已經將DQL在工程上做了實現，並作為潤乾報表的DQL伺服器釋出出來，它能將DQL語句翻譯成SQL語句執行，也就是可以在任何關聯式資料庫上執行。
對DQL理論和應用感興趣的讀者可以關注乾學院上釋出的論文和相關文章。

解決關聯查詢

多表JOIN問題

我們知道，SQL允許用WHERE來寫JOIN運算的過濾條件（回顧原始的笛卡爾積式的定義），很多程式設計師也習慣於這麼寫。
當JOIN表只有兩三個的時候，那問題還不大，但如果JOIN表有七八個甚至十幾個的時候，漏寫一個JOIN條件是很有可能的。而漏寫了JOIN條件意味著將發生多對多的完全叉乘，而這個SQL卻可以正常執行，會有以下兩點危害：
- 一方面計算結果會出錯:回憶一下以前說過的，發生多對多JOIN時，大概率是語句寫錯了
- 另一方面，如果漏寫條件的表很大，笛卡爾積的規模將是平方級的，這極有可能把資料庫直接“跑死”！

簡化JOIN運算好處：

一個直接的效果顯然是讓語句書寫和理解更容易
外來鍵屬性化、同維表等同化和子表集合化方案直接消除了顯式的關聯運算，也更符合自然思維
維度對齊則可讓程式設計師不再關心表間關係，降低語句的複雜度
簡化JOIN語法的好處不僅在於此，還能夠降低出錯率，採用簡化後的JOIN語法，就不可能發生漏寫JOIN條件的情況了。因為對JOIN的理解不再是以笛卡爾積為基礎，而且設計這些語法時已經假定了多對多關聯沒有業務意義，這個規則下寫不出完全叉乘的運算。
對於多個子表分組後與主表對齊的運算，在SQL中要寫成多個子查詢的形式。但如果只有一個子表時，可以先JOIN再GROUP，這時不需要子查詢。有些程式設計師沒有仔細分析，會把這種寫法推廣到多個子表的情況，也先JOIN再GROUP，可以避免使用子查詢，但計算結果是錯誤的。
使用維度對齊的寫法就不容易發生這種錯誤了，無論多少個子表，都不需要子查詢，一個子表和多個子表的寫法完全相同。

關聯查詢

重新看待JOIN運算，最關鍵的作用在於實現關聯查詢。
當前BI產品是個熱門，各家產品都宣稱能夠讓業務人員拖拖拽拽就完成想要的查詢報表。但實際應用效果會遠不如人意，業務人員仍然要經常求助於IT部門。造成這個現象的主要原因在於大多數業務查詢都是有過程的計算，本來也不可能拖拽完成。但是，也有一部分業務查詢並不涉及多步過程，而業務人員仍然難以完成。
這就是關聯查詢，也是大多數BI產品的軟肋。在之前的文章中已經講過為什麼關聯查詢很難做，其根本原因就在於SQL對JOIN的定義過於簡單。
結果，BI產品的工作模式就變成先由技術人員構建模型，再由業務人員基於模型進行查詢。而所謂建模，就是生成一個邏輯上或物理上的寬表。也就是說，建模要針對不同的關聯需求分別實現，我們稱之為按需建模，這時候的BI也就失去敏捷性了。
但是，如果我們改變了對JOIN運算的看法，關聯查詢可以從根本上得到解決。回憶前面講過的三種JOIN及其簡化手段，我們事實上把這幾種情況的多表關聯都轉化成了單表查詢，而業務使用者對於單表查詢並沒有理解障礙。無非就是表的屬性（欄位）稍複雜了一些：可能有子屬性（外來鍵欄位指向的維表並參照其欄位），子屬性可能還有子屬性（多層的維表），有些欄位取值是集合而非單值（子表看作為主表的欄位）。發生互相關聯甚至自我關聯也不會影響理解（前面的中國經理的美國員工例子就是互關聯），同表有相同維度當然更不礙事（各自有各自的子屬性）。
在這種關聯機制下，技術人員只要一次性把資料結構（後設資料）定義好，在合適的介面下（把表的欄位列成有層次的樹狀而不是常規的線狀），就可以由業務人員自己實現JOIN運算，不再需要技術人員的參與。資料建模只發生於資料結構改變的時刻，而不需要為新的關聯需求建模，這也就是非按需建模，在這種機制支援下的BI才能擁有足夠的敏捷性。

外來鍵預關聯

我們再來研究如何利用JOIN的特徵實現效能優化，這些內容的細節較多，我們挑一些易於理解的情況來舉例，更完善的連線提速演演算法可以參考乾學院上的《效能優化》圖書和SPL學習資料中的效能優化專題文章。

全記憶體下外來鍵關聯情況

設有兩個表：

customer 客戶資訊表
    key 編號
    name 名稱
    city 城市
    ...

orders 訂單表
    seq 序號
    date 日期
    custkey 客戶編號
    amount 金額
    ...

其中orders表中的custkey是指向customer表中key欄位的外來鍵，key是customer表的主鍵。
現在我們各個城市的訂單總額（為簡化討論，就不再設定條件了），用SQL寫出來：

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

資料庫一般會使用HASH JOIN演演算法，需要分別兩個表中關聯鍵的HASH值並比對。
我們用前述的簡化的JOIN語法（DQL）寫出這個運算：

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

這個寫法其實也就預示了它還可以有更好的優化方案，下面來看看怎樣實現。
如果所有資料都能夠裝入記憶體，我們可以實現外來鍵地址化。
將事實表orders中的外來鍵欄位custkey，轉換成維表customer中關聯記錄的地址，即orders表的custkey的取值已經是某個customer表中的記錄，那麼就可以直接參照記錄的欄位進行計算了。
用SQL無法描述這個運算的細節過程，我們使用SPL來描述、並用檔案作為資料來源來說明計算過程：

	A
1	=file(“customer.btx”).import@b()
2	>A1.keys@i(key)
3	=file(“orders.btx”).import@b()
4	>A3.switch(custkey,A1)
5	=A3.groups(custkey.city;sum(amount))

A1讀出客戶表，A2為客戶表設定主鍵並建立索引。
A3讀出訂單表，A4的動作是將A3的外來鍵欄位custkey轉換成對應的A1的記錄，執行完後，訂單表欄位custkey將變成客戶表的某條記錄。A2建了索引能讓switch更快，因為通常事實表遠大於維表，這個索引能被複用很多次。
A5就可以執行分組彙總了，遍歷訂單表時，由於custkey欄位取值現在已經是一條記錄，那麼可以直接用.操作符參照其欄位了，custkey.city就可以正常執行。
完成A4中的switch動作之後，記憶體中事實表A3的custkey欄位儲存內容已經是維表A1的某條記錄的地址，這個動作即稱為外來鍵地址化。這時候參照維表欄位時，可以直接取出，而不需要再用外來鍵值在A1中查詢，相當於在常數時間內就能取到維表的欄位，避免了HASH值計算和比對。
不過，A2建主鍵索引一般也會用HASH辦法，對key計算HASH值，A4轉換地址時也是計算custkey的HASH值與A2的HASH索引表對比。如果只做一次關聯運算，地址化的方案和傳統HASH分段方案的計算量基本上一樣，沒有根本優勢。
但不同的是，如果資料能在記憶體中放下，這個地址一旦轉換之後可以複用，也就是說A1到A4只要做一次，下次再做關於這兩個欄位的關聯運算時就不必再計算HASH值和比對了，效能就能大幅提高。
能夠這樣做，正是利用了前面說過的外來鍵關聯在維表這一方具有的唯一性，一個外來鍵欄位值只會唯一對應一條維表記錄，可以把每個custkey轉換成它唯一對應的那條A1的記錄。而延用SQL中對JOIN的定義，就不能假定外來鍵指向記錄的唯一性，無法使用這種表示法。而且SQL也沒有記錄地址這種資料型別，結果會導致每次關聯時都要計算HASH值並比對。
而且，如果事實表中有多個外來鍵分別指向多個維表，傳統的HASH分段JOIN方案每次只能解析掉一個，有多個JOIN要執行多遍動作，每次關聯後都需要保持中間結果供下一輪使用，計算過程複雜得多，資料也會被遍歷多次。而外來鍵地址化方案在面對多個外來鍵時，只要對事實表遍歷一次，沒有中間結果，計算過程要清晰很多。
還有一點，記憶體本來是很適合平行計算的，但HASH分段JOIN演演算法卻不容易並行。即使把資料分段平行計算HASH值，但要把相同HASH值的記錄歸聚到一起供下一輪比對，還會發生共用資源搶佔的事情，這將犧牲很多平行計算的優勢。而外來鍵式JOIN模型下，關聯兩表的地位不對等，明確區分出維表和事實表後，只要簡單地將事實表分段就可以平行計算。
將HASH分段技術參照外來鍵屬性方案進行改造後，也能一定程度地改善多外來鍵一次解析和並行能力，有些資料庫能在工程層面上實施這種優化。不過，這種優化在只有兩個表JOIN時問題不大，在有很多表及各種JOIN混在一起時，資料庫並不容易識別出應當把哪個表當作事實表去並行遍歷、而把其它表當作維表建立HASH索引，這時優化並不總是有效的。所以我們經常會發現當JOIN的表變多時效能會急劇下降的現象（常常到四五個表時就會發生，結果集並無顯著增大）。而從JOIN模型上引入外來鍵概念後，將這種JOIN專門處理時，就總能分清事實表和維表，更多的JOIN表只會導致效能的線性下降。
記憶體資料庫是當前比較火熱的技術，但上述分析表明，採用SQL模型的記憶體資料庫在JOIN運算上是很難快起來的！

進一步的外來鍵關聯

我們繼續討論外來鍵JOIN，並延用上一節的例子。
當資料量大到無法全部放進記憶體時，前述的地址化方法就不再有效了，因為在外存無法儲存事先算好的地址。
一般來講，外來鍵指向的維表容量較小，而不斷增長的事實表要大得多。如果記憶體還能把維表放下的話，我們可以採用臨時指向的方法來處理外來鍵。

	A
1	=file(“customer.btx”).import@b()
2	=file(“orders.btx”).cursor@b()
3	>A2.switch(custkey,A1:#)
4	=A2.groups(custkey.city;sum(amount))

前兩步與全記憶體時相同，第4步的地址轉換是邊讀入邊進行的，而且轉換結果無法保留複用，下次再做關聯時還要再計算HASH和比對，效能要比全記憶體的方案差。計算量方面，比HASH JOIN演演算法少了一次維表的HASH值計算，這個維表如果經常被複用時會佔些便宜，但因為維表相對較小，總體優勢並不算大。不過，這個演演算法同樣具有全記憶體演演算法可以一次解析全部外來鍵以及易於並行的特點，在實際場景下比HASH JOIN演演算法仍有較大的效能優勢。

外來鍵序號化

在這個演演算法基礎上，我們還可以做個變種：外來鍵序號化。

如果我們能把維表的主鍵都轉換成從1開始的自然數，那麼我們就可以用序號直接定位維表記錄，就不需要計算和比對HASH值，這樣就可以獲得類似全記憶體下地址化的效能了。

	A
1	=file(“customer.btx”).import@b()
2	=file(“orders.btx”).cursor@b()
3	>A2.switch(custkey,A1:#)
4	=A2.groups(custkey.city;sum(amount))

維表主鍵是序號時就不需要再做原來建HASH索引的第2步了。
外來鍵序號化本質上相當於在外存實現地址化。這種方案需要把事實表中的外來鍵欄位轉換成序號，這類似在全記憶體運算時地址化的過程，這個預計算也可以得到複用。需要注意的是，維表發生重大變化時，需要同步整理事實表的外來鍵欄位，否則可能對應錯位。不過一般維表變化頻度低，而且大多數動作是追加和修改而非刪除，需要重整事實表的情況並不多。工程上的細節處理也可以再參考乾學院中的資料。
SQL使用了無序集合的概念，即使我們事先把外來鍵序號化了，資料庫也無法利用這個特點，不能在無序集合上使用序號快速定位的機制，只能使用索引查詢，而且資料庫並不知道外來鍵被序號化了，仍然會去計算HASH值和比對。
如果維表也大到記憶體裝不下呢？
我們仔細分析上面的演演算法會發現，過程中對於事實表的存取是連續的，但對於維表的存取則是隨機的。我們以前討論硬碟的效能特徵時談到過，外存不適合隨機存取，所以外存中的維表不能再使用上述演演算法了。
外存中的維表可以事先按主鍵排序儲存，這樣我們就可以繼續利用維表關聯鍵是主鍵的特徵來優化效能。
如果事實表很小，可以在記憶體裝放下，那麼用外來鍵去關聯維表記錄實際上會變成一個（批次）外存查詢動作。只要維表上針對主鍵建有索引，也可以很快地查詢，這樣可以避免遍歷大維表，獲得更好的效能。這種演演算法也可以同時解析多個外來鍵。SQL不區分維表和事實表，面對一大一小兩個表時，優化過的HASH JOIN不會再做分堆快取，通常會把小表讀入記憶體而去遍歷大表，這樣仍然會有遍歷大維表的動作，效能會比剛才說的外存查詢演演算法差得多。
如果事實表也很大，則可以使用單邊分堆的演演算法。因為維表已經按關聯鍵（即主鍵）有序，可以方便地邏輯上分成若干段並取出每一段的邊界值（每一段主鍵的最大最小值），然後將事實表按這些邊界值做分堆，每一堆分別和維表的每一段再做關聯就可以了。過程中只需要對事實表單邊做物理分堆快取，維表不需要再做物理分堆快取，而且不使用HASH函數，直接用分段，不可能會出現HASH函數運氣不好導致二次分堆，效能是可控的。而資料庫的HASH分堆演演算法會將兩個大表都做物理分堆快取，也就是雙邊分堆，還可能出現HASH函數運氣不好導致二次分堆的現象，效能要比單邊分堆差得多，還不可控。

藉助叢集的力量解決大維表問題。

一臺機器的記憶體裝不下，可以多搞幾臺機器來裝下，把維表按主鍵值分段存放在多臺機器上形成叢集維表，然後就可以繼續使用上面針對記憶體維表的演演算法了，也能獲得一次解析多個外來鍵和易於並行的好處。同樣地，叢集維表也可以使用序號化的技術。這種演演算法下，事實表不需要被傳輸，產生的網路傳輸量並不大，也不需要節點本地快取資料。而SQL體系下不能區分出維表，HASH拆分方法要將兩個表都做Shuffle動作，網路傳播量要大得多。
這些演演算法的細節仍有些複雜，這裡限於篇幅無法詳細解釋，有興趣的讀者可以去乾學院的資料查閱。

有序歸併

同維表&主子表的JOIN優化提速手段

我們前面討論過，HASH JOIN演演算法的計算複雜度（即關聯鍵的比較次數）是SUM(nimi)，比全遍歷的複雜度nm要小很多，不過要看HASH函數的運氣。
如果這兩個表都對關聯鍵有序，那麼我們就可以使用歸併演演算法來處理關聯，這時的複雜度是n+m；在n和m都較大的時候（一般都會遠大於HASH函數的取值範圍），這個數也會遠小於HASH JOIN演演算法的複雜度。歸併演演算法的細節有很多材料介紹，這裡就不再贅述了。
但是，外來鍵JOIN時不能使用這個辦法，因為事實表上可能有多個要參與關聯的外來鍵欄位，不可能讓同一個事實表同時針對多個欄位都有序。
同維表和主子表卻可以！因為同維表和主子表總是針對主鍵或主鍵的一部分關聯，我們可以事先把這些關聯表的資料按其主鍵排序。排序的成本雖然較高，但是一次性的。一旦完成了排序，以後就可以總是使用歸併演演算法實現JOIN，效能可以提高很多。
這還是利用了關聯鍵是主鍵（及其部分）的特徵。
有序歸併對於巨量資料特別有效。像訂單及其明細這種主子表是不斷增長的事實表，時間長了常常會積累得非常大，很容易超出記憶體容量。
外存巨量資料的HASH分堆演演算法需要產生很多快取，資料在外存中被讀兩次寫一次，IO開銷很大。而歸併演演算法時，兩個表的資料都只要讀一次就行了，沒有寫。不僅是CPU的計算量減少，外存的IO量也大幅下降。而且，執行歸併演演算法需要的記憶體很少，只要在記憶體中為每個表保持數條快取記錄就可以了，幾乎不會影響其它並行任務對記憶體的需求。而HASH分堆需要較大記憶體，每次讀出更多資料，以減少分堆的次數。
SQL採用笛卡爾積定義的JOIN運算不區分JOIN型別，不假定某些JOIN總是針對主鍵的，就沒辦法從演演算法層面上利用這一特點，只能在工程層面進行優化。有些資料庫會檢查資料表在物理儲存上是否針對關聯欄位有序，如果有序則採用歸併演演算法，但基於無序集合概念的關聯式資料庫不會刻意保證資料的物理有序性，許多操作都會破壞歸併演演算法的實施條件。使用索引可以實現資料的邏輯有序，但物理無序時的遍歷效率還是會大打折扣。
有序歸併的前提是將資料按主鍵排序，而這類資料常常會不斷追加，原則上每次追加後就要再次排序，而我們知道巨量資料排序成本通常很高，這是否會導致追加資料難度很大呢？其實，追加資料再加入的過程也是個有序歸併，把新增資料單獨排序後和已有序的歷史資料歸併，複雜度是線性的，相當於把所有資料重寫一次，而不像常規的巨量資料排序需要快取式寫出再讀入。在工程上做些優化動作還可以做到不必每次都全部重寫，進一步提高維護效率。這些在乾學院上都有介紹。

分段並行

有序歸併的好處還在於易於分段並行。
現代計算機的都有多核CPU，SSD硬碟也有較強的並行能力，使用多執行緒平行計算就能夠顯著提高效能。但傳統的HASH分堆技術實現並行比較困難，多執行緒做HASH分堆時需要同時向某個分堆寫出資料，造成共用資源衝突；而第二步實現某組分堆關聯時又會消費大量記憶體，無法讓實施較大的並行數量。
使用有序歸併實現平行計算時需要把資料分成多段，單個表分段比較簡單，但兩個關聯表分段時必須同步對齊，否則歸併時兩個表資料錯位了，就無法得出正確的計算結果，而資料有序就可以保證高效能的同步對齊分段。
先把主表（同維表則取較大的即可，其它討論不影響）平均分成若干段，讀出每段第一條記錄的主鍵值，然後用這些鍵值到子表中用二分法尋找定位（因為也有序），從而獲得子表的分段點。這樣可以保證主子表的分段是同步對齊的。
因為鍵值有序，所以主表每段的記錄鍵值都屬於某個連續區間，鍵值在區間外的記錄不會在這一段，鍵值在區間內的記錄一定在這一段，子表對應分段的記錄鍵值也有這個特性，所以不會發生錯位情況；而同樣因為鍵值有序，才可以在子表中執行高效的二分查詢迅速定位出分段點。即資料有序保證了分段的合理性及高效性，這樣就可以放心地執行並行演演算法了。
主子表這種主鍵關聯的關係還有一個特徵，就是子表只會和一個主表在主鍵上關聯（其實同維表也有，但用主子表容易解釋），它不會有多個相互無關的主表（可能有主表的主表）。這時候，還可以使用一體化儲存的機制，把子表記錄作為主表的欄位值去儲存。這樣，一方面減少了儲存量（關聯鍵只要儲存一次），又相當於預先做好了關聯，不需要再做比對了。對於巨量資料，就能獲得更好的效能。
我們已經將上述這些效能優化手段在集算器SPL中實現並在實際場景用得到了應用，也取得了非常好的效果。SPL目前已經開源，讀者可以去數速公司或潤乾公司官網及論壇下載並獲得更多資料。