[MSSQL] JOIN의 방식 - Nested loop Join / Merge Join / Hash Join

Join의 방식에 관하여

Join의 종류는 5가지가 있습니다.

1. INNER Join
2. OUTER Join
3. CROSS Join
4. FULL OUTER Join
5. SELF Join

Join의 방식은 3가지가 있습니다.

1. Nested Loop Join - 중첩반복
2. Merge Join - 정렬병합
3. Hash Join - 해시매치

Join의 종류는 논리적 Join이라고 합니다.
Join의 방식은 물리적 Join이라고 합니다.
이 포스트에서는 JOIN의 방식에 대해서 알아보겠습니다.

중첩반복(Nested Loops) 조인

바깥 테이블의 처리 범위를 하나씩 액세스하면서 그 추출된 값으로 안쪽 테이블을 조인하는 방식

1. 순차적으로 처리된다.
2. 바깥 테이블과 일치하는 값을 안쪽 테이블에서 찾아야 하므로 안쪽 테이블의 해당 열에 인덱스가 필요하다.
3. 메모리 사용량은 가장 적다.
4. 바깥 테이블과 안쪽 테이블의 크기는 성능과 관련이 없다.

순차적인 진행

첫 테이블 필터링 -> 두테이블간의 연결 -> 최종운반 단위 산출가지 반복적, 순차적으로 진행됩니다.

선행적

선행 테이블의 처리 범위가 전체 일의 양을 결정합니다.
후행 테이블의 필터링 조건은 선행 테이블에서 나온 결과를 한번 더 걸러주는 체크 조건 역할을 할 뿐 전체 처리량을 좌우하지 않습니다.

종속적

후행 테이블은 선행 테이블의 결과값을 받아 처리됩니다.
선행 테이블의 결과에 종속적입니다.
하지만 후행 테이블의 인덱스를 전체 일의 양을 줄여줄 수 있는 필터링 조건으로 사용 못합니다. (체크조건으로만 사용)

랜덤 액세스

선행 테이블의 결과를 통해 후행 테이블을 액세스 할대 랜덤 I/O가 발생합니다.
선행 테이블은 최초 ROW만 액세스가 발생하고 이후에는 스캔방식으로 진행합니다.

연결 고리의 중요성

SELECT *
FROM TAB1 A
     INNER JOIN TAB2 B ON A.KEY = B.KEY

A.KEY = B.KEY에서 보듯이 TAB1에서 처리한 row를 가지고 TAB2의 인덱스 페이지를 액세스하기때문에 TAB2의 인덱스 유무가 중요합니다.
만약 TAB2에 인덱스가 없다면 옵티마이저는 TAB2를 후행 테이블로 선택하지 않습니다.
그럴경우 인덱스가 있는 TAB1이 후행 테이블로써 성능면에서 유리하기 때문이다

장점

• 처리량이 적다
• 처리의 방향성이 필요
• 부분 범위 처리

  단점

  두 테이블을 연결할 때의 랜덤 i/o가 가장큰 부담

정렬병합(Sort Merge) 조인

양쪽 테이블의 처리 범위를 각자 액세스하여 정렬한 결과를 차례로 스캔하며, 연결고리 조건으로 Merge하는 방식을 말합니다.
이 방식은 경우에따라 Loop Join 보다 훨씬 빨라지는 경우도 많이 있으며, 랜덤 액세스가 줄어들어 시스템 부하를 감소 시킵니다.
하지만 일반적으로 Loop Join보다는 사용빈도가 적습니다.

동시적 처리

각 키에 의해 정렬된 양쪽 행들을 순차적으로 병합하여 조인을 수행합니다.

인덱스가 필요

양 테이블의 모두 조인키에 의해 정렬되어있어야 합니다.

전체 범위 처리

선행 테이블, 후행 테이블 크기는 성능과 관련이 없습니다.
그러나 선행 테이블에 중복행이 존재하지 않을때 메모리 사용량이 적으며 권장하고 있습니다.
부분 범위처리를 할 수가 없으며 항상 전체 범위를 처리합니다.

스캔방식

주로 스캔방식으로 처리합니다.
자신의 처리범위를 줄이기 위해 인덱스를 사용하는 경우만 랜덤 액세스이며 나머지작업은 스캔방식입니다.

