SQL基礎 結合に関して

SQL実践入門を読んで勉強しておりますが、本日は結合に関して。

クロス結合

要は全行の結合です。こんな結合自体あることを知りませんでした・・・

書いたこともないですが、上記のようにかくとクロス結合されます。

具体的には全ての列が結合されます。

要は
Atable

id| name | dep_id
1 | suzuki  | 10
2 | tanaka | 20

Btable

dep_id| dep_name
10     | 営業
20     | 開発

といったテーブルがあった際結果は下記のようになります。

id | name | dep_id | dep_id | dep_name
1 | suzuki  | 10     | 10  | 営業
1 | suzuki  | 10     | 20  | 開発
2 | tanaka | 20     | 10  | 営業
2 | tanaka | 20     |  20 | 開発

一般的にこういった結合を使うことはないので、ほぼお目にかからないでしょう。

また非常に高コストのようです。

内部結合

id | name |  dep_name
1 | suzuki  | 営業
2 | tanaka | 開発

一般的な結合ですね。またクロス結合の部分集合という見方もできます。

また内部結合は下記のようにサブクエリで代替できます。

たしかに・・・あまり考えたことはありませんでしたが、一緒ですね。

外部結合

• 左外部結合(右外部結合)
• 完全外部結合

これは片方のテーブルにNULLがあったときにどちらを優先するかですね。NULLがなければINNER JOINと変わりません。最も私はLEFT JOIN以外はほとんど使いませんが・・・

結合のアルゴリズムとパフォーマンス

ここでは結合のロジックについて書かせていただきます。

NestedLoops

一番頻繁にみられるアルゴリズムのようです。MySQLなどはこれしかないようですね。

例えばAtableとBtableをスキャンするときに

1. 結合対象となるAtableを一行ずつループしながらスキャンする
2. このテーブルを駆動表または外部表と呼ぶ。もう一方のテーブルを内部表(ここでいうBtable)
3. この動作を駆動表のすべての行に対して実行する

このような仕組みになっているのでアクセスされる行数はAtableのレコード数 × Btableのテーブル数になります。

特徴としては

• 単純で理解しやすい
• HashやMergeと比べてあまりメモリを消費しない
• どのDBMSでも必ずサポートしていること

がポイントです。

また検索効率を上げるには

• 駆動表をできれば小さくする
• 内部表のループを小さくするためにキーに対してインデックスが張られていること

が大切になります。

ただ、内部表のヒット数が大きくなるとやはり計算量が増えますので、検索時間は長くなります。

Hash

Hashによる結合動作

1. 小さいテーブルをスキャンする
2. ハッシュテーブルを生成する
3. マッチングする別テーブルを見に行く

この説明読むよりもSQL実践入門の図を見たほうが早いでしょう・・・(汗)

特徴

• 結合テーブルからハッシュテーブルを作るためにNestedLoopsに比べるとメモリを多く消費消費する
• メモリ内にハッシュテーブルが収まらないとストレージを使用するため、遅延が発生する
• 出力となるハッシュ値は入力値の順序性を保存しないため、等値結合でしか使用しない

Hashが有効なケース

• NestedLoopで適切な駆動表(十分に小さいテーブル)が存在しない場合
• NestedLoopの駆動表として小さいテーブルは指定できるが、内部表のヒット件数が存在しない場合
• NestedLoopの内部表にインデックスが存在しない場合

大まかにいうとNestedLoopが効率的に動作しない場合に用いられます。

SortMerge

Hashと並んでもう一つの選択肢となるのが、SortMergeというアルゴリズムです。

これは結合対象のテーブルをそれぞれの結合キーでソートし、一致する結合キーを見つけたらそれを結果セットに含めるというものです。

1. 片方のテーブルの結合キーをソート
2. もう片方のテーブルの結合キーをソート
3. マッチングさせる

特徴

• 対象テーブルをどちらもソートするため、メモリ消費が最大
• Hashと違い、等値結合だけでなく不等号を使った結合にも利用できる
• 原理的にはテーブルが結合キーでソートされていれば、ソートをスキップできる

かなり例外的なケースで使われるもののようですね。