Top N＋ORDER BYのSQLチューニング

# TL;DR

- Top N取得SQLでは、**ORDER BY句狙いのインデックス**を使うと性能改善する場合が多い。
- それでも無駄なレコード取得が行われるケースがあるので、実行計画を良く見よう。
- #そーだい本 で楽しいSQLチューニングライフを！

# はじめに
今日は基本的な事象ながら意外と見落としがちな、
「**先頭N件（Top N）の取得でORDER BYも使うケースのSQLチューニング**」
について、解説をしてみたいと思います。

(2020/3/29 追記)
初稿は基本的にOracleを前提としていたため、PostgreSQLでの例を検証して追記しました。

# テーブル・レイアウト
まず、今回チューニングの対象となるデータモデルについてです。
対象はメッセージキューでDBにテーブルとして実装されており、以下のレイアウトとなっていました。

```sql:MESSAGE_QUEUEのレイアウト
 名前                  型                説明
 -------------------- ----------------- -------------------
 MESSAGE_ID           CHAR(10)          PK
 USER_ID              CHAR(10)          PK,FK
 CREATE_DATE          CHAR(8)           PK
 SEND_ID              CHAR(10)          ユニークに採番されるSeq
 SEND_STS             CHAR(1)           0:未送信、1:送信済
 SUBJECT              VARCHAR2(250)
 MESSAGE_TEXT         CLOB(2000)

※インデックスは複合キーであるPKだけに作成されている。
```
データの持ち方も問題で、過去レコードは論理削除されるだけでテーブルに残り続け、レコードが増えるほど性能劣化する構造となっていました。

## チューニング対象SQLの確認
まず過去レコードを別テーブルなどに退避し、メッセージキューを小さく保つことは大前提になります。

その前提で問題のSQLと実行計画を確認しましょう。

```sql:【チューニング前】SQL：Top&nbsp;N＋ORDER&nbsp;BY
SELECT SEND_ID
FROM (
  SELECT SEND_ID
  FROM   MESSAGE_QUEUE
  WHERE  SEND_STS = '0'
  ORDER BY SEND_ID
)
WHERE ROWNUM <= 10 ;
```

```sql:【チューニング前】実行計画：Top&nbsp;N＋ORDER&nbsp;BY
--------------------------------------------------
| Id  | Operation                | Name          |
--------------------------------------------------
|   0 | SELECT STATEMENT         |               |
|   1 |  SORT ORDER BY           |               |
|*  2 |   COUNT STOPKEY          |               |
|   3 |    VIEW                  |               |
|*  4 |     TABLE ACCESS FULL    | MESSAGE_QUEUE |
--------------------------------------------------
```
ROWNUMが出てきていることから分かるとおり、DBMSは少し古いOracleです（ただし、今回のチューニング自体はFETCH OFFSET句やWINDOW関数を使っている場合でも同じ効果があります）。

このSQLと実行計画では、PKはWHEREでもORDER BYでも条件指定されていない一方で、実質的なキーとして使われている```SEND_ID```にインデックスがないため、下記2つの問題が生じています。

:one: 毎回、**<font color="red">テーブル・フルスキャン</font>**が発生する。
:two: SORTが発生することで実際は10件以上のレコードを読み込んでいる。

:one:と:two:に同時に対応し、実行計画を改善していく必要があります。


## （対応:one:） ORDER BYでインデックスを使う
まずは:one:の対応として、ソートを省略する手段を考えます。

