by Hayato Matsuura.

複合インデックス


データベースは、プライマリキーに対して自動的にインデックスを 作成しますが、キーが複数の列からなる時は、さらに手動で調整をする 余地があります。この場合、データベースはプライマリキーの全ての列に いわゆる 連結インデックス(あるいはマルチカラム インデックス、複合インデックス)を作成します。 複合インデックスの列の順番は、インデックスの使い勝手に大きな影響を 及ぼすので、注意して決定する必要があります。

例として、企業が合併した場合を考えてみましょう。他の会社の社員が 加わったので、EMPLOYEESテーブルが10倍の大きさになったと しましょう。ここで問題が発生します。EMPLOYEE_IDが、 それぞれの会社で一意になっていなかったのです。子会社IDのような追加の 識別子で、プライマリキーを拡張する必要があります。このため、プライマリ キーは、以前からのEMPLOYEE_IDに加えて、一意性を保つ ためのSUBSIDIARY_IDを加えた2列になりました。

新しいプライマリキーに対するインデックスは、以下のように 定義されます。

CREATE UNIQUE INDEX employee_pk
    ON employees (employee_id, subsidiary_id)

特定の従業員を呼び出すクエリでは、完全なプライマリキーを指定する 必要があります。つまり、SUBSIDIARY_ID列も指定 しなければなりません。

SELECT first_name, last_name
  FROM employees
 WHERE employee_id   = 123
   AND subsidiary_id = 30
DB2

Explain Plan
--------------------------------------------------------
ID | Operation             |                 Rows | Cost
 1 | RETURN                |                      |   13
 2 |  FETCH EMPLOYEES      |     1 of 1 (100.00%) |   13
 3 |   IXSCAN EMPLOYEES_PK | 1 of 10000 (   .01%) |    6

Predicate Information
 3 - START (Q1.EMPLOYEE_ID = +00123.)
     START (Q1.SUBSIDIARY_ID = +00030.)
      STOP (Q1.EMPLOYEE_ID = +00123.)
      STOP (Q1.SUBSIDIARY_ID = +00030.)

MySQL

+----+-----------+-------+---------+---------+------+-------+
| id | table     | type  | key     | key_len | rows | Extra |
+----+-----------+-------+---------+---------+------+-------+
|  1 | employees | const | PRIMARY | 10      |    1 |       |
+----+-----------+-------+---------+---------+------+-------+

以前の例と同じく、このクエリは複数行に一致することは ないので、MySQLはconstアクセスタイプを 使うことができます。2つの列を使うインデックスなので、 キーの長さ(key_len)が長くなっていることに注意 しましょう。アクセス述語とフィルタ述語の見分け方に詳しい 説明があります。

Oracle

---------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |    1 |    2 |
| 1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES    |    1 |    2 |
|*2 |  INDEX UNIQUE SCAN         | EMPLOYEES_PK |    1 |    1 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("EMPLOYEE_ID"=123 AND "SUBSIDIARY_ID"=30)

PostgreSQL

                QUERY PLAN
-------------------------------------------
 Index Scan using employees_pk on employees 
   (cost=0.00..8.27 rows=1 width=14)
   Index Cond: ((employee_id   = 123::numeric)
            AND (subsidiary_id = 30::numeric))

SQL Server

|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:employees_pk,
   |               SEEK:employee_id=@1 AND subsidiary_id=@2
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employees,
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

完全なプライマリキーを使ったクエリの場合、インデックスがいくつの 列からなっていたとしても、データベースはINDEX UNIQUE SCANを 使うことができます。しかし、キーの列のうちのひとつだけを使う場合、 以下の例のように、子会社の全従業員を検索してしまうことになります。

SELECT first_name, last_name
  FROM employees
 WHERE subsidiary_id = 20
DB2

