最近、インデックスについて調べることがあったので、忘れないうちに出来る限り情報を残しておこうと思います。
ちなみにMySQLのバージョンは5.5および5.6の情報を元にしています。
InnoDBにおけるインデックス
インデックスの構造
B+Treeインデックス
InnoDBではデータはテーブルスペースと呼ばれる領域にあります。さらにこのテーブルスペースはページ(ブロック)単位で管理されており、このページ単位でB+Treeが構成されるようになっています。つまりI/Oの単位はページ単位になっている、ということです。
クラスタインデックスとセカンダリインデックス
InnoDBではテーブルの検索や操作に使われるインデックスとして2種類のインデックスが存在します。それはクラスタインデックス(Clustered index)とセカンダリインデックス(Secondary Index)です。
クラスタインデックス
クラスタインデックスはすべてのInnoDBのテーブルで存在する特別なインデックスになります。
InnoDBはクラスタインデックスとして使用するキーを以下の順序で探しているようです。
- 定義された主キーを用いる
- 主キーが定義されていない場合には、最初に見つかったすべてのキー列がNOT NULLであるUNIQUEインデックスを使用する
- 1および2で適切なキーが見つからなかった場合には、内部的なRowIDを割り当て、それにより生成したインデックスを使用する
クラスタインデックスはツリーのリーフノードにキーと対応するRowIDを持っており、データファイル上の場所を一意に特定できるようになっています。データファイル上のデータはRowIDと列のすべてのデータを持っています。 ただ、このままではアクセスをするたびに常にリーフへのアクセスとデータファイルへのランダムアクセスが発生するため、リーフとデータファイルはキャッシュされるようになっています。(テーブルが巨大になるとこのキャッシュが行われないリーフやデータファイルが出てきます)
- クラスタインデックスのリーフノードの構造のイメージ例
キー | RowID |
---|---|
1 | 20450 |
2 | 12 |
... | ... |
セカンダリインデックス
セカンダリインデックスはクラスタインデックス以外のすべてのインデックスを指します。
このインデックスはリーフノードにインデックスのキーとクラスタインデックスのキーの対応を持っています。
- セカンダリインデックスのリーフノードの構造の例
キー | クラスタインデックスのキー |
---|---|
1 | 2 |
2 | 1 |
... | ... |
インデックスを含むアクセス
主キーの検索によるアクセス
InnoDBでは主キー検索はクラスタインデックスによる検索となり、1回の検索ですべての列の値を取得できるため高速です。
主キー以外のインデックスでの検索
主キー以外のインデックスでの検索では、基本的に対応するセカンダリインデックスでの検索を行ったあと、クラスタインデックスにアクセスして、その他の列のデータを取得します。 そのため、速度が遅くなる可能性があります。
インデックスでの範囲検索
インデックスでの範囲検索は、まず範囲が収まっているリーフノードの数だけアクセスが行われます。
その後、範囲に対応する行をデータファイルから読み込むことになるのですが、対応するRowIDはバラバラであるため、データファイル上の位置も連続していないことが考えられます。そのため、各行に対して1回ずつのランダムアクセスが発生すると考えられます。
インデックスが使用されない検索
非常に大量のインデックスにヒットする場合は範囲検索で述べたように、ヒットした件数分ランダムアクセスが増加することになります。 インデックスを使用するかはオプティマイザによって決定されますが、オプティマイザはこのような場合にフルテーブルスキャンを選択することがあるようです。
フルテーブルスキャン
フルテーブルスキャンは、インデックスを全く用いないでテーブルの先頭から順番に読み込んでいきます。ヒットする件数が多い場合にはインデックスを用いるより効率が良い場合もありますが、クエリによって一般的に大量の行がヒットしないのであれば、インデックスによるアクセスのほうが効率的です。
カバリングインデックス(Covering Index)
「インデックスが含む値のみを読み出すような検索」の場合、データファイルへのアクセスをすることなく、インデックスへのアクセスのみで完結することができます。 これをカバリングインデックスと呼びます。
例えば以下のクエリで作成されたテーブルを考えます。
CREATE TABLE index_test ( key1 INT UNSIGNED PRIMARY KEY, value INT);
そして次のようなSELECT文を投げる場合を考えます。
SELECT key1 from key1 > 0 and key1 <= 10;
このとき、データファイルにのみ存在する列の情報を取得する必要が無いため、このクエリは(クラスタ)インデックスのみにアクセスをして完結します。これによりリーフノードの読み込みのみで完結するために非常に高速になります。
上記の場合において、以下のように、SELECT文で指定した列(ここではvalue)がインデックスに含まれていない場合はカバリングインデックスとはなりません。
SELECT key1, value from key1 > 0 and key1 <= 10;
このようにカバリングインデックスを積極的に狙うのであれば、不要な列を取得しない、とくにSELECT * from ... は極力避けたほうがよい、ということになります。
インデックスマージ
tblというテーブルの列key1, key2にそれぞれ独立なインデックスがあった場合を考えます。 そのとき以下のSELECT文を発行すると、各key1, key2のインデックスをマージして使用する状況になります。
SELECT key1, key2 FROM tbl WHERE key1 < 1 AND key2 = 1;
これはそれぞれの対応するインデックスで条件判定を行い、その結果をマージして利用するというものです。
マルチカラムインデックス
ここまででは1つの列に対応するインデックスのみで話をしましたが、複数列に対応するインデックスを作成できます。
ここで、マルチカラムインデックスは含んでいる列がAND条件で指定されているときに利用できます。 またインデックスマージが行われるよりも適切なマルチカラムインデックスが用いられたほうが一般的に早くなります。
WHERE句とORDER BY句がある場合の注意点
WHERE句とORDER BY句がある場合、(マルチカラム)インデックスで指定された先頭の列がWHERE条件で指定されなければ使われません。
またOR条件でも使用されません。
また、WHERE句での列の出現する順序がマルチカラムインデックスで指定された順序と同じでなければ、使用されません。
その他
インデックスが適切に使われているかを調べる方法
EXPLAIN文を用いると、インデックスが適切に使われているか調べることができます。
詳しくは以下で。(いつも見に行ってて、すごく助かっています)
漢(オトコ)のコンピュータ道: MySQLのEXPLAINを徹底解説!!
5.6.3から導入されたoptimizer_trace
こちらも詳しくは以下のページを参考に。
MySQL 5.6での、マルチカラムインデックスとカラムごとのインデックスの比較 | Yakst
mysql バージョン5.6で使えるoptimizer_trace - hironomiu's Blog
参考にした本、Webページ
漢(オトコ)のコンピュータ道
MySQL :: MySQL 5.6 Reference Manual
インデックスを使いこなす