MySQL 查詢優化之 Block Nested-Loop 與 Batched Key Access Joins 在MySQL中，可以使用批量密鑰訪問（BKA）連接演算法，該演算法使用對連接表的索引訪問和連接緩衝區。 BKA演算法支持：內連接，外連接和半連接操作，包括嵌套外連接。 BKA的優點：更加高效的 ...

MySQL 查詢優化之 Block Nested-Loop 與 Batched Key Access Joins

在MySQL中，可以使用批量密鑰訪問（BKA）連接演算法，該演算法使用對連接表的索引訪問和連接緩衝區。

BKA演算法支持：內連接，外連接和半連接操作，包括嵌套外連接。

BKA的優點：更加高效的表掃描提高了連接性能。

此外，先前僅用於內連接的塊嵌套迴圈（BNL）連接演算法現已擴展，可用於外連接和半連接操作，包括嵌套外連接。

以下部分討論了連接緩衝區管理，它是原始BNL演算法擴展，擴展BNL演算法和BKA演算法的基礎。有關半連接策略的信息，請參見“使用半連接轉換優化子查詢，派生表和視圖引用”

Nested Loop Join 演算法
Block Nested-Loop 演算法
Batched Key Access 演算法
BNL和BKA演算法的優化器Hint

Nested Loop Join演算法

將外層表的結果集作為迴圈的基礎數據，然後迴圈從該結果集每次一條獲取數據作為下一個表的過濾條件去查詢數據，然後合併結果。如果有多個表join，那麼應該將前面的表的結果集作為迴圈數據，取結果集中的每一行再到下一個表中繼續進行迴圈匹配，獲取結果集並返回給客戶端。

偽代碼如下：

for each row in t1 matching range {
  for each row in t2 matching reference key {
     for each row in t3 {
      if row satisfies join conditions,
      send to client
    }
  }
 }

普通的Nested-Loop Join演算法一次只能將一行數據傳入記憶體迴圈，所以外層迴圈結果集有多少行，那麼記憶體迴圈就要執行多少次。

Block Nested-Loop演算法

MySQL BNL演算法原本只支持內連接，現在已支持外連接和半連接操作,包括嵌套外連接。

BNL演算法原理：將外層迴圈的行/結果集存入join buffer，記憶體迴圈的每一行數據與整個buffer中的記錄做比較，可以減少內層迴圈的掃描次數

舉個簡單的例子：外層迴圈結果集有1000行數據，使用NLJ演算法需要掃描內層表1000次，但如果使用BNL演算法，則先取出外層表結果集的100行存放到join buffer, 然後用內層表的每一行數據去和這100行結果集做比較，可以一次性與100行數據進行比較，這樣內層表其實只需要迴圈1000/100=10次，減少了9/10。

偽代碼如下：

for each row in t1 matching range {
   for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
         for each t1, t2 combination in join buffer {
          if row satisfies join conditions,
          send to client
        }
        }
       empty buffer
     }
   }
 }

 if buffer is not empty {
    for each row in t3 {
     for each t1, t2 combination in join buffer {
       if row satisfies join conditions,
       send to client
      }
   }
 }

如果t1, t2參與join的列長度只和為s, c為二者組合數, 那麼t3表被掃描的次數為

(S * C)/join_buffer_size + 1

掃描t3的次數隨著join_buffer_size的增大而減少, 直到join buffer能夠容納所有的t1, t2組合, 再增大join buffer size, query 的速度就不會再變快了。

optimizer_switch系統變數的block_nested_loop標誌控制優化器是否使用塊嵌套迴圈演算法。

預設情況下，block_nested_loop已啟用。

在EXPLAIN輸出中，當Extra值包含Using join buffer（Block Nested Loop）且type值為ALL，index或range時，表示使用BNL。

示例

mysql> explain SELECT  a.gender, b.dept_no FROM employees a, dept_emp b WHERE a.birth_date = b.from_date;
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
|  1 | SIMPLE      | a     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 298936 |   100.00 | NULL                                               |
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 331143 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

Batched Key Access 演算法

對於多表join語句，當MySQL使用索引訪問第二個join表的時候，使用一個join buffer來收集第一個操作對象生成的相關列值。BKA構建好key後，批量傳給引擎層做索引查找。key是通過MRR介面提交給引擎的，這樣，MRR使得查詢更有效率。