Explain Plan
-------------------------------------------------------
ID | Operation         |                    Rows | Cost
 1 | RETURN            |                         |  689
 2 |  TBSCAN EMPLOYEES | 1195 of 10000 ( 11.95%) |  689

Predicate Information
 2 - SARG (Q1.SUBSIDIARY_ID = +00002.)

希望する結果を得るために、SUBSIDIARY_ID = 2 をつけてクエリを実行しています。これはここで説明することには影響しません。

TBSCANは、 フルテーブルスキャンが行われていることを表しています。

MySQL

+----+-----------+------+------+-------+-------------+
| id | table     | type | key  | rows  | Extra       |
+----+-----------+------+------+-------+-------------+
|  1 | employees | ALL  | NULL | 11000 | Using where |
+----+-----------+------+------+-------+-------------+

アクセスタイプALLは、フルテーブルスキャンが 行われることを表します。テーブルの全行が読みだされ、 where句と比較されます。

Oracle

----------------------------------------------------
| Id | Operation         | Name      | Rows | Cost |
----------------------------------------------------
|  0 | SELECT STATEMENT  |           |  106 |  478 |
|* 1 |  TABLE ACCESS FULL| EMPLOYEES |  106 |  478 |
----------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("SUBSIDIARY_ID"=20)

PostgreSQL

                QUERY PLAN
-------------------------------------------
 Seq Scan on employees 
   (cost=0.00..1398.50 rows=1070 width=14)
   Filter: (subsidiary_id = 2::numeric)

PostgreSQLのオペレーションSeq Scanでは、 フルテーブルスキャンが実行されます。

SQL Server

|--Table Scan(OBJECT:employees,
               WHERE:subsidiary_id=30)

実行計画を見ることで、データベースはインデックスを使わず、代わりに TABLE ACCESS FULLを実行することがわかります。これにより、 データベースはテーブル全体を読み込み、各行をwhere句と 比較します。この場合、テーブルの大きさに実行時間が比例するので、 テーブルが10倍の大きさになれば、TABLE ACCESS FULLにかかる 時間も10倍必要になります。この処理の危険なところは、開発環境の小さな データベースではそれなりの速度で動作しますが、ひとたび本番環境で実行すると たちまち重大なパフォーマンス問題を引き起こしてしまうことです。

フルテーブルスキャン

TABLE ACCESS FULLあるいはフルテーブル スキャンと呼ばれる処理は、テーブルのかなり多くの部分を 読み出す場合などは、最も効率的な方法になります。

これは、TABLE ACCESS FULLの処理では必要とされない、 インデックスの検索そのもののオーバーヘッドによるところがあります。 インデックスの検索では、現在指し示しているブロックを処理し終わった後で ないと、次に読むべきブロックがどれなのかが判断できません。 FULL TABLE SCANの場合、データベースが大きな塊 でデータを読み込む(マルチブロックリード )ために、一旦全テーブルを読み込んでしまいます。 データベースからデータを読み込んで行く度に発生する処理が少なくて 済むのです。

複合インデックスから任意の1つの列を選んで使う事はできないので、 データベースはインデックスを使いません。インデックスの構造をより深く 見ていくと、この理由がはっきりします。

複合インデックスは、ソートされたリストにインデックスのデータを 保存する他のインデックスと同じく、Bツリーインデックスです。データベースは、 インデックスのエントリをソートするのに、インデックスの定義に書かれた 順序に従って列を識別します。最初の列は並べ替えの優先順位が最も 高く、最初の列に同じ値が複数ある時に限り、2番目の列でも並べ替えが されます。

重要

複合インデックスは、複数の列にまたがるひとつの インデックスのことです。

2列からなるインデックスの順序付けは、最初に姓で並べ替え、 さらに名前で並べ替えるという点で、電話帳の順序付けと似ています。 名前だけで電話帳を引くことはできないように、2列のインデックスは、 2番目の列だけでの検索はできません。

図複合インデックス

