リレーショナルなSQLデータベースかリレーショナルでないシステムかに関わらず、正しいインデックスを作ることは、クエリの応答時間を短くする最善の方法です。

USE THE INDEX, LUKE!

僕はパフォーマンスチューニングをしたことがありません。RDBのインデックスを使うとクエリが速くなるという話は聞いたことがありましたが、実際のSQLに対してどのようにインデックスが使用されて、どれくらいのパフォーマンスが出ているのかは考えたことがありませんでした。

そんなときに、RDBのインデックスとチューニングに関するオンラインブック「USE THE INDEX, LUKE!」を読み、とても参考になりました。この投稿は、そのオンラインブックを自分の理解のためにまとめたものです。

1章はインデックスの構造とパフォーマンスへの影響について、2章は実際のSQLでどのようにインデックスが使われるかについて書いていきます。1章はインデックスについての概要を振り返るため、2章は実際のSQLでどのようにチューニングを行うかの参考にするためにまとめています。

インデックスの構造とパフォーマンス

インデックスの構造

インデックスはクエリの実行を速くするために存在し、双方向連結リストと探索木というデータ構造を組み合わせたものになっています。双方向連結リストは連続したデータへの効率的なアクセスのために使用され、探索木は高速な検索のために使用されています。

インデックスは実際のテーブルデータとは別に、メタデータとして持たせます。実際のテーブルデータを連続的なデータにすると、更新のたびに大量のデータをずらす必要が出てくるのでパフォーマンスが悪いです。その対策としてテーブルデータの並び順とは独立して、論理的な順序付けを双方向連結リストで作っています。

インデックスは、インデックスを張ったカラムであるキーとテーブルデータ行への参照の組を複数持つリーフノードが双方向連結リストで繋がれています。インデックスから行を取得するためには、キーを使用してリーフノードを見つけ、テーブルデータ行への参照を使って、実際のテーブルデータにアクセスします。

双方向リストだけでは、キーを探すのに最悪でリーフノードの数だけアクセスが必要になるので、探索木を使用して効率的に検索できるようにしています。探索木は、各リーフノードから選んだ一つのキーを一定数並べてブランチノードとします。さらに各ブランチノードから選んだ一つのキーを一定数並べてルートノードとします。これらのノード同士を参照させて、ルートノードからキーの大小によって効率的に検索が行えるようにしています。

b-tree

探索木は、リーフノード数の増加に対して木の深さの増加が遅いため、データが増加してもパフォーマンスが下がりにくいという性質があります。探索木の検索は、親ノードから子ノードをたどっていく構造なので、たどる数は木の深さによって決まり、木が浅いほうがパフォーマンスが良くなりやすいです。

テーブルデータやインデックスの各ノードは、データベースブロックやページと呼ばれる、データベースが扱える最小の格納単位に保存されています。16KBや8KBなどの単位が使われます。

インデックスの検索が遅いケース

インデックスを利用していても期待するほど高速にはならない場合もあります。インデックスが劣化してくるのが原因だとよく言われていましたが、インデックスの再構築によってリーフノードを減らしても、殆どの場合インデックスの深さは削減されないため、パフォーマンスはそこまで良くなりません。

実際に検索が遅くなる原因は2つで

リーフノードのチェーン
テーブルへのアクセス

です。

1つ目のリーフノードのチェーンは、双方向連結リストによって繋げられたリーフノードを大量に辿らなければいけないときに問題になります。例えば、選択性の悪いインデックスを使用しているケースや、複合インデックスの順序が適切ではないケースなどです。選択性の悪いインデックスとは、多くの行が同じ値を持つカラムに対して作成されたインデックスのことで、これを使用して値を絞り込んでも、行数が多いために大量のリーフノードをたどる必要が出てきます。

