PostgreSQL 조인 알고리즘 비교: 해시 조인(Hash Join), 중첩 루프 조인(Nested Loop Join), 병합 조인(Merge Join)

데이터베이스에서 조인(Join)은 가장 중요한 연산 중 하나이며, 조인 방식에 따라 성능이 크게 달라질 수 있습니다. PostgreSQL은 기본적으로 다음 세 가지 조인 알고리즘을 사용합니다

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

이 글에서는 각 조인 방식의 동작 원리, 장단점, 사용 조건을 깊이 있게 분석하고, EXPLAIN ANALYZE를 활용한 실제 테스트 결과도 비교하겠습니다.

---

1. 해시 조인 (Hash Join)

원리

• 작은 테이블(혹은 조인 키의 작은 부분 집합)을 해시 테이블(Hash Table)로 생성합니다.
• 큰 테이블을 스캔하면서 해시 테이블을 참조하여 빠르게 조인합니다.

조건

• 등가 조인(Equal Join, = 연산자 사용)에만 적용 가능
• 조인하는 두 테이블 중 적어도 하나는 메모리에 적재할 수 있어야 성능이 좋음

장점

✅ 테이블 크기가 크고 인덱스가 없을 때 효율적

✅ 랜덤 접근을 최소화하여 디스크 I/O를 줄일 수 있음

✅ 정렬이 필요하지 않음

단점

❌ 메모리를 많이 사용하며, 해시 테이블이 클 경우 디스크로 스왑될 가능성이 있음

❌ 비등가 조인 (>, < 등)에는 사용할 수 없음

❌ 해시 테이블을 생성하는 오버헤드가 존재

예제 및 실행 계획

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

출력 예시

Hash Join  (cost=5000.00..10000.00 rows=100000 width=200) (actual time=10.5..20.1 rows=100000 loops=1)
  Hash Cond: (o.customer_id = c.id)
  -> Seq Scan on orders o (cost=0.00..5000.00 rows=100000 width=100)
  -> Hash  (cost=2000.00..2000.00 rows=50000 width=100)
     -> Seq Scan on customers c (cost=0.00..2000.00 rows=50000 width=100)

해시 조인 특징

• Hash Cond는 조인 조건을 의미합니다.
• Hash 연산은 고객 테이블을 해시 테이블로 만들었다는 뜻입니다.
• Seq Scan이 사용되었으므로 테이블 풀 스캔을 수행했습니다.

---

2. 중첩 루프 조인 (Nested Loop Join)

원리

• 외부 테이블(Outer Table)을 한 줄씩 순회하면서, 내부 테이블(Inner Table)에서 조인 조건을 만족하는 행을 찾음
• 내부 테이블에서 인덱스가 있다면 성능이 크게 향상됨

조건

• 인덱스가 존재하면 매우 빠름
• 작은 테이블이 외부 테이블(Loop의 바깥쪽)일 때 유리

장점

✅ 인덱스가 있는 경우 매우 효율적

✅ 작은 데이터셋에서는 빠르고 메모리 사용량이 적음

단점

❌ 큰 테이블에서는 성능이 매우 나쁨 (O(N*M))

❌ 내부 테이블에 적절한 인덱스가 없으면 비효율적

예제 및 실행 계획

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

출력 예시

Nested Loop  (cost=5000.00..10000.00 rows=100000 width=200) (actual time=10.5..200.1 rows=100000 loops=1)
  -> Seq Scan on customers c (cost=0.00..5000.00 rows=1 width=100) (actual time=0.5..1.0 rows=1 loops=1)
        Filter: (name = 'Alice')
  -> Index Scan using orders_customer_id_idx on orders o (cost=0.00..5000.00 rows=100000 width=100)

중첩 루프 조인 특징

• Index Scan이 사용되었기 때문에 내부 테이블 검색이 최적화됨
• Seq Scan이 있으면 성능이 떨어질 가능성이 있음

---

3. 병합 조인 (Merge Join)

원리

• 두 테이블을 정렬한 후 병합(Merge)하여 조인하는 방식
• 정렬된 데이터가 있을 때 매우 빠르게 조인 가능

조건

• 두 테이블이 조인 키 기준으로 정렬되어 있어야 함
• ORDER BY를 포함한 쿼리에서 자주 사용됨

장점

✅ 대용량 테이블 조인 시 매우 효율적

✅ 디스크 I/O가 적음

✅ 비교적 메모리 사용량이 낮음

단점

❌ 정렬이 필요할 경우 추가 비용 발생

❌ 등가 조인(Equal Join)에만 사용 가능

예제 및 실행 계획

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

출력 예시

Merge Join  (cost=5000.00..10000.00 rows=100000 width=200) (actual time=5.0..12.0 rows=100000 loops=1)
  Merge Cond: (o.customer_id = c.id)
  -> Index Scan using orders_customer_id_idx on orders o (cost=0.00..5000.00 rows=100000 width=100)
  -> Index Scan using customers_pkey on customers c (cost=0.00..5000.00 rows=50000 width=100)

병합 조인 특징

• Merge Cond는 병합 조건을 의미합니다.
• 두 테이블이 정렬된 상태라면 조인 성능이 매우 우수합니다.

---

4. 조인 알고리즘 비교 및 정리

조인 방식	사용 조건	장점	단점
해시 조인	등가 조인(=)	대용량 테이블에서 빠름, 인덱스 필요 없음	메모리 사용량 많음, 비등가 조인 불가
중첩 루프 조인	작은 테이블 또는 인덱스가 있는 경우	인덱스 사용 시 빠름, 메모리 사용 적음	큰 테이블에서는 매우 비효율적
병합 조인	정렬된 테이블 조인	대용량 데이터에서 효율적	정렬 비용이 추가될 수 있음

---

결론

1. 작은 테이블 조인 → 중첩 루프 조인(Nested Loop Join)
2. 큰 테이블이지만 인덱스 없음 → 해시 조인(Hash Join)
3. 정렬된 데이터 조인 → 병합 조인(Merge Join)

조인의 성능을 최적화하려면 EXPLAIN ANALYZE를 사용하여 실행 계획을 확인하고, 필요에 따라 인덱스 추가, 테이블 정렬, 메모리 조정을 수행해야 합니다.