泛读了整个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 '\004',
max_flag = 0 '\000',
maybe_null = 1 '\001',
field = 0x7f651400d2f0,
min_value = 0x7f6518008e60 "",
max_value = 0x7f6518008bb0 "",
left = 0xcecac0,
……
color = SEL_ARG::BLACK,
type = SEL_ARG::KEY_RANGE
}
min_flag = 4 NEAR_MIN 即下界为开区间
max_flag = 0 表示上界为闭区间
516 #define NO_MIN_RANGE 1
517 #define NO_MAX_RANGE 2
518 #define NEAR_MIN 4
519 #define NEAR_MAX 8
520 #define UNIQUE_RANGE 16
…
maybe_null = 1 表示这个key part可以为空，存储值，第一个字节预留
min_value = 0x7f6518008e60 "" 表示取值下届，这里存储的值为0
max_value = 0x7f6518008bb0 "" 表示取值上界，这里存储的值为1，所以，这个SEL_ARG表示的区间为：
(0,1]
left/right/parent/prev/next_key_part/color等指针本文后续介绍
2.3 SEL_ARG链表：复杂的区间
（阅读本段，可以先阅读MySQL源码中关于SEL_ARG的注释部分：A construction block of the SEL_ARG-graph。opt_range.cc）
这次我先来看一个复杂的WHERE条件，及其对应的SER_ARG结构，然后通过几个从简单到复杂的案例，来分析之。假设有如下的WHERE条件，对应的索引为(kp1,kp2,kp3)：
select * from tmp_sel_arg where
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
(kp1=2 AND (kp3=11 OR kp3=14)) OR
(kp1=3 AND (kp3=11 OR kp3=14));
每一个"简单区间"都由一个SEL_ARG表示，对相同的key part，如果是多个OR条件则用指针prev/next链接，如果是相关的多个key part则用next_key_part指针链接。于是又如下关系图：
$ $
$ $
SEL_ARG(-∞, 1) $ ===> SEL_ARG [5,5] ===> $ SEL_ARG [10,10]
|^ $ $ |^
next|| $ $ next||
||prev $ $ ||prev
|| $ $ v
|| $ $ SEL_ARG [12,12]
|| $ $
v| $ $
SEL_ARG [2, 2] $=== next_key_part =====| $
|^ $ | $
next|| $ |===>$
||prev $ |===>$ SEL_ARG[11,11]
v| $ | $ |^
SEL_ARG [3, 3] $=== next_key_part =====| $ next||
$ $ ||prev
$ $ v|
SEL_ARG[14,14]
上图中，水平方向使用指针next_key_part串联，表示多个key part之间的and关系。垂直部分，是多个OR条件关联相同key part，通过指针next/prev关联。
除了上面的指针next/prev以及next_key_part，SEL_ARG对象还有三个指针left/right/parent指针，同一个key part的不同SEL_ARG对象组成的一颗红黑树就是靠这三个指针链接。在上图中SEL_ARG(-INF,1) SEL_ARG [2, 2] SEL_ARG [3, 3]通过这三个指针构成一颗红黑树。
上面这个案例比较复杂，但是完整的展示了SEL_ARG表示一个复杂的RANGE条件。下面我来看几个简单案例，来逐步认识SEL_ARG如何描述一个完整的RANGE条件。最后，再回头来看看上面这个结构。
2.3.1 简单条件 WHERE id > 10
这是一个最简单的区间。SEL_ARG(10,∞)，有标志位NEAR_MIN和NO_MAX_RANGE，仅单个SEL_ARG对象，所有指针都无效。
2.3.2 WHERE id > 2 and id < 10
id>2和id<10是两个可以合并的SEL_ARG，合并后为SEL_ARG(2,10)，两边开区间，故有标志位NEAR_MIN NEAR_MAX。
2.3.3 WHERE id > 10 or id <= 2
这个WHERE条件中有两个SEL_ARG，分别为SEL_ARG(10,∞)和SEL_ARG (-∞,2]。这是这两个条件是索引的同一个key part，用OR关联，所以这两个SEL_ARG一方面用next/prev指针关联，另一方面指针left/right/parent也让他们构成一颗简单的红黑树：
$
链表结构 $ 简单红黑树
SEL_ARG (-∞,2] $ SEL_ARG (10,∞)
|^ $ /(black)
next|| $ /
||prev $ /
v| $ SEL_ARG (-∞,2]
SEL_ARG (10,∞) $ (red)
$
$
2.3.4 WHERE id > 10 or id <= 2 or ( id >= 3 and id < 5 )
看下面的图，如果你真是从上面一直看下来的，应该不需要我解释什么了吧：
$
SEL_ARG (-∞,2] $ SEL_ARG [3,5)
|^ $ /\ Black
next|| $ / \
||prev $ / \
v| $ SEL_ARG (-∞,2] SEL_ARG (10,∞)
SEL_ARG [3,5) $ Red Red
|^ $
next|| $
||prev $
v| $
SEL_ARG (10,∞) $
$
2.3.5 WHERE id = 7 or id > 10 or id <= 2 or ( id >= 3 and id < 5 )
看下面的图，如果你真是从上面一直看下来的，应该不需要我解释什么了吧：
$
SEL_ARG [7,7] $
|^ $ RB-Tree
next|| $
||prev $ SEL_ARG [7,7]
v| $ /\ Black
SEL_ARG (10,∞) $ / \
|^ $ / \
next|| $ SEL_ARG (-∞,2] SEL_ARG (10,∞)
||prev $ /\Black Red
v| $ / \
SEL_ARG (-∞,2] $ / \
|^ $ SEL_ARG [3,5)
next|| $ RED
||prev $
v| $
SEL_ARG [3,5) $
$
到这里，就可以再回头看看2.3节给出的复杂案例了。
2.4 SEL_ARG链表结构的构造
本文不打算详述SEL_ARG链表构造详细过程（如果后续还有耐心的话，会写出来），这里仅给出一个简单的调用栈：
#0 get_mm_leaf # 根据简单谓词，构建SEL_ARG对象
#1 get_mm_parts # 根据简单谓词，将上一步的SEL_ARG构建，添加到SEL_TREE(使用函数sel_add)
#2 get_func_mm_tree> # 根据谓词Item_func::NE_FUNC/BETWEEN/IN_FUNC，分别构建SEL_TREE
#3 get_full_func_mm_tree> # 处理”特殊的等号” 这是啥，还没有太明白
#4 get_mm_tree # <递归根据简单谓词，构建SEL_TREE对象>
#5 get_mm_tree(递归) # 根据WHERE条件，构建SEL_TREE对象
#6 SQL_SELECT::test_quick_select # 根据WHERE条件，构建SEL_TREE，并评估每个RANGE找到多少条记录
#7 get_quick_record_count # 构建RANGE优化的SQL_SELECT对象
#8 make_join_statistics # ...
#9 JOIN::optimize
2.5 合
所以对于一个复杂的WHERE条件，MySQL会针对每一个可能使用Range的索引(possable key初始化在另一篇文章中介绍过)，生成一个对应的SEL_ARG链表结构，可以用cond_key_i表示，那么整个RANGE条件就可以看作下面的结构：
range_cond = (cond_key_1 AND cond_key_2 AND ... AND cond_key_N)
在MySQL中cond_key_i其实就是一个SEL_ARG指针，该指向第一个key part的红黑树的根节点。所有的cond_key_i数组存放SEL_TREE的成员keys中。SEL_TREE对象在get_mm_tree函数中构造。
3. RANGE代价的评估
如果你是泛读方式读到这里，那么建议你再回头看看SEL_ARG的数据结构，想想如果要遍历这棵树。如果是以精度的态度看到了这里，那么，谢谢，很荣幸能够分享一点点东西，相信稍加思考，便能够体会到，应该如何遍历这颗树了。如果理解了上面的SEL_ARG的结构，再来看Range代价评估就很简单了。主线剧情就是递归整个红黑树，然后每次尽可能的深度优先地沿着next_key_part走。
写得有点累了，这部分下次再写吧。算了，还是一口气写完吧。
这里，我通过一个案例来解释Range代价评估的过程。我们来看看下面这个SQL，看看他的SEL_ARG结构，然后看看Range代价评估的递归过程：
select
*
from
tmp_sel_arg
where
(kp1 = 5 and kp2 > 10) or
(kp1 = 10 and kp3 >20) or
(kp1 =8 and kp2 = 19 and (kp3 <=10 or kp3 >15) ) or
(kp1 > 12 and kp2 =5);
3.1 构建对应的SEL_ARG树
$ $
SEL_ARG[5,5] $ ===> SEL_ARG(10,+∞) $
|^ $ $
next|| $ $
||prev $ $
v| $ $
SEL_ARG[8,8] $ ===> SEL_ARG[19,19] $ ===> SEL_ARG(-∞,10]
|^ $ $ |^
next|| $ $ next||
||prev $ $ ||prev
|| $ $ v|
|| $ $ SEL_ARG(15,+∞)
|| $ $
v| $ $
SEL_ARG[10,10] $ =====================$=====> SEL_ARG(20,+∞)
|^ $ $
next|| $ $
||prev $ $
|| $ $
v| $ $
SEL_ARG(12,∞) $ ===> SEL_ARG[5,5] $
$ $
3.2 "深度优先"遍历SEL_ARG树
首先，对于每一个KEY PART是一颗红黑树，例如，我们看这里的第一个key part部分，即kp1对应的SEL_ARG，他们构成的红黑树如下：
SEL_ARG[8,8]
/\ Black
/ \
/ \
SEL_ARG[5,5] SEL_ARG[10,10]
Black /\ Black
/ \
/ \
SEL_ARG(12,∞)
Red
那么，遍历的顺序是先从kp1的范围SEL_ARG[8,8]入手，先左子树，再自身节点，然后右子树。为什么这里说是"深度优先"，例如当遍历到根节点SEL[8,8]时，如果这个对象的next_key_part指针不为空，那么将next_key_part部分加入；如果next_key_part的left/right/parent指针不为空（实时上parent总是为空，因为next_key_part总是指向红黑树的根节点），那么先遍历left节点，以此递归。
那么这里的遍历的顺序是：
SEL_ARG[5,5] SEL_ARG(10,+∞)
SEL_ARG[8,8] SEL_ARG[19,19] SEL_ARG(-∞,10]
SEL_ARG[8,8] SEL_ARG[19,19] SEL_ARG(15,+∞)
SEL_ARG[10,10]……(no kp2)……SEL_ARG(20,+∞)
SEL_ARG(12,∞) SEL_ARG[5,5]
3.3 筛选MySQL无法处理的Range
在MySQL中，如果是一个多列区间，那么除最后一列之外，其他列必须存在且是单点区间，才能使用Range优化。（单点区间是指[5,5]这样的等值区间）
所以，上面的例子中下面两个Range无法使用Range优化，MySQL直接跳过：
SEL_ARG[10,10]……(no kp2)……SEL_ARG(20,+∞)
SEL_ARG(12,∞) SEL_ARG[5,5]
代码逻辑：
if(
key_tree->next_key_part && # 是否有next_key_part
key_tree->next_key_part->part == key_tree->part+1 # 且next_key_part跟当前key part连续
)
{
if(min_key_length == max_key_length){ # 这是最后一个key part
#递归调用
goto end
}
}
…
table->file->records_in_range(…)
end:
3.4 调用存储引擎接口
最后，MySQL将陷入存储引擎接口records_in_range预估在这个范围大约有多少条记录。预估的办法，各个存储引擎各有不同，InnoDB通过在Range的上限和下限处各做一次统计，然后预估整个区间的记录数。
最后，最后，最后，MySQL评估所有的Range、全表扫描的代价，最后选出代价最小Range作为执行计划。（是不是最想看这部分，却一笔带过了！会有的:)）
参考
1. MySQL查询优化浅析 by 何登成
2. Internal Details of MySQL Optimizations @ MySQL Manual
3. Multi-Range Read Optimization @ MySQL Manual
4. Multi Range Read optimization @ Knowledge Base of MariaDB
5. Block-Based Join Algorithms @ Knowledge Base of MariaD
6. Understanding and control of MySQL Query Optimizer by Sergey Petrunya@2009
7. Multi Range Read interface By Sergey Petrunia
8. The range Join Type @MySQL Internal
9. Interaction Between Optimizer and Storage Engine
10. MySQL Source Code