MySQL JOIN類型

MySQL支持多種JOIN類型，下面是每種JOIN類型的簡要概述:

• INNER JOIN：將兩個表中符合條件的行組合在一起。返回的結果集只包含滿足連接條件的行，即兩個表中都存在的行。一般簡寫成JOIN

• LEFT JOIN：返回左表中的所有行以及符合條件的右表中的行。如果右表中沒有匹配的行，則用NULL填充。

• RIGHT JOIN：返回右表中的所有行以及符合條件的左表中的行。如果左表中沒有匹配的行，則用NULL填充

• FULL OUTER JOIN：返回左表和右表中的所有行，如果一個表中沒有匹配的行，則用NULL填充。

• CROSS JOIN：返回兩個表中的所有可能的組合，也稱為笛卡爾積。

MySQL JOIN 算法

在了解完 MySQL JOIN類型概念之后，我們來了解 MySQL JOIN 算法，在之前的版本只支持Nested Loop Join這一種算法，在 MySQL 8.0.18之后支持 Hash Join算法。

Nested-Loop Join 算法

執(zhí)行流程

假設兩個表一個 user 用戶表，一個 order 訂單表，需要查詢用戶的所有訂單信息，表結構如下:

CREATE TABLE `user` (
  `id` int(11) NOT NULL COMMENT '主鍵id',
  `name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用戶名稱',
  `age` int(255) DEFAULT NULL COMMENT '年齡',
  `user_code` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用戶編號',
  PRIMARY KEY (`id`),
  KEY `idx_user_code` (`user_code`) USING BTREE COMMENT '用戶編號索引'
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='用戶表';

CREATE TABLE `order` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主鍵id',
  `order_name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '訂單名稱',
  `user_code` varchar(11) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用戶編號',
  PRIMARY KEY (`id`),
  KEY `idx_user_code` (`user_code`) USING BTREE COMMENT '用戶編號索引'
) ENGINE=InnoDB AUTO_INCREMENT=10 DEFAULT CHARSET=utf8 COMMENT='訂單表';

其中 user_code是連接字段，也是索引。SQL 如下：

mysql> SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code;
+------+-----------+------------+
| name | user_code | order_name |
+------+-----------+------------+
| 李   | 002       | 訂單1      |
| 李   | 002       | 訂單2      |
| 李   | 002       | 訂單3      |
| 李   | 002       | 訂單4      |
| 李   | 002       | 訂單5      |
| 李   | 002       | 訂單6      |
| 李   | 002       | 訂單7      |
| 李   | 002       | 訂單8      |
| 李   | 002       | 訂單9      |
+------+-----------+------------+
9 rows in set (0.08 sec)

看一下這條語句的explain結果

這個語句的執(zhí)行流程如下：

• 從表order中讀入一行數據 ；
• 從數據行中， 取出user_code字段到表user里去查找；
• user表根據索引找到滿足條件的行字段， 跟上面的數據行組成一行；
• 重復執(zhí)行步驟1到3， 直到表user的末尾循環(huán)結束。

工作原理

這個過程就跟我們寫程序時的嵌套查詢，一般稱為Nested-Loop Join (NLJ)，是一種最基本的Join算法，它通過對兩個表進行嵌套循環(huán)來查找匹配的行。具體來說，它從一個表中取出一行，然后在另一個表中掃描所有行，查找與之匹配的行。類似于這樣:

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
    }
  }
}

時間復雜度分析

這個過程將會對每一行進行一次比較，因此它的時間復雜度為：O(m∗n)O(m*n)O(m∗n)，其中 m 和 n 分別是兩個表的行數。

假設被驅動表的行數是M。 每次在被驅動表查一行數據， 要先搜索索引a， 再搜索主鍵索引。每次搜索一棵樹近似復雜度是logMlog MlogM， 所以在被驅動表上查一行的時間復雜度是 2∗logM2*log M2∗logM。

