432. 소트 머지 조인 (Sort Merge Join)

⚠️ 이 문서는 두 개의 대용량 테이블을 합칠(JOIN) 때, 인덱스가 없어서 중첩 루프 조인(NL Join)을 쓰면 디스크가 폭발하는 상황을 막기 위해 **두 테이블을 먼저 예쁘게 정렬(Sort)한 다음 지퍼를 채우듯 한 번에 싹 병합(Merge)해버리는 '소트 머지 조인'**을 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 조인할 두 테이블을 각자 조인 컬럼 기준으로 오름차순 정렬(Sort)한 뒤, 위에서부터 아래로 차례대로 비교하며 합치는(Merge) 방식이다.
  2. 가치: 중첩 루프 조인의 최악의 약점인 '랜덤 I/O(디스크 널뛰기)'가 전혀 발생하지 않기 때문에 대용량 데이터를 처리할 때 매우 안정적이다.
  3. 한계: 데이터를 정렬(Sort)하는 작업 자체가 메모리와 CPU를 엄청나게 잡아먹기 때문에, 현대 데이터베이스에서는 대부분 더 빠르고 메모리를 덜 먹는 **해시 조인(Hash Join - 433번 문서)**으로 대체되었다.

Ⅰ. 개요: 지퍼 채우기 (Context & Necessity)

부서 테이블(1만 건)과 직원 테이블(100만 건)을 조인하려고 한다. 그런데 조인 컬럼인 부서코드에 둘 다 인덱스가 없다!

  • 인덱스가 없는 상태에서 중첩 루프 조인(431번 문서)을 쓰면? 1만 번 $\times$ 100만 번 = 100억 번을 뒤져야 한다. 서버가 며칠 동안 멈춘다.

이럴 때 옵티마이저는 소트 머지 조인을 선택한다.

  1. "일단 부서 테이블을 부서코드 순으로 '가나다순' 정렬해 놔!" (Sort)
  2. "직원 테이블도 부서코드 순으로 정렬해 놔!" (Sort)
  3. 두 테이블이 모두 정렬되었으니, 위에서부터 아래로 쭉 내려가면서 지퍼를 채우듯이(Merge) 겹치는 애들만 쏙쏙 묶어준다.

📢 섹션 요약 비유: 소트 머지 조인은 **'두 벌의 카드를 순서대로 맞추는 게임'**과 같습니다. 카드 뭉치가 뒤죽박죽일 때는 짝을 찾기 힘들지만, 일단 양쪽 다 숫자 순서대로 예쁘게 정렬(Sort)해두면, 위에서부터 카드 한 장씩 까보면서 같은 숫자끼리 딱딱 짝지어주는(Merge) 작업은 눈 감고도 할 수 있을 만큼 빠릅니다.

Ⅱ. 소트 머지 조인의 핵심 특징 ★

1. 인덱스가 없어도 빠르다

  • 인덱스가 없으면 디스크를 미친 듯이 긁어대야 하는 NL 조인과 달리, 소트 머지 조인은 메모리에서 한 번 정렬만 끝내두면 순차적으로 쭉 읽어 내리기만 하면 된다. (순차 I/O의 승리)

2. 비동등 조인 (Non-Equi Join)이 가능하다

  • 이건 해시 조인(Hash Join)이 절대 못 하는 소트 머지 조인만의 필살기다.
  • 해시 조인은 무조건 A.id = B.id 처럼 값이 똑같을(=) 때만 쓸 수 있다.
  • 하지만 소트 머지는 이미 크기순으로 '정렬'이 되어있기 때문에, A.date >= B.date 라거나 BETWEEN 같은 범위 조건(비동등 조인)에서도 훌륭하게 작동한다.

3. 치명적 단점: 정렬(Sort)의 비용

  • 100만 건을 정렬하는 건 메모리(Sort Area)를 엄청나게 소모한다.
  • 메모리가 꽉 차면 디스크에 임시 파일을 썼다 지웠다 해야 하므로(Temp Space I/O) 속도가 수십 배 느려진다.

Ⅲ. 조인 방식별 성능 교차점

데이터양에 따라 옵티마이저가 선택하는 1순위 조인 방식이 달라진다.

  • 데이터가 소량일 때: 무조건 NL 조인이 빠르다. (정렬할 필요 없이 인덱스만 슉슉 타면 됨)
  • 데이터가 대량일 때: 해시 조인이 1짱이다.
  • 해시 조인을 못 쓸 때 (비동등 조인이거나 범위 검색일 때): 어쩔 수 없이 소트 머지 조인을 쓴다.
┌──────────────────────────────────────────────────────────────┐
│           소트 머지 조인 (Sort Merge Join) 작동 구조 시각화            │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│ [ 👨‍💼 직원 (뒤죽박죽) ]                 [ 🏢 부서 (뒤죽박죽) ]         │
│  (C부서, A부서, B부서)                    (B부서, C부서, A부서)        │
│          │                                     │             │
│          ▼ 1. 각각 정렬 (Sort)                   ▼             │
│ [ 👨‍💼 직원 (정렬됨) ]                   [ 🏢 부서 (정렬됨) ]           │
│  A부서: 철수                            A부서: 기획팀                │
│  B부서: 영희                            B부서: 영업팀                │
│  C부서: 민수                            C부서: 개발팀                │
│                                                              │
│          ▼ 2. 병합 (Merge - 지퍼 채우기!)                       │
│  [A:철수-기획팀] ──▶ [B:영희-영업팀] ──▶ [C:민수-개발팀] (끝!)        │
└──────────────────────────────────────────────────────────────┘

Ⅳ. 결론

"소트 머지는 역사의 뒤안길로 가고 있지만, 대체 불가능한 영역이 있다." 과거 Oracle 데이터베이스 시절, 대용량 데이터를 처리하는 유일한 희망은 소트 머지 조인이었다. 하지만 더 빠르고 메모리도 덜 먹는 해시 조인(Hash Join)이 등장하면서 왕좌에서 밀려났다. 그럼에도 불구하고 우리가 이 알고리즘을 배워야 하는 이유는 두 가지다. 첫째, 조인 조건이 >= 나 < 처럼 부등호로 이루어졌을 때는 해시 조인이 불가능하므로 소트 머지가 유일한 대안이다. 둘째, 우연히 조인할 두 테이블이 이미 인덱스를 통해 예쁘게 정렬되어 있는 상태라면? (정렬 비용이 0원이라면?) 소트 머지 조인은 해시 조인조차 씹어먹는 우주 최강의 속도를 보여준다.

📌 관련 개념 맵

  • 관련 연산: 관계 대수 JOIN ($\bowtie$, 409번 문서)
  • 대안 방식: Nested Loop Join (431번), Hash Join (433번)
  • 발생 조건: Non-Equi Join (비동등 조인), 인덱스가 없을 때 대용량 조인
  • 주의할 점: Sort Area (메모리) 부족 시 디스크 I/O 발생으로 성능 폭락

👶 어린이를 위한 3줄 비유 설명

  1. 소트 머지 조인은 빨간 숫자 카드 뭉치와 파란 숫자 카드 뭉치에서 같은 숫자끼리 짝을 찾는 게임이에요.
  2. 카드 뭉치가 섞여 있으면 찾기 힘드니까, 먼저 두 뭉치 모두 1, 2, 3, 4 순서대로 예쁘게 정리(Sort)를 해둬요.
  3. 양쪽 다 정렬되어 있으니까, 맨 위에서부터 한 장씩 넘겨보면서 같은 숫자끼리 쓱쓱 묶어주기만(Merge) 하면 게임이 순식간에 끝난답니다!