[Database] Nested Loop Join , Hash Join, Merge Join

옵티마이저를 공부하다 보니 JOIN의 종류가 단순히 INNER, OUTER, SELF, CROSS 같은 논리적 조인만 있는 것이 아니라,
실제 DB 엔진이 조인을 실행할 때 사용하는 물리적 조인 방식이 존재한다는 것을 알게 되었습니다.

대표적인 물리적 조인 방식은 다음과 같습니다.

• Nested Loop Join
• Hash Join
• Merge Join

옵티마이저는 쿼리 구조, 데이터 크기, 인덱스 유무 등을 고려하여
각 조인 방식 중 가장 효율적인 방법을 선택해 실행합니다.

 

예시 테이블을 통해 각각 join의 장단점에 대해서 알아보도록 하겠습니다.

예시 테이블

다음은 예시 쿼리 입니다.

SELECT *
FROM A
JOIN B ON A.key = B.key;

Nested Loop Join

Nested Loop Join 방식은 이중 for문 방식이라고 보면 되겠습니다.

아래는 엔진 내부에서 돌아가는 이중 for문을 실제로 표 스캔 방식으로 펼쳐서 확인해 보았습니다.

A의 첫 번째 row (1, key=10)를 기준으로 inner 테이블 조사

A = 1 (key=10)

비교 시점	A.key	B.row	B.key	조건 (A.key = B.key)	결과
step 1	10	1	3	X	무시
step 2	10	2	10	O	(a1, b2) 매칭
step 3	10	3	20	X	무시

→ A(a1) 기준 결과: (a1, b2) 한 줄 생성

A의 두 번째 row (2, key=20) 탐색

A = 2 (key=20)

비교 시점	A.key	B.row	B.key	조건(A.key = B.key)	결과
step 1	20	1	3	X	무시
step 2	20	2	10	X	무시
step 3	20	3	20	O	(a2, b3) 매칭

→ A(a2) 기준 결과: (a2, b3) 한 줄 생성

A의 세 번째 row (3, key=30) 탐색

A = 3 (key=30)

비교 시점	A.key	B.row	B.key	조건(A.key = B.key)	결과
step 1	30	1	3	X	무시
step 2	30	2	10	X	무시
step 3	30	3	20	X	무시

→ A(a3) 기준 결과: 매칭 없음 → 결과 없음

결과 및 정리

A.id	A.key	A.value	B.id	B.key	B.value
1	10	a-row-1	2	10	b-row-2
2	20	a-row-2	3	20	b-row-3

A에서 key=30인 a3은 매칭되는 B.key가 없기 때문에 결과에서 빠집니다.

 

• Nested Loop Join은 A를 한 줄씩 읽고, B 전체를 스캔하는 구조입니다.
• 그래서 A가 작고, B.key에 인덱스가 있을 때 (Index Nested Loop Join) 빠르게 동작합니다.
• A가 크고 B에도 인덱스가 없으면 O(M×N)에 가까운 최악의 성능이 나올 수 있습니다.

Hash Join

Hash Join은 두 테이블 중 더 작은 쪽으로 해시 테이블을 만든 뒤, 다른 테이블의 row를 하나씩 읽으면서 해시 버킷에 있는 값만 비교하는 방식입니다.

• 작은 테이블(B)을 Build Phase(해시 테이블 구성 단계)에서 해시 테이블로 변환
• 큰 테이블(A)을 Probe Phase(탐색 단계)에서 순차적으로 읽으면서 해시 테이블과 비교

하는 구조입니다.

Hash Join은 대규모 테이블 조인에서 매우 효과적이며, Nested Loop Join보다 훨씬 빠르게 동작합니다.

 

Build Phase – B로 해시 테이블 만들기

먼저 DB 엔진은 B 테이블의 조인 키(B.key)를 기준으로 해시 테이블을 생성합니다.

아래 표는 B 테이블 → 해시 테이블로 변환된 모습입니다.

Bucket(Hash(B.key))	B.row (매달린 row)
h(3)	(1, key=3)
h(10)	(2, key=10)
h(20)	(3, key=20)

 

여기서 해시 값 h(key)는 이해를 돕기 위한 추상적인 값이며, 중요한 건 각 key가 자신만의 버킷에 저장된다는 것입니다.

Probe Phase – A 테이블을 읽으면서 해시 테이블 조회

이제 A의 각 row를 읽으면서, A.key에 대한 해시값으로 B가 있는 버킷만 조회합니다.

A의 첫 번째 row (1, key=10)

단계	A.key	해시값 h(A.key)	대응 bucket	bucket 내용	매칭 결과
step 1	10	h(10)	bucket[h(10)]	(b2, key=10)	(a1, b2)

즉, A.key=10 → B.key=10 버킷만 검사합니다.
➡ 대규모 테이블에서도 매우 빠른 성능을 보입니다.

A의 두 번째 row (2, key=20)

단계	A.key	해시값	대응 bucket	bucket 내용	매칭 결과
step 1	20	h(20)	bucket[h(20)]	(b3, key=20)	(a2, b3)

A.key=20 → B.key=20 버킷만 확인합니다.

A의 세 번째 row (3, key=30)

단계	A.key	해시값	대응 bucket	bucket 내용	매칭 결과
step 1	30	h(30)	bucket[h(30)]	(empty)	없음

A.key=30에 대응하는 버킷이 없기 때문에 매칭되지 않습니다.

결과 및 정리

A.id	A.key	A.value	B.id	B.key	B.value
1	10	a-row-1	2	10	b-row-2
2	20	a-row-2	3	20	b-row-3

Hash Join의 장점

• 대규모 테이블 조인 시 성능 향상
  • B 전체를 해시 테이블로 만드는 작업: O(N)
  • A를 탐색하며 해시 lookup 하는 작업: O(M)
  • 전체 복잡도: O(M + N)
  • Nested Loop Join의 O(M × N)에 비해 효율적입니다
• 해시 테이블 자체가 인덱스 역할을 수행하기 때문에 인덱스가 없어도 빠르게 동작합니다.

Hash Join의 단점

• 해시 테이블 생성 시 메모리 사용량이 큽니다.
  • 작은 테이블(B)을 통째로 메모리에 올려야 합니다.
  • 테이블이 크면 디스크 spill(임시 파일 사용) 발생하며 성능 저하를 유발할 수 있습니다.
• 비-equi 조인에는 적합하지 않습니다.
  • 예: A.key > B.key, BETWEEN, LIKE
  • 이런 비교는 해싱 구조에 맞지 않기 때문입니다.
• 두 테이블이 이미 정렬된 상태라면 Merge Join보다 느립니다.
  • 정렬 비용이 없는 상황에서는 Merge Join이 더 유리할 수 있습니다.

 

Merge Join

Merge Join(Sort-Merge Join)은 양쪽 테이블을 조인 키 기준으로 정렬한 뒤, 두 포인터를 움직여가며 정렬된 리스트를 병합 하듯이 조인을 수행하는 방식입니다. Hash Join과 마찬가지로 대규모 테이블 조인 시 사용하며, 특히 이미 정렬된 상태로 데이터를 읽을 수 있을 때 최적의 성능을 냅니다.

 

Merge Join은 크게 두 단계로 이루어집니다.

1. Sort Phase – A.key, B.key 기준으로 정렬
2. Merge Phase – 두 포인터를 이동시키며 병합 조인 수행

예시 테이블 A, B는 이미 key 순서대로 정렬되어 있으므로 추가 정렬 없이 바로 Merge 단계로 진행한다고 가정합니다.

 

Merge Phase – 단계별 동작

두 테이블에 각각 포인터를 둡니다.

• i → A의 현재 row
• j → B의 현재 row

시작 위치는 i=1번째, j=1번째 row.