2つ目のテーブルへのアクセスは、検索の度に大量のテーブルへのアクセスが発生しているときに問題になります。一つのリーフノードだけでも数百のエントリを保持していることがあり、対応するテーブルの行は、通常、たくさんのテーブルブロックに分散して保存されています。データベースは同じテーブルブロックに格納されているデータは1回の読み込みで取得できるのですが、複数のデータブロックに分散している場合、データベースは多くの行を読み取る必要が出てきます。例えば、インデックスだけでデータを絞り込めないときや、インデックスを使用していても絞り込んだ結果の行が多いときに問題になります。

インデックスによる検索は、

ツリーの走査
リーフノードのチェーンをたどる
テーブルからデータを読み出す

という手順で行われます。ツリーの走査はインデックスによって効率的に行うことができるのですが、それ以外の2ステップではたくさんのブロックにアクセスする必要があるため、検索が遅い原因になってしまいます。

アクセス・フィルター述語

インデックスを使用した検索が遅くなっている原因を知るために、クエリの実行計画からアクセス・フィルター述語を確認するのが役に立つ場合があります。

アクセス述語は、インデックス操作の始めと終わりを決める条件です。つまり、リーフノードの走査の開始と終了の条件を表しています。例としてOracleの実行計画では、INDEX UNIQUE SCANというアクセス方法で、access("EMPLOYEE_ID"=123)というアクセス述語が使用されているといった情報が表示されます。このアクセス述語は、インデックスツリーの中でEMPLOYEE_IDが123であるエントリだけを取得していることを表しています。

フィルター述語には、インデックス・テーブルの2種類が存在し、インデックスフィルター述語はリーフノード走査時に適用されるフィルターで、テーブルフィルター述語はテーブルデータをロードしたあとに適用されるフィルターです。Oracleの実行計画では、filter("SUBSIDIARY_ID"=30)のように表示されます。テーブルフィルター述語はインデックスフィルター述語と違い、実際のテーブルを読み込む必要があるため、アクセス対象となっているリーフノードの数が大きい場合には、無駄なテーブルアクセスが増えてしまうため、遅くなってしまいます。

インデックスを使って効果的に検索を行うためには、できるだけフィルター述語を減らしてアクセス述語だけで検索が行われている必要があります。アクセス述語とインデックスフィルター述語が使用されている場合には大量のリーフノードを走査している可能性があり、アクセス述語とテーブルフィルター述語が使用されている場合には大量のテーブルアクセスが発生している可能性があります。

インデックスでのクラスタリング

インデックスはデータをクラスタリングすることができ、遅くなる原因である大量のテーブルアクセスを減らすことができます。データのクラスタリングとは、少ないI/O処理でアクセスできるように、連続してアクセスされるデータを近くに保存することをいいます。ここではデータベースの集合を表すコンピュータークラスタではなく、データクラスタという意味で使っています。

インデックスでのクラスタリングによってパフォーマンスを向上させる方法には、以下のようなものがあります。どの方法も、インデックスに追加の情報を持たせることで、負荷の高いテーブルアクセスを減らす方法と言えます。

意図的なフィルター述語の使用
カバリングインデックス
クラスタ化インデックス

意図的なフィルター述語の使用では、テーブルフィルターをインデックスフィルターとして使用することで、パフォーマンスを向上させることができます。WHERE句の条件にインデックスを使用できない場合、その条件はテーブルフィルターとして使われることになるのですが、テーブルフィルターではテーブルデータをロードする必要があるため、条件と一致しない行が多いほど無駄になってしまいます。そこで、インデックスに列を追加してインデックスフィルターとして利用させることでフィルタリングをインデックスだけで行えるようにできます。

カバリングインデックスは、クエリに必要な情報がすべてインデックスに存在している状況のことで、テーブルアクセスを完全になくすことができます。クエリのSELECTやWHEREに存在する列がすべてインデックスに乗っている場合にカバリングインデックスになります。

!

