在除了前面介绍的常见index merge的案例(Index Merge Union Access Algorithm)之外，还有一类很少见也比较特殊的index merge，多个索引扫描后进行交集，即 Index Merge Intersection。这类执行计划比较少见(因为MySQL需要ROR的原因)，但是，在合适的场景使用，效率仍然会有很大的提示，本文将看看MySQL优化器如何评估和选择此类执行计划。MySQL手册对此只是三言两语简单介绍了一下，这里做个较为详细的说明。
这类执行计划完整名称应该是：The Index Merge Intersection Access Algorithm，下文简称Intersection。
目录 [hide]
1. 为什么需要考虑Intersection
考虑如下查询:
SELECT COUNT(*) FROM t1 WHERE key1=1 AND key2=1;
优化器可以考虑使用索引key1或者key2进行REF/Range访问，如果使用key1，那么key2=1则作为过滤条件。另外，优化器还会考虑使用Intersection，即同时使用索引key1和key2。这样做可能的好处是：
(a) 如果两次索引扫描后做交集，如果最后ROWID很少，则回表次数大大减少
(b) 如果扫描这两个索引能是覆盖扫描的话，则无需回表
对比ref/range访问方式，index merge需要额外多访问一个索引，ROWID需要做交集，所以需要额外的比较操作。优化器将各自计算ref/range和index merge的成本，然后选择成本较低作为最终的执行计划。
2. MySQL优化器的Intersection
前面描述了Intersection的两个好处，MySQL优化器先使用了一个较为复杂的算法来预估合并后ROWID数量；另外，如果发现有覆盖扫描，则无需回表，则成本会大大减少。
另外，因为index merge通常需要访问两个以上索引，成本通常不抵，MySQL选择Intersection的时候，加上了一个额外的要求：
(a) 只有ROR类型的索引使用才能作为Intersection执行计划的一部分(什么是ROR)
3. 优化器如何筛选Intersection使用的索引
3.1 算法说明
这里分了两个部分，先使用贪婪算法在所有的ROR索引中，组合出一组成本最小的做Intersection。如果这个“最小组合”不是覆盖索引，而且又存在覆盖索引，那么再做一次贪婪算法找到一个成本最小的覆盖查询，如果成本更小则选择之。
3.1.1 找到成本最小的ROR组合
这是一个贪婪算法，找到未必是全局最优的结果。这里简单描述一下算法(可以参考get_best_ror_intersect的注释和实现)：
初始：R是所有可用的ROR索引查询；S是空集；
R中的记录是按照需要扫描索引的大小排序(E(#records_matched) * key_record_length)
S= first(R); R= R-first(S);
min_cost= cost(S); min_scan= make_scan(S);
while (R is not empty)
{
firstR= R – first(R);
if (!selectivity(S + firstR < selectivity(S)))
continue;
S= S + first(R);
if (cost(S) < min_cost)
{min_cost= cost(S);min_scan= make_scan(S);}
}
return min_scan;
算法说明：每次从所有ROR中取出扫描成本最低的索引，判断加入该索引后成本是否会下降。如果成本下降，则将本ROR加入结果集；如果成本不会下降，那么忽略；
除此，MySQL还做了一个判断，如果新增ROR索引之后，会计算其选择度(selectivity)，只有当新增ROR索引会降低整体区分度的时候，这个索引才会被加入其中。这部分计算的目的，一方面是保证新增索引后一定会降低选择度，这通常都是满足的，只要新增的索引条件不是S集合的子集，一般都是满足的；另一方面，会顺便计算出新增索引后的选择度，这样就可以计算，多个索引合并后返回的记录数大约是多少。下面会单独介绍MySQL如何预估，两个条件交集命中的记录数。
3.1.2 计算两个索引交集命中的记录数
这个问题的抽象如下：有如下条件key1_p1=c1 and key1_p1=c2 and key2_p1=c3 and key2_p2=c4，现在已知key1_p1=c1 and key1_p1=c2的选择度是X，key2_p1=c3 and key2_p2=c4的选择度是Y，问，总体选择度是多少？
如果key1和key2是完全独立的，没有任何字段重复，那么按照均匀计算，交集后，总体选择度为X*Y，这部分是较为容易理解的。
如果key1和key2不是独立的，问题就较为复杂了，例如，key1_p1 = c1 和 key2_p1=c3 是两个一样的重复的条件，即索引key1和key2的某个字段相同。那么，如果按照上面的公式计算就非常不准确了。MySQL计算的办法，是逐个添加：
假设有集合A={key1_p1 = c1, key1_p1=c2}，对应的选择度记为P(A)，如果有索引条件：key2_p1=c3 and key2_p2=c4，MySQL先将key2_p1=c3加入集合A，并计算选择度；然后把key2_p2=c4加入集合A，并计算选择度。进一步抽象，有集合A，已知选择度为P(A)，现有索引条件key2对应的两个AND条件为b1和b2，现在演示如何逐个将b1和b2加入集合A并计算其选择度。
已知集合A，其选择度为P(A)；索引条件b1 and b2；并记 B1={b1}，B2={b2}；；
记R为该表总记录数，R(b1)表示条件b1对应的记录数，可以通过函数records_in_range计算；
P(X|Y)表示Y条件发生时的条件概率，这里假设都是均匀分布，选择度就是概率。且有P(X|Y) = P(X)*P(Y|X)；
那么，将集合B1合并到集合A之后，选择度计算为：
(1) 如果A，B1不独立，即对应条件b1属于集合A，那么，P(B1|A)=1。那么选择度不变，仍然是P(A);
(2) 如果A，B1独立，对应条件b1不属于集合A，那么有
这时就可以把条件b1并入集合A，对应的选择度如上式。继续，考虑把条件b2加入合计A。
同样的，如果B2和A∩B1不独立，即B2是{x|x∈A或者x∈B1}的子集，那么
如果两者独立，继续计算：
MySQL将使用上面的方法计算多个条件合并的时候的选择度。 MySQL通过records_in_range来计算R(b1andb2)。
MySQL在实现的时候，略有不同的地方是，为了尽可能少的避免records_in_range的调用次数，如果连续的多个条件都是同时独立或者同时都不独立，那么则会将这多个条件作为一个整理来计算。
3.1.3 找到成本最小覆盖索引组合
如果前面找到ROR组合不是覆盖查询，而且又存多个索引组合的覆盖索引的话，MySQL还会再做一次贪婪查找，尝试找到最优的覆盖索引组合，如果成本比之前的”最小成本”更小，则选择这组索引。
这部分实现参考函数get_best_covering_ror_intersect，没有特别需要说明的。
4. 成本的计算
如果上面计算好了选择度，Intersection的成本计算就很简单了。每次新增一个索引到index merge中的时候，先计算各个索引读取的成本(参考)，如果不是覆盖扫描则需要额外加上，根据ROWID取出记录的成本(参考)。
5. Intersection的案例
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
for i in `seq 1 5000` ; do mysql -vvv -uroot test
-e ‘insert into tmp_index_merge values (60000*rand(),5000*rand(),
5000*rand(),5000*rand(),5000*rand(),5000*rand(),2877)’; done
for i in `seq 1 5000` ; do mysql -vvv -uroot test
-e ‘insert into tmp_index_merge values (600000*rand(),4333,1657,
5000*rand(),5000*rand(),5000*rand(),5000*rand())’; done
explain select count(*) from tmp_index_merge where
(key1_part1 = 4333 and key1_part2 = 1657) and (key3_part1 = 2877)G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: tmp_index_merge
type: index_merge
possible_keys: ind1,ind3
key: ind3,ind1
key_len: 4,8
ref: NULL
rows: 3622
Extra: Using intersect(ind3,ind1); Using where; Using index
如果不满足ROR的条件，例如将上面案例的ind3索引的ID字段去掉，则不会再考虑使用Intersection。
alter table tmp_index_merge drop index ind3,add KEY `ind3` (`key3_part1`);
Query OK, 14137 rows affected (1.15 sec)
Records: 14137 Duplicates: 0 Warnings: 0
root@test 04:32:58>explain select * from tmp_index_merge where
(key1_part1 = 4333 and key1_part2 = 1657) and (key3_part1 = 2877)G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: tmp_index_merge
type: ref
possible_keys: ind1,ind3
key: ind1
key_len: 8
ref: const,const
rows: 3408
Extra: Using where
6. 最后
Intersection这类执行计划，因为需要满足ROR条件，所以较为少见。理想情况是，覆盖但非ROR成本也可能会很低，但是MySQL不考虑这点。另外，较新版本开始支持Index Condition Pushdown，这会大大降低选择ref/range的执行成本，Intersection的优势会大大下降。
到此，MySQL index merge调研就告一段落了。
Pingback: slow log中出现大量的binlog dump记录 – IT技术博客大全