by Hayato Matsuura.

インデックスを使ったorder by


order by付きのSQLクエリでは、関連するインデックスが 行を既に必要な順番に並べ替えている時には、結果を明示的にソートする必要はありません。つまり、where句に使われるのと同じインデックスが、order by句もサポートしている必要があります。

例として、前日の売上を売上日と製品IDで並べ替える、以下のようなクエリを考えてみましょう。

SELECT sale_date, product_id, quantity
  FROM sales
 WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY sale_date, product_id

where句で使えるインデックスは、 既にSALE_DATEに作られています。しかし、order by句を満たすように、データベースは明示的なソート処理を行う必要があります。

DB2
Explain Plan
------------------------------------------------------------
ID | Operation             |                     Rows | Cost
 1 | RETURN                |                          |  682
 2 |  TBSCAN               |     394 of 394 (100.00%) |  682
 3 |   SORT                |     394 of 394 (100.00%) |  682
 4 |    FETCH SALES        |     394 of 394 (100.00%) |  682
 5 |     IXSCAN SALES_DATE | 394 of 1009326 (   .04%) |   19

Predicate Information
 5 - START (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
      STOP (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))

DB2ではwhere句は、WHERE sale_date > CURRENT_DATE - 1 DAYと変更する必要があります。

Oracle
---------------------------------------------------------------
|Id | Operation                    | Name       | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT             |            |  320 |   18 |
| 1 |  SORT ORDER BY               |            |  320 |   18 |
| 2 |   TABLE ACCESS BY INDEX ROWID| SALES      |  320 |   17 |
|*3 |    INDEX RANGE SCAN          | SALES_DATE |  320 |    3 |
---------------------------------------------------------------

INDEX RANGE SCANは、インデックスの順番で結果を返します。 その利点を利用するために、order by句に合うように インデックスの定義を拡張する必要があります。

  DROP INDEX sales_date
CREATE INDEX sales_dt_pr ON sales (sale_date, product_id)
SELECT sale_date, product_id, quantity
  FROM sales
 WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY sale_date, product_id

DB2
Explain Plan
-----------------------------------------------------------
ID | Operation            |                     Rows | Cost
 1 | RETURN               |                          |  688
 2 |  FETCH SALES         |     394 of 394 (100.00%) |  688
 3 |   IXSCAN SALES_DT_PR | 394 of 1009326 (   .04%) |   24