PostgreSQLはデータを削除してもすぐには削除されず、VACUUMという処理で実際に削除されます。そのため、インデックスが存在していてもデータが常に存在しているとは限らないので、テーブルのブロック単位での可視性が保存されているVisibility Mapを参照する必要があります。アクセスしようとしているブロックに削除されているレコードがある場合には実際にテーブルにアクセスしに行く必要があります。

MySQLでもデータはすぐに削除されず、パージという処理で実際に削除されます。この処理はトランザクションが終了したときに自動的に行われるのですが、長時間トランザクションを実行していると問題になりやすいです。

クラスタ化インデックスは、すべてのテーブルデータが保存されているインデックスです。1つのインデックスしか持たないテーブルの場合には向いているのですが、インデックスが複数あるとパフォーマンスが落ちてしまいます。2つ目以降はセカンダリインデックスと呼ばれ、データにはクラスタ化インデックスのキーが格納されており、テーブルにアクセスするためにはクラスタ化インデックスを走査する必要が出てくるためです。

インデックスは参照を効率的に行えますが、更新系のクエリにとってはネガティブな影響を与えることが多いため、インデックスの数は小さく保つことが非常に重要です。データがインサートされるとインデックスにもデータを追加する必要がありますし、インデックスツリーのバランスを保つためのメンテナンスも行う必要があるため、インデックスが増えるほどこのコストが大きくなってきます。

!

参照元のページでは、近い値の列を持つインデックスリーフノード同士が近くに配置されることをクラスタ化されていると言っていると読み取れます。しかし、紹介されている3つの手法はクラスタリングによってパフォーマンスが向上する例ではないと思います。例えば「意図的なフィルター述語の使用」では、インデックスがクラスタリングを行わなくてもテーブルアクセスは減ります。単純にインデックスに必要な値をもたせることでテーブルアクセスを減らしている手法だと思います。

参照元のページではクラスタリングの定義として、「連続的にアクセスされるデータを近くに保存すること」と書いてあります。無理矢理ではありますが、この抽象的な定義を拡大解釈して、「インデックスに連続的にアクセスされる追加の情報をもたせること」もクラスタリングと呼びます。例えば「意図的なフィルター述語の使用」では、「連続的にアクセスされる追加の情報」をアクセス述語のあとにフィルター述語によってアクセスされるテーブルの列、「近く」をアクセス述語によってアクセスされるインデックスのノードとします。そのうえで、インデックスの中にアクセス述語で必要だった列とフィルター述語で必要だった列を含めることをクラスタリングと呼びます。

インデックスが持つ3つの力

インデックスの強力な特徴は以下の3つです。これらの特徴のおかげで、インデックスを正しく使用することでクエリのパフォーマンスを向上させることができます。

検索に適したデータ構造
クラスタ化されたデータ
ソートされたデータ

検索に適したデータ構造とはB-Treeのことで、上述したように高速な検索が可能です。ツリーのバランス構造によって同じステップ数ですべての要素にアクセスできるため、巨大なデータセットに対してもほとんど一瞬で処理できます。また、リーフノードの数の増加に比べてツリーの深さの増加が非常に遅いという理由もあります。

クラスタ化されたデータとは、インデックスに様々なデータを持たせることができるという特徴です。インデックスに含まれるデータは、基本的にインデックスリーフノードの範囲を絞り込むアクセス述語として使われるのが理想的です。一方で、インデックスにはその他のデータも含めることができ、フィルター述語のためのデータやクエリが返す必要のあるデータを持たせることで、クエリのパフォーマンスが向上するケースも存在します。

ソートされたデータとは、インデックスは持っている列の値によってソートされているという特徴です。この特徴によって、並び替えが必要なクエリのソート処理が不要になるケースがあります。その結果、ソートするためにすべての行を読み込む必要が無くなり、必要な行を取得できたら読み込みを中断するという最適化の余地も生まれます。このように、すべてのデータが処理されるのを待たずに部分的な結果を返すような仕組みをパイプライン化といいます。

