結合アルゴリズムと結合順序

本記事で使うデータ — perf_sales と employee

テーブルを結合するとき、データベースは内部で結合アルゴリズム（join algorithm、2 つのテーブルの行をどう突き合わせるかの手順）を選びます。

結合の方法によって効率が変わります。

題材は売上テーブルperf_sales（5 万行。

emp_idが担当者を指す）と、社員テーブルemployee（30 行。

emp_idが主キー相当）です。

この 2 つをemp_idで結合するとき、実行計画にどちらが外側ループとして出るか、索引の有無で結合順序がどう変わるかを観察します。

演習に入る前に、本記事で使う 2 つのテーブル — perf_salesとemployee — の列定義とデータのサンプルを確認しておきます。perf_salesの生成に少し時間がかかるので、最初の実行は数秒待つことがあります。

① PRAGMA table_info(perf_sales);とPRAGMA table_info(employee);で両テーブルの列定義を確認してください。

② SELECT * FROM perf_sales LIMIT 5;とSELECT * FROM employee LIMIT 5;で先頭 5 行をプレビューしてください。

③ SELECT COUNT(*) FROM perf_sales;とSELECT COUNT(*) FROM employee;で両テーブルの行数差（5 万 対 30）を確認してください。

ネステッドループ結合と結合順序

ネステッドループ結合（nested loop join）は、外側のテーブルを 1 行ずつ走査し、その各行について内側のテーブルから結合条件に合う行を探す、という二重ループの方式です。

-- 同じ結合クエリを 3 つの結合方式で比較してみます
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- ネステッドループ結合の内部処理イメージ
-- for each e in employee:        -- 外側ループ (30 行)
--   for each s in perf_sales:    -- 内側 (索引が無いと 5 万行を全走査)
--     if s.emp_id = e.emp_id then 結合結果に追加

• 外側ループは行数分だけ回るので、行数の少ないテーブルを外側にする
• 内側は外側の各行から繰り返し引かれるので、結合キーに索引を作って 1 発で引ける形にする
• 実行計画では最初に出てくるテーブルが外側、次に出てくるテーブルが内側
• 最適化器は統計から外側 / 内側を自動で決めるので、FROMに書いた順序が必ず守られるわけではない

-- perf_sales と employee を emp_id で結合（部署 1 の社員別 売上合計）
-- perf_sales.emp_id に索引が無いと内側 perf_sales を全走査する計画になりやすい
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SCAN perf_sales AS s   （索引が無いので内側も全走査）

-- perf_sales.emp_id に索引を作ると内側を索引で引ける
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

「担当者ごとの売上件数」を求める結合クエリの実行計画を見て、どちらのテーブルが外側ループになっているかを読み取ります。（正しく実行できれば解説が表示されます）

① EXPLAIN QUERY PLANを付けて、employeeとperf_salesをemp_idで結合し、社員名ごとに件数をGROUP BYで集計するクエリの計画を確認してください。

② 出力で先に出てくるテーブルが外側ループ、後に出てくるテーブルが内側です。perf_sales.emp_idに索引が無いこの状態で、どちらが外側に来ているか・内側がどう読まれているかを読み取ってください。

結合クエリの内側テーブルを索引で引ける形にして、実行計画がSCANからSEARCH ... USING INDEXに変わることを確認します。1 回の実行で索引作成と計画確認を完結させてください。

① DROP INDEX IF EXISTSで同名索引を消してから、perf_salesのemp_id列に索引をCREATE INDEXで作成してください。

② EXPLAIN QUERY PLANを付けて、employeeとperf_salesをemp_idで結合し社員名ごとに件数を集計するクエリの計画を確認してください。外側がemployee（30 行）のまま、内側perf_salesが索引で引かれる形に変わることを読み取ってください。

結合順序は最適化器が統計から自動で決める

結合順序（どちらを外側ループにするか）は、原則として最適化器が統計に基づいて自動で決めます。

前の記事で扱ったANALYZEで統計を集めておくと、「どちらのテーブルが小さいか」「内側を索引で引けるか」をより正確に見積もり、外側 / 内側の割り当てを最適化します。

書き手がFROMに書く順番は、最適化器が無視して入れ替えることがあります。

結合順序を読むコツは、EXPLAIN QUERY PLANの出力で上に出るテーブルほど外側のループだと読むことです。

意図しないテーブルが外側になって遅いときは、内側にしたいテーブルの結合キーに索引があるかをまず確認します。

-- ANALYZE 後は統計に基づいて外側/内側がより的確に決まる
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
ANALYZE;

-- FROM を perf_sales 先頭にしても、最適化器は小さい employee を外側に回しうる
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM perf_sales s
JOIN employee e ON e.emp_id = s.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

FROMに書くテーブルの順番を入れ替えても、最適化器が同じ結合順序を選ぶことを確認します。1 回の実行で索引作成・統計収集・計画確認まで完結させてください。

① DROP INDEX IF EXISTSで同名索引を消してからperf_salesのemp_idに索引を作り、ANALYZE;で統計を収集してください。

