#title Merge Join 
[[TableOfContents]]

앞서서 MSSQL Server의 Join 방식 중 가장 기본적인 Join 방식인 Nested Loop Join을 다루었다. 이제 대용량 데이터베이스에서 자주 볼 수 있는 Merge Join에 대해서 다룬다. Merge Join은 아래와 같이 각각의 테이블을 정렬 후 비교를 한다. 개념은 매우 간단하다. 연결이 될 때는 '=' 연산을 해야 한다는 제약조건이 있다. ('=' 이외에는 모두 Loop Join이다.) 

attachment:merge_join01.jpg

==== SQL Server 2000에서의 Merge Join ====
SQL Server 2000에서는 필자의 경험상 연결고리가 정렬이 된 상태면 무조건 Merge Join했었다. 실제 예를 보자. 

{{{
use pubs
go
 
select *
from employee a inner join jobs b
on a.job_id = b.job_id

--'jobs' 테이블. 스캔 수 43, 논리적 읽기 수 86, 물리적 읽기 수 1, 미리 읽기 수 0.
--'employee' 테이블. 스캔 수 1, 논리적 읽기 수 2, 물리적 읽기 수 0, 미리 읽기 수 0.

}}}

attachment:merge_join02.jpg

Nested Loop Join으로 풀렸다. Merge Join으로 바꾸기 위해서 힌트를 사용해도 되지만, Merge Join의 개념을 바탕으로 정렬 후 비교를 하도록 해보자. 

{{{
select *
from (select top 100 percent * from employee order by job_id) a inner join
        (select top 100 percent * from  jobs order by job_id) b
on a.job_id = b.job_id
}}}

attachment:merge_join03.jpg

실제로 Order By절을 이용하여 Job_Id로 정렬을 시도했지만 Jobs 테이블은 정렬 아이콘이 보이지 않는다. 이유는 Clustered Index가 Job_Id로 정렬되어 있으므로 정렬이 필요없다고 옵티마이저가 판단했기 때문이다. 연결될 두 테이블을 모두 정렬 후 비교를 시도했더니 Merge Join으로 풀렸다. SQL Server 2000에서는 이렇게 일부러 정렬을 하거나 연결고리가 모두 Clustered Index면 대부분 Merge Join으로 풀렸다. 2000 이후 버전은 어떨까?

==== SQL Server 2005 이상 버전에서의 Merge Join ====
SQL Server 2008에서 위에서와 똑같은 쿼리문을 던져보겠다. 
{{{
--employee.job_id에 clustered index가 존재하면 삭제한다.
select *
from (select top 100 percent * from employee order by job_id) a inner join
        (select top 100 percent * from  jobs order by job_id) b
on a.job_id = b.job_id
}}}

attachment:merge_join04.jpg

Loop Join으로 풀렸다. employee 테이블을 먼저 읽었지만 job_id로 정렬을 하지 않았다. 필자의 의도는 Merge Join을 수행하게 하여 job_id로 정렬된 결과를 얻으려고 했다. 하지만 SQL Server 2008은 필자의 의도대로 움직여 주지 않았다. SQL Server 2005 이후 버전은 정렬을 원한다면 반드시 정렬을 하라고 SQL에 표시를 해줘야 한다. 정렬에 대해서는 [Ordered]를 참고하기 바란다. 그래서 필자는 다음과 같이 SQL문을 수정하였다. 

{{{
select *
from (select top 100 percent * from employee order by job_id) a inner join
        (select top 100 percent * from  jobs order by job_id) b
on a.job_id = b.job_id
order by a.job_id

--또는
select *
from employee a inner join jobs b
on a.job_id = b.job_id
order by a.job_id
}}}
attachment:merge_join05.jpg

