Sort Merge Join의 원리와 튜닝: 정렬·병합·Workarea·비등치 조인

핵심 요약

Sort Merge Join은 두 입력 Row Source를 Join Key 순서로 준비한 뒤, 현재 위치를 전진시키면서 조건을 만족하는 행을 결합하는 Join Method입니다.

입력 1 생성 → Join Key 순서로 준비 ┐
                                    ├→ MERGE JOIN → 결과
입력 2 생성 → Join Key 순서로 준비 ┘

처리는 두 단계로 이해합니다.

Sort 단계
  → 각 입력을 Join Key 순서로 준비

Merge 단계
  → 작은 Key 쪽 Pointer를 전진
  → Match 또는 범위가 겹치는 구간을 결합

Optimizer가 Sort Merge Join을 고려하는 대표 조건입니다.

• <, <=, >, >=, BETWEEN 등 순수 비등치 Join
• 대량 Join에서 이미 필요한 정렬을 활용할 수 있음
• 첫 입력이 Index 등으로 필요한 순서를 제공해 일부 Sort를 생략 가능
• NL Join의 반복 Index·ROWID Random Access가 큼
• Hash Join보다 Sort·Merge와 Workarea 비용이 낮게 추정됨

개념적 비용입니다.

Sort Merge 총비용
≈ 입력 1 생성
 + 입력 2 생성
 + 입력 1 Sort
 + 입력 2 Sort
 + Merge 비교
 + Join 결과 후속 처리

실제 Sort 대상은 원본 Table 전체가 아니라 Access·Filter를 통과한 Row Source입니다.

원본 Row 수
→ Predicate 후 A-Rows
→ Projection 후 Row 폭
→ Sort Workarea·TEMP 요구량

이 이론의 범위

이 이론은 SQLP의 SQL 고급활용 및 튜닝 → 조인 순서와 조인 방식 → 소트 머지 조인 범위에서 정렬·병합 원리, 비등치 Join, Workarea·TEMP, Index 순서 활용과 Hint 검증을 다룹니다.

학습 목표

이 이론을 학습한 뒤에는 다음을 설명할 수 있어야 합니다.

• Join Type·Join Order·Join Method·Access Path를 구분한다.
• SORT JOIN과 MERGE JOIN Operation의 역할을 설명한다.
• Sort 대상이 원본 Table이 아니라 Predicate 후 Row Source임을 설명한다.
• 첫 번째 입력의 Sort가 생략될 수 있는 조건을 설명한다.
• 중복 Join Key의 결과 Cardinality를 계산한다.
• NULL 등치 비교와 Outer Join 보존 규칙을 분리한다.
• 순수 비등치 Join에서 Sort Merge가 후보가 되는 이유를 설명한다.
• Band 범위 중첩이 결과 Row 수를 늘리는 원리를 설명한다.
• OPTIMAL·ONE PASS·MULTI-PASS Workarea를 구분한다.
• V$SQL_WORKAREA의 Memory·TEMP 지표를 해석한다.
• Index 순서 활용과 대량 ROWID Access의 Trade-off를 설명한다.
• LEADING·ORDERED·USE_MERGE·NO_USE_MERGE의 역할을 구분한다.
• 최종 결과 순서는 ORDER BY만 보장함을 설명한다.
• 동일 Bind·Fetch·Parallel 조건에서 NL·Hash·Merge를 비교한다.

1. 네 가지 결정을 분리한다

Sort Merge Join은 Join Method입니다.

MERGE JOIN
  → 정렬·병합 Algorithm

MERGE JOIN OUTER
  → 정렬·병합 Algorithm
  + Outer Join의 보존 규칙

같은 Join Type도 여러 Method로 구현될 수 있으므로 결과 의미와 실행 방식을 혼동하지 않습니다.

2. 기본 실행 흐름

다음 SQL을 가정합니다.

SELECT /*+ GATHER_PLAN_STATISTICS */
       d.department_id,
       d.department_name,
       e.employee_id
FROM   departments d
JOIN   employees e
  ON   e.department_id=d.department_id