インデックスはどう使われるか

この章では、実際のSQLでインデックスがどのように使用されるかを書いていきます。インデックスの使われ方は、実際に格納されているデータや統計情報によって異なるので、ここでは一例として書いています。

WHERE

以下のような複合インデックスでは、

CREATE UNIQUE INDEX employees_pk
    ON employees (employee_id, subsidiary_id)

以下のような等価演算のみのSQLを実行してもインデックスは使用されず、フルテーブルスキャンが実行されます。

SELECT first_name, last_name
  FROM employees
 WHERE subsidiary_id = 20

上のインデックスでは、まずemployee_idで並び替えられたあと、subsidiary_idで並び替えられます。そのため、subsidiary_idの順には並んでおらず、インデックスを使って効率的に検索することはできません。インデックスを使用させるためには、列を並び替える必要があります。

次は、範囲検索と等価演算が含まれるSQLを見ていきます。

SELECT first_name, last_name, date_of_birth
  FROM employees
 WHERE date_of_birth >= TO_DATE(?, 'YYYY-MM-DD')
   AND date_of_birth <= TO_DATE(?, 'YYYY-MM-DD')
   AND subsidiary_id  = ?

このようなSQLに対して、date_of_birth、subsidiary_idの順に並んでいるインデックスの場合はどうなるでしょうか。仮にそのインデックスが使われる場合のOracleの実行計画は以下のようになります。

CREATE UNIQUE INDEX emp_test
    ON employees (date_of_birth, subsidiary_id)

--------------------------------------------------------------
|Id | Operation                    | Name      | Rows | Cost |
--------------------------------------------------------------
| 0 | SELECT STATEMENT             |           |    1 |    4 |
|*1 |  FILTER                      |           |      |      |
| 2 |   TABLE ACCESS BY INDEX ROWID| EMPLOYEES |    1 |    4 |
|*3 |    INDEX RANGE SCAN          | EMP_TEST  |    2 |    2 |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter(:END_DT >= :START_DT)
3 - access(DATE_OF_BIRTH >= :START_DT 
       AND DATE_OF_BIRTH <= :END_DT)
    filter(SUBSIDIARY_ID  = :SUBS_ID)txt

idが3のINDEX RANGE SCANエントリで使用されている述語をみると、date_of_birthの条件はアクセス述語として使用されているのですが、
subsidary_idの条件はインデックスフィルター述語として使用されていることがわかります。この場合には無駄なリーフノードの走査が発生しています。例えば、指定された範囲のdate_of_birthが複数件存在し、指定されたsubsidiary_idが1件しか存在しないときには、無駄なリーフノードの走査が発生します。

一方でsubsidiary_id、date_of_birthの順に並んでいるインデックスが存在する場合には、
sub_sidiary_idが1件しかない場合にはそこで打ち切られるので、無駄なリーフノードをたどる必要がなくなります。Oracleの実行計画は以下のようなものが考えられます。

CREATE UNIQUE INDEX emp_test2
    ON employees (subsidiary_id, date_of_birth)

---------------------------------------------------------------
| Id | Operation                    | Name      | Rows | Cost |
---------------------------------------------------------------
|  0 | SELECT STATEMENT             |           |    1 |    3 |
|* 1 |  FILTER                      |           |      |      |
|  2 |   TABLE ACCESS BY INDEX ROWID| EMPLOYEES |    1 |    3 |
|* 3 |    INDEX RANGE SCAN          | EMP_TEST2 |    1 |    2 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter(:END_DT >= :START_DT)
3 - access(SUBSIDIARY_ID  = :SUBS_ID
       AND DATE_OF_BIRTH >= :START_DT
       AND DATE_OF_BIRTH <= :END_T)

subsidiary_idとdate_of_birthの条件が両方ともアクセス述語として使用されているため、無駄なリーフノードの走査は存在しません。

