「SQL 実践入門」を学ぶ
nkm中途半端だが6章から。
第6章 結合を制するものはSQLを制す
結合には様々な種類があるが、概ね3つ
- クロス結合(Cross Join)
- 内部結合(Inner Join)
- 外部結合 (Outer Join)
交差結合
参考書の例をDBに取り込んで実行してみる
mysql> SELECT * FROM Employees CROSS JOIN Departments;
+--------+-----------+---------+---------+-----------+
| emp_id | emp_name | dept_id | dept_id | dept_name |
+--------+-----------+---------+---------+-----------+
| 001 | 石田 | 10 | 13 | 営業 |
| 001 | 石田 | 10 | 12 | 開発 |
| 001 | 石田 | 10 | 11 | 人事 |
| 001 | 石田 | 10 | 10 | 総務 |
| 002 | 小笠原 | 11 | 13 | 営業 |
| 002 | 小笠原 | 11 | 12 | 開発 |
| 002 | 小笠原 | 11 | 11 | 人事 |
| 002 | 小笠原 | 11 | 10 | 総務 |
| 003 | 夏目 | 11 | 13 | 営業 |
| 003 | 夏目 | 11 | 12 | 開発 |
| 003 | 夏目 | 11 | 11 | 人事 |
| 003 | 夏目 | 11 | 10 | 総務 |
| 004 | 米田 | 12 | 13 | 営業 |
| 004 | 米田 | 12 | 12 | 開発 |
| 004 | 米田 | 12 | 11 | 人事 |
| 004 | 米田 | 12 | 10 | 総務 |
| 005 | 釜本 | 12 | 13 | 営業 |
| 005 | 釜本 | 12 | 12 | 開発 |
| 005 | 釜本 | 12 | 11 | 人事 |
| 005 | 釜本 | 12 | 10 | 総務 |
| 006 | 岩瀬 | 12 | 13 | 営業 |
| 006 | 岩瀬 | 12 | 12 | 開発 |
| 006 | 岩瀬 | 12 | 11 | 人事 |
| 006 | 岩瀬 | 12 | 10 | 総務 |
+--------+-----------+---------+---------+-----------+
24 rows in set (0.01 sec)
交差結合があまり実務で使われない理由は主に2つ
- 実際にこういう結果を求めたいケースがない
- 非常にコストがかかる演算である
下記のようなSQLは交差結合となってしまう
SELECT * FROM Employees, Departments;
内部結合
内部結合は、全てがクロス結合の結果の部分集合になる
mysql> 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;
+--------+-----------+---------+-----------+
| emp_id | emp_name | dept_id | dept_name |
+--------+-----------+---------+-----------+
| 001 | 石田 | 10 | 総務 |
| 002 | 小笠原 | 11 | 人事 |
| 003 | 夏目 | 11 | 人事 |
| 004 | 米田 | 12 | 開発 |
| 005 | 釜本 | 12 | 開発 |
| 006 | 岩瀬 | 12 | 開発 |
+--------+-----------+---------+-----------+
6 rows in set (0.00 sec)
内部とは「直積の部分集合」という意味
実際にDBMSが内部結合を行うアルゴリズムでは結合対象をなるべく絞り込むように動作する
内部結合は相関サブクエリで書き換え可能なことが多い。
mysql> SELECT E.emp_id, E.emp_name, E.dept_id, (
-> SELECT D.dept_name FROM Departments D WHERE D.dept_id = E.dept_id) FROM Employees E;
+--------+-----------+---------+----------------------------------------------------------------------+
| emp_id | emp_name | dept_id | (
SELECT D.dept_name FROM Departments D WHERE D.dept_id = E.dept_id) |
+--------+-----------+---------+----------------------------------------------------------------------+
| 001 | 石田 | 10 | 総務 |
| 002 | 小笠原 | 11 | 人事 |
| 003 | 夏目 | 11 | 人事 |
| 004 | 米田 | 12 | 開発 |
| 005 | 釜本 | 12 | 開発 |
| 006 | 岩瀬 | 12 | 開発 |
+--------+-----------+---------+----------------------------------------------------------------------+
6 rows in set (0.01 sec)
dept_idは主キーなので、このサブクエリは常にスカラサブクエリとなる。
相関サブクエリは行ごとに実行されることに注意する。
nkm外部結合
外部結合には、次の3種類がある
- 左外部結合
- 右外部結合
- 完全外部結合
SELECT E.emp_id , E.emp_name, D.dept_id, D.dept_name FROM Employees E RIGHT OUTER JOIN Departments D ON E.dept_id = D.dept_id LIMIT 0, 1001;
+--------+----------+---------+-----------+
| emp_id | emp_name | dept_id | dept_name |
+--------+----------+---------+-----------+
| 001 | 石田 | 10 | 総務 |
| 003 | 夏目 | 11 | 人事 |
| 002 | 小笠原 | 11 | 人事 |
| 006 | 岩瀬 | 12 | 開発 |
| 005 | 釜本 | 12 | 開発 |
| 004 | 米田 | 12 | 開発 |
| null | null | 13 | 営業 | // この行はクロス結合では生成されない
+--------+----------+---------+-----------+
外部結合ではNULLの値が生成されることがクエリによってはある。そのため、下記の関係が成り立つ。
- 内部結合はクロス結合の真部分集合である。
- 外部結合は内部結合やクロス結合と部分集合をもつ。
nkm結合のアルゴリズムのパフォーマンス
結合アルゴリズムには大きく次の3つがある。
- Nested Loops
- Hash
- Sort Merge
Nested Loops
Nested Loopsは文字通り入れ子ループを使うアルゴリズム。
SQLの結合では一度につき2つのテーブルしか結合しないため二重ループになる。
①結合対象となるテーブル（Table_A)を1行ずつループしながらスキャンする。このテーブルを駆動表(driving table)または外部表(outer table)と呼ぶ。もう一つのテーブルは内部表(inner table)と呼ぶ。
②駆動表の一行について、結合条件に合致すればそれを返却する
③この動作を駆動表のすべての行に対して繰り返す
Table_A、Table_Bの結合対象の行数をR(A), R(B)とすると、アクセスされる行数はR(A) x R(B)となる。
駆動表にどちらを選択するかは一見重要ではなさそうだが、
内部表の結合キーの列にインデックスが存在している場合、駆動表の行がマッチするか判定する②の処理を高速に見つけられるため、(検索後に絞られた後の)駆動表のほうが行数が小さい方がよい。
キーあり
EXPLAIN SELECT E.emp_id , E.emp_name, D.dept_id, D.dept_name FROM Employees E INNER JOIN Departments D ON E.dept_id = D.dept_id;
+----+-------------+-------+------------+--------+---------------+---------+---------+----------------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+--------+---------------+---------+---------+----------------------+------+----------+-------------+
| 1 | SIMPLE | E | null | ALL | null | null | null | null | 6 | 100 | Using where |
| 1 | SIMPLE | D | null | eq_ref | PRIMARY | PRIMARY | 8 | sandbox_db.E.dept_id | 1 | 100 | null |
+----+-------------+-------+------------+--------+---------------+---------+---------+----------------------+------+----------+-------------+
キーなし
ALTER TABLE Departments DROP PRIMARY KEY;
EXPLAIN SELECT E.emp_id , E.emp_name, D.dept_id, D.dept_name FROM Employees E INNER JOIN Departments D ON E.dept_id = D.dept_id;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| 1 | SIMPLE | D | null | ALL | null | null | null | null | 4 | 100 | null |
| 1 | SIMPLE | E | null | ALL | null | null | null | null | 6 | 16.67 | Using where; Using join buffer (hash join) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
※内部表にインデックスを張っていても、駆動表に対応する内部表側カラムのヒット件数が多ければ、ループ回数が増えてパフォーマンスが下がる点に注意する。
ハッシュ結合
ハッシュ結合は以下のステップで実施される。
①まず小さいテーブルをスキャンし、結合キーをハッシュ値に変換する
②もう一方の大きなテーブルをスキャンし、結合キーがそのハッシュ値に存在するかを調べる
ハッシュ結合は、Nested Loopを使うのに適さない条件の場合に用いられる。すなわち内部表にインデックスを張っていない・小さい駆動表が存在しない（テーブルサイズがほぼ同じ）など。
結合テーブルからハッシュテーブルを作るため、Nested Loopに比べるとメモリを多く消費する上、出力となるハッシュ値が入力値の順序性を保証しないため、等値結合でしか使えない。
また、ハッシュは当然衝突しうる。
Sort Merge
単にMerge/Merge Joinとも。
①対象テーブルをそれぞれ結合キーでソートする。
②一致する結合キーを見つけたら結果セットに含める。
等値結合以外、不等号を用いた結合でも適用でき、テーブルが既にソート済みであればソート処理①をスキップでき、片方のテーブルをすべてスキャンした段階で検索が終了する。ただし、対象テーブルを両方ソートするため、Nested Loopよりメモリを消費する。
テーブルのソートに膨大な時間がかかるため、ソートができる場合以外はNested LoopまたはHashが現実的な選択肢となる。
クロス結合が用いられるパターン
3つのテーブルを相互に結合する三角結合パターンでは、暗黙的にクロス結合が用いられるパターンが有る。詳細は書籍に任せるが、これを回避するには、全てのテーブルに明示的にJOIN条件を設定してやると良い。
SELECT A.col_a, B.col_b, C.col_c
FROM Table_A A
INNER JOIN Table_b B
ON A.col_a = B.col_b
INNER JOIN Table_c C
ON A.col_a = C.col_c
AND B.col_b = C.col_c;
DBMSによっては実行計画は制御できず、特にMySQLにはNested Loop系のアルゴリズムしかないため、ここをチューニングする余地はない。
実行計画はテーブルのデータ量によって変動し、特にこの実行計画変動を最も引き起こしやすいのが結合。
したがって、SQLの性能変動リスクを抑えるためには、なるべく結合を避ける方針が重要。
nkm7 サブクエリが引き起こす弊害
サブクエリを用いた操作はテーブル操作と同じように扱える。
- テーブル ... 永続的、かつデータを保持する
- ビュー... 永続的だがデータは保持せず、アクセスごとにSELECTが実行される
- サブクエリ ... 非永続的でスコープはSQL実行時のみ
サブクエリの問題点は性能面、パフォーマンスにある。
- サブクエリの計算コストが上乗せされる
- データのI/Oコストがかかる(メモリに収まらない場合はTEMP落ち)
- 制約・インデックスによる最適化を受けられない
Receiptsテーブルの中でcust_idごとにseq最小の行を選択する
SELECT R1.cust_id, R1.seq, R1.price
FROM Receipts R1
INNER JOIN (
SELECT cust_id, MIN(seq) AS min_seq FROM Receipts GROUP BY cust_id
) R2
ON R1.cust_id = R2.cust_id
AND R1.seq = R2.min_seq
ウィンドウ関数を用いて、Receiptsへのアクセス回数が1回になるようにする。
SELECT cust_id, seq, price
FROM (
SELECT cust_id, seq, price, ROW_NUMBER() OVER (
PARTITION BY cust_id ORDER BY seq
) AS row_seq FROM Receipts
) WORK
WHERE WORK.row_seq = 1;
+---------+-----+-------+
| cust_id | seq | price |
+---------+-----+-------+
| A | 1 | 500 |
| B | 5 | 100 |
| C | 10 | 600 |
| D | 3 | 2000 |
+---------+-----+-------+
4 rows in set (0.01 sec)
先述の通り結合クエリは実行計画の不安定性、インデックス・メモリなど環境起因の遅延リスクがあるためなるべく用いない。実行計画をシンプルに保ち、非機能要件たるパフォーマンスを担保する。
nkm8,9 章はマニアックな内容なため飛ばし。
連番を振る例題などは中々面白かったですが、自分の実務では、テクニカルな、データ更新用の、1回限りのSQLを書く機会は中々少ないです。そもそもレビュワーがレビューできないことも多々ありますし。
COUNT(*) OVER () などウィンドウ関数を用いた解法は中々出てこないですが、使いこなしてみたいところです。
10章インデックスを使いこなす
インデックスが使えない例は多々ある。
- 全件検索時
- そもそも絞り込みが発生しないため。
- テキストに対する中間一致/後方一致
- IS NULLを条件に含む場合
- 索引列による演算を含む場合
- 否定形(NOT, <>, !=)
頻繁に実行されるクエリがある場合、そのクエリに含まれるカラムをすべて含む複合インデックスを作成することで、検索を高速化することができる。これをカバリングインデックスとよぶ。
考え方としてはデータマート、列指向DBの再現に近い。