5.6 조인 알고리즘

PostgreSQL은 세 가지 조인 알고리즘을 갖는다 — Nested Loop, Hash Join, Merge Join. 각각 강점이 다르고 옵티마이저가 비용 추정으로 고릅니다. 셋의 동작과 운영자가 알아 둘 트레이드오프를 정리합니다.

세 알고리즘 비교

1. Nested Loop

    flowchart LR
  OUTER["outer<br/>(작은 쪽)"]
  INNER["inner<br/>(인덱스 있음)"]
  R["조인 결과"]

  OUTER -- "row 1" --> INNER
  OUTER -- "row 2" --> INNER
  OUTER -- "row 3" --> INNER
  INNER --> R

  classDef o fill:#dbeafe,stroke:#1d4ed8,color:#1e3a8a
  classDef i fill:#fef3c7,stroke:#b45309,color:#78350f
  classDef r fill:#d1fae5,stroke:#047857,color:#064e3b
  class OUTER o
  class INNER i
  class R r
  

전형적 형태:

 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

    flowchart LR
  INNER["inner"] --> H["Hash Table<br/>(메모리)"]
  OUTER["outer"] --> P["probe"]
  H --> P --> R["결과"]

  classDef i fill:#fef3c7,stroke:#b45309,color:#78350f
  classDef o fill:#dbeafe,stroke:#1d4ed8,color:#1e3a8a
  classDef h fill:#ede9fe,stroke:#6d28d9,color:#3b0764
  classDef r fill:#d1fae5,stroke:#047857,color:#064e3b
  class INNER i
  class OUTER o
  class H,P h
  class R r
  

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

    flowchart LR
  A["a (정렬)"] --> Z["zip 진행"]
  B["b (정렬)"] --> Z
  Z --> R["결과"]

  classDef sort fill:#fed7aa,stroke:#c2410c,color:#7c2d12
  classDef zip fill:#dbeafe,stroke:#1d4ed8,color:#1e3a8a
  classDef r fill:#d1fae5,stroke:#047857,color:#064e3b
  class A,B sort
  class Z zip
  class R r
  

전형적 형태:

 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은 = 기준)

옵티마이저의 선택 기준

강제로 알고리즘 바꾸기

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보다 항상 안전·빠름

다음 절(5.7)에서는 PostgreSQL에 공식 힌트가 없는 이유와 우회 방법을 봅니다.