index merge的数据结构和成本评估

前面以案例的形式介绍了什么是index merge,以及它的使用场景。本文将介绍index merge实现的主要数据结构以及MySQL如何评估index merge的成本。在开始本文之前,需要先理解Range访问相关的数据结构介绍:SEL_ARG结构SEL_TREE结构

1. 概述:index merge的数据结构

index merge的主要数据结构仍然是存放在SEL_TREE中:

class SEL_TREE :public Sql_alloc { ... List<SEL_IMERGE> merges; ... };

在merges这个list中存放了所有可能的index merge。本文将从几个案例,来看看SEL_TREE/SEL_IMERGE如何代表一个index merge访问方式。本文将不再重复介绍SEL_ARG/SEL_TREE的Range相关结构。

SEL_IMERGE的主要成员是一个SEL_TREE的链表,每一个SEL_TREE代表了一个独立的索引条件,这个链表中多个条件共同构成这个index merge。我们通过两个案例看看一个SEL_TREE如何表示一个index merge。(这里需要注意,SEL_TREE既可以代表一个RANGE条件,也可以代表一个index merge;代表Range时,其merges成员为空)。

2. 案例1:简单的index merge

SELECT * FROM tmp_sel_tree where ( key1_part1 = 1 or (key1_part2 = 2 and key2_part1 = 3) ) or ( key3_part1 = 5 )

这是一个多个索引的index merge,且没有任何的range可以使用。or条件的三个分支,分表可以使用一个独立的索引,其构成的SEL_TREE结构如下:

SEL_TREE | |-->List<SEL_IMERGE> merges; | | / SEL_TREE-> SEL_ARG(key1_part1 = 1) \ SEL_IMERGE1 | SEL_TREE-> SEL_ARG(key2_part1 = 3) \ SEL_TREE-> SEL_ARG(key3_part1 = 5)

3. 案例2:单个查询多个index merge

SELECT * FROM tmp_sel_tree where ( key1_part1 = 1 or (key1_part2 = 2 and key2_part1 = 3) ) and ( key3_part1 = 5 or key2_part1 = 5)

这个案例中,And条件两边都可以各自使用index merge,MySQL可以选择其中任何一个执行。对应的SEL_TREE中,将会有多个SEL_IMERGE对象,每个SEL_IMERGE对象里面存储了多个独立的可以使用索引的条件(有独立的SEL_TREE表示):

SEL_TREE | \-->List<SEL_IMERGE> merges; | | / SEL_TREE-> SEL_ARG(key1_part1 = 1) | SEL_IMERGE1 | SEL_TREE-> SEL_ARG(key2_part1 = 3) | \ SEL_TREE-> SEL_ARG(key3_part1 = 5) | | / SEL_TREE-> SEL_ARG(key2_part1 = 5) \ SEL_IMERGE2 | \ SEL_TREE-> SEL_ARG(key3_part1 = 5)

MySQL会在选择执行计划时,逐一评估每个SEL_IMERGE的成本,然后选择最优的执行计划。

4. 成本计算

MySQL在计算index merge的成本时,分开考虑了ROR和non-ROR的场景。所以这里先单独介绍一下什么是ROR,后面再介绍MySQL如何区别对待ROR的成本计算。

4.1 什么是Rowid-Ordered Retrieval

Rowid-Ordered Retrieval简称ROR。看下面的说明。有基于索引的查询:

“key_1=c_1 AND … AND key_n=c_n”

该索引定义为:(key_1, …, key_N [,a_1, …, a_m]),且主键列为(a_1, …, a_m, b1, …, b_k),并且n >= N。

那么这个查询就是一个ROR查询。简单说明:对于该索引左前缀(key_1,…key_n)都是定值,对应该值的子树顺序是按照剩余索引列来排序的,而剩余的索引列又都是主键最左前缀,所以子树的顺序恰好同主键顺序相同。

(这一段可以参考函数is_key_scan_ror的注释和实现部分)

示例:

CREATE TABLE `tmp_index_merge` ( `id` int(11) NOT NULL, `key1_part1` int(11) NOT NULL, `key1_part2` int(11) NOT NULL, `key2_part1` int(11) NOT NULL, `key2_part2` int(11) NOT NULL, `key2_part3` int(11) NOT NULL, `key3_part1` int(11) NOT NULL DEFAULT '4', PRIMARY KEY (`id`), KEY `ind2` (`key2_part1`,`key2_part2`,`key2_part3`), KEY `ind1` (`key1_part1`,`key1_part2`,`id`), KEY `ind3` (`key3_part1`,`id`) ) ENGINE=InnoDB; explain select * from tmp_index_merge where (key1_part1 = 4333 and key1_part2 = 1657) or (key3_part1 = 2877); j+----+-------------+-----------------+-------------+---------------+-----------+---------+------+------+-------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-----------------+-------------+---------------+-----------+---------+------+------+-------------------------------------+ | 1 | SIMPLE | tmp_index_merge | index_merge | ind1,ind3 | ind1,ind3 | 8,4 | NULL | 2 | Using union(ind1,ind3); Using where | +----+-------------+-----------------+-------------+---------------+-----------+---------+------+------+-------------------------------------+ 这就是一个ROR的index查询。ROR在Explain的执行计划中并没有任何体现,通过在代码中设置断点可以观察到。在函数get_best_disjunct_quick中,代码会跳到标签skip_to_ror_scan处执行。

