文章目錄
-
- SNLJ
- INLJ
- BNLJ
- 比較
MySQL 使用 NLJ（Nested-Loop Join） 算法實作 join 聯表查詢。
NLJ 一共有三種實作 SNLJ、INLJ 和 BNLJ。後面兩種是對 SNLJ 的優化。
SNLJ
SNLJ，Simple Nested-Loop Join，簡單嵌套循環。。
假設 A 是驅動表，B 是被驅動表。
掃描 A 表，記錄一行一行取出比較，每一次比較都會掃描一次 B 表。
僞代碼如下：
For each row a in A do
For each row b in B do
If a and b satify the join condition
Then output the tuple
假設 A 表有 N 行，B 表有 M 行。SNL 的開銷如下：
- A 表掃描 1 次。
- B 表掃描 N 次。
- 一共有 N 個内循環，每個内循環要 M 次，一共有内循環 N * M 次。有就是比較了 N * M 次。
- 總共讀取記錄數： N + N * M 。
- 回表讀取記錄數：0。
INLJ
INLJ，Index Nested-Loop Join，索引嵌套循環。
和 SNLJ 的差別在于 join 使用的字段已經建立索引，利用索引提高效率。
我們假設 A 是驅動表，B 是被驅動表。
使用聚簇索引：
沒有使用聚簇索引，需要增加回表操作：
掃描 A 表，還是一行一行記錄取出比較。不一樣地方在于不用掃描 B 表，而是查詢 B 表的索引，嵌套循環的内循環被大幅度優化。
僞代碼如下：
For each row a in A do
lookup b in B index
if found b == a
Then ouput the tuple
假設 A 表 N 行，B 表 M 行，索引 B+ 樹的高度為 IndexHeight。
- A 表掃描 1 次。
- B 表掃描 0 次。因為使用了索引查詢。
- 一共有 N 個内循環，每個内循環周遊次數為索引樹的高度，為 IndexHeight 次，一共有内循環 N * IndexHeight 次。也就是比較了 N * IndexHeight 次。
- 總共讀取的記錄數：N + M(match)。M(match) 為索引傳回的記錄數。
- 回表次數：主鍵的聚簇索引為，非聚簇索引為 M(match)，即每個記錄還需要進行一次回表。
這裡有個回表問題需要關注一下。
如果要查詢的字段為 B 表的主鍵，使用了主鍵的聚簇索引，可以直接拿到記錄。
如果要查詢的字段不是 B 表的主鍵，使用的不是主鍵的聚簇索引，而是輔助索引，還需要進行一次回表查主鍵的聚簇索引。這裡的性能會很有很大的下降。
BNLJ
BNLJ，Block Nested-Loop Join，塊嵌套循環。
在 join 的字段沒有加索引的情況下，會使用 join buffer 進行優化。就是 BNLJ 算法。
假設 A 為驅動表，B 為被驅動表：
MySQL 預設 buffer 大小 256K，如果有 n 個 join 操作，會生成 n-1 個 join buffer。
A 表掃描一次，需要 join 聯表查詢的字段緩存到 buffer 中。然後掃描 B 表，把 B 表的每一行和 buffer 中的字段進行批量比較。
如果我們把 buffer 的空間開得很大，可以容納下 A 表的所有記錄，那麼 B 表也隻需要通路通路一次。
僞代碼如下：
For each tuple a In A do
store used column as p from A in join buffer
for each tuple b In B do
If p and b satisfy the join condition
Then ouput the tuple
假設 A 表 N 個記錄，B 表 M 個記錄。開銷如下：
- A 表掃描 1 次。
- B 表掃描的次數和 buffer 的大小有關，
N * (used_column_size)/join_buffer_size + 1
used_column_size
join_buffer_size
- 雖然加了 buffer，但實際上 A 表的每個記錄和 B 表的每個記錄都進行了比較，有 N * M 次比較。
- 總共讀取的記錄數： 設定 B 表掃碼次數為 H，則這裡記錄數 = M * H。
- 回表次數：0。不走索引，不存在回表。
比較
以上就是嵌套循環算法的三種實作。
假設有這樣的資料：
- 驅動表為 A，記錄數 N；被驅動表為 B，記錄數 M。
- 如果 join 字段使用索引，B+ 樹的深度為 IndexHeight。比對的記錄數為 M(match)。
- 如果 join 字段不使用索引，使用的 buffer 大小為
join_buffer_size
used_column_size
三種實作的效率比較如下：
| SNLJ | INLJ | BNLJ | |
|---|---|---|---|
| 驅動表掃描次數 | 1 | 1 | 1 |
| 被驅動表掃描次數 | N | N * (used_column_size) / join_buffer_size + 1 | |
| join 比較次數 | N * M | N + M(match) | N * M |
| 回表次數 | M(match) |
總的來說，應用 join 需要注意：
- 用來進行 join 的字段要加索引，會觸發 INLJ 算法，如果是主鍵的聚簇索引，性能最優。
- 如果無法使用索引，那麼注意調整 join buffer 大小，适當調大些。
- 小結果集驅動大結果集。用資料量小的表去驅動資料量大的表，這樣可以減少内循環個數，也就是被驅動表的掃描次數。