MySQL 5.6で追加された新しい最適化
現在最新の開発版であるMySQL 5.6では、オプティマイザの改良がいくつか行われている。
- BNLJがLEFT/RIGHT JOINに対応。（以前はInner JOINのみ）
- Batched Key Access Joinアルゴリズムの追加
- Multi Range Read最適化の追加
- Index Condition Pushdown最適化の追加
- FROM句のサブクエリの評価の先延ばし（その結果マテリアライズする必要性が低下）
本稿では、新しいJOINアルゴリズムであるBatched Key Access Joinについて解説するが、BKAJが内部的に利用する最適化アルゴリズムであるMulti Range Readというアルゴリズムについて先に触れよう。
Multi Range Read
Multi Range Read（以下MRR）は、簡単にいうと「ディスクの並び順に従ってデータファイルを読み取る」というもので、RDBMSでは非常に古くからある最適化手法である。セカンダリインデックスを使って検索を行うと、レコード全体を取得する際の操作はランダムアクセスになってしまう。InnoDBの場合はクラスタインデックスとして主キーにレコードが含まれており、MyISAMの場合にはレコードは独立した"テーブル名.MYD"という名前のファイルに格納されている。一般的にはセカンダリインデックスとレコードの順序には相関がないので、セカンダリインデックスの順序でレコードをフェッチすると、レコードへのアクセスはランダムアクセスになってしまうのだ。レコードがメモリ上のバッファにすべて存在する場合にはランダムアクセスでも問題にならないが、ディスク上にある場合にはランダムアクセスは効率が悪い。それをシーケンシャルアクセスに変更するのがMRR最適化なのだ。
MySQLでは今回が初登場であるが、既に様々なRDBMSで当たり前のように実装されている最適化アルゴリズムある。ストレージエンジンを前提とした標準的なアルゴリズムを実装したというところがミソである。
MRRでは、ファイル（ディスク上のオブジェクト）へのアクセスを最適化するものなので、全てのデータがメモリに乗っているような場合には意味がない。最近はそのような環境も増えてきたので、MRRに対する過度の期待は禁物である。
Batched Key Access Join
Batched Key Access Join（以下BKAJ）は、BNLJと非常によく似たアルゴリズムである。BKAJはBNLJと同じく、駆動表から条件にマッチするレコードをフェッチして、いったんJOINバッファにためる。動作が異なるのはそこから先で、BNLJでは内部表に対してスキャンを行うのに対して、BKAでは内部表に対してMRR最適化を用い、インデックスを用いてアクセスするという点だ。
これにより、InnoDBやMyISAMでは内部表へのアクセスがランダムアクセスではなくシーケンシャルアクセスになる。BNLJとは違って、内部表はすべてスキャンされるのではなく、必要なレコードだけがフェッチされるようになる。しかもデータファイル内におけるレコードの並び順でである。ただし、実装方法としてBNLJとBKAJは似ているが、両者のパフォーマンスを比較するのはナンセンスである点に留意したい。元々BKAJは、内部表へのアクセスにおいてインデックスが利用できる場合のアルゴリズムなので、インデックスが利用できないために内部表をスキャンする必要があるBNLJとはユースケースが全く異なる。BKAJと比較すべきなのは、内部表へのアクセスにインデックスが利用できるNLJなのである。
BKAJはMRRを前提としたアルゴリズムなので、MRR同様すべてのレコードがメモリ内に収まっている場合には性能向上は期待できないだろう。反対に、データ量が巨大でバッファの何倍もあるような場合には、BKAJによって劇的な性能向上が見込めることになる。
また、BKAJはMySQL Clusterのようにデータがリモートのホストに格納されている場合にはかなりの効果が期待できる。インデックスの値をまとめてストレージエンジンに渡し、それに対応したレコードをまとめて受け取ることによって、ネットワークのラウンドトリップが少なくなるからだ。ただし、現行執筆時点での最新正式バージョン（MySQL Cluster 7.1）および最新の開発版（MySQL Cluster 7.2）では、残念ながらまだBKAJは利用できない。将来のバージョンで、SQLノードとしてMySQL 5.6以降のバージョンが採用されるのを待とう。
