インデックスの基礎知識

インデックスとは

データベースの世界で、インデックス(索引)とはテーブルに格納されているデータを

高速に取り出す為の仕組みを意味します。

インデックスを適切に使用することによってSQL文の応答時間が劇的に改善

される可能性があります。

インデックスにはB-Treeインデックスをはじめ、ビットマップインデックス、

関数インデックスなどの種類がありますが、ここでは最も一般的に使われ、かつ

ほとんどのDBMSでサポートされているB-Treeインデックスについて解説します。

※ CREATE INDEX文でオプションを指定しない場合は通常B-Treeインデックスが

作成されます。


B-Treeインデックスのしくみ

B-Tree(Balanced Tree)インデックスは次のようなツリー状の構造になっています。



ツリーの先頭はヘッダブロックと呼ばれています。ヘッダブロックでは、キー値の

範囲と下層のブロックへのポインタを管理していて、キーの値が指定された場合に、

次にどのブロックを読めばいいかが分かるようになっています。

ブランチブロックはキー値を更に細かく分割して管理しています。キー値が多い

場合はブランチブロックが複数連なります。

リーフブロックは最下層のブロックでキー値とテーブルの行の物理的な位置を

管理しています。又、リーフブロックには前後のリーフブロックへのポインタが

含まれており、<、>、BETWEENなどの範囲検索がスムーズに行われます。

図のインデックスを使って「TSUMIKI」を検索する場合、次のような経路で実際の行への

アクセスが行われます。



B-Treeインデックスの特徴

B-Treeインデックスはその構造から次のような特徴を持っています。

・どのようなキー値でも、同一の速度が期待できる。
 (これは全てのリーフブロックが同じ深さになっているためです。)

・大量のデータでも良いパフォーマンスが期待できる。
 (これは大量のデータを格納した場合でも、インデックスの深さが4ブロック以内に
 収まることが多いためです。又、ヘッダやブランチ部分はメモリ上にロードされて
 いることが多く、実際には1,2ブロックの読み込みで済むことから推測されます。)

・一致検索(=による検索)だけでなく、範囲検索(<,>,BETWEENによる検索)を行うことが
 できる。(これはリーフブロックに前後のリーフブロックへのポインタが
 含まれており、前後のデータを連続して処理することが出来るためです。)

・ソート処理を高速に行うことが出来る。
 (これはインデックス内の各データが既にソートされて格納されているためです。)


B-Treeインデックス使用時のオーバーヘッド

B-Treeインデックスは柔軟で効率的な検索をサポートしてくれます。

しかしその一方で、データを更新するときには、その構造を維持するために

オーバーヘッドが発生します。

インデックスが複数設定されていると、更新処理に必要な時間が数倍になることも

あります。

インデックスを作成する場合には、更新系処理と検索系処理のバランスを考えながら

作業することが必要になります。

なお、比較的大きな表では更新系処理よりも検索系処理の方が負荷が高いため、

一般的にはインデックスを作成した方が、トータルパフォーマンスは向上する

可能性が高いようです。

また、当然ながらインデックスを作成するには、そのためのディスク容量が必要に

なります。個々のインデックスの容量は表に比べれば小さいものですが、ひとつの

表に複数のインデックスを作成した場合には、表とインデックスを合計した容量が

元の表の2倍以上になることもあります。


B-Treeインデックスが有効に動作するデータ取得量

B-Treeインデックスが有効に動作するのは、取得するデータの量が表全体の

5%〜15%以下の場合です。一概には言えませんが、それ以上のデータを取得する

場合や、検索する表の容量が小さい場合は、インデックスを使用しないで全表走査

(表のすべての行を読み込んでWHERE条件を判定)した方が高速になります。


B-Treeインデックスの選択性

重複しているキー値が少なければ選択性が高く、インデックスは有効に働きます。

たとえば誕生日を表す列は選択性が優れていますが、性別を表す列は選択性は

悪いでしょう。

選択性の優れているインデックスは特定のキー値で対象となるデータを

絞り込めるので効率的に機能します。

ユニークインデックスやプライマリキー(NULLを許可しないユニークインデックス)は

最も選択性の高いインデックスです。たとえ膨大な量のデータが存在する表でも、

プライマリキーを使用した一意検索であれば1秒以下の応答が期待できます。

なお、OracleなどのDBMSでは選択性の悪い列に対して効果を発揮するビットマップ

インデックスというインデックスがサポートされています。


結合インデックス

結合インデックスとは、複数の列で構成されるインデックスのことです。

WHERE句でよく複数の列が指定される場合は、それらの列に対してインデックスを

作成するとより効果的な検索が可能になります。

たとえば、

SELECT
  first_name,second_name
FROM
  tsumiki_mst
WHERE
  first_name='値' AND
  second_name='値'

のようなSQL文を実行する場合は、

次のようなインデックスを作成すると検索が高速になります。

CREATE INDEX tsumiki_mst_name_idx
  ON tsumiki_mst(first_name,second_name)

このインデックスはfirst_nameを単独で指定したときにも機能するので、

first_nameのインデックスの代わりに使うこともできます。

しかし、second_nameを単独で指定した場合には機能しません。