WHERE  d.region_code=:region_code
AND    e.status='ACTIVE';

개념적 처리입니다.

DEPARTMENTS Access
→ region_code Filter
→ department_id 순서 준비

EMPLOYEES Access
→ status Filter
→ department_id 순서 준비

두 입력의 현재 department_id 비교
→ Match 구간 결합

중요합니다.

Sort 입력 크기
= 원본 Table Row 수가 아님
= Predicate 적용 후 Row Source A-Rows

또한 Sort는 Row 전체가 아니라 해당 Query Block에서 전달해야 하는 Column Byte를 처리하므로 Row 폭도 중요합니다.

3. Sort 단계

3.1 SORT JOIN

두 입력이 필요한 순서를 제공하지 못하면 다음과 같은 Plan이 나타날 수 있습니다.

MERGE JOIN
  SORT JOIN
    TABLE ACCESS FULL DEPARTMENTS
  SORT JOIN
    TABLE ACCESS FULL EMPLOYEES

• Table·Index Access가 입력 Row Source를 만듭니다.
• SORT JOIN이 Join Key 순서로 입력을 준비합니다.
• MERGE JOIN이 두 정렬 입력을 병합합니다.

3.2 첫 입력 Sort 생략

Oracle의 일반적인 Sort Merge 처리에서는 첫 번째 입력이 이미 Join Key 순서를 제공하면 첫 번째 Sort를 생략할 수 있습니다.

예시 Index입니다.

DEPT_REGION_ID_IX(region_code, department_id)

WHERE d.region_code=:region_code

region_code가 Equality로 고정되면 해당 Index 구간 안에서 department_id 순서를 제공할 수 있습니다.

가능한 Plan입니다.

MERGE JOIN
  TABLE ACCESS BY INDEX ROWID DEPARTMENTS
    INDEX RANGE SCAN DEPT_REGION_ID_IX
  SORT JOIN
    TABLE ACCESS FULL EMPLOYEES

단, Index가 존재한다는 사실만으로 Sort 생략을 단정하지 않습니다.

확인합니다.

• Join Key와 Index Key 순서
• Join Key 앞 Column의 Equality 고정
• Ascending·Descending 방향
• 중간 Operation의 순서 보존 여부
• 실제 Plan의 SORT JOIN 유무
• Index ROWID Access의 Buffers·Reads

3.3 Sort 생략의 Trade-off

Index 순서 활용
  → Sort 하나 감소 가능
  → Single Block I/O·ROWID Table Access 증가 가능

Full Scan + Sort
  → Sequential·Multiblock I/O
  → Workarea·TEMP 사용 가능

따라서 Sort Operation 하나가 사라졌다는 이유만으로 Index Plan이 더 빠르다고 결론내리지 않습니다.

4. Merge 단계

정렬 후 현재 Key를 비교합니다.

A Key < B Key
  → A Pointer 전진

A Key > B Key
  → B Pointer 전진

A Key = B Key
  → 같은 Key 구간의 Match 조합 반환

이전 비교 위치를 유지하므로 NL Join처럼 Inner 입력의 시작점으로 반복 복귀하는 구조와 다릅니다.

4.1 중복 Key

A: 20(a1), 20(a2)
B: 20(b1), 20(b2), 20(b3)

결과는 다음과 같습니다.

2 × 3 = 6행

정렬은 중복을 제거하지 않습니다. 같은 Key의 모든 Match 조합이 결과에 남습니다.

중복도는 다음 비용을 증가시킵니다.

• Join 결과 A-Rows
• 후속 Sort·GROUP BY
• TEMP와 Client 전송
• 상위 Join의 입력 Cardinality

4.2 NULL

일반 Equijoin에서 NULL=NULL은 TRUE가 아니므로 서로 Match하지 않습니다.

Outer Join에서는 Join Type의 미Match 보존 규칙에 따라 NULL 확장 Row가 반환될 수 있습니다.

정렬 위치
  ≠ NULL 비교 의미

