Block Nested Loop Join
Block Nested Loop Join（以下BNLJ）は、内部表へのアクセスにおいてインデックスが使えない場合の負荷を軽減する。インデックスが使えないということは、駆動表から1行フェッチするごとに、その行とマッチする行を探すべく内部表がスキャンされるということである。スキャンを繰り返し実行するのは非常に効率が悪いので、オンライン系トランザクションでそのような処理が起きている場合には、インデックスを追加してスキャンが行われないようにするなどの対処を直ちにおこなう必要がある。だが、1日1回しか実行しないようなレポーティングなどの処理ならば、インデックスを使わずにJOINするというような状況も十分にあり得るだろう。そのような場合、効果を発揮するのがBNLJだ。
BNLJはJOINバッファというバッファを使って、内部表がスキャンされる回数を減らすアルゴリズムである。以下の図はBNLJを実行する様子を模式的に示したものである。（t1が駆動表、t2が内部表）
駆動表から条件にマッチするレコードをフェッチすると、それをまずJOINバッファにためる。JOINバッファがいっぱいになったら内部表をスキャンして、マッチするレコードを探すのである。こうすることで、NLJでは駆動表からフェッチしたレコード数と同じ回数だけ内部表のスキャンが必要だったのが、BNLJでは「駆動表からフェッチしたレコード数 ÷ JOINバッファに貯めることができるレコード数」まで内部表のスキャン回数が減ることになる。例えば、JOINバッファに駆動表のレコードを100行貯めこんでおくことができれば、内部表をスキャンする回数は1/100まで低減されることになるのだ。
従って、BNLJでは内部表をスキャンすることで生じるI/O負荷は劇的に軽減されることだろう。ただし、最終的にはバッファ内のレコードと、内部表のレコードが逐一比較されることになるため、CPUには負荷がかかることになる。全てのレコードがメモリ（InnoDBバッファプール）に収まっているような贅沢な環境では、BNLJはそれほど効果はないと言える。
駆動表からフェッチしたレコードが全部JOINバッファに収まると、内部表をスキャンする回数は1回だけで済むので、その場合が最も高速となる。それ以上JOINバッファを増やしても性能は向上しない。JOINバッファが大きすぎると、メモリ割り当てのためのオーバーヘッドが大きくなるし、メモリを使いすぎることでスワップが発生する恐れもあるので、サイズは慎重に選ぶようにしたい。JOINバッファはセッションごとに変えることができるので、レポーティングなどの処理を行う場合には、アプリケーション側で事前にSETコマンドでサイズを変更するといった工夫をしよう。
