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
}
}
