where field in(...) 是怎么执行的？
The following article is from 一树一溪 Author 操盛春
作者丨操盛春
我们日常写 SQL 时，子查询应该算是常客了。MySQL 为子查询执行准备了各种优化策略，接下来我会写子查询各种优化策略是怎么执行的系列文章。
本文以包含最简单的 in 条件的查询入手，介绍 where field in (8,18,88,...) 这种值都是常量的 in 条件是怎么执行的。
这虽然不是子查询，我们就把它当成子查询的邻居好了，用它作为子查询系列的开篇，算是离子查询又近了一步 ^_^。
本文内容基于 MySQL 8.0.29 源码。
目录
1. 概述
2. 二分法查找
2.1 构造二分法查找数组
2.2 填充数组并排序
2.3 判断记录是否匹配 in 条件
3. 循环比较
4. 总结
正文
1. 概述
MySQL 为了能让 SQL 语句执行得更快一点，费尽心思进行了各种优化。
where field in (8,18,88,...) 这种值都是常量的 in 条件，看起来已经是最简单的形式了，执行过程似乎也没有什么可以优化的，但 MySQL 还是对它进行了优化。
这种 in 条件会有 2 种执行方式：
二分法查找 循环比较
MySQL 会优先使用二分法查找方式执行，如果不满足条件，再退而使用循环比较方式。
2. 二分法查找
判断 in 条件括号中的值和记录字段值是否匹配，相比于循环比较方式，二分法查找把时间复杂度从 O(N) 降为 O(logN)，大大减少了需要比较的次数，提升了 SQL 的执行效率。
2.1 构造二分法查找数组
二分法查找虽好，但需要满足一定条件才能使用：
in 条件括号中的所有值都是
常量，也就是说不能包含任何表中的字段、也不能包含系统变量（如@@tmp_table_size）或自定义变量（如@a），总之是不能包含任何可以变化的东西。in 条件括号中所有值的数据类型必须
相同。举个反例：where field in (1,8,'10')这种既包含整数又包含字符串的 in 条件就是不行的。in 条件括号中所有值的类型，以及
字段本身的类型都不能是json。
如果以上 3 个条件都满足，就具备使用二分法查找的基础了。
接下来我们看看判断上述 3 个条件是否满足的主要流程：
第 1 步，循环 in 条件括号中的每个值，看看是否都是常量，只要碰到一个不是常量的值，就结束循环。
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;
// 然后结束循环
break;
}
}
......
}
上面代码里面还干了另一件事，就是判断 in 条件括号中的所有值，以及 in 条件字段是不是 json 类型。
args[0]表示 in 条件字段，args[1~N]是 in 条件括号中的值。
第 2 步，计算 in 条件括号中的所有值总共有几种数据类型。
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 条件也会尽量使用二分法查找，本文内容不会涉及这些逻辑。
2.2 填充数组并排序
要使用二分法查找，只满足 3 个前提条件不算完事，还要求 in 条件括号中的值必须是已经排好序的，接下来就该再往前推进一步了，那就是对 in 条件括号中的值进行排序。
排序流程分为 2 步：
第 1 步，依然是用一个循环，把 in 条件括号中的每个值都依次加入到数组中。
第 2 步，所有值都加入数组之后，对数组元素进行排序。
// items 就是用于存放 in 条件括号中所有值的数组
bool in_vector::fill(Item **items, uint item_count) {
used_count = 0;
for (uint i = 0; i < item_count; i++) {
// in 条件括号中的值加入数组
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);
// 对数组元素进行排序
resize_and_sort();
// True = at least one null value found.
return used_count < item_count;
}
不知道大家有没有这样的疑问：如果 in 条件括号中存在重复值，MySQL 会对数组中的元素去重吗？
答案是：MySQL 只会把 in 条件括号中的值原样加入数组，不会对数组中的元素去重。
到这里，使用二分法查找的准备工作都已完成，这些准备工作都是在查询准备阶段进行的。
2.3 判断记录是否匹配 in 条件
server 层每从存储引擎读取到一条记录，都会判断记录是否和 in 条件匹配。
有了前面构造的有序数组，判断是否匹配的逻辑就很简单了，就是从读取出来的记录中拿到 in 条件字段的值，然后用有序数组进行二分法查找。
如果找到了，就说明记录和 in 条件匹配。
以 in 条件括号中所有值都是整数为例，二分法查找代码如下：
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. 循环比较
前面介绍过，使用二分法查找执行 in 条件判断是有前提条件的，如果不满足条件，那就只能退而使用原始的执行方式了。
原始执行方式就是循环 in 条件括号中的值，逐个和存储引擎读取出来的记录字段值进行比较。
只要碰到一个相等的值，说明记录和 in 条件匹配，就结束循环，这条记录需要返回给客户端。
如果一直循环到 in 条件括号中的最后一个值，都没有碰到和存储引擎读取出来的记录字段值一样的，说明记录和 in 条件不匹配，这条记录不需要发送给客户端。
longlong Item_func_in::val_int() {
......
for (uint i = 1; i < arg_count; i++) {
// in 条件括号中当前循环的值是 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 字段值转换为 cmp_type 类型
in_item->store_value(args[0]);
value_added_map |= 1U << (uint)cmp_type;
if (current_thd->is_error()) return error_int();
}
// 比较读取出来的记录的 in 字段值和当前循环的值是否相等
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 条件，和存储引擎读取出来的记录字段值进行比较，有二分法查找、循环比较两种方式。
二分法查找虽然有 3 个条件限制，但实际上这些条件还是很容易满足的，所以，多数情况下都能够使用二分法查找以获得更高执行效率。
点分享
点点赞
点在看