【转】MySQL松散索引扫描与紧凑索引扫描

CREATE TABLE `t1` (
 
`c1` int(11) DEFAULT NULL,
`c2` int(11) DEFAULT NULL,
`c3` int(11) DEFAULT NULL,
`c4` int(11) DEFAULT NULL,
KEY `idx_g` (`c1`,`c2`,`c3`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
 
mysql> explain extended select c1,c2  from t1 group by c2 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: index
possible_keys: NULL
          key: idx_g
      key_len: 15
          ref: NULL
         rows: 15441
     filtered: 100.00
        Extra: Using index; Using temporary; Using filesort
```

MySQL建立的索引（B+Tree）通常是有序的，如果通过读取索引就完成group by操作，那么就可避免创建临时表和排序。因而使用索引进行group by的最重要的前提条件是所有group by的参照列（分组依据的列）来自于同一个索引，且索引按照顺序存储所有的keys（即BTREE index，而HASH index没有顺序的概念）。

MySQ有两种索引扫描方式完成group by操作，就是上面提到的松散索引扫描和紧凑索引扫描。在松散索引扫描方式下，分组操作和范围预测（如果有的话）一起执行完成的。在紧凑索引扫描方式下，先对索引执行范围扫描（range scan），再对结果元组进行分组。
 
-----------------
** 松散索引扫描（Loose Index Scan）**

松散索引扫描相当于Oracle中的跳跃索引扫描（skip index scan），就是不需要连续的扫描索引中得每一个元组，扫描时仅考虑索引中得一部分。当查询中没有where条件的时候，松散索引扫描读取的索引元组的个数和groups的数量相同。如果where条件包含范围预测，松散索引扫描查找每个group中第一个满足范围条件，然后再读取最少可能数的keys。松散索引扫描只需要读取很少量的数据就可以完成group by操作，因而执行效率非常高。使用松散索引扫描需要满足以下条件：

* 1）查询在单一表上。
* 2）group by指定的所有列是索引的一个最左前缀，并且没有其它的列。比如表t1（ c1,c2,c3,c4）上建立了索引（c1,c2,c3）。如果查询包含“group by c1,c2”，那么可以使用松散索引扫描。但是“group by c2,c3”(不是索引最左前缀)和“group by c1,c2,c4”(c4字段不在索引中)。
* 3）如果在选择列表select list中存在聚集函数，只能使用 min()和max()两个聚集函数，并且指定的是同一列（如果min()和max()同时存在）。这一列必须在索引中，且紧跟着group by指定的列。比如，select t1,t2,min(t3),max(t3) from t1  group by c1,c2。
* 4）如果查询中存在除了group by指定的列之外的索引其他部分，那么必须以常量的形式出现（除了min()和max()两个聚集函数）。比如，select c1,c3 from t1 group by c1,c2不能使用松散索引扫描。而select c1,c3 from t1 where c3 =  3 group by c1,c2可以使用松散索引扫描。
* 5）索引中的列必须索引整个数据列的值(full column values must be indexed)，而不是一个前缀索引。比如，c1 varchar(20), INDEX (c1(10)),这个索引没发用作松散索引扫描。
(前缀索引，与上面提到的索引的最左前缀是不同的)

如果查询能够使用松散索引扫描，那么执行计划中Etra中提示“ using index for group-by”。
```
mysql> explain select c1,c2  from t1 group by c1,c2 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: range
possible_keys: NULL
          key: idx_g
      key_len: 10
          ref: NULL
         rows: 15442
        Extra: Using index for group-by
```

自从5.5开始，松散索引扫描可以作用于在select list中其它形式的聚集函数，除了min()和max()之外，还支持：

* 1）AVG(DISTINCT), SUM(DISTINCT)和COUNT(DISTINCT)可以使用松散索引扫描。AVG(DISTINCT), SUM(DISTINCT)只能使用单一列作为参数。而COUNT(DISTINCT)可以使用多列参数。
* 2）在查询中没有group by和distinct条件。
* 3）之前声明的松散扫描限制条件同样起作用。

下面的查询可以使用松散索引扫描
```
SELECT COUNT(DISTINCT c1), SUM(DISTINCT c1) FROM t1;
 
SELECT COUNT(DISTINCT c1, c2), COUNT(DISTINCT c2, c1) FROM t1;
```

下面的查询不能够使用松散索引扫描

```
SELECT DISTINCT COUNT(DISTINCT c1) FROM t1;
 
SELECT COUNT(DISTINCT c1) FROM t1 GROUP BY c1;
```
-----------------
**紧凑索引扫描（Tight Index Scan）**
紧凑索引扫描可能是全索引扫描或者范围索引扫描，取决于查询条件。当松散索引扫描条件没有满足的时候，group by仍然有可能避免创建临时表。如果在where条件有范围扫描，那么紧凑索引扫描仅读取满足这些条件的keys（索引元组），否则执行全索引扫描。这种方式读取所有where条件定义的范围内的keys，或者扫描整个索引，因而称作紧凑索引扫描。对于紧凑索引扫描，只有在所有满足范围条件的keys被找到之后才会执行分组操作。

如果紧凑索引扫描起作用，那么必须满足：在查询中存在常量相等where条件字段（索引中的字段），且该字段在group by指定的字段的前面或者中间。来自于相等条件的常量能够填充搜索keys中的gaps，因而可以构成一个索引的完整前缀。索引前缀能够用于索引查找。如果要求对group by的结果进行排序，并且查找字段组成一个索引前缀，那么MySQL同样可以避免额外的排序操作。

c2在c1,c3之前，c2=‘a’填充这个坑，组成一个索引前缀，因而能够使用紧凑索引扫描。
select c1,c2,c3 from t1 where c2 = ‘a’ group by c1,c3
c1在索引的最前面，c1=a和group by c2,c3组成一个索引前缀，因而能够使用紧凑索引扫描。
select c1,c2,c3 from t1 where c1 = ‘a’ group by c2,c3
使用紧凑索引扫描，执行计划Extra一般显示“using index”，相当于使用了覆盖索引。
```
mysql> explain extended select c1,c2  from t1 where c1=2 group by c2 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ref
possible_keys: idx_g
          key: idx_g
      key_len: 5
          ref: const
         rows: 5
     filtered: 100.00
        Extra: Using where; Using index
```

松散索引扫描和紧凑索引扫描的最大区别是是否需要扫描整个索引或者整个范围扫描。

-----------------
**参考资料：**

高性能MySQL第三版，P235

MySQL Reference Manual,[GROUP BY Optimization](http://dev.mysql.com/doc/refman/5.5/en/group-by-optimization.html)
[MySQL 中 GROUP BY 基本实现原理](http://isky000.com/database/mysql_group_by_implement)

[原文地址](http://mdba.cn/2014/03/25/mysql%E6%9D%BE%E6%95%A3%E7%B4%A2%E5%BC%95%E6%89%AB%E6%8F%8F%E4%B8%8E%E7%B4%A7%E5%87%91%E7%B4%A2%E5%BC%95%E6%89%AB%E6%8F%8F/?utm_source=tuicool&utm_medium=referral)


------------------

### 其他资料
可以参考一下 阿里[玄惭](https://yq.aliyun.com/users/1368306804063034) 的一些博客
http://hidba.org/?spm=5176.100239.blogcont17090.3.V7H7Xs&p=380
https://yq.aliyun.com/articles/17090?spm=5176.153233.793261.20.yEk5WS
http://hidba.org/?spm=5176.100239.blogcont17090.3.V7H7Xs&p=380

-----------------------