我們?nèi)粘?SQL 時，子查詢應該算是常客了。MySQL 為子查詢執(zhí)行準備了各種優(yōu)化策略，接下來我會寫子查詢各種優(yōu)化策略是怎么執(zhí)行的系列文章。
本文以包含最簡單的 in 條件的查詢?nèi)胧郑榻B where field in (8,18,88,...) 這種值都是常量的 in 條件是怎么執(zhí)行的。
這雖然不是子查詢，我們就把它當成子查詢的鄰居好了，用它作為子查詢系列的開篇，算是離子查詢又近了一步 ^_^。
本文內(nèi)容基于 MySQL 8.0.29 源碼。
正文
1、概述
MySQL 為了能讓 SQL 語句執(zhí)行得更快一點，費盡心思進行了各種優(yōu)化。
where field in (8,18,88,...) 這種值都是常量的 in 條件，看起來已經(jīng)是最簡單的形式了，執(zhí)行過程似乎也沒有什么可以優(yōu)化的，但 MySQL 還是對它進行了優(yōu)化。
這種 in 條件會有 2 種執(zhí)行方式：
MySQL 會優(yōu)先使用二分法查找方式執(zhí)行，如果不滿足條件，再退而使用循環(huán)比較方式。
2、二分法查找
判斷 in 條件括號中的值和記錄字段值是否匹配，相比于循環(huán)比較方式，二分法查找把時間復雜度從 O(N) 降為 O(logN)，大大減少了需要比較的次數(shù)，提升了 SQL 的執(zhí)行效率。
（1）構造二分法查找數(shù)組
二分法查找雖好，但需要滿足一定條件才能使用：
- in 條件括號中的所有值都是常量，也就是說不能包含任何表中的字段、也不能包含系統(tǒng)變量（如 @@tmp_table_size）或自定義變量（如 @a），總之是不能包含任何可以變化的東西。
- in 條件括號中所有值的數(shù)據(jù)類型必須相同。舉個反例：where field in (1,8,'10') 這種既包含整數(shù)又包含字符串的 in 條件就是不行的。
- in 條件括號中所有值的類型，以及字段本身的類型都不能是 json。
如果以上 3 個條件都滿足，就具備使用二分法查找的基礎了。
接下來我們看看判斷上述 3 個條件是否滿足的主要流程：
第 1 步，循環(huán) in 條件括號中的每個值，看看是否都是常量，只要碰到一個不是常量的值，就結束循環(huán)。
bool Item_func_in::resolve_type(THD *thd){
......
// 判斷 in 條件字段本身是不是 json 類型
bool compare_as_json = (args[0]->data_type() == MYSQL_TYPE_JSON);
......
bool values_are_const = true;
Item **arg_end = args + arg_count;
for (Item **arg = args + 1; arg != arg_end; arg++) {
// 判斷 in 條件括號中的值是不是 json 類型
compare_as_json |= (arg[0]->data_type() == MYSQL_TYPE_JSON);
// 判斷 in 條件括號中的值是不是常量
if (!(*arg)->const_item()) {
// in 條件括號中的值，只要有一個不是常量，就記錄下來
values_are_const = false;
// @todo - rewrite as has_subquery() ???
if ((*arg)->real_item()->type() == Item::SUBSELECT_ITEM)
dep_subq_in_list = true;
// 然后結束循環(huán)
break;
}
}
......
}上面代碼里面還干了另一件事，就是判斷 in 條件括號中的所有值，以及 in 條件字段是不是 json 類型。
args[0] 表示 in 條件字段，args[1~N] 是 in 條件括號中的值。
第 2 步，計算 in 條件括號中的所有值總共有幾種數(shù)據(jù)類型。
bool Item_func_in::resolve_type(THD *thd){
......
uint type_cnt = 0;
for (uint i = 0; i <= (uint)DECIMAL_RESULT; i++) {
if (found_types & (1U << i)) {
(type_cnt)++;
cmp_type = (Item_result)i;
}
}
......
}第 3 步，基于前兩步的結果，綜合起來判斷是否滿足二分法查找的 3 個前提條件。
bool Item_func_in::resolve_type(THD *thd){
......
/*
First conditions for bisection to be possible:
1. All types are similar, and
2. All expressions in <in value list> are const
3. No JSON is compared (in such case universal JSON comparator is used)
*/
bool bisection_possible = type_cnt == 1 && // 1
values_are_const && // 2
!compare_as_json; // 3
......
}判斷是否滿足二分法查找的 3 個前提條件，邏輯就是上面這些了，不算太復雜。
MySQL 對于 where row(filed1,field2) in ((1,5), (8,10), ...) 這種 row 類型的 in 條件也會盡量使用二分法查找，本文內(nèi)容不會涉及這些邏輯。
（2）填充數(shù)組并排序
要使用二分法查找，只滿足 3 個前提條件不算完事，還要求 in 條件括號中的值必須是已經(jīng)排好序的，接下來就該再往前推進一步了，那就是對 in 條件括號中的值進行排序。
排序流程分為 2 步：
第 1 步，依然是用一個循環(huán)，把 in 條件括號中的每個值都依次加入到數(shù)組中。
第 2 步，所有值都加入數(shù)組之后，對數(shù)組元素進行排序。
// items 就是用于存放 in 條件括號中所有值的數(shù)組
bool in_vector::fill(Item **items, uint item_count){
used_count = 0;
for (uint i = 0; i < item_count; i++) {
// in 條件括號中的值加入數(shù)組
set(used_count, items[i]);
/*
We don't put NULL values in array, to avoid erroneous matches in
bisection.
*/
// include this cell in the array.
if (!items[i]->null_value) used_count++;
}
assert(used_count <= count);
// 對數(shù)組元素進行排序
resize_and_sort();
// True = at least one null value found.
return used_count < item_count;
}
不知道大家有沒有這樣的疑問：如果 in 條件括號中存在重復值，MySQL 會對數(shù)組中的元素去重嗎？
答案是：MySQL 只會把 in 條件括號中的值原樣加入數(shù)組，不會對數(shù)組中的元素去重。
到這里，使用二分法查找的準備工作都已完成，這些準備工作都是在查詢準備階段進行的。
（3）判斷記錄是否匹配 in 條件
server 層每從存儲引擎讀取到一條記錄，都會判斷記錄是否和 in 條件匹配。
有了前面構造的有序數(shù)組，判斷是否匹配的邏輯就很簡單了，就是從讀取出來的記錄中拿到 in 條件字段的值，然后用有序數(shù)組進行二分法查找。
如果找到了，就說明記錄和 in 條件匹配。
以 in 條件括號中所有值都是整數(shù)為例，二分法查找代碼如下：
bool in_longlong::find_item(Item *item){
if (used_count == 0) return false;
packed_longlong result;
// 從記錄中讀取 in 字段的值到 result
val_item(item, &result);
// 讀取出來的記錄中，in 字段值為 null 就不用二分法查找了
if (item->null_value) return false;
// 對于非 null 值進行二分法查找
return std::binary_search(base.begin(), base.end(), result, Cmp_longlong());
}3、循環(huán)比較
前面介紹過，使用二分法查找執(zhí)行 in 條件判斷是有前提條件的，如果不滿足條件，那就只能退而使用原始的執(zhí)行方式了。
原始執(zhí)行方式就是循環(huán) in 條件括號中的值，逐個和存儲引擎讀取出來的記錄字段值進行比較。
只要碰到一個相等的值，說明記錄和 in 條件匹配，就結束循環(huán)，這條記錄需要返回給客戶端。
如果一直循環(huán)到 in 條件括號中的最后一個值，都沒有碰到和存儲引擎讀取出來的記錄字段值一樣的，說明記錄和 in 條件不匹配，這條記錄不需要發(fā)送給客戶端。
longlong Item_func_in::val_int(){
......
for (uint i = 1; i < arg_count; i++) {
// in 條件括號中當前循環(huán)的值是 null，跳過
if (args[i]->real_item()->type() == NULL_ITEM) {
have_null = true;
continue;
}
// 獲取 in 條件括號中的值，用什么類型進行比較，記為 cmp_type
Item_result cmp_type =
item_cmp_type(left_result_type, args[i]->result_type());
in_item = cmp_items[(uint)cmp_type];
assert(in_item);
if (!(value_added_map & (1U << (uint)cmp_type))) {
// 把讀取出來的記錄的 in 字段值轉(zhuǎn)換為 cmp_type 類型
in_item->store_value(args[0]);
value_added_map |= 1U << (uint)cmp_type;
if (current_thd->is_error()) return error_int();
}
// 比較讀取出來的記錄的 in 字段值和當前循環(huán)的值是否相等
const int rc = in_item->cmp(args[i]);
// rc 就是比較結果，false 表示相等
if (rc == false) return (longlong)(!negated);
have_null |= (rc == UNKNOWN);
if (current_thd->is_error()) return error_int();
}
......
}4、總結
不包含子查詢的 in 條件，和存儲引擎讀取出來的記錄字段值進行比較，有二分法查找、循環(huán)比較兩種方式。
二分法查找雖然有 3 個條件限制，但實際上這些條件還是很容易滿足的，所以，多數(shù)情況下都能夠使用二分法查找以獲得更高執(zhí)行效率。
本文轉(zhuǎn)載自微信公眾號「一樹一溪」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系一樹一溪公眾號。