조인의 방향과는 무관

테이블 스캔수는 한번

장점

• 처리량이 많을때 성능상 이점이 있다.
• 중첩반복(Nested Loops)은 연결고리의 상태가 굉장히 중요하다. 한쪽 연결고리에 이상이 발생하면 중첩반복은 심히 고려해야한다. 이때 연결고리에 영향을 받지않는 Sort Merge를 쓰면 좋다.

단점

• 정렬에 따른 부담 (메모리 사용 증가)
  정렬은 tempdb를 사용한다. 정렬양이 극도로 많아 tempdb의 임계치를 넘었을때 순간 전체 데이터베이스에 페이지잠금이 발생하는등 DB성능에 심각한 영향을 줄 수 있다.
  물론 가공없이 Clustered Index를 그대로 사용하게 되면 정렬은 안해도 되니 이때만큼은 정렬의 부담에서 해방된다.

참고

MSSQL에서는 양쪽 테이블에서 필터링 되어 나온 값이 각 테이블에서 유니크(Unique)할때만 이 조인방식을 사용하려는 경향이 있다고한다.
연결고리로 사용할 키값에 중복이 심하면 잘 선택하지 않으려고 한다고 하니 알아두자

해시매치(Hash Match) 조인, 해시(Hash) 조인

조인할 테이블에 대해서 해시 버킷을 생성하고 (이를 빌드입력이라한다) 해시 버킷의 순서대로 결과가 출력된다.
따라서 테이블의 인덱스는 사용되지 않으며, 인덱스가 없거나 임의성 쿼리에 탁월한 성능을 발휘한다.

적은 행에 대해 인덱스가 있는 테이블에 대해서는 중첩루프조인이 사용될 가능성이 높다.
하지만 용량이 커지고 행수가 많아지면 중첩 루프 조인은 행수 만큼의 테이블 스캔이 발생하므로 매우 느린 방법이다.
이때 해시 조인이 발생한다.

MSSQL 온라인 북에 있는 내용을 아래 추가 하였다.

해시 조인에는 빌드 입력과 검색 입력 등 두 가지 입력이 있습니다. 쿼리 최적화 프로그램은 두 가지 입력 중 작은 쪽이 빌드 입력이 될 수 있도록 이러한 역할을 할당합니다.

해시 조인은 여러 가지 유형의 집합 일치 연산, 즉 내부 조인, 왼쪽, 오른쪽, 완전 외부 조인, 왼쪽 및 오른쪽 세미 조인, 교집합, 합집합, 차집합 등에 사용합니다. 또한, 해시 조인의 변형은 중복 요소 제거 및 그룹화(예: SUM(salary) GROUP BY department)를 수행할 수 있습니다. 이러한 수정에서는 빌드 및 검색 역할 모두에 대해 한 개의 입력만 사용합니다.

다음 섹션에서는 인-메모리 해시 조인, 유예 해시 조인 및 재귀 해시 조인 등 여러 해시 조인 유형을 설명합니다.

 인-메모리 해시 조인
해시 조인은 먼저 전체 빌드 입력을 스캔하거나 계산한 다음 해시 테이블을 메모리에 작성합니다. 해시 키에 대해 계산된 해시 값에 따라 각 행이 해시 버킷에 삽입됩니다. 전체 빌드 입력이 사용 가능한 메모리보다 작으면 모든 행을 해시 테이블에 삽입할 수 있습니다. 이 빌드 단계 다음으로는 검색 단계가 이어집니다. 전체 검색 입력은 한 번에 한 행씩 스캔 또는 계산되며, 각 검색 행에 대해 해시 키 값이 계산되고 해당 해시 버킷이 스캔되며 일치하는 항목이 생성됩니다.

 유예 해시 조인
빌드 입력이 메모리 크기에 맞지 않으면 해시 조인은 몇 개의 단계로 진행됩니다. 이것을 유예 해시 조인이라고 합니다. 각 단계마다 빌드 단계와 검색 단계가 있습니다. 처음에는 전체 빌드 및 검색 입력이 사용되며 해시 키에 대한 해시 함수를 사용하여 여러 파일로 분할됩니다. 해시 키에 대한 해시 함수를 사용하면 2개의 조인 레코드가 모두 동일한 파일 쌍에 있는 것이 보장됩니다. 따라서 2개의 큰 입력을 조인하는 작업이 동일한 작업의 여러 개의 작은 인스턴스로 축소되었습니다. 그런 다음 해시 조인은 분할된 파일의 각 쌍에 적용됩니다.

 재귀 해시 조인
