最新消息:

Range优化相关的数据结构

mysql admin 2740浏览 0评论

希望能够往前走一点。泛读了整个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 '04',
  max_flag = 0 '00',
  maybe_null = 1 '01',
  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

转载请注明:爱开源 » Range优化相关的数据结构

您必须 登录 才能发表评论!