登博开了一个头，希望能够往前走一点。泛读了整个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 }
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 ...
(0,1]
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
Leave a Reply