② EXPLAIN QUERY PLANを付けて、今度はFROM perf_sales s JOIN employee e ON ...（大きいテーブルをFROMの先頭に書く）の順で社員名ごとの件数を集計するクエリの計画を確認してください。FROMの順を変えても、最適化器が 30 行のemployeeを外側ループに選んでいるかを読み取ってください。

ハッシュ結合とソートマージ結合 — 他 DB の結合方式

大規模 DB（PostgreSQL / Oracle / SQL Server など）は、ネステッドループ結合以外にハッシュ結合（hash join、小さい表をハッシュ表にしてもう一方を突き合わせる）とソートマージ結合（sort-merge join、両方を結合キーで並べてから同時に走査する）も使います。

本講座のブラウザコンソールが使うエンジンは結合方式としてネステッドループだけを使うため、ここでは概念図でこの 2 方式の動き方を押さえます。

ハッシュ結合 — 小さい表をハッシュ表にしてもう一方を流す

-- 同じクエリをハッシュ結合で実行した場合のイメージ
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- ハッシュ結合の内部処理イメージ
-- H := { e.emp_id => e | e in employee }    -- ① ビルド (employee をハッシュ表に)
-- for each s in perf_sales:                  -- ② プローブ (perf_sales を流す)
--   if H[s.emp_id] が存在: 結合結果に追加

• 小さい表をビルド側にするとハッシュ表がメモリに載りやすく速い
• 等値結合（=）にしか使えず、範囲条件（< / BETWEEN）の結合では使えない
• 内側に索引が無くても大量行どうしを 1 回ずつの走査で結合できるため、ネステッドループより速いことが多い
• 実務 DB のEXPLAINではHash Joinのような表記で出る

ソートマージ結合 — 両方を並べてから同時に走査する

-- 同じクエリをソートマージ結合で実行した場合のイメージ
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- ソートマージ結合の内部処理イメージ
-- E := sort(employee by emp_id)        -- ① ソート (両方を emp_id 順に)
-- S := sort(perf_sales by emp_id)
-- i, j := 0, 0
-- while i < |E| かつ j < |S|:           -- ② マージ
--   if E[i].emp_id = S[j].emp_id: 結合結果に追加, j++
--   else if E[i].emp_id < S[j].emp_id: i++
--   else: j++

• 両方が既にソート済み（索引で並んでいる等）なら、ソート費用がほぼゼロで非常に速い
• 範囲結合（< / BETWEEN を含む結合条件）も扱える、ハッシュ結合に無い強み
• 結果は結合キー順に整列して出るため、後段の集計やマージ処理に都合がよい
• 実務 DB のEXPLAINではMerge Joinのような表記で出る

ハッシュ結合 / ソートマージ結合は他 RDBMS の結合方式

ハッシュ結合とソートマージ結合は PostgreSQL / Oracle / SQL Server など大規模 DB が備える結合方式です。

本講座のブラウザコンソールが使うエンジンは結合アルゴリズムとしてネステッドループだけを使い（必要なら結合補助の一時的な内部索引を作ります）、ハッシュ結合・ソートマージ結合はこのコンソールでは実演して見せることができません。

ここでは概念図と読むだけのコードで方式の考え方を押さえます。

一方、本記事の前半で扱ったネステッドループ結合の外側 / 内側、結合順序、索引で内側をSEARCHに変える挙動は実際に観察できます。

どの結合方式が選ばれたかを読み解く力は、このネステッドループと結合順序の理解がそのまま土台になります。

実務 DB ではEXPLAINにHash Join / Merge Joinのような語が出るので、まず本講座でネステッドループの読み方を体得してください。

-- 以下は PostgreSQL での EXPLAIN のイメージ（読むだけ・本講座のコンソールでは実行しない）
-- EXPLAIN SELECT e.name, SUM(s.amount) FROM employee e
--   JOIN perf_sales s ON s.emp_id = e.emp_id GROUP BY e.name;
-- 計画例:
--   Hash Join  （employee をハッシュ表にして perf_sales を流す）
--   または Merge Join （両方を emp_id でソートしてから突き合わせ）
-- PostgreSQL は統計とコストでこれら方式を自動選択する

-- 本講座のコンソールで実際に観察できるのはこちら（ネステッドループ）:
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee / SEARCH perf_sales USING INDEX ix_sales_emp (emp_id=?)

本記事のまとめとして、索引を付けた状態の結合計画をもう一度確認し、外側ループ・内側の索引アクセス・結果の意味を読み取ります。1 回の実行で索引作成と計画確認・結果確認を完結させてください。

① DROP INDEX IF EXISTSで同名索引を消してからperf_salesのemp_idに索引を作成してください。

② EXPLAIN QUERY PLANを付けて、employeeとperf_salesをemp_idで結合し、担当者名ごとの売上件数を求めるクエリの計画を確認してください。

③ 同じ集計クエリ（EXPLAIN QUERY PLAN無し）をORDER BY cnt DESC LIMIT 5;付きで実行し、件数上位 5 名を取り出してください。計画と実結果の両方を読み取ってください。