PostgreSQL 조인 전략

1. 조인 전략 목록

1. 중첩 루프 조인(Nested Loop Join)
2. 머지 조인(Merge Join)
3. 해시 조인(Hash Join)

참고: 이 외에도 “인덱스 중첩 루프(Index Nested Loop)”나 “병렬 조인(Parallel Join)” 같은 변형이 있지만, 기본 원리는 위 세 가지에 포함된다.

---

2. 각 조인 전략의 특징

2.1 중첩 루프 조인 (Nested Loop Join)

• 원리
  • 외부 테이블(outer)의 각 튜플을 순회하면서, 내부 테이블(inner)에서 조건에 맞는 튜플을 매칭(탐색)
• 장점
  • 작은 테이블끼리의 조인이나, 외부 튜플이 극히 적을 때 효율적임
  • 인덱스가 잘 구축되어 있으면 인덱스 중첩 루프(Index Nested Loop)로 빠르게 탐색 가능
• 단점
  • 튜플 수가 많아지면 O(Nouter × Cost(inner scan)) 만큼 비용 급증
  • 내부 테이블에 인덱스가 없거나, 외부 튜플 수가 많으면 비효율적임

2.2 머지 조인 (Merge Join)

• 원리
  • 두 테이블을 조인 키 기준으로 정렬한 뒤, 양쪽 커서를 이동하며 일치하는 키를 병합(join)
• 장점
  • 이미 정렬된(또는 정렬 비용이 낮은) 큰 테이블끼리의 조인에 적합
  • 양쪽 커서를 한 번씩만 이동하므로, 대량 데이터 처리에 효율적임
• 단점
  • 정렬 비용(O(N log N))이 커질 수 있음
  • 정렬을 위한 외부 메모리(external sort) 사용 시 디스크 I/O 증가

2.3 해시 조인 (Hash Join)

• 원리
  1. Build 단계: 작은 쪽(보통 inner 테이블)의 조인 키로 해시 테이블(Hash Table)을 메모리에 구축
  2. Probe 단계: 큰 쪽(outer 테이블)을 순회하며, 각 튜플의 키를 해시 테이블에서 조회
• 장점
  • 정렬이 불필요하므로, 정렬 비용 없이 비정렬 상태의 대량 데이터에 강력함
  • 메모리 내 해시 조회가 빠름 (O(1) 평균 시간 복잡도를 가짐)
• 단점
  • 해시 테이블이 work_mem 한계를 넘으면 디스크로 스필(Spill) → 성능 저하 발생하게 됨 (Disk I/O > In-Memory I/O)
  • 해시 함수 충돌 시 성능 저하 가능
• 사용 조건
  • 조인 키가 해시 가능(hashing)해야 하며, 보통 동등 조인(=)에서만 적용
  • 해시 테이블을 구축할 정도로 작은 쪽 테이블이 메모리에 수용되어야 최적

---

3. 해시 조인(Hash Join) 상세 설명

3.1 작동 단계

1. Build (구축) 단계
   • PostgreSQL이 옵티마이저로부터 “해시 조인”을 선택하면, 먼저 smaller relation(build side)의 모든 튜플을 읽어들여
   • 각 튜플의 조인 키를 해시 함수에 투입해 버킷(bucket)으로 분산
   • 버킷별로 연결 리스트 또는 버퍼 구조를 만들어 메모리에 저장
2. Probe (탐색) 단계
   • larger relation(probe side)을 첫 튜플부터 순회
   • 각 튜플의 조인 키를 동일 해시 함수에 투입하여 해당 버킷을 찾고,
   • 그 버킷에 저장된 build-side 튜플들과 키를 비교해 일치하는 튜플을 출력
3. 마무리
   • probe-side 스캔이 끝나면 조인 결과를 반환
   • 이후 필요하다면 정렬, 집계 등 후속 작업 수행

---

3.2 메모리 관리 및 스필(Spill)

• PostgreSQL은 각 세션별 work_mem 설정을 기준으로 해시 테이블을 메모리에 할당
• 메모리 초과 시:
  • 해시 테이블을 여러 개의 배치(batch)로 분할해 디스크에 임시 파일로 저장(즉, 디스크 스필 발생)
  • 각 배치를 순차적으로 다시 로드(build)하고 probe를 반복 → 디스크 I/O에 의한 성능 저하

---

3.3 파라미터 및 튜닝 포인트

• work_mem
  • 세션당 사용 가능한 메모리 한계. 해시 조인의 build 쪽 테이블 크기보다 커야 메모리 내 처리 가능
• hash_mem_multiplier
  • 복수 프로세스 병렬 해시 조인의 메모리 배분 비율 조정
• effective_cache_size
  • 옵티마이저가 생각하는 OS와 데이터베이스 캐시 크기를 반영하여, 해시 vs 머지 조인 선택에 영향
• enable_hashjoin
  • 해시 조인 사용을 켜거나 끌 수 있는 옵티마이저 플래그

---

3.4 병렬 해시 조인 (Parallel Hash Join)

• PostgreSQL 10 이후부터 병렬 해시 조인을 지원
• 여러 워커 프로세스가 build 또는 probe 단계에 참여해 처리 속도 향상
• max_parallel_workers_per_gather 등 병렬 실행 파라미터로 제어

---

3.5 실행 계획 예시

EXPLAIN ANALYZE
SELECT *
FROM orders o
JOIN customers c ON o.customer_id = c.id;

Hash Join  (cost=.... rows=... width=...)
  Hash Cond: (o.customer_id = c.id)
  ->  Seq Scan on orders o
  ->  Hash  (build)
        -> Seq Scan on customers c

• Hash 노드에서 customers 테이블을 build
• 그 위의 Hash Join 노드에서 orders를 probe

---

4. 언제 해시 조인을 선택할까?

• 비정렬(unsorted) 상태의 대량 데이터 조인 시 추천
• 조인 키에 인덱스가 없거나, 정렬 비용이 크다고 판단될 때
• 메모리에 build-side 전체를 올릴 수 있을 때 최적 성능 발휘
• 동등(=) 조인에만 적용 가능하며, 범위 조인(>, < 등)에는 부적합

---

요약

• Nested Loop: 소규모/인덱스 활용 조인에 적합
• Merge Join: 이미 정렬된 대용량 조인에 유리, 정렬 비용이 관건
• Hash Join: 메모리 내 해시 테이블로 빠른 동등 조인, 메모리 한계 시 디스크 스필 주의

특히 해시 조인은 메모리 관리가 성능의 핵심이며, work_mem 설정과 병렬 처리 옵션을 적절히 튜닝하면 매우 대용량의 조인에서도 뛰어난 성능을 낼 수 있다.