5498 words
27 minutes
[SQL]Join 알고리즘: Nested Loop vs Hash vs Sort Merge

선행 글: [SQL]Join의 의미 — 여기서는 “4. 논리적 JOIN과 물리적 JOIN” 중 물리적 JOIN을 다룸

모든 실행 계획은 PostgreSQL 16.15에서 직접 실행한 결과. customers 10만 행, orders 100만 행, orders.customer_id에 인덱스 존재

0. 한눈에 비교#

구분Nested LoopHash JoinSort Merge Join
동작outer 한 행마다 inner를 탐색작은 쪽으로 해시 테이블을 만들고 큰 쪽으로 probe양쪽을 조인 키로 정렬한 뒤 동시에 훑음
조인 조건모든 조건(=, <, BETWEEN, LIKE …)등가(=)만등가(=)만 (PostgreSQL 기준)
유리한 상황outer가 작고 inner 조인 키에 인덱스 있음대량 vs 대량, 인덱스 없음, 정렬 불필요양쪽이 이미 정렬됨(인덱스), 결과도 정렬 필요
비용outer 행 수 × inner 1회 탐색양쪽 1회 스캔 + 해시 빌드 메모리정렬 비용(이미 정렬돼 있으면 0) + 양쪽 1회 스캔
메모리거의 없음build 쪽 크기만큼(work_mem × hash_mem_multiplier)정렬 시 work_mem, 초과 시 디스크 정렬
첫 행 반환빠름 (LIMIT에 유리)해시 빌드 완료 후정렬 완료 후 (이미 정렬돼 있으면 빠름)
위험 신호loops= 값이 큼 + 행 수 추정 오류Batches: N (N > 1) → 디스크 spillSort Method: external merge

Concept

  • 물리적 JOIN(Physical Join) : 논리적 JOIN을 실제로 수행하는 실행 알고리즘. 같은 SQL이라도 옵티마이저가 통계와 비용을 보고 Nested Loop·Hash·Merge 중 하나를 고름
  • Outer / Inner : JOIN 실행 계획에서 바깥 루프를 도는 쪽(driving)과 탐색당하는 쪽. EXPLAIN 트리에서 자식 노드 중 위가 outer, 아래가 inner
  • 등가 조인(Equi-Join) : =로만 이루어진 조인 조건. Hash Join과 Merge Join은 등가 조인에서만 사용 가능
  • 비용 기반 옵티마이저(Cost-Based Optimizer) : 테이블 통계로 행 수를 추정하고 실행 계획별 비용을 계산해 가장 싼 계획을 고르는 옵티마이저. 추정이 틀리면 고른 알고리즘도 틀어짐

1. EXPLAIN ANALYZE 읽는 법 (최소한)#

EXPLAIN (ANALYZE, BUFFERS) -- 실제 실행 + 버퍼 I/O
SELECT ...;
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF) -- 추정 비용 숨기고 실측만
EXPLAIN (COSTS OFF) -- 실행 없이 계획 모양만
  • EXPLAIN만 쓰면 추정 계획, ANALYZE를 붙이면 실제로 실행함 → UPDATE/DELETE는 트랜잭션으로 감싸고 ROLLBACK
  • 조인 알고리즘 판단 시 볼 항목
항목의미확인 포인트
rows= (cost 괄호 안)옵티마이저 추정 행 수실측과 10배 이상 차이 나면 계획이 틀렸을 가능성
actual ... rows=실제 행 수 (loop 1회당)실제 총 행 수 = rows × loops
loops=해당 노드 실행 횟수Nested Loop의 inner는 outer 행 수만큼 반복
Buffers: shared hit/read캐시 적중 / 디스크 읽기 블록 수시간보다 안정적인 I/O 지표
temp read/written디스크 임시 파일 사용해시·정렬이 work_mem을 넘쳤다는 신호

