[RDBMS] JOINのドライビングテーブルとドリブンテーブル整理

// ドライビング = A、ドリブン = B と仮定
for each row in A (ドライビング):             // Aを一度巡回
    for each matching row in B (ドリブン):  // BをAのrow数だけ繰り返し探索
        output(A.row + B.row)

ドライビング結果 = N件
ドリブン探索コスト = 1回当たり C

全体コスト = N × C

SELECT *
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.status = 'PENDING';

1. ordersでstatus = 'PENDING'フィルター → 500件抽出
2. 500件のcustomer_idでcustomersテーブルのインデックス探索 → 500回
総探索回数 = 500回

1. customers全体読み込み → 100,000件
2. 100,000件それぞれでordersテーブルを探索 → 100,000回
総探索回数 = 100,000回

✅ WHERE条件適用後の結果件数が少ないテーブル
✅ フィルター効果の大きい条件を持つテーブル
✅ JOIN前にrow数を多く減らせるテーブル

ordersテーブル：1,000,000件
status = 'PENDING'条件後の結果：500件

条件一致率 = 500 / 1,000,000 = 0.0005（0.05%）
→ 残るrow比率が非常に低いのでフィルター効果が大きい

✅ JOIN列（ON句の列）にインデックスが張られているテーブル
✅ 単件または少数件のlookupの役割をするテーブル
✅ テーブルが大きくてもJOIN列インデックスで素早く見つけられるテーブル

-- テーブル構造
CREATE TABLE orders (
    id          BIGINT PRIMARY KEY,
    customer_id BIGINT NOT NULL,
    status      VARCHAR(20) NOT NULL,
    created_at  DATETIME NOT NULL
);

CREATE TABLE customers (
    id    BIGINT PRIMARY KEY,
    name  VARCHAR(100),
    email VARCHAR(200)
);

-- インデックス追加
CREATE INDEX idx_orders_status      ON orders(status);        -- WHERE条件用
CREATE INDEX idx_orders_customer_id ON orders(customer_id);   -- JOIN/FK列用

SELECT *
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.status = 'PENDING';

Step 1. ordersでidx_orders_statusを使用
        → status = 'PENDING' に該当するrowだけ素早く抽出（ドライビング）

Step 2. 抽出されたN件のcustomer_idそれぞれで
        customersのPKインデックスを探索（ドリブン）
        → 毎回繰り返しのたびにindex seek

結果：全体コスト ≈ N × lookup_cost

-- 最悪に近いシナリオ
SELECT * FROM small_ref_table s
JOIN huge_table h ON h.non_indexed_col = s.id;

→ small_ref_tableの結果がN件なら
→ huge_tableをN回Full Table Scan
→ 全体コスト = N × M  （M = huge_table全件数）
→ N=1,000、M=5,000,000ならrow比較数が爆増

FKがあるからインデックスもあるはずだ → 危険な仮定
実際のインデックス定義 + EXPLAINの結果を確認 → 安全なアプローチ

-- 必要な場合は明示的に作成
CREATE INDEX idx_orders_customer_id ON orders(customer_id);

特徴：
- ドライビングテーブルを一度巡回
- ドリブンテーブルをドライビングのrow数だけ繰り返し探索

最適条件：
- ドライビング：少量の結果、フィルター効果が大きい
- ドリブン：JOIN列にインデックスが非常に重要

適した状況：OLTP、比較的小さい結果セット、インデックスが整備された環境

-- NLJの動作疑似コード
for each row r1 in driving_table:
    lookup driven_table where join_col = r1.join_col
    if found:
        emit(r1, matched_row)

動作方式：
Phase 1（Build）：通常はより小さい入力をハッシュテーブルに積み込む
Phase 2（Probe）：もう一方の入力をスキャンしてハッシュテーブルとマッチング

特徴：
- ドリブンのインデックスがなくても動作可能
- メモリ使用量が大きい
- メモリを超えるとディスクspillが発生する可能性がある

適した状況：大容量データ、equi-join中心、インデックスが弱い環境

-- MySQL 8.4でHash Joinの動作を確認
EXPLAIN FORMAT=TREE
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id;
-- 出力に "Hash" または "Inner hash join" が見えればHash Joinを使用中

-- MySQL：hash joinのメモリに関連する代表的な設定
SET join_buffer_size = 256 * 1024 * 1024;  -- 256MB

動作方式：
1. 両方の入力をJOIN列基準でソート
2. ソートされた2つのリストを順次スキャンしてマージ

特徴：
- 両方の入力がソートされていなければならない
- ソートコストがかかる場合がある
- 範囲条件やソートされた入力の活用に有利な場合がある
- ドライビング/ドリブンの概念がNLJより重要でない

-- MySQL
EXPLAIN SELECT *
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.status = 'PENDING';

