u16suzuの blog

日々学んだことのメモブログです。

MySQLの参照系のインデックスチューニングについて

MySQL Index

最近MySQLのインデックスに関する勉強をしているので、それについてまとめたいと思います。

今回参考にした本です。内容が充実しおり、とてもオススメの本です。

Linux-DB システム構築/運用入門 (DB Magazine SELECTION)

Linux-DB システム構築/運用入門 (DB Magazine SELECTION)

MySQLのパフォーマンスを上げるには?

MySQLのパフォーマンスアップの要諦は以下の2点です。

  1. 捜査対象のレコード数を減らすこと
  2. ランダムI/Oの回数を減らすこと

これらを実現するために、インデックスを使いこなす必要がある。 インデックスを有効活用できないと性能に数倍から数百倍クラスの違いがある。 インデックス戦略はDBチューニングの中でもっとも重要な部類です。

インデックスの構造と検索の種類

インデックスの構造

  • リレーショナルDBで通常使用されているインデックスは、 B+Tree と呼ばれているデータ構造を使っている。
  • I/Oはブロック単位で行われるため、ある程度まとまった分量を読み書きしても大した差はない。
  • インデックスはルート, ブランチ, リーフの3つから構成されているツリー構造になっている。
  • インデックスは前の列から順にキーが昇順でソートされた状態で格納されている。(つまり、インデックスをうまく使えば、ORDER BY句もインデックスの恩恵を受けられる。)

インデックスの種類

  • クラスタインデックス : PKと実データ行の組
  • セカンダリインデックス : PK以外の列からなるインデックスとPKの組

インデックスをつかった検索の種類

  • 主キー検索 : クラスタインデックスはPKと同時に実データも読み込まれるため、I/Oが1回で完了する。早い。
  • セカンダリインデックス検索 : セカンダリインデックスの検索の後に、クラスタインデックス検索が行われる。速度では主キー検索に劣る。実質2度のフェッチ処理が走る。

インデックスを使うときの注意事項

  • WHERE句にNot条件を使うと、インデックスが使われない。
    • 例. WHERE age != 17 => WHERE age in(16,18,19) のような書き換えが必要

次から、インデックスの種類とそれぞれの注意点について説明します。

カバーリングインデックス

カバーリングインデックスとは?

クエリする際に使用する列をあらかじめインデックスしておくこと。 こうすると、セカンダリインデックス上に取得したい列データを載せることができるので、実データを読み込まなくてもよくなる。 ディスクI/Oを減らせるため検索が高速になる。 次節で述べるマルチカラムインデックスと相性が良い。

カバーリングインデックスの確認方法

EXPLAIN した時に Extra に Using index となっていれば, カバーリングインデックスが使われている。

カバーリングインデックスの名前の由来

カバーリングインデックスの名前の由来はインデックスがクエリ全体をカバーしているところからきている。

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

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

複数カラムにインデックスを張ったもの。 カバーリングインデックスと相性が良い。 ただし、幾つかの注意点がある。

マルチカラムインデックスの注意点

  1. WHERE句で検索する際にマルチカラムインデックスの先頭列を必ず指定する必要がある。
  2. カラム c1, c2, c3 にマルチカラムインデックス(c1,c2,c3)を張ったとき、c1とc3 しか where で指定していないときは、c1のインデックスしか使ってくれない。
  3. 範囲検索が含まれる場合(次の節を参照)。

マルチカラムインデックスと範囲検索

ここでいう範囲検索とは LIKE句 や WHERE created_at < 100 と言った検索のことを言う。 ここから先の説明では、マルチカラムインデックスを含むインデックスはキーのソート順に格納されていることを背景知識として覚えておきたい。

例えば(a,b)というマルチカラムインデックスがある時に select * from tbl where a < 1000 AND b = 10 というクエリを発行した場合、 図1. のように a < 1000 を満たす行がたくさんあり、かつそれを満たす行の a の値が大きくバラついているとする。 この時、インデックスにおいて、それらの行に含まれる b の値はソートされている値にはならないため、遅くなってしまうという問題がある。

a b
100 10
200 1
300 3
400 99
500 84

図1. 範囲検索でaの値が異なるレコードが引っかかったため、列bの値がソートされていない例

このことは、範囲検索を含む場合のマルチカラムインデックスの注意点である。 この問題はLIKEや日付型の範囲検索でよく発生する(どちらも列のとりうる値すなわちカーディナリティが高くなる為) この場合は、イコール検索されるb列を前に持ってきて、(b,a)とインデックスを逆に貼れば解決する。 このことから、「範囲検索はできるだけイコール検索に帰着させること」 が重要であることがわかる。(図2. 参照)

a b
900 1
900 2
900 3
900 80
900 84

図2. aが同じ値なため、列bがソートされている例

ソート処理とインデックス

