淺談MySQL、PostgreSQL、Oracle使用的三種 join 演算法

SQL資料庫
Andy Wu

工作中前前後後也接觸過了 MySQL、PostgreSQL、Oracle 三種資料庫。每次寫完 SQL 習慣性用 explain 看一下執行計劃，久了之後注意到一件有趣的事，雖然三家 DB 的語法和輸出格式各有不同，但 join 的執行計劃翻來覆去都圍繞著類似的幾個關鍵字。稍微研究後才發現，這背後其實大概可以歸納為三種 join 演算法。

因此本篇想來聊聊在各大 DB 常見使用的三種 join 演算法。

Nested Loop Join

Nested Loop Join 是最直觀、也是最傳統的 join 演算法。它顧名思義就只是兩層 for 迴圈，如果用程式實作，大概會這樣：

for each row_a in table_a:     # 外層表 (驅動表)
    for each row_b in table_b: # 內層表 (被驅動表)
        if row_a.key == row_b.key:
            output(row_a, row_b)

外層表跑一次，內層表就要被掃 M 次 (M 為外層 row 數)，所以最原始的 Nested Loop Join 時間複雜度是O(M × N)。但事實上，最原始的 Nested Loop Join 在現代 DB 幾乎都成為了非不得已才選的下下策選擇，實務上跑的都是叫 Index Nested Loop 優化過的變種。

Index Nested Loop

如果內層表的 join key 上有 index，內層就不用掃整張表，改用 index lookup，複雜度也就能從O(M × N)降到O(M × logN)，這才是 Nested Loop Join 在實務上真正常見的形式。

for each row_a in table_a:
    matched_rows = index_lookup(table_b, row_a.key)

    for each row_b in matched_rows:
        output(row_a, row_b)

而面試題考 DB 常常聽到的小表驅動大表也就是在講這個 case。如果外層表每個 row 都必須遍歷一遍工省不了，但是內層表能走 index 快速限縮內層 join 匹配的 row 數量，那盡量把大表放在內層讓它走 index lookup，就能大幅降低比較次數。我們可以直接用數字代入來看這件事：

  • M = 100、N = 10 則複雜度為O(100 × log10) = 100
  • M = 10、N = 100 則複雜度為O(10 × log100) = 20

代入數字後立刻有 fu 了，大表放內層走 index 比較次數整整少了 5 倍。以上就是 Nested Loop Join 的原理，實務上也可以透過這三家 DB 的 explain 語句出現的關鍵字判斷 DB 是不是選擇了 Nested Loop Join。

MySQL

EXPLAIN FORMAT=TREE
SELECT u.name, o.amount, o.created_at
FROM users u
INNER JOIN orders o ON u.id = o.user_id
WHERE u.id IN (1, 2, 3);

-> Nested loop inner join  (cost=11.8 rows=29.9)
    -> Filter: (u.id in (1,2,3))  (cost=1.36 rows=3)
        -> Index range scan on u using PRIMARY over (id = 1) OR (id = 2) OR (id = 3)  (cost=1.36 rows=3)  -- 小表驅動大表，外層表是 users
    -> Index lookup on o using idx_orders_user_id (user_id=u.id)  (cost=2.83 rows=9.98)  -- 內層表 orders 走 index lookup

PostgreSQL

EXPLAIN
SELECT u.name, o.amount, o.created_at
FROM users u
INNER JOIN orders o ON u.id = o.user_id
WHERE u.id IN (1, 2, 3);

Nested Loop  (cost=4.66..140.84 rows=30 width=23)
   ->  Index Scan using users_pkey on users u  (cost=0.29..16.91 rows=3 width=17)  -- 小表驅動大表，外層表是 users
         Index Cond: (id = ANY ('{1,2,3}'::bigint[]))
   ->  Bitmap Heap Scan on orders o  (cost=4.37..41.21 rows=10 width=22)
         Recheck Cond: (u.id = user_id)
         ->  Bitmap Index Scan on idx_orders_user_id  (cost=0.00..4.37 rows=10 width=0)  -- 內層表 orders 走 index lookup
               Index Cond: (user_id = u.id)

Oracle

EXPLAIN PLAN FOR
SELECT u.name, o.amount, o.created_at
FROM users u
INNER JOIN orders o ON u.id = o.user_id
WHERE u.id IN (1, 2, 3);

SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY);

