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にテーブルとして実装されており、以下のレイアウトとなっていました。

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：Top N＋ORDER BY

SELECT SEND_ID
FROM (
  SELECT SEND_ID
  FROM   MESSAGE_QUEUE
  WHERE  SEND_STS = '0'
  ORDER BY SEND_ID
)
WHERE ROWNUM <= 10 ;

【チューニング前】実行計画：Top N＋ORDER 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つの問題が生じています。

毎回、**テーブル・フルスキャン**が発生する。
SORTが発生することで実際は10件以上のレコードを読み込んでいる。

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

（対応） ORDER BYでインデックスを使う

まずはの対応として、ソートを省略する手段を考えます。

これは「失敗から学ぶRDBの正しい歩き方」の6章に、ORDER BY句狙いのINDEXとして紹介されています。

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

SEND_IDにインデックスを貼る①

CREATE INDEX send_id_idx ON message_queue(send_id,send_sts);

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

【チューニング①】実行計画：Top N＋ORDER 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に含まれるため、インデックスを読むだけで結果を取得できるのです。これはインデックス・オンリー・スキャンなどと呼ばれる手法で、使い方によっては性能を劇的に改善することが出来ます。

（対応） 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	0
00000012	0

テーブルレイアウトで見たようにSEND_IDは単純増加するSequenceであり、SEND_IDが小さいときはSEND_STSが1:送信済、大きいときは0:未送信であるという構造になっています。

【チューニング前・一部抜粋】SQL：Top N＋ORDER BY

  WHERE  SEND_STS = 0
  ORDER BY SEND_ID

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

更なる改善

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

インデックスの列順序を入れ替える②

CREATE INDEX send_id_idx ON message_queue(send_sts,send_id);

【チューニング②】SQL：Top N＋ORDER 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 ;

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

【チューニング②】実行計画：Top N＋ORDER BY、INDEX RANGE 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
0	00000011
0	00000012
1	00000001
1	00000002

(2020/3/29追記) PostgreSQLの部分インデックスを利用する例

ここまでのチューニングはOracleを念頭に置いたものでしたが（他DBMSでも使えます）、PostgreSQLに存在する**部分インデックス**を使うと、より容易にチューニングできる可能性があります。

SELECT文の変更

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

PostgreSQL版のチューニング前SQL：Top N＋ORDER BY

SELECT SEND_ID
FROM   MESSAGE_QUEUE
WHERE  SEND_STS = '0'
ORDER  BY SEND_ID
LIMIT  10 ;

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

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を実行しつつ実行計画を取ってみます。

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文も改修してみましょう。

INDEX FULL 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 ;

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

                                                                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文の変更で述べたPostgreSQL用のもので構いません。

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

部分インデックスの定義

# CREATE INDEX send_id_idx ON message_queue(send_id) WHERE send_sts = '0';

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

部分インデックス利用時の実行計画

                                                                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文の処理時間やコスト上、今回用意したデータではさほど有意な差が見えません。

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

通常インデックスと部分インデックスのサイズ比較

/* 通常インデックスのサイズ */
# 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チューニングに対する関心は高まっていると思います。今日紹介した以外にもいろいろなチューニング・テクニックがありますので、是非この機会に学んでみることをおすすめします。