このページは機械翻訳したものです。

8.2.1.7 Nested Loop 結合アルゴリズム

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

• Nested Loop 結合アルゴリズム

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

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

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

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

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

• join_buffer_size システム変数は、クエリーの処理に使用される各結合バッファのサイズを決定します。

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

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

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