MySQL JOIN類型

MySQL支持多種JOIN類型，下面是每種JOIN類型的簡(jiǎn)要概述:

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

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

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

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

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

MySQL JOIN 算法

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

Nested-Loop Join 算法

執(zhí)行流程

假設(shè)兩個(gè)表一個(gè) user 用戶表，一個(gè) order 訂單表，需要查詢用戶的所有訂單信息，表結(jié)構(gòu)如下:

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 '用戶編號(hào)',
  PRIMARY KEY (`id`),
  KEY `idx_user_code` (`user_code`) USING BTREE COMMENT '用戶編號(hào)索引'
) 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 '用戶編號(hào)',
  PRIMARY KEY (`id`),
  KEY `idx_user_code` (`user_code`) USING BTREE COMMENT '用戶編號(hào)索引'
) 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)

看一下這條語(yǔ)句的explain結(jié)果

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

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

工作原理

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

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

時(shí)間復(fù)雜度分析

這個(gè)過(guò)程將會(huì)對(duì)每一行進(jìn)行一次比較，因此它的時(shí)間復(fù)雜度為：O(m∗n)O(m*n)O(m∗n)，其中 m 和 n 分別是兩個(gè)表的行數(shù)。

假設(shè)被驅(qū)動(dòng)表的行數(shù)是M。 每次在被驅(qū)動(dòng)表查一行數(shù)據(jù)， 要先搜索索引a， 再搜索主鍵索引。每次搜索一棵樹(shù)近似復(fù)雜度是logMlog MlogM， 所以在被驅(qū)動(dòng)表上查一行的時(shí)間復(fù)雜度是 2∗logM2*log M2∗logM。

假設(shè)驅(qū)動(dòng)表的行數(shù)是N， 執(zhí)行過(guò)程就要掃描驅(qū)動(dòng)表N行， 然后對(duì)于每一行， 到被驅(qū)動(dòng)表上匹配一次。因此整個(gè)執(zhí)行過(guò)程， 近似復(fù)雜度是 N+N∗2∗logMN + N*2*log MN+N∗2∗logM。 N對(duì)掃描行數(shù)的影響更大， 因此應(yīng)該讓小表來(lái)做驅(qū)動(dòng)表。對(duì)于大型數(shù)據(jù)集來(lái)說(shuō)，它的性能會(huì)變得非常慢，因?yàn)樗枰獙?duì)一個(gè)表的每一行都掃描另一個(gè)表。

Block Nested-Loop Join 算法

執(zhí)行流程

接下來(lái)， 我們刪除掉索引，再看看被驅(qū)動(dòng)表用不上索引的情況

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

再看一下這條語(yǔ)句的explain結(jié)果,多了一個(gè) Using join buffer (Block Nested Loop

這個(gè)時(shí)候語(yǔ)句的執(zhí)行流程如下：

• 從表user中讀入name，user_code字段數(shù)據(jù)放到線程內(nèi)存join_buffer中

• 掃描表order表， 把表order中的每一行取出來(lái)， 跟join_buffer中的數(shù)據(jù)做對(duì)比， 滿足join條件的， 作為結(jié)果集的一部分返回。

工作原理

Join Buffer是一種內(nèi)存緩存，并在查詢完成后釋放,它可以在執(zhí)行時(shí)緩存Join的中間結(jié)果。join_buffer 的大小是由參數(shù)join_buffer_size設(shè)定的， 默認(rèn)值是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的所有數(shù)據(jù)話會(huì)怎么處理呢？ 策略很簡(jiǎn)單， 就是分段 ，每次清空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
    }
  }
}

時(shí)間復(fù)雜度分析

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

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

• 內(nèi)存中的判斷次數(shù)是M∗NM*NM∗N

