前面以案例的形式介绍了什么是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 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 mergeselect * 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 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 mergeselect * 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 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 retrievalrowid-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的数据结构和成本评估, 感谢原作者分享。