ハッシュ結合について

ハッシュ結合には、ビルド入力とプローブ入力という 2 つの入力があります。クエリ オプティマイザでは、2 つの入力のうち小さい方がビルド入力になるように、ロールを割り当てます。

ハッシュ結合は多種多様な集合の照合操作に使用されます。ハッシュ結合を使用できるのは、Inner Join、Left Outer Join、Right Outer Join、Full Outer Join、Left Semi Join、Right Semi Join、Intersect、Union、Diff です。また、ハッシュ結合の派生形では、重複の削除やグループ化を行うことができます (SUM(salary) GROUP BY department など)。このような変更では、ビルドとプローブの両方のロールに 1 つの入力しか使用しません。

ここでは、インメモリ ハッシュ結合、猶予ハッシュ結合、再帰的ハッシュ結合など、さまざまなハッシュ結合について説明します。

インメモリ ハッシュ結合

このハッシュ結合では、まずビルド入力全体がスキャンまたは計算され、メモリ内にハッシュ テーブルが作成されます。各行はハッシュ キー用に計算されたハッシュ値に従ってハッシュ バケットに挿入されます。ビルド入力全体が使用可能なメモリを超えない場合、すべての行をハッシュ テーブルに挿入できます。このビルド フェーズの後、プローブ フェーズになります。プローブ入力全体が 1 回に 1 行ずつスキャンまたは計算されます。プローブ行ごとにハッシュ キーの値が計算され、対応するハッシュ バケットがスキャンされて、照合が行われます。

猶予ハッシュ結合

ビルド入力がメモリに入りきらない場合、ハッシュ結合が複数のステップで進められます。これを、猶予ハッシュ結合と呼びます。各ステップにはビルド フェーズとプローブ フェーズがあります。まず、ビルド入力とプローブ入力全体が使用され、複数のファイルにパーティション分割されます (ハッシュ キーにハッシュ関数を使用)。ハッシュ キーにハッシュ関数を使用すると、2 つの結合レコードが同じファイルの組に含まれることが保証されます。したがって、2 つの大規模な入力を結合する作業は、小規模な同一作業の複数のインスタンスになります。その後、ハッシュ結合がパーティション分割されたファイルの組それぞれに適用されます。

再帰的ハッシュ結合

ビルド入力が大規模なので、標準の外部マージの入力に複数のマージ レベルが必要な場合、複数のパーティション分割ステップと複数のパーティション分割レベルが必要です。パーティションの一部だけが大規模な場合、その特定のパーティションだけに使用するパーティション分割ステップが追加されます。すべてのパーティション分割ステップをできるだけ高速にするには、大規模な非同期 I/O 操作を使用し、1 つのスレッドで複数のディスク ドライブを集中的に使用できるようにします。

ms189313.note(ja-jp,SQL.90).gifメモ :
ビルド入力がわずかに使用可能なメモリを超える場合は、インメモリ ハッシュ結合と猶予ハッシュ結合の要素が 1 つのステップに組み合わされ、ハイブリッド ハッシュ結合が作成されます。

最適化時にどのハッシュ結合を使用するかを、常に決定できるわけではありません。このため SQL Server では、始めにインメモリ ハッシュ結合が使用され、ビルド入力のサイズに従って、徐々に猶予ハッシュ結合と再帰的ハッシュ結合に移行します。

オプティマイザが、2 つの入力のうち、ビルド入力になるべき小さい方を誤って予想した場合、ビルド ロールとプローブ ロールは動的に逆転されます。ハッシュ結合では、必ず小さい方のオーバーフロー ファイルをビルド入力として使用します。この技法はロール逆転と呼ばれます。ロール逆転は、ディスクへの書き込みが少なくとも 1 回行われた後にハッシュ結合の内部で行われます。

ms189313.note(ja-jp,SQL.90).gifメモ :
ロール逆転は、クエリ ヒントやクエリの構造とは無関係に行われます。ロール逆転はクエリ プランには示されません。ロール逆転が行われてもユーザーには認識されません。

ハッシュの保留

猶予ハッシュ結合または再帰的ハッシュ結合を説明するために、ハッシュの保留という用語が使用されることがあります。

ms189313.note(ja-jp,SQL.90).gifメモ :
再帰的ハッシュ結合またはハッシュの保留により、サーバーのパフォーマンスが低下します。トレース内に多数の Hash Warning イベントを確認した場合は、結合対象の列の統計を更新します。

ハッシュの保留の詳細については、「Hash Warning イベント クラス」を参照してください。

参照

概念

結合の基礎
論理操作と物理操作のリファレンス

その他の技術情報

クエリ ヒント (Transact-SQL)
クエリの分析

ヘルプおよび情報

SQL Server 2005 の参考資料の入手