index merge的补充说明

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条件为b 1

和b 2

，现在演示如何逐个将b 1

和b 2

加入集合A并计算其选择度。

已知集合A，其选择度为P(A)；索引条件b 1

and b 2

；并记 B 1 ={b 1 }，B 2 ={b 2 }；

；

记R为该表总记录数，R(b 1 )

表示条件b 1

对应的记录数，可以通过函数records_in_range计算；

P(X|Y)

表示Y条件发生时的条件概率，这里假设都是均匀分布，选择度就是概率。且有P(X|Y) = P(X)*P(Y|X)；

那么，将集合B 1

合并到集合A之后，选择度计算为：

P(A∩B 1 )=P(A)∗P(B 1 |A)

(1) 如果A，B 1

不独立，即对应条件b 1

属于集合A，那么，P(B 1 |A)=1

。那么选择度不变，仍然是P(A)

;

(2) 如果A，B 1

独立，对应条件b 1

不属于集合A，那么有

P(A∩B 1 )=P(A)∗P(B 1 )

P(B 1 )=R(b 1 )R

P(A∩B 1 )=P(A)∗R(b 1 )R

这时就可以把条件b 1

并入集合A，对应的选择度如上式。继续，考虑把条件b 2

加入合计A。

P((A∩B 1 )∩B 2 )=P(A)∗R(b 1 )R ∗P(B 2 |A∩B 1 )

同样的，如果B 2

和A∩B 1

不独立，即B 2

是{x|x∈A或者x∈B 1 }

的子集，那么

P(B 2 |A∩B 1 )=1

P((A∩B 1 )∩B 2 )=P(A)∗R(b 1 )R

如果两者独立，继续计算：

P(B 2 |A∩B 1 )=P(B 2 )=R(b 1 andb 2 )R(b 1 )

P((A∩B 1 )∩B 2 )=P(A)∗R(b 1 )R ∗R(b 1 andb 2 )R(b 1 ) =P(A)∗R(b 1 andb 2 )R

MySQL将使用上面的方法计算多个条件合并的时候的选择度。 MySQL通过records_in_range来计算R(b 1 andb 2 )

。

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调研就告一段落了。