-----------------------------------------------------------------------------------------------------
| Id  | Operation                       | Name               | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |                    |    30 |  1020 |    10   (0)| 00:00:01 |
|   1 |  NESTED LOOPS                   |                    |    30 |  1020 |    10   (0)| 00:00:01 |
|   2 |   NESTED LOOPS                  |                    |    30 |  1020 |    10   (0)| 00:00:01 |
|   3 |    INLIST ITERATOR              |                    |       |       |            |          |
|   4 |     TABLE ACCESS BY INDEX ROWID | USERS              |     3 |    42 |     4   (0)| 00:00:01 |
|*  5 |      INDEX UNIQUE SCAN          | SYS_C008305        |     3 |       |     3   (0)| 00:00:01 |  -- 小表驅動大表，外層表是 users
|*  6 |    INDEX RANGE SCAN             | IDX_ORDERS_USER_ID |     1 |       |     1   (0)| 00:00:01 |
|   7 |   TABLE ACCESS BY INDEX ROWID   | ORDERS             |    10 |   200 |     2   (0)| 00:00:01 |  -- 內層表 orders 走 index lookup
-----------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   5 - access("U"."ID"=1 OR "U"."ID"=2 OR "U"."ID"=3)
   6 - access("U"."ID"="O"."USER_ID")
       filter("O"."USER_ID"=1 OR "O"."USER_ID"=2 OR "O"."USER_ID"=3)

下一個問題來了，那如果 join key 沒有 index 該怎麼辦？我們的 DB 會把 join 退化成最原始的 Nested Loop Join 嗎？答案是在現代 DB 上還有另一招 Hash Join 可以使用，這也是我們下一章要介紹的，DB 很聰明不會那麼快就退化到選最原始的 Nested Loop Join。

Hash Join

Hash Join 從名字也能猜到就是利用 hash table 來加速 join，它會將其中一張表 (通常是較小的那張表) 根據 join key 先去建立 hash table，然後遍歷另一張比較大的表的資料去 hash table 匹配看看是否能 join 成功。用程式邏輯表示大概會長這樣：

hash_table = {}

# build hash table 階段
for each row_a in table_a:
    hash_table[row_a.key].append(row_a)

# join 階段
for each row_b in table_b:
    matched_rows = hash_table[row_b.key]

    for each row_a in matched_rows:
        output(row_a, row_b)

Hash Join 的時間複雜度是O(M + N)，其中 M 是建立 hash table 階段的小表 row 數，N 是 join 階段的大表 row 數。比起 Nested Loop Join 的O(M × N)，當 M 和 N 都很大的時候，Hash Join 的O(M + N)看起來香很多。

但天下沒有白吃的午餐，Hash Join 的代價就是那個前置的 build hash table 階段，build hash table 需要把整張小表掃過一遍，還要分配一塊記憶體把 hash table 放著。所以如果 join key 有 index 且表不大的情況下，有些 DB 的 optimizer (例如下面的 MySQL explain plan 看到的) 會更傾向選擇走 Index Nested Loop Join 因為直接走 index lookup 比額外 build hash table 更划算。只有當沒有 index 可用，但又不想退化成O(M × N)的暴力解時，或者有 index 但是表太大 optimizer 覺得建成 hash table CP 值更高時，Hash Join 才會被搬出來。

另外剛剛有提到為什麼 DB 會選比較小的表來 build hash table 呢，原因是 DB 會盡量把 hash table 放在記憶體裡，如果 build side 太大 hash table 放不下，部份 memory 的資料不得不暫時搬回到 disk 上時，join 過程就會開始頻繁 disk I/O，效能也會明顯下降。

除此之外，Hash Join 還有另一個更根本的限制是它只能處理 equal join (等值 join，也就是 a.key = b.key 這種條件)。原因也很直觀，hash 是根據 key 去 mapping 對應的 bucket 的，只有值完全相等的 row 才會落在同一個 bucket。一旦 join 條件變成 a.key < b.key 這種範圍比較，兩個本來應該匹配的值會被散到不同 bucket，hash table 就完全派不上用場了。

講完原理和限制，一樣來看看三家 DB 在 explain 中怎麼呈現 query 使用了 Hash Join。

MySQL

EXPLAIN FORMAT=TREE
SELECT u.country, COUNT(*), SUM(o.amount)
FROM users u IGNORE INDEX (PRIMARY) -- 強迫不走 PK，MySQL 特愛 Nested Loop Join
INNER JOIN orders o IGNORE INDEX (idx_orders_user_id) ON u.id = o.user_id -- 強迫不走 idx_orders_user_id，讓 order 當成大表
GROUP BY u.country;

-> Table scan on <temporary>
    -> Aggregate using temporary table
        -> Inner hash join (o.user_id = u.id)  (cost=102e+6 rows=101849)
            -> Table scan on o  (cost=0.0141 rows=99863) -- 大表 orders 掃全表
            -> Hash
                -> Covering index scan on u using idx_users_country  (cost=1028 rows=10207) -- 小表 users 用 idx_users_country 建 hash table