+----+-------------+-------+--------+-------------------------+-------------------+---------+-------------------+------+
| id | select_type | table | type   | possible_keys           | key               | key_len | ref               | rows |
+----+-------------+-------+--------+-------------------------+-------------------+---------+-------------------+------+
|  1 | SIMPLE      | o     | ref    | idx_orders_status       | idx_orders_status | 22      | const             |  500 |
|  1 | SIMPLE      | c     | eq_ref | PRIMARY                 | PRIMARY           | 8       | mydb.o.customer_id|    1 |
+----+-------------+-------+--------+-------------------------+-------------------+---------+-------------------+------+

-- MySQL
ANALYZE TABLE orders;
ANALYZE TABLE customers;

-- PostgreSQL
ANALYZE orders;
ANALYZE customers;

-- Oracle
EXEC DBMS_STATS.GATHER_TABLE_STATS('schema_name', 'orders');

-- STRAIGHT_JOIN：FROM句の順序を固定
SELECT STRAIGHT_JOIN *
FROM orders o
JOIN customers c ON o.customer_id = c.id;

-- JOIN_ORDER：より細かいジョイン順序の指定
SELECT /*+ JOIN_ORDER(o, c) */ *
FROM orders o
JOIN customers c ON o.customer_id = c.id;

-- MySQL 8.4ではHASH_JOIN/NO_HASH_JOINの代わりにBNL/NO_BNLを使用
SELECT /*+ NO_BNL(c) */ *
FROM orders o
JOIN customers c ON o.customer_id = c.id;

-- ジョインの再整列を強く制限
SET join_collapse_limit = 1;

-- 特定のアルゴリズムを非選好
SET enable_hashjoin = off;
SET enable_mergejoin = off;

-- LEADINGヒント：ジョイン順序の起点を指定
SELECT /*+ LEADING(o) */ *
FROM orders o
JOIN customers c ON o.customer_id = c.id;

-- USE_NL：指定したテーブルをinner tableとしてnested loopを使用
SELECT /*+ LEADING(o) USE_NL(c) */ *
FROM orders o
JOIN customers c ON o.customer_id = c.id;

SELECT *
FROM orders o
INNER LOOP JOIN customers c ON o.customer_id = c.id
OPTION (FORCE ORDER);

✅ WHERE条件で結果が多く減るテーブルをドライビング候補として見る
✅ ドリブンテーブルのJOIN列（ON句）にインデックスがあるか確認する
✅ FK列は「自動インデックスがあるはず」と仮定せず実際のインデックスを確認する
✅ 3つ以上のJOIN時はEXPLAINで実行順序を確認する
✅ SELECT * を避け、必要な列だけを選択してカバリングインデックスの可能性を高める

Step 1. EXPLAINを実行
        → JOIN順序とアクセスタイプを確認
        → ドリブン側がALLかどうかまず確認する

Step 2. rows / filteredを確認
        → ドライビング候補の結果件数が異常に大きくないか点検

Step 3. 統計情報の更新
        → ANALYZEまたはDBMS_STATS後に実行計画を再確認

Step 4. インデックスの追加
        → ドリブンJOIN列のインデックス
        → 必要な場合はドライビングフィルター列のインデックス

Step 5. それでも遅い場合
        → DBMS別ヒントまたはplanner設定で例外的に補正

-- 悪い例
SELECT * FROM small_table s
JOIN huge_table h ON h.non_indexed_col = s.id;

-- 解決
CREATE INDEX idx_huge_non_indexed ON huge_table(non_indexed_col);

-- 悪い例
SELECT * FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE o.status = 'PENDING';

-- 確認後にジョイン順序を補正
SELECT STRAIGHT_JOIN *
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.status = 'PENDING';

ALTER TABLE orders
  ADD CONSTRAINT fk_orders_customer
  FOREIGN KEY (customer_id) REFERENCES customers(id);

-- 実際のスキーマを確認後、必要な場合は明示的に作成
CREATE INDEX idx_orders_customer_id ON orders(customer_id);

SELECT *
FROM orders o
JOIN customers c ON o.customer_id = c.id
JOIN products p ON o.product_id = p.id
JOIN categories cat ON p.category_id = cat.id
WHERE o.created_at BETWEEN '2024-01-01' AND '2024-03-31';

-- ドライビング候補用：WHERE条件列
CREATE INDEX idx_orders_status_created ON orders(status, created_at);

-- ドリブン候補用：JOIN列
CREATE INDEX idx_orders_customer_id ON orders(customer_id);

-- カバリングインデックス例
CREATE INDEX idx_orders_covering ON orders(customer_id, status, created_at);

小さいドライビング × インデックスありのドリブン = 速いJOIN
大きいドライビング × インデックスなしのドリブン = 遅いJOIN