【轉】MySQL松散索引掃描與緊湊索引掃描

在優化group by查詢的時候，一般的會想到兩個名詞：松散索引掃描（Loose Index Scan）和緊湊索引掃描（Tight Index Scan），因為通過這兩種索引掃描就可以高效快速弟完成group by操作。

group by操作在沒有合适的索引可用的時候，通常先掃描整個表提取資料并建立一個臨時表，然後按照group by指定的列進行排序。在這個臨時表裡面，對于每一個group的資料行來說是連續在一起的。完成排序之後，就可以發現所有的groups，并可以執行聚集函數（aggregate function）。可以看到，在沒有使用索引的時候，需要建立臨時表和排序。在執行計劃中通常可以看到“Using temporary; Using filesort”。

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

-----------------------
>個人介紹：
>
>** 高廣超** ：多年一線網際網路研發與架構設計經驗，擅長設計與落地高可用、高性能網際網路架構。目前就職于美團網，負責核心業務研發工作。

**本文首發在 [高廣超的簡書部落格](http://www.jianshu.com/u/2766e4cfc391) 轉載請注明！**

![image.png](http://upload-images.jianshu.io/upload_images/5401760-ac57cb57e6221417.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)