이제서야 Merge Join을 볼 수 있다. employee.job_id에 Clustered Index를 생성한다면 어떨까? 필자는 확신할 수 없었다. 2000버전이라면 두 연결고리가 정렬된 상태를 보장한다면 Merge Join으로 실행계획이 풀렸다. 하지만 2005 버전 이상은 Order By를 명시[* 앞선 예처럼 명시도 잘해야 한다.]하지 않는 이상은 정렬되었다는 것을 보장할 수 없다. 그러므로 employee.job_id에 Clustered Index가 생성되어 있다고 해도 Merge Join으로 실행계획을 풀릴지는 알 수 없다. 또한 물리적으로 정렬되었다고 해도 2005버전 이후부터는 Merge Join으로 풀릴지 확실히 예상 할 수 없다. 왜냐하면 [Ordered]문서에서도 언급했듯이 이제는 Clustered Index를 이용한다고 해도 정렬을 보장할 수 없기 때문이다. 중요한 것은 이러한 DBMS 옵티마이저가 올바른 판단을 할 수 있도록 좋은 환경을 만들어주는 것이며, 좋은 환경에서도 원하는 실행계획을 볼 수 없다면 DB쟁이들이 옵티마이저의 결론에 딴지를 걸어야 한다는 것이다. 그러므로 DB쟁이는 자신이 원하는 실행계획을 만들어 낼 수 있어야 한다. 물론 실행계획을 해석 할 줄 아는 것이 먼저겠지만..


==== merge join의 순서 ====
먼저 #temp1, #temp2 테이블을 만들자. #temp1은 1백만 건, #temp2는 1백건이다. 참고로 64bit, 32core/64thread, 256GB ram에서 실행했다.
{{{
select top 1000000
    row_number() over(order by (select 1)) rownum
,   a.name
into #temp1
from master.dbo.spt_values a
    cross join master.dbo.spt_values b
    cross join master.dbo.spt_values c

select top 100
    row_number() over(order by (select 1)) rownum
,   a.name
into #temp2
from master.dbo.spt_values a
    cross join master.dbo.spt_values b
    cross join master.dbo.spt_values c
}}}

'''건수가 많은 테이블 먼저 읽는 경우'''
{{{
set statistics time on

select b.*
from #temp1 a
    inner merge join #temp2 b
        on a.rownum = b.rownum
option(force order, maxdop 4)
/*
 SQL Server 실행 시간: 
 CPU 시간 = 1686밀리초, 경과 시간 = 481밀리초
SQL Server 구문 분석 및 컴파일 시간: 
   CPU 시간 = 0ms, 경과 시간 = 0ms.

 SQL Server 실행 시간: 
 CPU 시간 = 0밀리초, 경과 시간 = 0밀리초
*/
}}}

'''건수가 적은 테이블 먼저 읽는 경우'''
{{{
set statistics time on

select a.*
from #temp2 a
    inner merge join #temp1 b
        on a.rownum = b.rownum
option(force order, maxdop 4)
/*
 SQL Server 실행 시간: 
 CPU 시간 = 172밀리초, 경과 시간 = 65밀리초
SQL Server 구문 분석 및 컴파일 시간: 
   CPU 시간 = 0ms, 경과 시간 = 0ms.

 SQL Server 실행 시간: 
 CPU 시간 = 0밀리초, 경과 시간 = 0밀리초
*/
}}}

응답시간도 건수가 적은 테이블 먼저 읽는 경우가 빠르다. 이는 ssis의 merge join에서도 확인 할 수 있다. 조인되는 어느 한쪽 테이블이 모두 build input 되면 그 다음부터는 훨씬 빨라진다.
==== 어떤 경우에 유리한가? ====
Merge Join은 비교되는 데이터의 양이 많고 두 테이블의 데이터 액세스의 양이 비슷할 때 유리하다. 데이터의 양이 적은 테이블을 먼저 읽는 것이 성능상 유리하다는 것은 merge join역시 유효하다. OLTP 환경에서 Merge Join이나 Table Spool, Index Spool이 많이 보인다면 일단은 많은 양이 처리되거나 적절한 Index 설계가 되지 않은 경우가 많이 있다. 대부분은 MSSQL Server의 옵티마이저가 잘 판단해주지만 환경[* DB설계, Index설계, 열악한 H/W등]이 좋지 않다면 적절하지 않은 실행계획이 세워질 수 있다. 

==== 참고자료 ====
 * attachment:LoopJoin/Join_Algorithm.pdf