본문으로 건너뛰기

5.6 조인 알고리즘

PostgreSQL의 조인 알고리즘은 Nested Loop, Hash Join, Merge Join 세 가지입니다. 각각 강점이 다르고, 옵티마이저가 비용 추정으로 그중 하나를 고릅니다. 셋이 어떻게 동작하고 어떤 트레이드오프를 갖는지 알아 두면 plan이 왜 그렇게 나왔는지 읽어낼 수 있습니다.

세 알고리즘 비교​

알고리즘동작강점약점
Nested Loopouter의 row마다 inner를 한 번씩 검색outer가 작거나 inner에 좋은 인덱스가 있을 때outer × inner 크면 폭증
Hash Joininner로 hash table 만들고 outer가 probeinner가 메모리에 들어가고 자유로운 join 조건inner가 크면 spill, equi-join 한정
Merge Join양쪽을 정렬해 zip둘 다 정렬돼 있거나 인덱스 순서대로 들어올 때정렬 비용 크면 손해

1. Nested Loop​

전형적 형태:

 Nested Loop
   ->  Index Scan on users  (rows=5)
   ->  Index Scan on orders  (rows=20, loops=5)
         Index Cond: (orders.user_id = users.id)

loops가 outer rows와 같다는 점이 핵심입니다.

강점​

  • outer가 매우 작으면 (수 ~ 수백) 가장 빠르다
  • inner의 join 키에 인덱스가 있으면 한 호출이 O(log n)
  • 메모리 사용 거의 없음

약점​

  • outer rows × inner cost가 곱해진다 — outer가 커지면 폭증
  • 잘못된 통계로 outer를 작다고 잘못 예측하면 수초~수분 차이의 plan 미스 발생

운영에서 nested loop이 갑자기 느려진 사고는 거의 항상 통계 미스가 원인입니다.

2. Hash Join​

PostgreSQL은 보통 작은 쪽을 inner로 골라 hash table을 만듭니다. 메모리가 부족하면 partitioned hash join — 양쪽을 같은 키로 파티션해 디스크에 쓴 뒤 묶음 단위로 처리합니다.

전형적 형태:

 Hash Join
   Hash Cond: (orders.user_id = users.id)
   ->  Seq Scan on orders  (rows=1000000)
   ->  Hash
         ->  Seq Scan on users  (rows=10000)
               Filter: (city = 'Seoul')

강점​

  • 양쪽이 크고 인덱스가 없거나 무관할 때 best
  • equi-join (=)에서 매우 빠름
  • 매 row를 한 번씩만 처리 (outer × inner의 곱 없음)

약점​

  • =만 지원합니다. <, BETWEEN 같은 조건은 불가
  • inner가 메모리에 안 들어가면 spill (work_mem 부족)
  • Batches > 1이 나오면 디스크 I/O가 추가됨

work_mem 영향​

 Hash  (Batches: 8 (originally 1))

work_mem이 inner 크기보다 작으면 PostgreSQL이 batch로 나눠 처리합니다. 임시 파일 I/O가 추가돼 느려집니다. 한 번 분석 쿼리에서는 SET work_mem = '512MB'로 늘려 batch를 줄이는 게 표준입니다.

3. Merge Join​

전형적 형태:

 Merge Join
   Merge Cond: (a.id = b.a_id)
   ->  Index Scan using a_pkey on a    (rows=1M, 정렬됨)
   ->  Index Scan using b_a_id on b    (rows=2M, 정렬됨)

강점​

  • 양쪽이 이미 인덱스 순서로 정렬돼 들어오면 매우 빠름
  • 메모리 거의 사용 안 함 (순차 비교)
  • 매우 큰 데이터셋의 equi-join에서 hash보다 유리할 수 있음

약점​

  • 한쪽이라도 정렬 안 돼 있으면 명시 Sort가 추가됨 — 그러면 hash가 보통 더 빠름
  • range 조건은 부분 지원 (merge join은 = 기준)

옵티마이저의 선택 기준​

상황보통 고르는 알고리즘
outer가 매우 작음, inner에 인덱스 있음Nested Loop
양쪽 큼, 메모리 OK, equi-joinHash Join
양쪽 큼, 둘 다 정렬돼 들어옴 (PK = FK)Merge Join
비-equi join (<, BETWEEN)Nested Loop만 가능
FULL OUTER JOINHash 또는 Merge (Nested Loop 못 함)

강제로 알고리즘 바꾸기​

SET enable_nestloop = off;       -- nested loop 비활성
SET enable_hashjoin = off;
SET enable_mergejoin = off;

-- 또는 pg_hint_plan 확장
SELECT /*+ HashJoin(a b) */ ...;

운영에서는 SET LOCAL ... = off로 트랜잭션 단위만 변경. 클러스터 전역 변경은 다른 쿼리에 영향.

운영 사례 — 자주 보는 함정​

1. Nested Loop이 갑자기 느림​

 Nested Loop  (rows=1) → (actual rows=500000)

원인: 통계 미스. ANALYZE → plan 다시 검토합니다.

2. Hash Join이 디스크 spill​

 Hash  (Batches: 16, Memory Usage: 4MB)

원인: work_mem 부족. 분석 쿼리에 한해 SET LOCAL work_mem = '512MB'.

3. Merge Join에 Sort가 추가됨​

 Merge Join
   ->  Sort  (Sort Method: external merge)
         ->  Seq Scan on a
   ->  Index Scan on b

정렬 비용이 커지면 Hash Join이 더 빠를 가능성이 있습니다. enable_mergejoin = off로 확인합니다.

4. FULL OUTER JOIN이 Hash만 가능​

FULL OUTER JOIN은 Nested Loop으로 불가능합니다. 양쪽이 매우 크면 Hash가 메모리에 안 들어가 spill — LEFT JOIN으로 충분한지 검토합니다.

Anti-join / Semi-join​

NOT EXISTS / EXISTS는 별도 노드(Hash Anti Join, Hash Semi Join)로 나타납니다. NOT IN보다 NULL 안전성 + 성능 모두 우위 — 운영 표준은 NOT EXISTS.

-- 권장
SELECT * FROM users u
WHERE NOT EXISTS (
  SELECT 1 FROM banned_users b WHERE b.user_id = u.id
);

-- 함정: banned_users.user_id에 NULL이 있으면 결과가 비어 버림
SELECT * FROM users WHERE id NOT IN (SELECT user_id FROM banned_users);

정리​

  • 세 조인 Nested Loop·Hash Join·Merge Join은 각각 강점이 다름
  • Nested Loop은 작은 outer에 좋은 inner 인덱스가 있을 때 빠르고, 통계 미스에 가장 취약합니다
  • Hash Join은 양쪽이 크고 메모리가 충분한 equi-join용. work_mem이 핵심
  • Merge Join은 양쪽이 정렬돼 들어올 때 유리하고, 정렬 비용이 크면 손해입니다
  • 비-equi·FULL OUTER는 알고리즘 선택에 제한
  • NOT EXISTS가 NOT IN보다 항상 안전하고 빠름