前回の続きで第六章の主要点をまとめていきたいと思います。 (※具体的なテーブル表など割愛させてもらうことが多いです)

今回は「結合(JOIN)」についてです。

正規化というプロセスを踏むために、必然的にRDBではテーブルが増えることになります。散在するデータを得るため、さまざまな種類の結合を利用するということになります。

結合の際にもパフォーマンスは重要なポイントになってきます。

「Nested Loops」というアルゴリズムを覚えておきましょう。

DBMS内でどういったアルゴリズムが使用されているか意識できるようになれば、応用も熟していけるでしょう。

それで順番にみていきましょう。

結合の種類

クロス結合
内部結合
外部結合
自己結合
等値結合 / 非等値結合
自然結合

ここでは主に上から3つをみていきます。

クロス結合(cross join)

名前はなんとなく聞いたことがあるかもしれませんが、クロス結合は業務ではほとんど使用したことがないかもしれません。

クロス結合は、数学的には直積やデカルト積と呼ばれる演算です。 2つのテーブルのレコードから、可能な全ての組み合わせを網羅する演算になります。

なので、このような2つのテーブルでは、「6×4 = 24」24行が結果として出力されます。

Employees(社員)テーブル

emp_id	emp_name	dept_id
001	石田	10
002	小笠原	11
003	夏目	11
004	米田	12
005	山田	12
006	岩瀬	12

Departments(部署)テーブル

emp_id	emp_name
10	総務
11	人事
12	開発
13	営業

SELECT * FROM Employees
CROSS JOIN Departments;

このクエリを実行するとわかりますが、この結果を求めたいという時はほぼないでしょうし、非常にコストのかかる演算になってしまいます。

ただし、この結合をわかっていれば内部結合や外部結合が理解しやすくなるでしょう。

内部結合 (inner join)

さきほどの2つのテーブルにたいして内部結合を行うにはこうします。

SELECT E.emp_id, E.emp_name, E.dept_id, D.dept_name
FROM Employees E 
INNER JOIN Departments D
ON E.dept_id = D.dept_id;

内部とは「直積の部分集合」という意味です。内部結合ではサブクエリで代替可能ですが、基本的に結合で記述できる場合は結合を選択すべきです。

外部結合 (outer join)

外部とは「直積の部分集合にならない」という意味です。常に部分集合にならないというわけではありません。

外部結合には3種類あります。

左外部結合
右外部結合
完全外部結合

マスタとなるテーブルを左に書くなら左外部結合、右に書くなら右外部結合です。マスタにのみあるキーがあった場合は、出力されることになります。

f:id:o21o21:20180318140855p:plain

自己結合 (self join)

自己結合は、演算の対象になにを使うかという点が問題になってきます。

一般的に同じテーブルに別名をつけて、 (例: Employeesというテーブルに対してSQL内で、AS E1, AS E2 などとする) それらをあたかも別テーブルのようにして扱います。

アルゴリズム

オプティマイザがどのアルゴリズムを使用するかは、データサイズや結合キーの分散といった要因にも依存してきますが、最も頻繁に確認できるのが「Nested Loops」でしょう。

その他にも、

Hash
Sort Merge

などがあります。これらのアルゴリズムは多くのDBMSでサポートされているかと思います。確認してみたら、「そんなアルゴリズムは使用されていない！」って方も、派生系などがありますので、よくドキュメントを参考にしてみてください。要は、基本的なところでは似ているかと思います。

Nested Loops

結合は常に1度につき2つのテーブルしか結合しません。

tabale_Aとtable_Bとの結合だとして、

結合対象となるtable_A(駆動表or外部表)を1行ずつループしながらスキャンする。
table_B(内部表)を1行ずつスキャンして、結合条件に合致したものを返却する。

この繰り返しです。

それぞれのテーブルの行数をR(A), R(B)とします。アクセスされる行数は、R(A) × R(B)となります。これはNested Loopsの実行時間はこの行数に比例するということになります。

また、Hashなどと比べて、1ステップで処理する行数が少ないためあまりメモリを消費しません。

さて一見するとこれならどちらでもいいではないか(R(A) × R(B)とR(B) × R(A))と思われますが、そんなことはありません。駆動表が小さければNested Loopsの性能が良くなりますが、内部表の結合キーの列にインデックスが存在することという前提があります。内部表のインデックスをたどることでループすることなく1行を特定できます。この場合のアクセス行数は、R(A) × 2 になります。

駆動表に小さなNested Loops + 内部表の結合キーにインデックスが基本的なものということを覚えておきましょう。

(= 内部表でヒット件数が多いとパフォーマンスは下がる)

Hash

ハッシュ結合は、まず小さいテーブルをスキャンし、結合キーに対してハッシュ関数を適用することでハッシュ値に変換します。その次に、もう一方の大きなテーブルをスキャンして、結合キーがそのハッシュ値に存在するかどうかを調べる、という方法で結合を行います。

なのでハッシュテーブルをワーキングメモリに作ります。ワーキングメモリに収まらないと遅延が発生してしまいます。ハッシュテーブルを作るのでメモリを消費します。出力となるハッシュ値は順序性を保存しません。

ハッシュ結合では両方のテーブルのレコードを全件読込必要があります。

Sort Merge

MergeとかMerge JOINと呼ばれることが多い気がします。 SOrt Mergeは、結合対象のテーブルをそれぞれ結合キーでソートを行い、一致する結合キーを見つけたらそれを結果セットに含めるというものです。

テーブルのソートに多くの時間とリソースを要する可能性があります。テーブルソートをスキップできるケースに考慮が値します。。なので、Nested Loopsなどがまず優先的に選択肢になると考えておけばよいでしょう。

三角結合でクロス結合？

三角結合とは、JOINを2つ1つのクエリの中に記述するものが考えられます。それによって、テーブルAとテーブルB、テーブルAとテーブルCの間だけで結合条件を成り立つものです。テーブルBとテーブルC間には結合条件が存在しません。

こうした時の実行計画でまれにクロス結合が使用されている場合があります。理由はおくまで推測になるのですが、テーブルBとテーブルCのテーブルサイズが非常に小さいと評価される場合です。この2つのテーブルサイズが小さければ、テーブルAに2回あたりにいくよりも先にBとCを結合させておくことでテーブルAへの結合を1回におさめることができるからです。

こうした結合を回避させたい場合には、テーブルBとテーブルCの間に結合条件を加えることです。

まとめ

ここまで色々なSQLを試していて、「意図した結果が得られないな〜」なんてことがあるかと思います。そういうときは、第一章でやった統計情報を更新しましょう。

結合において、実行計画を考慮する際は、変動がおきやすいということを覚えておきましょう。アルゴリズムが複数あるためです。きちんと考慮しなければならない場合は、一度結合から離れて考えてみるべきです。

前回の記事

o21o21.hatenablog.jp

helloworlds

not a noun, it's a verb

【SQL】RDBの結合について