これは「[失敗から学ぶRDBの正しい歩き方](https://gihyo.jp/book/2019/978-4-297-10408-5)」の6章に、**ORDER BY句狙いのINDEX**として紹介されています。

つまり、```ORDER BY SEND_ID```とSQLに書かれているのですから、SEND_IDにインデックスを作成します。インデックスはテーブルとは別のDBオブジェクトですが、指定列値で**事前にソートがされている**という特徴があります。

```sql:SEND_IDにインデックスを貼る①
CREATE INDEX send_id_idx ON message_queue(send_id,send_sts);
```

この結果、SQL文は何も変えなくても以下のように実行計画が変わります。

```sql:【チューニング①】実行計画：Top&nbsp;N＋ORDER&nbsp;BY
--------------------------------------------------
| Id  | Operation                | Name          |
--------------------------------------------------
|   0 | SELECT STATEMENT         |               |
|*  1 |  COUNT STOPKEY           |               |
|   2 |   VIEW                   |               |
|*  3 |    INDEX FULL SCAN       | SEND_ID_IDX   |
--------------------------------------------------
```

チューニング前の実行計画にあった```SORT ORDER BY```が消えました。これにより性能が大幅に改善されます。

また、```TABLE ACCESS FULL```と表示されていた行が```INDEX FULL SCAN```に変わりました。これは**MESSAGE_QUEUEテーブルからレコードを読み込んでいない**ことを示しています。
SQLで必要なカラム（```SEND_ID、SEND_STS```）が```SEND_ID_IDX```に含まれるため、インデックスを読むだけで結果を取得できるのです。これは**インデックス・オンリー・スキャン**などと呼ばれる手法で、使い方によっては性能を劇的に改善することが出来ます。

## （対応:two:） Top NでINDEX FULL SCANを回避する
では、```SEND_ID_IDX(SEND_ID,SEND_STS)```のインデックスを作ることでチューニングは完了でしょうか。

気になるのは【チューニング①】の実行計画にある```INDEX FULL SCAN```です。
インデックスはテーブルよりも遥かにサイズが小さいとはいえ、Top 10件を取得するために```FULL SCAN```をするのは無駄です。

こうなってしまう理由をデータ構造とSQLから分析して見ましょう。

``MESSAGE_QUEUE内のレコード（SEND_IDでソート済、先頭部分・該当列のみ）``

|SEND_ID|SEND_STS|
|---|:-:|
|00000001|1|
|00000002|1|
|00000011|**<font color="red">0</font>**|
|00000012|**<font color="red">0</font>**|

テーブルレイアウトで見たようにSEND_IDは単純増加するSequenceであり、SEND_IDが小さいときはSEND_STSが```1:送信済```、大きいときは```0:未送信```であるという構造になっています。
 
```sql:【チューニング前・一部抜粋】SQL：Top&nbsp;N＋ORDER&nbsp;BY
  WHERE  SEND_STS = 0
  ORDER BY SEND_ID
```

そのため、上記のSQLではSEND_IDでORDER BYした後にSEND_STSが```送信済```のレコードを捨て、```未送信```のレコードから先頭10件を取得する動きになります。つまり、ORDER BYの結果がフィルタ条件によって変動して確定しません。

### 更なる改善
これを改善するために、インデックスとSQLを以下のように変更します。

```sql:インデックスの列順序を入れ替える②
CREATE INDEX send_id_idx ON message_queue(send_sts,send_id);
```

```sql:【チューニング②】SQL：Top&nbsp;N＋ORDER&nbsp;BYにSEND_STSも指定
SELECT SEND_ID
FROM (
  SELECT SEND_ID
  FROM   MESSAGE_QUEUE
  WHERE  SEND_STS = '0'
  ORDER BY SEND_STS,SEND_ID
)
WHERE ROWNUM <= 10 ;
```

これにより、実行計画は以下のように変わります。

```sql:【チューニング②】実行計画：Top&nbsp;N＋ORDER&nbsp;BY、INDEX&nbsp;RANGE&nbsp;SCAN
--------------------------------------------------
| Id  | Operation                | Name          |
--------------------------------------------------
|   0 | SELECT STATEMENT         |               |
|*  1 |  COUNT STOPKEY           |               |
|   2 |   VIEW                   |               |
|*  3 |    INDEX RANGE SCAN      | SEND_ID_IDX   |
--------------------------------------------------
```

変化点は```INDEX FULL SCAN```が```INDEX RANGE SCAN```になった点です。

上記チューニングはレコードのソート順を下表のように変更したのと同じ意味となります。つまり、```未送信```が先頭に来るように並び替えされているため、そのうちの先頭10件を取るだけでORDER BYの結果が確定的となります。今回のケースでは```送信済```レコードがテーブルに大量にたまっていますので、この効果は大きいです。

``MESSAGE_QUEUE内のレコード（SEND_STS、SEND_IDでソート済）``

|SEND_STS|SEND_ID|
|:-:|---|
|**<font color="red">0</font>**|00000011|
|**<font color="red">0</font>**|00000012|
|1|00000001|
|1|00000002|

# (2020/3/29追記) PostgreSQLの部分インデックスを利用する例
ここまでのチューニングはOracleを念頭に置いたものでしたが（他DBMSでも使えます）、PostgreSQLに存在する**[部分インデックス](https://use-the-index-luke.com/ja/sql/where-clause/partial-and-filtered-indexes)**を使うと、より容易にチューニングできる可能性があります。

## SELECT文の変更
PostgreSQLにはOracleのROWNUMはありませんので、LIMIT句を使って、SELECT文を書き換えます。

```sql:PostgreSQL版のチューニング前SQL：Top&nbsp;N＋ORDER&nbsp;BY
SELECT SEND_ID
FROM   MESSAGE_QUEUE
WHERE  SEND_STS = '0'
ORDER  BY SEND_ID
LIMIT  10 ;
```

[テーブル・レイアウト](#テーブルレイアウト)は先ほどと同様です。
そこに以下のように未送信/送信済のデータを用意しておきます。

```sql:message_queueのデータ内訳
# SELECT send_sts,COUNT(*) FROM message_queue GROUP BY send_sts ORDER BY send_sts;
 send_sts | count 
----------+-------
 0        |   108    /* 未送信 */
 1        | 15060    /* 送信済 */

```

## PostgreSQLにおけるフルスキャン時の実行計画
ではまずPostgreSQLでインデックスなしの際の実行計画を見てみましょう。EXPLAIN ANALYZEで実際にSQLを実行しつつ実行計画を取ってみます。

```sql:PostgreSQLフルスキャン時の実行計画
                                                        QUERY PLAN                                                        
--------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=566.22..566.25 rows=10 width=11) (actual time=1.922..1.944 rows=10 loops=1)
   ->  Sort  (cost=566.22..566.49 rows=108 width=11) (actual time=1.920..1.927 rows=10 loops=1)
         Sort Key: send_id
         Sort Method: top-N heapsort  Memory: 25kB
         ->  Seq Scan on message_queue  (cost=0.00..563.89 rows=108 width=11) (actual time=0.145..1.788 rows=108 loops=1)
               Filter: (send_sts = '0'::bpchar)
               Rows Removed by Filter: 15060
 Planning time: 0.073 ms
 Execution time: 1.972 ms

```

出力結果は異なるのですが、Oracleの際と同様にテーブルフルスキャンが走っていることが`Seq Scan on message_queue`の記述から読み取れます。
フルスキャンの結果から`send_sts = '0'`のものをフィルタしてSortし、`Limit`により`rows=10`で先頭10行を読み取っています。

Oracleの場合と同様に、**テーブルフルスキャン**の問題と、ORDER BYが必要なため`LIMIT 10`は性能観点で上手く効いていないというパフォーマンス上の欠点を抱えています。

## ORDER BYでインデックスを利用し、INDEX FULL SCANを回避する
では、Oracleと同様にインデックスを作成して、さらにSELECT文も改修してみましょう。

```sql:INDEX&nbsp;FULL&nbsp;SCAN回避時のインデックス定義とSELECT文
# CREATE INDEX send_id_idx ON message_queue(send_sts,send_id);

# SELECT SEND_ID
  FROM   MESSAGE_QUEUE
  WHERE  SEND_STS = '0'
  ORDER BY SEND_STS,SEND_ID  /* ORDER BYにSEND_STSを追加 */
  LIMIT 10 ;
```

こちらの実行計画は以下のようになります。

```sql
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.29..0.83 rows=10 width=13) (actual time=0.031..0.055 rows=10 loops=1)
   ->  Index Only Scan using send_id_idx on message_queue  (cost=0.29..6.17 rows=108 width=13) (actual time=0.029..0.039 rows=10 loops=1)
         Index Cond: (send_sts = '0'::bpchar)
         Heap Fetches: 0
 Planning time: 0.111 ms
 Execution time: 0.084 ms
```

先ほどのフルスキャン時と異なり、`Seq Scan`が消えて`Index Only Scan using send_id_idx on message_queue`となっています。これがPostgreSQLにおける**INDEX ONLY SCAN**の実行計画になります。
※残念ながら、PostgreSQLの実行計画ではINDEX RANGE SCANか、INDEX FULL SCANかを見分ける方法がないように見え、Oracleと同様の判別は出来ていません。

さらにソート済のデータ構造であるインデックスを使うことで、実行計画中から`Sort`関連の処理が消えています。前述したように、これは大きなパフォーマンス上のアドバンテージになります。

## 部分インデックスを使う
では最後にPostgreSQLの部分インデックスを使ったチューニング例を見てみましょう。
この際、SELECT文は[SELECT文の変更](#select文の変更)で述べたPostgreSQL用のもので構いません。

そのうえでインデックスを以下のもので作り直します。

```sql:部分インデックスの定義
# CREATE INDEX send_id_idx ON message_queue(send_id) WHERE send_sts = '0';
```

部分インデックス作成後に取得した実行計画は以下となります。

```sql:部分インデックス利用時の実行計画
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.14..1.03 rows=10 width=11) (actual time=0.019..0.040 rows=10 loops=1)
   ->  Index Only Scan using send_id_idx on message_queue  (cost=0.14..9.76 rows=108 width=11) (actual time=0.017..0.025 rows=10 loops=1)
         Heap Fetches: 0
 Planning time: 0.097 ms
 Execution time: 0.064 ms
```

実行計画を先ほどのものと比較すると、`Index Cond:`の行が消えています。
今回の部分インデックスでは`send_sts = '0'`のものだけにインデックスを貼っているため、`send_sts`に対する条件式は実行計画中から消えたようです。

### 通常のインデックスと部分インデックスを比較して
比較するとどちらのインデックスが速いのか、というのが気になるところです。
残念ながら、SELECT文の処理時間やコスト上、**今回用意したデータではさほど有意な差が見えません**。

しかし、インデックスのサイズを比較すると大きな違いが見えます。

```sql:通常インデックスと部分インデックスのサイズ比較
/* 通常インデックスのサイズ */
# CREATE INDEX send_id_idx ON message_queue(send_sts,send_id);
# select relname,relpages from pg_class where relname = 'send_id_idx';
   relname   | relpages 
-------------+----------
 send_id_idx |       61

/* 部分インデックスのサイズ */
# CREATE INDEX send_id_idx ON message_queue(send_id) WHERE send_sts = '0';
# select relname,relpages from pg_class where relname = 'send_id_idx';
   relname   | relpages 
-------------+----------
 send_id_idx |        2
```

今回のケースでは、通常インデックスが61pageに対し、部分インデックスはわずか2pageとなっています。これはバッファマネジメント等から考えても、大きなメリットとなるでしょう。

**【部分インデックスのデメリット】**
`send_sts='0'`以外の検索条件では今回の部分インデックスは全く使えません。`send_sts='1'`のレコードを検索したり、ORDER BYする際にはテーブルフルスキャンが必要となります。
通常のインデックスではこのようなデメリットはありません。

# まとめ
今日はSQLチューニングについて、方法・考え方をまとめてみました。

最近、上でも触れている所謂 #そーだい本 の効果でSQLチューニングに対する関心は高まっていると思います。今日紹介した以外にもいろいろなチューニング・テクニックがありますので、是非この機会に学んでみることをおすすめします。