조인 알고리즘 (Nested Loop, Hash Join, Merge Join)

조인을 실제로 수행하는 세 가지 방식. 옵티마이저가 비용으로 고르며, 각각이 언제 유리한지 알면 실행계획의 선택이 이해된다.

① Nested Loop — 바깥 행마다 안쪽을 찾는다

for (바깥 테이블의 각 행) {

안쪽 테이블에서 조인 키로 일치하는 행을 찾는다 }
유리: — 바깥 결과가 작고(WHERE 로 20행) 안쪽에 인덱스가 있을 때
- 인덱스 탐색 20번이면 끝난다
최악: — 양쪽 다 클 때
- O(n × m). 100만 × 100만이면 사실상 끝나지 않는다

② Hash Join — 작은 쪽으로 해시 테이블을 만든다

① 작은 테이블 전체를 읽어 조인 키로 메모리에 해시 테이블을 만든다
② 큰 테이블을 한 번 훑으며 해시 테이블에서 찾는다
유리: — 큰 두 테이블을 등치(=) 로 조인할 때의 일꾼
제약: — 메모리가 필요하다. 부족하면 디스크로 흘러(spill) 느려진다
- 등치 조인에만 쓸 수 있다 (범위 조인 불가)

③ Merge Join — 정렬해서 지퍼처럼 병합한다

양쪽을 조인 키로 정렬한 뒤, 두 줄을 앞에서부터 나란히 맞춰 나간다

유리: — 양쪽이 이미 조인 키로 정렬돼 있을 때 (인덱스 순서 그대로)
- 정렬 비용이 0이면 매우 효율적
불리: — 정렬을 새로 해야 하면 그 비용이 든다

엔진별 차이 — 실무에서 자주 부딪힌다

PostgreSQL — 셋 다 오래전부터 지원
MySQL — 오래 Nested Loop 계열만 썼다
- 8.0.18+ 부터 Hash Join 지원

"큰 테이블 조인이 유독 느리다" 면 MySQL 버전과 Hash Join 사용 여부를 본다. 8.0.18 미만이면 Nested Loop로 O(n·m)을 돌고 있을 수 있다.

계획에서 확인하기

EXPLAIN ANALYZE SELECT * FROM orders o JOIN member m ON o.member_id = m.id;
-- Hash Join  (cost=... rows=...)          ← PostgreSQL
--   ->  Seq Scan on orders
--   ->  Hash
--         ->  Seq Scan on member

Nested Loop가 나왔는데 양쪽이 크다면, 안쪽 테이블의 조인 키에 인덱스가 있는지 확인하는 것이 첫 수순이다.

면접 함정

❌ "Hash Join이 항상 빠르다" → 메모리가 부족하면 디스크로 흘러 느려지고, 한쪽이 아주 작으면 Nested Loop가 낫다.
❌ "조인이 많으면 무조건 느리다" → 인덱스와 알고리즘 선택이 맞으면 조인 자체는 싸다. N+1로 쪼개는 것이 훨씬 비싸다.

메모리가 부족하면 무슨 일이 생기나

EXPLAIN (ANALYZE, BUFFERS) SELECT ... ;
-- Hash Join
--   Buckets: 1024  Batches: 16  Memory Usage: 4096kB
--                  ^^^^^^^^^^^ Batches 가 1보다 크면 디스크로 흘렀다(spill)

Batches: 1이면 해시 테이블이 메모리에 다 들어간 것이고, 그보다 크면 디스크를 오가며 나눠 처리한 것이라 느리다. 처방은 작업 메모리를 늘리는 것이다.

SET work_mem = '64MB';       -- 세션 단위. 정렬·해시 하나당 할당되는 양이다

work_mem은 연결당이 아니라 연산당이라는 점이 함정이다 — 동시 접속 100에 해시가 3개씩 쓰이면 100×3×64MB를 쓸 수 있다.

조인 순서도 옵티마이저가 정한다

-- 테이블이 많으면 순서 후보가 폭발한다 (n! 에 가깝다)
SHOW join_collapse_limit;    -- 기본 8. 이보다 많으면 적힌 순서를 대체로 따른다
SHOW geqo_threshold;         -- 12개 이상이면 유전 알고리즘으로 근사한다

조인이 12개를 넘으면 옵티마이저가 최적을 포기하고 근사한다. 거대 조인 쿼리가 예측 불가능하게 느려지는 이유이고, 뷰나 CTE로 쪼개는 것이 실용적 처방이다.