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

前面以案例的形式介绍了什么是index merge，以及它的使用场景。本文将介绍index merge实现的主要数据结构以及MySQL如何评估index merge的成本。在开始本文之前，需要先理解Range访问相关的数据结构介绍：SEL_ARG结构，SEL_TREE结构。 1. 概述: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;
...
};</sel_imerge>

在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)</sel_imerge>

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)</sel_imerge>

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介绍。

原文地址：index merge的数据结构和成本评估, 感谢原作者分享。