はインデックスの一部を表したものです。子会社ID 20のエントリは、隣同士に 保存されているわけではありません。リーフノードにエントリは存在して いますが、SUBSIDIARY_ID = 20としてアクセスできるエントリが まとまっているわけではないことが分かるでしょう。このようなツリーでは、 2番目の列だけで検索するクエリは役に立たないのです。

ヒント

インデックスを視覚的に見るのは、 インデックスをうまく使えるのはどのようなクエリかを理解するのに 役立ちます。以下は、インデックスの順序でデータベースから エントリを取り出すクエリです(SQL:2008文法、LIMITTOPROWNUMを使った方法については、 を参照)。

SELECT <INDEX COLUMN LIST> 
  FROM <TABLE>  
 ORDER BY <INDEX COLUMN LIST>
 FETCH FIRST 100 ROWS ONLY

インデックスの定義とテーブル名をこのクエリに当てはめたら、 実行してデータを取り出してみましょう。欲しい行が一か所にかたまって いるかどうか確認しましょう。もしバラバラになっているようなら、 インデックスツリーは、欲しい行を探し出すのに役に立たないことに なります。

もちろん、SUBSIDIARY_IDに別のインデックスを追加する ことで、クエリの速度を上げることもできます。EMPLOYEE_ID だけで検索するのは意味がないのは分かっていますが、もっと良い解決策も あります。

インデックスの最初の列は常に検索に使えるという事実を、 うまく利用します。もう一度電話帳の例を考えてみましょう。 姓で検索する際には、名前を知っている必要はありません。つまり、 SUBSIDIARY_IDが最初に来るように、インデックスの列の 順序を変えてやればいいのです。

CREATE UNIQUE INDEX EMPLOYEES_PK 
    ON EMPLOYEES (SUBSIDIARY_ID, EMPLOYEE_ID)

2つの列を合わせたものは、一意であることには変わりありません ので、プライマリキーを完全に指定したクエリは、INDEX UNIQUE SCAN のままです。しかし、インデックスのエントリの順番は完全に変わっています。 SUBSIDIARY_IDが、並べ替えの際に最優先される条件になって います。これによって、ある子会社の全てのエントリは、インデックスに 連続して並んでいることになるので、データベースはBツリーを使って 検索することができるのです。

重要

複合インデックスを定義する際に考えるべき最も重要なのは、 そのインデックスを使えるSQL文ができるだけ多くなるように、 列の順番を決めることです。

実行計画から、データベースがこの「逆の」インデックスを使うことを 確認しましょう。SUBSIDIARY_IDだけでは、一意な結果はもう 得られなくなったので、データベースは、一致するエントリ全てを検索するため リーフノードをたどらなくてはなりません。これには、 INDEX RANGE SCANのオペレーションが実行されます。

DB2

Explain Plan
-------------------------------------------------------------
ID | Operation               |                    Rows | Cost
 1 | RETURN                  |                         |  128
 2 |  FETCH EMPLOYEES        |  1195 of 1195 (100.00%) |  128
 3 |   RIDSCN                |  1195 of 1195 (100.00%) |   43
 4 |    SORT (UNQIUE)        |  1195 of 1195 (100.00%) |   43
 5 |     IXSCAN EMPLOYEES_PK | 1195 of 10000 ( 11.95%) |   43

Predicate Information
 2 - SARG (Q1.SUBSIDIARY_ID = +00002.)
 5 - START (Q1.SUBSIDIARY_ID = +00002.)
      STOP (Q1.SUBSIDIARY_ID = +00002.)

この実行計画は、インデックスを使う前の実行計画と比べると 複雑になっています。キーの操作は相変わらず存在していますが、IXSCANは インデックスの範囲スキャンを意味し、FETCHはテーブルアクセスを表しています。 この処理の間には、意図しないSORTRIDSCN処理が含まれており、 SORT処理では、インデックスから取り出したエントリを ヒープテーブル上の行の物理的なストレージの場所に応じて並べ替えています。 それからRIDSCANは関係するデータベースのページをすべてプリフェッチ します(複数の隣り合うブロックを一つのIO操作にまとめています)。

