-
1. 기본 매커니즘
해시조인은 둘 중 작은 집합(Build Input)을 읽어 해시 영역(Hash Area)에 해시 테이블(=해시 맵)을 생성하고,
반대쪽 큰 집합 (Probe Input)을 읽어 해시 테이블을 탐색하면서 조인하는 방식이다.
select /*+ordered use_hash(e)*/ d.deptno, d.dname, e.empno, e.ename from dept d, emp e where d.deptno=e.deptno ------------------------------------- Execution Plan ------------------------------------- 0 SELECT STATEMENT Opimizer=CHOOSE (Cost=5 Card=654 Bytes=35K) 1 0 HASH JOIN (Cost=5 Card=654 Bytes=35K) 2 1 TABLE ACCESS (FULL) OF 'DEPT' (Cost=2 Card=654 Bytes=14K) 3 1 TABLE ACCESS (FULL) OF 'EMP' (Cost=2 Card=327 Bytes=11K)
해시 함수는 출력값을 미리 알 순 없지만, 같은 입력값에 대한 같은 출력값을 보장하는 함수다. 다른 입력값에 같은 출력값이 나올 수 있는데 이를 해시 충돌이라 한다. 해시 테이블을 만들 때 해시 충돌이 발생하면, 입력값이 다른 엔트리가 한 해시 버킷에 감실 수 있다. 이런 원리를 바탕으로 해시 조인 과정을 더 자세히 보자.
1단계 : 해시 테이블 생성도 집합 중 작다고 판단되는 집합(Build Input)을 읽어 해시 테이블을 만든다.
해시 테이블을 만들 때 해시 함수를 사용한다. 해시 테이블은 해시 버킷으로 구성된 배열이라고 생각하면 된다. 해시 함수에서 리턴받은 해시 값이 같은 데이터를 같은 해시 버킷에 체인(연결리스트)로 연결한다.
2단계 : Probe Input 스캔
해시 테이블 생성을 위해 선택되지 않은 나머지 데이터 집합(Probe Input)을 스캔한다.
3단계 : 해시 테이블 탐색
Probe Input 에서 읽은 데이터로 해시 테이블을 탐색할 때도 해시 함수를 사용한다.
즉 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다.
해시 조인은, NL조인처럼 조인 과정에서 발생하는 랜덤 엑세스 부하가 없도 소트 머지 조인처럼 조인 전에 미리 양쪽 집합을 정렬하는 부담도 없다. 다만 해시 테이블을 생성하는 비용이 수반된다. 따라서 Build Input 이 작을 때 효과적이다.
만약 Hash Build 를 위해 가용한 메모리 공간을 초과할 정도로 Build Input 이 대용량 테이블이면 디스크에 썻다가 다시 읽어 들이는 과정을 거치기 때문에 성능이 많이 저하된다.
Build Input 으로 선택된 테이블이 작은 것도 중요하지만 해시 키 값으로 사용되는 컬럼에 중복 값이 거의 없을 때라야 효과적이다.
해시 테이블을 만드는 단계는 전체범위처리가 불가피하지만, 반대쪽 Probe Input 을 스캔하는 단계는 NL 조인처럼 부분범위처리가 가능하다.
2. Build Input 이 가용 메모리 공간을 초과할 때 처리 방식
만약 In-Memory 해시 조인이 불가능 할 때 DBMS 는 Grace 해시 조인이라고 알려진 조인 알고리즘을 사용한다.
이는 아래 두 단계로 나눠 진행된다.
가. 파티션 단계
조인되는 양쪽 집합(->조인 이외 조건절을 만족하는 레코드) 모두 조인 컬럼에 해시 함수를 적용하고, 반환된 해시 값에 따라 동적으로 파티셔닝을 실시한다. 독립적으로 처리할 수 있는 여러 개의 작은 서브 집합으로 분함으로써 파티션 짝(pair) 을 생성하는 간계다.
파티션 단계에서 양쪽 집합을 모두 읽어 디스크 상의 temp 공산에 일단 저장해야 하므로 In-Memory 해시 조인보다 성능이 크게 떨어지게 된다.
나. 조인 단계
파티션 단계가 완료되면 각 파티션 짝(pair) 에 대해 하나씩 조인을 수행한다. 이 때 각각에 대한 Build Input 과 Probe Input 은 독립적으로 결정된다. 즉 파티션하기 전 어느쪽이 작은 테이블이었는지에 상관없이 각 파티션 짝별로 작은 쪽 파티션을 Build Input 으로 선택해 해시 테이블을 생성한다.
해시 테이블이 생성되고 나면 반대쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색하며, 모든 파티션 짝에 대한 처리가 완료될 때까지 이런 과정을 반복한다.
Grace 해시 조인은 한마디로, 분할 정보 방식이라고 할 수 있다. 실제로는 DBMS 벤터마다 조금씩 변경된 형태의 하이브리드 방식을 사용하지만 두 개의 큰 테이블을 해시조인하는 기본 알고리즘은 Grace 해시 조인에 바탕을 두고 있다.
* Recursive 해시 조인 (NL 해시 조인)
디스크에 기록된 파티션 짝(pair) 끼리 조인을 수행하려고 '작은 파티션'을 메모리에 로드하는 과정에서 또다시 가용 메모리를 초과하는 경우가 발생할 수 있다. 그럴 때는 추가적인 파티셔닝 단계를 거치게 되는데, 이를 Recursive 해시 조인이라고 한다.
3. Build Input 이 해시 키 값에 중복이 많을 때 발생하는 비효율
해시 알고리즘의 성능은 해시 충동을 얼마나 최소화 할 수 있으냐에 달렸다. 이를 방지하려면 그만큼 많은 해시 버킷을 할당해야만 한다. 위 그림에서는 개념적으로 설명하기 위해 하나의 버킷에 여러 키 값이 달리는 구조로 표현했지만, DBMS 는 가능한 충분히 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력한다.
그런데 해시 버킷을 아무리 많이 할당하더라도 해시 테이블에 저장할 키 컬럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달릴 수 밖에 없다. 그러면 해시 버킷을 아무리 빨리 찾거라도 해시 버킷을 스캔하는 단계에서 많은 시간을 허비하기 때문에 탐색 속도가 현저히 저하된다.
Build Input 의 해시 키는 중복 값이 (거의) 없어야 해시 조인이 빠르게 수행될 수 있다.
4. 해시 조인 사용 기준
해시 조인의 성능을 좌우하는 두 가지 키 포인트는 다음과 같다.
1. 한쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야함
2. Build Input 해시 키 칼럼에 중복 값이 거의 없어야 함
두 가지 조건을 만족할 때 해시 조인이 가장 극적인 성능 효과를 낼 수 있다.
그럼 해시 조인을 언제 사용하는 것이 효과적인지 선택 기준을 살펴보자.
- 조인 컬럼에 적당한 인덱스가 없어 NL 조인이 비효율적일 때
- 조인 컬럼에 인덱스가 있더라고 NL 조인 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 랜덤 액세스 부하가 심할 때
- 소트 머지 조인을 하기에 두 테이블이 너무 커 소트 부하가 심할 때
- 수행 빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인할 때
수행시간이 매우 짧으면서 수행빈도가 매우 높은 쿼리(이는 OLTP 성 쿼리의 특징이기도 함)를 해시 조인으로 처리하면 어떤 일이 발생할까?
NL 조인에 사용되는 인덱스는 영구적으로 유지되면서 다양한 쿼리를 위해 재사용, 공유되는 구조이다.
반면 해시테이블은 단 하나의 쿼리를 위해 생성하고 조인이 끝나면 곧바로 소멸하는 자료구조다.
따라서 수행 빈도가 높은 쿼리에서 해시 조인을 사용한다면 CPU와 메모리사용률을 크게 증가시킴은 물론, 메모리 자원을 확보하기 위한 각종 래치 경합이 발생해 시스템 동시성을 떨어뜨릴 수 있다.
따라서 해시 조인은 1.수행빈도가 낮고, 2.쿼리 수행시간이 오래걸리는 3.대용량 테이블을 조인할 때 (배치 프로그램, DW, OLAP 성 쿼리의 특징) 주로 사용해야한다. OLTP 환경이라고 해서 해시 조건을 사용하지 못할 이유는 없지만 1~3번 조건을 만족하는지 체크해야한다.
출처
SQL 전문가 가이드 - 한국데이터산업진흥원
반응형