これは複合インデックスの仕組みを考えるとわかります。複合インデックスでは、最初の列で並べられたあとに次の列で並び替えるため、2番目の列は連続して並んでいるわけではありません。

大ざっぱに言うと、インデックスはまず等価性を確認するためにあり、それから範囲を調べるために使われます。

USE THE INDEX, LUKE!

また、インデックスを使用するよりもフルテーブルスキャンを実行したほうが速くなるケースというのも存在します。例えば以下のようなインデックスとSQLを考えます。

CREATE UNIQUE INDEX EMPLOYEES_PK 
    ON EMPLOYEES (SUBSIDIARY_ID, EMPLOYEE_ID)

SELECT first_name, last_name, subsidiary_id, phone_number
  FROM employees
 WHERE last_name  = 'WINAND'
   AND subsidiary_id = 30

このとき、テーブルの中にsubsidiary_idが30の行が大量に存在する場合、データベースはその行に対して1行ずつデータを読み出すことになるため、クエリは遅くなり、フルテーブルスキャンを行ったほうが早くなるというケースがありえます。もちろん、last_nameへのインデックスを追加することで、より効果的な検索を行えるようにはなります。

これら例のように、適切なインデックスを追加するためには、何かの一般論に従うのではなく、実際のアプリケーションがどのようにデータベースにアクセスするのかを把握しておく必要があります。最も選択性の高い列をインデックスの左に置けばよいという都市伝説も存在しますが、その列が使われないのであればそのインデックスは意味がありません。

JOIN

データベースは結合するために、入れ子ループ、ハッシュ結合、ソートマージというアルゴリズムを使い分けています。

入れ子ループを使用する場合、以下のようなインデックスとSQLでは、

CREATE INDEX emp_up_name ON employees (UPPER(last_name))

CREATE INDEX sales_emp ON sales (subsidiary_id, employee_id)

SELECT e0_.employee_id AS employee_id0
       -- MORE COLUMNS
  FROM employees e0_ 
  LEFT JOIN sales s1_ 
         ON e0_.subsidiary_id = s1_.subsidiary_id 
        AND e0_.employee_id = s1_.employee_id 
 WHERE UPPER(e0_.last_name) LIKE ?

以下のような実行計画が表示されます。

---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |  822 |   38 |
| 1 | NESTED LOOPS OUTER          |             |  822 |   38 |
| 2 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |    1 |    4 |
|*3 |   INDEX RANGE SCAN          | EMP_UP_NAME |    1 |      |
| 4 |  TABLE ACCESS BY INDEX ROWID| SALES       |  821 |   34 |
|*5 |   INDEX RANGE SCAN          | SALES_EMP   |   31 |      |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
  3 - access(UPPER("LAST_NAME") LIKE 'WIN%')
      filter(UPPER("LAST_NAME") LIKE 'WIN%')
  5 - access("E0_"."SUBSIDIARY_ID"="S1_"."SUBSIDIARY_ID"(+)
        AND  "E0_"."EMPLOYEE_ID"  ="S1_"."EMPLOYEE_ID"(+))

データベースは、EMP_UP_NAMEを使ってEMPLOYEESテーブルから結果を取り出した後、SALESテーブルから各従業員に対応するレコードを抽出しています。アルゴリズムの名前に入れ子ループとあるように、検索したEMPLOYEESテーブルのデータを1行ずつ取り出してSALESテーブルの行と結合していきます。外側(ここではEMPLOYEESテーブルの絞り込み)の行数が少ない場合には良いパフォーマンスを発揮します。そのため、チューニングでは外側のクエリができるだけ小さい行数を返すようにする必要があります。

