前言
連接配接（Join）是關系資料庫重要特性，它和事務常被作為資料庫與檔案系統的兩個重要差別項。程式員江湖一直流傳着某某 baba 的神秘開發寶典，其中資料庫部分有重要一條避免過多表的 Join，奈何 Join 特性實在是好用，廣大程式員們無視着寶典的諄諄教誨，依舊每天樂此不疲的使用這 Join 特性。那資料庫有哪些連接配接算法呢？它們的實作方式是怎樣呢？它們之間又有什麼差別呢？為什麼需要這麼多不同的連接配接算法呢？如果你也好奇這些問題，那麼請繼續往下閱讀，本文将逐一回答上述問題。
關聯算法簡介
關系型資料庫主要有三種 Join 算法：Nested Loop Join，Hash Join、 Merge Join，像 Oracle、SqlServer 、DB2 這幾位資料庫中的老炮均支援三種 Join 方式；MySQL 長久以來隻支援 NLJ 或其變種，直到8.0.18 版本後才有限的支援 Hash Join。在 「程式員必備的資料庫知識：資料存儲結構」一文中介紹了資料庫幾種常見的資料存儲結構，存儲引擎之上是計算引擎。以 MySQL 資料庫為例，計算引擎層通常包括 SQL 接口、解析器、查詢優化器、緩存等元件，資料庫 Join 實作就在計算引擎的查詢優化器中。
以 MySQL 資料庫為例，計算引擎層
然而資料庫具體選擇哪種連接配接算法，是由本身決定的，主要根據目前的優化器模式、表大小、連接配接列是否有索引和排序等因素決定。
多表連接配接方式又分為：内連接配接（等值連接配接）、外連接配接和交叉連接配接，外連接配接又分為：左外連接配接、右外連接配接和全外連接配接。對于不同方式的連接配接查詢，使用相同的 Join 算法也會有不同的成本産生，這和實作方式緊密相關的。本文不涉及同一個 Join 算法在不同連接配接方式的情況。
Nested Loop Join
NLJ 是 MySQL 最重要的連接配接方式，也是 MySQL 長期唯一支援的連接配接方式，直到 8.0.18 版本 MySQL 才有限的支援 Hash Join。那什麼是 NLJ 呢？從概念上講，NLJ 相當于兩個嵌套循環，用第一張表做 Outter Loop，第二張表做 Inner Loop，Outter Loop 的每一條記錄跟 Inner Loop 的記錄作比較，最終符合條件的就将該資料記錄。
可以用以下僞代碼表示：
NLJ 可以用僞代碼表示
如果忽略記憶體和 CPU 的時間，它的成本是：
Cost(NLJ) = Read(M) + M * Read(N) （其中M和N表示需要讀兩個關聯表中的資料行數）
NLJ 的算法比較簡單，并且對 Join 的連接配接條件沒有特殊要求（Hash Join 通常隻支援等值，Merge Join 一般不支援不等和like），在有索引過濾性較好的 OLTP 場景下，它的查詢效率很高。缺點也同樣明顯，由于它的成本是：Read(M) + M * Read(N) 。在 OLAP 需要大表間 Join 場景下，它的查詢效率變得比較差。在 MySQL 中 NLJ 還有兩個變種：Index Nested Loop Join（INLJ）、Block Nested Loop Join（BNLJ），本文不涉及這方面的擴充，有興趣的同學可以深入研究。
Hash Join
Hash Join 是Oracle、SQLServer 、PostgreSQL 中重要的關聯算法，當兩個表關聯時，選擇一張表按照 join 條件給的列建構 hash 表，然後将第二張表的每行記錄去探測 hash 表中的資料，如果符合連接配接條件就輸出該資料。前一張表我們叫做 build 表，後一張表我們的叫做 probe 表。為了減少記憶體使用量，通常選擇小表作為 hash 表，大表作為 probe 表。
Hash Join
經典 Hash Join 主要有兩個步驟：選擇 hash 表，掃描該表并建立 hash 表；将另一個作為 probe 表，掃描每一行資料，然後在 hash 表中找尋對應的滿足條件的記錄。忽略記憶體和 CPU 時間，它的成本是：
Cost(HJ) = Read(M) + Read(N)
Hash Join 需要把表放到記憶體中，如果記憶體不夠怎麼辦？為了處理這種情況，又誕生一些 Hash Join 的變種，比如 Grace Hash Join 。簡單說是通過分區方式實作，根據關聯字段将兩個表的資料分區，然後對同一分區的資料再進行原生 Hash join 的 build 與 probe 過程，最後将所有分區的資料合并成最後的結果集。當然在實際中會更複雜，比如在大資料量的情況下，有機率出現不同資料的 HASH 值卻是相同的問題。
總的來說，Hash Join 是處理大表間 Join 的不錯選擇。MySQL 在 8.0.18 前一直沒有 Hash join 的實作，甚至在5.5以前隻有最原始的 NLJ，5.5後才有 NLJ 優化變種的 B（Block）NLJ。但 Oracle 早在7.3版本之後就引入了 Hash join 算法，在 OLAP 領域中 Hash join 更是絕對的标配，Greenplum 和 Spark SQL 就充分利用了它。但是它也有缺點，比如隻能使用等值查詢、需要更多的記憶體資源等。
Merge Join
Merge Join ，準确地說它叫 Sort Merge Join， 在合并關聯查詢時要先確定兩個關聯表是按關聯字段相同排序的。如果關聯字段有可用的索引（配合聚集索引服用效果更佳）并且排序一緻，則可以直接進行Merge 操作，否則要先對關聯表按照關聯字段進行一次排序。排好序後，再從每個表取一條記錄開始比對，如果符合關聯條件，則放入結果集中；否則将關聯字段值較小的記錄抛棄，從這條記錄對應的表中取下一條記錄繼續進行比對，直到整個循環結束。是以它的成本是這樣的：
COST(MJ) = Read(M) + Sort(M) + Read(N) + Sort(N)
顯然，Merge Join 适合在關聯列上有索引的表，最好在關聯列還有相同的排序方式，在這種情況下它的關聯查詢效率是最高的。但是關聯字段如果沒有排序，那麼它的排序階段則比較耗時。
總結
通過前文的分析，我們基本可以回答文章最開頭的幾個問題了，更多資訊可以看下表格。另外，除了上述常見的三種資料庫Join方式外，還有 Hive 支援 Map Join 和 Reduce Join。
常見 Join 算法的優勢對比總覽
作者
司馬遼太傑是 NineData 工程師。NineData 向企業和個人提供高效、安全的資料庫 SQL 開發、資料庫備份、資料複制/遷移/內建、資料對比等功能，是一個 SaaS 服務開箱即用，可以快速提升企業 SQL 開發效率，保障企業資料安全。NineData 位址：NineData-讓每個人用好資料和雲-玖章算術