3-4-2. 소트 머지 조인
과목3. SQL 고급 활용 및 튜닝
제4장 조인 튜닝
제2절 소트 머지 조인
NL Join은 조인 칼럼을 선두로 갖는 인덱스가 있는지가 매우 중요하다. 만약 조인 칼럼을 선두로 갖는 인덱스가 없으면 Outer 테이블에서 읽히는 건마다 Inner 테이블 전체를 스캔하기 때문이다. 그럴 때 옵티마이저는 Sort Merge Join이나 다음 절에서 설명할 Hash Join을 고려한다. Sort Merge Join은 이름이 의미하는 것처럼 두 테이블을 각각 정렬한 다음에 두 집합을 머지(Merge)하면서 조인을 수행한다. Sort Merge Join은 아래 두 단계로 진행된다.
① 소트 단계 : 양쪽 집합을 조인 칼럼 기준으로 정렬한다. ② 머지 단계 : 정렬된 양쪽 집합을 서로 머지(merge)한다.
만약 조인 칼럼에 인덱스가 있으면(Oracle의 경우 Outer 테이블에만 해당) ①번 소트 단계를 거치지 않고 곧바로 조인할 수도 있다. Oracle은 조인 연산자가 부등호이거나 아예 조인 조건이 없어도 Sort Merge Join으로 처리할 수 있지만, SQL Server는 조인 연산자가 '=' 일 때만 Sort Merge Join을 수행한다는 사실에도 유념하기 바란다.
1. 기본 메커니즘
아래 SQL은 dept 테이블을 기준으로 emp 테이블과 조인할 때 Sort Merge Join 방식을 사용하라고 힌트로 지시하고 있다.
[예제] Oracle
0
SELECT STATEMENT Optimizer = CHOOSE (Cost = 11 Card = 654 Bytes = 35K)
1
0
MERGE JOIN (Cost = 11 Card = 654 Bytes = 35K)
2
1
SORT ( JOIN ) (Cost = 6 Card = 654 Bytes = 14K)
3
2
TABLE ACCESS (FULL) OF 'DEPT' (Cost = 2 Card = 654 Bytes = 14K)
4
1
SORT ( JOIN ) (Cost = 5 Card = 327 Bytes = 11K)
5
4
TABLE ACCESS (FULL) OF 'EMP' (Cost = 2 Card = 327 Bytes = 11K)
[예제] SQL Server
--Merge Join(Inner Join, MANY-TO-MANY MERGE:([d].[deptno]) =([e].[deptno]))
| --Sort(ORDER BY:([d].[deptno] ASC))
| | --Table Scan(OBJECT:([SQLPRO].[dbo].[dept] AS [d]))
| --Sort(ORDER BY:([e].[deptno] ASC))
| --Table Scan(OBJECT:([SQLPRO].[dbo].[emp] AS [e]))
Sort Merge Join의 수행 과정을 그림으로 도식화하면 [그림 Ⅲ-4-29]와 같다.
[그림 Ⅲ-4-29]에서 주목할 점은, Inner 집합인 emp 테이블이 정렬돼 있기 때문에 조인에 실패하는 레코드를 만나는 순간 멈출 수 있다는 사실이다. 예를 들어, deptno=10인 레코드를 찾기 위해 ①번 스캔을 진행하다가 20을 만나는 순간 멈춘다. 또 한 가지는, 정렬된 emp에서 스캔 시작점을 찾으려고 매번 탐색하지 않아도 된다는 점이다. 예를 들어, deptno=20인 레코드를 찾는 ②번 스캔은 ①번에서 스캔하다가 멈춘 지점을 기억했다가 거기서부터 시작하면 된다. Outer 집합인 dept 테이블도 같은 순서로 정렬돼 있기 때문에 가능한 일이다. 아래는 Sort Merge Join이 머지하는 방식을 pseudo 코드로 작성한 것이다.
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
[그림 Ⅲ-4-29]와 위 pseudo 코드를 잘 살펴보면, 실제 조인 수행 과정이 NL Join과 크게 다르지 않다. outer 집합과 inner 집합을 미리 정렬해 둔다는 점만 다르다. 다시 말하지만, 양쪽 집합을 먼저 정렬해 두었기 때문에 위와 같은 처리 로직이 가능하다.
2. Sort Merge Join의 특징
Sort Merge Join은 다음과 같은 특징을 가진다.
조인 하기 전에 양쪽 집합을 정렬한다.
NL Join은 정렬 없이 Outer 집합을 한 건씩 차례대로 조인을 진행하지만, Sort Merge Join은 양쪽 집합을 조인 칼럼 기준으로 정렬한 후에 조인을 시작한다. 대량 집합 조인은 random 액세스 위주의 NL Join의 경우 비효율이 있고, 이 비효율을 줄이고자 나온 조인 방식이 Sort Merge Join이다. 만약 정렬해야 할 집합이 초대용량 테이블이면 정렬 자체가 큰 비용을 수반하기 때문에 성능 개선 효과를 얻지 못할 수도 있다. 하지만, 일반 인덱스나 클러스터형 인덱스처럼 미리 정렬된 오브젝트를 이용하면 정렬작업을 하지 않고 바로 조인을 수행할 수 있어 Sort Merge Join이 좋은 대안이 될 수 있다.
부분적으로, 부분범위처리가 가능하다.
Sort Merge Join은 양쪽 집합을 정렬해야 함으로 부분범위처리가 불가능할 거 같지만, 부분적으로는 가능하다. Outer 집합이 조인 칼럼 순으로 미리 정렬된 상태에서 사용자가 일부 로우만 Fetch 하다가 멈춘다면 Outer 집합은 끝까지 읽지 않아도 되기 때문이다.
테이블별 검색 조건에 의해 전체 일량이 좌우된다.
NL Join은 Outer 집합의 매 건마다 Inner 집합을 탐색한다. Outer 집합에서 조인 대상이 되는 건수에 의해 전체 일량이 좌우되는 이유다. 그러나 Sort Merge Join은 두 집합을 각각 정렬한 후에 조인함으로 각 집합의 크기, 즉 테이블별 검색 조건에 의해 전체 일량이 좌우된다.
스캔(Scan) 위주의 조인 방식이다.
NL Join이 random 액세스 위주의 조인 방식이라면 Sort Merge Join은 스캔 위주의 조인 방식이다. Inner 테이블을 반복 액세스하지 않으므로 머지 과정에서 random 액세스가 발생하지 않는 것이다. 하지만, random 액세스가 전혀 없는 것은 아니다. 각 테이블 검색 조건에 해당하는 대상 집합을 찾을 때 인덱스를 이용한 random 액세스 방식으로 처리될 수 있고, 이때 발생하는 random 액세스량이 많다면 Sort Merge Join의 이점이 사라질 수 있다.
Last updated
Was this helpful?
