希望能够往前走一点。泛读了整个MySQL Range优化的相关代码,这里将总结Range优化相关的数据结构。本文不是从宏观(High Level)角度介绍Range优化相关内容,如果看客对此感兴趣,建议绕过本文,直接阅读参考文献,相信会有收获。
已经连续写了几篇关于优化器相关的数据结构的博客了,只是希望需要的人是在需要的时候能够看到。
1. 背景知识
在开始介绍Range的主要数据结构之前,我们先看Range优化的一些概念和背景。依旧建议先阅读参考文件的[1-8],Sergey Petrunya写的PPT和文档质量都很高,很多图示,非常直观的展示了原理。
(1) 什么是Range条件? 参考Range Optimization@MySQL Manual 单列Range和多列Range
(2) 给定一个KEY(key1)对应的WHERE条件,如何将其转化成一个Range,下面是”简述”,详细参考单列Range:
SELECT * FROM t1 WHERE (key1 < 'abc' AND (key1 LIKE 'abcde%' OR key1 LIKE '%b')) OR (key1 < 'bar' AND nonkey = 4) OR (key1 < 'uux' AND key1 > 'z');
1.1 替换所有非RANGE查询为TRUE
先将所有非RANGE查询为TRUE,这样就不会漏掉任何数据,这里有key1 LIKE ‘%b’ nonkey = 4,所以有:
(key1 < 'abc' AND (key1 LIKE 'abcde%' OR TRUE)) OR (key1 < 'bar' AND TRUE) OR (key1 < 'uux' AND key1 > 'z')
1.2 移除恒真,或者恒假的表达式
(key1 < 'abc' AND (key1 LIKE 'abcde%' OR TRUE)) OR (key1 < 'bar' AND TRUE) OR (key1 < 'uux' AND key1 > 'z')
这其中,有:
(key1 LIKE 'abcde%' OR TRUE) 恒真 (key1 < 'uux' AND key1 > 'z') 恒假
继续替换:
(key1 < 'abc' AND TRUE) OR (key1 < 'bar' AND TRUE) OR (FALSE)
移除不必要的分支,移除原则:
OR分支中如果恒假,则可以移除;
OR分支中如果恒真,则整个OR恒真
AND分支中如果恒假,则整个
AND恒假 AND分支中如果恒真,则可以移除
这是一个递归的过程
1.3 递归结束
(key1 < 'abc') OR (key1 < 'bar')
1.4 合并有覆盖的区间
这里第一个RANGE是第二个RANGE的子集,这里又是OR,所以合并
(key1 < 'bar')
2 Range的数据结构
对任何的WHERE条件,MySQL在尝试Range优化时,会构造可以个SEL_TREE对象存储所有的Range。每一个索引,对应一个Range,所以有:
range_cond = (cond_key_1 AND cond_key_2 AND ... AND cond_key_N)
说明:针对某个索引key_i,MySQL会构造对应的RANGE,记为cond_key_1(如何根据索引简化WHERE条件?参考本文第一节)。MySQL会评估所有这些索引对应的RANGE,选择代价最小的作为执行计划的一部分。
2.1 “简单区间”
对某个索引,MySQL使用SEL_ARG对象来代表一个”简单区间”,进一步SEL_ARG构成整个cond_key_1对象。先来看看什么是一个简单区间:
min_value <=? table.keypartX <=? max_value ("?" 表示”=”可有可无)
这可以是一个非空的任何类型的区间:
(-INF,9) (-INF,9] (9,INF) [9,INF) (8,9) (8,9] [8,9)
任何一个复杂的Range表达式,都是由多个”简单区间”构成。
2.2 SEL_ARG:描述”简单区间”的对象
例如有如下查询:
select * from tmp_sel_arg where kp1 <= 1 and kp1 > 0;
那么对应SEL_ARG对象表示了区间(-INF,1],具体的:
(gdb) p tree->keys[0] $93 = (SEL_ARG *) 0x7f6518008bb8 (gdb) p *tree->keys[0] $94 = { min_flag = 4 '