Concept

  • EXPLAIN : 쿼리를 실행하지 않고 옵티마이저가 고른 실행 계획과 추정 비용을 보여주는 명령. 계획의 모양만 확인할 때 사용
  • EXPLAIN ANALYZE : 쿼리를 실제로 실행하고 노드별 실측 행 수·시간·반복 횟수를 함께 보여주는 명령. DML은 실제로 반영되므로 트랜잭션 안에서 ROLLBACK
  • 추정 행 수 vs 실측 행 수 : rows=(추정)와 actual rows=(실측)의 차이. 차이가 크면 통계가 낡았거나 컬럼 상관관계를 모르는 것으로, 잘못된 조인 알고리즘 선택의 1순위 원인
  • BUFFERS 옵션 : 노드별 공유 버퍼 적중(hit)·디스크 읽기(read)·임시 파일(temp) 블록 수를 출력. 캐시 상태에 흔들리는 시간보다 비교 지표로 안정적

2. Nested Loop Join#

2.1 개념#

for each row r in OUTER:
for each row s in INNER where s.key matches r.key: -- 인덱스가 있으면 탐색 1회
emit (r, s)
  • outer 한 행마다 inner를 한 번씩 탐색하는 가장 단순한 방식
  • inner에 조인 키 인덱스가 있으면 한 번 탐색 비용이 O(log N)이 되어 매우 빠름
  • 인덱스가 없으면 inner를 outer 행 수만큼 풀스캔 → O(N × M)
  • 조인 조건 제약이 없어 비등가 조인(<, BETWEEN, 범위 조인)은 Nested Loop만 가능

2.2 사용 상황#

  • OLTP 조회: “고객 5명의 주문” 처럼 outer가 소량이고 inner 조인 키에 인덱스가 있을 때
  • LIMIT이 있는 쿼리: 첫 행을 바로 반환할 수 있어 전체 결과를 다 만들 필요가 없음
  • 비등가 조인: 시간 구간 매칭(event_time BETWEEN start_at AND end_at) 등

2.3 실행 계획 확인#

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT c.name, o.amount
FROM customers c
JOIN orders o ON o.customer_id = c.customer_id
WHERE c.customer_id BETWEEN 1 AND 5;
Nested Loop (actual time=0.008..0.078 rows=56 loops=1)
Buffers: shared hit=74
-> Index Scan using customers_pkey on customers c (actual ... rows=5 loops=1)
Index Cond: ((customer_id >= 1) AND (customer_id <= 5))
-> Bitmap Heap Scan on orders o (actual ... rows=11 loops=5)
Recheck Cond: (c.customer_id = customer_id)
-> Bitmap Index Scan on idx_orders_customer (actual ... rows=11 loops=5)
Index Cond: (customer_id = c.customer_id)
Execution Time: 0.094 ms
  • outer(customers)에서 5행 → inner(orders) 인덱스 탐색 loops=5
  • 버퍼 74블록, 0.094ms. 이 쿼리에서는 Hash Join처럼 orders 100만 행을 다 읽는 것보다 압도적으로 유리

비등가 조인은 Nested Loop 외에 선택지가 없음

EXPLAIN (COSTS OFF)
SELECT * FROM customers c JOIN orders o ON o.amount > c.customer_id
WHERE c.customer_id < 3;
Nested Loop
-> Seq Scan on orders o
-> Memoize
Cache Key: o.amount
-> Index Scan using customers_pkey on customers c
Index Cond: ((customer_id < o.amount) AND (customer_id < 3))
  • Memoize(PG 14+): inner 결과를 파라미터(o.amount)별로 캐시해 같은 값이 반복되면 재탐색 생략

2.4 함정: 추정 오류로 인한 Nested Loop 오선택#

  • Nested Loop는 outer가 작다고 추정될 때 선택됨 → 추정이 틀리면 inner 탐색이 수만 번 반복됨
-- grade='VIP'와 customer_id % 3 = 0 은 이 데이터에서 완전히 같은 행 집합 (상관관계)
EXPLAIN (ANALYZE, TIMING OFF)
SELECT c.customer_id, sum(o.amount)
FROM customers c
JOIN orders o ON o.customer_id = c.customer_id
WHERE c.grade = 'VIP' AND c.customer_id % 3 = 0
GROUP BY c.customer_id;
GroupAggregate (cost=... rows=165 ...) (actual rows=30000 loops=1)
-> Sort (cost=... rows=1650 ...) (actual rows=333334 loops=1)
Sort Method: external merge Disk: 5888kB
-> Nested Loop (cost=... rows=1650 ...) (actual rows=333334 loops=1)
-> Seq Scan on customers c (cost=... rows=165 ...) (actual rows=33333 loops=1)
-> Index Scan using idx_orders_customer on orders o (... rows=11 ...) (actual rows=10 loops=33333)
Execution Time: 294.976 ms
  • 옵티마이저는 두 조건이 독립이라 가정하고 선택도를 곱함 → 추정 165행, 실제 33,333행 (200배 차이)
  • 결과: inner 인덱스 탐색 loops=33333 + 정렬 추정도 틀려 디스크 정렬(external merge)까지 발생
  • 해결: 확장 통계(extended statistics) 로 컬럼 상관관계를 알려줌
