[MSSQL/SQL SERVER] JOIN의 물리적 구조

1. Nested Loops Join

 

한 조인의 입력은 작고 다른 조인의 입력이 큰 경우에 효과적인 방식.
TABLE1에서 TABLE2 방향으로 조인이 될 때 TABLE1을 외측 테이블 TABLE2를 내측 테이블이라 칭함.
외측 테이블과 일치하는 모든 행을 내측 테이블에서 반복하여 찾는 방식. 즉 조인횟수는 외측 테이블의 입력에 의해 결정됨. 그렇기 때문에 WHERE절에서 걸리는 필터는 외측테이블에 걸려야 조인의 크기를 줄일 수 있다.
내측 테이블의 조인 조건의 컬럼에 인덱스가 있는 경우 효과적임. 만약 적절한 인덱스가 없다면 매번 전체 테이블을 읽어야 한다.
다른 방식에 비해 메모리 사용량이 가장 적고 외측 테이블을 정렬 후 조인을 할 경우에 더 효율적이다.
외측 테이블에서 내측 테이블에 접근할 때 랜덤 I/O가 발생한다.

랜덤I/O : 논리/물리 순서와 상관없이 한 건을 읽기 위해 한 페이지씩 접근하는 것. 한번에 하나의 페이지만을 액세스 한다. 인덱스를 액세스하여 확인한 rowid를 이용하여 테이블을 액세스 하는 경우 발생.

확인 랜덤 액세스 : where 조건의 컬럼이 인덱스에 존재하지 않아 테이블을 액세스하는 랜덤 액세스

 

 

2. Sort Merge Join

 

TABLE1에서 TABLE2 방향으로 조인이 이루어질때 TABLE1을 첫 번째 입력, TABLE2를 두 번째 입력이라 칭한다.
양 테이블이 모두 조인키에 의해 정렬되어 있어야 함.
각 키에 의해 정렬된 양쪽 행들을 순차적으로 병합하여 조인이 수행됨.
양쪽 테이블에서 스캔 수가 한번이라는 장점이 있음.
첫 번째 테이블과 두 번째 테이블의 크기는 성능과 관련이 없다.
첫 번째 테이블이 중복 행이 존재하면  임시테이블을 사용하여 메모리 사용량이 증가한다. 즉 첫 번째 테이블에 중복 행이 없을 경우 메모리 사용량이 적어진다.
이를 피하기 위해선 UNIQUE INDEX, UNIQUE CONSTRAINT과 GROUP BY로 묶는 방법이 있다.
Merge 조인은 한 개 이상의 '=' 조건이 존재해야함. 하지만 FULL OUTER JOIN은 예외이다.

 

입력 조건에 따른 효율은 다음과 같다.

 

3. Hash Match Join

 

해시 키와 해시 테이블을 통해서 조인을 하며 해시 키는 해시 테이블의 인덱스 역할을 한다.
테이블은 빌드 입력(Build Input), 검색 입력(Prove Input)으로 나누어 지며 옵티마이저는 작은 테이블을 빌드 입력으로 설정한다.
조인 조건의 컬럼이 정렬이 필요가 없으며 해시 버킷의 순서대로 결과가 출력되기 때문에 결과값은 정렬되어있지 않다.
조인 조건에는 Equal(=)조건이 필요하다.
조인 컬럼의 인덱스 유무가 속도에 영향을 안준다.
메모리가 부족한 경우 시간이 오래 걸림.

In-Memory Hash Join (인 메모리 해시 조인, 해시 테이블을 메모리에 유지할 수 있는 경우)

 1. 작은 테이블을 빌드 입력을 설정하고 이를 읽어 해시 테이블을 생성한 뒤 각 행을 해시 버킷에 삽입.
 2. 검색 입력을 row 단위로 읽어서 해시 테이블을 탐색하며 동일 값을 조인.
 3. 1~2를 반복

Grace Hash Join (유예 해시 조인, 메모리가 부족한 경우)

1. 인 메모리 해시 조인처럼 해시 테이블을 생성.
2. 메모리에 해시 테이블을 저장할 수 없기 때문에 해시키 기반으로 된 임시 파일로 저장
3. 검색 입력도 해시키를 기반으로 임시 파일 중 한개를 선택해서 해시키와 출력에 필요한 컬럼들을 같이 저장. 해시키를 기반으로 저장되기 때문에 해시키를 통해 임시 파일을 찾을 수 있음.
4. 임시 파일을 메모리에 올려 해시조인 진행

해시 재귀 : 유예 해시 조인에서 테이블을 해시키를 기반으로 분할할 때 분할 후에도 메모리에 모두 저장할 수 없는 경우 재 분할 함.

해시 재귀 초과 :  해시 재귀가 일정 횟수 이상 반복 될 경우

→ 프로파일러의 Hash Warning Event를 통해 확인 가능.