MySQL6.0における新しいJOIN最適化手法 - BKA

MySQL 6.0では新たなJOIN最適化手法であるBKA - Batched Key Accessの実装が進んでいる。BKAとは、読んで字のごとくキーを用いたアクセスをバッチ（ひとまとまりの）処理にすることである。現在のバージョンのMySQLでは、2つのテーブルをJOINする際、一つ目のテーブルから選択した行に対して、逐一2つめのテーブルから行が一つずつフェッチされる。例えば次のクエリを用いてテーブルt1とt2をJOINする際には以下のような流れで行われる。

mysql> SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b WHERE t1.c > 1000 AND t1.c <= 2000;

t1からWHERE句の条件（1000 < c <= 2000）に適合する行をフェッチする。 条件に合う行が1000行あったとする。 1行目のt1.aと同じt2.bの値を持つ行をt2からフェッチする。 2行目のt1.aと同じt2.bの値を持つ行をt2からフェッチする。 　　: 1000行目のt1.aと同じt2.bの値を持つ行をt2からフェッチする。

という具合に、上記の場合にはt2テーブルに対して1000回のキーアクセスが発生してしまう。t2.bの順番がバラバラである場合や、t2.bにインデックスがない場合、さらにはt2がMySQL Clusterのようにリモートホストにある場合などには、1000回のキーアクセスは無視出来ないオーバーヘッドになってしまう。BKAを利用すると、次のような流れでクエリが処理される。

t1からWHERE句の条件（1000 < c <= 2000）に適合する行をフェッチする。 条件に合う行が1000行あったとする。 1000行分のt1.aの値をt2.bのキーとしてストレージエンジンにプッシュする。 ストレージエンジンからt2.bのキーに適合する行が返される。

つまり1000回も必要だったキーアクセスが、たった1回の大きな処理になってしまう。BKAが実装された暁には、MySQL Clusterが苦手としているJOINの性能が向上することであろう。

MySQL Clusterは上記のように細かいキーアクセスが発生するような状況は本当に苦手なのである。それはネットワークのレイテンシに起因する。ギガビットイーサネットでは、ホスト間の通信において最低でも25マイクロ秒程度のレイテンシが発生する。間にスイッチが入るとさらに倍、往復でさらに倍で、100マイクロ秒となる。それが1000回発生すると100ミリ秒＝0.1秒。ネットワークのレイテンシだけでこんなにも掛かってしまうことになるのである。これが、現在MySQL ClusterがJOINを苦手とする理由である。BKAを使えばネットワークのレイテンシによるオーバーヘッドは劇的に減少する。この例では1往復分なので100マイクロ秒である。

BKAは6.0系における次のバージョンである6.0.9αから利用できる。ただし、MySQL 6.0.xには現時点でMySQL Clusterが含まれていないので、MySQL Clusterにおける性能改善をテストすることはできない。MyISAMでも性能が改善するので、検証をしたい人はそちらを使うといいだろう。BKAを利用するには、次のオプションを有効にする必要がある。

mysql> SET engine_condition_pushdown=1;
mysql> SET optimizer_use_mrr=1;
mysql> SET join_cache_level=6;
mysql> SET join_buffer_size=2*1024*1024; -- お好みで

BKAはMRR - Multi Read RangeやICP - Index Condition Pushdownに立脚した最適化手法であるので、これらの手法についても一読されることをお勧めする。（英語だけど）

http://dev.mysql.com/doc/refman/6.0/en/mrr-optimization.html
http://dev.mysql.com/doc/refman/6.0/en/index-condition-pushdown-optimization.html

BKAに関する詳細な情報については、次のプレゼン資料でわかり易く説明されているので見て欲しい。（英語だけど）
http://forge.mysql.com/w/images/9/9f/BatchedKeyAccess-UC2008.pdf