CREATE STATISTICS st_c (dependencies) ON grade, (customer_id % 3) FROM customers;
ANALYZE customers;
HashAggregate (cost=... rows=33157 ...) (actual rows=30000 loops=1)
-> Hash Join (cost=... rows=331570 ...) (actual rows=333334 loops=1)
-> Seq Scan on orders o (actual rows=1000000 loops=1)
-> Hash (actual rows=33333 loops=1)
Buckets: 65536 Batches: 1 Memory Usage: 1684kB
-> Seq Scan on customers c (cost=... rows=33157 ...) (actual rows=33333 loops=1)
Execution Time: 161.888 ms
  • 추정 33,157행 ≈ 실측 33,333행 → Hash Join으로 바뀌고 디스크 정렬도 사라짐
  • 힌트로 알고리즘을 강제하기 전에, 먼저 추정 행 수가 맞는지 확인하는 것이 순서

Concept

  • Nested Loop Join : outer의 각 행마다 inner를 탐색해 매칭하는 조인 알고리즘. 조건 제약이 없어 비등가 조인도 처리 가능
  • Index Nested Loop : inner 조인 키에 인덱스가 있어 행마다 인덱스 탐색 1회로 끝나는 Nested Loop. outer가 작을 때 가장 빠른 조인
  • 비등가 조인(Non-Equi Join) : <, >, BETWEEN 등 =가 아닌 조인 조건. 해시·정렬 매칭이 불가능해 Nested Loop로만 수행
  • Memoize : Nested Loop의 inner 결과를 파라미터 값별로 캐싱해 같은 키 재탐색을 생략하는 노드(PostgreSQL 14+). outer에 중복 키가 많을 때 효과적
  • 카디널리티 추정 오류(Cardinality Misestimate) : 옵티마이저의 행 수 추정이 실제와 크게 어긋나는 현상. 작다고 잘못 추정하면 대량 데이터에 Nested Loop가 선택됨
  • 확장 통계(Extended Statistics) : CREATE STATISTICS로 여러 컬럼(또는 표현식) 간 상관관계를 수집하게 하는 기능. 조건 간 독립 가정으로 생기는 과소 추정을 교정

3. Hash Join#

3.1 개념#

-- 1) Build: 작은 쪽(inner)을 조인 키로 해시 테이블 생성
for each row s in INNER: hash_table[hash(s.key)].append(s)
-- 2) Probe: 큰 쪽(outer)을 한 번 스캔하며 해시 테이블 조회
for each row r in OUTER:
for each s in hash_table[hash(r.key)] where s.key = r.key:
emit (r, s)
  • 양쪽을 각각 한 번씩만 스캔 → O(N + M)
  • 인덱스가 필요 없음. 대신 build 쪽을 메모리에 올릴 공간이 필요
  • 해시 테이블이 work_mem × hash_mem_multiplier(PG 15+ 기본 2.0)를 넘으면 배치로 쪼개 디스크에 spill
  • 해시 값 비교라 등가 조인만 가능

3.2 사용 상황#

  • 배치/분석 쿼리: 대량 테이블끼리 조인 후 집계 (DW, ELT, 리포트)
  • 조인 키에 인덱스가 없거나, 있어도 결과 행이 많아 인덱스 탐색이 비효율적일 때
  • 결과에 정렬이 필요 없을 때
  • 한쪽이 확실히 작을 때(dimension) 특히 유리 → 작은 쪽이 build

3.3 실행 계획 확인#

