Index Condition Pushdown
BKAJのアルゴリズムの解説のついでに、MySQL 5.6で追加された最適化アルゴリズムであるIndex Condition Pushdown（以下ICP）についても触れておこう。
ICPを利用しない場合、MySQLではマルチカラムインデックス内で先に定義されたキーから順に指定しなければインデックスが利用されない。たとえば、３つのINTカラムで構成された(col1, col2, col3)というセカンダリインデックスがある場合、このインデックスを用いて検索するにはcol1から順に検索条件として指定されなくてはならない。なおかつ、右側のカラムがインデックスの条件として用いられるには、左側のカラムが等価比較でなければならない。例えばWHERE col1=1 AND col2<10というような条件である。この場合、col3は指定されていないが、col1およびcol2の値を条件にして、ストレージエンジンからレコードをフェッチする際にインデックスが用いられる。
もし間のカラムの値が指定されていない場合、例えばWHERE col1=1 AND col3<10というような場合には、残念ながらcol3はストレージエンジンからレコードをフェッチする際には評価されない。いったんcol=1の条件だけを用いてストレージエンジンからレコードをフェッチし、その後MySQL本体（SQL実行部分）が残りの検索条件であるcol3<10の部分を評価することになる。この場合、先ほどの例よりも絞り込みの条件が少ないため、平均するとストレージエンジンからフェッチされるレコード数は多くなり、効率が悪い。この条件のクエリを最大限インデックスを用いて効率化するには、(col1, col3)というインデックスが必要になる。
ストレージエンジンからインデックスの値に基づいてレコードをフェッチするのと、レコードをフェッチしてからWHERE句の他の条件で絞り込むのとではそんなに違うのか？と思われるかも知れないが、実は大きな違いがある。理由は次の2つだ。
- 不要なレコードがフェッチされる。上記の例では、col3の値が何であってもcol1=1という条件にマッチするレコードが全ていったんフェッチされる
- レコードのフェッチは処理が重い。レコードはセカンダリインデックスとは異なる場所に格納されているため
ICPではこの問題を解消する。以下はICPによってストレージエンジンからフェッチするレコードが減少している様子を示している。
ちなみに、クエリがCoverying Indexで解決できる場合にはICP最適化の出番はない。クエリがCoverying Indexで、すなわちセカンダリインデックスだけで解決できるなら、そもそもレコード本体にアクセスする必要がないからだ。とはいえ、全てのクエリをCoverying Indexで解決するのは現実的ではなく、インデックスをつけるカラムは絞り込む必要があるだろう。（セカンダリインデックスが増えれば増えるほどと更新の負荷が高くなり、なおかつデータ量が増えてしまうからだ。）しかしICPをうまく活用すれば、Coverying Indexほどではないにしろ高速化を狙うことが可能だ。複合インデックスを作成する場合に、ICPを考慮すれば、どのカラムを含めるかという選択肢の幅が増えることになるだろう。
まとめ
ここまで、MySQLが使用する基本的なJOINのアルゴリズムであるNLJ、BNLJ、さらにはBKAJについて解説してきた。どのようにJOINが実装されているかということを意識すれば、効率の良いJOINをSQLを使って書くのに役立つだろう。MRRやBKAJは潤沢にメモリがあってワーキングセットがすべてメモリに収まるような環境では、あまり恩恵がないと言える。高速なPCIeタイプのSSDを利用する場合にも効果は低い。また、ICPはCoverying Indexが利用できる場合には一切効果がない。どのような状況でどのような最適化が利用されるか、またはされないかを知っていれば、上手にクエリの書き換えやインデックスの設計ができるようになるだろう。
次回は、クエリのチューニングの総括として、オプティマイザの重要なテーマのひとつであるソートの最適化と、基本的なクエリの書き換えについて解説しようと思う。