一方で、結合の片側のレコードをハッシュテーブルに一度に読み込むというのが、ハッシュ結合アルゴリズムです。入れ子ループ結合では外部クエリの行数が多いと、ループで結合を行うという性質上、内部クエリでBツリーへの走査が大量発生してしまうというデメリットが存在します。上の例でいうと、EMPLOYEESテーブルから1行取り出してSALESテーブルの行と結合するという操作を、EMPLOYEESテーブルの行数分繰り返すことになります。そのため、SALESテーブルのインデックスツリーを何度も走査する必要が出てきます。そこで、結合の片側の対象レコードを一旦全てハッシュテーブルに読み込んでおくことで、高速に突き合わせができるようにしています。

以下のようなインデックスとSQLでは、

CREATE INDEX sales_date ON sales (sale_date)

SELECT *
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH

以下のような実行計画が表示されます。

--------------------------------------------------------------
| Id | Operation                    | Name      | Bytes| Cost|
--------------------------------------------------------------
|  0 | SELECT STATEMENT             |           |   59M| 3252|
|* 1 |  HASH JOIN                   |           |   59M| 3252|
|  2 |   TABLE ACCESS FULL          | EMPLOYEES |    9M|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| SALES     |   10M| 1724|
|* 4 |    INDEX RANGE SCAN          | SALES_DATE|      |     |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID"  )
   4 - access("S"."SALE_DATE" > TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)

入れ子ループ結合では結合条件でインデックスが使用されていますが、ここではフルテーブルアクセスになっています。結合時には一度すべてのテーブルデータを読み込んでハッシュテーブルに格納し、ハッシュ結合時にそのテーブルを使用しています。結合条件でインデックスは使われていませんが、Id4をみると、独立したテーブルの条件に使われているsale_dateには、インデックスが使用されていることがわかります。

ハッシュ結合のニューニングは入れ子ループ結合とは全く異なる、ハッシュテーブルのサイズを小さくするというアプローチが必要になります。例えば、SELECTで*を使用せずに、必要な列を明示的に指定することでサイズを小さくすることができます。

ソートマージ結合は、結合属性でソートされた2つのテーブルを結合する方法で、左外部結合と右外部結合を同時に実行する、完全外部結合が可能です。テーブルが既に並び替えられている場合にはパフォーマンスが良いですが、並び替えられていない場合は、ソートの処理が重いのであまり利用されていません。

ORDER BY

インデックスには順序があるので、ORDER BY付きのSQLでは、関連するインデックスが行をすでに並び替えている場合、結果をソートする必要がなく、パフォーマンスが良くなります。

以下のようなインデックスとSQLでは、

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

以下のような実行計画が表示されます。

---------------------------------------------------------------
|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を、パイプライン化されたORDER BYと呼びます。

パイプライン化されたORDER BYは、どちらの方向にも進むことができます。例えば、以下のようなインデックスとSQLでも、ORDER BYの順序が揃っているので、ソートはスキップされます。

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 DESC, product_id DESC

GROUP BY

データベースは、GROUP BYのためにハッシュアルゴリズムとソートグループアルゴリズムを使い分けます。ハッシュアルゴリズムは、一時的なハッシュテーブル上でまとめて全レコードを処理したあとに結果を返すもので、ソートグループアルゴリズムは、グループキーでソートすることで各グループを順番に処理できるようにするものです。

ソートグループアルゴリズムでは、インデックスを使用することでソートの処理が不要になり、パフォーマンスが向上します。ここではこのようなGROUP BYをパイプライン化されたGROPU BYと呼びます。

以下のようなインデックスとSQLでは、

CREATE INDEX sales_dt_pr ON sales (sale_date, product_id)

SELECT product_id, sum(eur_value)
  FROM sales
 WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
 GROUP BY product_id

以下のような実行計画が表示されます。

---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |   17 |  192 |
| 1 | SORT GROUP BY NOSORT        |             |   17 |  192 |
| 2 |  TABLE ACCESS BY INDEX ROWID| SALES       |  321 |  192 |
|*3 |   INDEX RANGE SCAN          | SALES_DT_PR |  321 |    3 |
---------------------------------------------------------------

