01. 前言

寫過或者學過 SQL 的人應該都知道 left join，知道 left join 的實現的效果，就是保留左表的全部信息，然后把右表往左表上拼接，如果拼不上就是 null。除了 left join 以外，還有 inner join、outer join、right join，這些不同的 join 能達到的什么樣的效果，大家應該都了解了，如果不了解的可以看看網上的帖子或者隨便一本 SQL 書都有講的。今天我們不講這些 join 能達到什么效果，我們主要講這些 join 的底層原理是怎么實現的，也就是具體的效果是怎么呈現出來的。

join 主要有 Nested Loop、Hash Join、Merge Join 這三種方式，我們這里只講最普遍的，也是最好的理解的 Nested Loop，Nested Loop 翻譯過來就是嵌套循環的意思，那什么又是嵌套循環呢？嵌套大家應該都能理解，就是一層套一層；那循環呢，你可以理解成是 for 循環。

Nested Loop 里面又有三種細分的連接方式，分別是 Simple Nested-Loop Join、Index Nested-Loop Join、Block Nested-Loop Join，接下來我們就分別去看一下這三種細分的連接方式。

在正式開始之前，先介紹兩個概念：驅動表（也叫外表）和被驅動表（也叫非驅動表，還可以叫匹配表，亦可叫內表），簡單來說，驅動表就是主表，left join 中的左表就是驅動表，right join 中的右表是驅動表。一個是驅動表，那另一個就只能是非驅動表了，在 join 的過程中，其實就是從驅動表里面依次（注意理解這里面的依次）取出每一個值，然后去非驅動表里面進行匹配，那具體是怎么匹配的呢？這就是我們接下來講的這三種連接方式。

02.Simple Nested-Loop Join

Simple Nested-Loop Join 是這三種方法里面最簡單，最好理解，也是最符合大家認知的一種連接方式，現在有兩張表 table A 和 table B，我們讓 table A left join table B，如果是用第一種連接方式去實現的話，會是怎么去匹配的呢？直接上圖：

上面的 left join 會從驅動表 table A 中依次取出每一個值，然后去非驅動表 table B 中從上往下依次匹配，然后把匹配到的值進行返回，最后把所有返回值進行合并，這樣我們就查找到了 table A left join table B 的結果。是不是和你的認知是一樣的呢？利用這種方法，如果 table A 有10行，table B 有10行，總共需要執行 10 x 10 = 100 次查詢。

這種暴力匹配的方式在數據庫中一般不使用。

---

03.Index Nested-Loop Join

Index Nested-Loop Join 這種方法中，我們看到了 Index，大家應該都知道這個就是索引的意思，這個 Index 是要求非驅動表上要有索引，有了索引以后可以減少匹配次數，匹配次數減少了就可以提高查詢的效率了。

為什么會有了索引以后可以減少查詢的次數呢？這個其實就涉及到數據結構里面的一些知識了，給大家舉個例子就清楚了。

上圖中左邊就是普通列的存儲方式，右邊是樹結構索引，什么是樹結構呢？就是數據分布的像樹這樣一層一層的，樹結構有一個特點就是左邊的數據小于頂點的數，右邊的數大于頂點的數，你看右圖中，左邊的數3是不是小于頂點6，右邊的數7是不是大于頂點6；左邊的數1是不是小于頂點3，右邊的數4是不是大于頂點3。

假如我們現在要匹配數值9，如果是左邊這種數據存儲方式的話，我們需要從第一行依次匹配到最后一行才能找到數值9，總共需要匹配7次；但是如果我們是用右邊這種樹結構索引的話，我們先拿9和最上層頂點6去匹配，發現9比6大，我們就去頂點的右邊去找，再去和7匹配，發現9仍然比7大，再去7的右邊找，就找到了9，這樣我們只匹配了3次就把我們想要的9找到了。是不是相比匹配7次節省了很多時間。

