SQL (25) - Merge JOIN

이번 포스트에서는 SQL에서 JOIN을 수행하는 3가지 방법 중에서 Merge JOIN에 대해 알아보겠습니다.

Merge JOIN은 병합 JOIN으로 부르지만,

내부적으로 정렬과정도 거치게 되므로 Sort-Merge JOIN으로 부르기도 합니다.

 

1) Merge JOIN

Merge JOIN은 다음의 과정을 거쳐 수행됩니다.

 

• 우선, Sort를 수행(이미 정렬된 상태라면  SKIP), 최종적으로 O(n * logn)의 시간복잡도
• 다음으로 Merge를 수행하는데, Outer(FROM의 인자)의 상태에 따라 다르게 수행됨
  • One-to-Many : Outer에 중복이 없는 경우
    • Outer의 데이터 개수를 a, Inner의 데이터 개수를 b라고 표현한다면
    • a * O(a + b)의 시간복잡도를 갖게 됨
  • Many-to-Many : Outer에 중복이 있는 경우
    • Outer의 데이터 개수를 a, Innre의 데이터 개수를 b라고 표현한다면
    • a * O(a * b)의 시간복잡도를 갖게됨

위와 같은 과정을 거쳐서 수행됩니다.

따라서 Merge JOIN을 사용하는 가장 이상적인 경우는

Outer로 사용되는 데이터 테이블에서 중복이 없는 상황이 됩니다.

 

2) Merge JOIN의 예시

다음은 Merge JOIN으로 사용할 2개의 쿼리입니다.

SELECT *
FROM players AS p
	INNER JOIN salaries AS s
	ON p.playerID = s.playerID;

SELECT *
FROM schools AS s
	INNER JOIN schoolsplayers AS p
	ON s.schoolID = p.schoolID;

 

우선 위의 쿼리를 먼저 실행해보겠습니다.

 

두 개의 데이터 테이블 모두에서 Index Scan과 더불어 Sort가 수행되는 것을 확인할 수 있습니다.

이는 곧 Many-to-Many가 수행되었다는 것인데, 두 데이터 테이블을 한번 살펴보겠습니다.

 

 

위와 같이 구성되었습니다.

Outer로 사용된 players 테이블의 경우는 Primary Key가 playerID가 아니기 때문에 Many이고,

Innre로 사용된 salaries의 경우 playerID가 가장 뒤에 있으므로 역시 Many로 취급되고 있습니다.

 

이어서 다음 쿼리의 실행 결과를 살펴보겠습니다.

 

이전 쿼리와는 다르게 Index Scan이 이뤄지긴 했지만, Sort가 생략된 것을 확인할 수 있습니다

두 개의 데이터 테이블을 확인해보겠습니다.

 

 

schools 테이블의 경우 Primary Key를 schoolID로 사용하여 정렬이 되어 있으므로 정렬이 생략되었고,

schoolsplayers 테이블만이 Sort 후에 데이터를 찾아오는 과정이 수행되었습니다.

 

따라서 다음과 같은 결론을 얻을 수 있습니다.

 

3) Merge JOIN에서의 유의사항

• Merge JOIN은 Outer와 Inner 모두를 Sort하고 Merge하여 JOIN한다 
• 이미 정렬되었다면 Sort는 생략한다
• 따라서 One-to-Many로 수행하는 것이 효과적이다
• One-to-Many로 수행하기 위해서는 Primary Key나 UNIQUE 키를 사용해주는 것이 좋다
• Loop JOIN과는 다르게 랜덤하게 접근하지는 않는다
• 정렬할 데이터의 양이 많다면 Hash JOIN을 사용하는 것이 효과적이다