假設驅動表的行數是N， 執(zhí)行過程就要掃描驅動表N行， 然后對于每一行， 到被驅動表上匹配一次。因此整個執(zhí)行過程， 近似復雜度是 N+N∗2∗logMN + N*2*log MN+N∗2∗logM。 N對掃描行數的影響更大， 因此應該讓小表來做驅動表。對于大型數據集來說，它的性能會變得非常慢，因為它需要對一個表的每一行都掃描另一個表。

Block Nested-Loop Join 算法

執(zhí)行流程

接下來， 我們刪除掉索引，再看看被驅動表用不上索引的情況

ALTER TABLE `user` DROP INDEX `idx_user_code`;
EXPLAIN SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code

再看一下這條語句的explain結果,多了一個 Using join buffer (Block Nested Loop

這個時候語句的執(zhí)行流程如下：

• 從表user中讀入name，user_code字段數據放到線程內存join_buffer中

• 掃描表order表， 把表order中的每一行取出來， 跟join_buffer中的數據做對比， 滿足join條件的， 作為結果集的一部分返回。

工作原理

Join Buffer是一種內存緩存，并在查詢完成后釋放,它可以在執(zhí)行時緩存Join的中間結果。join_buffer 的大小是由參數join_buffer_size設定的， 默認值是256k。

mysql> show variables like '%join_buffer_size%';
+------------------+---------+
| Variable_name    | Value   |
+------------------+---------+
| join_buffer_size | 1048576 |
+------------------+---------+
1 row in set (0.10 sec)

那如果Join Buffer中放不下表user的所有數據話會怎么處理呢？ 策略很簡單， 就是分段 ，每次清空join_buffer；

for each row in t1 matching range {
    store used columns from t1 in join buffer
    ## 如果buffer滿了
	if buffer is full {
      for each row in t2 {
        for each t1 combination in join buffer {
		  ## 如果行滿足連接條件，則發(fā)送到客戶端
          if row satisfies join conditions, send to client
        }
      }
	  ## 清空buffer
      empty join buffer
    }
 
}

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

時間復雜度分析

可以看到，在這個過程中， 對表user和order都做了一次全表掃描。 因此它的時間復雜度為：O(M+N)O(M+N)O(M+N)。由于join_buffer是以無序數組的方式組織的， 因此對表order中的每一行， 都要做判斷。假設小表的行數是N， 大表的行數是M， 那么在這個算法里：

• 兩個表都做一次全表掃描， 所以總的掃描行數是M+NM+NM+N；

• 內存中的判斷次數是M∗NM*NM∗N

Block Nested-Loop Join(BNL)是一種優(yōu)化的NLJ算法，BNL 通過將一個表分成多個塊（block），然后逐個塊與另一個表進行Join操作，從而減少了不必要的重復掃描和比較。它可以提高NLJ在處理大數據集時的性能,但是會占用過多的CPU資源。會多次掃描被驅動表，占用磁盤IO資源。

Hash Join 算法

Beginning with MySQL 8.0.20, support for block nested loop is removed, and the server employs a hash join wherever a block nested loop would have been used previously.(dev.mysql.com/doc/refman/…)

  從 MySQL 8.0.20 開始，刪除了BNL算法，使用了Hash Join 算法替代。

執(zhí)行流程

我們以下面官方例子為準：

SELECT?? 
	given_name,country_name 
FROM?persons
JOIN countries 
ON persons.country_id = countries.country_id;

hash join 分為兩個階段; build 構建階段和 probe 探測階段。

build 構建

在構建階段，MySQL使用Join字段作為哈希表Key，在內存中構建Hash 表。

正常情況MySQL會選擇結果集較?。ㄒ宰止?jié)為單位，而不是行數）的去構建。比如上面會對 countries.country_id 進行 hash 計算：hash(countries.country_id) 然后將值放入內存中 hash table 的相應位置。將所有行存儲在哈希表中后，構建階段就完成了。

probe 探測階段

在探測階段，MySQL逐行遍歷被驅動表，然后計算join條件的hash值，并在hash表中查找，如果匹配，則輸出給客戶端，否則跳過。所有內表記錄遍歷完，則整個過程就結束了。

