はじめに

最近ISUCONに参加するべく、いろんな高速化技術について勉強しています。

今回はSQLチューニングする際のインデックスについて学んだので、簡単ですが紹介したいと思います。

インデックスとは

テーブルの実データ(レコード)に対するポインタを保持した索引みたいなもの
テーブルのレコードにアクセスする際に、索引(インデックス)を参照して、普通に検索するよりも早く特定のレコードにアクセスできる。 2分探索(バイナリーサーチ)で検索されるイメージ。
インデックスがないと、全てのレコードを一つ一つ合致するか調べる必要があり、時間がかかる
インデックスはDB内にあるテーブルとは独立したオブジェクト

SQLのパフォーマンス設計において、インデックスを考えることは重要です。

インデックスがない検索はなぜ遅い

データがどこにあるかわからないので、ディスクに対して最悪の場合フルスキャンするので

インデックスの種類

いくつか種類があるが、利用するのはほとんどB-treeインデックス。通常、どのDBでもインデックスを作成するとB-treeインデックスが作成される。
場合によっては他のインデックスが優れていることもある

B-treeインデックスの構造

木構造で2分探索(バイナリーサーチ)に適した構造
最下層のリーフと呼ばれるノードだけが、実データへのポインタを保持
インデックスを利用するときは、最上位のノードから順にノードを辿って、リーフから実データを見つけに行く
平衡木(どのリーフもルートからの距離が一定)なため、検索の計算量が常に一定
リーフはソートされているので、ソート処理を省ける

あるIDカラムにインデックスを作成していた場合、以下のように値のインデックスが昇順で作成される。この場合目的のレコードに通常よりも早くアクセスすることができる

引用:@ITデータへの最短ルートを確保せよ！図2　Bツリーインデックスを利用したアクセスより

B-treeインデックスを作成するときに気をつけること

どの列に対してインデックスをつくればよいのか

前提として、インデックスを作る対象はレコード数が多いテーブル、カーディナリティが多い列でなければインデックスの効果がない

レコード数が多いテーブル

目安はレコード数が1万件以上のテーブルに対して作成する
レコード数が少ないテーブルにインデックスを作成しても効果はない

カーディナリティが多い列

カーディナリティとは列の値がどれくらいの種類の多さをもつか
- データが分散しているほど　カーティナリティが高い
検索結果が多い場合 = カーディナリティが低い
- 結局いくつもの結果を読み込まないといけないので
カーディナリティについてまとめてみたに詳しく書かれているので参照ください

インデックスを作る時の目安は特定のカラム値を指定した時に、全体の 5%程度に絞り込めるだけのカーディナリティがあることである。例えば先ほどの日付の例だと、365日のうちの1日を指定するselect文を考えるとする。
この場合 1 / 365 ≒ 0.27%となるので、インデックスを作成する意味はあるといえるだろう。
反対に、性別の場合男女どちらを選んでも 1 / 2 = 50%となるので、インデックスを作成する意味はないし、むしろマイナスになるだろう。

ORDER BY 狙いのインデックス

インデックスはデータをソート済みの状態で保存している
- 要するにインデックスを用いた検索をすると、つねにソートされた状態で取得できる
なのでORDER BYに対してインデックスを使うことでソート処理をスキップできるので高速化できる
DBで重いソート処理をする必要がなくなる

マルチカラムインデックス

複数のカラムを組み合わせたインデックスのこと
where条件で同じテーブルのカラムが使用されていた場合、マルチカラムインデックスを使用すると最も良いパフォーマンスが発揮される

マルチカラムインデックスには順序がある

マルチカラムインデックスの順番には気をつける必要がある。実行速度が遅くなる場合もありえる。

複合インデクスの特徴の１つである、「キーとして構成されているカラムの全てが検索条件に指定されていなくても、キーの先頭から途中までのカラムが指定されていれば、インデクスが使われる」という点です。

