Documentation Home
MySQL 5.6 リファレンスマニュアル
Download this Manual
PDF (US Ltr) - 27.1Mb
PDF (A4) - 27.2Mb
HTML Download (TGZ) - 7.2Mb
HTML Download (Zip) - 7.2Mb


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

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

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

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

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

MySQL 5.6 では、MySQL Server は、内部テーブルへのインデックスアクセスなしの内部結合だけでなく、外部結合と、サブクエリーのフラット化のあとに見られる準結合も実行するために結合バッファーを使用できます。さらに、内部テーブルへのインデックスアクセスがある場合、結合バッファーを効率的に使用できます。

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

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

  • 標準結合バッファーには、各結合オペランドからのカラムが格納されます。B2 が標準結合バッファーである場合、B2 に入れられる各行 r は、B1 からの行 r1 のカラムと、テーブル t2 からの一致する行 r2 の対象のカラムから構成されます。

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

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

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

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

MySQL 5.6.3 現在、optimizer_switch システム変数の block_nested_loop および batched_key_access フラグによって、オプティマイザがどのように Block Nested Loop 結合アルゴリズムと Batched Key Access 結合アルゴリズムを使用するかを制御します。デフォルトで、block_nested_looponbatched_key_accessoff です。セクション8.8.5.2「切り替え可能な最適化の制御」を参照してください。

MySQL 5.6.3 より前では、optimizer_join_cache_level システム変数によって、結合バッファー管理を制御します。この変数の指定可能な値とそれらの意味については、セクション5.1.4「サーバーシステム変数」の説明を参照してください。

準結合戦略については、「セクション8.2.1.18.1「準結合変換によるサブクエリーの最適化」」を参照してください。

8.2.1.14.2 外部結合と準結合の Block Nested Loop アルゴリズム

MySQL 5.6 では、BNL アルゴリズムの元の実装が、外部結合および準結合操作をサポートするように拡張されています。

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

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

MySQL 5.6.3 現在、optimizer_switch システム変数の block_nested_loop フラグによって、オプティマイザが Block Nested Loop アルゴリズムを使用する方法を制御します。デフォルトで、block_nested_loopon です。セクション8.8.5.2「切り替え可能な最適化の制御」を参照してください。

MySQL 5.6.3 より前では、optimizer_join_cache_level システム変数によって、結合バッファー管理を制御します。この変数の指定可能な値とそれらの意味については、セクション5.1.4「サーバーシステム変数」の説明を参照してください。

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

準結合戦略については、「セクション8.2.1.18.1「準結合変換によるサブクエリーの最適化」」を参照してください。

8.2.1.14.3 Batched Key Access 結合

MySQL 5.6.3 では Batched Key Access (BKA) 結合アルゴリズムと呼ばれるテーブルの結合の方法を実装しています。BKA は、2 つめの結合オペランドによって生成されるテーブルへのインデックスアクセスがある場合に適用できます。BNL 結合アルゴリズムと同様、BKA 結合アルゴリズムでは、結合バッファーを使用して、結合操作の最初のオペランドによって生成された行の対象カラムを累積します。次に、BKA アルゴリズムは、バッファー内のすべての行に対し、結合されるテーブルにアクセスするためのキーを構築し、これらのキーをインデックスルックアップのために、データベースエンジンに一括で送信します。キーは、Multi-Range Read (MRR) インタフェース経由で、エンジンに送信されます (セクション8.2.1.13「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 の使用が示されます。


User Comments
Sign Up Login You must be logged in to post a comment.