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


Applies to
DB2Yes
MySQLYes
OracleYes
PostgreSQLYes
SQL ServerYes

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

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

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


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

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

このクエリでは、昨日の売上を取得する代わりに、 昨日からの売上全てを取得します。つまり、 このクエリは複数日をカバーするので、PRODUCT_IDで ソートされていない範囲にまたがって実行されることになります。 図 6.1を もう一度見て、スキャンされるインデックスの範囲を一番下まで拡げてみると、 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つの理由があり得ます。

初心者からエキスパートまで役に立つ内容です。
特に駆け出しのエンジニアは持っておくといい

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

Tweet this tip

ヒント

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

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

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

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

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