SQL Hash Join(해시 조인) - Build Input, Probe Input

이번 포스팅에서는 Join 수행 방식 중 세 번째로 Hash Join을 살펴보겠습니다. rdbms 중 특히 오라클에서는 hash 조인이라는 것을 재공 합니다. 대용량 조인에  효율적인 조인 작업이라고 할 수 있습니다. 또한 Hash map에 대한 오라클에 자부심 또한 강한데요. 그 만큼 쿼리의 성능 향상에 도움을 주는 것은 사실입니다. 
 

 

Hash Join이란

해시 Join은 두 테이블 간의 조인 작업을 효율적으로 실행하기 위해 Hash map을 사용하는 알고리즘입니다. 이 방법은 기존 Nested Loop,  Sort Merge 조인에서 부족할 수 있는 대규모 데이터 세트를 처리할 때 특히 유용합니다. 그러면 어떻게 작동할까요?
 

수행 방식

1. 파티셔닝

• 해시 조인은 조인 작업을 위해 두 테이블 중 하나를 Bulid Input 테이블로 지정합니다. 각 행은 조인 키의 해시 값을 기반으로 특정 파티션에 할당됩니다. 이 단계는 동일한 조인 키를 가진 행이 동일한 파티션에 있도록 만들어 효율적인 조인을 위한 기반을 마련합니다.

2. 해싱

• 각 파티션 내의 조인 키 값을 hash 함수에 넣어 해시 테이블을 생성합니다. 해시 테이블을 사용하면 조인 작업 중에 빠른 조회가 가능합니다. 이 원리로 기존 Nested Loop 또는 Sort Merge 조인 방법에 비해 시간이 크게 줄어듭니다.

3. Probe 단계

• 프로브 단계 동안 Hash 조인은 두 번째 테이블을 처리하여 조인 키에 대한 해시 값을 생성합니다. 그런 다음 알고리즘은 파티셔닝 단계에서 생성된 해시 테이블에서 해당 hash 값을 조회하여 일치하는 행을 효과적으로 식별합니다.

4. 조인 후 결과 출력

• 일치하는 행이 식별되면 Hash 조인이 이를 결합하여 최종 결과 세트를 생성합니다. 이 접근 방식의 장점은 최적의 메모리 사용으로 대규모 데이터 세트를 처리하여 리소스 경합을 줄인다는 데 있습니다.

 

Hash Join

 

Hash Join 특징

• Build Input은 SELECT 절 Column들을 모두 포함하여 Hash Map 생성함
• Memory 크기보다 작아야 효율적임, 이유는 SELECT 절 Column 개수 최소화되야 유리함
• Build Input의 Hash 키 Column 고유 값 많을수록 빠름, 이유는 Hash 체인에 대한 탐색이 감소하기 때문
• 데이터 건수가 적은 테이블을 선행 테이블(Build Input)로 두는 것이 유리 - Nested Loop와 동일함
• 각 테이블에 INDEX가 반드시 필요한 것은 아님 - 해당 데이터를 해시 맵을 만들기 때문에 인덱스를 꼭 사용하는 것은 아님

장점

• Join으로 인한 Random Access, Sort 부하가 없음
• PGA 영역에서의 처리하기 때문에 Latch 경합 없어 빠른 속도를 낼 수 있음
• 메모리(PGA) 내 조인을 수행하기 때문에 디스크 I/O를 크게 줄여 쿼리 실행 속도를 높이는 데 도움이 됨

단점

• 해시 조인의 경우 등치(=) 조건만 사용 가능
• CPU 연산 및 Memory 활용 특성 상 OLTP 환경에서 수행빈도 높으면 CPU/Memory 사용률 크게 증가함
• 큰 Table이면서 NDV가 낮은 Column일수록 Hash 체인 탐색 중복으로 인한 심한 성능 저하 발생됨

NDV : Number of Distinct Value의 약자이다. 말 그래도 유일하게 구별되는 Column값의 개수이다. 만일 Column c1이 {'A', 'B', 'C', 'D', 'E'} 다섯 가지 종류의 값으로 이루어져 있다면 NDV(C1) = 5가 된다. (출처 : 구글)

 

Nested Loop Join vs Sort Merge Join vs Hash Join 비교

1. Nested Loop Join

• 온라인 트랜잭션이 많고 부분범위처리(Paging 처리 등)가 가능할 때 사용
• 조인하는 Table은 크지만 조건(where) 등으로 추출 Data 양은 적을 때

Nested Loop Join 원리

 2. Sort Merge Join

• Outer Table에 조인 컬럼 Index가 있어 Sort 대체가 가능할 때
• Group by, Order by 등으로 이미 Sorting 된 Inline View와 Join 시 Inner Table이 작을 때
• 데이터셋이 매우 커서 Nested Loop Join이 힘들고, 조건이 등치(=)가 아니어서 Hash Join도 어려운 때

Sort Merge Join 원리

3. Hash Join

• 수행 빈도 낮은 대용량 Table Join 시 Index가 없어서 Nested Loop Join이 힘들 때
• Index가 있어 Nested Loop도 가능하지만 Join 량이 많아 Inner Table Random Access 가 많이 발생될 때
• 두 Table이 PGA에 못 담을 만한 크기이거나, 담겨도 Sort/Merge 부하가 클 때

 

마무리

Hash 조인은 과도한 디스크 I/O 작업을 메모리 공간의 Hash map으로 최소화하는 방식입니다. Hash 조인의 튜닝은 병렬처리 옵션(parallel)과 같이 사용하여 대규모 데이터 처리에 적합합니다. 그래서 주로 배치 프로그램에 많이 사용합니다. 실행계획도 약간은 복잡한 형태를 보입니다. 이 부분은 좀 더 고급 레벨이기 때문에 여기서는 해시 조인을 통해 큰 테이블의 조인을 처리하기 용의하다는 정도만 이야기 하겠습니다.