[ Oracle ] Nested Loop Join,Sort-Merge Join,Hash Join의 비교

 

안녕하세요.

오늘은 Oracle에서 plan 확인시 자주 마주치는

Nested Loop Join,Sort-Merge Join,Hash Join 3가지 조인 방식에 대하여 간략히 비교해보겠습니다.

 

1. Nested Loop Join (NL 조인)

 

실행 방식 -

• 외부 테이블(Outer Table)의 모든 행을 순회하면서, 각 행에 대해 내부 테이블(Inner Table)에서 일치하는 행을 찾습니다.
• 내부 테이블에서 일치하는 행은 인덱스를 통해 빠르게 조회하거나, 테이블 전체를 검색(Full Table Scan)합니다.
• 알고리즘 구조 - 
  • 외부 테이블에서 첫 번째 행을 읽음.
  • 내부 테이블에서 조인 조건에 맞는 행을 검색.
  • 결과를 결합 후, 다음 외부 테이블 행으로 이동.
  • 외부 테이블의 모든 행에 대해 반복.

장점 -

• 구현이 간단하고, 작은 데이터셋에 적합합니다.
• 외부 테이블이 작고 내부 테이블에 인덱스가 있는 경우 빠르게 동작.

단점 - 

• 조인 조건이 없는 경우, 외부 테이블 크기 × 내부 테이블 크기만큼의 반복 작업 수행(시간 복잡도 O(N×M)).
• 테이블 크기가 크면 매우 비효율적.

 

 

2. Sort-Merge Join

 

실행 방식 -

• 두 테이블을 조인 키로 정렬한 후, 정렬된 데이터를 순차적으로 병합하면서 조인합니다.
• 알고리즘 구조 -
  • 두 테이블의 조인 키를 기준으로 정렬.
  • 정렬된 데이터를 앞에서부터 읽으며, 동일한 키를 가진 데이터를 매칭.
  • 조인 조건에 맞는 결과를 생성.

예시 - 

• 테이블 A: {1, 2, 3}
• 테이블 B: {2, 3, 4}
• 정렬 후 병합: 2, 3이 조인 조건에 맞음.

장점 -

• 대량의 데이터를 처리할 때 효율적.
• 정렬된 입력 데이터를 처리하거나, 인덱스 정렬된 데이터를 사용할 때 빠름.
• 순차 접근을 하므로, 디스크 I/O 효율성이 높음.

단점  -

• 두 테이블 모두 정렬해야 하므로, 정렬 비용이 발생.
• 정렬된 데이터가 없거나 메모리가 부족하면 성능 저하.

 

 

3. Hash Join

 

실행 방식  -

• 해시 테이블(Hash Table)을 이용해 데이터를 매칭.
• 알고리즘 구조 -
  • 작은 테이블(빌드 입력, Build Input)을 메모리에 올려 해시 테이블 생성.
  • 큰 테이블(프로브 입력, Probe Input)을 순회하며, 해시 테이블에서 일치하는 키를 찾음.

단계  -

• Build 단계: 작은 테이블에서 조인 키를 기준으로 해시 테이블 생성.
• Probe 단계: 큰 테이블을 순회하면서 해시 테이블에서 조인 키 검색.

장점  -

• 조인 키에 대한 인덱스가 없어도 효율적.
• 테이블이 클수록 Nested Loop Join보다 빠르게 동작.

단점  -

• 메모리 의존적: 메모리가 충분하지 않으면 디스크로 해시 테이블을 분할 저장해야 하며, I/O 비용 증가.
• 조인 키 값의 중복이 많거나 데이터 분포가 불균형하면 성능 저하.

 

조인 비교 -

 

조인 방식	시간 복잡도	주요 활용 사례	장점	단점
NL 조인	O(N×M)	외부 테이블 작고, 내부 테이블에 인덱스가 있는 경우	간단한 구현, 소규모 데이터에 적합	대규모 데이터 처리 시 비효율적
Sort-Merge 조인	O(NlogN + MlogM)	대량 데이터, 조인 키로 정렬된 데이터, 순차 접근이 가능한 대량 데이터 처리	대량 데이터 처리에 효율적	정렬 비용 발생, 정렬되지 않은 경우 성능 저하
Hash 조인	O(N+M)	인덱스 없는 대량 데이터, 조인 키 값이 적은 경우	메모리 기반 빠른 조인	메모리 부족 시 디스크 I/O 발생

 

적합한 선택 -

• NL 조인: 소규모 데이터 또는 인덱스를 활용한 조인. [ 제일 우선 고려 ]
• Hash 조인: 대량 데이터이면서 적당한 인덱스가 없는 경우. [ 2순위 ]
• Sort-Merge 조인: 대규모 데이터. [ 3순위 ]

 

감사합니다.