如果外部表掃描的是主鍵，那麼表中的記錄訪問都是比較有序的，但是如果聯接的列是非主鍵索引，那麼對於表中記錄的訪問可能就是非常離散的。因此對於非主鍵索引的聯接，Batched Key Access Join演算法將能極大提高SQL的執行效率。BKA演算法支持內連接，外連接和半連接操作，包括嵌套外連接。

Batched Key Access Join演算法的工作步驟如下：

1) 將外部表中相關的列放入Join Buffer中。
2) 批量的將Key（索引鍵值）發送到Multi-Range Read（MRR）介面。
3) Multi-Range Read（MRR）通過收到的Key，根據其對應的ROWID進行排序，然後再進行數據的讀取操作。
4) 返回結果集給客戶端。

Batched Key Access Join演算法的本質上來說還是Simple Nested-Loops Join演算法，其發生的條件為內部表上有索引，並且該索引為非主鍵，並且聯接需要訪問內部表主鍵上的索引。這時Batched Key Access Join演算法會調用Multi-Range Read（MRR）介面，批量的進行索引鍵的匹配和主鍵索引上獲取數據的操作，以此來提高聯接的執行效率，因為讀取數據是以順序磁碟IO而不是隨機磁碟IO進行的。

使用BKA時，join_buffer_size的值定義了對存儲引擎的每個請求中批量密鑰的大小。緩衝區越大，對連接操作的右側表的順序訪問就越多，這可以顯著提高性能。

要使用BKA，必須將optimizer_switch系統變數的batched_key_access標誌設置為on。 BKA使用MRR，因此mrr標誌也必須打開。目前，MRR的成本估算過於悲觀。因此，mrr_cost_based也必須關閉才能使用BKA。

以下設置啟用BKA：

mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

在EXPLAIN輸出中，當Extra值包含Using join buffer（Batched Key Access）且類型值為ref或eq_ref時，表示使用BKA。

示例：

mysql> show index from employees;
+-----------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table     | Non_unique | Key_name       | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-----------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| employees |          0 | PRIMARY        |            1 | emp_no      | A         |      298936 |     NULL | NULL   |      | BTREE      |         |               |
| employees |          1 | idx_name       |            1 | last_name   | A         |        1679 |     NULL | NULL   |      | BTREE      |         |               |
| employees |          1 | idx_name       |            2 | first_name  | A         |      277495 |     NULL | NULL   |      | BTREE      |         |               |
| employees |          1 | idx_birth_date |            1 | birth_date  | A         |        4758 |     NULL | NULL   |      | BTREE      |         |               |
+-----------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)


mysql> explain SELECT a.gender, b.dept_no FROM employees a, dept_emp b WHERE a.birth_date = b.from_date;
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+-------+
| id | select_type | table | partitions | type | possible_keys  | key            | key_len | ref                   | rows   | filtered | Extra |
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+-------+
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL           | NULL           | NULL    | NULL                  | 331143 |   100.00 | NULL  |
|  1 | SIMPLE      | a     | NULL       | ref  | idx_birth_date | idx_birth_date | 3       | employees.b.from_date |     62 |   100.00 | NULL  |
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+-------+

#使用hint，強制走bka

mysql> explain SELECT /*+ bka(a)*/ a.gender, b.dept_no FROM employees a, dept_emp b WHERE a.birth_date = b.from_date;
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+
| id | select_type | table | partitions | type | possible_keys  | key            | key_len | ref                   | rows   | filtered | Extra                                  |
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL           | NULL           | NULL    | NULL                  | 331143 |   100.00 | NULL                                   |
|  1 | SIMPLE      | a     | NULL       | ref  | idx_birth_date | idx_birth_date | 3       | employees.b.from_date |     62 |   100.00 | Using join buffer (Batched Key Access) |
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+
2 rows in set, 1 warning (0.00 sec)

BNL和BKA演算法的優化器Hint

除了使用optimizer_switch系統變數來控制優化程式在會話範圍內使用BNL和BKA演算法之外，MySQL還支持優化程式提示，以便在每個語句的基礎上影響優化程式。請參見“優化程式Hint”。

要使用BNL或BKA提示為外部聯接的任何內部表啟用聯接緩衝，必須為外部聯接的所有內部表啟用聯接緩衝。

使用qb_name

SELECT /*+ QB_NAME(qb1) MRR(@qb1 t1) BKA(@qb2) NO_MRR(@qb3t1 idx1, id2) */ ...
  FROM (SELECT /*+ QB_NAME(qb2) */ ...
  FROM (SELECT /*+ QB_NAME(qb3) */ ... FROM ...)) ...