조인 최적화: nested loop, hash join, merge join과 통계 정보

조인은 SQL 성능에서 가장 많이 오해받는 영역이다

JOIN이 들어간 쿼리가 느리면 "조인 때문에 느리다"고 말하기 쉽다. 그러나 조인이 느린 건 대부분 조인 알고리즘 자체의 문제가 아니다. 입력이 너무 크거나, optimizer가 잘못된 알고리즘을 선택했거나, 통계 정보가 낡아서 cardinality를 잘못 추정했거나, 인덱스가 없어 inner side를 반복해서 읽기 때문이다.

조인 최적화는 세 가지 레이어로 나뉜다.

1. 조인 알고리즘 이해: nested loop, hash join, merge join은 언제 선택되고, 각각 어떤 조건에서 빠른가.
2. optimizer가 선택하는 기준: 통계 정보, cardinality 추정, cost model.
3. 잘못된 선택을 만나는 패턴과 개선: cardinality 오차, index 부재, join order, statistics 갱신.

세 가지 조인 알고리즘

Nested Loop Join: 작은 입력 + indexed inner

Nested Loop는 개념이 단순하다. 외부(outer) 입력의 각 row에 대해 내부(inner) 입력을 조회한다.

for each row R in outer:
    for each row S in inner where S.key = R.key:
        output (R, S)

비용은 outer rows × inner access cost다. 내부 접근이 index seek라면 inner access cost가 매우 낮다. 예를 들어 outer가 20 row이고 inner를 PK로 20번 seek하면, 총 비용은 20번의 random index read 정도다.

Nested Loop가 강한 경우:

• outer 입력이 작다(수십~수백 row).
• inner side에 join key에 대한 인덱스가 있다.
• LIMIT이 있어 조기에 멈출 수 있다.

Nested Loop가 위험한 경우:

• outer가 수십만 row로 커진다 → inner를 수십만 번 반복 접근한다.
• inner에 인덱스가 없다 → 매번 full table scan.
• cardinality 오차로 optimizer가 outer가 작다고 잘못 예상한다.

Hash Join: 큰 입력 두 개의 equi-join

Hash Join은 한쪽 입력(보통 작은 쪽, build side)으로 hash table을 만들고, 다른 쪽(probe side)을 읽으면서 hash table을 탐색해 매칭한다.

-- Build phase: 작은 입력으로 hash table 생성
build_table = {}
for each row S in smaller_input:
    build_table[hash(S.key)] = S

-- Probe phase: 큰 입력을 읽으며 hash 조회
for each row R in larger_input:
    if hash(R.key) in build_table:
        output (R, build_table[R.key])

비용은 양쪽 입력을 각 한 번씩 읽고 hash table 연산을 더한 것이다. 따라서 두 테이블이 크더라도 각각 한 번 읽는 비용에 memory가 허용한다면 효율적이다.

Hash Join이 강한 경우:

• 두 입력이 모두 크다.
• join key에 적합한 인덱스가 없다.
• equi-join(=)일 때만 적용 가능.
• build side가 memory 안에 들어온다.

Hash Join의 위험:

• build side가 메모리를 초과하면 disk로 spill(grace hash join, hybrid hash join). spill이 발생하면 성능이 급락할 수 있다.
• cardinality 오차로 build side를 잘못 선택하면 memory 부족이나 불필요한 spill이 생긴다.
• MySQL 8.0.18+에서는 inner equi-join에 hash join이 도입됐다. MySQL은 merge join을 일반적으로 지원하지 않는다.

Merge Join: 정렬된 입력의 일직선 스캔

Merge Join(sort-merge join)은 양쪽 입력이 join key로 이미 정렬되어 있을 때 두 포인터를 동시에 앞으로 이동하며 일치하는 행을 출력한다.

-- 두 입력이 join key로 정렬되어 있다고 가정
pointer_R = start of R
pointer_S = start of S

while R and S have rows:
    if R.key == S.key:
        output (R, S); advance both
    elif R.key < S.key:
        advance R
    else:
        advance S

양쪽 입력을 각 한 번씩 읽는다. 이미 정렬된 상태라면 매우 빠르다. 하지만 정렬되어 있지 않으면 먼저 sort가 필요하다.

Merge Join이 강한 경우:

• 양쪽 입력이 join key로 이미 정렬되어 있다(index scan이 정렬된 순서를 보장할 때).
• 큰 입력 두 개를 조인해야 하고 equi-join이며, hash join보다 메모리 효율이 중요할 때.
• ORDER BY, window function과 함께 최종 결과도 join key 순서로 정렬해야 할 때.

Merge Join의 단점:

• 정렬 비용이 높을 수 있다. 정렬이 추가된 merge join은 hash join보다 느릴 수 있다.
• non-equi-join(range join)에는 사용하기 어렵다.

알고리즘 선택 기준 한눈에 보기

Optimizer는 어떻게 조인 알고리즘을 선택하는가: 통계와 cost model

조인 알고리즘 선택은 optimizer의 cost-based 결정이다. optimizer는 가능한 플랜 후보들의 비용을 추정하고 가장 낮은 비용을 선택한다. 비용 추정의 핵심은 각 단계를 통과하는 row 수(cardinality) 추정이다.