5. 비등치 Join과 Band Join

Hash Join은 일반적으로 Equality Hash Key가 필요합니다. 순수 비등치 Join에서는 Sort Merge 또는 NL이 주요 후보입니다.

SELECT e.employee_id,
       e.salary,
       g.grade
FROM   employees e
JOIN   salary_grade g
  ON   e.salary BETWEEN g.low_salary AND g.high_salary;

조건입니다.

e.salary >= g.low_salary
AND
e.salary <= g.high_salary

정렬된 범위 위치를 활용해 Match 가능한 Band를 비교할 수 있습니다.

5.1 범위 중첩

한 Salary가 여러 Grade Band와 겹치면 여러 Row와 Match합니다.

Employee 1행
× 겹치는 Grade 4행
= 결과 4행

비등치 Join이라고 무조건 Merge가 최적은 아닙니다.

비교합니다.

• 작은 입력을 이용한 NL Range Probe
• 각 Band의 중첩도
• Predicate 후 입력 A-Rows
• Sort Row 폭
• Workarea와 TEMP
• 전체 Fetch 여부

6. 비용 구조

6.1 Row 폭 줄이기

1,000,000행 × 24Byte
vs
1,000,000행 × 500Byte

행 수가 같아도 Sort Byte는 크게 다릅니다.

조인 전에 불필요한 Projection을 줄이면 다음을 줄일 수 있습니다.

• Workarea 요구량
• TEMP Write·Read
• CPU Copy·Compare
• Parallel Data 이동

단, Query Transformation으로 Projection 위치가 바뀔 수 있으므로 실제 Plan과 Row Size를 확인합니다.

7. Workarea와 TEMP

Sort·Hash·GROUP BY는 SQL Workarea를 사용합니다.

V$SQL_WORKAREA의 대표 Column입니다.

• OPERATION_TYPE
• OPERATION_ID
• ESTIMATED_OPTIMAL_SIZE
• ESTIMATED_ONEPASS_SIZE
• LAST_MEMORY_USED
• LAST_EXECUTION
• LAST_TEMPSEG_SIZE
• MAX_TEMPSEG_SIZE
• OPTIMAL_EXECUTIONS
• ONEPASS_EXECUTIONS
• MULTIPASSES_EXECUTIONS

예시입니다.

SELECT sql_id,
       child_number,
       operation_id,
       operation_type,
       estimated_optimal_size,
       estimated_onepass_size,
       last_memory_used,
       last_execution,
       last_tempseg_size,
       max_tempseg_size
FROM   v$sql_workarea
WHERE  sql_id=:sql_id
ORDER BY child_number, operation_id;

7.1 해석

LAST_EXECUTION='OPTIMAL'
  → 마지막 실행이 Memory 안에서 완료

'ONE PASS'
  → TEMP를 사용한 추가 Pass

'MULTI-PASS'
  → 반복 TEMP 처리 가능

LAST_TEMPSEG_SIZE가 NULL이면 마지막 실행에서 TEMP Segment를 만들지 않았음을 나타낼 수 있습니다.

7.2 Memory만 늘리기 전에

불필요한 입력 Row 감소
→ 불필요한 Column 감소
→ Cardinality 오류 수정
→ 적합한 Join Method 비교
→ 동시 Workarea 부하 확인
→ PGA 정책 검토

한 SQL의 PGA만 늘리면 다른 Concurrent Workarea와 전체 PGA 압력에 영향을 줄 수 있습니다.

8. NL·Hash·Merge 비교

8.1 선택 기준

작은 Outer + 효율적인 Inner Index
  → NL 우선 비교

대량 Equijoin + 적합한 Build Input
  → Hash 우선 비교

순수 Non-Equijoin 또는 정렬 활용
  → Sort Merge 우선 비교

규칙이 아니라 후보 우선순위입니다. 최종 판단은 Runtime으로 합니다.

9. 실행계획과 Runtime 검증

SELECT /*+ GATHER_PLAN_STATISTICS */
       ...
FROM   ...;

