index merge的补充说明

在除了前面介绍的常见index merge的案例(Index Merge Union Access Algorithm)之外，还有一类很少见也比较特殊的index merge，多个索引扫描后进行交集，即 Index Merge Intersection。这类执行计划比较少见(因为MySQL需要ROR的原因)，但是，在合适的场景使用，效率仍然会有很大的提示，本文将看看MySQL优化器如何评估和选择此类执行计划。MySQL手册对此只是三言两语简单介绍了一下，这里做个较为详细的说明。

这类执行计划完整名称应该是：The Index Merge Intersection Access Algorithm，下文简称Intersection。

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\cap 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\cap B_1) = P(A)*P(B_1) \]

\[P(B_1) = \frac{R(b_1)}{R}\]

\[P(A\cap B_1) = P(A)*\frac{R(b_1)}{R} \]

这时就可以把条件\(b_1\)并入集合A，对应的选择度如上式。继续，考虑把条件\(b_2\)加入合计A。

\[P((A \cap B_1) \cap B_2) = P(A)*\frac{R(b_1)}{R}*P(B_2|A \cap B_1) \]

同样的，如果\(B_2\)和\(A \cap B_1\)不独立，即\(B_2\)是\(\{x|x \in A 或者 x \in B_1 \}\)的子集，那么

\[P(B_2|A \cap B_1) = 1\]

\[P((A \cap B_1) \cap B_2) = P(A)*\frac{R(b_1)}{R} \]

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

\[P(B_2|A \cap B_1) = P(B_2) = \frac{R(b_1 and b_2)}{R(b_1)} \]

\[P((A \cap B_1) \cap B_2) = P(A)*\frac{R(b_1)}{R} * \frac{R(b_1 and b_2)}{R(b_1)} = P(A)*\frac{R(b_1 and b_2)}{R} \]

MySQL将使用上面的方法计算多个条件合并的时候的选择度。 MySQL通过records_in_range来计算\(R(b_1 and b_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调研就告一段落了。

orczhou.com