Linux-DB システム構築/運用入門 (DB Magazine SELECTION)著者：松信 嘉範
販売元：翔泳社
発売日：2009-09-17
おすすめ度：
クチコミを見る
最近、この本を読んでいます。非常に面白いし、参考になります〜。中でもインデックスについての記事が特に興味深かったので簡単にまとめてみます。
前提
・インデックスは検索性能には効果があるが、更新性能は落ちてしまう
・MyISAM と InnoDB ではインデックスの構造が違う
・インデックスは B+Tree インデックスと呼ばれ、ルート、ブランチ、リーフの階層構造になっている
・インデックスはソートされた状態で作成されている
まずは MyISAM と InnoDB でのインデックスの違いを簡単に。
MyISAM のインデックス
インデックスを検索していくと、最終的にはリーフにたどり着きます。リーフにはインデックスと、そのインデックスに対応したデータが保存されているファイルの場所が保存されており、この値を使って実際のデータにアクセスすることが出来ます。
例えば [fuga_id] にインデックスを張り、SELECT * FROM hoge WHERE fuga_id = 2 と検索したときにはこのような動きになります。
InnoDB のインデックス
InnoDB には主キーインデックス（クラスタインデックス）とそれ以外のインデックス（セカンダリインデックス）という2種類のインデックスがあります。ルート、ブランチ、リーフと階層構造になっているのは同じですが、リーフの中身が少し違います。
クラスタインデックスの場合には、主キーとそれ以外の列値がそのまま保存されています。そのため、インデックスの値を読めば即、その他の列値も取得できます。一方、セカンダリインデックスではインデックスを検索することで主キーの値がわかり、その主キーの値を使って、その他の列値の値を知ることが出来ます。
インデックスと I/O
で、重要なことですが、高速に処理されるのはリーフの検索までです。ルートとブランチは基本的にキャッシュされ、リーフの検索もデータがソートされているお陰で隣接したインデックスは同一ブロックに格納されており、少ない I/O で検索することが出来るためです（ I/O はブロック単位で行われます）。
そのため InnoDB のクラスタインデックスの場合は非常に高速です。しかし、MyISAM の場合にはリーフで検索した後に、実際のデータに対してランダムアクセスが必要です。InnoDB のセカンダリインデックスの場合にもリーフで主キーを取得した後、その主キーを使ってクラスタインデックスを検索する必要があります。このような I/O の度にシークや回転待ちといった処理が発生しますが、これが非常に時間が掛かります。。。高速化のためには、I/O の回数を減らすことが非常に重要です。
ソート処理時のインデックス
ちょっと話がそれますが、ソートするときにもインデックスは有効です。というのも、インデックスはソートされた状態で作成されるため、インデックスを使った検索を行えば、ソート処理が発生しません（既にソートされた状態です）。
フルテーブルスキャン
インデックスを作成すれば処理が早くなりそうですが、実際に試してみるとインデックスが利用されない（無理やりインデックスを利用するとむしろ遅くなってしまう）ことがあります。この理由がイマイチわかってなかったんですが、この本を読んで納得しました。
MyISAM や InnoDB のセカンダリインデックスを用いた検索を行う場合、リーフで実データの場所や、主キーの値がわかります。その後、キャッシュされていない限りその値を用いてランダムアクセスが発生するんですが、このランダムアクセスが大量に行われると非常に遅くなります。リーフでの検索はデータが特定のブロックにまとまっているため、少ない数の I/O しか発生しませんが、ランダムアクセスでは、データはバラバラのブロックに存在しているため、都度 I/O が発生してしまうためです。
そのため、ある程度ランダムアクセスが多くなってくると、フルテーブルスキャン（インデックスを利用せずに、テーブル全体を読み込む方法）の方がデータをまとまって読み込める分、高速になっていくようです。
Covering Index
さて、やっと本題です（長かった... (ノд｀)）。ここまで読んでいただけたらわかるかと思いますが、要はいかに I/O を減らすかが重要になってくるというわけです。例えばこのような SQL を考えてみます。
SELECT hoge, fuga FROM table_1 WHERE foo = 1;
普通に考えると [foo] にインデックスを張って、リーフで得られた値から他の列値 (hoge, fuga) を取得する、とやりたくなるところです。ただ、ここで [foo, hoge, fuga] という複合インデックスを張ることで、リーフだけで必要なデータが全て得られ、その後のランダムアクセスが無くなるため高速になります。このようなインデックスだけで完結するインデックスを Covering Index と言うそうです。
そこで hoge, fuga, foo それぞれに 1 〜 999 の値を持つ適当なデータを MyISAM で 50 万件用意して実際に試してみました。毎回 SELECT する前に Tricorn Labs » Linuxのページキャッシュをきれいさっぱり消すには？ で紹介されている方法でページキャッシュを消してから行っています。
-- インデックスを作成していない場合 (2.99 sec) SELECT SQL_NO_CACHE hoge, fuga FROM table_1 WHERE foo = 1; -- インデックス index_1 の作成 ALTER TABLE table_1 ADD INDEX index_1(foo); -- インデックス index_1 を利用した場合 (2.52 sec) SELECT SQL_NO_CACHE hoge, fuga FROM table_1 WHERE foo = 1; -- インデックス index_2 の作成 ALTER TABLE table_1 ADD INDEX index_2(foo, hoge, fuga); -- インデックス index_2 を利用した場合 (0.01 sec) SELECT SQL_NO_CACHE hoge, fuga FROM table_1 WHERE foo = 1;
[foo] だけにインデックスを貼った場合には 2.52 sec も掛かっていたものが、[foo, hoge, fuga] にインデックスを張った場合 0.01 sec と改善されていることが確認できました。ランダムアクセスが無くなるとこんなにも早くなるんですね。爆速です。
GROUP BY 句にインデックスを張る場合に、集約関数で利用しているカラムにもインデックスを張ったほうが良いというのもこれが理由だと思います。非常に役に立つテクニックじゃないかと。
まとめ
・高速化のためには、いかに I/O を減らすかが大事
・I/O が増えると、インデックスを使うよりフルテーブルスキャンした方が高速になってくる（それだけ I/O は遅い処理）
・Covering Index 使ってインデックスのみで処理すると高速 ｡ﾟ+.(・∀・)ﾟ+.ﾟ