Block Nested-Loop Join(BNL)是一種優(yōu)化的NLJ算法，BNL 通過(guò)將一個(gè)表分成多個(gè)塊（block），然后逐個(gè)塊與另一個(gè)表進(jìn)行Join操作，從而減少了不必要的重復(fù)掃描和比較。它可以提高NLJ在處理大數(shù)據(jù)集時(shí)的性能,但是會(huì)占用過(guò)多的CPU資源。會(huì)多次掃描被驅(qū)動(dòng)表，占用磁盤(pán)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 開(kāi)始，刪除了BNL算法，使用了Hash Join 算法替代。

執(zhí)行流程

我們以下面官方例子為準(zhǔn)：

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

hash join 分為兩個(gè)階段; build 構(gòu)建階段和 probe 探測(cè)階段。

build 構(gòu)建

在構(gòu)建階段，MySQL使用Join字段作為哈希表Key，在內(nèi)存中構(gòu)建Hash 表。

正常情況MySQL會(huì)選擇結(jié)果集較小（以字節(jié)為單位，而不是行數(shù)）的去構(gòu)建。比如上面會(huì)對(duì) countries.country_id 進(jìn)行 hash 計(jì)算：hash(countries.country_id) 然后將值放入內(nèi)存中 hash table 的相應(yīng)位置。將所有行存儲(chǔ)在哈希表中后，構(gòu)建階段就完成了。

probe 探測(cè)階段

在探測(cè)階段，MySQL逐行遍歷被驅(qū)動(dòng)表，然后計(jì)算join條件的hash值，并在hash表中查找，如果匹配，則輸出給客戶端，否則跳過(guò)。所有內(nèi)表記錄遍歷完，則整個(gè)過(guò)程就結(jié)束了。

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

內(nèi)存中hash表的大小是由參數(shù)join_buffer_size 控制的，但是，如果構(gòu)建hash table 內(nèi)存大于可用內(nèi)存，會(huì)發(fā)生什么情況？

  當(dāng)內(nèi)存在build構(gòu)建階段變滿時(shí)，服務(wù)器會(huì)將其余的構(gòu)建寫(xiě)入磁盤(pán)上的多個(gè)文件中。同時(shí)會(huì)設(shè)置文件的數(shù)量，確保最大的文件的大小與join_buffer_size一致。

每行數(shù)據(jù)寫(xiě)入哪個(gè)塊文件是通過(guò)計(jì)算 join 屬性的哈希來(lái)確定的。請(qǐng)注意，在下圖中，使用的哈希函數(shù)與內(nèi)存中生成階段使用的哈希函數(shù)不同。我們稍后會(huì)明白為什么

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

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

到這里也明白了，如果我們對(duì)兩個(gè)操作使用相同的哈希函數(shù)，那么在將構(gòu)建文件加載到哈希表中時(shí)，我們會(huì)得到一個(gè)非常糟糕的哈希表，因?yàn)橥粋€(gè)文件中的所有行都將哈希為相同的值。

如何使用

在MySQL 8.0.20之前，使用 EXPLAIN FORMAT=tree 來(lái)查看是否將使用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)

時(shí)間復(fù)雜度分析

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

MySQL JOIN 優(yōu)化

NLJ算法優(yōu)化

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

在join的時(shí)候明確知道哪張表是小表的時(shí)候,可以用straight_join寫(xiě)法固定連接驅(qū)動(dòng)方式

BNL算法優(yōu)化

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

優(yōu)化的常見(jiàn)做法是，給被驅(qū)動(dòng)表的join字段加上索引，把BNL算法轉(zhuǎn)成NLJ算法。

無(wú)法設(shè)置索引的情況可以通過(guò)設(shè)置join_buffer_size參數(shù)來(lái)控制Join Buffer的大小，以減少分段查詢次數(shù)

Hash Join算法優(yōu)化

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

當(dāng)哈希表所需的內(nèi)存量超過(guò)join_buffer_size大小，會(huì)使用磁盤(pán)的文件進(jìn)行處理，所以增加 join_buffer_size值避免生成文件可以極大提升查詢速度。

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

最新評(píng)論