[2] Sort Merge Join

• 두 테이블을 각각 정렬한 다음에 두 집합을 머지(Merge)하면서 조인을 수행한다.
• 실제 조인 수행 과정이 NL Join과 크게 다르지 않다.
• outer 집합과 inner 집합을 미리 정렬해 둔다는 점만 NL Join과 다르다.

(1) Sort Merge Join을 사용하는 경우

조인 칼럼을 선두로 갖는 인덱스가 없어서 Outer 테이블에서 읽히는 건마다 Inner 테이블 전체를 스캔해야 할 때

(2) Sort Merge Join 과정

Outer 집합(정렬된 dept)에서 첫 번째 로우 o를 가져온다. 
Inner 집합(정렬된 emp)에서 첫 번째 로우 i를 가져온다. 
loop 
  양쪽 집합 중 어느 것이든 끝에 도달하면 loop를 빠져나간다. 
  if o = i 이면 
    조인에 성공한 로우를 리턴한다. 
    inner 집합에서 다음 로우 i를 가져온다. 
  else if o < i 이면 
    outer 집합에서 다음 로우 o를 가져온다. 
  else (즉, o > i 이면) 
    inner 집합에서 다음 로우 i를 가져온다. 
  end if 
end loop

첫번째 , 소트 단계

• 양쪽 집합을 조인 칼럼 기준으로 정렬한다.
• 만약 조인 칼럼에 인덱스가 있으면(Oracle의 경우 Outer 테이블에만 해당) 소트 단계를 거치지 않고 곧바로 조인할 수도 있다.
• Inner 집합인 emp 테이블이 정렬돼 있기 때문에 조인에 실패하는 레코드를 만나는 순간 멈출 수 있다.

두번째 , 머지 단계

• 정렬된 양쪽 집합을 서로 머지(merge)한다.
• 정렬된 emp에서 스캔 시작점을 찾으려고 매번 탐색하지 않아도 된다.
• 레코드를 찾는 ②번 스캔은 ①번에서 스캔하다가 멈춘 지점을 기억했다가 거기서부터 시작한다.
  • Outer 집합인 dept 테이블도 같은 순서로 정렬돼 있기 때문에 가능하다/

(3) Sort Merge Join 특징

1. 특징

• 조인 하기 전에 양쪽 집합을 정렬한다.
• 양쪽 집합을 조인 칼럼 기준으로 정렬한 후에 조인을 시작한다.
• 대량 집합 조인은 Random 액세스 위주의 NL Join의 경우 비효율적이며 이 비효율을 줄이고자 나온 조인 방식이 Sort Merge Join이다.
• 만약 정렬해야 할 집합이 초대용량 테이블이면 정렬 자체가 큰 비용을 수반하기 때문에 성능 개선 효과를 얻지 못할 수도 있다.
  • 일반 인덱스나 클러스터형 인덱스처럼 미리 정렬된 오브젝트를 이용하면 정렬작업을 하지 않고 바로 조인을 수행할 수 있어 Sort Merge Join이 좋은 대안이 될 수 있다.
• 부분적으로, 부분범위처리가 가능하다.양쪽 집합을 정렬해야 함으로 부분범위처리가 불가능할 거 같지만, 부분적으로는 가능하다.
  • Outer 집합이 조인 칼럼 순으로 미리 정렬된 상태에서 사용자가 일부 로우만 Fetch 하다가 멈춘다면 Outer 집합은 끝까지 읽지 않아도 되기 때문이다.
• 테이블별 검색 조건에 의해 전체 일량이 좌우된다.두 집합을 각각 정렬한 후에 조인하기 떄문이다.
  • 집합의 크기, 즉 테이블별 검색 조건에 의해 전체 일량이 좌우된다.
  • NL Join은 Outer 집합의 매 건마다 Inner 집합을 탐색한다. Outer 집합에서 조인 대상이 되는 건수에 의해 전체 일량이 좌우된다.
• 스캔 위주의 조인 방식이다.(NL Join은 Random 액세스 위주의 조인 방식이다.)
• Inner 테이블을 반복 액세스하지 않으므로 머지 과정에서 Random 액세스가 발생하지 않는다.
• Random 액세스가 발생하는 경우
  • 각 테이블 검색 조건에 해당하는 대상 집합을 찾을 때 인덱스를 이용한 Random 액세스 방식으로 처리된다.
  • 이때 발생하는 Random 액세스량이 많다면 Sort Merge Join의 이점이 사라질 수 있다.

2. Oracle

• 조인 연산자가 부등호이거나 아예 조인 조건이 없어도 Sort Merge Join으로 처리한다.

3. SQL Server

• 조인 연산자가 ‘=’ 일 때만 Sort Merge Join을 수행한다.