[MySQL]オプティマイザトレースでインデックス選択根拠を調べる[単一テーブル編]

この記事は [Lancers（ランサーズ） Advent Calendar 2020](https://qiita.com/advent-calendar/2020/lancers) 6日目のエントリーです。

バックエンドエンジニア＆DBRE の [まみー](https://twitter.com/mamy1326) です。
僕は MySQL が大好きです。

普段 ORM 任せでクエリを意識しないことも多い昨今。
だからこそクエリ [^1] とインデックス [^2] くらいはわかる僕らでありたいと思うんですが、思ってたんと違うインデックスが選択されることありますよね。

じゃあ理由を明確にして本質を知った上で対応しよう。
というわけでインデックス選択の根拠をオプティマイザが算出するコストから検証してみます。

オプティマイザトレースの使い方をサクッと知りたい方は [コチラ](https://qiita.com/mamy1326/private/08c299949dd60dd6590a#%E3%82%AA%E3%83%97%E3%83%86%E3%82%A3%E3%83%9E%E3%82%A4%E3%82%B6%E3%83%88%E3%83%AC%E3%83%BC%E3%82%B9) からご覧ください。

## 条件

- 単一テーブル
- 複合インデックス
    - 1番目で ID で絞り込み
    - 2番目で前方一致 LIKE 検索

実例 [^3] として、TODO管理情報を

- ユーザーID
- キーワード前方一致

で検索していきます。

### テーブル
TODO管理をするテーブルはこんな感じです。

```sql
mysql> show create table todos\G
*************************** 1. row ***************************
       Table: todos
Create Table: CREATE TABLE `todos` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `user_id` int(11) NOT NULL,
  `keyword` varchar(255) NOT NULL,
  `content` varchar(255) NOT NULL,
  `started` datetime DEFAULT NULL,
  `expired` datetime DEFAULT NULL,
  `completed` datetime DEFAULT NULL,
  `created` datetime NOT NULL,
  `modified` datetime NOT NULL,
  PRIMARY KEY (`id`)
)
1 row in set (0.01 sec)
```

### データ
検証用には十分かなというレコード数です。

```sql
mysql> select count(id) from todos;
+-----------+
| count(id) |
+-----------+
|    350932 |
+-----------+
1 row in set (0.89 sec)
```

前方一致 LIKE 対象のデータパターンとしては、ある程度までは前方一致する数が多く、さらに絞り込める構造になっているとします。
上位 10 件しか表示していませんが、keyword の最後尾に ID 的な値があるため、3位以降のカーディナリティは高いです。

```sql
mysql> select keyword, count(keyword) as key_count from todos group by keyword order by keyword_count desc limit 10;
+-----------------------------------------------+---------------+
| keyword                                       | keyword_count |
+-----------------------------------------------+---------------+
| UserProjectFeedbackConfirmation               |         40325 |
| ClientProjectFeedbackConfirmation             |         35189 |
| ClientProjectUploadedFileConfirmation/aaaaaaa |            33 |
| UserProjectUploadedFileConfirmation/bbbbbbb   |            22 |
| ClientProjectUploadedFileConfirmation/ccccccc |            20 |
| ClientProjectUploadedFileConfirmation/ddddddd |            20 |
| ClientProjectUploadedFileConfirmation/eeeeeee |            17 |
| ClientProjectUploadedFileConfirmation/fffffff |            17 |
| ClientProjectUploadedFileConfirmation/ggggggg |            15 |
| ClientProjectUploadedFileConfirmation/hhhhhhh |            15 |
+-----------------------------------------------+---------------+
```

また、今回は user_id で最初に絞るので、ある程度レコード数が多いユーザーを選択するものとします。

```sql
mysql> select count(user_id) as count, user_id from todos group by user_id order by count desc limit 5;
+-------+----------+
| count | user_id  |
+-------+----------+
|  5433 | 11000501 |
|  1942 | 20018912 |
|  1746 | 11000194 |
|  1406 | 21354356 |
|  1119 | 22663348 |
+-------+----------+
5 rows in set (0.08 sec)
```

## クエリ
該当ユーザーの Client に対応する TODO 一覧を取得する、シンプルなクエリです。
LIKE の文字列は条件によりどんどん絞り込める (文字列が長くなる) ものとします。

```sql
SELECT
    *
FROM
    todos
WHERE
    user_id=11000501
AND
    keyword LIKE 'Client%'
```

## インデックス
`user_id_keyword` が今回追加したインデックスで、これが使われて欲しいです。
他は既存のインデックスです。

```sql
mysql> show index from todos;
+-------+------------+---------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name                  | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+---------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| todos |          0 | PRIMARY                   |            1 | id          | A         |      342442 |     NULL | NULL   |      | BTREE      |         |               |
| todos |          1 | user_id_keyword_completed |            1 | user_id     | A         |       28574 |     NULL | NULL   |      | BTREE      |         |               |
| todos |          1 | user_id_keyword_completed |            2 | keyword     | A         |      291843 |     NULL | NULL   |      | BTREE      |         |               |
| todos |          1 | user_id_keyword_completed |            3 | completed   | A         |      287793 |     NULL | NULL   |      | BTREE      |         |               |
| todos |          1 | user_id_completed         |            1 | user_id     | A         |       27407 |     NULL | NULL   |      | BTREE      |         |               |
| todos |          1 | user_id_completed         |            2 | completed   | A         |       41562 |     NULL | NULL   |      | BTREE      |         |               |
| todos |          1 | user_id_keyword           |            1 | user_id     | A         |       27861 |     NULL | NULL   |      | BTREE      |         |               |
| todos |          1 | user_id_keyword           |            2 | keyword     | A         |      288007 |     NULL | NULL   |      | BTREE      |         |               |
+-------+------------+---------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
8 rows in set (0.00 sec)
```

## EXPLAIN（実行計画）
検索条件に合わせて新規で作った `user_id_keyword` インデックスではなく、既存の `user_id_completed ` が選択されました。
ぐぬぬ、なぜ…

```sql
mysql> explain SELECT
    ->     *
    -> FROM
    ->     todos
    -> WHERE
    ->     user_id=11000501
    -> AND
    ->     keyword LIKE 'Client%'\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: todos
   partitions: NULL
         type: ref
possible_keys: user_id_keyword_completed,user_id_completed,user_id_keyword
          key: user_id_completed
      key_len: 4
          ref: const
         rows: 5432
     filtered: 11.11
        Extra: Using where
1 row in set, 1 warning (0.00 sec)
```

実行計画を、[漢のコンピュータ道　MySQLのEXPLAINを徹底解説!!](http://nippondanji.blogspot.com/2009/03/mysqlexplain.html) から引用しながら見ていきます。

### type: ref
> ref・・・ユニーク（PRIMARY or UNIQUE）でないインデックスを使って等価検索（WHERE key = value）を行った時に使われるアクセスタイプ。

今回、 `key = value` なのは `user_id=11000501` なので、この部分だけがインデックスで検索されたことになります。

### key: user_id_completed
> オプティマイザによって選択されたキー。

読んで字の如く。このあとでトレースをし、オプティマイザが選択したコストを見ていきます。
短いキー長、今回は user_id でレコード取得し、その結果に対しインデックスを使わず LIKE 検索した方が高速である (コストが低い) と判断されたのかな、という推測ができます。

### key_len: 4
> 選択されたキーの長さ。インデックスの走査は、キー長が短い方が高速である。インデックスをつけるカラムを選ぶ時にはそのことを念頭に置いて欲しい。

`user_id int(11) ` で Integer なので、4 byte、つまり user_id の検索にしかインデックスが利用されていない、ということがわかります。

### rows: 5432
> そのテーブルからフェッチされる行数の見積もりである。このフィールドはあくまでもテーブル全体の行数やインデックスの分散具合から導き出された大まかな見積もりなので、実際にフェッチされる正確な行数ではないので注意が必要されたい。

ユーザーID別に件数を見た際、総件数は以下でした。

```sql
+-------+----------+
| count | user_id  |
+-------+----------+
|  5433 | 11000501 |
```

ほとんど全てのレコードが検索対象として見積もられていることがわかります。
ここで以下が推測できました。

- 先頭が user_id であるインデックスを選択して行数・コスト計算
- 最も行数・コストの少ないインデックスを選択

なぜ、今回 WHERE 句で絞り込むために作ったインデックスが選択されず、既存のインデックスが使われてしまうのか。
ここまでの推測が正しいのか。
それを調べるため、オプティマイザトレースをしてみます。

## オプティマイザトレース

### 前準備1：オプティマイザトレースを有効化する
オプティマイザトレースは [有効化](https://dev.mysql.com/doc/refman/5.6/ja/optimizer-trace-table.html) しないとトレースしてくれません。
なので [optimizer_trace 変数](https://dev.mysql.com/doc/internals/en/optimizer-trace-system-variable.html) に以下の設定を実行します。

```sql
mysql> show variables like 'optimizer_trace';
+-----------------+--------------------------+
| Variable_name   | Value                    |
+-----------------+--------------------------+
| optimizer_trace | enabled=off,one_line=off |
+-----------------+--------------------------+
1 row in set (0.00 sec)

mysql> SET optimizer_trace="enabled=on";
Query OK, 0 rows affected (0.00 sec)

mysql> show variables like 'optimizer_trace';
+-----------------+-------------------------+
| Variable_name   | Value                   |
+-----------------+-------------------------+
| optimizer_trace | enabled=on,one_line=off |
+-----------------+-------------------------+
1 row in set (0.00 sec)
```

`one_line` をオンにすると空白も改行もなく1行で表示されます。人間ではなくパーサーに渡すためのようですね。

なお、設定時の注意点としては以下が挙げられます。

- 普段は無効になってるのでトレースしてくれない
    - 常時有効にするとメモリに影響するので、使うときだけ有効にすること
    - 都度コマンドで有効にした場合は、quit すれば設定は無効になります
    - とはいえ設定を戻すことは忘れずに

### 前準備2：利用するメモリ容量を適切に設定する
オプティマイザトレースはメモリを適切に割り当てないと、出力結果が全部表示されない場合があります。
今回はデフォルト値が少なく、トレース結果の JSON が途中で欠落していました。

なので以下のように [optimizer_trace_max_mem_size 変数](https://dev.mysql.com/doc/internals/en/tracing-memory-usage.html) 設定を実行します。
1 MB あれば大丈夫でした。

```sql
mysql> show variables like 'optimizer_trace_max_mem_size';
+------------------------------+-------+
| Variable_name                | Value |
+------------------------------+-------+
| optimizer_trace_max_mem_size | 16384 |
+------------------------------+-------+
1 row in set (0.00 sec)

mysql> SET optimizer_trace_max_mem_size = 1048576;
Query OK, 0 rows affected (0.00 sec)

mysql> show variables like 'optimizer_trace_max_mem_size';
+------------------------------+---------+
| Variable_name                | Value   |
+------------------------------+---------+
| optimizer_trace_max_mem_size | 1048576 |
+------------------------------+---------+
1 row in set (0.00 sec)
```

### クエリ実行
先ほどと同じく、EXPLAIN を実行します。
実際に結果を取得しなくても、オプティマイザトレースの結果は変わりません。

```sql
mysql> explain SELECT
    ->     *
    -> FROM
    ->     todos
    -> WHERE
    ->     user_id=11000501
    -> AND
    ->     keyword LIKE 'Client%'\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: todos
   partitions: NULL
         type: ref
possible_keys: user_id_keyword_completed,user_id_completed,user_id_keyword
          key: user_id_completed
      key_len: 4
          ref: const
         rows: 5432
     filtered: 11.11
        Extra: Using where
1 row in set, 1 warning (0.00 sec)
```

注意点としては以下が挙げられます。

- この1回がトレース結果としてメモリに保持される
    - 2回目以降は上書きされるので、都度トレース結果をみる必要がある

### トレース結果取得
クエリを実行すると、トレース結果がメモリ上に記録されます。
あとは以下のSQLで、トレース結果をSELECTしてあげればOKです。

```sql
mysql> SELECT * FROM INFORMATION_SCHEMA.OPTIMIZER_TRACE\G
*************************** 1. row ***************************
                            QUERY: EXPLAIN SELECT 
(省略、実行したSQLが表示されます)
                            TRACE: {
(後述、オプティマイザトレースの内容)
}
MISSING_BYTES_BEYOND_MAX_MEM_SIZE: 0 --メモリ不足で切り捨てられたサイズ
          INSUFFICIENT_PRIVILEGES: 0
1 row in set (0.00 sec)
```

結果は非常に長いので、全文は割愛し、重要な部分のみ解説していきます。
実際には下記の手前で行数見積もりする `rows_estimation` セクションがあったりと興味深い内容なので、ご興味ある方はぜひ [詳解MySQL 5.7 止まらぬ進化に乗り遅れないためのテクニカルガイド](https://www.amazon.co.jp/dp/4798147400) を読んでみて欲しいです。本当に詳解です。

```json
"considered_execution_plans": [
  {
    "plan_prefix": [
    ],
    "table": "`todos`",
    "best_access_path": {
      "considered_access_paths": [
        {
          "access_type": "ref",
          "index": "user_id_keyword_completed",
          "rows": 11740,
          "cost": 14088,
          "chosen": true
        },
        {
          "access_type": "ref",
          "index": "user_id_completed",
          "rows": 5432,
          "cost": 6518.4,
          "chosen": true
        },
        {
          "access_type": "ref",
          "index": "user_id_keyword",
          "rows": 10804,
          "cost": 12965,
          "chosen": false
        },
        {
          "access_type": "range",
          "range_details": {
            "used_index": "user_id_completed"
          },
          "chosen": false,
          "cause": "heuristic_index_cheaper"
        }
      ]
    },
    "condition_filtering_pct": 11.11,
    "rows_for_plan": 603.5,
    "cost_for_plan": 6518.4,
    "chosen": true
  }
]
```

### オプティマイザが検討した実行計画：considered_execution_plans
`user_id_keyword_completed ` `user_id_completed ` `user_id_keyword ` のインデックスそれぞれの、行数とコストが出力されます。
この中から、最もコストが低いインデックスが採用されます。

結果をみてみると、以下が最もコストが低いことがわかります。

```json
        {
          "access_type": "ref",
          "index": "user_id_completed",
          "rows": 5432,
          "cost": 6518.4,
          "chosen": true
        },
```

選択されたことが `"chosen": true`  からわかります。

## 結果

- インデックス上で LIKE 検索をかけるより、user_id で全件取ってきた結果を LIKE した方が高速であると判断された
    - そもそも LIKE 検索対象が user_id で絞った件数とほぼ同一だった
    - それならより短いインデックスを使い高速に処理する
    - 統計情報上、新規インデックスではなく既存インデックスが高速と判断された
- 本当にこのクエリを高速化したいなら、LIKE で指定する文字列を長くしてより絞り込む必要がある

## 結果からの検証
### LIKE 検索をより絞り込んだ結果
より絞り込めばインデックスが有効に利用されるのではないかと推測できたので、実際に検証してみました。

`rows: 5432` -> `rows: 1176` になったことで、LIKE 検索にもインデックスが選択されるようになりました。

`Extra: Using index condition` となり、[インデックスコンディションプッシュダウンの最適化](https://dev.mysql.com/doc/refman/5.6/ja/index-condition-pushdown-optimization.html)が行われ高速に動作しているのがわかります。

`user_id_keyword_completed ` と、completed カラムが含まれるインデックスが選択されるのは、統計情報によるものではないかなと考えています。
ここは今後の深掘りの課題です。

```sql
mysql> explain SELECT
    ->     *
    -> FROM
    ->     todos
    -> WHERE
    ->     user_id=11000501
    -> AND
    ->     keyword LIKE 'ClientProjectMilestone%'\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: todos
   partitions: NULL
         type: range
possible_keys: user_id_keyword_completed,user_id_completed,user_id_keyword
          key: user_id_keyword_completed
      key_len: 1026
          ref: NULL
         rows: 1176
     filtered: 100.00
        Extra: Using index condition
1 row in set, 1 warning (0.01 sec)
```

### user_id 単体インデックス
より短いインデックスが選択されるならば、インデックス自体を最も短くしてみたら選択されるのか、を検証してみました。
結果、既存インデックスが選択されました。

これも統計情報なのだろうか…合わせて今後の課題ですね。

```sql
mysql> alter table todos add index user_id(user_id);
Query OK, 0 rows affected (0.55 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> explain SELECT
    ->     *
    -> FROM
    ->     todos
    -> WHERE
    ->     user_id=11000501
    -> AND
    ->     keyword LIKE 'Client%'\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: todos
   partitions: NULL
         type: ref
possible_keys: user_id_keyword_completed,user_id_completed,user_id_keyword,user_id
          key: user_id_completed
      key_len: 4
          ref: const
         rows: 5432
     filtered: 11.11
        Extra: Using where
1 row in set, 1 warning (0.00 sec)
```

## 課題
### 複数テーブルを JOIN した際のトレース
今回は単一テーブルでの検証でしたが、開発現場では JOIN されることの方が多いと思います。
次回は JOIN された際にどうインデックスが使われるのか、どのような順番で JOIN されるのか、などをトレースしたいと考えています。

### 統計情報を知る
今回の結果は、新規に作ったインデックスは結局選択されませんでした。
それおそらく、既存インデックスの方が統計情報が多く存在し、より正確な行数見積もりとコスト計算ができたからではないかと推測しています。

今後は、その裏付けをしていきたいと考えています。

### 未使用のインデックス調査
今回の主題とは違いますが、未使用では？というインデックスも時々見られるのが現状です。
インデックスショットガンにならないよう、未使用と思われるインデックス、他で代替できるインデックスは、今後ウォッチして削除したり統合したりしていきたいです。

## 所感
DBRE として、通常の開発業務から何歩か踏み込んでいるのが僕の日常になりつつあります。
やってみて、今まで雰囲気で EXPLAIN してたかもしれないなって思いましたし、より根拠が明確になり、実際の行数やコスト算出の経緯をみていくことでいくつかの推測も成り立ち、さらなる検証につながり理解も深まりました。

開発する人はここまでやる必要はないと思いますが、EXPLAIN とその見方は今後社内で展開し、エンジニアの底を地道に上げていきたいなと考えています。

RDB は沼だなってずっと思ってはいるんですが、これが何より楽しいので、今後もより高みを目指しつつアウトプットしていきたいと思います。

さて、明日は [あだちん](https://qiita.com/adachin0817) 先生の「ランサーズの各サービスをECS/Fargateへ移行する取り組みについて」です。インフラも楽しいですよ！

[^1]: クエリ (query) は検索を意味しますが、SQLの文脈では書き込みもひっくるめてクエリ、と表現するのが一般的なようです。なお余談ですが、 `SQL` と `SQL文` は違います。前者は言語そのものを表します。 `ドメイン` と `ドメイン名` の違いに似てます
[^2]: 本稿では全て複合インデックスを指します
[^3]: 実例とはいえ、一部マスクしています