Edited at

MySQL InnoDBのIndex

More than 5 years have passed since last update.

mysqlのInnoDBではclustered indexというのを採用していて、indexを貼る際に注意が必要ということでメモ


結論から言うと

InnoDBでは...

* Primary Key(以下PK)はできるかぎり設定して、できるかぎりauto_incrementの整数型が良い

* PKの検索は速いが、secondary indexやcount(*)での検索は若干遅い

* PKのupdateは避ける

* 無闇やたらとsecondary indexを付けない

* covering indexを狙えると速い


かんたんに解説

図とか用意したかったけど気力がなかった。


indexの構造

InnoDBのインデックスではB-Treeというデータ構造が使われている。B-Treeの解説はwikipediaに任せる。

ツリー構造の一番下のリーフブロックに目的の行の物理的な位置が記録されている。ルート/ブランチのブロックはだいたいキャッシュされるので、実質ディスクIO2回(リーフブロック、行データ)で行データを取ってくることができる。

B-Treeは二分木と違ってブロック単位で管理できるから、ディスクIOを減らせる。全体がメモリに乗るくらいのサイズなら二分木で問題ないんだけど、DBだとそうはいかないのでB-Treeみたいな多分木が向いている。


clustered index

InnoDB ではclustered indexというindexを強制的に持つようになっている。このclustered indexのリーフブロックには、行の位置ではなくて行データそのものが格納されている。リーフブロックを読み込んだ段階で行データも取れるので、実質ディスクIO1回で行データを取ってくることができる。これがPKでの検索が速い理由。

こういう構造なので、InnoDBはPKを設定してもIndex_lengthが増えない(Data_lengthに含まれている)。そのうえ、何もしないとclustered indexが勝手に生成されるので、PKを設定することでData_lengthが減ることさえある。適当に10万件くらい入れたデータをPK付けたり外したり、エンジンをMyISAMにしたりInnoDBにしたりしてみて、show table statusでData_length, Index_lengthを見てみると面白い。

このclustered indexに使われるカラムには決まりがある。

以下の優先順でclustered indexが使われる。

1. PK

2. NOT NULL の UNIQUEキー

3. 1,2に該当するものがなければ、内部的に勝手に一意になるカラムが作られて、それ

だいたいの場合、テーブルにはPKを設定すると思うので、clustered index = PKという認識で困ることはそんなにないとおもう


secondary index

clustered index以外のインデックスをsecondary indexという。

secondary indexのリーフノードには、対応するclustered indexのキーが保存されていて、それを元に、clustered indexで検索する。

つまりsecondary indexでの検索の場合、secondary index→clustered indexという順番で二回インデックスを辿ることになる。これがsecondary indexが遅い理由。

ただし、SELECT primary_key, secondary_key FROM *** WHERE secondary_key = 1; みたいな条件で検索したときは、covering indexになるので速い。

secondary indexの全てのリーフにclustered indexのキーが保存されるので、MyISAMとかclustered indexじゃないエンジンに比べて、clustered indexのカラムサイズsecondary keyの数によるインデックスサイズの増大が激しい。


auto_increment

PKをauto_incrementで設定すべきというのには三つ理由がある。


整数型はコンパクト

前述の理由でPKはコンパクトに保ちたい。


更新時のリーフノードがキャッシュに乗りやすい

auto_incrementの場合、ブロックがいっぱいになって新しいブロックが作られる(リーフ追加)場合を除いて、同じブロックに更新されるので、リーフノードがキャッシュに乗りやすい。


リーフ分割が起きない

リーフ分割というのは、あるブロックに新しい値が挿入されてブロックのサイズが足りなくなったときに、二つのブロックに分かれる仕組みのこと。例えば1,2,3,5,6が入っていて満杯のリーフに、4を挿入すると1,2,3のブロックと4,5,6のブロックに別れるイメージ。

リーフ分割は各ブロックで無駄なスペースが出来たり、構造に変更が加わるのであんまり頻繁に増えて欲しくない。

auto_incrementの場合は前回より大きい値が必ず入るので、新しくリーフを追加するのみなんだけど、そうでなくランダムインサートになってしまう場合、リーフ分割が頻繁に行われる。

要するに、ランダムインサートの場合更新性能が落ちる。

同じ理由で、PKをやたらとUPDATEするのも、よくない。(そんな運用ないだろうけど)


まとめ

InnoDBはclustered indexを理解したうえでインデックス計画を練ろう!