テーブルデータを全件読み込むよりも、インデスクを使用した方が速いのではないかと誤解する方も多いのですが、テーブルの全件検査はブロック読み込みという方式で何件もまとまった単位で連続して読み込みますので、検査だけであればそれほど時間はかかりません。※1
それに比べて、インデクスを参照してから次にテーブルデータを読み込むという処理は１レコード単位のランダムアクセス処理の積み重ねとなりますので、１件ごとの時間は短くても件数が多くなるとトータルとして膨大な時間となります。

データの散らばりが小さい(カーディナリティが小さい)ものはそもそもインデックス条件に加えないほうがよさそう。上記のようなことがあり、本来インデックスを使わないほうが早いけど、インデックスを使うことで遅くなることがある。

上記インデクスにおいて例えば、会社＝本社かつ生年月日＜1960/01/01のような検索条件を実行すると、「インデクス０」を参照

JOIN 結合

JOINの特性

joinの回数が増えると急激に性能が悪くなる。SQLの中で重い処理の一つ
2つの10000テーブルのjoin時のテーブルスキャンは 10000 × 10000

JOIN時のインデックス

結合キーがユニークキー出ない場合、遅くなる可能性あり
- 内部表には必ずインデックスを使おう
駆動表(結合する側)、内部表(結合される側)があって、内部表へのアクセスにはインデックスが使用される
オプティマイザが駆動表、内部表を決めるので、実行計画をみて確認する必要がある
- 表が小さい方が駆動表になるみたい(単純にレコード数？)。実行計画で確認は必要そう。
Mysqlでは結合する際のアルゴリズムはNested Loops。駆動表が小さいほど性能は良いものになる。
- 性能がよくなるのは、前提として内部表の結合キーの列にインデックスが存在すること
- 内部表のループを完全にスキップできるのは、結合キーが内部表に対してユニークな場合のみ
- さらに、内部表の結合キーとwhereで内部表の検索条件のマルチカラムインデックスがあればより高速化できる

「駆動表の小さなNestedLoops + 内部表の結合キーにインデックス」

ただし、インデックスがあっても内部表がでかすぎるとNG

その他

クラスターインデックス

引用:クックパッド開発者ブログ MySQL with InnoDB のインデックスの基礎知識とありがちな間違い

セカンダリインデックスを使った検索は、まずセカンダリインデックスの B+ 木を辿って主キーを取得し、次にクラスタ化インデックスの B+ 木を辿ってレコードを取得することになります。

セカンダリインデックスに必要な情報が全て格納されていれば、クラスタ化インデックスを辿る手順をスキップすることができるので高速です。このようにレコードを取得する際にセカンダリインデックスで完結する場合のことをカバリングインデックスと呼びます。

プライマリインデックス

主キー、一意制約を作成したらインデックスが作成されている。主キーに作成されるインデックスがプリマリインデックス

セカンダリインデックス

プライマリインデックス以外のインデックス

その他注意事項

主キーや一意制約の列には作成不要
- 主キー、一意制約を作成したらインデックスが作成されているため
B-treeインデックスは更新機能を劣化させる
- レコードの値が変更されると、インデックスも変更しないといけないので
- 極力無駄なインデックスは差k末井しない
定期的なメンテナンスが必要
- データが更新されていくと、長期的に構造が崩れて、性能が劣化していく
インデックスはデータが変化していくと、今はインデックスが利用されても、将来的に利用されなくなる時があるので注意

SQLの記述時の注意

インデックス列に下記条件が加わると、インデックスを利用できなくなるので注意

検索条件や、結合条件で使用されていない
インデックス列に演算
SQL関数を使用
IS NULL 述語を使っている
否定形を用いている
ORを用いている
後方一致、中間一致のLIKE述語を使っている
暗黙の型変換している
複数のインデックスがあってもSQLで１つのテーブルに対して使用されるインデックスは１つのみ

参考

達人に学ぶDB設計徹底指南書初級者で終わりたくないあなたへ
SQL実践入門──高速でわかりやすいクエリの書き方 (WEB+DB PRESS plus)