Where Field in(...) 是怎么執(zhí)行的?
我們?nèi)粘?SQL 時(shí),子查詢應(yīng)該算是??土?。MySQL 為子查詢執(zhí)行準(zhǔn)備了各種優(yōu)化策略,接下來我會(huì)寫子查詢各種優(yōu)化策略是怎么執(zhí)行的系列文章。
本文以包含最簡(jiǎn)單的 in 條件的查詢?nèi)胧?,介紹 where field in (8,18,88,...) 這種值都是常量的 in 條件是怎么執(zhí)行的。
這雖然不是子查詢,我們就把它當(dāng)成子查詢的鄰居好了,用它作為子查詢系列的開篇,算是離子查詢又近了一步 ^_^。
本文內(nèi)容基于 MySQL 8.0.29 源碼。
正文
1、概述
MySQL 為了能讓 SQL 語句執(zhí)行得更快一點(diǎn),費(fèi)盡心思進(jìn)行了各種優(yōu)化。
where field in (8,18,88,...) 這種值都是常量的 in 條件,看起來已經(jīng)是最簡(jiǎn)單的形式了,執(zhí)行過程似乎也沒有什么可以優(yōu)化的,但 MySQL 還是對(duì)它進(jìn)行了優(yōu)化。
這種 in 條件會(huì)有 2 種執(zhí)行方式:
- 二分法查找
- 循環(huán)比較
MySQL 會(huì)優(yōu)先使用二分法查找方式執(zhí)行,如果不滿足條件,再退而使用循環(huán)比較方式。
2、二分法查找
判斷 in 條件括號(hào)中的值和記錄字段值是否匹配,相比于循環(huán)比較方式,二分法查找把時(shí)間復(fù)雜度從 O(N) 降為 O(logN),大大減少了需要比較的次數(shù),提升了 SQL 的執(zhí)行效率。
(1)構(gòu)造二分法查找數(shù)組
二分法查找雖好,但需要滿足一定條件才能使用:
- in 條件括號(hào)中的所有值都是常量,也就是說不能包含任何表中的字段、也不能包含系統(tǒng)變量(如 @@tmp_table_size)或自定義變量(如 @a),總之是不能包含任何可以變化的東西。
- in 條件括號(hào)中所有值的數(shù)據(jù)類型必須相同。舉個(gè)反例:where field in (1,8,'10') 這種既包含整數(shù)又包含字符串的 in 條件就是不行的。
- in 條件括號(hào)中所有值的類型,以及字段本身的類型都不能是 json。
如果以上 3 個(gè)條件都滿足,就具備使用二分法查找的基礎(chǔ)了。
接下來我們看看判斷上述 3 個(gè)條件是否滿足的主要流程:
第 1 步,循環(huán) in 條件括號(hào)中的每個(gè)值,看看是否都是常量,只要碰到一個(gè)不是常量的值,就結(jié)束循環(huán)。
上面代碼里面還干了另一件事,就是判斷 in 條件括號(hào)中的所有值,以及 in 條件字段是不是 json 類型。
args[0] 表示 in 條件字段,args[1~N] 是 in 條件括號(hào)中的值。
第 2 步,計(jì)算 in 條件括號(hào)中的所有值總共有幾種數(shù)據(jù)類型。
第 3 步,基于前兩步的結(jié)果,綜合起來判斷是否滿足二分法查找的 3 個(gè)前提條件。
判斷是否滿足二分法查找的 3 個(gè)前提條件,邏輯就是上面這些了,不算太復(fù)雜。
MySQL 對(duì)于 where row(filed1,field2) in ((1,5), (8,10), ...) 這種 row 類型的 in 條件也會(huì)盡量使用二分法查找,本文內(nèi)容不會(huì)涉及這些邏輯。
(2)填充數(shù)組并排序
要使用二分法查找,只滿足 3 個(gè)前提條件不算完事,還要求 in 條件括號(hào)中的值必須是已經(jīng)排好序的,接下來就該再往前推進(jìn)一步了,那就是對(duì) in 條件括號(hào)中的值進(jìn)行排序。
排序流程分為 2 步:
第 1 步,依然是用一個(gè)循環(huán),把 in 條件括號(hào)中的每個(gè)值都依次加入到數(shù)組中。
第 2 步,所有值都加入數(shù)組之后,對(duì)數(shù)組元素進(jìn)行排序。
不知道大家有沒有這樣的疑問:如果 in 條件括號(hào)中存在重復(fù)值,MySQL 會(huì)對(duì)數(shù)組中的元素去重嗎?
答案是:MySQL 只會(huì)把 in 條件括號(hào)中的值原樣加入數(shù)組,不會(huì)對(duì)數(shù)組中的元素去重。
到這里,使用二分法查找的準(zhǔn)備工作都已完成,這些準(zhǔn)備工作都是在查詢準(zhǔn)備階段進(jìn)行的。
(3)判斷記錄是否匹配 in 條件
server 層每從存儲(chǔ)引擎讀取到一條記錄,都會(huì)判斷記錄是否和 in 條件匹配。
有了前面構(gòu)造的有序數(shù)組,判斷是否匹配的邏輯就很簡(jiǎn)單了,就是從讀取出來的記錄中拿到 in 條件字段的值,然后用有序數(shù)組進(jìn)行二分法查找。
如果找到了,就說明記錄和 in 條件匹配。
以 in 條件括號(hào)中所有值都是整數(shù)為例,二分法查找代碼如下:
3、循環(huán)比較
前面介紹過,使用二分法查找執(zhí)行 in 條件判斷是有前提條件的,如果不滿足條件,那就只能退而使用原始的執(zhí)行方式了。
原始執(zhí)行方式就是循環(huán) in 條件括號(hào)中的值,逐個(gè)和存儲(chǔ)引擎讀取出來的記錄字段值進(jìn)行比較。
只要碰到一個(gè)相等的值,說明記錄和 in 條件匹配,就結(jié)束循環(huán),這條記錄需要返回給客戶端。
如果一直循環(huán)到 in 條件括號(hào)中的最后一個(gè)值,都沒有碰到和存儲(chǔ)引擎讀取出來的記錄字段值一樣的,說明記錄和 in 條件不匹配,這條記錄不需要發(fā)送給客戶端。
4、總結(jié)
不包含子查詢的 in 條件,和存儲(chǔ)引擎讀取出來的記錄字段值進(jìn)行比較,有二分法查找、循環(huán)比較兩種方式。
二分法查找雖然有 3 個(gè)條件限制,但實(shí)際上這些條件還是很容易滿足的,所以,多數(shù)情況下都能夠使用二分法查找以獲得更高執(zhí)行效率。
本文轉(zhuǎn)載自微信公眾號(hào)「一樹一溪」,可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系一樹一溪公眾號(hào)。