ちょっと硬派なコンピュータフリークのBlogです。

カスタム検索

2010-10-05

知って得するInnoDBセカンダリインデックス活用術!

InnoDBはクラスタインデックスという構造になっている。今日はクラスタインデックスがどういうことかということを、皆さんに理解して頂きたい。もっとも理解して頂きたいポイントは「セカンダリインデックスのリーフノードには主キーの値が含まれている」ということだ。

主キーの構造

InnoDBの主キーは次の図のように「データが主キーのリーフノードに含まれる」という構造になっている。このような構造をクラスタインデックスという。
このような構造になっていることには利点と欠点があるが、大きな利点は主キーの値で検索をすると非常に高速だということだ。主キーのリーフノードにたどり着いたときには、既にデータのフェッチも完了している。データとインデックスが別々に格納されているタイプのストレージエンジンでは、インデックスからデータの位置を読み取って、その後データファイルからデータをフェッチする。このように二段階の操作が必要であると、キャッシュが効いていない場合には余分なディスクI/Oが生じてしまうだろう。だが、クラスタインデックスになっていると、インデックスを検索するだけでデータもフェッチできるのである。

クラスタインデックスのデメリットとしては、インデックスのサイズが大きくなってしまうこと、セカンダリインデックスを用いた検索が遅くなってしまうことなどが挙げられる。後者については次の項で解説しよう。

セカンダリインデックスの構造

クラスタインデックスを用いる場合、データはすべて主キーに格納されているので、セカンダリインデックスは特殊な構造にならざるを得ない。セカンダリインデックスの値からデータを取得するにはどうすればいいのだろうか?ご存知の方も多いだろうが、セカンダリインデックスのリーフノードには主キーの値が格納されている。例えば次のようなテーブルがあるとしよう。
mysql [localhost] {msandbox} (test) > show create table t1\G
*************************** 1. row ***************************
       Table: t1