Predicate Information
 3 - START (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
      STOP (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
Oracle
---------------------------------------------------------------
|Id | Operation                   | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT            |             |  320 |  300 |
| 1 |  TABLE ACCESS BY INDEX ROWID| SALES       |  320 |  300 |
|*2 |   INDEX RANGE SCAN          | SALES_DT_PR |  320 |    4 |
---------------------------------------------------------------

クエリにはorder by句は残ったままですが、 ソート処理を表すSORT ORDER BYは実行計画から消えてしまいました。 データベースは、インデックスによる順序付けを利用して、ソート処理をスキップしたのです。

重要

order by句がインデックスによる順序付けと一致している場合、 データベースは明示的なソート処理を省略できます。

新しい実行計画では処理の数は減っていますが、新しいインデックスのクラスタ化係数が悪くなっている(自動的に最適化されたクラスタ化係数を参照)ため、 コスト値は明らかに増えています。この点から言うと、コスト値がいつでも 実行時に必要なリソースを示す良い指標であるとは言えないとするべきかもしれません。

自動的に最適化されたクラスタ化係数

Oracleは、インデックスの順序に対するROWIDを 考慮に入れることによって、クラスタ化係数を小さく保とうとします。2つのインデックスエントリが同じキー値を持っている時には、 ROWIDで最終的な順序付けをします。 インデックスはテーブル内の行の順序に並んでおり、ROWIDは テーブル行の物理的なアドレスを表すように付けられているものなので、クラスタ化係数は可能な限り小さくなることになります。

インデックスに新しい列を追加すると、ROWID前に新しいソートのルールを追加することになります。 データベースはテーブルの順序に基づいてインデックスエントリを調整しづらくなるので、クラスタ化係数は悪くなってしまいます。

しかしいずれにしても、インデックスは大まかにはテーブルの順序に従って並んでいるでしょう。ある日の売上は、テーブル内あるいは インデックス内では、完全に順序通りではないにしても、クラスタ化されて近くに配置されているはずです。 SALE_DT_PRインデックスを使った時、データベースはテーブルブロックを複数回読む必要がありますが、 前の処理と同じブロックを読む可能性が高いということです。頻繁にアクセスされるデータはキャッシュされるので、 実際に表示されているコスト値よりも、パフォーマンスへのインパクトはかなり小さくなります。

最適化のためには、order by句で参照される インデックスの範囲がソートされていれば十分です。そのため、次のような、PRODUCT_IDだけでソートするような例でも、 最適化が行われます。

SELECT sale_date, product_id, quantity
  FROM sales
 WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY product_id

では、 スキャンされるインデックスの範囲内ではPRODUCT_IDが唯一の ソート条件であることが分かります。このインデックスの範囲では、インデックスの順序にorder by句が対応しているので、 データベースはソート処理をしなくて済むのです。

図対応するインデックス範囲でのソート順序

スキャンされるインデックスの範囲を拡げてしまうと、この最適化は予期せぬ動きをしてしまうことがあります。

SELECT sale_date, product_id, quantity
  FROM sales
 WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY product_id

このクエリでは、昨日の売上を取得する代わりに、 昨日からの売上全てを取得します。つまり、 このクエリは複数日をカバーするので、PRODUCT_IDでソートされていない範囲にまたがって実行されることになります。 を もう一度見て、スキャンされるインデックスの範囲を一番下まで拡げてみると、 PRODUCT_IDの小さい値が2回出てきてしまうことが分かるでしょう。データベースは、order by句を満たすために、 明示的にソート処理を行わなくてはならなくなってしまいました。

DB2
Explain Plan
-------------------------------------------------------------
ID | Operation              |                     Rows | Cost
 1 | RETURN                 |                          |  688
 2 |  TBSCAN                |     394 of 394 (100.00%) |  688
 3 |   SORT                 |     394 of 394 (100.00%) |  688
 4 |    FETCH SALES         |     394 of 394 (100.00%) |  688
 5 |     IXSCAN SALES_DT_PR | 394 of 1009326 (   .04%) |   24

Predicate Information
 5 - START ((CURRENT DATE - 1 DAYS) <= Q1.SALE_DATE)
Oracle
---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |  320 |  301 |
| 1 | SORT ORDER BY               |             |  320 |  301 |
| 2 |  TABLE ACCESS BY INDEX ROWID| SALES       |  320 |  300 |
|*3 |   INDEX RANGE SCAN          | SALES_DT_PR |  320 |    4 |
---------------------------------------------------------------

パイプライン処理を期待していても、データベースがソート処理を行ってしまう場合、(1) 明示的なソートがあった方がコスト値が低い、 (2) スキャンされるインデックスの範囲のインデックス順序がorder by句に対応していない、という2つの理由があり得ます。

協力してください

この記事が気に入ったら、私の書いた本「SQLパフォーマンス詳解」や私によるトレーニングもきっと気にいるはず。

2つのケースを見分ける簡単な方法は、order by句を完全に含むインデックスを使うことです。つまり、2つ目の理由に当てはまらないようにインデックスを調整するのです。 これでもデータベースが明示的なソート処理を行うのであれば、オプティマイザはコスト値によって判断していると分かります。 そうでなければ、データベースは元のorder byに対応する インデックスを使えないということになります。

ヒント

明示的なソートが行われてしまう原因を知りたければ、order by句を完全に含むインデックス定義を使ってみましょう。

どちらのケースでも、パイプライン化されたorder byが そもそも使えるのかどうか、使えるならどうすればいいのかが気になるでしょう。その場合は、order by句を完全に含むインデックスを使って、その結果を見てみればいいのです。恐らく、インデックスを勘違いしているか、 インデックスの順序は元のorder by句に必要ないものであるために、 データベースはそのインデックスを使ったソート処理ができないことに気付くのではないでしょうか。

オプティマイザが、コスト値を元に明示的なソート処理を選択してしまう時は、 クエリの完全な実行完了のために最適な実行計画を 選ぶためであることが多いです。言い換えると、オプティマイザは、結果の最後のレコードを最も早く得られる実行計画を選ぶのです。 もしアプリケーションが最初の数行しか結果を必要としないことをデータベースが分かっているのなら、order byに対応したインデックスを選ぶことでしょう。第7章, 「部分結果で、これに関する最適化法を説明します。

この説明が気に入れば、きっとこの本も 気に入るはず。

著者について

Markus Winandの写真

Markus Winand氏は、開発者がSQLパフォーマンスを改善するお手伝いをしています。彼は、SQL Performance Explainedの 著者でもあり、出張トレーニングhttp://winand.at/での リモート講義も 行っています。

彼の本

カバー『SQLパフォーマンス詳解』

核心をわかりやすく 解説。

Markusから購入します
(送料無料+PDF)

Amazonで購入
(印刷版のみ)

“Use The Index, Luke!” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
法律上の通知 | 接触 | 無保証 | 商標 | Privacy and GDPR | CC-BY-NC-ND 3.0 license