[MSSQL] 세 가지 JOIN 계획 정리

MSSQL에는 세 가지 JOIN 계획이 존재한다. 바로 Nested Loops Join(중첩 루프 조인), Merge Join(병합 조인), Hash Join(해쉬 조인)이다. 이는 각각 다른 상황에 최적의 성능을 내기 때문에 쿼리 옵티마이저는 통계를 보고 적절한 Join 계획을 세워 Join 동작을 수행한다.

일반적으로 쿼리 옵티마이저가 계획한 대로 실행하지만 쿼리 옵티마이저라고 항상 최적화 된 계획만 세우는 것은 아니다. 그렇기 때문에 적절한 때에 더 효율적인 Join 계획을 수동으로 넣어줘야 하는 경우가 생긴다. 각각의 Join 계획이 어떻게 동작하는지 알아보자.

 

---

 

Nested Loops Join (중첩 루프 조인)

한 쪽 Join의 입력이 작고(10 행 미만), 다른 한 쪽의 Join의 입력이 아주 크고 Join 열에 인덱스가 지정된 경우 가장 빠른 방법이다. (I/O 연산과 비교 연산이 가장 적게 필요하기 때문)

 

'Nested Iteration'이라고도 불리며, 한 쪽 Join의 입력을 외부 입력 테이블(외부 Loop)로 사용하고 다른 한 쪽 Join의 입력을 내부 입력 테이블(내부 Loop)로 사용한다. (외부 입력이 작고 내부 입력이 커야 효과적이다.)

 

 

중첩 루프 조인 종류

• Naive Nested Loops Join (원시 중첩 루프 조인): 내부 입력에 대해 전체 테이블 또는 인덱스를 스캔(scan)하는 경우
• Index Nested Loops Join (인덱스 중첩 루프 조인): 내부 입력에 대해 인덱스를 사용(seek)하는 경우
• Temporary Index Nested Loops Join (임시 인덱스 중첩 루프 조인): 내부 입력에 대해 인덱스가 쿼리 계획의 일부로 작성되고 쿼리 완료와 동시에 삭제되는 경우
  • 잘 발생하지는 않지만, run-time 시에 인덱스를 생성하는 쿼리 비용이 인덱스가 없는 상태에서 찾는 비용 보다 적다고 판단했을 경우 수행한다.
  • ex) 인덱스가 없고 크기가 큰 테이블에  반복적으로 접근(spool)하는 경우

특징

• 순차적: 두 테이블 간의 연결 및 최종 운반단위 산출까지 반복적이며 순차적으로 진행된다.
• 선행적: 선행 테이블의 처리 범위가 전체 일의 양을 결정한다.
• 종속적: 후행 테이블은 선행 테이블의 결과 값을 받아 처리된다.
•  (선행 테이블의 조건은 전체 처리량을 좌우하지만 후행 테이블의 조건은 최종 결과를 내보내기 전에 체크만 한다.)
• 랜덤 액세스: 선행 테이블의 결과를 통해 후행 테이블을 액세스할 때 랜덤 I/O가 발생한다.
•  (선행 테이블은 최초 행만 랜덤 액세스이고 이후에는 스캔 방식으로 액세스 한다.)
• 연결고리 중요성: 선행 테이블 열의 값을 가지고 후행 테이블의 인덱스 페이지를 액세스하기 때문에 후행 테이블의 인덱스 유무가 중요하다.
•  (인덱스가 존재하는 테이블을 후행 테이블로 선택한다.)

 

 

(Sort) Merge Join (병합 조인)

두 Join 입력이 작지 않지만 Join 열을 (인덱스로부터 미리) 정렬된 상태로 가져올 수 있는 경우 가장 빠른 방법이다.

• 두 입력의 크기가 서로 비슷할 경우에는 Merge Join과 Hash Join 성능이 비슷하지만, 두 입력의 크기가 서로 많이 다를 경우 Hash Join 성능이 더 좋다.
• 정렬 작업이 필요한 경우에는 비용이 많이 들 수 있다.

두 입력의 Join 열이 정렬되어 있고 ON절에 동등 연산(=)일 경우 수행되고, 정렬되어 있지 않다면 쿼리 옵티마이저가 Merge Join 아래에 정렬 연산자를 배치한다.

각 입력으로부터 행을 가져와서 비교하되, 행의 값이 동일하지 않은 경우 더 낮은 행이 무시되고 다른 행을 가져오면서 모든 행이 동일한 값을 찾을 때 까지 작업을 반복한다.

 

 

병합 조인 종류

