Shoeisha Technology Media

EnterpriseZine(エンタープライズジン)

EnterpriseZine(エンタープライズジン)

テーマ別に探す

Block Nested Loop Join/Batched Key Access Join

2011/11/30 00:00

前回はNested Loop Join(以下NLJ)の原理とオプティマイザの挙動を大まかに説明した。NLJは非常に高速なJOINアルゴリズムなので普段はNLJだけでも困らないのだが、内部表へのアクセスにインデックスを使えない場合には必ずしも最適なアルゴリズムであるとは言えない。この問題に対して、MySQLはNLJの改良版である、Block Nested Loop Joinを実装しているので、本稿ではまずこのアルゴリズムについて紹介する。次に、内部表へのアクセスにインデックスを用いている場合でもさらに高速化の可能性がある、Batched Key Access Joinについても解説しよう。こちらは最新の開発版であるMySQL 5.6.3 m6で追加された機能である。

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コマンドでサイズを変更するといった工夫をしよう。


著者プロフィール

バックナンバー

連載:MySQLチューニング虎の巻
All contents copyright © 2007-2018 Shoeisha Co., Ltd. All rights reserved. ver.1.5