by Hayato Matsuura.

ソートマージ


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

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

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

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

協力してください

この記事が気に入ったら、私の書いた本「SQLパフォーマンス詳解」や私によるトレーニングもきっと気にいるはず。

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

事実

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

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

著者について

Markus Winandの写真

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

彼の本

カバー『SQLパフォーマンス詳解』

核心をわかりやすく 解説。

Markusから購入します
(送料無料+PDF)

Amazonで購入
(印刷版のみ)

“Use The Index, Luke!” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
法律上の通知 | 接触 | 無保証 | 商標 | Privacy | CC-BY-NC-ND 3.0 license