これは、結合インデックスは最初の列から連続して列が指定されている場合にのみ

機能するという制限があるからです。

たとえば、A,B,Cの順序でインデックスが指定されている場合、有効/無効は次の

ようになります。

検索指定列 有効/無効
A
B ×
C ×
AB
AC ×
BC ×

結合インデックスを使う場合は次のガイドラインに従って列や順序を決定すると

良いでしょう。

・WHERE句でよく一緒に使われる列をインデックスに指定する。

・WHERE句に単独で使われることもある列は、インデックスの最初の列に指定する。

・選択性の優れている列から順に指定する。

なお、さらに検索を高速化したい場合は、選択する列(SELECT句の後に指定される列)

も結合インデックスに含めてしまえばよいでしょう。

この場合、インデックス対象のテーブルにアクセスする必要が無くなるので、

インデックスに対するアクセスのみの更に高速な検索が期待できます。


インデックスマージ

WHERE句に複数の列が指定されていて、それら列に対して結合インデックスが

ないけれども列の個々に対してインデックスが作成されている場合、

インデックスマージという処理が行われることがあります。

インデックスマージとはそれぞれのインデックスから値が一致するすべての行を

取得して、最終的にどの結果にも含まれる行を抽出するという処理です。

インデックスマージは、複数のインデックスを読み込むため、結合インデックス

に比べると効率が良くありません。又、DBMSによってはインデックスマージ

そのものが機能しない場合もあります。

インデックスマージによって十分なレスポンスが得られない場合は

結合インデックスの作成を検討した方が良いでしょう。


NULL値

NULL値はインデックスに含まれません。又、結合インデックスの場合は、

全ての列がNULL値ならインデックスに含まれません。

WHERE句でIS NULL条件が指定された場合、インデックスは使用されずに

テーブル全走査が行われます。

膨大な量のデータが格納されているテーブルの検索では、NULL値の扱いには

気をつけなければなりません。

NULL値の検索によって十分な結果が得られない場合は、NULL値の変わりに

デフォルト値を設定してこの問題を回避することができます。


!=(Not Equals)の使用

!=又は<>を使用した場合、テーブルの全走査が行われることがあります。

これはすべての行からある値に一致する行を除くときに、たいていの場合、

テーブルの全走査をした方が速いからです。

!=の使用で十分な結果が得られない場合、INやORで条件を置き換えることに

よってテーブルの全走査を回避することが必要になります。


列に対する関数や演算子の使用

WHERE句で列に対して関数や演算子が使われるとインデックスを

利用できなくなります。

たとえば、

SELECT
  *
FROM
  tsumiki_sales
WHERE
  val * 2 > 2000

のようなSQL文ではvalに設定されているインデックスは使用されません。

関数や演算子の使用で十分な結果が得られない場合、それと意味的に等価な

SQL文に置き換えられないか検討する必要があります。

上記のSQLは次のようにするとインデックスが使用されるようになります。

SELECT
  *
FROM
  tsumiki_sales
WHERE
  val > 2000 / 2

なお、DBMSによっては、この問題を回避するために関数インデックスという

インデックスがサポートされている場合があります。


LIKE句の使用

ワイルドカードを使った一致検索にLIKE句を使うことができますが、

ワイルドカードで始まるLIKE検索を行う場合、インデックスを使用することは

できません。

これはB-Treeインデックスの構造上の限界です。


ソートの使用

ORDER BY句にインデックスがある場合、インデックス内で既にデータがソート

されているため、実質ソート処理が行われません。そのため、非常に高速な

レスポンスが期待できます。

ただし、ORDER BY句の列はNOT NULLである必要があります。

明示的にソートを行う場合ORDER BY句を指定しますが、DISTINCT句を指定すると、

重複した行を除外するためにDBMS内部で自動的にソート処理が行われます。

慣例的にDISTINCT句を使用している場合は、極力DISTINCT句を使用しない方が

パフォーマンスのためには好ましいでしょう。

また、UNION演算をおこなう場合にもDISTINCTと同様に、重複する行を除外するため

ソートが行われます。重複する行を除外する必要がない場合はUNION ALLを使った

方が好ましいといえます。


グルーピングの使用

GROUP BY句を使用したSQL文を高速化するにはGROUP BY句と選択リストの全ての列を

含んだ結合インデックスを作成する必要があります。

たとえば、

SELECT
  place_id,sum(val)
FROM
  tsumiki_sales
GROUP BY
  place_id

のようなSQL文では次のようなインデックスを作成することによって処理が高速になる

可能性があります。

CREATE INDEX tsumiki_sales_grp_idx
  ON tsumiki_sales(place_id,val)

これは、SQL実行時にインデックス対象のテーブルにアクセスする必要がなくなる

ためです。実績用テーブルなど更新系処理でのオーバーヘッドを気にしないでいい

テーブルなどでは効率的といえます。

なお、HAVING句はグルーピングの処理が終了した後に適応されます。

グルーピングの処理は高価な処理ですので、HAVINGを使わずにすむ条件は

出来るだけWHERE句に記述してグルーピングの対象件数を減らすようにすると

レスポンスが向上するでしょう。