JOIN のアルゴリズムについて
MySQL の JOIN アルゴリズムは NLJ (Nested Loop JOIN) のみとなる。ただし、NLJ をチューニングした BNLJ (Block Nested Loop JOIN) や BKAJ (Batched Key Access JOIN) などが存在する。
NLJ
NLJ の基本となるアルゴリズムはループとなる。例えば t1 と t2 という 2 つのテーブルを条件を指定せずに結合する場合は以下のようになる。
for each row in t1 {
for each row in t2 {
send joined row to client
}
} このように、t1 の全ての行と t2 の全ての行を組み合わせた結果行がクライアントに送信される。テーブル数が増えればループのネストがどんどん深くなる。
また、WHERE 句による絞り込みを行う際は以下のようになる。
for each row in t1 matching where condition {
for each row in t2 mating join and where condition {
send joined row to client
}
} 上記のようなアルゴリズムのため、できるだけ早い段階で多くの絞り込みを行なった方が効率的なクエリとなる。よって JOIN の順序は効率化するために重要な要因となる。
BNLJ や BKAJ も基本的にはこのアルゴリズムに従い、バッファを用いてできる限り行アクセスを効率化しているという違いがある。
BNLJ
BNLJ は、内部表へのアクセスにおいてインデックスが使用できない際の負荷を軽減する。インデックスが使用できないということは、駆動表から 1 行フェッチするごとに、その行とマッチする行を探すために内部表がスキャンされることになり、これは効率が悪い。
JOIN の条件が存在するのに有効なインデックスがない場合には、インデックスを追加してスキャンが行われないようにすべきである。ただ、1 日 1 回しか実行されないようなレポーティングなどの処理であればインデックスを使わずに JOIN することも許容される可能性がある。インデックスがあれば更新のコストが高くなるし、必要なストレージのサイズも増えてしまう。とはいえ、純粋な NLJ でインデックスを使用しないで JOIN するのは効率が悪い。
このような場合に BNLJ は効果を発揮する。
BNLJ は JOIN バッファというメモリ領域を使用し、内部表がスキャンされる回数を減らすアルゴリズムとなる。以下に概要図を示す (t1 が駆動表、t2 が内部表)。
駆動表から条件にマッチする行をフェッチすると、まず JOIN バッファにためられ、JOIN バッファがいっぱいになったら内部表をスキャンしてマッチする行を探すことになる。これにより内部表へのアクセスが減ることになる。例えば JOIN バッファに駆動表から取得した行を平均で 100 行貯めておけば、内部表をスキャンする回数は 1/100 まで低減されることになる。
BKAJ
まず、BKAJ の実行に必要な MRR (Multi Range Read) について記載する。
セカンダリインデックスを用いて検索を行うと、テーブルから行データを取得する際の操作はランダムアクセスとなる。InnoDB の場合はクラスタインデックス構造になっているため、主キーに行データが含まれており、MyISAM の場合にはデータは独立したテーブル名.MYD というファイルに格納されている。一般的にセカンダリインデックスと行データの順には相関が無いので、セカンダリインデックスの順に行データをフェッチすると、アクセスはランダムになる。それをシーケンシャルアクセスに変更するのが MRR となる。
以下に MRR を使わない場合と使う場合のアクセスの違いを示す。
[ MRR がない場合 ]
[ MRR がある場合 ]
BKAJ は BNLJ と MRR を組み合わせたアルゴリズムとなる。BKAJ は BNLJ と同様に駆動表から条件にマッチする行をフェッチし、JOIN バッファにためる。動作が異なるのはここから先で、BNLJ では内部表をスキャンするのに対して、BKAJ では内部表に MRR 最適化を用いてアクセスする。これにより InnoDB や MyISAM では内部表へのアクセスがランダムアクセスではなくシーケンシャルアクセスとなる。
内部表は全てスキャンされるのではなく、“データファイル内における行のならび順で”、“必要な行だけが” フェッチされることになる。
なお、BKAJ は MRR を前提としたアルゴリズムであるため、全てのデータがメモリ上に収まっている場合は IO 数に変化はなく、あまり性能向上は期待できない。