Documentation Home
MySQL 8.0 リファレンスマニュアル
Download this Manual
PDF (US Ltr) - 36.1Mb
PDF (A4) - 36.2Mb


MySQL 8.0 リファレンスマニュアル  /  ...  /  Block Nested Loop 結合と Batched Key Access 結合

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

8.2.1.12 Block Nested Loop 結合と Batched Key Access 結合

MySQL では、結合テーブルと結合バッファの両方へのインデックスアクセスを使用するバッチキーアクセス (BKA) 結合アルゴリズムを使用できます。 BKA アルゴリズムでは、内部結合、外部結合、およびネストされた外部結合を含む準結合操作がサポートされています。 BKA には、テーブルスキャンの効率性の向上による結合パフォーマンスの改善というメリットもあります。 また、以前は内部結合にのみ使用されていた Block Nested-Loop (BNL) 結合アルゴリズムが拡張され、ネストされた外部結合を含む外部結合および準結合操作に使用できます。

次のセクションでは、元の BNL アルゴリズムの拡張の基礎にある結合バッファー管理、拡張 BNL アルゴリズム、および BKA アルゴリズムについて説明します。 準結合戦略の詳細は、セクション8.2.2.1「準結合変換による IN および EXISTS サブクエリー述語の最適化」 を参照してください

Block Nested Loop および Batched Key Access アルゴリズムの結合バッファー管理

MySQL では、結合バッファを使用して、内部テーブルへのインデックスアクセスなしで内部結合のみでなく、サブクエリーのフラット化後に表示される外部結合および準結合も実行できます。 さらに、内部テーブルへのインデックスアクセスがある場合、結合バッファーを効率的に使用できます。

結合バッファー管理コードは、目的の行カラムの値を格納する際に、結合バッファー領域を少し効率的に利用します。行カラムの値が NULL の場合に行カラムにバッファー内の追加バイトを割り当てず、VARCHAR 型の値には最小数のバイトが割り当てられます。

コードでは、標準と増分の 2 つの種類のバッファーをサポートします。 結合テーブル t1t2 に結合バッファー B1 が使用されており、この操作の結果が結合バッファー B2 を使用して、テーブル t3 と結合されるとします。

  • 標準結合バッファーには、各結合オペランドからのカラムが格納されます。 B2 が通常の結合バッファの場合、B2 に配置される各行 r は、B1 の行 r1 のカラムと、テーブル t3 の一致する行 r2 の興味深いカラムで構成されます。

  • 増分結合バッファーには、2 つめの結合オペランドによって生成されるテーブルの行からのカラムのみが格納されます。 つまり、それは 1 つめのオペランドバッファーからの行の増分になります。 B2 が増分結合バッファーである場合、それには、B1 からの行 r1 へのリンクとともに、行 r2 の対象のカラムが格納されます。

増分結合バッファーは常に、前の結合操作からの結合バッファーに相対的な増分になるため、最初の結合操作からのバッファーは常に標準バッファーになります。 直前の例では、テーブル t1 および t2 を結合するために使用されるバッファー B1 は標準バッファーである必要があります。

結合操作に使用される増分バッファーの各行には、結合されるテーブルからの行の対象カラムのみが格納されます。 これらのカラムには、最初の結合オペランドによって生成されたテーブルからの一致する行の対象カラムへの参照が追加されます。 増分バッファー内の複数の行から、カラムが前の結合バッファーに格納されている同じ行 r を参照できます。ただし、これらのすべての行が行 r に一致する場合にかぎります。

増分バッファーにより、前の結合操作で使用されたバッファーからのカラムのコピーの頻度を少なくできます。 これにより、一般に、最初の結合オペランドによって生成された行が 2 つめの結合オペランドによって生成される複数の行に一致する可能性があるため、バッファー領域が節約されます。 最初のオペランドからの行のコピーを何回も行う必要がありません。 さらに、増分バッファーにより、コピー時間の短縮のため、処理時間も節約されます。

