by Hayato Matsuura.

ソートマージ


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

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

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

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

協力してください

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

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

事実

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

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

著者について

Markus Winandの写真

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

彼の本

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

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

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

Amazonで購入
(印刷版のみ)

Do not use offset for pagination

Learn why

Visit my sibling!A lot changed since SQL-92!

Use The Index, Luke のカップは

ステッカー、コースター、本、コーヒーマグ。 学習に必要なものすべて。

今すぐ購入

Connect with Markus Winand

Markus Winand on LinkedInMarkus Winand on XINGMarkus Winand on Twitter
“Use The Index, Luke!” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
法律上の通知 | お問い合わせ | 無保証 | 商標 | プライバシーとGDPR | CC-BY-NC-ND 3.0 license