[Database] JOIN 기법의 종류 (Nested Loops Join, Merge Join, Hash Join)

조인에는 세 가지 기법이 존재한다.

 

1. 중첩 루프 조인 (Nested Loops Join)

2. 병합 조인 (Sort Merge Join)

3. 해시 조인 (Hash Join)

 

다양한 상황에서 최적의 성능을 내기 위해 적절한 JOIN 계획을 세워 동작을 수행한다.

일반적으로 옵티마이저가 계획을 세워 동작을 수행하지만, 항상 최적화된 계획만을 세우지는 않는다.

그런 경우, 수동적으로 JOIN 계획을 세워 넣어줘야하는 경우가 있다.

 

각각의 JOIN 계획이 어떻게 동작하며, 어떤 상황에 어떤 기법이 효과적인지 알아보자.

 

1. 중첩 루프 조인 (Nested Loops Join)

---

NL Join 방식

조인하려는 두 개의 테이블 중 더 작은 테이블을 선행 테이블 (Outer Table) 이라 하고, 더 큰 테이블을 후행 테이블 (Inner Table) 이라고 한다.

선행 테이블에서 결합 조건에 일치하는 레코드를 후행 테이블에 반복적으로 탐색하며, 조인하는 방식이다.

이 때 선행 테이블(Outer Table) 이 작고, 후행 테이블(Inner Table) 이 커야 효과적이다.

 

 

NL Join 특징

1) 인덱스 필수

Join 열에 해당하는 컬럼들은 인덱스를 가지고 있어야 한다. 인덱스가 없으면 성능이 매우 떨어질 수 있다.

NL 조인은 두 개의 테이블의 모든 조합을 비교하는 랜덤 액세스 위주의 조인 방식이며, 선행 테이블을 기준으로 한 레코드씩 순차적으로 진행한다.

이때, 적절한 인덱스가 없다면 Inner Table(후행 테이블) 을 탐색할 때마다 반복적으로 Full Scan 을 수행하므로 매우 비효율적이다.

랜덤 액세스 범위를 좁히기 위한 인덱스 구성 전략이 특히 중요하며, 만약 인덱스가 없다면 다른 기법의 조인(Sort Merge Join, Hash Join) 을 추천한다.

*랜덤 액세스 방식: 테이블의 레코드를 순차적으로 읽는 것이 아니라, 레코드의 위치와 관계없이 필요한 레코드에 직접 액세스하는 방식이다. 이를 위해서는 디스크에서 레코드를 읽기 위해 디스크 I/O 작업을 수행해야한다.

 

2) 작은 데이터에 적합

하지만 인덱스를 완벽히 구성하여도 데이터 자체가 크다면, 해당 데이터를 모두 랜덤 액세스해야 하기 때문에 대량 데이터 처리에는 매우 비효율적이다.

NL 조인은 작은 테이블을 처리할 때 빠르고 효율적이지만, Outer Table 의 크기가 커질수록 성능이 저하될 수 있다.

 

3) OLTP 시스템에 적합

NL 조인은 작은 데이터 집합에 대해 빠르게 처리할 수 있어 실시간성인 OLTP 시스템에 적합하다. OLAP 시스템에서는 데이터의 양이 매우 크기 때문에 다른 방식의 조인 기법(Sort Merge Join, Hash Join) 을 추천한다.

 

 

 

 

2. 병합 조인 (Sort Merge Join)

---

Sort Merge Join 방식

조인하려는 두 개의 테이블(Outer Table, Inner Table) 을 조인 컬럼을 기준으로 오름차순 정렬한 후, 두 개의 테이블에서 정렬된 조인 대상 키를 스캔하면서 조인 결과를 생성하는 방식이다.

 

Sort Merge Join 특징

1) NL 조인 단점 보완안

Merge 조인은 NL 조인의 (대량 집합 조인에 대한) 랜덤 액세스 방식의 비효율을 줄이고자 나온 방식이다.

Inner Table 을 반복적으로 탐색하는 NL 조인과 달리 Merge 조인은 두 테이블을 한 번에 액세스 한 후 메모리에서 모두 정렬 후 비교해서 탐색한다.

 

2) 정렬 작업에 의한 비용 발생

정렬된 데이터이기 때문에 일치하는 값들을 빠르게 찾아낼 수 있어 성능이 좋으나, 정렬 작업에 의한 비용이 발생한다.

정렬할 데이터가 너무 많아 메모리(tempdb) 에서 수행하기 어려운 경우 디스크를 사용하므로 성능 하락이 있을 수 있다.

대용량의 테이블이라면 정렬 작업에 큰 비용이 부담되기 때문에 조인 컬럼에 인덱스를 생성하여 정렬 작업을 생략할 수 있도록 하는 것이 좋다.

단, 클러스터인덱스가 아닌 넌클러스터 인덱스를 사용할 경우 Lookup 비용을 발생할 수 있어 이 점도 고려해야한다.

 

3) 스캔 방식 사용

랜덤 액세스 방식을 사용하는 NL 조인과 달리 Sort Merge 조인은 주로 스캔 방식을 사용한다.

정렬을 먼저 진행한 테이블들을 순차적으로

스캔하기 때문에 인덱스를 사용하지 않는다.

각 테이블을 1회씩만 읽기 때문에 이는 테이블의 크기가 큰 경우 더 효율적이다.

 

4) 동등 조건(=) 필요

조인 조건 중 동등 조건(=) 이 있어야한다. '=' 조건은 두 테이블의 조인 키 값이 정확히 일치하는 행을 쉽게 찾는데 사용된다.

다른 비동등 조건(<,>,!=) 을 사용하면 정렬된 순서를 활용하기 어려우며 이는 조인의 성능을 저하시킬 수 있다.