MySQL

+----+-----------+------+---------+---------+------+-------+
| id | table     | type | key     | key_len | rows | Extra |
+----+-----------+------+---------+---------+------+-------+
|  1 | employees | ref  | PRIMARY | 5       |  123 |       |
+----+-----------+------+---------+---------+------+-------+

MySQLのアクセスタイプrefは、Oracleの INDEX RANGE SCANと同等の操作です。

Oracle

--------------------------------------------------------------
|Id |Operation                   | Name        | Rows | Cost |
--------------------------------------------------------------
| 0 |SELECT STATEMENT            |             |  106 |   75 |
| 1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |  106 |   75 |
|*2 |  INDEX RANGE SCAN          | EMPLOYEE_PK |  106 |    2 |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("SUBSIDIARY_ID"=20)

PostgreSQL

                 QUERY PLAN
----------------------------------------------
 Bitmap Heap Scan on employees
 (cost=24.63..1529.17 rows=1080 width=13)
   Recheck Cond: (subsidiary_id = 2::numeric)
   -> Bitmap Index Scan on employees_pk
      (cost=0.00..24.36 rows=1080 width=0)
      Index Cond: (subsidiary_id = 2::numeric)

PostgreSQLはこの場合、Bitmap Index Scanと、 それに続くBitmap Heap Scanという、2つの オペレーションを実行します。これは、大まかに言うとOracleの INDEX RANGE SCANTABLE ACCESS BY INDEX ROWID に当たりますが、1つだけ重要な違いがあります。まずBitmap Index Scanでインデックスから全ての結果を引き出し、 それからBitmap Heap Scanで、行の物理的な場所が 保存されているヒープテーブルを元に行を並べ替え、テーブルから 必要な行の全てを取り出します。この方法により、テーブルに対する ランダムIOアクセス回数を減らすことができます。

SQL Server

|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:employees_pk,
   |               SEEK:subsidiary_id=20
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employees,
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

通常、データベースは、最初の(一番左の)列で検索を行う時に 複合インデックスを使うことができます。3列に対する複合インデックスを 作った時は、1番目の列だけで検索する場合、1番目と2番目の列で検索する 場合、全ての列で検索する場合に、そのインデックスが使えます。

2つインデックスを作ると、selectの パフォーマンスはよくなりますが、インデックスは1つの方がよいでしょう。 ストレージ領域の節約だけにとどまらず、2番目のインデックスのメンテナンスの オーバーヘッドも減らすことができるからです。テーブルに対するインデックスの 数が少ないほど、insertdeleteupdateのパフォーマンスは向上します。

適切なインデックスを定義するには、インデックスがどのように動作 するかだけを知っていればいいわけではなく、アプリケーションがデータベースに どのようにデータを問い合わせるかを知っている必要があります。つまり、 where句に、どのような列の組み合わせが出てくるかを 知っておかなければならないということです。

アプリケーションのデータに対するアクセスパスの概要を知らない外部の コンサルタントにとって、適切なインデックスを定義するのは非常に難しいこと です。コンサルタントは、ある1つのクエリだけを考慮の対象にすることが多いで しょう。インデックスが他のクエリにまでよい影響を与えるように設計することは ありません。データベース管理者にしても、データベースのスキーマについては 詳しいかもしれませんが、アクセスパスを深く理解していないであろう点では、 同じようなものです。

データベースの技術的な知識とビジネスの機能的な知識がうまく交わる 唯一の場所は、開発を行う部署です。開発者は、データに対する勘がはたらく でしょうし、アクセスパスを知っています。小さな負担で、アプリケーション 全体に最も有益な形で正しいインデックスを作ることができるでしょう。

著者について

Markus Winandの写真

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

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