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

MySQL 8.0.18 より前は、このアルゴリズムはインデックスを使用できなかった場合に等価結合に適用されていました。MySQL 8.0.18 以降では、このような場合にハッシュ結合の最適化が採用されます。 MySQL 8.0.20 以降では、ブロックのネステッドループは MySQL で使用されなくなり、ブロックのネステッドループが以前に使用されていたすべての場合にハッシュ結合が使用されます。 セクション8.2.1.4「ハッシュ結合の最適化」を参照してください。

MySQL 結合バッファリングには、次の特性があります:

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 join 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 スキャンの回数は減少します。 その時点では、それを大きくしても速度は向上しません。