比如上面遍歷persons 表中每行數據，然后取出Join字段的值進行 hash 計算；hash(persons.country_id)，然后去內存中 hash table 中進行查找，匹配成功會發(fā)送給客戶端。

內存中hash表的大小是由參數join_buffer_size 控制的，但是，如果構建hash table 內存大于可用內存，會發(fā)生什么情況？

  當內存在build構建階段變滿時，服務器會將其余的構建寫入磁盤上的多個文件中。同時會設置文件的數量，確保最大的文件的大小與join_buffer_size一致。

每行數據寫入哪個塊文件是通過計算 join 屬性的哈希來確定的。請注意，在下圖中，使用的哈希函數與內存中生成階段使用的哈希函數不同。我們稍后會明白為什么

在探測階段，服務器對于persons 表每一行數據使用同樣的hash算法進行分區(qū)。這樣，我們就可以確定兩個輸入之間的匹配行將位于同一對文件中。

探測階段完成后，開始從磁盤讀取文件。首先會將build構建階段的第一個文件，也就是下圖中的左邊的文件，加載到內存中哈希表中。這就解釋了為什么希望最大的文件大小與內存一致，接著讀取在探測階段生成的文件，下圖中右邊的文件，在內存哈希表中進行匹配，就像之前內存操作一樣。處理第一個文件后，移動到下一塊文件，繼續(xù)，直到處理完所有文件。

到這里也明白了，如果我們對兩個操作使用相同的哈希函數，那么在將構建文件加載到哈希表中時，我們會得到一個非常糟糕的哈希表，因為同一個文件中的所有行都將哈希為相同的值。

如何使用

在MySQL 8.0.20之前，使用 EXPLAIN FORMAT=tree 來查看是否將使用Hash Join算法。

mysql> EXPLAIN   FORMAT=tree  SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code;
+-------------------------------------------------------------+
| EXPLAIN                                                           
+-------------------------------------------------+
| -> Inner hash join (u.user_code = o.user_code)  (cost=7.50 rows=7)
    -> Table scan on o  (cost=0.05 rows=9)
    -> Hash
        -> Table scan on u  (cost=0.95 rows=7)
+-----------------------------------------------------------+
1 row in set (0.04 sec)

時間復雜度分析

整體上對驅動表遍歷1次(驅動表有M行記錄)，被驅動表遍歷1次(被驅動表有N行記錄)。 因此它的時間復雜度為：O(M+N)O(M+N)O(M+N)。它通常比嵌套循環(huán)算法(NLJ)更有效，尤其是在其中一個結果集可以完全放入join_buffer內存的情況下。

MySQL JOIN 優(yōu)化

NLJ算法優(yōu)化

為了優(yōu)化Nested-Loop Join的性能，盡可能減少 Join 語句中的 Nested Loop 的循環(huán)總次數，就是讓驅動表的結果集盡可能的小。對于很多表的關聯通過應用層拆分成多個語句然后再拼接查詢結果更方便， 而且性能也不會差。

在join的時候明確知道哪張表是小表的時候,可以用straight_join寫法固定連接驅動方式

BNL算法優(yōu)化

使用Block Nested-Loop Join(BNL)算法時，可能會對被驅動表做多次掃描,占用磁盤IO資源，并且需要執(zhí)行M∗NM*NM∗N次對比但是會占用過多的CPU資源。

優(yōu)化的常見做法是，給被驅動表的join字段加上索引，把BNL算法轉成NLJ算法。

無法設置索引的情況可以通過設置join_buffer_size參數來控制Join Buffer的大小，以減少分段查詢次數

Hash Join算法優(yōu)化

Hash Join算法在從 MySQL 8.0.18 以后才會用到，也是為了替代上面的BNJ算法。

當哈希表所需的內存量超過join_buffer_size大小，會使用磁盤的文件進行處理，所以增加 join_buffer_size值避免生成文件可以極大提升查詢速度。

以上就是一文詳解MySQL—Join的使用優(yōu)化的詳細內容，更多關于MySQL Join使用優(yōu)化的資料請關注腳本之家其它相關文章！

最新評論