소트 머지 조인(Sort Merge Join)
배경
조인 연산은 데이터베이스 성능에 가장 큰 영향을 주는 핵심 연산이다.
일반적으로 인덱스 기반의 NL 조인(Nested Loop Join)이 OLTP 환경에서 많이 쓰이지만, 대량 데이터를 다룰 때는 성능이 급격히 저하된다.
이때 옵티마이저는 소트 머지 조인이나 해시 조인을 선택한다. 해시 조인이 등장하면서 소트 머지 조인의 활용도는 줄었지만, 등치 조인(=)이 아닌 조건에서는 여전히 유용한 방법으로 쓰인다.
소트 머지 조인과 해시 조인을 설명하기 전에 PGA에 대한 설명이 선행되어야 한다.
메모리 구조: SGA vs PGA
- SGA(System Global Area)는 공유 메모리 영역이다. 여러 프로세스가 함께 접근할 수 있지만 동시에 접근하려면 래치(latch) 같은 동기화 메커니즘이 필요하다. DB 버퍼 캐시가 여기에 속한다.
- PGA(Process Global Area)는 프로세스 전용 메모리 영역이다. 다른 프로세스와 공유하지 않으므로 래치가 필요 없다. 동일한 데이터를 읽더라도 SGA보다 빠르다. PGA가 부족하면 TEMP 테이블스페이스를 사용한다.
소트 머지 조인은 이 PGA를 적극 활용하는 조인 방식이다.
기본 메커니즘
소트 머지 조인은 이름 그대로 소트 단계와 머지 단계 두 단계로 이루어진다.
- 소트 단계
- 양쪽 입력 집합을 조인 키 기준으로 정렬한다.
- 정렬 결과는 PGA의 Sort Area에 저장된다.
- PGA가 부족하면 TEMP 테이블스페이스를 사용한다.
- 머지 단계
- 정렬된 집합을 순차적으로 스캔하면서 매칭되는 행을 병합한다.
- NL 조인처럼 루프 구조를 사용하지만, 정렬된 순서를 활용하므로 Inner 테이블을 매번 Full Scan하지 않는다.
즉, 조인 오퍼레이션 자체는 NL 조인과 유사하지만 정렬된 순서 덕분에 탐색 비용을 크게 줄일 수 있다는 점이 차이점이다.
실행 과정 예시
select *
from 사원 e, 고객 c
where c.관리사원번호 = e.사원번호
- 사원 집합 정렬
- 조건에 맞는 사원 데이터를 읽어 사원번호 기준으로 정렬한다.
- 정렬된 결과는 PGA의 Sort Area에 저장된다.
- Sort Area에 담을 수 없을 정도로 크면 TEMP 테이블스페이스를 사용한다.
- 고객 집합 정렬
- 조건에 맞는 고객 데이터를 읽어 관리사원번호 기준으로 정렬한다.
- 역시 결과는 Sort Area에 저장되며, 공간이 부족하면 TEMP 테이블스페이스에 저장된다.
- 머지 단계 수행
- PGA에 정렬된 사원 데이터를 순차적으로 스캔하면서, 정렬된 고객 데이터와 조인한다.
- PL/SQL 루프 코드로 표현하면 다음과 같다.
begin
for outer in(select * from PGA에_정렬된_사원)
loop -- outer 루프
for inner in (select * from PGA에_정렬된_고객
where 관리사원번호 = outer.사원번호)
loop --inner 루프
dbms_output.put_line(...);
end loop;
end loop;
end;1, 2단계가 소트 단계, 3단계가 머지 단계이다.
실제로 조인을 수행하는 3단계의 구조 자체는 NL 조인과 동일하다.
주목할 점은 사원 데이터를 기준으로 고객 데이터를 매번 Full Scan 하지 않는다는 사실이다. 고객 데이터가 정렬돼 있으므로 조인 대상 레코드가 시작되는 지점을 쉽게 찾을 수 있고, 조인에 실패하는 레코드를 만나는 순간 바로 멈출 수 있다.
Sort Area에 저장한 데이터 자체가 인덱스 역할을 하므로 소트머지 조인은 조인 컬럼에 인덱스가 없어도 사용할 수 있는 조인 방식이다. 조인 컬럼에 인덱스가 있어도 NL 조인은 대량 데이터를 조인할 때 불리하므로 소트머지 조인을 사용할 수 있다.
핵심 포인트
- 고객 테이블을 매번 Full Scan하지 않는다.
고객 데이터가 이미 정렬되어 있기 때문에, 매칭되는 구간을 바로 찾아갈 수 있고, 불일치하는 레코드를 만나면 탐색을 중단한다. - Sort Area 자체가 인덱스 역할을 한다.
따라서 조인 컬럼에 인덱스가 없어도 소트 머지 조인을 사용할 수 있다. - NL 조인 대비 장점
조인 컬럼에 인덱스가 있더라도, 대량 데이터 조인에서는 NL 조인이 불리하다.
이때 소트 머지 조인이 더 효율적인 대안이 된다.
NL 조인과의 성능 차이
- NL 조인은 인덱스를 통한 랜덤 액세스 기반이다.
모든 블록을 건건이 읽으면서 버퍼캐시를 경유해야 하고, 버퍼에서 못 찾으면 디스크까지 접근해야 한다.
이 과정에서 래치 획득과 체인 스캔이 반복되므로 대량 데이터 조인에는 불리하다. - 소트 머지 조인은 조인 대상 집합을 한 번에 읽어 PGA에 저장한 후 순차적으로 조인한다.
PGA는 프로세스 전용 메모리라서 래치 경합이 없고, 순차 액세스 방식으로 처리되므로 대량 데이터 조인에 유리하다.
소트 머지 조인의 주용도
해시 조인이 대량 조인의 주류가 되었지만, 해시 조인은 등치(=) 조인에서만 동작한다.
따라서 소트 머지 조인은 다음과 같은 상황에서 여전히 유용하다.
- 비등가 조인(<, >, BETWEEN, LIKE 등)
- 조인 조건이 없는 카테시안 곱
- 대량 데이터 조인인데 인덱스가 없거나 인덱스 활용이 비효율적일 때
특징 요약
- 소트 머지 조인은 정렬을 통해 즉석에서 인덱스를 생성하는 방식이다.
- 조인 컬럼에 인덱스가 없어도 사용 가능하다.
- 조인 대상 집합을 개별적으로 읽고 정렬한 뒤 조인을 시작한다.
- 스캔 위주의 방식이지만, 필요하면 인덱스를 활용해 랜덤 액세스가 발생할 수도 있다.
- 해시 조인과 달리 비등가 조인까지 처리할 수 있다.
👉 결론: 소트 머지 조인은 “정렬 기반 순차 조인”으로, 대량 데이터 조인에서 NL 조인의 랜덤 액세스 한계를 보완하는 방식이다.
reference
- 교재 '친절한 SQL 튜닝'
'DataBase > SQL 튜닝' 카테고리의 다른 글
| [SQL 튜닝] NL 조인(Nested Loop Join) 이해와 튜닝 (0) | 2025.09.30 |
|---|
