前面以案例的形式介绍了什么是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>Nach dem Login kopieren
在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 )
Nach dem Login kopieren
这是一个多个索引的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>Nach dem Login kopieren
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)
Nach dem Login kopieren
这个案例中，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>Nach dem Login kopieren
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"
Nach dem Login kopieren
该索引定义为：(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处执行。
Nach dem Login kopieren
在对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;
......
}Nach dem Login kopieren
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;
Nach dem Login kopieren
另外，这里记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;
Nach dem Login kopieren
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;
Nach dem Login kopieren
第一行是完整树的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);
Nach dem Login kopieren
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)
Nach dem Login kopieren
MySQL这里做了一个近似：
(R(1)+R(2)+R(3)) - R(a)*((R(1)*R(2)*R3)/R(a)^3)
Nach dem Login kopieren
MySQL利用这个近似值作为上面公式的rows。到这里ROR部分成本就完成了。
5 最后
最后，如果index merge的成本比其他执行计划的成本要更小的话，那么MySQL就会选择改执行计划。案例可以参考index merge介绍。
原文地址：index merge的数据结构和成本评估, 感谢原作者分享。
