一文詳解MySQL—Join的使用優(yōu)化
MySQL JOIN類型
MySQL
支持多種JOIN
類型,下面是每種JOIN
類型的簡要概述:
INNER JOIN
:將兩個表中符合條件的行組合在一起。返回的結(jié)果集只包含滿足連接條件的行,即兩個表中都存在的行。一般簡寫成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
訂單表,需要查詢用戶的所有訂單信息,表結(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 '用戶編號', 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
結(jié)果
這個語句的執(zhí)行流程如下:
- 從表
order
中讀入一行數(shù)據(jù) ; - 從數(shù)據(jù)行中, 取出
user_code
字段到表user
里去查找; user
表根據(jù)索引找到滿足條件的行字段, 跟上面的數(shù)據(jù)行組成一行;- 重復執(zhí)行步驟1到3, 直到表
user
的末尾循環(huán)結(jié)束。
工作原理
這個過程就跟我們寫程序時的嵌套查詢,一般稱為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
分別是兩個表的行數(shù)。
假設被驅(qū)動表的行數(shù)是M
。 每次在被驅(qū)動表查一行數(shù)據(jù), 要先搜索索引a, 再搜索主鍵索引。每次搜索一棵樹近似復雜度是logMlog MlogM, 所以在被驅(qū)動表上查一行的時間復雜度是 2∗logM2*log M2∗logM。
假設驅(qū)動表的行數(shù)是N
, 執(zhí)行過程就要掃描驅(qū)動表N
行, 然后對于每一行, 到被驅(qū)動表上匹配一次。因此整個執(zhí)行過程, 近似復雜度是 N+N∗2∗logMN + N*2*log MN+N∗2∗logM。 N
對掃描行數(shù)的影響更大, 因此應該讓小表來做驅(qū)動表。對于大型數(shù)據(jù)集來說,它的性能會變得非常慢,因為它需要對一個表的每一行都掃描另一個表。
Block Nested-Loop Join 算法
執(zhí)行流程
接下來, 我們刪除掉索引,再看看被驅(qū)動表用不上索引的情況
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
結(jié)果,多了一個 Using join buffer (Block Nested Loop
這個時候語句的執(zhí)行流程如下:
從表
user
中讀入name,user_code
字段數(shù)據(jù)放到線程內(nèi)存join_buffer
中掃描表
order
表, 把表order
中的每一行取出來, 跟join_buffer
中的數(shù)據(jù)做對比, 滿足join
條件的, 作為結(jié)果集的一部分返回。
工作原理
Join Buffer
是一種內(nèi)存緩存,并在查詢完成后釋放,它可以在執(zhí)行時緩存Join
的中間結(jié)果。join_buffer
的大小是由參數(shù)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
的所有數(shù)據(jù)話會怎么處理呢? 策略很簡單, 就是分段 ,每次清空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
是以無序數(shù)組的方式組織的, 因此對表order
中的每一行, 都要做判斷。假設小表的行數(shù)是N
, 大表的行數(shù)是M
, 那么在這個算法里:
兩個表都做一次全表掃描, 所以總的掃描行數(shù)是M+NM+NM+N;
內(nèi)存中的判斷次數(shù)是M∗NM*NM∗N
Block Nested-Loop Join(BNL)
是一種優(yōu)化的NLJ
算法,BNL
通過將一個表分成多個塊(block
),然后逐個塊與另一個表進行Join
操作,從而減少了不必要的重復掃描和比較。它可以提高NLJ
在處理大數(shù)據(jù)集時的性能,但是會占用過多的CPU
資源。會多次掃描被驅(qū)動表,占用磁盤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
構(gòu)建階段和 probe
探測階段。
build 構(gòu)建
在構(gòu)建階段,MySQL
使用Join
字段作為哈希表Key
,在內(nèi)存中構(gòu)建Hash
表。
正常情況MySQL
會選擇結(jié)果集較?。ㄒ宰止?jié)為單位,而不是行數(shù))的去構(gòu)建。比如上面會對 countries.country_id
進行 hash
計算:hash(countries.country_id)
然后將值放入內(nèi)存中 hash table
的相應位置。將所有行存儲在哈希表中后,構(gòu)建階段就完成了。
probe 探測階段
在探測階段,MySQL
逐行遍歷被驅(qū)動表,然后計算join
條件的hash
值,并在hash
表中查找,如果匹配,則輸出給客戶端,否則跳過。所有內(nèi)表記錄遍歷完,則整個過程就結(jié)束了。
比如上面遍歷persons
表中每行數(shù)據(jù),然后取出Join
字段的值進行 hash
計算;hash(persons.country_id)
,然后去內(nèi)存中 hash table
中進行查找,匹配成功會發(fā)送給客戶端。
內(nèi)存中hash表的大小是由參數(shù)join_buffer_size
控制的,但是,如果構(gòu)建hash table
內(nèi)存大于可用內(nèi)存,會發(fā)生什么情況?
當內(nèi)存在build
構(gòu)建階段變滿時,服務器會將其余的構(gòu)建寫入磁盤上的多個文件中。同時會設置文件的數(shù)量,確保最大的文件的大小與join_buffer_size
一致。
每行數(shù)據(jù)寫入哪個塊文件是通過計算 join
屬性的哈希來確定的。請注意,在下圖中,使用的哈希函數(shù)與內(nèi)存中生成階段使用的哈希函數(shù)不同。我們稍后會明白為什么
在探測階段,服務器對于persons
表每一行數(shù)據(jù)使用同樣的hash
算法進行分區(qū)。這樣,我們就可以確定兩個輸入之間的匹配行將位于同一對文件中。
探測階段完成后,開始從磁盤讀取文件。首先會將build
構(gòu)建階段的第一個文件,也就是下圖中的左邊的文件,加載到內(nèi)存中哈希表中。這就解釋了為什么希望最大的文件大小與內(nèi)存一致,接著讀取在探測階段生成的文件,下圖中右邊的文件,在內(nèi)存哈希表中進行匹配,就像之前內(nèi)存操作一樣。處理第一個文件后,移動到下一塊文件,繼續(xù),直到處理完所有文件。
到這里也明白了,如果我們對兩個操作使用相同的哈希函數(shù),那么在將構(gòu)建文件加載到哈希表中時,我們會得到一個非常糟糕的哈希表,因為同一個文件中的所有行都將哈希為相同的值。
如何使用
在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)
時間復雜度分析
整體上對驅(qū)動表遍歷1次(驅(qū)動表有M
行記錄),被驅(qū)動表遍歷1次(被驅(qū)動表有N
行記錄)。 因此它的時間復雜度為:O(M+N)O(M+N)O(M+N)。它通常比嵌套循環(huán)算法(NLJ)
更有效,尤其是在其中一個結(jié)果集可以完全放入join_buffer
內(nèi)存的情況下。
MySQL JOIN
優(yōu)化
NLJ算法優(yōu)化
為了優(yōu)化Nested-Loop Join
的性能,盡可能減少 Join
語句中的 Nested Loop
的循環(huán)總次數(shù),就是讓驅(qū)動表的結(jié)果集盡可能的小。對于很多表的關(guān)聯(lián)通過應用層拆分成多個語句然后再拼接查詢結(jié)果更方便, 而且性能也不會差。
在join
的時候明確知道哪張表是小表的時候,可以用straight_join
寫法固定連接驅(qū)動方式
BNL算法優(yōu)化
使用Block Nested-Loop Join(BNL)
算法時,可能會對被驅(qū)動表做多次掃描,占用磁盤IO
資源,并且需要執(zhí)行M∗NM*NM∗N次對比但是會占用過多的CPU
資源。
優(yōu)化的常見做法是,給被驅(qū)動表的join
字段加上索引,把BNL
算法轉(zhuǎn)成NLJ
算法。
無法設置索引的情況可以通過設置join_buffer_size
參數(shù)來控制Join Buffer
的大小,以減少分段查詢次數(shù)
Hash Join算法優(yōu)化
Hash Join
算法在從 MySQL 8.0.18
以后才會用到,也是為了替代上面的BNJ
算法。
當哈希表所需的內(nèi)存量超過join_buffer_size
大小,會使用磁盤的文件進行處理,所以增加 join_buffer_size
值避免生成文件可以極大提升查詢速度。
以上就是一文詳解MySQL—Join的使用優(yōu)化的詳細內(nèi)容,更多關(guān)于MySQL Join使用優(yōu)化的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
mysql報錯:Deadlock found when trying to get lock; try restarti
這篇文章主要給大家介紹了關(guān)于mysql出現(xiàn)報錯:Deadlock found when trying to get lock; try restarting transaction的解決方法,文中通過示例代碼介紹的非常詳細,對大家具有一定的參考學習價值,需要的朋友們下面來一起看看吧。2017-07-07MySQL多表關(guān)聯(lián)查詢方式及實際應用
MySQL語句學習的難點和重點就在于多表查詢,同時MySQL也有諸多方法供大家選擇,不論是多表聯(lián)查(聯(lián)結(jié)表、左連接、右連接……),這篇文章主要給大家介紹了關(guān)于MySQL多表關(guān)聯(lián)查詢方式及實際應用的相關(guān)資料,需要的朋友可以參考下2024-07-07設置MySQL中的數(shù)據(jù)類型來優(yōu)化運行速度的實例
這篇文章主要介紹了設置MySQL中索引的數(shù)據(jù)類型來優(yōu)化運行速度的實例,主要是適當使用短字節(jié)的數(shù)據(jù)類型來處理短索引,需要的朋友可以參考下2015-05-05MySQL實現(xiàn)查詢某個字段含有字母數(shù)字的值
這篇文章主要介紹了MySQL實現(xiàn)查詢某個字段含有字母數(shù)字的值方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-07-07關(guān)于mysql?left?join?查詢慢時間長的踩坑總結(jié)
這篇文章主要介紹了關(guān)于mysql?left?join?查詢慢時間長的踩坑總結(jié),具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-09-09一文教你快速生成MySQL數(shù)據(jù)庫關(guān)系圖
我們經(jīng)常會用到一些表的數(shù)據(jù)庫關(guān)系圖,下面這篇文章主要給大家介紹了關(guān)于生成MySQL數(shù)據(jù)庫關(guān)系圖的相關(guān)資料,文中通過圖文以及實例代碼介紹的非常詳細,需要的朋友可以參考下2022-06-06