PostgreSQL

EXPLAIN
SELECT u.country, COUNT(*), SUM(o.amount)
FROM users u
INNER JOIN orders o ON u.id = o.user_id
GROUP BY u.country;

HashAggregate  (cost=3145.61..3145.74 rows=10 width=43)
    Group Key: u.country
    ->  Hash Join  (cost=299.00..2395.61 rows=100000 width=9)
        Hash Cond: (o.user_id = u.id)
        ->  Seq Scan on orders o  (cost=0.00..1834.00 rows=100000 width=14) -- 大表 orders 掃全表
        ->  Hash  (cost=174.00..174.00 rows=10000 width=11) -- 小表 users 建 hash table
                ->  Seq Scan on users u  (cost=0.00..174.00 rows=10000 width=11)

Oracle

EXPLAIN PLAN FOR
SELECT u.country, COUNT(*), SUM(o.amount)
FROM users u
INNER JOIN orders o ON u.id = o.user_id
GROUP BY u.country;

SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY);

------------------------------------------------------------------------------
| Id  | Operation           | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |        |    10 |   160 |   189   (3)| 00:00:01 |
|   1 |  HASH GROUP BY      |        |    10 |   160 |   189   (3)| 00:00:01 |
|*  2 |   HASH JOIN         |        |   100K|  1562K|   186   (1)| 00:00:01 | -- 第一個子節點為 build hash table 方，第二個子節點為 probe hash table 方
|   3 |    TABLE ACCESS FULL| USERS  | 10000 | 70000 |    15   (0)| 00:00:01 | -- 小表 users 建 hash table
|   4 |    TABLE ACCESS FULL| ORDERS |   100K|   878K|   171   (1)| 00:00:01 | -- 大表 orders 掃全表做 probe
------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("U"."ID"="O"."USER_ID")

那如果今天要做有範圍比較的 join 怎麼辦？或者反過來說，兩張表的 join key 上剛好都已經排好序了，能不能不用花時間建 hash table、也不用一筆筆 loop 比對？這就要說到我們下一章介紹的 Sort-Merge Join。

Sort-Merge Join

前一章提到的 Hash Join 雖然時間複雜度很漂亮只有O(M + N)，但它有兩個很明顯的限制：

  1. 需要額外 build hash table
  2. 只能處理 equal join

那如果今天兩張表的 join key 剛好都已經排好序了，能不能不要 build hash table，也不要像 Nested Loop Join 一樣反覆掃描呢？這時候就輪到 Sort-Merge Join 登場了。Sort-Merge Join 的想法是既然兩邊都已經有序，那只要像 merge sort 一樣同步往前掃描就好了。

在此先說一個重要前提，Sort-Merge Join 目前只有 PostgreSQL 和 Oracle 原生支援，MySQL 至今都還沒有。所以等等測試 explain 時在 MySQL 的部分會看到 MySQL 選擇的是 Index Nested Loop Join。

Sort-Merge Join 如果用程式邏輯表示，大概會長這樣：

sort(table_a)
sort(table_b)

pointer_a = 0
pointer_b = 0

while pointer_a < len(table_a) and pointer_b < len(table_b):

    row_a = table_a[pointer_a]
    row_b = table_b[pointer_b]

    if row_a.key < row_b.key:
        pointer_a += 1

    elif row_a.key > row_b.key:
        pointer_b += 1

    else:
        output(row_a, row_b)
        pointer_a += 1
        pointer_b += 1

# (上面假設 join key 都是 unique 的，沒有 duplicate value 的情況，這裡為了方便理解省略處理多對多 matching 的細節)

這種感覺其實很像兩個排好序的陣列做 merge。

假設：

A: 1 3 5 7 9
B: 2 3 6 7 8

一開始：

1 < 2，所以 A 往前
3 > 2，所以 B 往前
3 = 3，join 成功，A、B 都往前
5 < 6，所以 A 往前
7 > 6，所以 B 往前
7 = 7，join 成功，A、B 都往前
9 > 8，所以 B 往前
B 掃完了，結束

因為資料本身有序，所以整個過程中 pointer 永遠只會往前走，不需要回頭重新掃描。因此已排序的兩個 table 使用 Sort-Merge Join 的時間複雜度是O(M + N)，其中 M 和 N 分別是兩張表的 row 數。與 Hash Join 相比同樣是O(M + N)，但 Sort-Merge Join 不需要額外去 build hash table，也不受限於 equal-join 的條件。

上述是理想情境，現實當然並不是每次都這麼理想，真實世界的資料通常不是排好序的。所以 DB 在真正做 Merge Join 前，通常還會先做：