통계 정보란 무엇인가

PostgreSQL의 경우 ANALYZE 명령을 실행하면 pg_statistic 카탈로그에 각 컬럼의 통계가 저장된다. 이 통계에는 다음이 포함된다.

• distinct count: 해당 컬럼의 unique 값 수 추정.
• most common values (MCV): 가장 자주 나타나는 값과 그 빈도.
• histogram: 값 분포를 등분한 구간별 경계.
• null fraction: NULL 비율.

MySQL도 유사하게 ANALYZE TABLE로 통계를 갱신한다. information_schema.COLUMN_STATISTICS에서 히스토그램을 확인할 수 있다. SQL Server는 Query Store와 Statistics auto-update로 통계를 관리한다.

Cardinality 추정의 한계

통계 기반 cardinality 추정은 몇 가지 제한된 가정을 전제한다.

1. 균등 분포 가정: 히스토그램 구간 안에서 값이 균일하게 분포한다고 가정한다. 실제 데이터는 skewed distribution을 가지는 경우가 많다.
2. 컬럼 독립성 가정: 두 컬럼의 조건이 독립적이라고 가정한다. 예를 들어 country = 'KR' AND city = 'Seoul'에서 city 값은 country에 따라 강하게 종속되지만 optimizer는 두 조건이 독립적이라고 추정할 수 있다.
3. 조인 key overlap 가정: 두 테이블의 join key 값 범위가 겹친다고 가정한다. 한쪽에만 있는 값이 많으면 추정이 틀린다.

이 가정들이 깨지면 cardinality 추정이 크게 빗나가고, 이로 인해 잘못된 조인 알고리즘이나 조인 순서가 선택된다. PostgreSQL 10+에서는 CREATE STATISTICS로 multi-column statistics를 만들어 컬럼 간 상관관계를 통계로 반영할 수 있다.

-- PostgreSQL: country와 city의 상관관계를 통계에 반영
CREATE STATISTICS stts_country_city ON country, city FROM locations;
ANALYZE locations;

조인 순서와 cardinality

세 테이블 A, B, C를 조인할 때 어떤 순서로 조인하느냐에 따라 중간 결과의 크기가 달라지고, 그에 따라 전체 비용이 크게 달라진다. optimizer는 join reordering으로 가장 낮은 비용의 순서를 탐색한다.

일반 원칙: 조인 순서에서 먼저 row 수를 줄여라. 선택도가 높은 조건이 있는 테이블을 먼저 좁히고, 그 결과를 다음 테이블과 조인하면 중간 결과가 작아진다.

-- orders가 millions of rows, filtered_orders가 수십 rows라면
-- filtered_orders를 먼저 좁히고 customers와 조인하는 것이 낫다.
SELECT c.name, fo.total_amount
FROM customers c
JOIN orders fo ON fo.customer_id = c.id
WHERE fo.created_at >= '2026-06-01'
  AND fo.status = 'PAID';

Cardinality 오차가 만드는 대표 장애 패턴

패턴 1: Nested Loop가 폭주한다

optimizer가 outer를 100 row로 추정했는데 실제로 1,000,000 row가 들어온다. nested loop는 inner를 1,000,000번 탐색하고, 인덱스 seek를 1,000,000번 실행한다. I/O와 CPU가 폭주하며 쿼리가 수분~수십분으로 늘어난다.

확인 방법: EXPLAIN ANALYZE에서 nested loop node의 loops 수와 estimated rows vs actual rows를 본다.

Nested Loop  (cost=0.43..500.00 rows=100) (actual rows=1000000 loops=1)

이처럼 estimated rows와 actual rows가 10,000배 차이가 나면 통계 문제를 의심한다.

개선 방법: 통계 갱신(ANALYZE), predicate 순서 조정, join hint(PostgreSQL은 enable_nestloop = off 세션 설정으로 우회), outer를 먼저 좁히는 서브쿼리.

패턴 2: Hash Join이 spill한다

optimizer가 build side를 10MB로 추정했는데 실제로 2GB다. 메모리 한도를 넘어 디스크로 spill이 발생한다. 디스크 I/O로 인해 쿼리 시간이 10배 이상 늘어날 수 있다.

확인 방법: PostgreSQL EXPLAIN (ANALYZE, BUFFERS)의 Sort/HashAggregate 노드에서 disk 사용 여부. MySQL Performance Schema의 memory/sql/JOIN_CACHE. SQL Server의 Spill 경고.

개선 방법: 통계 갱신, work_mem(PostgreSQL) / join_buffer_size(MySQL) 증가, build side를 줄이는 필터 추가, 인덱스 추가로 nested loop 또는 merge join으로 전환.

패턴 3: Sort + Merge Join 추가 비용

optimizer가 merge join을 선택했지만 양쪽 입력이 이미 정렬되어 있지 않아 sort step이 추가된다. sort 비용이 join 비용보다 훨씬 크면 hash join보다 느려진다.

