JOIN 동작 원리 — Nested Loop부터 Hash Join까지

드라이빙 테이블 (Driving Table): 먼저 읽히는 테이블 (외부 루프)
드리븐 테이블 (Driven Table):  나중에 읽히는 테이블 (내부 루프)

-- 옵티마이저가 드라이빙 테이블을 결정합니다
SELECT u.name, o.amount
FROM users u            -- 드라이빙? 드리븐?
JOIN orders o ON u.id = o.user_id  -- 옵티마이저가 결정
WHERE u.age > 20;

-- 드라이빙 테이블 순서 강제 (옵티마이저가 잘못 선택할 때만 사용)
SELECT STRAIGHT_JOIN u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id;

for each row in 드라이빙_테이블:
    for each row in 드리븐_테이블:
        if 조인_조건_일치:
            결과에 추가

-- 예시: users(100행) JOIN orders(10,000행)
-- 비교 횟수: 100 × 10,000 = 1,000,000
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id;

드라이빙 테이블의 행을 join_buffer에 가득 채움
for each row in 드리븐_테이블:
    for each row in join_buffer:
        if 조인_조건_일치:
            결과에 추가

-- join_buffer_size로 버퍼 크기 조절 (기본 256KB)
SHOW VARIABLES LIKE 'join_buffer_size';

NLJ: 드리븐 테이블 풀 스캔 × 드라이빙 행 수
     = 10,000 × 100 = 1,000,000 행 읽기

BNL: join_buffer에 50행이 담긴다면
     드리븐 테이블 풀 스캔 × (100/50) = 2번
     = 10,000 × 2 = 20,000 행 읽기

for each row in 드라이빙_테이블:
    인덱스를 사용하여 드리븐_테이블에서 매칭 행 검색  -- O(log n)
    if 조인_조건_일치:
        결과에 추가

-- orders.user_id에 인덱스가 있는 경우
CREATE INDEX idx_user_id ON orders(user_id);

-- users(100행) JOIN orders(10,000행)
-- 비교 횟수: 100 × log(10,000) ≈ 100 × 13 = 1,300
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.age > 20;

EXPLAIN SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.age > 20;

-- type: ref (인덱스 사용)
-- key: idx_user_id
-- Extra: Using index condition (ICP 적용 시)

Build Phase (빌드 단계):
    작은 테이블로 해시 테이블 생성
    for each row in 작은_테이블:
        hash(조인_키) → 해시 테이블에 저장

Probe Phase (탐색 단계):
    for each row in 큰_테이블:
        hash(조인_키) → 해시 테이블에서 매칭 검색

-- 인덱스가 없는 등가 조인에서 자동 사용
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id;  -- user_id에 인덱스 없으면 Hash Join

-- EXPLAIN으로 확인
EXPLAIN FORMAT=TREE
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id;
-- → Hash join 이 표시됩니다

-- join_buffer_size가 해시 테이블 메모리로 사용됩니다
-- 메모리가 부족하면 디스크를 사용하는 Grace Hash Join으로 전환
SET join_buffer_size = 262144;  -- 256KB (기본값)

SELECT a.*, b.*, c.*
FROM A
JOIN B ON A.id = B.a_id
JOIN C ON B.id = C.b_id;

-- 실행 순서 (옵티마이저가 결정):
-- for each row in A:
--     for each row in B (using index on B.a_id):
--         for each row in C (using index on C.b_id):
--             결과에 추가

-- optimizer_search_depth로 탐색 깊이 제한
SHOW VARIABLES LIKE 'optimizer_search_depth';

-- 가장 중요한 최적화
CREATE INDEX idx_user_id ON orders(user_id);

-- 드라이빙 테이블의 행 수를 줄이면 전체 성능 향상
SELECT u.name, o.amount
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.created_at >= '2026-01-01';  -- users 테이블 필터링

-- 나쁜 예: SELECT *
SELECT * FROM users u JOIN orders o ON u.id = o.user_id;

-- 좋은 예: 필요한 컬럼만
SELECT u.name, o.amount FROM users u JOIN orders o ON u.id = o.user_id;

EXPLAIN FORMAT=TREE
SELECT u.name, COUNT(o.id)
FROM users u
LEFT JOIN orders o ON u.id = o.user_id
GROUP BY u.name;