sort(table_a) # O(M*logM)
sort(table_b) # O(N*logN)

因此加上排序後的時間複雜度會變成：

O(M*logM + N*logN + M + N) ≈ O(M*logM + N*logN)

也因為這個 sort 成本不便宜，所以 optimizer 不會隨便選 Merge Join。

那什麼情況下 DB 會決定選 Sort-Merge Join 呢？當 join key 上剛好有 B-Tree index，而且資料本身已經有序的時候。因為 B-Tree index 本身就是排序結構，所以 DB 可以直接利用 index scan 拿到排序後的資料，省掉額外 sort 的成本，那選 Merge Join 的成本就會瞬間下降很多。

除此之外，Sort-Merge Join 還有一個 Hash Join 做不到的優勢是它可以處理 range join。例如 ON a.key < b.key 這種條件 Hash Join 就無法處理，因為 hash bucket 只能處理等值的匹配。但 Merge Join 因為資料本身有序，所以 range comparison 反而是它擅長的場景。

最後也是一樣，我們來看看三家 DB 在 explain 中怎麼呈現 Sort-Merge Join。

MySQL

EXPLAIN FORMAT=TREE
SELECT u.id, u.name, o.amount
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.id > 1000 AND u.id < 7000 -- 製造有 range 的場景
ORDER BY u.id; -- 製造有序的場景

-> Nested loop inner join  (cost=19454 rows=52663) -- MySQL 不支援 Sort-Merge，這個場景退化成 Index Nested Loop Join
    -> Filter: ((u.id > 1000) and (u.id < 7000))  (cost=1022 rows=5103)
        -> Index range scan on u using PRIMARY over (1000 < id < 7000)  (cost=1022 rows=5103)
    -> Index lookup on o using idx_orders_user_id (user_id=u.id)  (cost=2.58 rows=10.3)

PostgreSQL

EXPLAIN
SELECT u.id, u.name, o.amount
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.id > 1000 AND u.id < 7000 -- 製造有 range 的場景
ORDER BY u.id; -- 製造有序的場景

Merge Join  (cost=0.58..6509.42 rows=59990 width=23)
   Merge Cond: (u.id = o.user_id) -- 兩邊都走 index scan 拿到排序後的資料，直接做 merge join
   ->  Index Scan using users_pkey on users u  (cost=0.29..240.27 rows=5999 width=17)
         Index Cond: ((id > 1000) AND (id < 7000))
   ->  Index Scan using idx_orders_user_id on orders o  (cost=0.29..5404.26 rows=100000 width=14)

Oracle

EXPLAIN PLAN FOR
SELECT u.id, u.name, o.amount
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.id > 1000 AND u.id < 7000 -- 製造有 range 的場景
ORDER BY u.id; -- 製造有序的場景

SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY);

----------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name        | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |             | 36014 |   808K|       |   406   (1)| 00:00:01 |
|   1 |  MERGE JOIN                  |             | 36014 |   808K|       |   406   (1)| 00:00:01 | -- 主節點做 merge join
|   2 |   TABLE ACCESS BY INDEX ROWID| USERS       |  6001 |  84014|       |     4   (0)| 00:00:01 | -- users 端從已排序的 PK 拿資料
|*  3 |    INDEX RANGE SCAN          | SYS_C008305 |  6001 |       |       |     1   (0)| 00:00:01 |
|*  4 |   SORT JOIN                  |             | 60006 |   527K|  2376K|   402   (1)| 00:00:01 | -- orders 端選擇直接 filter 撈表出來排序，不走 index
|*  5 |    TABLE ACCESS FULL         | ORDERS      | 60006 |   527K|       |   171   (1)| 00:00:01 |
----------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("U"."ID">1000 AND "U"."ID"<7000)
   4 - access("U"."ID"="O"."USER_ID")
       filter("U"."ID"="O"."USER_ID")
   5 - filter("O"."USER_ID"<7000 AND "O"."USER_ID">1000)

結論

從上面的介紹和實際的 explain plan 範例可以看到，在現代 DB 中，小資料量加上有 index lookup 的情況下，DB 通常會選擇 Nested Loop Join (MySQL 特愛)；如果是大表的 equal join，DB 會傾向選擇將其中一方小表做 Hash Join；如果資料剛好需要按 join key 排序、或是遇到 range 條件 (Hash 處理不了的場景)，DB 還有 Sort-Merge Join 可以選擇。

說白了 DB optimizer 的工作就是在看 table 大小、index、有沒有排序、預估 row 數這些資訊，然後從這幾種 join 演算法挑一個它覺得成本最低的 plan 出來執行。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *