Mysql體系化解析之JOIN運算

本篇文章為大家帶來了關於mysql的相關知識，主要介紹了體系化探討令人頭疼的JOIN運算,本文將對JOIN運算進行體系化深入的探討，根據自己工作經驗及參考業界經典案例，針對性地提出語法簡化和效能優化的方法論，希望對大家有幫助。

推薦學習：mysql影片教學

#前言

• 之前經歷過從零到一新創項目，也有大量資料項目；整體來說當專案在逐漸發展過程中如何建構一個安全可靠，穩定的資料儲存一直是專案中最核心、最重要、最關鍵部分，沒有之一
• 接下來我會體系化輸出儲存系列文章；這篇文章我們先談談資料中一個最令人頭痛的連線運算—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

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目前已經開源，讀者可以去數速公司或潤乾公司官網及論壇下載並取得更多資料。

推薦學習：mysql影片教學

#

以上是Mysql體系化解析之JOIN運算的詳細內容。更多資訊請關注PHP中文網其他相關文章！