在对index merge的成本评估时,只有所有的SEL_TREE子树都是ROR的,对应的SEL_IMERGE才是ROR的。后面我们将看看ROR和non-ROR在成本评估上的不同。

4.2 成本概述

一个index merge是由多个SEL_TREE子树组成,每个SEL_TREE对应一个range操作(参考),所以每个SEL_TREE成本仍然会按照range操作类似各自计算成本,并累加。

各个SEL_TREE子树各自获取ROWIDs后,MySQL需要对这些ROWID进行去重,最后根据ROWID获取所有数据。去重操作其实是一个对多组ROWID归并排序的问题。对于ROR和non-ROR场景归并排序复杂度略有不同。对于non-ROR的场景,需要先进行分组排序,然后合并。而对于ROR,因为ROWID是顺序的,所以前面的分组排序就省略了,直接做合并操作,这让non-ROR和ROR在成本计算上有较大的不同。

在完成去重之后,最后是根据ROWID取出主键的成本(对应的二级索引里面取出的ROWID)。

一个细节:如果某个SEL_TREE对应的索引恰好是主键索引时,那么MySQL会在其他SEL_TREE子树扫描时,直接判断扫描出来的ROWID是否在主键对应的SEL_TREE的range内,如果这个ROWID已经存在,则不在记录。这样可以尽可能的减少归并排序的元素个数。我们称这部分成本味”二级ROWID过滤成本“。

4.3 SEL_TREE子树的成本

这部分成本计算与range成本计算相同(参考),这里会将多个子树成本单独计算并累加。

for (every SEL_TREE IN SEL_IMERGE){ cur_child= get_key_scans_params(param, *ptree, TRUE, FALSE, read_time); imerge_cost += (*cur_child)->read_cost; ...... }

4.4 non-ROR场景的成本计算

这里通过排序进行去重,是典型的归并排序,如果超过MySQL排序内存的限制,则是典型的外排序。先分组做红黑树排序,然后进行合并。成本分为几部分:创建红黑树、外排时磁盘读写、最后顺序读取排序结果。

4.4.1 去重复成本计算概述

这部分的成本可以完整的参考函数Unique::get_use_cost,这里做一个较为详细的补充说明。

对这个问题做一个简单的抽象:有两部分数据,第一部分有cpk_scan_records条,已排序。第二部分有non_cpk_scan_records未排序,现在需要返回去重后所有数据。单条数据大小为key_size,可用内存为max_in_memory_size。因为前面对第二部数据做了”二级ROWID过滤”,所以这部分ROWID跟第一部分没有重复。因此,仅这里的第二部分数据需要进行去重。去重通过一个排序实现。

简单的说,需要对non_cpk_scan_records条记录进行外排序,最大可用内存是max_in_memory_size,单条记录大小是key_size。排序分成两部分,对部分数据做排序,然后合并。

4.4.2 二级ROWID过滤成本

如果有子树SEL_TREE是对应主键聚簇索引,另一部分子树SEL_TREE对应二级索引,那么在遍历二级索引时将取出对应的ROWID,看看是否再聚簇索引的SEL_TREE子树中,如果是,那么可以忽略这个ROWID,以免重复计算(减少后面Unique操作)。这部分的成本计算为:

imerge_cost += non_cpk_scan_records / TIME_FOR_COMPARE_ROWID;

另外,这里记cpk_scan_records为主键聚簇索引对应的SEL_TREE返回的ROWID数量,non_cpk_scan_records为二级索引对应的所有SEL_TREE返回的ROWID数量。

4.4.3 排序比较成本

需要进行N=non_cpk_scan_records*key_size/max_in_memory_size次排序。在每次排序过程中,如果已经排序好的记录树m个,那么新增一条记录平均需要做log2(m+1)次比较操作,m取值是从1,2…N。比较操作的成本为log2((m+1)!),MySQL使用了如下公式计算log2((m+1)!):

\[n! \approx \sqrt{2{\pi}n}(\frac{n}{e})^n\]

\[\log{n!} \approx \log{\sqrt{2{\pi}n}} + n*\log{\frac{n}{e}} \]

这里log是2为底数,再使用\[log_{n}{m} = \frac{\lg{n}}{\lg{m}}\] 通过此公式底数都可以转换为10进行运算(这一部并不是必须的,不过MySQL是这样计算的)。

阶乘转换参考:斯特靈公式(口味略重,慎入)。

对应的代码段:

result+= n_full_trees * log2_n_fact(max_elements_in_tree + 1.0);
result /= TIME_FOR_COMPARE_ROWID;

4.4.4 外排序时候的磁盘IO成本

在外排的时候,需要对所有的数据进行一次IO操作,成本计算如下:

293 result += DISK_SEEK_BASE_COST * n_full_trees * max_elements_in_tree / IO_SIZE;
295 result += DISK_SEEK_BASE_COST * key_size * last_tree_elems / IO_SIZE;

第一行是完整树的IO成本,第二部分是最后一个可能不完整树的IO成本。

4.4.5 合并成本

最后是合并成本,这是一个典型的归并排序,是对K个有序列表进行归并,时间复杂度为:

\[O(N*\lg{K})\]

归并过程中有一次读写操作,IO和比较成本加起来就是合并的成本:

\[\frac{total\_buf\_elems*\log(n\_buffers)}{TIME\_FOR\_COMPARE\_ROWID*\log2} + 2*\frac{total\_buf\_elems*elem\_size}{IO\_SIZE} \]

total_buf_elems是总元素个数;n_buffers子树数量;elem_size为单个元素大小。

未尽的细节:MySQL一次最多对15(MERGEBUFF2)颗子树做归并。

4.4.6 最后的读取

这时,完成了所有的排序操作,最后是读取结果到内存的成本:

result += ceil((double)key_size*nkeys/IO_SIZE);

4.4.7 根据ROWID取出记录的成本

所有非聚簇索引扫描获得ROWID后,最后仍然需要根据这些ROWID获取记录。

对于索引组织表(聚簇索引,InnoDB),这部分的成本计算较为简单,假设聚簇索引的总page为total_pages,这里二级索引取出的rowid数量为rows,该表的总记录树为total_rows,那么成本为:

(rows / total_rows) *total_pages

代码参考:

imerge_cost += get_sweep_read_cost(param, non_cpk_scan_records);

4.5 ROR场景的成本计算

ROR的时候,去重时则少了对子队列的排序,直接是对多个已经排列好的队列做合并排序。所以这里的成本计算相对简单:索引读取,合并排序,最后是根据ROWID取出所有记录的成本。

4.5.1 索引读取成本

这部分计算与索引覆盖扫描计算相同。假设单个索引块大小为BS,索引字段长度味KL,ROWID长度为RL,总是假设索引块有50%为空,如果需要扫描的记录数为RS,那么这部分成本计算为:

\[\frac{RS}{\frac{1}{2}\frac{BS}{(KL+RL)}}\]

参考函数get_index_only_read_time的实现。

4.5.2 合并排序

这次合并排序,是对多个有序列表的合并。若有K个有序列表,总记录数味N,那么其成本为:

\[O(N*\lg{K})\]

这里N为各个SEL_TREE子树对应found_records之和(MySQL这里的计算略微不同)。

4.5.3 根据ROWID取出记录的成本

这部分成本于NON-ROR场景相同,对于索引组织表(聚簇索引,InnoDB),这部分的成本计算较为简单,假设聚簇索引的总page为total_pages,这里二级索引取出的rowid数量为rows,该表的总记录树为total_rows,那么成本为:

(rows / total_rows) *total_pages

在MySQL中,对于上面表达式的rows计算做了一些不一样的处理。这里说一下主要思想,MySQL假设每个SEL_TREE完全独立,总记录数味R,如果有三个SEL_TREE子树,记对应的记录数为R(1),R(2),R(3)。如果数据都均匀分布,那么去重后总记录数为:

(R(1)+R(2)+R(3)) – R(a)*(R(1)*R(2)+R(2)+R(3)+R(1)*R(3))/R(a)^2 + R(a)*((R(1)*R(2)*R3)/R(a)^3)

MySQL这里做了一个近似:

(R(1)+R(2)+R(3)) – R(a)*((R(1)*R(2)*R3)/R(a)^3)

MySQL利用这个近似值作为上面公式的rows。到这里ROR部分成本就完成了。

5 最后

最后,如果index merge的成本比其他执行计划的成本要更小的话,那么MySQL就会选择改执行计划。案例可以参考index merge介绍

3 responses to “index merge的数据结构和成本评估”

  1. […] (a) 只有ROR类型的索引使用才能作为Intersection执行计划的一部分(什么是ROR) […]

  2. Anonymous

    (R(1)+R(2)+R(3)) – R(a)*(R(1)*R(2)+R(2)+R(3)+R(1)*R(3))/R(a)^2 + R(a)*((R(1)*R(2)*R3)/R(a)^3) 应该是
    (R(1)+R(2)+R(3)) – R(a)*(R(1)*R(2)+R(2)*R(3)+R(1)*R(3))/R(a)^2 + R(a)*((R(1)*R(2)*R3)/R(a)^3) 吧?
    即R(2)+R(3) ==> R(2)*R(3)

  3. digdeep

    牛叉,您这几乎是在解析mysql源码了…
    请收膝盖

Leave a Reply

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