MySQL は、入れ子ループアルゴリズムまたはその変形を使用してテーブルの結合を実行します。

入れ子ループ join アルゴリズム

単純な入れ子ループ join (NLJ、nested-loop join) アルゴリズムは、ループ内の最初のテーブルから 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 つずつ渡されるため、内側のループで処理されるテーブルは何度も読み取られることになります。

ブロック入れ子ループ join アルゴリズム

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

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 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
    }
  }
}

結合バッファーに格納された各 t1, t2 の組み合わせのサイズを S、バッファー内の組み合わせの数を C とすると、テーブル t3 のスキャン回数は次のようになります。

(S * C)/join_buffer_size + 1

t3 のスキャン回数は、join_buffer_size の値が増大するにつれて減少します。この減少は、join_buffer_size がそれまでの行の組み合わせをすべて保持できるサイズになるまで続きます。その時点で、さらに大きくしても速度は向上しなくなります。