• One to one (1-1): 두 입력이 중복이 없는 경우 (순서가 중요하지 않다.)
• One to many (1-M): 한쪽 입력이 중복이 없는 경우 (중복이 없는 입력이 최상위 입력이 된다.)
  • 최상위 열과 하위 열의 값이 동일하면 하위 행을 진행한다.
  • 다음 행이 이전 행과 동일한 값을 가지면 최상위 열의 값과도 동일하다.
  • 상위 입력은 하위 입력이 그 다음 높은 값에 도달하는 경우에만 그 다음 높은 값으로 진행된다.
• Many to many (M-N): 두 입력 모두 중복이 있는 경우
  • 1-M 알고리즘을 적용하면, 상위 행의 값과 같은 하위 행의 값을 모두 확인한 뒤 상위 입력을 진행했을 때, 상위 입력의 다음 행의 값이 이전 행의 값과 동일하다면 하위 입력은 다시 위로 진행할 방법이 없다.
    (getPrevious()를 지원하지 않고 getNext()만 존재하기 때문)
  • 이러한 문제점을 해결하기 위해 Tempdb에 다시 필요할 수 있는 데이터를 저장한다.
  • (상위 입력 하위 입력으로 중복이 처리될 때 하위 입력의 중복의 시작부분까지 되감아야 한다.)

특징

• 동시적: 양쪽 테이블을 동시에 읽고 양쪽 테이블이 조인할 준비가 되었을 때 Join을 수행한다.
•  (어느 한쪽의 테이블 처리가 늦어지면 다른 한쪽은 대기해야 한다.)
• 독립적: 처리 범위를 줄일 수 있는 수단은 각 테이블의 WHERE(필터링) 조건이다.
•  (인덱스를 사용하지 않는 단순 체크 조건이라도 범위를 줄여주기 때문에 체크 조건이 중요하다.)
• 전체 범위 처리: 정렬 작업 후 조인이 일어나므로 부분 범위 처리가 되지 않는다.
• 연결고리 중요 X: 정렬된 양쪽 결과를 스캔하는 방식이므로 인덱스 유무는 중요하지 않다.

참고로...

• 주로 스캔 방식으로 읽기 때문에 인덱스가 없는 경우에도 사용 할 수 있다.
• NL Join에서 부담이 되던 넓은 범위의 데이터를 처리할 때 이용되는 기법이다.
• 정렬할 데이터가 너무 많은 경우 메모리가 아닌 디스크를 사용하므로 성능 하락이 있다.
• 비동등 조인(<, >, ...)에 대해서도 조인 작업이 가능하다.

 

Hash (Match) Join (해쉬 조인)

Join 입력의 크기가 크고 정렬되지 않았으며 인덱싱되지 않은 입력을 효율적으로 처리한다.

 

두 종류의 입력이 있다.

• Build Input (outer table)
  • 해쉬 테이블을 만드는 데 사용되는 입력
  • 쿼리 옵티마이저가 두 입력 중 더 작은 입력을 build input으로 설정한다.
• Probe Input (inner table)
  • 해쉬 테이블을 탐색하는 입력

해쉬 조인은 여러 유형의 '집합 일치 연산'(inner/outer/semi join, intersection, union, difference 등), '중복 제거', '그룹핑'에 사용된다.

• '중복 제거', '그룹핑'의 경우에는 하나의 입력이 build/probe input 역할을 한다.

Build Input을 읽어 해쉬 영역(Hash Area)에 해쉬 테이블(=해쉬 맵)을 생성하고, Probe Input을 읽어 해쉬 테이블을 탐색하면서 조인하는 방식이다.

 

 

해쉬 함수

같은 입력 값에 대해 같은 출력 값을 보장하는 함수이다.

 

• 다른 입력 값에 대한 출력 값이 같은 경우 '해쉬 충돌'이라고 하는데, 해쉬 충돌이 발생하면 입력 값이 다른 엔트리가 하나의 해쉬 버킷(Hash Bucket)에 들어간다.
  • 해쉬 버킷에 들어갈 때 해쉬 값이 같은 입력 값들은 체인(linked list)으로 연결된다.
• 해쉬 테이블은 해쉬 버킷으로 구성된 배열이라고 생각하면 된다.

해쉬 조인 종류

In-Memory Hash Join (인 메모리 해쉬 조인)

해쉬 테이블을 메모리에 유지할 수 있는 경우의 조인 방법이다.

• Build Input을 읽어 해쉬 테이블을 생성한다. 이 때, 해쉬 함수를 이용한다.
  해쉬 테이블에는 해쉬 키와 결과에 출력될 컬럼들이 저장된다.