Create Table: CREATE TABLE `t1` (
  `a` int(10) unsigned NOT NULL,
  `b` int(11) DEFAULT NULL,
        :
   その他のカラム
        :
  PRIMARY KEY (`a`),
  KEY `b` (`b`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row in set (0.00 sec)
カラムaが主キー、bがセカンダリインデックスである。このテーブルに対して、b=2の条件で検索をかけたとき、たまたま主キーの値a=3という検索結果が得られたとする。他のカラムの値(=データ)にアクセスするためには、そこからさらに主キーで検索をしなければならないのである。
もちろん、これは検索のコストが高くつく。単純計算では主キーの倍である。

見えざるCovering Index

クラスタインデックスにおけるセカンダリインデックスは、悪いことばかりではない。そもそも検索がセカンダリインデックスだけで済むようにCovering Indexにすれば非常に高速だ。その辺の事情については、過去記事「InnoDBでCOUNT()を扱う際の注意事項あれこれ。」にも書いてあるので参照して頂きたい。

セカンダリインデックスには主キーの値が格納されていることは先程述べた通りである。それは、即ちセカンダリインデックスの定義には、最後のカラムとして主キーが必ず含まれているようなものである。例えば、次のテーブル定義は全く同一なのである。
mysql [localhost] {msandbox} (test) > show create table t1\G
*************************** 1. row ***************************
       Table: t1
Create Table: CREATE TABLE `t1` (
  `a` int(10) unsigned NOT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`a`),
  KEY `b` (`b`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row in set (0.00 sec)
mysql [localhost] {msandbox} (test) > show create table t2\G
*************************** 1. row ***************************
       Table: t2
Create Table: CREATE TABLE `t2` (
  `a` int(10) unsigned NOT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`a`),
  KEY `b` (`b`,`a`)                      # <==== インデックスにカラムaを追加しても同じ!
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row in set (0.00 sec)
このことは、InnoDBテーブルモニターを使うとよく分かる。
--------------------------------------
TABLE: name test/t1, id 0 25, columns 5, indexes 2, appr.rows 0
  COLUMNS: a: DATA_INT DATA_UNSIGNED DATA_BINARY_TYPE DATA_NOT_NULL len 4; b: DATA_INT DATA_BINARY_TYPE len 4; DB_ROW_ID: DATA_SYS prtype 256 len 6; DB_TRX_ID: DATA_SYS prtype 257 len 6; DB_ROLL_PTR: DATA_SYS prtype 258 len 7;
  INDEX: name PRIMARY, id 0 25, fields 1/4, uniq 1, type 3
   root page 3, appr.key vals 0, leaf pages 1, size pages 1
   FIELDS:  a DB_TRX_ID DB_ROLL_PTR b
  INDEX: name b, id 0 26, fields 1/2, uniq 2, type 0
   root page 4, appr.key vals 0, leaf pages 1, size pages 1
   FIELDS:  b a
--------------------------------------
TABLE: name test/t2, id 0 26, columns 5, indexes 2, appr.rows 0
  COLUMNS: a: DATA_INT DATA_UNSIGNED DATA_BINARY_TYPE DATA_NOT_NULL len 4; b: DATA_INT DATA_BINARY_TYPE len 4; DB_ROW_ID: DATA_SYS prtype 256 len 6; DB_TRX_ID: DATA_SYS prtype 257 len 6; DB_ROLL_PTR: DATA_SYS prtype 258 len 7;
  INDEX: name PRIMARY, id 0 27, fields 1/4, uniq 1, type 3
   root page 3, appr.key vals 0, leaf pages 1, size pages 1
   FIELDS:  a DB_TRX_ID DB_ROLL_PTR b
  INDEX: name b, id 0 28, fields 2/2, uniq 2, type 0
   root page 4, appr.key vals 0, leaf pages 1, size pages 1
   FIELDS:  b a
両方のテーブルにおいて、2つ目のインデックスのFIELDSという項目には「b a」という2つのカラムが含まれているのがお分かりだろうか。テーブルt1のセカンダリインデックスには明示的にカラムaを追加していないのだが、暗黙的に主キーの値が含まれるのである。そのため、次のような検索は自ずとCovering Indexとなるため高速である。そして、ソートにもインデックスが利用される。
mysql> select a, b from t1 where b = 123 order by a;

まとめ

クラスタインデックスがどのような構造になっているかということ、その影響でInnoDBではセカンダリインデックスによる検索の特性が主キーとは異なるということについて説明した。そして、セカンダリインデックスには主キーの値が必ず含まれているので、Covering Indexとして利用できるということを説明した。クエリのチューニングを行う場合にはセカンダリインデックスの特性を考慮に入れて行うと、さらに一歩進んだ考察ができることだろう。

6 コメント:

kenn さんのコメント...

「セカンダリインデックスの定義には、最後のカラムとして主キーが必ず含まれている」とのことですが、実際にやってみるとCovering Indexにならず、PRIMARYとのUsing intersect (index_merge) になってしまいました。このようなクエリーでは、結局 (key, id) の複合インデックスは必要ということでしょうか?

mysql> explain SELECT * FROM things WHERE key = 100 AND (id < 1000000) ORDER BY id DESC LIMIT 10\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: things
type: index_merge
possible_keys: PRIMARY,index_things_on_key
key: index_things_on_key,PRIMARY
key_len: 4,4
ref: NULL
rows: 8067
Extra: Using intersect(index_things_on_key,PRIMARY); Using where; Using filesort
1 row in set (0.00 sec)

Mikiya Okuno さんのコメント...

kennさん、

コメントありがとうございます。

Coverying Indexにならないのは、SELECT *だからですね。他のカラムが混じっているとindex_things_on_keyだけでは解決できないのです。SELECT key, idだけならCoverying Indexとして処理可能です。

kenn さんのコメント...

ご回答ありがとうございます。
すいません、ぼけてました、Coverying Indexは関係なかったですね。

議論したかったポイントをあらためて整理しますと、主キーカラムを明示的に末尾に加えたインデックスとそうでないインデックスでは、同じクエリでも実行計画に違いが出てきたり、実測したところ性能にも大きく違いが出るケースがある、ということなのでした。

例をわかりやすくするために、Twitterで友達の最新タイムラインを取得するのをイメージしていただくといいのですが、(friend_id)と(friend_id, id)の二種類のインデックスをUSE INDEXして試しました。まずはexplainから。

mysql> explain SELECT * FROM messages USE INDEX (index_messages_on_friend_id_and_id) WHERE friend_id = 100 AND (id < 1000000) ORDER BY id DESC LIMIT 10\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: messages
type: range
possible_keys: index_messages_on_friend_id_and_id
key: index_messages_on_friend_id_and_id
key_len: 8
ref: NULL
rows: 183182
Extra: Using where
1 row in set (0.00 sec)

mysql> explain SELECT * FROM messages USE INDEX (index_messages_on_friend_id) WHERE friend_id = 100 AND (id < 1000000) ORDER BY id DESC LIMIT 10\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: messages
type: ref
possible_keys: index_messages_on_friend_id
key: index_messages_on_friend_id
key_len: 4
ref: const
rows: 97612
Extra: Using where
1 row in set (0.00 sec)

ここで、「セカンダリインデックスの定義には、最後のカラムとして主キーが必ず含まれている」が本当なら、(friend_id)でも(friend_id, id)でも同じになる、むしろ(friend_id, id)はキーが冗長になるので不利、と考えたのですが、実際にはidで範囲指定+ソートをする場合、(friend_id)を使ったケースでは最適な実行計画を得ることができませんでした。実際の運用でも、USE INDEX (friend_id)では2000msぐらいのslow logが頻出し、USE INDEX (friend_id, id)では一切slow logに出なくなりました。

これってつまり、末尾のidは単なるポインタで、ツリーとしてメンテされてるわけではないから、idでソートする場合には、やはり明示的にidをインデックスを含める必要がある、ということですよね?

よくタイトルをみれば、「見えざるCovering Index」とあるので、今ならCovering Indexに限定された話だと理解できるのですが、「例えば、次のテーブル定義は全く同一なのである。」というくだりの表現は誤解を招きやすいのではないか?と思いました。

ブログも本も、いつもお世話になっています。引き続き楽しみにしています。 :)

Mikiya Okuno さんのコメント...

kennさん、こんばんは。

ふーむ。実行時間に差異が出るのは不思議ですね。ちなみに、どちらのクエリも実行計画だけを見れば、ソートにインデックスを使っているということが分かります。なぜなら、Using filesortが出力されていないからです。

本文にも書いたとおり、いずれのインデックスも実体は同じです。(key_lenは異なる値が表示されていますが。)それでいて実行時間に差が生じるとすれば、インデックスがキャッシュに載ってるかどうかということだと思います。MySQLから見るといずれも同じ特性のインデックスに見えるので、USE INDEXを使わないクエリは片方のインデックスだけを集中的に選択し、その結果もう片方のインデックスがキャッシュから追い出されたため、SELECTの実行時間に差異が出たというシナリオが考えられます。

それを確かめるには、スロークエリログに出ているクエリを、負荷が低い時間に2回連続で実行してみてください。一回目と二回目で速度に差が出るかどうか、またはもう片方のインデックスを利用したときに速度差が出るかどうかということを見てください。また、SHOW SESSION STATUSでHandler関係の変数を見ることで、実際にレコードをいくつフェッチしているのかが分かりますので、より正確に2つのクエリの違いを測定できるかと思います。FLUSH STATUSをしてからクエリを実行すると、そのクエリによる増分(+SHOW STATUSによる増分)だけを見ることができるので便利です。

> ブログも本も、いつもお世話になっています。引き続き楽しみにしています。 :)

ありがとうございます!励みになります。

kenn さんのコメント...

超遅レスですが、この件、たまたま松信さんの

http://assets.en.oreilly.com/1/event/21/Mastering%20the%20Art%20of%20Indexing%20Presentation.pdf

を見ていて、やはRowIDはただのポインタで、ツリーとしてソートされて保持されてるわけではないから、というのが当たりのようです。

つまり、行フェッチしてくるところで上記資料の8-9pあたりで起こっているようなrandom i/oが発生して、速度が劣化する。セカンダリインデックスの末尾にidを明示的に加えることで、11pでMySQL6.0の新機能(資料が古い。。。)として紹介されているMulti-Range Readと似たような事前ソート効果が得られたのかなと思います。

それにしても、idでソートしてたかだかLIMIT件数しかrandom i/oが発生しないわけで、これだけの性能差が出るというのには、もしかしてWHEREの範囲検索やORDER BYに使われてるidの評価は、インデックスの末尾に暗黙に含まれるidベースでは行われてないんじゃないか?とさえ思えてきます。(RowIDの性質を考えると、ありそうな話だと思います)

というわけで、idを明示的にインデックス末尾に加えたほうがいいケースはありましたよというご報告まで。

ご報告まで。。。

Mikiya Okuno さんのコメント...

kenn さん、

お久しぶり?です :)

松信さんの資料を見ましたが、Covering Indexの話はP.20からですね。

InnoDBの場合、ROWIDというのは明示的に主キーがない場合だけ作成される隠れたカラムなんですが、なぜROWIDを用いて説明がなされているのかはちょっと合点が行かないところです。

あと、MRR最適化は、MySQL 5.6で搭載予定です。(ただし開発版なので予定は決定ではないのですが。)
http://dev.mysql.com/doc/refman/5.6/en/mrr-optimization.html

ところで一点気になることがあるのですが、使ってるバージョンはいくつでしょう。

コメントを投稿