索引失效

引言

• 在一个列或多个列上建立索引，其本质是为这些列上的数据组织成平衡二叉树(B+Tree)之后，将基于全表扫描的时间复杂度优化为基于二分查找的时间复杂度，以大大提升效率。
• 每一条sql语句在提交到Mysql服务端后，在真正执行前都会经过优化器优化，优化器会判断能否使用索引，如果有多个索引可以使用，还会进行成本计算来选择一个较优的执行方式。
• 不恰当的sql语句往往无法利用索引来进行查询优化，反而为创建索引白白浪费磁盘空间。
• 下面介绍几种会造成索引失效的不恰当查询方法。

最左前缀匹配原则

• 多数索引失效的情况都发生在联合索引的情况，比如在使用联合索引时没有遵守最左前缀匹配原则。
• 先说下什么是最左前缀匹配原则，首先创建一个简单的表t1，并在a, b列上添加联合索引idx_a_b。

 CREATE TABLE t1(
      id INT NOT NULL auto_increment,
      a  INT NOT NULL,
      b  Int NOT NULL,
      PRIMARY KEY(id),
      KEY idx_a_b(a, b)
     );

• 再给表中添加一些演示数据

INSERT INTO t1 VALUES(1, 1, 1),(2,1,2),(3,2,2),(4,2,3),(5,2,4),(6,3,1),(7,3,2);
SELECT * FROM t1;
+----+---+---+
| id | a | b |
+----+---+---+
|  1 | 1 | 1 |
|  2 | 1 | 2 |
|  3 | 2 | 2 |
|  4 | 2 | 3 |
|  5 | 2 | 4 |
|  6 | 3 | 1 |
|  7 | 3 | 2 |
+----+---+---+

• 我们先给出一些符合最左匹配原则和一些不符合最左匹配原则的示例，再分析具体原因。

SELECT * FROM t1 WHERE a = xxx AND b = xxx;  # 符合
SELECT * FROM t1 WHERE a = xxx AND b = xxx;  # 符合
SELECT * FROM t1 WHERE b = xxx;              # 不符合

可以看到最后一条查询语句跳过了a直接对b进行查询，不符合最左前缀匹配原则。（以上只是一些示例，还有很多复杂的情况。）

• 因为我们在列a和b上添加了联合索引idx_a_b, Mysql会为我们在磁盘上建立一个二级索引(非聚簇索引)，我们假设这个二级索引如下所示（只是一个简单的示意图，叶子结点之间还有双向链表相连，且叶节点还会存储主键值）
  idx_a_b索引结构
• 这颗B+树中会根据列a进行排序，在列a值相同的情况下，再根据列b的值进行排序。
• 现在我们查询(2,2)

SELECT * FROM t1 WHERE a=2 AND b=2;
+----+---+---+
| id | a | b |
+----+---+---+
|  3 | 2 | 2 |
+----+---+---+

• 再使用EXPLAIN对该条语句进行分析

EXPLAIN SELECT * FROM t1 WHERE a=2 AND b=2;
+------+-------------+-------+------+---------------+---------+---------+-------------+------+-------------+
| id   | select_type | table | type | possible_keys | key     | key_len | ref         | rows | Extra       |
+------+-------------+-------+------+---------------+---------+---------+-------------+------+-------------+
|    1 | SIMPLE      | t1    | ref  | idx_a_b       | idx_a_b | 8       | const,const |    1 | Using index |
+------+-------------+-------+------+---------------+---------+---------+-------------+------+-------------+

• 发现其确实是利用到了我们设置的索引idx_a_b，其具体步骤:

1. 在B+Tree的第一层与非叶子结点(2,4)比较，因为列a值都相同，此时再比较列b的值。
2. 因为 b的值,此时确定到左侧的叶节点上继续查找。
3. 在左侧的页节点内部继续使用同上二分查找的方式定位到目的节点，最后再根据主键值（未画出）进行回表操作。

• 同理，我们分析一下SELECT * FROM t1 WHERE a = 2;

EXPLAIN SELECT * FROM t1 WHERE a=2;
+------+-------------+-------+------+---------------+---------+---------+-------+------+-------------+
| id   | select_type | table | type | possible_keys | key     | key_len | ref   | rows | Extra       |
+------+-------------+-------+------+---------------+---------+---------+-------+------+-------------+
|    1 | SIMPLE      | t1    | ref  | idx_a_b       | idx_a_b | 4       | const |    3 | Using index |
+------+-------------+-------+------+---------------+---------+---------+-------+------+-------------+

可以看到也成功利用索引查找到列第一个满足a=2的记录，然后再通过记录间的前后指针将满足要求的记录全部查找出来。

• 再看一下违反了最左前缀匹配原则的查询SELECT * FROM t1 WHERE b = 2

EXPLAIN SELECT * FROM t1 WHERE b=2;
+------+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                    |
+------+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
|    1 | SIMPLE      | t1    | index | NULL          | idx_a_b | 8       | NULL |   13 | Using where; Using index |
+------+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+

那么问题来了，虽然possible_keys确实等于null，但是实际上key里却用到了idx_a_b索引，不是说违反了最左前缀匹配原则，会发生索引失效么？其实使用了索引和以二分查找的方式使用索引是不一样的，这里虽然用到了idx_a_b索引，也只是因为这个联合索引上有b这个列，并且在这个索引上使用了扫描的方式来获取满足条件的主键值再进行回表操作，与之前利用二分查找的方式相比是很慢的。 我们还可以注意到ref这一列的值为NULL,也就是说确实没用到任何等值匹配条件，索引确实失效了。

• 为什么违反了最左前缀匹配原则的查询语句就会导致索引失效呢？我们把上图叶子节点的值中a列不考虑，只看b列，则其为1、2、2、3、4、1、2。很显然是无序的，而能够使用二分查找的最根本条件就是有序，所以自然也就无法利用二分查找来提升效率，正确的使用索引了。

利用索引优化排序操作

• 前面我们说了索引已经为我们将某些列上的数据组织成有序，那么当在查询中涉及排序操作时，很多时候可以避免在内存中排序，提升效率。比如以下三条语句。

EXPLAIN SELECT * FROM t1 ORDER BY a, b;
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
|    1 | SIMPLE      | t1    | index | NULL          | idx_a_b | 8       | NULL |   13 | Using index |
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+

 EXPLAIN SELECT * FROM t1 ORDER BY a;
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
|    1 | SIMPLE      | t1    | index | NULL          | idx_a_b | 8       | NULL |   13 | Using index |
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
EXPLAIN SELECT * FROM t1 ORDER BY  b;
+------+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                       |
+------+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+
|    1 | SIMPLE      | t1    | index | NULL          | idx_a_b | 8       | NULL |   13 | Using index; Using filesort |
+------+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+

前两条因为尊从了最左前缀匹配原则，取出的数据本身就是有序的，而最后一条可以看到了使用了Using filesort，因为以b列中的元素本身不是有序的，所以需要在内存中再进行一次排序。