Join Algorithms

Nested Loop は、最も明白な処理を行います。外側ソースのすべての行について、内側ソースのすべての行と比較します。入れ子ループは、結合条件に等結合述語がない場合にのみ使用されます。

Merge Join はまず、結合された列で入力ソースをソートします。その後、並列に各側をウォークスルーし(事実上、ソートされたソースを1回ずつ通過します)、マッチしたときに行を出力します。一般的に、Merge JoinはNested Loopではn*mではなくn+mのオーダーになります。Merge Joinはデフォルトのアルゴリズムです。

原価情報を使用して、エンジンはフルソートMerge Joinを実行するかどうかの決定を遅らせることもできます。関係する実際の行数に基づいて、エンジンは小さい側のインデックスを作成するか(これはハッシュ結合と同様に実行されます)、リレーションの大きい側のみを部分的にソートするかを選択することができます。

等結合述語を含むJOINもDependent Joinにすることができます。

Sort Based Algorithms

ソートは、Sort ( ORDER BY )、Grouping ( GROUP BY )、DupRemoval ( SELECT DISTINCT )操作の基礎として使用されます。このソートアルゴリズムはマルチパスマージソートであり、すべての結果セットがメモリ上に存在する必要はありませんが、バッファマネージャによって許容される最大量のメモリを使用します。

OFは2つのフェーズで構成されています。最初のフェーズ (「ソート」) は、ソートされていない入力ストリームを受け取り、 1つ以上のソートされた入力ストリームを生成します。各パスは、ソートされていないストリームを可能な限り読み込み、ソートし、新しいストリームとして書き戻します。ストリームはメモリに収まりきらないかもしれないので、ソートされたストリームが多数になるかもしれません。

第2フェーズ(「MERGE」)は、メモリに収まるだけのソートされた入力ストリームから次のバッチを取得する一連のフェーズで構成されます。そして、各ストリームからソートされた順序で次のタプルを繰り返し取得し、ソートされたバッチを新しいソートストリームにマージして出力します。パス後、すべての入力ストリームはドロップされます。このようにして、各パスはソートされたストリームの数を減らします。ストリームが1つだけ残ると、それが最終出力となります。