溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了Mysql體系化之JOIN運算實例分析的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Mysql體系化之JOIN運算實例分析文章都會有所收獲，下面我們一起來看看吧。
SQL是如何理解JOIN運算
兩個集合（表）做笛卡爾積后再按某種條件過濾，寫出來的語法就是A JOIN B ON …。
理論上講，笛卡爾積的結果集應該是以兩個集合成員構成的二元組作為成員，不過由于SQL中的集合也就是表，其成員總是有字段的記錄，而且也不支持泛型數據類型來描述成員為記錄的二元組，所以就簡單地把結果集處理成兩表記錄的字段合并后構成的新記錄的集合。
這也是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。
條件可能由多個有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。設表A有n條記錄，B有m條記錄，要計算A JOIN B ON A.a=B.b時，硬遍歷的復雜度會是nm，即要進行nm次過濾條件的計算。
顯然這種算法會比較慢。不過，支持多數據源的報表工具中有時就是用這種慢辦法實現關聯的，因為在報表中數據集的關聯關系（也就是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也是類似的，根據關聯鍵的HASH值將記錄分發到各個節點機上，稱為Shuffle動作，然后再分別做單機的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的代碼書寫？
例子，設有如下兩個表：
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理論和應用感興趣的讀者可以關注乾學院上發布的論文和相關文章。
我們知道，SQL允許用WHERE來寫JOIN運算的過濾條件（回顧原始的笛卡爾積式的定義），很多程序員也習慣于這么寫。
當JOIN表只有兩三個的時候，那問題還不大，但如果JOIN表有七八個甚至十幾個的時候，漏寫一個JOIN條件是很有可能的。而漏寫了JOIN條件意味著將發生多對多的完全叉乘，而這個SQL卻可以正常執行，會有以下兩點危害：
一方面計算結果會出錯:回憶一下以前說過的，發生多對多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動作，網絡傳播量要大得多。
這些算法的細節仍有些復雜，這里限于篇幅無法詳細解釋，有興趣的讀者可以去乾學院的資料查閱。
我們前面討論過，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分堆時需要同時向某個分堆寫出數據，造成共享資源沖突；而第二步實現某組分堆關聯時又會消費大量內存，無法讓實施較大的并行數量。
使用有序歸并實現并行計算時需要把數據分成多段，單個表分段比較簡單，但兩個關聯表分段時必須同步對齊，否則歸并時兩個表數據錯位了，就無法得出正確的計算結果，而數據有序就可以保證高性能的同步對齊分段。
先把主表（同維表則取較大的即可，其它討論不影響）平均分成若干段，讀出每段第一條記錄的主鍵值，然后用這些鍵值到子表中用二分法尋找定位（因為也有序），從而獲得子表的分段點。這樣可以保證主子表的分段是同步對齊的。
因為鍵值有序，所以主表每段的記錄鍵值都屬于某個連續區間，鍵值在區間外的記錄不會在這一段，鍵值在區間內的記錄一定在這一段，子表對應分段的記錄鍵值也有這個特性，所以不會發生錯位情況；而同樣因為鍵值有序，才可以在子表中執行高效的二分查找迅速定位出分段點。即數據有序保證了分段的合理性及高效性，這樣就可以放心地執行并行算法了。
主子表這種主鍵關聯的關系還有一個特征，就是子表只會和一個主表在主鍵上關聯（其實同維表也有，但用主子表容易解釋），它不會有多個相互無關的主表（可能有主表的主表）。這時候，還可以使用一體化存儲的機制，把子表記錄作為主表的字段值去存儲。這樣，一方面減少了存儲量（關聯鍵只要存儲一次），又相當于預先做好了關聯，不需要再做比對了。對于大數據，就能獲得更好的性能。
關于“Mysql體系化之JOIN運算實例分析”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Mysql體系化之JOIN運算實例分析”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
