mysqlをdisる会の記事を読んで、インストールや設定のわかりづらさにｳﾝｳﾝ言ってたのですが、インデックスの話が少し気になったので、検証したことをメモします。
先に結論を書くと
- 複合キーでの検索の仕組みは、50音順の辞書を連想すると理解しやすい
- だけど、オプティマイザがどう判断するかは話が別
- 条件を「aとb」にしたときと「aとc」にしたときで、実際の処理が変わらないSQLもあれば、処理が異なるSQLもある
準備
まず、元の記事と同じテーブルを作ります。MySQLは手元にあったMySQL-5.6.14を使用しました。
作成したテーブルは以下のコマンドで作成。
CREATE TABLE index3 (
a INTEGER NOT NULL DEFAULT 0,
b INTEGER NOT NULL DEFAULT 0,
c INTEGER NOT NULL DEFAULT 0,
INDEX(a,b,c)
);
私の環境では以下のようになりました。文字コードなどは環境によって異なると思いますが、ストレージエンジンはInnoDBであることを確認します。
mysql> SHOW CREATE TABLE index3\G
Table: index3
Create Table: CREATE TABLE `index3` (
`a` int(11) NOT NULL DEFAULT '0',
`b` int(11) NOT NULL DEFAULT '0',
`c` int(11) NOT NULL DEFAULT '0',
KEY `a` (`a`,`b`,`c`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
テスト用データですが、元記事にはどのようなデータか詳しく書いていなかったので、以下のスクリプトを使って100万件作成しました。
require 'mysql2'
client = Mysql2::Client.new(:host => 'localhost', :username => 'root', :password => '')
q = %{ INSERT INTO mydis.index3 (a, b, c) VALUES (?, ?, ?) }
stmt = client.prepare(q)
client.query('begin');
for a in 1..100
for b in 1..100
for c in 1..100
stmt.execute(a, b, c)
end
end
end
client.query('commit');
これは具体的には、cが1～100まで1ずつ増えてゆき、cが100に到達すると繰り上がってbが1増えてcは1に戻り、bも100に到達すると繰り上がってaが1増えて……というデータで、以下のようになります。
+-----+-----+-----+
| a | b | c |
+-----+-----+-----+
| 1 | 1 | 1 |
| 1 | 1 | 2 |
| 1 | 1 | 3 |
| （中略） |
| 1 | 1 | 99 |
| 1 | 1 | 100 |
| 1 | 2 | 1 |
| 1 | 2 | 2 |
| （中略） |
| 1 | 2 | 99 |
| 1 | 2 | 100 |
| 1 | 3 | 1 |
| 1 | 3 | 2 |
| （中略） |
| 1 | 100 | 100 |
| 2 | 1 | 1 |
| 2 | 1 | 2 |
| （中略） |
| 100 | 100 | 99 |
| 100 | 100 | 100 |
+-----+-----+-----+
複合キーについて
元の記事の方は、「(a,b,c)や(a,b)や(a,c)ではインデックスが使えるけど(b,c)では使えなくてややこしい」という意見だと思います。（誤読していたらごめんなさい。）
しかし、これはMySQLに限った話ではなく、DBのインデックスというもの自体がそういう仕組みなのではないかと思います（「思います」である理由は後述します）。
まずは、MySQLがどうするかという話を横に置いて、「自分が実際に作業するならどのような手順でデータを取り出すか？」を想像してみます。
DBのインデックスはその名の通り目次なので、ここでは、目次を使って辞書から単語を探す作業で喩えます。
INDEX(a,b,c)で作成されるインデックスは、「優先順位がa列,b列,c列の順でソートされている目次」と考えられます。
辞書で喩えるならば、a列は1文字目、b列は2文字目、c列は3文字目と考えると、このインデックスが50音順の辞書の並びに相当します。
この場合、WHERE a > X AND b > Y AND c > Zという条件は、「1文字目がカより後、2文字目がシより後、3文字目がパより後」というような条件に相当します。
この条件に一致する単語を手動で調べるとしたら、まず第一に辞書の「カ」以前のページは無視します。1文字目がカより後の単語はそのページには絶対にないからです。これがこの喩えの文脈での「インデックスが効いている」状態です。
一方で、WHERE b > Y AND c > Zという条件は、「2文字目がシより後、3文字目がパより後」のように喩えられます。
この条件では、1文字目を使ってページを絞り込めないので、アのページからンのページまで順に探さなければなりません。この喩えの文脈での「フルインデックススキャン」状態です。
そう考えれば、「(a,b,c)や(a,b)や(a,c)ではインデックスが使えるけど(b,c)では使えない」というのも別段ややこしくはありません。
（というか正確には、今回のテーブルでは「(b,c)の場合、インデックスは使用されるが、インデックス内をフルスキャンしている」ですね。）
「思います」の理由（言い訳）
最初に「MySQLに限った話ではなく、DBのインデックスというもの自体がそういう仕組みなのではないかと思います」と書いた理由なのですが、この辺の調査をMySQLでしかしたことがないので、他のDBでは事情が違うのかもしれません。。。ご存知の方がいらっしゃいましたらぜひ教えてください！
a > X AND b > Y と a > X AND c > Y の違い
前述の喩えで考えると、「条件にa,bを使った場合とa,cを使った場合では効率が異なるのではないか？」という疑問が浮かびます。
a,bを使った場合を辞書に喩えると「1文字目がカより後、2文字目がシより後」です。
一方、a,cを使った場合は「1文字目がカより後、3文字目がパより後」です。
前者の作業を人間が行う場合、以下のようにします。
- まず「カ」以前のページを無視＝「キ」を開く
- 次に「キシ」以前のページを無視＝「キス」を開く
- 「キス」をスタート地点として、条件に合うものを順番に探していく
一方、後者の場合は、上記の2つ目の絞込みができないので、「キ」をスタート地点とすることになります。
しかし、元の記事のEXPLAINには上記の差はありません。
オプティマイザの判断
辞書の喩えでは、自分ならどう作業するかを考えましたが、MySQLのデータでこの「どう作業するか」を判断するのがオプティマイザです。
オプティマイザについては詳細を理解していないのですが、ドキュメントには以下のように書かれています。
MySQL はコストベースのオプティマイザを使用して、クエリーを実行する最適な方法を判別しています。多くの場合、MySQL は実行可能な最適なクエリー計画を計算できますが、データに関する情報を十分に取得できず、データについて「学習による」推測を行う必要がある場合があります。
MySQL で「適切」に処理されなかった場合に、MySQL に指示を送るために使用できるツールを次に示します。
要するに、「データに関する情報を元に最適な計画を立てようと頑張るけれど、情報が足りないと最適にならないこともあるよ」というような意味です。
ここには、実際にオプティマイザがどのような判断をしているかを見るためにEXPLAINを使えとあるので、実際に使ってみます。EXPLAINの読み方は以下を参考にします。
元の記事とはデータの数や分布が異なるので、改めて自分の環境で計測した結果を記載します。
mysql> EXPLAIN SELECT COUNT(*) FROM index3 WHERE a > 90 AND b > 90;
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
| 1 | SIMPLE | index3 | range | a | a | 4 | NULL | 194706 | Using where; Using index |
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
mysql> EXPLAIN SELECT COUNT(*) FROM index3 WHERE a > 90 AND c > 90;
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
| 1 | SIMPLE | index3 | range | a | a | 4 | NULL | 194706 | Using where; Using index |
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
a,bを使った場合もa,cを使った場合も、まったく同じ結果が出ています。
keyとしてaと表示されていますが、これが何を表すのかはSHOW INDEX FROM index3;で確認できます。
mysql> SHOW INDEX FROM index3;
+--------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| index3 | 1 | a | 1 | a | A | 202 | NULL | NULL | | BTREE | | |
| index3 | 1 | a | 2 | b | A | 20367 | NULL | NULL | | BTREE | | |
| index3 | 1 | a | 3 | c | A | 997984 | NULL | NULL | | BTREE | | |
+--------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
テーブル作成時にINDEX(a,b,c)で指定したインデックスに、aという名前が付けられており、a列,b列,c列の順番の複合キーであることがわかります。
EXPLAINのkeyがaなのは、このインデックスが使用されたという意味になります。
注目はkey_lenが4になっていることです。ドキュメントのkey_lenの項目には以下のようにあります。
key_len の値によって、MySQL が実際に使用するマルチパートキーのパート数を判断できます。
つまり、複合キー(a,b,c)のうち、長さ4が使われていることになります。MySQLのINTEGERの長さは4なので、INTEGERひとつぶん、a列のぶんだけが使用されていることがわかります。
今回は、「検索条件がa,bでもa,cでも、(a,b,c)のインデックスのうちaだけ使う」とオプティマイザが判断したことがわかります。
差が出るSQLもある
上記の例ではa,bのときもa,cのときも同じ結果になりましたが、ほとんど同じSQLでも差が出ることがあります。
条件の> 90を>= 91に変えてみます。今回のa,b,cは整数なので、これらの条件で得られる最終的な結果は同一のはずです。
EXPLAINの結果は以下のようになりました。
mysql> EXPLAIN SELECT COUNT(*) FROM index3 WHERE a >= 91 AND b >= 91;
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
| 1 | SIMPLE | index3 | range | a | a | 8 | NULL | 176800 | Using where; Using index |
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
mysql> EXPLAIN SELECT COUNT(*) FROM index3 WHERE a >= 91 AND c >= 91;
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
| 1 | SIMPLE | index3 | range | a | a | 4 | NULL | 194706 | Using where; Using index |
+----+-------------+--------+-------+---------------+------+---------+------+--------+--------------------------+
key_lenにもrowsにも違いが出ています！
a,bを使った方のkey_lenが8になっており、aだけでなくbまでが使用されていることがわかります。よって、前述の辞書の喩えでいうと「キス」を探す作業までを行っていると考えられます。
rowsは17,906件減っています。理論上は、a=91のレコードのうちb=1～b=90までの9,000行がスキップできたはずですが、まぁこの値はあくまでも予測見積もりなので、あまり気にしなくていいと思います。
まとめ
私は、DBのパフォーマンスやインデックスを考えるとき、いつもこの辞書の喩えを思い出して、自分が作業するならどうするか考えています。
それでもオプティマイザがどのように判断するかは話が別というところが、難しいところだなぁと思います。
（そもそも、今回のような分布が単純で量が少ないデータならまだしも、実際には複雑で大量のデータを扱うので、自分で最適な処理を想像できるとも限らないのですが。。。）
それから、さっきも書きましたが、他のDBでは事情が違うぞとか、お前の認識原始的過ぎるぞ、という可能性もありますので、ご存知の方がいらっしゃいましたらぜひ教えてください！