sale_dateが一つに特定され、product_idで並び替えているのでインデックスを使用することができ、
SORT GROUP BYに、NOSORTという補足がついています。

一方で、以下のSQLのようにsale_dateが一つに特定できず、パイプライン化されたORDER BYが使用できない場合には、

SELECT product_id, sum(eur_value)
  FROM sales
 WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
 GROUP BY product_id

以下のような実行計画が表示されます。

---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |   24 |  356 |
| 1 | HASH GROUP BY               |             |   24 |  356 |
| 2 |  TABLE ACCESS BY INDEX ROWID| SALES       |  596 |  355 |
|*3 |   INDEX RANGE SCAN          | SALES_DT_PR |  596 |    4 |
---------------------------------------------------------------

ここではハッシュアルゴリズムが使用されています。ハッシュアルゴリズムはソートグループアルゴリズムと違い、集計結果だけをバッファリングしておけばよいので、必要なメモリが少なくなります。

LIMIT

パイプライン化したORDER BYを使用する場合、データベースに全行を取得しないことを伝えるためにLIMTIやFETCH FIRSTを使うことで、全行を取得する前に実行を止めることができます。

例えば、以下のようなインデックスとSQLでは、

CREATE INDEX sales_dt_pr ON sales (sale_date, product_id)

SELECT *
  FROM sales
 ORDER BY sale_date DESC
 FETCH FIRST 10 ROWS ONLY

以下のような実行計画が表示されます。

-------------------------------------------------------------
| Operation                     | Name        | Rows | Cost |
-------------------------------------------------------------
| SELECT STATEMENT              |             |   10 |    9 |
|  COUNT STOPKEY                |             |      |      |
|   VIEW                        |             |   10 |    9 |
|    TABLE ACCESS BY INDEX ROWID| SALES       | 1004K|    9 |
|     INDEX FULL SCAN DESCENDING| SALES_DT_PR |   10 |    3 |
-------------------------------------------------------------

COUNT STOPKEYを使用した実行停止が計画されていることがわかります。パイプライン化されたORDER BYを使用した最初のN件の選択は、テーブルが大きくなってもパフォーマンスはほぼ変わらないため、スケーラビリティがあります。一方で、インデックスが存在せず、パイプライン化したORDER BYが使用できない場合は以下のような実行計画になります。

--------------------------------------------------
| Operation               | Name  | Rows |  Cost |
--------------------------------------------------
| SELECT STATEMENT        |       |   10 | 59558 |
|  COUNT STOPKEY          |       |      |       |
|   VIEW                  |       | 1004K| 59558 |
|    SORT ORDER BY STOPKEY|       | 1004K| 59558 |
|     TABLE ACCESS FULL   | SALES | 1004K|  9246 |
--------------------------------------------------

ソートが行われていないため、まず全行を読み込んでソートを行ったあと、SORT ORDER BY STOPKEYによって最初のN件を選択するクエリが実行されます。COUNT STOPKEYは存在していますが、そこに至るまでに1004Kの行を処理する必要があります。すべてのデータにアクセスしているため、テーブルサイズが大きくなるとパフォーマンスは劣化しやすいです。

さいごに

「遅くなるインデックスと速くなるインデックス」という観点で、USE THE INDEX, LUKE!を自分なりにまとめました。

インデックスはどんな使い方でも速くなるわけではなく、遅くなるケースを理解しておく必要があると感じました。その理解のために「インデックスを使っても検索が遅いケース」と「アクセス・フィルター述語」の内容が役に立つと思うので、覚えておきたいです。

この投稿では、一部のSQLでインデックスがどのように使用されるかを紹介しましたが、実際のアプリケーションでは、より多様なSQLが使用されます。この投稿や、USE THE INDEX, LUKE!にある例を参考にして、実際に問題が発生したときに役に立つことを願っています。

Discussion