MySQL源码:Range优化相关的数据结构

登博开了一个头,希望能够往前走一点。泛读了整个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

    7 responses to “MySQL源码:Range优化相关的数据结构”

    1. admin

      补充:SEL_ARG->type == SEL_TREE::MAYBE 如果条件是field,例如WHERE id_status and reg_date = 10;

    2. […] 关于 上一篇:MySQL源码:Range优化相关的数据结构 […]

    3. […] MySQL源码:Range访问方式相关的数据结构–续 2013-01-25  |  20:24分类:MySQL  |  1 views 前文着重介绍了MySQL的WHERE条件如何针对单个索引构造对应的SEL_ARG结构,本文是一个补充,将简单介绍多个索引对应的SEL_TREE结构。 […]

    4. […] 这个案例也能够使用index merge。内部的实现比它表面上看起来要复杂,这里简单解释一下:MySQL在递归处理这个WHERE条件时,先处理前一部分(key1_part1 = 2 or key1_part1 = 7)。对于同一个索引的同一个字段进行or操作,MySQL会将其合并成一颗SEL_ARG树(具体参考),两个条件通过SEL_ARG的Next/prev指针连接。MySQL的range访问方式可以通过遍历这棵树(也可以参考前面这篇文章)。接着优化器再处理or的另一个分支(key2_part1 = 4)发现可以使用第二个索引,于是将index merge加入可能的执行计划列表(后续评估成本,再决定是否实用该访问方式)。 […]

    5. louis

      nice work.

    6. […] 这个案例也能够使用index merge。内部的实现比它表面上看起来要复杂,这里简单解释一下:MySQL在递归处理这个WHERE条件时,先处理前一部分(key1_part1 = 2 or key1_part1 = 7)。对于同一个索引的同一个字段进行or操作,MySQL会将其合并成一颗SEL_ARG树(具体参考),两个条件通过SEL_ARG的Next/prev指针连接。MySQL的range访问方式可以通过遍历这棵树(也可以参考前面这篇文章)。接着优化器再处理or的另一个分支(key2_part1 = 4)发现可以使用第二个索引,于是将index merge加入可能的执行计划列表(后续评估成本,再决定是否实用该访问方式)。 […]

    Leave a Reply

    Your email address will not be published. Required fields are marked *