MySQL 8.0 では、optimizer_switch システム変数の block_nested_loop フラグは次のように機能します:

  • MySQL 8.0.20 より前は、オプティマイザが Block Nested Loop 結合アルゴリズムを使用する方法を制御していました。

  • MySQL 8.0.18 以降では、ハッシュ結合の使用も制御します (セクション8.2.1.4「ハッシュ結合の最適化」 を参照)。

  • MySQL 8.0.20 以降、このフラグはハッシュ結合のみを制御し、ブロックネストループアルゴリズムはサポートされなくなりました。

batched_key_access フラグは、オプティマイザがバッチキーアクセス結合アルゴリズムを使用する方法を制御します。

デフォルトで、block_nested_looponbatched_key_accessoff です。 セクション8.9.2「切り替え可能な最適化」を参照してください。 オプティマイザヒントも適用できます。ブロックネストループおよびバッチキーアクセスアルゴリズムのオプティマイザヒント を参照してください。

準結合戦略の詳細は、セクション8.2.2.1「準結合変換による IN および EXISTS サブクエリー述語の最適化」 を参照してください

外部結合および準結合のブロックネストループアルゴリズム

MySQL BNL アルゴリズムの元の実装は、外部結合および準結合操作をサポートするように拡張されました (後でハッシュ結合アルゴリズムに置き換えられました。セクション8.2.1.4「ハッシュ結合の最適化」 を参照)。

結合バッファーを使用して、これらの操作が実行されると、バッファーに入れられた各行に一致フラグが付加されます。

結合バッファーを使用して、外部結合操作が実行された場合、2 つめのオペランドによって生成されたテーブルの各行で、結合バッファー内の各行に対する一致がチェックされます。 一致が見つかると、新しく拡張された行が形成され (元の行に 2 つめのオペランドからのカラムを追加)、残りの結合操作によるさらなる拡張のために送られます。 さらに、バッファー内の一致した行の一致フラグが有効にされます。 結合されるテーブル内のすべての行が調査されたあとに、結合バッファーがスキャンされます。 有効にされた一致フラグがないバッファーからの各行は、NULL の補完 (2 つめのオペランドの各カラムの NULL 値) によって拡張され、残りの結合操作によるさらなる拡張のために送られます。

MySQL 8.0 では、optimizer_switch システム変数の block_nested_loop フラグは次のように機能します:

  • MySQL 8.0.20 より前は、オプティマイザが Block Nested Loop 結合アルゴリズムを使用する方法を制御していました。

  • MySQL 8.0.18 以降では、ハッシュ結合の使用も制御します (セクション8.2.1.4「ハッシュ結合の最適化」 を参照)。

  • MySQL 8.0.20 以降、このフラグはハッシュ結合のみを制御し、ブロックネストループアルゴリズムはサポートされなくなりました。

詳しくはセクション8.9.2「切り替え可能な最適化」,をご覧ください。 オプティマイザヒントも適用できます。ブロックネストループおよびバッチキーアクセスアルゴリズムのオプティマイザヒント を参照してください。

EXPLAIN 出力で、Extra 値に Using join buffer (Block Nested Loop) が含まれ、type 値が ALLindex、または range の場合に、テーブルへの BNL の使用が示されます。

準結合戦略の詳細は、セクション8.2.2.1「準結合変換による IN および EXISTS サブクエリー述語の最適化」 を参照してください

Batched Key Access 結合

MySQL では Batched Key Access (BKA) 結合アルゴリズムと呼ばれるテーブルの結合の方法を実装しています。 BKA は、2 つめの結合オペランドによって生成されるテーブルへのインデックスアクセスがある場合に適用できます。 BNL 結合アルゴリズムと同様、BKA 結合アルゴリズムでは、結合バッファーを使用して、結合操作の最初のオペランドによって生成された行の対象カラムを累積します。 次に、BKA アルゴリズムは、バッファー内のすべての行に対し、結合されるテーブルにアクセスするためのキーを構築し、これらのキーをインデックスルックアップのために、データベースエンジンに一括で送信します。 キーは、Multi-Range Read (MRR) インタフェース経由で、エンジンに送信されます (セクション8.2.1.11「Multi-Range Read の最適化」を参照してください)。 キーの送信後、MRR エンジン関数は最適な方法で、インデックス内のルックアップを実行し、これらのキーによって見つかった結合されたテーブルの行をフェッチし、BKA 結合アルゴリズムに一致する行の提供を開始します。 一致する各行は結合バッファー内の行への参照が組み合わされます。