1) Step 1 — A(10) vs B(3)

A.row	A.key	B.row	B.key	비교	결과
(1,10)	10	(1,3)	3	10 > 3	B 포인터 이동 (j++)

A.key > B.key 이므로 B 포인터를 다음으로 이동시킵니다.

2) Step 2 — A(10) vs B(10)

A.row	A.key	B.row	B.key	비교	결과
(1,10)	10	(2,10)	10	10 = 10	매칭 (a1, b2)

동일한 key이므로 매칭됩니다. 두 포인터 모두 다음 row로 이동합니다. (i++, j++)

3) Step 3 — A(20) vs B(20)

A.row	A.key	B.row	B.key	비교	결과
(2,20)	20	(3,20)	20	20 = 20	매칭 (a2, b3)

동일한 key이므로 매칭됩니다. 두 포인터 모두 다음 row로 이동합니다. (i++, j++)

4) Step 4 — A(30) vs B(끝)

B는 더 이상 row가 없으므로 병합 종료합니다.

A.row	A.key	B.row	B.key	비교	결과
(3,30)	30	없음	-	종료	매칭 없음

A.key=30은 B에 없으므로 매칭되지 않습니다.

결과 및 정리

A.id	A.key	A.value	B.id	B.key	B.value
1	10	a-row-1	2	10	b-row-2
2	20	a-row-2	3	20	b-row-3

Merge Join의 장점

• 정렬된 데이터를 조인할 때 가장 빠른 조인 방식 중 하나입니다.
  • 인덱스를 통한 정렬된 스캔(Index Range Scan)이 가능하면 Sorting 없이 바로 병합 가능합니다.
• 대규모 테이블 조인에서도 좋은 성능
  • 순차 스캔 기반이라 디스크 I/O 패턴이 좋습니다.
• equi-join뿐 아니라 범위 조인에도 자연스럽게 확장이 가능합니다
  • A.key > B.key
  • A.key BETWEEN ...
  • Hash Join이 처리 못하는 영역을 커버할 수 있습니다.
• 메모리 사용이 적습니다
  • Hash Join처럼 테이블 전체를 메모리에 올릴 필요가 없습니다.

Merge Join의 단점

• 정렬 비용이 크면 비효율적
  • 양쪽 테이블이 정렬되어 있지 않다면 Sorting 비용 때문에 Hash Join보다 느려질 수 있습니다.
• 테이블이 작거나 인덱스가 없다면 오히려 과한 방식일 수 있습니다.
  • 작은 테이블 조인에는 Nested Loop가 성능이 좋을 수 있습니다.
• 조인 키가 정렬 가능한 속성이어야 합니다.
  • 정렬하려면 비교 가능한 값이 필요합니다.

 

정리

물리적 조인 방식은 모두 같은 결과를 만들어내지만, 어떤 경로로 그 결과에 도달하느냐에 따라 성능과 자원 사용량이 달라진다는 점이 핵심입니다.

 

Nested Loop Join은 가장 단순하고 직관적인 방식이지만, 데이터가 커질수록 성능이 급격히 떨어질 수 있습니다.

Hash Join은 해시 테이블이라는 자료 구조를 통해 대량의 데이터를 효율적으로 조인할 수 있으며,

Merge Join은 정렬된 데이터를 순차적으로 병합하는 구조 덕분에 대규모 분석 환경에서 뛰어난 성능을 보여줍니다.

 

결국 어떤 조인 방식을 사용할지는 옵티마이저가 테이블 크기, 인덱스 존재 여부, 정렬 상태, 메모리 조건 등을 종합적으로 판단해 결정합니다. 내부 동작을 정확히 이해할수록, 왜 해당 쿼리가 느린지, 어떤 인덱스를 추가해야 하는지, 어떤 조건을 바꾸면 플랜이 더 좋아지는지와 같은 실질적인 개선 포인트를 더 잘 찾을 수 있습니다.