조인 방식(중첩 루프 · 해시 · 정렬 병합)Join Methods
두 입력의 행을 조인 조건으로 짝짓는 실행 계획 노드의 알고리즘으로, 바깥 행마다 안쪽을 찾는 중첩 루프 · 한쪽으로 해시 표를 만들어 다른 쪽이 찾는 해시 조인 · 두 입력을 조인 키 순으로 나란히 읽는 정렬 병합 조인이 있다.
1요약
- 조인 방식은 옵티마이저가 조인 순서와 함께 고르는 조인 노드의 알고리즘이며, 중첩 루프 · 정렬 병합 · 해시 조인 세 가지가 PostgreSQL 계획의 Nested Loop · Merge Join · Hash Join 노드로 남아 있다(PostgreSQL 51.5.1) — 이 위에서 표 둘 이상을 잇는 모든 SELECT · 뷰가 돈다.
- 같은 두 표라도 방식에 따라 블록 전송이 4,010,000(인덱스 중첩 루프)과 42,000(해시 조인)으로 약 95배 갈리고(설명용 가정 값 · Silberschatz 2019 비용 식), 해시 표가 메모리를 넘치면 같은 해시 조인도 전송이 3배가 된다.
- 「조인이 느리다」는 계획 노드 이름과 숫자 하나로 가른다 — Nested Loop 이면 안쪽 loops 가 추정보다 큰가, Hash Join 이면 Batches 가 1 보다 큰가, Merge Join 이면 아래 Sort 가 디스크로 갔는가.
2등장 배경
정규화로 나뉜 표는 질의마다 다시 이어야 하고, 디스크 블록을 어떤 순서로 읽느냐에 따라 같은 결과의 비용이 자릿수로 갈린다. 외부 행마다 안쪽 표를 처음부터 다시 읽는 가장 단순한 방법은 안쪽 표를 외부 행 수만큼 읽는다(MySQL 10.2.1.7). 그래서 «무엇을 먼저 읽고 무엇을 메모리에 둘지»가 관계형 DBMS 초기부터 성능의 중심이었다.
1977년 IBM 의 Blasgen · Eswaran 은 중첩 루프와 정렬 병합을 포함한 조인 방법들의 비용을 견줬고, 1979년 System R 옵티마이저는 중첩 루프와 병합 스캔 두 방식을 비용으로 골랐다(Selinger 1979 5절). 1983년 Kitsuregawa 등은 데이터베이스 머신을 위해 두 입력을 해시로 나눠 처리하는 GRACE 해시 조인을 냈고, 1986년 Shapiro 는 메모리가 크면 해시 계열이 정렬 병합을 이기며 그중 하이브리드 해시가 가장 낫다고 보였다 — 당시 상용 시스템은 정렬 병합 중심이고 해시 조인을 구현하지 않았다(Shapiro 1986 초록).
지금 PostgreSQL 은 조인 쌍마다 세 방식의 계획을 모두 만들어 추정 비용이 가장 낮은 것을 고른다(PostgreSQL 51.5.1). MySQL 은 8.0.18 에서 해시 조인을 넣고 8.0.20 에서 블록 중첩 루프 지원을 없애 그 방식을 쓰던 조인을 모두 해시 조인으로 바꿨다(MySQL 8.0 해시 조인 절).
3쉽게 이해하기 — 응모권과 당첨자 명단 맞추기
경품 담당 민지 씨는 응모권 10,000장과 당첨자 명단 400명을 받아, 이름이 맞는 응모권만 골라내야 한다. 응모권 한 장마다 명단 400명을 처음부터 훑으면 400만 번을 대조한다. 그래서 민지 씨는 명단을 이름 첫 자음별 상자 14개에 나눠 두고, 응모권마다 그 자음 상자 하나만 연다. 상자가 책상에 다 올라가지 않으면 자음 묶음별로 창고에 내려 두고 한 묶음씩 올려 맞춘다.
그림 1 · 응모권과 명단의 짝을 찾는 방법은 셋이고 결과는 같다 — 어느 방법이 덜 수고로운지는 옵티마이저가 고른다.
그림 2 · 상자를 나눠 두면 응모권마다 상자 하나만 열면 되고, 책상이 좁아 창고를 쓰면 걸음이 늘듯 해시 표가 메모리를 넘치면 분할 파일을 쓰고 다시 읽는다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 응모권 10,000장 | 큰 입력(프로브 쪽) | 행마다 짝을 찾는다 |
| 당첨자 명단 400명 | 작은 입력(빌드 쪽) | 해시 표 · 정렬 · 외부 루프의 재료가 된다 |
| 응모권마다 명단 전체 훑기 | 중첩 루프 | 외부 행마다 안쪽 입력을 다시 읽는다 |
| 가나다 색인 탭이 달린 명단 | 인덱스 중첩 루프 | 안쪽 조인 키의 B+트리로 바로 찾는다 |
| 첫 자음 상자 14개 | 해시 표 · 버킷 | 조인 키의 해시 값으로 나눈 구역 |
| 창고에 내려 둔 묶음 | 배치 · 분할 파일 | 메모리를 넘친 해시 표를 디스크에 나눠 둔다 |
| 둘 다 가나다 순으로 놓고 나란히 넘기기 | 정렬 병합 조인 | 조인 키 순인 두 입력을 한 번씩 읽는다 |
| 짝이 맞은 응모권 | 조인 결과 행 | 조건을 만족한 두 행을 이어 내보낸다 |
⚠ 비유가 맞지 않는 곳: 첫 자음은 「ㅇ」 상자에만 사람이 몰리듯 고르지 않지만, 실제 해시 함수는 키 값을 버킷 수에 고르게 흩고 같은 버킷 안에서도 키를 다시 비교한다. 또 민지 씨는 방법을 스스로 고르지만 DBMS 에서는 옵티마이저가 추정 행 수로 고른다.
4구조 · 동작 — 출고 표와 상품 표의 조인
조인 노드는 두 자식(외부 · 내부, 또는 프로브 · 빌드)을 받아 짝지은 행을 위로 올린다. 세 방식은 두 입력을 «몇 번 읽는가»와 «메모리에 무엇을 두는가»가 다르다(PostgreSQL 51.5.1).
| 요소 | 역할 | 값 | 근거 |
|---|---|---|---|
| 외부 입력 | 중첩 루프에서 한 행씩 내주는 쪽 · EXPLAIN 의 첫 자식 | 작은 쪽 · 조건으로 걸러진 쪽 | PostgreSQL 14.1.1 |
| 내부 입력 | 외부 행마다 다시 실행 · loops = 외부 행 수 | 조인 키 색인이 있으면 행마다 B+트리 탐색 | 14.1.1 · 14.1.2 |
| 해시 표(빌드 쪽) | 한 입력을 조인 키 해시로 담는 Hash 노드 | 한도 = work_ | 19.4.1 |
| 프로브 쪽 | 행마다 해시 값의 버킷만 비교 | Hash Cond | 51.5.1 · 14.1.2 |
| 배치(분할) | 해시 표가 한도를 넘으면 두 입력을 같은 해시로 나눠 디스크에 씀 | Batches > 1 · 전송 3(b_ | 14.1.2 · Shapiro 1986 |
| 정렬 · 병합 | 두 입력을 조인 키 순으로 만든 뒤 한 번씩 읽음 | Sort 노드 또는 색인 순서 · Merge Cond | 51.5.1 · 14.1.1 |
| Memoize | 중첩 루프 안쪽 탐색 결과를 매개변수별로 캐시 | enable_ | 19.7.1 |
| MySQL 조인 버퍼 | 해시 조인 메모리 한도 · 넘치면 디스크 파일 | join_ | MySQL 10.2.1.4 · 시스템 변수 |
설명용 가정 값 — 출고 표 shipment(1,000,000행 · 10,000블록 · ship_date 색인)와 상품 표 product(400,000행 · 4,000블록 · id 기본 키 B+트리 높이 3), 작업 메모리 M = 102블록이다. 비용은 교과서 식의 블록 전송 수로 셈하고 탐색 시간 · CPU 는 뺐다(Silberschatz 2019).
SELECT s.id, p.name
FROM shipment s JOIN product p ON p.id = s.product_id;
-- 6단계는 WHERE s.ship_date = DATE '2026-11-18' 을 더한 경우
- 조인 조건 p.id = s.product_id 는 같음 조건이라 세 방식 모두 후보가 되고, 작은 product(4,000블록)를 블록 중첩 루프의 외부 · 해시 조인의 빌드 쪽으로 놓는다.
- 블록 중첩 루프 — product 를 M − 2 = 100블록씩 40번 올리고 그때마다 shipment 10,000블록을 다 읽는다: ⌈4,000 / 100⌉ × 10,000 + 4,000 = 404,000.
- 인덱스 중첩 루프 — shipment 행마다 product 기본 키를 B+트리 3블록 + 데이터 1블록 = 4블록으로 찾는다: 10,000 + 1,000,000 × 4 = 4,010,000.
- 정렬 병합 — 두 표를 조인 키 순으로 외부 정렬(런 만들기 읽기 · 쓰기 + 병합 1패스 읽기 · 쓰기 = 4b)한 뒤 나란히 한 번 읽는다: 5 × (4,000 + 10,000) = 70,000.
- 해시 조인 — product 4,000블록은 메모리 102블록에 안 들어가므로, 두 표를 같은 해시 함수로 40개씩 분할해 쓰고(분할 하나 ≤ 100블록 · 메모리 102 > √4,000 ≈ 63 · Shapiro 1986) 분할 쌍마다 빌드 · 프로브한다: 3 × (4,000 + 10,000) = 42,000 으로 가장 싸다.
- WHERE s.ship_date 조건으로 외부가 500행(색인 3블록 + 행마다 1블록 = 503)으로 줄면 — 인덱스 중첩 루프 = 503 + 500 × 4 = 2,503, 해시 조인 = 503 + product 1회 읽기 4,000 = 4,503 으로 인덱스 중첩 루프가 이긴다.
- 같은 6의 경우 블록 중첩 루프도 외부 500행이 메모리에 다 들어가 4,503 으로 해시 조인과 전송 수가 같지만, 비교 횟수는 500 × 400,000 = 2억 번 대 해시 탐색 400,000번이다.
- PostgreSQL 은 6의 계획을 아래 모양으로 보인다 — 안쪽 Index Scan 의 loops=500 이 외부 행 수이고, Index Cond 에 외부 행 값 s.product_id 가 들어간다(14.1.1).
Nested Loop (rows=500)
-> Index Scan using shipment_ship_date_idx on shipment s (rows=500)
Index Cond: (ship_date = '2026-11-18'::date)
-> Index Scan using product_pkey on product p (rows=1 loops=500)
Index Cond: (id = s.product_id)
그림 3 · 같은 두 표를 잇는 네 방법의 블록 전송이 4,010,000 에서 42,000 까지 갈리고, 메모리 102블록에서는 분할 해시 조인이 가장 싸다.
🔑 중첩 루프는 외부 행 수만큼 안쪽을 다시 찾고, 해시 · 정렬 병합은 두 입력을 정해진 횟수만 읽는다 — 그래서 외부 행 수가 방식을 가른다.
그림 4 · 외부 쪽을 읽는 비용은 두 방식에 같아 빼고 보면, 인덱스 중첩 루프는 외부 행 수 × 4 로 늘고 해시 조인은 product 1회 읽기 4,000 에 머물러 외부 1,000행에서 갈린다.
⚠ 그림 3 · 4 의 값은 블록 전송만 센 교과서 식이다. PostgreSQL 은 순차 · 무작위 페이지 비용을 1.0 · 4.0 으로 달리 매기고 행 처리 CPU 비용과 캐시를 셈에 넣으므로(19.7.2), 실제 손익분기는 이 값과 다르다.
🔑 해시 조인이 빠른 까닭은 «한 번만 읽기» 때문이고, 해시 표가 메모리를 넘치는 순간 두 입력을 쓰고 다시 읽어 전송이 b_r + b_s 에서 3(b_r + b_s)가 된다.
5비교 — 중첩 루프 · 해시 · 정렬 병합
| 기준 | 중첩 루프(인덱스) | 해시 조인 | 정렬 병합 조인 |
|---|---|---|---|
| 조인 조건 | 모든 조건(범위 · 부등호 포함) | 같음 조건 · MySQL 8.0.20 이후는 조건 없는 해시 뒤 Filter 로 부등호도 처리(10.2.1.4) | 같음 조건 · 정렬할 수 있는 키(Silberschatz 2019) |
| 메모리 | 거의 쓰지 않음 · 블록 방식은 M − 2 블록 | 빌드 쪽 해시 표 · 넘치면 분할 | 정렬 메모리 · 넘치면 외부 정렬 |
| 사례 전체 조인 비용 | 4,010,000 | 42,000 | 70,000 |
| 첫 행이 나오는 때 | 외부 첫 행 바로 뒤 · 예 시작 비용 4.65(14.1.1) | 빌드가 끝난 뒤 · 예 시작 비용 226.23 중 Hash 224.98(14.1.2) | 입력이 이미 키 순이면 바로 · 예 0.56(14.1.1) |
| 잘 맞는 꼴 | 외부가 작고 안쪽에 조인 키 색인 · LIMIT | 두 입력이 크고 조인 키 색인 · 정렬이 없음 | 두 입력이 이미 키 순(색인 · 같은 키의 ORDER BY) |
분석외부가 손익분기(사례 1,000행)보다 작고 안쪽에 조인 키 색인이 있으면 인덱스 중첩 루프, 두 입력이 크면 해시 조인, 결과를 같은 키로 정렬해야 하거나 입력이 이미 키 순이면 정렬 병합을 쓴다. 근거는 표의 비용 행과 첫 행 행이다 — 해시는 빌드 비용을 먼저 치르고, 정렬 병합은 정렬이 이미 되어 있으면 그 비용이 사라진다.
6실무 진단 — 조인 노드의 숫자 하나로 가르기
분석계획에서 조인 노드 이름을 먼저 보고, 그 방식이 비싸지는 숫자 하나(loops · Batches · Sort Method)만 확인한다. 세 방식은 비싸지는 원인이 서로 달라서(그림 3 · 그림 4) 그 숫자가 원인 단계를 바로 나눈다(PostgreSQL 14.1.2).
| # | 증상 | 의심 원인 | 단계 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | Nested Loop 가 느림 · 안쪽 loops 가 수만 | 외부 행 과소 추정으로 인덱스 중첩 루프를 고름 | 추정 | EXPLAIN ANALYZE 외부 노드의 rows 대 actual rows | 외부 실제 행이 손익분기를 넘으면 통계부터 고침 · 비교용 SET enable_nestloop = off(19.7.1) |
| 2 | Hash 노드 Batches 2 이상 | 해시 표가 메모리 한도를 넘어 분할 | 메모리 | EXPLAIN (ANALYZE) Hash 노드의 Buckets · Batches · Memory Usage | Batches > 1 = 디스크 사용(14.1.2) · 한도 = work_ |
| 3 | Merge Join 아래 Sort 가 느림 | 정렬이 메모리를 넘어 디스크로 감 | 정렬 | EXPLAIN ANALYZE 의 Sort Method | 메모리 정렬인지 디스크 정렬인지 표시(14.1.2) · 조인 키 색인 순서로 읽으면 Sort 가 빠짐(14.1.1) |
| 4 | MySQL 큰 조인이 실패 | 해시 조인 디스크 파일 수가 open_ | 메모리 | EXPLAIN FORMAT=TREE 의 Inner hash join · SHOW VARIABLES LIKE 'join_buffer_size' | join_ |
순서는 조인 노드 이름 → 그 방식의 숫자 → 외부 행 추정이다. 방식이 맞는데 느리면 메모리 한도를, 방식이 틀렸으면 행 수 추정(→ 옵티마이저)을 본다.
7시험 대비
시험에서는 세 조인 방식을 견주는 비교형과, 해시 조인의 빌드 · 프로브 · 분할 과정을 묻는 동작 · 절차 설명형이 나올 수 있다. 비교형은 비용 식 넷과 그림 4 의 손익분기로 「옵티마이저가 언제 무엇을 고르나」를 보이고, 절차형은 그림 3 의 해시 열에 메모리 한도와 Batches 를 붙인다.
- 개요 — 정의 · 조인 노드의 위치(옵티마이저가 조인 순서와 함께 고름) · 세 방식 이름
- 방식별 원리 — 그림 3: 중첩 루프(외부 · 내부 · 인덱스) · 해시(빌드 · 프로브 · 분할) · 정렬 병합(정렬 · 나란히 읽기)
- 비용 비교 — 표: 조건 · 메모리 · 비용 식(b_r + n_r × c · 3(b_r + b_s) · 정렬 + b_r + b_s) · 첫 행 시점 · 수치 예(4,010,000 · 42,000 · 70,000)
- 선택 조건 — 그림 4 손익분기 그래프(외부 1,000행) + 해시 메모리 넘침(Batches > 1 · 3배)
- 결론 — 실행 계획 노드(Nested Loop · Hash Join · Merge Join)로 확인 · 추정 행 수가 방식을 정함
꼭 쓸 키워드
중첩 루프인덱스 중첩 루프해시 조인빌드프로브GRACE 해시하이브리드 해시정렬 병합외부 정렬work_mem
차이를 내는 한 가지는 같은 두 표의 블록 전송 수를 네 방식으로 셈해 4,010,000 · 404,000 · 70,000 · 42,000 을 한 표에 놓고, 외부 행이 1,000행 아래로 줄면 순위가 뒤집힌다는 그림 4 를 붙이는 것이다.
8오해와 사실
- 오해해시 조인은 늘 중첩 루프보다 빠르다.사실외부 행이 적고 안쪽에 조인 키 색인이 있으면 인덱스 중첩 루프가 싸며, 사례에서 외부 500행이면 2,503 대 4,503 이고 손익분기는 1,000행이다(설명용 가정 값 · 그림 4).
- 오해enable_nestloop = off 로 중첩 루프를 끌 수 있다.사실중첩 루프는 완전히 막을 수 없고, 이 설정은 다른 방식이 있을 때 덜 고르게 할 뿐이다(PostgreSQL 19.7.1).
- 오해해시 표가 메모리를 넘으면 조인이 멈춘다.사실PostgreSQL 은 배치를 나눠 디스크를 쓰며 계속 진행하고(14.1.2) 전송만 3(b_r + b_s)로 늘며, MySQL 은 디스크 파일 수가 open_files_limit 를 넘을 때 실패할 수 있다(10.2.1.4).
9핵심 정리
| 방식 | 조건 | 비용 식(블록 전송) | 메모리 | 사례 값 | 계획 노드 |
|---|---|---|---|---|---|
| 블록 중첩 루프 | 모든 조건 | ⌈b_ | M − 2 블록 | 404,000 | Nested Loop · MySQL 8.0.20 전 BNL |
| 인덱스 중첩 루프 | 안쪽 조인 키 색인 | b_ | 거의 없음 | 4,010,000 · 외부 500행 2,503 | Nested Loop + Index Scan(loops) |
| 해시 조인(메모리 안) | 같음 | b_ | 빌드 쪽 전체 | 외부 500행 4,503 | Hash Join · Batches: 1 |
| 해시 조인(분할) | 같음 | 3(b_ | 약 √빌드 블록 이상 | 42,000 | Hash Join · Batches > 1 |
| 하이브리드 해시 | 같음 | b_ | 첫 분할을 메모리에 | — | Shapiro 1986 |
| 정렬 병합 | 같음 · 정렬 가능 | 정렬 + b_ | 정렬 메모리 | 70,000 | Merge Join · Sort |
10참고 문헌
- 먼저 볼 문헌
- ★ PostgreSQL 18 Documentation 51.5 Planner/Optimizer — 세 조인 방식의 정의와 조인 쌍마다 모든 방식을 견주는 플래너 동작을 볼 때
- ★ PostgreSQL 18 Documentation 14.1 Using EXPLAIN — Nested Loop · Hash Join · Merge Join 노드와 Batches · loops 읽는 법을 볼 때
- ★ MySQL 8.4 Reference Manual 10.2.1.4 Hash Join Optimization — MySQL 해시 조인의 메모리 한도와 디스크 넘침을 볼 때
- ★ Join Processing in Database Systems with Large Main Memories (ACM TODS 11(3)) — 정렬 병합 · GRACE · 하이브리드 해시 조인의 비용 비교 원문을 볼 때
- ★ Database System Concepts 7th Edition — 블록 전송 수로 센 조인 비용 식을 교과서로 볼 때
- 본문 근거
- PostgreSQL 18 Documentation 19.4 Resource Consumption (work_mem · hash_mem_multiplier) — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/runtime-config-resource.html· 확인 2026-11-18 - PostgreSQL 18 Documentation 19.7 Query Planning — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/runtime-config-query.html· 확인 2026-11-18 - MySQL 8.4 Reference Manual 10.2.1.7 Nested-Loop Join Algorithms — Oracle · 2026-11 ·
dev.mysql.com/doc/refman/8.4/en/nested-loop-joins.html· 확인 2026-11-18 - MySQL 8.0 Reference Manual Hash Join Optimization — Oracle · 2026-11 ·
dev.mysql.com/doc/refman/8.0/en/hash-joins.html· 확인 2026-11-18 - MySQL 8.4 Reference Manual Server System Variables (join_buffer_size) — Oracle · 2026-11 ·
dev.mysql.com/doc/refman/8.4/en/server-system-variables.html· 확인 2026-11-18 - Access Path Selection in a Relational Database Management System (Proc. ACM SIGMOD 1979) — P. G. Selinger · M. M. Astrahan · D. D. Chamberlin · R. A. Lorie · T. G. Price · 1979-05 ·
doi.org/10.1145/582095.582099· 확인 2026-11-18 - Storage and Access in Relational Data Bases (IBM Systems Journal 16(4)) — M. W. Blasgen · K. P. Eswaran · 1977-12 ·
doi.org/10.1147/sj.164.0363· 확인 2026-11-18 - Application of Hash to Data Base Machine and Its Architecture (New Generation Computing 1(1)) — M. Kitsuregawa · H. Tanaka · T. Moto-oka · 1983-03 ·
doi.org/10.1007/BF03037022· 확인 2026-11-18