[Oracle/SQLD 공부] Nested Loop Join, Sorted Merge Join, Hash Join

오라클 옵티마이저 : SQL을 위한 최적의 실행계획을 생성하는 알고리즘

RDBMS에서는 정규화에 의해 연관된 데이터를 여러개의 테이블로 나누는데 원하는 형식의 데이터를 받아오기 위해 Join을 통해서 테이블을 연결해서 받아옵니다. 

데이터베이스 내부적으로 어떻게 조인을 하는지 아래 3가지 방식에 대해 정리해보겠습니다.

 

• Nested Loop Join
• Sorted Merge Join
• Hash Join

Join에서는 driving table 과 driven 테이블이 있습니다. 실행계획에서 먼저 실행되는 테이블이 driving table이고 나중에 실행되는 것이 driven 테이블입니다. 

 

1. Nested Loop Join의 특징

두개의 테이블의 행을 각각 모두 확인하여 조인하는 방법 (중첩된 for문 느낌)

• driving table 결정 후 driven 테이블에 반복적인 접근
• 한 레코드씩 순차적으로 접근
• 많은 양의 데이터 조인 시 Random Access 증가
• Random Access 위주의 조인 방식
• 소량의 데이터를 조인 시 사용
• 부분 범위 처리에 최적화
• 인덱스 구성 전략이 중요

2. Sorted Merge Join의 특징

두개의 테이블을 조인 칼럼으로 정렬하여 조인하는 방법, 조인되는 칼럼에 인덱스가 없는 경우 유리

• 조인 칼럼으로 정렬 후 조인을 수행
• 실시간으로 인덱스를 생성하는 것과 비슷
• 정렬할 데이터가 많은 경우 부담이 가장 큰 조인 방법
• 두 테이블을 개별적으로 읽고 조인
• outer table에 인덱스가 있을 경우 사용
• outer table이 정렬되어 있을 때 사용
• non equi join 사용 시에 사용

3. Hash Join의 특징

Hash Table을 생성하여 Hash Function에 의한 탐색을 하여 조인, 대용량의 데이터를 사용할 때 사용되며 일반적으로 Nested Loop Join 이나 Sorted Merge Join 보다 빠름

• 두 집합 중 크기가 작은 집합을 Outer Table로 결정
• Outer Table 이 Hash Area에 담길 정도로 충분히 작을 때 사용
• Outer Table의 해시 키 칼럼에 중복값이 거의 없을 때 사용
• 대량의 데이터 조인 시 사용
• 소량의 데이터 조인 시 오히려 불필요한 I/O가 증가할 수 있음
• Equi Join에서만 가능
• 조인칼럼에 적당한 인덱스가 없는데 Nested Loop Join이 비효율 적일 때 사용
• Nested Loop Join 에서 조인 칼럼에 인덱스가 있더라도 Random Access 부하가 심할 때 사용
• Sort Merge Join 사용 시 두개의 집합이 너무 커서 정렬하는데 부하가 심할 때 사용