數據庫中的索引一般用 B+ 樹，為了讓大家更好的理解，我上面畫的圖只是最簡單的一種樹結構，而非真實的 B+ 樹，但是原理是一樣的。

如果索引是主鍵的話，效率會更高，因為主鍵必須是唯一的，所以如果被驅動表是用主鍵去連接，只會出現多對一或者一對一的情況，而不會出現多對多和一對多的情況。

04.Block Nested-Loop Join

理想情況下，用索引匹配是最高效的一種方式，但是在現實工作中，并不是所有的列都是索引列，這個時候就需要用到 Block Nested-Loop Join 方法了，這種方法與第一種方法比較類似，唯一的區別就是會把驅動表中 left join 涉及到的所有列（不止是用來on的列，還有select部分的列）先取出來放到一個緩存區域，然后再去和非驅動表進行匹配，這種方法和第一種方法相比所需要的匹配次數是一樣的，差別就在于驅動表的列數不同，也就是數據量的多少不同。所以雖然匹配次數沒有減少，但是總體的查詢性能還是有提升的。

Join操作是一種常見的數據庫操作，通過Join可以將多個表關聯起來，根據用戶的條件共同提供數據。一般情況，在數據庫中都會內置多種Join算法，優化器在優化的時候會根據SQL語句和表的統計信息選擇合適的算法。

Hash Join

在執行Hash Join時，1. 會根據Join條件將一張表進行Hash運算加載到內存中的一張Hash表中。Hash表類似與Java中的HashTable；2.遍歷另外一張表，進行Hash運算后在內存中查找滿足條件的記錄。

select * from t1 join t2 on t1.a = t2.b；在執行這個SQL的時候，先加載表t1的數據，然后根據表t1的a字段作為key構造Hash表。之后，從表t2中逐條取出記錄，計算字段b的Hash值，去Hash表中查找是否存在滿足條件的記錄。

Hash Join的性能很高，但是前提條件是內存中能夠存放下其中一張表的Hash表。所以一般適用于大小表Join。在一些大數據分析的數據查詢引擎中，當內存放不下這種Hash表的時候，會將小表進行分區保存到磁盤上，之后再執行Join。

嵌套循環Join

嵌套循環Join中，至少一張表存在索引，且Join的條件是對索引列的比對。帶有索引的表作為被檢索表，對不帶有索引或者兩張都帶有索引的表中較小的那張表進行遍歷。這個算法充分利用了索引的優勢，讓Join的時間復雜度從O(m*n)變成了O(n)，其中m為被檢索表的行數，n為遍歷表的行數。

---

Merge Hash

相對于上述兩個算法，這個算法的性能差些，但是使用范圍更廣些。在這個算法中，相對兩張表中的數據進行排序，之后再分別取一段進行Join。

---

Semi Join

半連接，對于左邊的表輸出滿足條件的記錄，而對于右邊的表則不管是否滿足條件都不會被輸出，也就是，最終的結果是左邊表數據記錄的一個子集，類似于in、exists。Semi Join本身就是Join的一種。在大數據跨數據源的查詢中，Semi Join是對inner join、left join、right join的一種優化。查詢跨數據源時，盡量減少從每個數據源出來的數據量是一種很有效的優化方式，畢竟網絡傳輸是要花費時間的。將Join轉化成Semi Join是一種有效減小數據量的方式。

對于：select * from t1 join t2 where t1.a = t2.b，Semi Join的過程如下：

1.將表t1的數據加載到內存；

2.根據t1的數據，改寫加載表t2的條件，即將SQL語句改寫成in、exists等。假設表t1中，全部記錄的a字段只有兩個值：aa和bb，那么SQL將被改寫為select * from t2 in (‘aa’,‘bb’);

3.對從表t1和t2加載的數據做Join；

第2步中對加載t2數據的SQL的改寫，使原本需要加載整個t2表改為僅加載t2中滿足條件的數據。

總結

以上是生活随笔為你收集整理的SQL 中 left join 的底层原理（各种JOIN的复杂度探究）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。