データベースのパフォーマンスを決める要因~インデックス~
そもそもインデックスとは
ある特定の部分を探すために使用する概念のことで、本の索引のようなものです。
インデックスにはいくつかの種類があり、DBMSによっても使用できる種類に差があります。
- B-treeインデックス
- ビットマップインデックス
- ハッシュインデックス
などがありますが、頻繁に利用するインデックスはB-treeインデックスです。
B-treeインデックスとは
前提として、インデックスの目的は、「ある特定の部分を速く探すこと」です。
検索する際のアルゴリズムとして、二分探索という検索方法があります。
二分探索とは、検索したい値が中央値より小さい場合は左に進み、大きい場合は右に進みながら検索していくアルゴリズムです。
二分探索を行いやすいように値を大小で振り分けたデータ構造を二分探索木と呼びます。
二分探索木は木の高さが揃っていない場合、検索回数が増えてしまう可能性があります。二分探索木の場合、データの挿入や削除によって木の高さが変わってしまいます。
その問題に対応したのが、AVL木です。
AVL木とは、木の高さに変更があった場合に、二分探索木に回転という操作を行うことで、木の高さを一定にするデータ構造(平衡木)のことです。
このAVL木を一般化し、多分岐の平衡木構造を持ったものがB-treeになります。
B-treeインデックスの構造と特徴
上記の通り、B-treeは木構造でデータを保持します。
最下層のリーフと呼ばれるノードだけが実データに対するポインタを保持し、データベースは最上位のノードから順にノードをたどって、リーフから実データを見つけに行きます。
木構造により、以下の5点に対して平均的に高いパフォーマンスを発揮することが可能です。
均一性
前述の通り、B-tree平衡木のため、どんなキーの値を使用しても、常にリーフまでの距離が一定になります。そのため、探索を同じ計算量で行うことが可能になります。
持続性
B-treeの性能劣化スピードは長期的に見て、非常に緩やかです。データ量が増えても、検索や更新にかかる時間はほとんど増えません。
なぜなら、B-treeの木の高さは、平均的には3~4程度の平べったい木だからです。背が低い木であるという特性は、データ量が増えても変わらない特性です。
処理汎用性
挿入、更新、削除のコストも、検索と同じくデータ量が増えても性能劣化の度合いが緩やかです。
非等値性
等号(=)による検索だけでなく、不等号(<、>、<=、>=)、BETWEENといった範囲検索の条件においても高速化を可能とします。B-treeは構築されるときに必ずキー値をソートするため、特定のノードよりも「左」「右」のノードのみに、探索範囲を絞ることができるからです。
否定条件(<>、!=)は、特定のノード以外のすべてのノードが該当するため、B-treeによる絞り込みが効かず、B-treeが効果を持たない検索条件です。
親ソート性
以下のような処理を実行した際に、DBMS内部では暗黙的にソート処理が行われています。
- 集約関数(COUNT、SUM、AVG、MAX,MIN)
- ORDER BY句
- 集合演算(UNION、INTERSECT、EXCEPT)
- OLAP関数(RANK、ROW_NUMBERなど)
しかし、ソートはかなりコストの高い演算です。
ソートは、DBMS内部で割り当てられている専用のメモリ領域内に一時的にデータを保持して実施されます。メモリ領域以上のデータでソートが実行された場合は、ディスクへデータを書き出すため、読み書きコストが非常に大きくなります。
つまり、極力大きなソートを避けることがパフォーマンス上は望ましい、ということになります。
B-treeインデックスの場合は、構築時にキー値をソートして保持します。そのため、B-treeインデックスが存在する列をORDER BY句で指定した場合、ソート処理をスキップすることが可能になります。
インデックスの設計方針
インデックスはどの列に対して作ればよいのか？
- 大規模なテーブルに対して作成する
- カーディナリティの高い列に作成する
- SQL文でWHERE句の選択条件、または結合条件に使用されている列に作成する。
大規模なテーブルに対して作成する
データ量が少ない場合、B-treeインデックスを使用するよりも、フルスキャンのほうが高速です。(ただし、処理時間の差はごくわずかでインデックスを使用しても大差はありませんが、わざわざ無駄なインデックスを作る必要はありません)
「データ量が少ない場合」の目安としては、レコード数が1万件以下の場合です。ストレージやサーバーの性能など環境要因によって大きく左右されるため、固定的な値は存在しませんが、目安として参考にしてみて下さい。
カーディナリティの高い列に作成する
カーディナリティとは、特定の列の値が、どのくらいの種類の多さを持つか、ということを表す概念のことです。
例えば、「都道府県」を表す列のカーディナリティは、「47」です。
B-treeインデックスを作る際は、カーディナリティの高い列を選ぶことが基本です。
目安としては、特定のキー値を指定した際に、全体のレコード数の5%以下になる程度のカーディナリティがあることです。
上記例で挙げた「都道府県」列の場合、およそ2%の絞り込みになるため、B-treeインデクスを作る意味はありそうです。
カーディナリティの注意点
・ 複合列に対してインデックスを作る場合、複合列の組み合わせで考える
・ カーディナリティが高くても、特定の値にデータが集中するような列には向いていない
SQL文でWHERE句の選択条件、または結合条件に使用されている列に作成する
当たり前ですが、SQLで検索条件や結合条件として使用されない列にいくらインデックスを作っても無意味です。ただし、インデックスが使用されるためには、SQLの記述方法としていくつかの条件があります。
- インデックス列に演算を行わない
☓ SELECT * FROM table WHERE col * 3 > 100;
インデックスの中に存在する値は「col」のため、「col * 3」ではないためです。
- 索引列に対してSQL関数を適用しない
☓ SELECT * FROM table WHERE SUBSTAR(col, 1, 1) = "hoge";
1.と同様で、インデックスの中に存在する値は、「SUBSTAR(col, 1, 1)」ではないためです。
- IS NULL述語を使用していない
☓ SELECT * FROM table WHERE col IS NULL;
B-treeインデックスは一般的にNULLはデータ値としてはみなさず、保持していません。つまり、IS NULLやIS NOT NULL述語に対しては有効ではありません。
- 否定形を使用していない
☓ SELECT * FROM table WHERE col != 5;
前述の通り、否定形の場合は選択範囲を絞ることができず、インデックスが有効に作用しません。
- ORを用いていない
☓ SELECT * FROM table WHERE col = 3 OR co = 4;
ORを用いた場合はインデックスが利用されません。以下のようにINを使用して書き換えて回避できます。
☓ SELECT * FROM table IN(3, 4);
- 後方一致、または中間一致のLIKE述語を用いていない
☓ SELECT * FROM table WHERE col LIKE "%a";
☓ SELECT * FROM table WHERE col LIKE "%a%";
○ SELECT * FROM table WHERE col LIKE "a%";
LIKE述語を使用するときは、前方一致検索の場合のみ索引が使用されます。
- 暗黙の型変換を行っていない
列とデータ型が異なる値を条件に指定した場合、DBMSは内部的に暗黙の型変換を行います。しかし、その場合はインデックスが使用されなくなります。
これを回避するために、明示的に条件使用する値のデータ型を列のデータ型に合わせる必要があります。
その他B-treeインデックスの設計方針の注意点
主キーおよび一意制約の列には作成不要
主キー制約や一意制約を作成する際は、内部的にはB-treeインデックスが作成されています。そのため、２重に作成することになり、作成する必要はありません。
B-treeインデックスは更新性能を劣化させる
インデックスはテーブルとは独立のオブジェクトとしてDBMS内部に保持されています。つまり、インデックスが作成されている対象の列値が変更されると、インデックs内に保持している値も更新する必要があります。
B-treeインデックスを作成すればするほど、当該テーブルにおける更新性能が劣化するというトレードオフに注意して、極力無駄なインデックスを作成しないように心がける必要があります。
定期的なメンテナンスを行うことが望ましい
長期的には構造が崩れて性能が劣化していくため、定期的なメンテナンス、具体的はインデックスの再構築を行うことが、性能を維持するために望ましい方策です。
DBMS毎にインデックスの構造が崩れている場合の指標値(断片化率や木の高さなど)を調査する方法があります。
Discussion
最近、素朴な疑問をもちました。
インデックスによる参照（正確には記憶番地の指定）はキャッシュ時間で処理ができるのだろうか？ それともメモリ時間なんだろか？
それでこんな文章かいています。