SQL実践入門第6章を読んだ

機能から見た結合の種類

どのような種類の結合がどういう動作を行うかの整理。軸となるのは内部結合と外部結合の違い。 結合によって生成される結果を基準に3つのタイプに分類できる（生成結果による分類）

クロス結合(cross join)

  • 結合対象となる2つのテーブルのレコードから、可能な全ての組み合わせを網羅する演算
  • 他の2つの結合（内部結合と外部結合）の母体となっている（内部結合と外部結合はクロス結合を基準にして考えると理解しやすくなる）
  • クロス結合を実務で使う機会はほとんどない（確かに。。。存在すら知らなかった）
    • 実際にこういう結果を求めたいケースがない
    • 全ての組み合わせを網羅するので非常に高コスト（実行時間が長くハードウェアリソースも多く消費する）

内部結合(inner join)

  • 一番よく使われる結合
  • 内部結合の結果は、クロス結合の結果の一部（部分集合の関係）となっている
    • 「内部」とは直積（Aテーブルの要素とBテーブルの要素の全ての組み合わせ）の部分集合という意味

外部結合(outer join)

  • 内部結合の次によく使われる
  • 「内部」「外部」という名前が示唆するように、内部結合とは排他的な演算
    • 単純に解釈すると、「外部結合は直積の部分集合にならない」という意味（実際は常に部分集合にならない訳ではなく、データの状態によってはそういうこともあり得るという程度）
外部結合の動作

  • 左外部結合(left outer join)、右外部結合(right outer join)

    • 左外部結合と右外部結合は実質的に同じ機能を持っている
      • マスタとなるテーブルを左に書くなら左外部結合、右に書くなら右外部結合
    • マスタ側のテーブルだけに存在するキーがあった場合そのキーを削除せず、結果を保存するように動作する
      • キーの値を全て網羅する場合に多用される（網羅したいキーが存在するテーブルをマスタにする）

  • 完全外部結合(full outer join)

    • 結合するどちらのテーブルのキーも優先する（どちらか片方のテーブルだけに存在するキーがあった場合、そのキーは削除せず結果を保存するように動作する）

外部結合と内部結合の違い

  • 内部結合

    • 完全にクロス結合（直積）に包含される形になる（直積の部分集合）
    • 直積の部分集合なので、当然NULLを生成することはない

  • 外部結合

    • マスタ側のテーブルの情報を保存するように動作するため、マスタ側のキーと一致するキーがもう一方のテーブルに存在しなかった場合はNULLを生成する。
    • NULLが生成された行はクロス結合（テーブルAとテーブルBの直積）のどのレコードとも被らない（直積の部分集合となり得ない）ので、この特徴を指して「外部に」はみ出していることから外部結合と呼ばれる

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

結合を行う場合に内部で選択されるアルゴリズムを基準にして結合を考える

  • オプティマイザが選択可能な結合アルゴリズムは大きく3つ

    • Nested Loops
    • Hash
    • Sort Merge

  • 最も頻繁に見るのはNested Loops、次いでHash、最後のSort Mergeは前者2つと比べると重要性が一段下がる

Nested Loops

  • 入れ子のループを使うアルゴリズム

  • 結合対象となるテーブルを１行ずつループしながらスキャンする。このテーブルを駆動表（driving table）または外部表（outer table）という。もう一方のテーブルは内部表（inner table）という。

  • 駆動表の１行について内部表を１行ずつスキャンして、結合条件に合致すればそれを返却する
  • この動作を駆動表の全ての行に対して繰り返す
Nested Loopsの特徴
  • 結合対象のテーブルの行数をそれぞれR(A)、R(B)とすると、アクセスされる行数はR(A)*R(B)となり、Nested Loopsの実行時間はこの行数に比例する
  • 1つのステップで処理する行数が少ないので、HashやSort Mergeに比べてあまりメモリを消費しない
  • どのDBMSも必ずサポートしている