SET max_parallel_workers_per_gather = 0; -- 설명 단순화를 위해 병렬 off
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT c.grade, sum(o.amount)
FROM customers c
JOIN orders o ON o.customer_id = c.customer_id
GROUP BY c.grade;
HashAggregate (actual ... rows=3 loops=1)
-> Hash Join (actual ... rows=1000000 loops=1)
Hash Cond: (o.customer_id = c.customer_id)
-> Seq Scan on orders o (actual ... rows=1000000 loops=1) -- probe (outer)
-> Hash (actual ... rows=100000 loops=1) -- build (inner)
Buckets: 131072 Batches: 1 Memory Usage: 5191kB
-> Seq Scan on customers c (actual ... rows=100000 loops=1)
Execution Time: 370.390 ms
  • Hash 노드 아래가 build 쪽. 작은 customers(10만)로 해시를 만들고 orders(100만)로 probe
  • Batches: 1 → 해시 테이블이 메모리에 다 들어감

3.4 함정: work_mem 초과 시 디스크 spill#

SET work_mem = '1MB';
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF) ... -- 같은 쿼리
-> Hash Join (actual ... rows=1000000 loops=1)
Buffers: shared hit=7447, temp read=2844 written=2844
-> Hash (actual ... rows=100000 loops=1)
Buckets: 65536 Batches: 4 Memory Usage: 1555kB
Buffers: shared hit=575, temp written=279
  • Batches: 4 + temp read/written → 해시 테이블을 4조각으로 나눠 디스크 임시 파일로 처리했다는 의미
  • 이 예제는 테이블이 작고 OS 캐시에 있어 시간 차이가 미미했지만, 실제 대용량에서는 임시 파일 I/O가 Hash Join 성능 저하의 주원인
  • 대응: 세션 단위로 work_mem 상향, build 쪽 행/컬럼 줄이기(필요한 컬럼만 SELECT, 조인 전 필터)

Concept

  • Hash Join : 작은 입력으로 조인 키 해시 테이블을 만들고(build) 큰 입력을 스캔하며 조회(probe)하는 조인 알고리즘. 양쪽을 한 번씩만 읽어 대량 등가 조인에 유리
  • Build / Probe : Hash Join의 두 단계. build는 해시 테이블을 만드는 쪽(작을수록 좋음), probe는 해시 테이블을 조회하며 스캔하는 쪽
  • work_mem : 정렬·해시 연산 하나가 디스크로 넘어가기 전까지 쓸 수 있는 메모리 한도. 쿼리 하나에서 여러 노드가 각각 사용하므로 전역으로 크게 잡으면 위험
  • hash_mem_multiplier : 해시 연산에만 work_mem의 몇 배까지 허용할지 정하는 배수(PG 15+ 기본 2.0). 정렬보다 해시가 메모리 부족에 더 민감하기 때문
  • Batch Spill : 해시 테이블이 메모리 한도를 넘어 여러 배치로 나뉘고 디스크 임시 파일을 쓰는 현상. EXPLAIN의 Batches: N(N > 1)과 temp read/written으로 확인

4. Sort Merge Join#

4.1 개념#

sort OUTER by key; sort INNER by key -- 이미 정렬돼 있으면 생략
r = first(OUTER); s = first(INNER)
while both not exhausted:
if r.key < s.key: advance r
elif r.key > s.key: advance s
else: emit all matching pairs, advance
  • 양쪽을 조인 키로 정렬한 뒤 지퍼처럼 동시에 훑어 매칭
  • 정렬 비용 O(N log N + M log M) + 병합 O(N + M)
  • 이미 정렬된 입력(인덱스 스캔, 정렬된 서브쿼리)이면 정렬 비용이 사라져 가장 효율적
  • 결과가 조인 키 순서로 정렬된 채 나오므로 상위 ORDER BY/GROUP BY/DISTINCT가 정렬을 재사용
  • PostgreSQL의 Merge Join은 merge 가능한 등가 조건에서만 사용 (범위 조인 불가)

4.2 사용 상황#

  • 양쪽 테이블 모두 조인 키 인덱스가 있거나 이미 정렬된 결과를 조인할 때
  • 결과를 조인 키 순서로 정렬해서 받아야 할 때 (ORDER BY join_key)
  • 양쪽 모두 커서 해시 테이블이 메모리에 안 들어갈 때 — 외부 정렬은 Hash spill보다 성능 저하가 완만한 경우가 많음

