8.2.1.10 Nested Loop 結合アルゴリズム

MySQL は、Nested Loop アルゴリズムまたはそのバリエーションを使用してテーブル間の結合を実行します。

Nested Loop 結合アルゴリズム

単純な Nested Loop Join (NLJ) アルゴリズムは、ループ内の最初のテーブルから行を一度に 1 つずつ読み取り、各行を、結合の次のテーブルを処理するネストしたループに渡します。このプロセスは、結合するテーブルが残っている回数だけ繰り返されます。

3 つのテーブル t1、t2、および t3 間の結合が、次の結合型を使用して実行されるとします。

Table   Join Type
t1      range
t2      ref
t3      ALL

単純な NLJ アルゴリズムを使用した場合、結合は次のように処理されます。

for each row in t1 matching range {
  for each row in t2 matching reference key {
    for each row in t3 {
      if row satisfies join conditions,
      send to client
    }
  }
}

NLJ アルゴリズムでは、外側のループから内側のループに、一度に 1 つずつ行を渡すため、一般に内側のループで処理されるテーブルを何回も読み取ります。

Block Nested Loop 結合アルゴリズム

Block Nested-Loop (BNL) 結合アルゴリズムは、外側のループで読み取られた行のバッファリングを使用して、内側のループでテーブルを読み取る必要がある回数が削減されます。たとえば、バッファーに 10 行が読み込まれ、このバッファーが次の内側のループに渡される場合、内側のループで読み取られる各行をバッファー内のすべての 10 行と比較できます。これにより、内部テーブルを読み取る必要のある回数が大幅に減少します。

MySQL は、次の条件下で結合バッファリングを使用します。

• join_buffer_size システム変数によって各結合バッファーのサイズが決まります。

• 結合バッファリングは、結合の型が ALL または index である (つまり、使用できるキーがなく、データ行またはインデックス行の完全スキャンがそれぞれ実行される場合) か、または range である場合に使用できます。MySQL 5.6 では、セクション8.2.1.14「Block Nested Loop 結合と Batched Key Access 結合」に説明するように、バッファリングの使用が外部結合に適用できるように拡張されています。

• バッファリング可能な結合ごとに 1 つのバッファーが割り当てられるため、特定のクエリーが、複数の結合バッファーを使用して処理されることがあります。

• ALL 型または index 型であっても、最初の非定数テーブルには結合バッファーが割り当てられません。

• 結合バッファーは、結合の実行前に割り当てられ、クエリーの完了後に解放されます。

• 結合バッファーには、行全体ではなく、結合に関連するカラムだけが格納されます。

NLJ アルゴリズム (バッファリングなし) で先述した結合の例では、結合は結合バッファリングを使用すると、次のように実行されます。

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions,
          send to client
        }
      }
      empty buffer
    }
  }
}

if buffer is not empty {
  for each row in t3 {
    for each t1, t2 combination in join buffer {
      if row satisfies join conditions,
      send to client
    }
  }
}

S が結合バッファー内の格納される各 t1、t2 の組み合わせのサイズであり、C がバッファー内の組み合わせの数である場合、テーブル t3 がスキャンされる回数は:

(S * C)/join_buffer_size + 1

join_buffer_size が前のすべての行の組み合わせを保持できるだけの大きさになる時点まで、join_buffer_size の値が大きくなるほど、t3 スキャンの回数は減少します。その時点では、さらに大きくしても速度は向上しなくなります。