ソートマージ


Applies to
DB2Yes
MySQLNo
OracleYes
PostgreSQLYes
SQL ServerYes

ソートマージ結合は、ファスナーのように2つのソート済みリストを 組み合わせる方法です。結合のどちら側も結合述語によって並べ替えされて いる必要があります。

ソートマージ結合では、ハッシュ結合と同じ、つまり候補となる 全てのレコードを一度に読み込むため、それぞれの条件に作られた インデックスが必要になります。ほぼ全てがハッシュ結合と同じですが、 1つだけソートマージ結合に特有なことがあります。それは、完全な 対称性があることです。結合の順序は全く影響を与えず、パフォーマンスにも 関係ありません。この特性は、外部結合を行う際に非常に便利なものです。 他のアルゴリズムでは、外部結合の方向(左結合か右結合か)は、結合の 順序に関係しますが、ソートマージ結合では関係ありません。それどころか、 ソートマージ結合では左外部結合と右外部結合を同時に実行してしまう、 つまりいわゆる完全外部結合が可能です。次の アニメーションが動作を表しています。

図4.1 FULL OUTER JOINを実行するソートマージ結合


ソートマージ結合は、入力が並べ替え済みの時は非常にパフォーマンスが 良いですが、結合の両側を並べ替えるのは非常にコストの大きい処理なので、 あまり使われません。ハッシュ結合では、事前に処理が必要なのは片側のみです。

このウェブサイトにぴったりのカップは僕たちのショップにあります。
#見た目もいい感じだし、ここでの僕の仕事を支えてくれています

ソートマージ結合が威力を発揮するのは、入力が既に並べ替え済みの 場合です。これは、並べ替えの処理を完全になくしてしまうために、インデックスの 順序を利用できると可能になります。第6章, 「ソートとグルーピングで、そのコンセプトを詳細に説明 しています。ただ、ハッシュ結合アルゴリズムの方が多くの場合は優れています。

Factbox

  • ソートマージ結合は、結合述語にインデックスは 必要ありません。

  • MySQLはソートマージ結合をサポートしていません。

Photo of Markus Winand
Markus Winand氏は、開発者がSQLパフォーマンスを改善するお手伝いをしています。 彼は、SQL Performance Explainedの 著者でもあり、出張トレーニングhttp://winand.at/での リモート講義も 行っています。