하지만 FULL OUTER JOIN 의 경우, '=' 조건 없이도 가능하다.

 

5) 중복 데이터 제거 필요

중복 값이 아주 많은 경우, 중복 데이터를 제거하기 위해 메모리에서 임시 테이블을 생성하게 되는데 이는 많은 비용을 발생시킨다. (*아래 M-N 방식 참고)

이를 피하기 위해 UNIQUE INDEX 를 생성하거나, GROUP BY 로 묶는 방법 등 중복 데이터 처리가 중요하다.

 

Sort Merge 조인 종류

1) One to one (1-1)

두 테이블에 중복이 없는 경우이다.

 

2) One to many (1-M)

한쪽 테이블에 중복이 없는 경우이다.

중복이 없는 테이블이 Outer Table 이 되며, Outer Table 을 기점으로 중복이 있는 Inner Table 을 순차적으로 스캔하게 된다. 

 

3) Many to many (M-N)

두 테이블에 모두 중복이 있는 경우이다. 

1-M 방식처럼 Outer Table 을 기점으로 Inner Table 을 순차적으로 스캔하게 된다.

그러나 M-N 에서는 Outer Table 에도 중복 데이터가 존재한다. 그러나, Inner Table 에서 다시 위로 진행할 방법이 없다.

이 때, Tempdb 를 사용하여 다시 사용이 필요한 데이터를 저장하게 된다.

 

 

 

 

3. 해시 조인 (Hash Match Join)

---

Hash Join 방식

조인 대상의 두 테이블 중 데이터가 더 작은 테이블을 Build Input(빌드 입력) 이라 하고, 큰 테이블을 Probe Input(프로브 입력) 이라고 한다.

Build Input 테이블의 조인 컬럼에 Hash Function(해시 함수) 를 이용해서 Hash Key(테이블의 인덱스 역할) 을 생성 후, Hash Table(해시 맵) 을 생성한다. 그리고, Probe Input 테이블의 조인 조건에 맞는 해시 테이블을 탐색하며, 해시 함수를 적용하여 해시 키를 생성하고, 해시 테이블에서 같은 해시 키를 찾아서 조인을 진행하는 방식이다.

 

 

Hash Join 특징

1) Nested Loops 조인, Sort Merge 조인 단점 보완안

조인 대상 테이블에 인덱스가 없고 결과를 정렬할 필요가 없을 때 효율적으로 사용할 수 있는 조인 방법이다.

Merge Join 을 하기에는 테이블의 크기가 너무 크거나, M-N 의 관계의 경우 해시 조인을 사용하면 좋다.

이 경우, 조인 속도가 NL 조인과 Sort Merge 조인에 비해 빠르다.

 

2) Hash Function (해시 함수) 사용

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

(예를 들어, SHA-256 해시 함수는 어떤 크기와 형식의 데이터도 256비트 길이의 출력으로 반환된다. 암호화 코드 생각하면 된다.)

입력 값에 대한 출력 값이 같을 경우를 '해시 충돌' 이라고 하는데, 해시 충돌이 발생하면 해당 값이 Hash Bucket (해시 버킷) 에 들어간다.

이 해시 버킷에 들어간 값들 중 해시 값이 동일한 값들은 체인으로 연결된다.

 

3) Hash Table (해시 테이블) 사용

해시 버킷으로 구성된 배열이다. 해시 테이블은 데이터를 빠르게 처리할 수 있는 장점이 있지만, 메모리를 많이 사용하는 단점이 있다.

또, 해시 테이블은 생성 후 조인이 끝나면 곧바로 소멸하여 재활용이 불가능하다.

 

4) 동등 조건(=) 필요

 

 

 

Hash Join 종류

아래와 같이 4가지 계획이 존재하며, 옵티마이저가 Build Input 크기에 따라 1번 부터 4번까지 순차적으로 점차 전환하며 실행한다.

1) In-Memory Hash Join

2) Grace Hash Join

3) Recursive Hash Join

4) Hybrid Hash Join

 

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

해시 테이블을 메모리에 유지할 수 있는 경우의 조인 방법이다. 해시 함수를 이용하여 Build Input 을 스캔하여 해시 테이블을 생성한다.

해시 테이블에는 해시 키와 결과에 출력될 컬럼들이 저장된다. 해시 함수를 통해 Probe Input 을 스캔하여 읽은 데이터로 해시 테이블을 탐색한다.

해시 값으로 버킷을 찾아가 해쉬 체인을 스캔하며 데이터를 탐색한다.

 

2) Grace Hash Join (유예 해시 조인)

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

 

파티션 단계

▪ where 조건으로 양쪽 테이블을 필터링한다.

▪ 해시 함수를 적용해서 해시 값에 따라 파티셔닝 한 후, 각각의 파티션 별로 Tempdb 에 임시 파일로 저장한다.

▪ 각 테이블에는 동일한 해시 함수가 적용되며, 같은 해시 키를 가지게 된다. 이러한 두 파티션을 Partition Pair 라고 한다.

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

 

조인 단계

▪ Partition Pair 에서 한 쪽의 파티션 파일에 대해 해시 함수를 적용하여 해시 테이블을 생성한다.

▪ 이 때 옵티마이저의 판단에 따라 Build Input, Probe Input 의 테이블이 정해진다.

▪ Partition Pair 에서 반대쪽 파티션 파일의 row 를 하나씩 읽어가며 해시 테이블을 탐색한다.

▪ 이 과정을 모든 Partition Pair 에 대한 처리가 완료될 때까지 반복한다.

 

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

Tempdb 에 있는 Partition Pair 끼리 조인을 수행하려고 더 작은 파티션을 메모리에 올리는 과정해서 또 메모리를 초과하는 경우, 추가적인 파티셔닝 단계를 수행한다.

 

4) Hybrid Hash Join

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