SQL実践入門第１０章を読んだ

インデックスの分類

RDBで使われるインデックスは、構造に基づいて分類すると３つに分けられる

B-tree（B+tree）インデックス

データを木構造で保持する
汎用性の高さから一番よく使われるインデックス
修飾なしでCREATE INDEX文を実行すると、まず全てのDBMSで暗黙にB-treeインデックスが作成される
実際には多くのデータベースでB+treeという検索をより効率化したアルゴリズムが使用されている（ツリーのリーフノードにだけキー値を保持する）

B+treeインデックスの優れている点

なるべくルートとリーフの距離を一定に保つバランスの取れた木であるため、検索性能が安定している
木の深さが一定していてデータもソートして保持しているため、2分探索によって検索コストをかなり小さく抑えることができる
データがソートされていることから、うまく使えば集約関数などで必要になるソートをスキップすることができる

ビットマップインデックス

データをビットフラグに変換して保持するインデックス
カーディナリティの小さい列に対して効果を発揮する
更新時のオーバーヘッドが大きい為、主にあまり頻繁な更新が行われないBI/DWH用途で使用される

ハッシュインデックス

キーをハッシュ分散することで、等値検索を高速化することを目的にしたインデックス
選択率の高い等値検索以外では効果が薄い
範囲検索では利用できない

インデックスを有効活用するためのポイント

インデックスは、とにかく作れば問題が解決するというものではなく、有効活用するために考慮すべきポイントがいくつかある。

カーディナリティと選択率

どのような列に対してインデックスを作成するべきかの基準となるのが、列の「カーディナリティ」と「選択率」

カーディナリティ
- 値のばらつき具合を示す概念
- 最も高いのは値が異なる一意キーの列で、最も低いのは値が１種類しか存在しない列
選択率
- 特定の列の値を指定した時に、行をテーブル全体の母集合からどの程度絞り込めるかを示す概念
- 絞り込めるほど選択率は小さく、絞り込めないほど選択率は大きくなる
- 100件のレコードを持つテーブルで、一意キーに対して「pkey = 1」のように等号で指定すれば必ず1件に絞り込める。この条件の選択率は1/100 = 0.01、つまり1%となる。

カーディナリティが高く（値がよくばらついていて）、選択率が低い（少ない行に絞り込める）ことが、良いインデックス候補となり得る列の条件。大体の目安として、選択率が5%未満に絞り込めるならば、その列集合に対してインデックスを作る価値があるかもしれない（ただし、選択率の閾値はストレージの性能向上に比例して小さくなっていく傾向にある（どんどんシビアになっている））選択率がそれより高いと、テーブルフルスキャンの方が速い可能性が高くなってくる

インデックスによる性能向上が難しいケース

絞りこみ条件が存在しない場合

データを全件取得するSELECT文

SELECT order_id, receive_date
  FROM Orders;

このクエリの場合、データを全件取得しているため、テーブルのフルスキャン以外ない。レコードを絞り込めるようなWHERE句がそもそもないので、インデックスを作成すべき列も存在しない。

（絞りこみ条件はあるが）ほとんどレコードを絞り込めない場合

flagの値でデータを絞りこむSELECT文

SELECT order_id, receive_date
  FROM Orders
 WHERE flag = '5';

flagの分布

- 1(仮受付)　　 : 200万件
- 2(受付済)　　 : 500万件
- 3(在庫確認中) : 500万件
- 4(発送準備中) : 500万件
- 5(発送済)　　 : 8,300万件

この場合（flag = '5'で絞りこむ場合）の選択率は83%と極めて高く、この状態でflag列にインデックスを作ってそれが使われたとしても、フルスキャンより遅くなる可能性が高い。（先にまとめたように、インデックスが意味をもつ選択率の目安は5%未満）インデックスが有効なのは、あくまで「大きくレコードを絞り込める検索条件」が存在する場合だけ。「hoge_flag」や「fuga_status」といった命名の列は種類の少ない何らかの状態を表していることが多いので、インデックスを作るには向かない列であることが多くある。

入力パラメータによって選択率が変動する場合

入力パラメータで設定した期間によって絞りこみを行うSELECT文

SELECT order_id
  FROM Orders
 WHERE receive_date BETWEEN :start_date AND :end_date;

:start_dateと:end_dateに同じ日付が設定されたならば、比較的小さい選択率が期待できる。一方、例えば1年間などの長い期間が設定されたならば、単純計算で前者の365倍のレコードがヒットすることになる。このように、その時々のパラメータに対する入力値によって選択率が良い方にも悪い方にも転ぶ。

（絞りこみのきく検索条件がありながら）インデックスが使えない検索条件の場合

構文的にインデックスが利用できないパターンがいくつか存在する。

中間一致、後方一致のLIKE述語
- LIKE述語を使う場合、インデックスが使用できるのは前方一致のみで、中間一致、後方一致ではインデックスが利用できずフルスキャンにならざるを得ない
索引列で演算を行なっている
- 索引列で演算を行なっているとインデックスを使用できない

SELECT *
  FROM SomeTable
 WHERE col_1 * 1.1 > 100;

ただし、条件式の右側で式を用いればインデックスが使用できる

WHERE col_1 > 100/1.1;

IS NULL述語を使っている　- 通常、索引データの中にNULLは存在しないため、インデックスは使用できない
索引列に関数を使用している　- 「索引列で演算を行なっている場合」と同じ理由でインデックスを利用できない
否定形を用いている
- 否定形（<>, !=, NOT IN）はインデックスを使用できない

インデックスが使用できない、使用すると逆に遅くなってしまう場合の対処方法

アプリケーション設計で対処する（王道）

外部設計による対処

選択率の高いクエリが実行されないように、そもそものUI設計から対処する。例えば、注文テーブルから「店舗ID」で絞り込んで検索する場合は、「受付日」も入力しなければ検索ボタンを押すことができない。別の例では、「期間検索」は最大でも１ヶ月間まで、などのように、選択率が低い（少ないレコード数に絞り込みが行える）クエリが実行されるように、アプリケーションで制御をかける。

データマートによる対処

データマートとは、特定のクエリで必要とされるデータだけを保持する、相対的に小さなサイズのテーブルのこと。アクセス対象のテーブルサイズを小さくすることでI/O量を減らすことが目的。

ただし、データ鮮度（オリジナルテーブルとのデータ同期）や、データマートが増えすぎて誰も管理できなくなるなど問題が起きやすいので注意が必要。

あくまでインデックスで対処する（飛び道具）

インデックスオンリースキャンによる対処

読み出したい列全てをカバーするインデックス（カバリングインデックス）が存在することによって、テーブルではなくインデックスだけをスキャン対象にする検索のこと。実行されるSQL文に必要な列をインデックスだけで充足できる場合に、テーブルへのアクセスをスキップすることによって、I/Oを削減できる。