つい最近、最新の開発版であるMySQL 5.6.3 m6がリリースされたが、このバージョンにはBatched Key Access JOIN（以下BKA JOIN）という新しいJOINのアルゴリズムが組み込まれている。その他にもMySQL 5.6ではいくつかオプティマイザの改良が行われているので、条件に合致すれば同じクエリを実行した場合でも、以前のバージョンより効率的な実行計画になるだろう。データベースエンジニアにとって、クエリのチューニングは必須スキルであるが、BKA JOINについて理解するためには、MySQLがどのようにJOINを実行するかということについて知っておく必要がある。そこで、本エントリではまずMySQLにおけるJOINのチューニングの定石について解説する。
Nested Loop Join
実は、MySQLが実装しているJOINのアルゴリズムは、Nested Loop Join（以下NLJ）とその変化形だけである。MySQL 5.6.3で新たに加わったBKA JOINも、ある条件下においてNLJを高速化したアルゴリズムであると見做すことができる。他のRDBMSではマージソートJOINやハッシュJOINといったアルゴリズムが実装されているものが多いが、MySQLはそれらのアルゴリズムには今のところ無縁である。
NLJとは一体いかなるアルゴリズムであるか。本稿の読者の多くはご存知のことだろうが、JOINの最適化を考える上でアルゴリズムの理解は欠かせないので、ここで改めて解説しよう。NLJについて熟知している人は読み飛ばして頂いて結構だ。
NLJはその名が示すように、基本となるアルゴリズムはループである。t1とt2という２つのテーブルを条件を指定せずに結合する場合、つまり直積（Product）を実行する場合のアルゴリズムは次のようになる。
for each row in t1 {
for each row in t2 {
send joined row to client
}
}
このようにNLJの処理はループになっており、テーブル数が増えればループのネストがどんどん深くなる。通常、直積が必要となるケースは稀であり、結合の条件を指定したり、それぞれのテーブルからフェッチする行について条件を指定するため、NLJのアルゴリズムは次のようになる。
for each row in t1 matching where condition {
for each row in t2 matching join and where condition {
send joined row to client
}
}
この記事は参考になりましたか？
- この記事の著者
-
奥野 幹也 （オクノ ミキヤ）
日本オラクル株式会社
MySQL Global Business Unitテクニカルアナリスト※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
この記事は参考になりましたか？
この記事をシェア