BKA が使用される場合、join_buffer_size の値によって、ストレージエンジンへの個々のリクエストでのキーのバッチの大きさが定義されます。 バッファが大きいほど、結合操作の右側のテーブルへの順次アクセスが多くなり、パフォーマンスが大幅に向上する可能性があります。

BKA を使用するには、optimizer_switch システム変数の batched_key_access フラグが on に設定されている必要があります。 BKA では MRR を使用するため、mrr フラグも on に設定されている必要があります。 現在、MRR のコスト見積もりはきわめて悲観的です。 したがって、BKA を使用するには、mrr_cost_basedoff にする必要もあります。 次の設定によって、BKA が有効になります。

mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

MRR 関数が実行される 2 つのシナリオがあります。

  • 最初のシナリオは、InnoDBMyISAM などの従来のディスクベースのストレージエンジンで使用されます。 これらのエンジンでは通常、結合バッファーからのすべての行のキーが一度に MRR インタフェースに送信されます。 エンジン固有の MRR 関数は、送信されたキーのインデックスルックアップを実行し、それらから行 ID (または主キー) を取得して、BKA アルゴリズムからのリクエストによって、これらの選択されたすべての行 ID の行を 1 つずつフェッチします。 各行は、結合バッファー内の一致した行へのアクセスを可能にするアソシエーション参照とともに返されます。 行は MRR 関数によって最適な方法でフェッチされます。それらは、行 ID (主キー) 順でフェッチされます。 これにより、読み取りがランダムな順序ではなく、ディスク順になるため、パフォーマンスが向上します。

  • 2 つめのシナリオは、NDB などのリモートストレージエンジンで使用されます。 結合バッファーからの行の一部のキーのパッケージが、それらのアソシエーションとともに、MySQL Server (SQL ノード) によって、MySQL Cluster データノードに送信されます。 返信で、SQL ノードは、対応するアソシエーションが組み合わされた一致する行のパッケージ (または複数のパッケージ) を受け取ります。 BKA 結合アルゴリズムでは、これらの行を取得し、新しく結合された行を構築します。 次に、新しいキーセットがデータノードに送信され、返されたパッケージからの行が新しい結合された行の構築に使用されます。 このプロセスは、結合バッファーからの最後のキーがデータノードに送信され、SQL ノードがこれらのキーに一致するすべての行を受け取り、結合するまで、続行されます。 これにより、SQL ノードによってデータノードに送信されるキーを含むパッケージが少なくなることは、結合操作を実行するために、それとデータノード間のラウンドトリップが少なくなることを意味するため、パフォーマンスが向上します。

最初のシナリオでは、結合バッファーの一部がインデックスルックアップによって選択され、MRR 関数へのパラメータとして渡される行 ID (主キー) を格納するために予約されます。

結合バッファーからの行に対して構築されるキーを格納するための特別なバッファーはありません。 代わりに、バッファー内の次の行のキーを構築する関数が、MRR 関数へのパラメータとして渡されます。

EXPLAIN 出力で、Extra 値に Using join buffer (Batched Key Access) が含まれ、type 値が ref または eq_ref の場合に、テーブルへの BKA の使用が示されます。

ブロックネストループおよびバッチキーアクセスアルゴリズムのオプティマイザヒント

BNL および BKA アルゴリズムのセッション全体でのオプティマイザの使用を制御するために optimizer_switch システム変数を使用することに加えて、MySQL はオプティマイザヒントをサポートして、ステートメントごとにオプティマイザに影響を与えます。 セクション8.9.3「オプティマイザヒント」を参照してください。

BNL または BKA ヒントを使用して外部結合の内部テーブルの結合バッファリングを有効にするには、外部結合のすべての内部テーブルに対して結合バッファリングを有効にする必要があります。