ソート処理の基本知識

  • ソート処理はインデックスの活用によって大きく性能の差が出る処理の１つ
  • インデックスはすでにソートされ、昇順に格納されているため、これをそのまま利用できる場合は早い。逆順でも同様
  • 一方で、インデックスをソートに使えない場合は一般的にO(nlogn)の計算量が必要。メモリも消費する。
  • ソート処理の速度にはインデックスの貼り方が大きく影響する。
  • なんとなく気分だけで ORDER BYをつけるのは禁物

絞り込み用のインデックスとソート用のインデックスは併用できない

「WHERE key1 < 30 ORDER BY key2」というクエリを考える場合、以下の実行計画が考えられる。

  • (1). key1のインデックスを使う場合, key2でさらにソートをする必要がある. この時 key2のインデックスは使うことができない.
  • (2). key2のインデックスを使う場合, key1の条件チェックがすべてのレコードに対して発生する.(フルインデックスキャン)

それぞれの実行計画が有利な場合と不利な場合について、考えてみる。

  • (1). のケースはkey1でうまくレコード数を絞り込みできるケースで高速になる。データ数が少なければ、ソート処理は負荷ではないためこちらが有利になる。
  • (2). のケースはkey1であまり絞り込みできない場合に有利になる。大量のレコードのソートによるオーバヘッドがなくなるためである。

実際には、RDBMSのオプティマイザがどちらを使うかを判断する。

マルチカラムインデックスとソート処理

マルチカラムインデックスはソート処理でも有効に使うことができるが、前で述べたマルチカラムインデックスの注意点と同様のことがソート処理でも言える。

  1. 「WHERE date='2008-10-10' ORDER BY price」のようなクエリの時は, (date,price)にマルチカラムインデックスを張っておけば良い。 逆に(price,date)だと、dateで絞り込みできないのでダメ.

  2. 「WHERE date>'2008-10-10' ORDER BY price」のように範囲検索がある時は, 前述の通りマルチカラムインデックスの2列目以降が使えなくなってしまうので priceでソートし直す必要が出てくる.

  3. 同様に、(date,foo,price)のように使用されないカラムがインデックスに含まれている場合も, fooの順番で並んでいるindexであるため price のソートには使えない.

「上位N件の取得」クエリの難しさ

例えば、最新のブログ記事10件を取るクエリ「 WHERE cond ORDER BY keyX LIMIT N 」について考えてみる。 この時、選択されうる実行計画としては、次の3つがありうる。

  1. cond でインデックスが使われる。マッチした結果全てを keyX でソートして上位N件を取得する。
  2. keyX でインデックスが使われる。その都度、condで条件判定をしていき、条件を満たすレコードがN件に達したところで終了する。
  3. フルテーブルスキャンをする。マッチした結果すべてをソートして上位N件を取得する。

ここでも、どの実行計画が一番高速になるかはケースによる。 それぞれ、項目ごとに考えてみる。

  1. condでうまくインデックスが使われて、十分にレコードを絞り込みできる場合は1. がもっとも実行効率がよくなる。 しかし、うまく絞り込みできない場合は、ランダムアクセスが多くなりソートの負荷も高くなる。 また、condの条件が複雑な時など、cond でインデックスがそもそも使えない場合、1. の方法は使えない。

  2. 1.とは逆に大量のレコードが条件を満たすとき実行効率がよくなる。 なぜなら、少しスキャンをしただけで、condを満たすレコードがN件に達するため。 逆に、condを満たすレコードが少ないと、レコードをスキャンする回数が増えて実行効率が遅くなる。 上位10件ではなく 110件目から120件目のレコードの取得というようなクエリの場合、条件を満たすレコードが少なくなってくるので 遅くなってきてしまう。 一般的に、ジャンプの件数が増えると遅くなる特徴がある。

  3. 1.と2.どちらの場合も使えずに、仕方なく選ばれる方法。 例えば、condの条件が複雑でインデックスが使えず、かつ、condを満たすレコードが少ない場合。 フルテーブルスキャンが広範囲にまたがるインデックススキャンよりも効率はいいので、インデックススキャンよりは効率が良い。

ページング処理のクエリの定石

10件目まで表示した後、11件目~20件目と検索する場合には、 10件目のkeyX を WHERE句に指定して、「WHERE keyX > 10 件目の keyX 値 ... LIMIT 10」とすれば 処理効率が落ちない。この方法はページング処理において定石となっている。

語句

カーディナリティ

列値のばらつき度合いを示す。

  • カーディナリティが大きい : 列値の取りうる種類が多い インデックスを貼るのに向いている
  • カーディナリティが小さい : 列値の取りうる種類が少ない インデックスを貼るのに向いていない

しかし、たとえカーディナリティが低くても、実データが大きく偏っており、 それを指定することで、大きく処理対象のデータ数を絞り込みできる場合もある。

最後に

とても大事な部分なので、かなり長くなりました。 これらを知っているのといないのでは、DBの設計が大きく変わってきますね。 次回は更新系のパフォーマンス改善について書きます。