4.3 실행 계획 확인#

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT c.customer_id, o.order_id
FROM customers c
JOIN orders o ON o.customer_id = c.customer_id
ORDER BY c.customer_id;
Merge Join (actual time=0.007..484.349 rows=1000000 loops=1)
Merge Cond: (c.customer_id = o.customer_id)
Buffers: shared hit=1001937
-> Index Only Scan using customers_pkey on customers c (actual ... rows=90001 loops=1)
-> Index Scan using idx_orders_customer on orders o (actual ... rows=1000000 loops=1)
Buffers: shared hit=1001173
Execution Time: 505.697 ms
  • 양쪽 다 인덱스 순서로 읽어 별도 Sort 노드 없이 병합, 결과가 이미 customer_id 순이라 ORDER BY용 정렬도 없음
  • actual time=0.007..: 첫 행이 즉시 나옴 (Hash Join은 build가 끝나야 첫 행)
  • 단, orders 쪽 Buffers: shared hit=1001173 → 행 100만 개에 블록 접근 100만 번
    • orders는 customer_id 순으로 물리 저장돼 있지 않아 인덱스 순서로 읽으면 힙을 랜덤 접근함
    • 같은 데이터를 Seq Scan으로 읽으면 6,872블록. 이 예제는 전부 캐시에 있어서 괜찮았지만, 디스크라면 Hash Join보다 훨씬 느려질 수 있음
    • 물리 정렬 상태는 pg_stats.correlation(1 또는 -1에 가까울수록 정렬됨)로 확인
SELECT tablename, attname, correlation
FROM pg_stats WHERE tablename = 'orders' AND attname = 'customer_id';

Concept

  • Sort Merge Join : 양쪽 입력을 조인 키로 정렬한 뒤 두 포인터를 전진시키며 매칭하는 조인 알고리즘. 이미 정렬된 입력이면 정렬 비용 없이 선형 시간
  • Interesting Order : 상위 연산(ORDER BY, GROUP BY, Merge Join)이 재사용할 수 있는 정렬 순서. 옵티마이저는 비용 계산 시 정렬을 공짜로 얻는 계획을 우대
  • External Merge Sort : 정렬 데이터가 work_mem을 넘으면 정렬된 조각을 디스크에 쓰고 병합하는 정렬 방식. EXPLAIN의 Sort Method: external merge Disk: ...
  • Correlation(물리 정렬도) : 컬럼 값 순서와 테이블의 물리 저장 순서가 얼마나 일치하는지를 나타내는 통계(-1 ~ 1). 낮으면 인덱스 순서 스캔이 랜덤 I/O가 됨
  • Startup Cost vs Total Cost : 첫 행을 내기까지의 비용과 전체 행을 내기까지의 비용. LIMIT이 있으면 startup이 작은 Nested Loop·정렬된 Merge가 유리

5. PostgreSQL에서 알고리즘 강제하기#

  • PostgreSQL은 Oracle식 힌트 구문을 기본 지원하지 않음 → 두 가지 방법 사용
    1. enable_* 플래너 파라미터로 특정 알고리즘을 비활성화(사실상 비용 패널티)
    2. pg_hint_plan 확장으로 주석 힌트 사용
  • 둘 다 진단·비교용으로 먼저 쓰고, 운영 쿼리에 고정하는 건 최후 수단 (데이터가 바뀌면 힌트가 오히려 독이 됨)

5.1 enable_* 파라미터 (기본 내장)#

파라미터끄면
enable_nestloopNested Loop 회피 (다른 방법이 불가능하면 여전히 사용)
enable_hashjoinHash Join 회피
enable_mergejoinMerge Join 회피
enable_memoizeMemoize 노드 회피 (PG 14+)
BEGIN;
SET LOCAL max_parallel_workers_per_gather = 0;
SET LOCAL enable_hashjoin = off; -- Hash 끄면 → Merge Join 선택됨
EXPLAIN (ANALYZE, COSTS OFF) SELECT c.grade, sum(o.amount) FROM customers c JOIN orders o ON o.customer_id = c.customer_id GROUP BY c.grade;
SET LOCAL enable_mergejoin = off; -- Merge까지 끄면 → Nested Loop
EXPLAIN (ANALYZE, COSTS OFF) SELECT c.grade, sum(o.amount) FROM customers c JOIN orders o ON o.customer_id = c.customer_id GROUP BY c.grade;
ROLLBACK; -- SET LOCAL은 트랜잭션 종료 시 원복

