3つの主要なSQL ServerアルゴリズムのI/Oコストの簡単な分析

1. ネストループ結合

アルゴリズム：

考え方は非常に単純かつ直接的です。関係 R の各タプル r を、JOIN 条件のフィールドで関係 S の各タプル s と直接比較し、条件を満たすタプルをフィルター処理します。疑似コードで記述すると:

料金：

結合されたテーブルが内部層または外部層に配置される順序は、ディスク I/O コストに非常に重要な影響を及ぼします。 CPUオーバーヘッドは比較的小さく、主にタプルがメモリに読み込まれた後のオーバーヘッド（インメモリ）はO（n * m）です。

I/Oコストについては、ページ単位の前提によれば、I/Oコスト = M + M * N、

これを翻訳すると、I/O オーバーヘッド = M ページの読み取りの I/O オーバーヘッド + N ページを M 回読み取る I/O オーバーヘッドとなります。

2. ソートマージ結合

ネストされたループは、両方のセットが大きい場合には一般的に非効率的ですが、この場合にはソートマージの方がはるかに効率的です。特に、2 つのセットの JOIN フィールドにクラスター化インデックスが存在する場合、ソートマージは最高のパフォーマンスを実現します。

アルゴリズム：

基本的な考え方も非常にシンプルです (データ構造のマージソートを確認してください)。主な手順は 2 つあります。

a. JOINフィールドで並べ替える

b. 2 つのソートされたセットをマージしてソートし、各ソースからデータ列を取得して比較します (JOIN フィールドに重複する値があるかどうかに基づいて特別な「パーティション分割」が必要です)

コスト: (主に I/O オーバーヘッド)

ソートマージのコストに影響する要因は 2 つあります。JOIN フィールドがソートされているかどうかと、JOIN フィールドに重複する値がいくつあるかです。

◆最良の場合（両方の列がソートされ、少なくとも 1 つの列に重複する値がない場合）：O（n + m）各セットのスキャンは 1 回のみ必要です。（mとnの両方がインデックスを使用できると良いでしょう）

◆最悪の場合（両方の列がソートされておらず、両方の列のすべての値が同じ）：O（n * log n + m * log m + n * m）2回のソートとすべてのタプル間の1回の直積

3. ハッシュ結合

ハッシュ結合は、2 つの列に重複した値がある場合のソートマージ (パーティション分割) の処理の考え方と本質的に似ています。ただし、違いもあります。ハッシュ結合はハッシュによってパーティションを結合し（各バケットがパーティション）、ソートマージはソートによってパーティションを結合します（各重複値がパーティションです）。

ハッシュ結合と上記の 2 つのアルゴリズムの最大の違いは、ハッシュ結合が等価結合にのみ適用できるという大きな制限でもあることに留意する価値があります。これは主に、ハッシュ関数とそのバケットの決定論と無秩序によるものです。

アルゴリズム：

基本的なハッシュ結合アルゴリズムは、次の 2 つのステップで構成されます。

ネストされたループと同じですが、ビルド入力が実行プランの上部にあり、プローブ入力が下部にある点が異なります。

ハッシュ結合操作は、ビルドフェーズとプローブフェーズの 2 つのフェーズで完了します。

a.入力フェーズの構築: JOIN フィールドに基づいて、ハッシュ関数 h2 を使用して、小さいセット S のメモリ内ハッシュテーブルを構築します。同じキー値は、リンクリストを使用してバケットに結合されます。

b.プローブ入力フェーズ: 結合を完了するために、より大きな R セットのハッシュテーブルをチェックします。

料金：

注目すべきは、大きなセット R 内の各タプル r について、ハッシュバケット内の r に対応するバケット内の各タプルを r と比較する必要があることです。これは、アルゴリズムの中で最も時間のかかる部分でもあります。

CPU コストは O (m + n * b) です。ここで、b はバケットあたりのタプルの平均数です。

要約:

3 つの結合方法にはすべて 2 つの入力があり、最適化の基本原則は次のとおりです。