• Probe Input을 스캔하여 읽은 데이터로 해쉬 테이블 탐색한다. 여기서도 해쉬 함수를 이용한다.
  즉, 해쉬 값으로 버킷을 찾아가 해쉬 체인을 스캔하며 데이터를 탐색한다.

Grace Hash Join (유예 해쉬 조인)

해쉬 테이블을 저장할 메모리가 부족해서 디스크가 필요한 경우의 조인 방법으로, 아래 두 단계로 나누어 진행된다.

 

1. 파티션 단계

 

• WHERE 조건으로 양쪽 테이블을 필터링한다.
• 해쉬 함수 적용해서 해쉬 값에 따라 파티셔닝 후 각각의 파티션 별로 Tempdb에 임시 파일로 저장한다.
• 같은 해쉬 함수를 적용했기 때문에 양쪽 테이블은 같은 해쉬 키를 기반으로 파티셔닝한다. (같은 해쉬 키를 가진 두 파티션을 파티션 pair라고 한다.)

 

2. 조인 단계

 

• 파티션 pair에서 한 쪽의 파티션 파일에 대해 해쉬 함수를 적용해 해쉬 테이블을 생성한다. 이 때, 파티션 pair에 대해 어떤 파티션을 Build Input으로 할지는 독립적으로 결정된다.
• 파티션 pair에서 반대 쪽 파티션 파일의 row를 하나씩 읽으면서 해쉬 테이블을 탐색한다.
• 모든 파티션 pair에 대한 처리가 완료될 때 까지 이 과정을 반복한다.

-> 파티션 단계에서 양쪽 집합을 모두 읽어 Tempdb에 저장해야하므로 In-Memory Hash Join보다 성능이 크게 떨어진다.

-> 분할 정복 (Divide & Conquer) 방식과 유사하다.

 

 

Recursive Hash Join (= Nested Loops Hash Join) (재귀 해쉬 조인)

• Tempdb에 있는 파티션 pair끼리 조인을 수행하려고 '작은 파티션'을 메모리에 로드하는 과정에서 다시 가용 메모리를 초과하는 경우, 추가적인 파티셔닝 단계를 수행한다.

Hybrid Hash Join

• Build Input이 가용 메모리보다 조금 밖에 크지 않다면 In-Memory Hash Join과 Grace Hash Join요소가 결합되어 조인한다.

특징

• 각 테이블의 열에 있는 인덱스를 사용하지 않는다.
• 동등 조인(=)에서만 사용 가능하다.
• 조인 결과가 정렬되지 않는다. (버킷의 순서대로 결과 출력)
• 해쉬 테이블 랜덤 액세스 방식이다. (But, NL Join와 같은 부하는 생기지 않는다.)
• Build Input이 작을 경우 & 해쉬 값에 중복이 거의 없을 경우 효과적이다.
  • 해쉬 값에 중복이 없으려면,(2) 해쉬 충돌이 나지 않아야 한다.
  • (1) 해쉬 함수를 적용할 열에 중복이 없어야 하고
• 해쉬 테이블을 만들 때 전체 범위 처리가 불가피하지만 Probe Input을 스캔하는 단계는 부분 범위 처리가 가능하다.
• 해쉬 함수를 사용해 서로 비교하므로, 페이지 I/O는 적지만, CPU 사용량이 많을 수 있다.
• 조인 속도가 NL Join과 Merge Join에 비해 빠르지만, 해쉬 테이블 생성 시 CPU와 메모리가 필요하고 일회성이라는 것이 단점이다.

사용 기준

• NL Join에 사용되는 인덱스는 (Drop하지 않는 한) 영구적으로 유제되면서 다양한 쿼리를 위해 공유 및 재사용되는 자료구조이다.
• 해쉬 테이블은 단 하나의 쿼리를 위해 생성하고 조인이 끝나면 곧바로 소멸하는 자료구조이다.
• 즉, Hash Join은 수행빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인할 때 주로 사용해야 한다.

참고로...

• 옵티마이저는 Build Input의 크기에 따라 계획을 In-Memory Hash Join -> Grace Hash Join -> Reculsive Hash Join으로 점차 전환한다.
• 역할 전환(= role reversal): 옵티마이저가 Build Input과 Probe Input을 잘못 예측한 경우 동적으로 역할이 바뀌는 것을 의미한다.
  • 역할 전환은 쿼리 계획에 나타나지 않기 때문에 사용자가 인식할 수 없다.
• Null 값은 조인 대상에서 제외된다.

 

 

 

[참고한 사이트]

 

• 조인(SQL Server) - Microsoft docs
• Introduction to Nested Loop Joins in SQL Server
• The many (too many?) reads of a many to many Merge Join
• [MS-SQL] 조인 방식 (Join Method)
• DBGuide.net