Sort Merge Join

Sort Merge Join

두 테이블을 각각 조인 키 기준으로 정렬(Sort Phase)한 후 순차적으로 병합(Merge Phase)하여 일치하는 행을 찾는 조인 방식

특징: 정렬 비용 발생하나 범위/비동등 조인 가능, 이미 정렬된 데이터에 매우 효율

동작원리

시간복잡도

• •정렬 포함: O(N·logN + M·logM) + O(N+M) 병합
• •이미 정렬 시: O(N + M) 병합만 수행

구성요소: 정렬 단계(Sort Phase), 병합 단계(Merge Phase), 정렬 버퍼

최적화 포인트

• •조인 키에 인덱스 있으면 정렬 생략 → 성능 대폭 향상
• •ORDER BY/GROUP BY와 조인 키 일치 시 추가 정렬 불필요

적용사례: 이미 정렬된 데이터, 범위 조인(>, <, BETWEEN), 비동등 조인

비교: SM(범위조인가능/정렬비용) vs Hash(동등만/해시비용) vs NL(소량/인덱스)

연관: 조인, 정렬, 실행계획, 인덱스