【PostgreSQL版】INDEXチューニング入門

# 目的

1,000万件程度のデータ量でも高速に参照可能な SQL を実現するため、インデックスを使って SQL のチューニングを行いました。インデックスの概要や効果などに触れつつ、作業手順をまとめたいと思います。

# 環境

Amazon Aurora PostgreSQL のバージョン 11.5 で検証しています。

# インデックスとは

[**インデックス**](https://www.postgresql.jp/document/11/html/indexes.html)は、データベースの性能を向上させる手段の１つです。インデックスを使用すると、使用しない場合に比べてかなり速く特定の行を抽出することができます。index は日本語で「索引」という意味です。**「データを検索しやすいように並べ替えて、ラベルをつけたもの」**と考えるとわかりやすいと思います。

例えば、レンタルビデオ屋さんにビデオを借りにいったとします。そこには10万本のビデオがおいてあります。インデックスがない状態とは、ランダムに並べられた10万本のビデオの中から、欲しいビデオを探し出すようなものです。しかし、実際には「名前順」などに並べ替えらえているため、スムーズに目的のビデオを探し出すことができます。

#### ★複合インデックス

インデックスは、複数の列を指定することができます。これを、[**複合インデックス**](https://www.postgresql.jp/document/11/html/indexes-multicolumn.html)（または複数列インデックス）と呼びます。レンタルビデオ屋さんの例でいうと、ビデオを「ジャンル別」の棚に分けたあと「名前順」に並び替えるようなイメージです。

複数の列が検索キーになっている場合などに有効ですが、2つ目以降のインデックスは単体では利用することができません。そのため、複合インデックスを作成する場合は、どの列を1つ目に指定するかが重要になります。頻繁に検索キーに利用される列を1つ目に指定すると、さまざまなクエリで有効に使われることが期待できます。

#### ★インデックスの注意点

レンタルビデオ屋さんが新作を入荷したとき、名前順で正しい場所に置くのは少しだけ手間がかかります。それと同じように、インデックスを作成するとデータの INSERT 時にオーバーヘッドが生じます。そのため、インデックスは必要なものに絞って、よく考えて作成する必要があります。

# インデックスを利用したときの計算量

#### ★計算量とは

計算量とは、**「入力値を n としたとき、アルゴリズムの計算ステップ数がどれくらいになるのか」**をおおまかに表したものです。$ O $ 記法（オーダー記法）を用いて、$ O(n) $ や $ O(n^2) $ や $ O(log~n) $ のように表します。厳密な式から最高次数の項以外や係数を無視することでシンプルに表記でき、大雑把にアルゴリズムの処理速度を評価することができます。

インデックスがない場合、データの検索は **[線形探索](https://e-words.jp/w/%E7%B7%9A%E5%BD%A2%E6%8E%A2%E7%B4%A2.html)** になります。線形探索の計算量は $ O(n) $ で表されます。これは、「入力値が1増えるごとに必要な計算量も1増える」ということを意味します。そのため、100万件のデータになると、100万の計算量が必要になります。

一方、インデックスを利用した場合、データは **[B-Tree](http://wwwa.pikara.ne.jp/okojisan/b-tree/index.html)** という構造で並び変えられ、検索に必要な計算量は $ O(log~n) $ となります。この場合、たとえ100万件のデータがあったとしても、計算量をだいたい20程度に抑えられるというイメージです。

※$ log $ の底が省略されている場合、一般には $ e $（自然対数の底）を表しますが、情報科学においては 2 を表すことが多いそうです。当記事でも、$ log $ の底を省略した場合は 2 で計算しています。

#### ★log のおさらい

$ log $（対数）は、**”a を何乗したら b になるか”** を表す数です。

例えば、”2 を $ x $ 乗したら 1024 になる” という式は下記のようになります。

```math
2^x = 1024
```

これを $ log $ で表現すると下記のようになります。

```math
log_{2}1024 = x
```

2を10乗すると1024なので、答えは10となります。

```math
log_{2}1024 = 10
```

この式が表しているのは、**「データ量が1024のとき、必要な計算量は10になる」**ということです。インデックスを利用しない線形探索の計算量は1024なので、約100分の1の計算量に抑えられることがわかります。

#### ★線形探索 O(n) とB-Tree構造 O(log n) の計算量の比較

データ量と計算量の関係を下記の表にまとめました。$ n $ はデータ量、$ O(n) $ は線形探索の計算量、$ O(log~n) $ は B-Tree 構造の計算量です。インデックスを使うと、データが増えても必要な計算量はあまり変わらないことがわかります。

|データ量$ (n) $|$ O(n) $|$ O(log~n) $|
|---|---|---|
|2|2|1|
|5|5|2|
|10|10|3|
|50|50|6|
|100|100|7|
|1,000|1,000|10|
|10,000|10,000|13|
|100,000|100,000|17|
|1,000,000|1,000,000|20|
|10,000,000|10,000,000|23|
|100,000,000|100,000,000|27|
|1,000,000,000|1,000,000,000|30|

データ量と計算量の関係を折れ線グラフにすると下記のようになります。

![chart (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/450243/f2ced775-3374-fb28-e720-109e1fa408dc.png)

インデックスを利用すると**「データが増えれば増えるほど、1件あたりの検索に必要な計算量が減少する」**ということがわかります。

# インデックスの作成と削除

[**CREATE INDEX**](https://www.postgresql.jp/document/11/html/sql-createindex.html) コマンドで、インデックスを作成できます。
index_name には任意の名前をつけることができます。

```sql
CREATE INDEX index_name ON table_name (column_name);
```

[**DROP INDEX**](https://www.postgresql.jp/document/11/html/sql-dropindex.html) コマンドで、インデックスを削除できます。

```sql
DROP INDEX index_name;
```

#### ★CONCURRENTLY オプション

CREATE INDEX コマンドの実行中は、対象テーブルの INSERT、UPDATE、DELETE を防止するロックがかかります（読み取りは可能）。このロックをかけずにインデックスを作成する場合には、[**CONCURRENTLY**](https://www.postgresql.jp/document/11/html/sql-createindex.html) オプションを使用します。詳細は[インデックスの同時作成](https://www.postgresql.jp/document/11/html/sql-createindex.html#SQL-CREATEINDEX-CONCURRENTLY)を参照してください。

```sql
CREATE INDEX CONCURRENTLY index_name ON table_name (column_name);
```


# SQL のパフォーマンスの測定方法

SQL のパフォーマンスの測定に便利なコマンドを紹介します。

#### ★EXPLAIN コマンド

[**EXPLAIN**](https://www.postgresql.jp/document/11/html/sql-explain.html) コマンドは、SQL の実行にかかるコストの見積もりを表示します。
下記のように、EXPLAIN のあとに実行する SQL を書くだけでOKです。

```sql
EXPLAIN SELECT COUNT(user_id) FROM comments WHERE user_id = 'xxxx' AND created_at >= '2021-10-31 00:00:00';
                                                                   QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=15329.15..15329.16 rows=1 width=8)
   ->  Gather  (cost=1000.00..15329.14 rows=1 width=45)
         Workers Planned: 2
         ->  Parallel Seq Scan on comments  (cost=0.00..14329.04 rows=1 width=45)
               Filter: ((created_at >= '2021-10-31 00:00:00'::timestamp without time zone) AND ((user_id)::text = 'xxxx'::text))
(5 rows)
```

表示される項目は下記の通りです。

**cost：**初期処理の推定コスト..全体の推定コスト
**rows：**出力する行の推定数
**width：**出力する行のバイト単位での推定平均幅

ここで大事なのは cost と rows です。
cost の単位は気にせず、相対的にどのインデックスが優れているかを比較します。

:::note warn
表示されるコストや行数はあくまでも「推定値」です。実際の結果とは異なるため注意が必要です。
:::

#### ★EXPLAIN ANALYZE コマンド

EXPLAIN に [**ANALYZE**](https://www.postgresql.jp/document/11/html/sql-analyze.html) のパラメータを追加すると、実際に SQL を実行して実際の実行時間やその他の統計情報を表示させることができます。実際に実行されるので、INSERT や DELETE を行う場合には注意が必要です。また、実際の実行時間は実行するごとに微妙に異なった結果を返します。そのため、複数回実行して平均値をとるようにします。

```sql
EXPLAIN ANALYZE SELECT COUNT(user_id) FROM comments WHERE user_id = 'xxxx' AND created_at >= '2021-10-31 00:00:00';
                                                                   QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=15329.15..15329.16 rows=1 width=8) (actual time=107.382..107.662 rows=1 loops=1)
   ->  Gather  (cost=1000.00..15329.14 rows=1 width=45) (actual time=0.261..107.652 rows=3 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Parallel Seq Scan on comments  (cost=0.00..14329.04 rows=1 width=45) (actual time=57.850..93.553 rows=1 loops=3)
               Filter: ((created_at >= '2021-10-31 00:00:00'::timestamp without time zone) AND ((user_id)::text = 'xxxx'::text))
               Rows Removed by Filter: 175095
 Planning Time: 0.104 ms
 Execution Time: 107.690 ms
(9 rows)
```

**actual time：**実際の処理時間（単位はミリ秒なので、単位の異なる cost とは単純比較はできない）
**rows：**実際に出力する行数
**loops：**ノードを実行する総回数
**Planning time：**解析された問い合わせから問い合わせ計画を生成し最適化するのに掛かった時間（解析と書き換えは含まない）
**Execution time：**実行時間（解析や書き換え、計画作成の時間は含まない）

今回のチューニングでは、EXPLAIN ANALYZE コマンドを利用します。

#### ★SQL の実行時間だけを表示する

`\timing` コマンドを利用すると、SQL の時間を表示してくれるようになります。

一度実行すると、実行時間の表示がオンになります。

```sql
db=> \timing
Timing is on.
```

SQL を実行すると実行時間が表示されます。

```sql
db=> SELECT COUNT(*) FROM users;
 count
--------
 100000
(1 row)

Time: 63.575 ms
```

もう一度 `\timing` コマンド実行すると、実行時間の表示がオフになります。

```sql
db=> \timing
Timing is off.
```

以上です。

# 今回チューニングするデータベースについて

今回は、ユーザーが投稿したコメントを格納する comments テーブルのチューニングを行います。検索対象のテーブルは下記の通りです。

|comments|
|---|
|id|
|user_id|
|comment|
|created_at|

取得したい内容は、「特定日時以降に投稿された特定ユーザーのコメント数」です。
テストでは日時を「2021年10月31日以降」に指定して検証します。

発行する SQL は下記のようになります。

```sql
SELECT COUNT("user_id") FROM comments WHERE user_id = 'xxxx' AND created_at >= '2021-10-31 00:00:00';
```

#### ★準備したテストデータについて

今回は、下記表の user_1 と user_2 のコメントを対象に検証します。2名のユーザーの他に、数名のユーザーが数件のコメントを投稿しています。

|user_id|2021/10/31以降のコメント数|2021/10/30以前のコメント数|合計コメント数|
|---|---|---|---|
|user_1|3|27|30|
|user_2|3|約500,000|約500,000|

**user_1：**全体で約50万件のコメントのうち、30件のみがこのユーザーの投稿です。
**user_2：**約50万件のコメントのほとんどが、このユーザーが投稿したものです。

どちらのユーザーも、2021年10月31日以降の投稿は3件のみです。

※本来は、テストを行う場合はもう少し実際のデータに近い状態を用意することが望ましいです。

# 実際にインデックスを作成して検証する

ここからは、具体的な検証作業に入ります。

### 1. 現在作成されているインデックスを確認する

インデックスはその数が増えるほど INSERT の速度を低下させます。そのため、ムダなインデックスを作らないように、現在作成済みのインデックスがどのようなものか確認しておきます。下記に2つの確認方法を記載します。

#### ★インデックス一覧を表示

`\di` コマンドで作成されているインデックスを一覧表示することができます。

```sql
postgres=> \di
```

#### ★テーブルの詳細を表示

`\d table_name` コマンドでは、特定のテーブルに絞ってインデックスを表示することが可能です。
下の方に **Indexes:** と表示され、指定したテーブルのインデックス情報を確認できます。
通常、id のインデックスはデフォルトで作成されており、削除することも可能です。

```sql
db=> \d comments

-- 省略 --
Indexes:
    comments_pkey PRIMARY KEY, btree (id)
```

今回は id のインデックスは残しておき、新たに今回の SQL に必要なインデックスを作成していきます。

### 2. インデックスを作成する

今回は、検索に利用する列が user_id と created_at なので、以下の 4 パターンのインデックスを作成し、それぞれのパフォーマンスを検証していきます。

1. user_id
2. created_at
3. user_id, created_at
4. created_at, user_id

※3 と 4 は複合インデックスです。

### 3. 複数のインデックスを比較する

インデックスがない場合や、さまざまななインデックスを作成した場合を比較しながら、EXPLAIN ANALYZE コマンドで検証を行っていきます。

#### ★user_1 を検証する

user_1 のコメント数取得時の EXPLAIN ANALYZE の出力結果について、抜粋して下記の表にまとめました。

|INDEX|cost|actual time|Planning time|Execution time|
|---|---|---|---|---|
|なし	|1000.00..15329.14		|0.261..107.652		|0.104	|107.69|
|user_id	|0.42..38.11		|0.025..0.057		|0.146	|0.099|
|created_at |1000.00..15329.14		|0.256..90.261		|0.133	|90.322|
|user_id, created_at |0.42..53.27		|0.068..0.071		|0.187	|0.111|
|created_at, user_id	|1000.00..15329.14		|0.256..107.110		|0.146	|107.15|

上記の通り、user_id 単体のインデックスや user_id, created_at の複合インデックスでは、SQL の実行時間を1000分の1程度に抑えることができました。

一方、created_at や created_at, user_id のインデックスは実行速度がほとんど変わっていません。EXPLAIN ANALIZE の実行結果をみると、PostgreSQL プランナに「インデックスを利用しない方がよい」と判断され、インデックスが利用されなかったようです。しかし、実際には created_at で残り 6 件まで絞り込むことが可能です。

この様に、プランナは必ずしも正しい判断をしてくれるわけではありません。強制的にインデックスを使用させることも可能ですが、いったんこのまま検証を続けます。

#### ★user_2 を検証する

user_2 のコメント数取得時の EXPLAIN ANALYZE の出力結果は下記の通りです。

|INDEX|cost|actual time|Planning time|Execution time|
|---|---|---|---|---|
|なし	|15330.24..15330.45	|109.160..118.191	|0.069	|118.236|
|user_id	|15330.24..15330.45	|100.792..111.623	|0.077	|111.671|
|created_at |15330.24..15330.45	|113.361..113.424	|0.073	|114.764|
|user_id, created_at |15330.24..15330.45	|94.097..99.108	|0.102	|99.153	|99.255|
|created_at, user_id	|15330.24..15330.45	|93.023..100.430	|0.079	|100.476|

EXPLAIN ANALIZE の出力結果を見ると、user_id のインデックスが使われなかったことがわかります。今回のように、user_id ではほとんど絞り込みができない場合、プランナは**「インデックスを使うより、普通に検索した方が速い可能性が高い」**と判断するようです。created_at はインデックスを利用した方が速いはずですが、なぜか今回も利用されませんでした。

#### ★実際にアプリを利用して検証する

これまではデータベースに入り、直接 SQL を実行していました。しかし、実際には SQL は PC やスマホのアプリのプログラムから利用されます。user_1 のケースではインデックスが有効なことがわかっているため、user_2 のケースでテスト環境でアプリを操作し、実際の SQL の処理時間を計測してみます。

|INDEX|平均実行時間（ms）|
|---|---|
|なし	|127.0|
|user_id	|127.7|
|created_at |9.7|
|user_id, created_at |10.7|
|created_at, user_id	|11.0|

上記の通り、実際にアプリを使ってみると created_at や created_at, user_id のインデックスも利用され、速度が大幅に向上していることがわかります。なぜアプリ利用時にのみプランナがインデックスを利用したのかはわかりませんが、インデックスの効果が証明されて良かったです。user_2 のケースでは user_id のインデックスが利用されないのは想定通りでした。

EXPLAIN ANALIZE で調査したときのインデックス利用時の SQL 実行時間に比べ、アプリ利用時の SQL 実行時間が増えています。これは、アプリから SQL を実行する際にサーバーからデータベースへの接続などのオーバーヘッドがあるためだと考えています。

### 4. 最適なインデックスを選択する

結論からいうと、今回は user_id, created_at の複合インデックスを採用することにしました。
このインデックスの採用理由は下記の通りです。

- user_id のインデックスを利用することで、大量のコメントの中から対象ユーザーのコメントを高速に取得できる
- 対象ユーザーが大量のコメントを投稿していても、created_at のインデックスで高速に取得できる
- user_id は他の WHERE 句でも利用されているため、user_id, created_at の順番でインデックスを作成することで user_id 単体での検索も高速になる

以上です。

あとは、本番環境で運用をしてみてモニタリングしながら、必要に応じてチューニングしていきたいと思います。

# インデックスを利用した方がよいケースまとめ

- 大量のデータから少しのデータを取得する場合
- 列の値のバリエーションが多く、カーディナリティが高い場合
    - users テーブルの例：〇誕生日、×性別
- WHERE 句で頻繁に利用される列
- ORDER BY 句で頻繁に利用される列
- JOIN の結合キーとして利用される列

# インデックス作成の注意点まとめ

- LIKE を利用する場合、前方一致のみ有効。hoge% は速くなるが、%hoge% や %hoge ではインデックスは利用されない。
- 複合インデックは順番が大事。user_id, created_at の順番で作成した場合、user_id 単体の検索ではインデックスが利用されるが、created_at 単体の検索ではインデックスは利用されない。
- インデックスの数が増えると、インサート時のオーバーヘッドが増えてインサートが遅くなる。
- インデックスを使っても対象を十分に絞り込めない場合、インデックスは利用されない場合がある。

# おわりに

今回は調べきれなかったことも多くあるので、また新たにわかったことがあれば追記や更新をしていきたいと思います。当記事が誰かの役に立てば幸いです。最後までお読みいただき、ありがとうございました。

# 参考ドキュメント・動画
- ドキュメント
    - [PostgreSQL 11.5文書（PostgreSQL日本語ドキュメント）](https://www.postgresql.jp/document/11/html/)
    - [計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜](https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0)
- 動画（YouTube）
    - [SQL を速くするインデックス入門 : B-Tree や複合インデックスが理解できる](https://www.youtube.com/watch?v=OsIxUT7D728)