빌드 입력이 너무 커서 표준 외부 병합에 대한 입력에 여러 개의 병합 수준이 필요한 경우에는 여러 개의 분할 단계와 여러 개의 분할 수준이 요구됩니다. 일부 파티션만 큰 경우에는 해당 파티션에서만 추가 분할 단계가 사용됩니다. 모든 분할 단계를 가능한 한 빠르게 유지하기 위해서는 단일 스레드가 여러 개의 디스크 드라이브를 사용 중인 상태로 유지할 수 있도록 대형의 비동기 I/O 작업이 사용됩니다.

참고:
빌드 입력이 사용 가능한 메모리보다 조금밖에 크지 않다면 인-메모리 해시 조인과 유예 해시 조인의 요소가 단일 단계에서 결합되어 하이브리드 해시 조인이 생성됩니다.
최적화 중에 사용될 해시 조인을 확인하는 것이 항상 가능한 것은 아닙니다. 따라서 SQL Server 는 빌드 입력의 크기에 따라 인-메모리 해시 조인을 사용하여 시작된 후 유예 해시 조인, 재귀 해시 조인으로 점차 전환됩니다.

2개의 입력 중 빌드 입력이 되어야 하는 작은 쪽을 최적화 프로그램이 잘못 예측하는 경우에는 빌드 및 검색 역할이 동적으로 바뀝니다. 해시 조인은 작은 쪽의 오버플로 파일을 빌드 입력으로 사용하게 합니다. 이 기술을 역할 반전이라고 합니다. 역할 반전은 하나 이상의 해시 조인이 디스크에 "spill"된 경우 해시 조인 내에서 발생합니다.

연결고리

각 테이블의 연결고리의 인덱스는 사용하지 않는다!
대신 테이블에 대한 해시 버킷을 생성하며 그것을 통해 조인을 한다. 물론 조인이 되면 삭제된다. 그래서 반복적으로 명령을 수행할경우 매번 새로 생성합니다.

조인 결과

조인의 결과는 정렬하지 않는 상태로 출력된다. 그래서 특정 컬럼으로 정렬을 하고 싶다면 ORDER BY 절을 이용해야 합니다.

랜덤 액세스

랜덤 액세스가 있으나 중첩조인과는 달리 빠른 랜덤 액세스입니다.

메모리 사용

해시 버킷을 만들기 때문에 많은 메모리를 사용합니다.

사용방법

mssql 기준 아래와 같이 사용합니다.

Nested Loop Join

SELECT *
FROM Sales.Customer AS c
     INNER LOOP JOIN Sales.CustomerAddress AS ca ON c.CustomerID = ca.CustomerID

SELECT *
FROM Sales.Customer AS c
     INNER JOIN Sales.CustomerAddress AS ca ON c.CustomerID = ca.CustomerID
OPTION (LOOP join);

Merge Join

SELECT *
FROM Sales.Customer AS c
     INNER MERGE JOIN Sales.CustomerAddress AS ca ON c.CustomerID = ca.CustomerID

SELECT *
FROM Sales.Customer AS c
     INNER JOIN Sales.CustomerAddress AS ca ON c.CustomerID = ca.CustomerID
OPTION (MERGE join);

Hash Join

SELECT *
FROM Sales.Customer AS c
     INNER HASH JOIN Sales.CustomerAddress AS ca ON c.CustomerID = ca.CustomerID

SELECT *
FROM Sales.Customer AS c
     INNER JOIN Sales.CustomerAddress AS ca ON c.CustomerID = ca.CustomerID
OPTION (HASH join);

참고

Gravity DB Team
양군’s 블로그 - [MS-SQL] 조인 방식 (Join Method)
DevNote - [MSSQL] 조인의 종류 (inner join,left(right) outer join, cross join, ….)

MSSQL hint 사용법