같은 대량 집계 쿼리의 알고리즘별 실측 (100만 행, 전부 캐시 상태)

알고리즘핵심 노드Execution Time
Hash Join (기본 선택)Hash ... Batches: 1370 ms
Merge Join (enable_hashjoin=off)양쪽 Index Scan, Sort 없음474 ms
Nested Loop (hash, merge off)inner Index Scan loops=100000594 ms
  • 전부 메모리에 있는 상황이라 차이가 1.6배 정도에 그쳤음. inner 랜덤 I/O가 디스크로 가면 Nested Loop·인덱스 Merge의 격차는 훨씬 커짐
  • SET은 세션 전체에 영향 → 실험할 때는 SET LOCAL + 트랜잭션, 또는 끝나고 RESET ALL

5.2 pg_hint_plan 확장#

-- 설치 (Debian/Ubuntu PGDG 저장소 기준)
-- apt install postgresql-16-pg-hint-plan
LOAD 'pg_hint_plan'; -- 세션 단위 로드. 상시 사용은 shared_preload_libraries에 추가
힌트의미
NestLoop(a b) / HashJoin(a b) / MergeJoin(a b)a, b 조인에 해당 알고리즘 사용
NoNestLoop(a b) 등해당 알고리즘 금지
Leading((a b))조인 순서 + 방향 고정. a가 outer, b가 inner
SeqScan(t) / IndexScan(t idx)테이블 접근 방식 지정
Rows(a b #1000)a⋈b 결과 행 수 추정치를 교정 (# 고정, * 배수, +/- 가감)
  • 힌트에는 테이블 별칭을 써야 함 (c, o)
  • 힌트 주석은 쿼리 맨 앞의 /*+ ... */ 블록만 인식
EXPLAIN (COSTS OFF)
/*+ NestLoop(c o) */
SELECT c.grade, sum(o.amount) FROM customers c JOIN orders o ON o.customer_id = c.customer_id GROUP BY c.grade;
HashAggregate
-> Nested Loop
-> Seq Scan on customers c
-> Index Scan using idx_orders_customer on orders o
Index Cond: (customer_id = c.customer_id)

Hash Join의 build 쪽은 Leading으로 결정 — 안쪽(두 번째)에 쓴 테이블이 build

/*+ HashJoin(c o) Leading((o c)) */ -- o가 probe, c가 build
SELECT c.name, o.amount FROM customers c JOIN orders o ON o.customer_id = c.customer_id
WHERE c.customer_id BETWEEN 1 AND 5;
Hash Join
Hash Cond: (o.customer_id = c.customer_id)
-> Seq Scan on orders o
-> Hash
-> Index Scan using customers_pkey on customers c
  • Leading((c o))로 바꾸면 orders 100만 행을 build하는 계획이 나옴 → 방향이 중요한 이유

힌트가 실제로 적용됐는지 확인

SET pg_hint_plan.debug_print = on;
SET client_min_messages = log;
LOG: pg_hint_plan:
used hint:
HashJoin(c o)
not used hint:
duplication hint:
error hint:
  • 별칭 오타나 문법 오류는 에러 없이 조용히 무시되므로 used hint에 나오는지 반드시 확인

Concept

  • enable_* 플래너 파라미터 : 특정 조인·스캔 방식에 큰 비용 패널티를 줘 사실상 비활성화하는 PostgreSQL 내장 설정. 다른 방법이 없으면 여전히 선택되므로 강제가 아닌 회피
  • SET LOCAL : 현재 트랜잭션 안에서만 유효한 설정 변경. 실험 후 COMMIT/ROLLBACK 시 자동 원복되어 세션 오염을 방지
  • pg_hint_plan : 쿼리 앞 주석(/*+ ... */)으로 조인 방식·순서·스캔 방식·행 수 추정을 지정하게 해주는 PostgreSQL 확장. 잘못된 힌트는 에러 없이 무시됨
  • Leading 힌트 : 조인 순서와 outer/inner 방향을 고정하는 힌트. Leading((a b))에서 a가 outer, b가 inner(Hash Join이면 build)
  • Rows 힌트 : 알고리즘을 직접 지정하는 대신 특정 조인 결과의 추정 행 수를 교정해 옵티마이저가 스스로 올바른 계획을 고르게 하는 힌트
  • Plan Pinning의 위험 : 힌트로 계획을 고정하면 데이터 분포가 바뀌어도 계획이 따라가지 못함. 통계·인덱스·쿼리 수정으로 해결이 안 될 때만 사용

6. 언제 무엇을 쓰는가 — 판단 흐름#

조인 조건이 등가(=)인가?
├─ 아니오 ──────────────────────────────▶ Nested Loop (유일한 선택지, inner 인덱스 확보가 관건)
└─ 예
├─ outer 결과가 소량 + inner 조인 키에 인덱스? ──▶ Nested Loop
├─ 양쪽이 이미 조인 키로 정렬(인덱스, 물리 정렬도 높음)
│ 또는 결과를 조인 키로 정렬해야 함? ───────────▶ Sort Merge
└─ 그 외 (대량 vs 대량, 인덱스 없음, 정렬 불필요) ─▶ Hash Join (작은 쪽 build)

옵티마이저가 기대와 다른 알고리즘을 골랐을 때 점검 순서

  1. 추정 vs 실측 행 수 비교 (EXPLAIN ANALYZE) — 10배 이상 차이 나는 노드 찾기
  2. 차이가 있다면: ANALYZE 재수집 → ALTER TABLE ... ALTER COLUMN ... SET STATISTICS 상향 → CREATE STATISTICS(상관 컬럼)
  3. 조인 키 인덱스 유무와 물리 정렬도(pg_stats.correlation) 확인
  4. temp read/written이 있으면 work_mem 조정
  5. 그래도 안 되면 enable_* / pg_hint_plan으로 비교 실험 → 효과가 확실할 때만 힌트 고정

Concept

  • 조인 알고리즘 선택 기준 : 조인 조건 종류(등가 여부), 입력 크기, 조인 키 인덱스 유무, 정렬 상태, 메모리 한도. 이 다섯 가지로 Nested Loop·Hash·Merge 중 하나가 결정됨
  • 소량 + 인덱스 → Nested Loop : outer가 작고 inner 조인 키에 인덱스가 있으면 탐색 횟수가 적어 가장 빠름. OLTP 단건·소량 조회의 기본
  • 대량 + 등가 → Hash Join : 인덱스 없이 양쪽을 한 번씩만 스캔. 배치·분석 쿼리의 기본이며 작은 쪽을 build로 둬야 함
  • 정렬된 입력 → Sort Merge : 이미 정렬돼 있거나 결과 정렬이 필요하면 정렬 비용을 공유할 수 있어 유리. 물리 정렬도가 낮은 인덱스 스캔은 랜덤 I/O 주의
  • 통계 먼저, 힌트는 나중 : 잘못된 알고리즘 선택의 대부분은 행 수 추정 오류에서 시작됨. 통계를 고치면 옵티마이저가 스스로 올바른 계획을 고름

관련 글#

추가적으로 공부하면 좋은 컨셉, 주제들#

  • Parallel Hash Join : 여러 워커가 공유 해시 테이블을 함께 빌드·조회하는 PostgreSQL 병렬 조인 (Parallel Hash 노드)
  • join_collapse_limit / from_collapse_limit : 옵티마이저가 조인 순서를 탐색하는 테이블 수 한도. 테이블이 많으면 GEQO(유전 알고리즘)로 전환
  • Hash Join Skew 처리 : 특정 키에 행이 몰릴 때 배치 분할이 무력해지는 문제와 PostgreSQL의 skew 최적화
  • auto_explain : 느린 쿼리의 실행 계획을 자동으로 로그에 남기는 확장. 운영 환경에서 계획 변화 추적에 사용
  • Bitmap Heap Scan : 인덱스로 매칭 위치를 먼저 모은 뒤 힙을 물리 순서로 읽어 랜덤 I/O를 줄이는 스캔 방식
[SQL]Join 알고리즘: Nested Loop vs Hash vs Sort Merge
https://yjinheon.netlify.app/posts/02de/06-sql/de-sql-join-algorithms/
Author
Datamind
Published at
2026-10-24
License
CC BY-NC-SA 4.0