Sort Merge Join (정렬 병합 조인)

Sort Merge Join(SM 조인, 정렬 병합 조인)은 두 개의 정렬된 테이블을 병합하여 조인하는 방식입니다.
주로 등가 조인(=)뿐만 아니라 범위 조인(<, >, BETWEEN 등)에서도 사용될 수 있으며, 대용량 데이터 조인에 적합합니다.

Table of Contents

Toggle

1. Sort Merge Join 개념

Sort Merge Join은 두 개의 입력 테이블을 정렬(Sort)한 후, 정렬된 데이터를 병합(Merge)하여 조인을 수행합니다.

테이블이 이미 정렬된 상태라면 빠르게 수행됨
정렬되지 않은 경우, 먼저 정렬하는 과정이 필요하여 성능이 저하될 수 있음
인덱스가 없는 대용량 데이터에서 해시 조인(Hash Join)보다 유리한 경우가 있음

2. Sort Merge Join의 동작 방식

SM 조인은 두 단계(Sort 단계 + Merge 단계)로 동작합니다.

1) 정렬 단계 (Sort Phase)

두 개의 입력 테이블을 조인 키 기준으로 정렬합니다.
만약 테이블이 이미 정렬되어 있으면 이 단계는 생략됨

2) 병합 단계 (Merge Phase)

정렬된 두 테이블을 한 번씩 순차적으로 읽으며 비교하여 조인
이진 탐색이 필요 없으며, 선형 탐색만으로 조인을 수행하여 효율적임

3. Sort Merge Join의 종류

SM 조인은 데이터 크기와 정렬 여부에 따라 두 가지 방식으로 실행됩니다.

1) 정렬된 입력을 이용한 Sort Merge Join

두 개의 입력 테이블이 이미 정렬된 상태라면 바로 병합(Merge) 작업만 수행
가장 빠르게 동작하는 방식

2) 정렬이 필요한 Sort Merge Join

두 개의 입력 테이블 중 하나 또는 둘 다 정렬되지 않은 경우, 정렬을 먼저 수행한 후 조인
정렬 과정이 추가되므로 성능이 저하될 수 있음

4. Sort Merge Join의 장점과 단점

✅ 장점

✔ 대용량 데이터 조인에 적합 (특히 인덱스가 없을 경우)
✔ 등가 조인(=)뿐만 아니라 범위 조인(<, >, BETWEEN)에서도 사용 가능
✔ 테이블이 이미 정렬되어 있다면 매우 빠르게 실행
✔ Full Table Scan을 활용하여 읽기 성능이 좋음

❌ 단점

❌ 정렬 단계가 필요할 경우, 정렬 비용이 큼
❌ 데이터가 작은 경우 Nested Loop Join보다 비효율적
❌ 랜덤 액세스가 많아 메모리 사용량 증가 가능

5. Sort Merge Join 실행 계획 예제 (MySQL, PostgreSQL, Oracle)

EXPLAIN ANALYZE
SELECT A.id, A.name, B.salary
FROM employees A
JOIN salaries B
ON A.id = B.emp_id;

실행 계획에서 Sort Merge Join이 표시되면, 해당 조인이 SM 조인을 사용하고 있다는 의미입니다.

6. Sort Merge Join vs 다른 조인 방식 비교

조인 방식	사용 조건	장점	단점
Nested Loop Join	인덱스가 있을 때	작은 테이블에서 빠름	인덱스 없으면 느림
Sort Merge Join	정렬된 데이터에서 적합	범위 조인에서 빠름	정렬 비용이 큼
Hash Join	등가 조인(=)에서 적합	대용량 데이터에서 빠름	많은 메모리 필요