駆動表の重要性

Nested Loopsの性能を改善するには「内部表の結合キーの列にインデックスが存在する状態」で「駆動表に小さなテーブルを選ぶ」

  • 内部表の結合キーの列にインデックスが存在すること
    • インデックスを辿ることによって、DBMSは駆動表の１行について内部表をループする必要がなくなる（内部表のループをある程度スキップできるようになる）
      • より理想的なケースでは、駆動表のレコード１行に対して内部表のレコード１行が１対１で対応していれば、内部表のインデックスを辿ることでループすることなく１行を特定できるので、完全にループを省略できる
      • 逆に言えば、内部表が結合キーで一意にならないと内部ループが残る

つまり、

  • 内部表を大きくする（インデックスによるループスキップの効果が大きくなるから）
  • 「駆動表の小さなNested Loops」＋ 「内部表の結合キーにインデックス」

この組み合わせはSQLチューニングの基本。

物理ERモデルとインデックスの設計を行う際は、どのテーブルを内部表にして、どの結合キーにインデックスを作成しておくべきか設計の段階から考えながら行う必要がある（まじか...）

Hash

  • 入力に対してなるべく一意性と一様性を持った値を出力する、いわゆるハッシュ関数を使うアルゴリズム

  • 小さい方のテーブルをスキャンして、結合キーに対してハッシュ関数を適用してハッシュ値に変換する

  • 大きい方のテーブルをスキャンして、結合キーがそのハッシュテーブルに存在するか調べる
Hashの特徴
  • 結合キーからハッシュテーブルを作るため、Nested Loopsに比べるとメモリを多く消費する
    • メモリ内にハッシュテーブルが収まらないとストレージを使用することになり遅延が発生する（TEMP落ち）
  • 出力となるハッシュ値は入力値の順序性を保存しないため、等値結合でしか使用できない
Hashが有効なケース
  • Nested Loopsで適切な駆動表（相対的に十分に小さいテーブル）が存在しない場合
  • Nested Loopsで、内部表のヒット件数が多い場合（ループの絶対数があまり少なくならない）
  • Nested Loopsの内部表にインデックスが存在しない場合
  • まとめると、Nested Loopsが効率的に動作しない場合の次善の策がHashということ
注意すべきHashのトレードオフ
  • ハッシュテーブルを作ってワーキングメモリに保持する必要があるため、Nested Loopsに比べて消費するメモリ量が多い
  • 結合する両方のテーブルのレコードを全権読み込む必要があるため、スキャンに要する時間も考慮する必要がある

Sort Merge

  • 結合対象のテーブルそれぞれを結合キーでソートし、一致する結合キーを見つけたらそれを結果セットに含めるアルゴリズム
  • 単にMerge、Merge Joinと呼ばれることもある
Sort Mergeの特徴
  • 対象テーブルをどちらもソートする必要があるためNested Loopsよりも多くのメモリを消費する
  • Hashと違い、等値条件だけでなく不等号を使った結合にも利用できる
  • 原理的にはテーブルがソート済みであればソートをスキップできる（ただしSQLではテーブルの行の物理的配置は意識しないことになっているので、恩恵を受けられるとしてもそれは実装依存）
  • テーブルをソートするため、片方のテーブルを全てスキャンしたところで結合を終了できる
Sort Mergeが有効なケース
  • テーブルのソートをスキップできるかなり例外的なケースでは考慮に値するが、それ以外の場合はまずNested LoopsとHashが優先的な選択肢となる

メモ

  • 結合はアルゴリズムが複数あるために実行計画変動を起こしやすい。性能変動リスクを防止するには「結合を代替手段によって回避する」ことが重要な戦略になり、このテーマについては本の後半で触れていくことになるらしい

感想

  • 実行計画でどんなアルゴリズムが選択されるのかこれから少しずつ意識するようにしていきたい。
  • 結合の種類を整理できたのがかなりよかった。