SELECT *
FROM TABLE(
  DBMS_XPLAN.DISPLAY_CURSOR(
    :sql_id,
    :child_no,
    'ALLSTATS LAST +PREDICATE +ALIAS +OUTLINE +NOTE'
  )
);

확인합니다.

입력

• Predicate 후 A-Rows
• Row Source Starts
• Access Path·Partition Pruning
• 예상 E-Rows와 실제 A-Rows

Sort

• SORT JOIN 위치
• Sort 입력 A-Rows
• OMem·1Mem·Used-Mem
• O/1/M
• Used-Tmp
• V$SQL_WORKAREA.LAST_EXECUTION
• TEMP Size

Merge

• Join 결과 A-Rows
• 중복 Key·Band 중첩
• Buffers·Reads·A-Time
• 후속 Sort·GROUP BY

상위 Operation 통계가 하위 작업을 포함할 수 있으므로 모든 Buffers·A-Time을 단순 합산하지 않습니다.

10. Hint 검증

10.1 LEADING·ORDERED

/*+ LEADING(d e) */
/*+ ORDERED */

• LEADING은 지정 Prefix의 Join Order를 유도합니다.
• ORDERED는 FROM 절 순서를 사용하도록 유도합니다.
• ORDERED가 있으면 LEADING보다 우선합니다.
• Join Graph 의존성이나 Hint 충돌로 무시될 수 있습니다.

10.2 USE_MERGE

/*+ LEADING(d e) USE_MERGE(e) */

USE_MERGE(e)는 e를 다른 Row Source와 연결할 때 Sort Merge 방식으로 Join하도록 유도합니다.

중요합니다.

USE_MERGE(e)
  → Join Order를 직접 지정하지 않음
  → e가 Inner Row Source일 때 의미가 있음

Oracle은 USE_MERGE·USE_NL을 LEADING·ORDERED와 함께 사용할 것을 권장합니다.

10.3 NO_USE_MERGE

/*+ NO_USE_MERGE(e) */

e를 Inner로 하는 Sort Merge 후보를 제외하도록 유도합니다. Hash 또는 NL이 반드시 선택되는 것은 아닙니다.

10.4 Alias·Query Block

Alias가 있으면 Hint에 실제 Alias를 사용합니다.

FROM employees e

/*+ USE_MERGE(e) */

Inline View·CTE·Transformation이 있으면 QB_NAME, +ALIAS, +OUTLINE과 Hint Report를 확인합니다.

11. 최종 결과 순서

Sort Merge Join은 내부적으로 Join Key 순서를 사용하지만 최종 결과 순서는 ORDER BY만 보장합니다.

순서를 바꿀 수 있는 요소입니다.

• 추가 Join
• GROUP BY·Hash Aggregate
• Parallel Execution
• View Transformation
• Adaptive Plan
• Plan 변경
• Input별 Sort·Scan 방향 변화

결정적인 정렬 예시입니다.

ORDER BY department_id,
         employee_id

Tie가 가능한 Column만 정렬하면 재실행 Top-N 결과가 달라질 수 있으므로 Unique Tie-Breaker를 포함합니다.

12. 실전 판단 절차

1. Join Type과 Equi·Non-Equi 조건을 확인한다.
2. 각 입력 Predicate 후 E-Rows·A-Rows와 Row 폭을 확인한다.
3. SORT JOIN이 어느 입력에 있는지 본다.
4. 첫 입력 Sort가 Index로 생략됐는지 확인한다.
5. Index ROWID Access와 Full Scan+Sort 비용을 비교한다.
6. V$SQL_WORKAREA와 Plan Memory·TEMP를 확인한다.
7. 중복 Key·Band 중첩으로 결과가 증가하는지 확인한다.
8. LEADING·USE_MERGE Hint 적용 여부를 실제 Cursor에서 확인한다.
9. NL·Hash·Merge를 동일 Bind·Fetch·Parallel로 비교한다.
10. 다른 Bind·동시 Workload와 결과 순서 회귀를 확인한다.

자주 혼동하는 판단