확인 방법: 실행계획에서 merge join 앞에 sort node가 보이고, sort의 estimated rows가 크다.

개선 방법: join key 순서로 정렬된 인덱스 추가, hash join으로 전환 유도(enable_mergejoin = off), 또는 쿼리 rewrite.

통계 관리 실전

통계가 낡으면 optimizer가 잘못된 플랜을 선택한다. 운영 환경에서는 다음을 주의한다.

언제 통계가 낡는가

• 대량 INSERT/DELETE/UPDATE 직후(배치 작업, 마이그레이션, 파티션 교체).
• 처음 데이터가 채워진 테이블.
• 분포가 skewed한 컬럼에 새 값이 추가됐을 때.
• auto-analyze가 실행될 interval보다 빠르게 데이터가 변한다.

PostgreSQL 통계 확인과 갱신

-- 통계가 오래된 테이블 확인
SELECT schemaname, relname, n_live_tup, n_dead_tup, last_analyze, last_autoanalyze
FROM pg_stat_user_tables
WHERE last_analyze < now() - interval '7 days'
ORDER BY n_live_tup DESC;

-- 특정 테이블 통계 강제 갱신
ANALYZE orders;

-- statistics_target 높이기: 중요 컬럼은 더 정밀한 히스토그램
ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 500;
ANALYZE orders;

기본 default_statistics_target은 100이다. cardinality 추정이 틀린 컬럼은 target을 높여 히스토그램을 세밀하게 만들면 추정 정확도가 올라간다.

MySQL 통계 확인과 갱신

-- 테이블 통계 상태 확인
SELECT table_name, table_rows, update_time
FROM information_schema.tables
WHERE table_schema = 'mydb'
ORDER BY table_rows DESC;

-- 강제 통계 갱신
ANALYZE TABLE orders;

-- 히스토그램 생성 (MySQL 8.0+)
ANALYZE TABLE orders UPDATE HISTOGRAM ON customer_id, status WITH 100 BUCKETS;

MySQL의 InnoDB 통계는 innodb_stats_persistent=ON이면 mysql.innodb_table_stats에 저장된다. ANALYZE TABLE로 명시적으로 갱신하거나 innodb_stats_auto_recalc=ON(기본값)으로 자동 갱신된다.

조인 최적화 실전 워크플로우

체크리스트

조인이 포함된 느린 쿼리를 보는 순서:

1. EXPLAIN ANALYZE에서 estimated rows와 actual rows가 처음 크게 벗어나는 node를 찾는다.
2. nested loop의 loops 수가 예상보다 훨씬 많지 않은가?
3. hash join node에서 disk 사용(spill)이 발생했는가?
4. merge join 앞에 추가 sort step이 있는가?
5. 통계가 최근 갱신되었는가? (last_analyze, UPDATE HISTOGRAM)
6. join key에 인덱스가 있는가? inner side의 random access가 최소화되는가?
7. 조인 순서가 row 수를 먼저 줄이는 방향인가? (선택도가 높은 테이블을 먼저)
8. 쿼리 rewrite로 outer를 먼저 좁힐 수 있는가?

조인 방식을 수동으로 유도할 때의 주의사항

optimizer가 잘못된 플랜을 선택한다고 확인된 경우에만 힌트나 세션 설정으로 개입한다.

힌트나 세션 설정은 임시 완화다. 근본 원인(통계 갱신, 인덱스 추가, 쿼리 rewrite)을 해결한 뒤에는 힌트를 제거한다. 힌트를 코드베이스에 남겨두면 데이터 분포가 바뀐 뒤에도 잘못된 플랜이 고정되는 문제가 생긴다.

References

• PostgreSQL Documentation, "14.3. Controlling the Planner with Explicit JOIN Clauses" — https://www.postgresql.org/docs/current/explicit-joins.html
• PostgreSQL Documentation, "14.2. Statistics Used by the Planner" — https://www.postgresql.org/docs/current/planner-stats.html
• MySQL 8.4 Reference Manual, "10.2.1.4 Hash Join Optimization" — https://dev.mysql.com/doc/refman/8.4/en/hash-joins.html
• Netdata Academy, "PostgreSQL Cardinality Estimation & Tuning Tips" — https://www.netdata.cloud/academy/cardinality-estimation-in-postgres/
• Medium – Philip McClarence, "PostgreSQL Join Optimization: Nested Loop, Hash, and Merge" — https://medium.com/@philmcc/postgresql-join-optimization-nested-loop-hash-and-merge-c87b86373908
• Rafael Rampineli on Medium, "Optimizing SQL Server: Understanding Nested Loops, Hash Match, Merge Join, and Adaptive Join" — https://rafaelrampineli.medium.com/optimizing-sql-server-joins-understanding-nested-loops-hash-match-merge-join-and-adaptive-join-5ba57fcf6ec3
• Chessman7 Substack, "Database Join Algorithms: The Hidden Mechanics Behind SQL Query Execution" — https://chessman7.substack.com/p/database-join-algorithms-the-hidden
• use-the-index-luke.com, "Anatomy of an Index" — https://use-the-index-luke.com/sql/anatomy