CH02. 조인 원리와 활용 - 03.해시조인

(1)기본 매커니즘

7.3버전에서 처음 소개된 해시 조인은 소트 머지 조인과 NL조인이 효과적이지 못한 상황에 대한 대안으로 개발되었습니다. 해시 조인은 둘 중 작은 집합(Build input)을 읽어 Hash Area에 해시 테이블을 생성하고, 반대쪽 큰 집합(Probe input)을 읽어 해시 테이블을 담색하면서 조인하는 방식입니다.

 

해시조인은 해시테이블을 생성할 때 해시함수를 사용합니다. 즉, 해시 함수에서 리턴받은버킷 주소로 찾아가서 해시 체인에 엔트리를 연결합니다. 해시 테이블을 탐색할 때도 해시 함수를 사용합니다. 해시 함수에서 리턴받은 버킷 주소로 찾아가서 해시 체인을 스캔하면서 데이터를 찾습니다.

해시 조인은 NL조인처럼 조인과정에서 발생하는 Random 액세스 부하가 없고(양쪽 집합을 읽는 과정에서 인덱스를 이용한다면 Random 액세스가 발생함) 소트 머지조인처럼 조인 전에 미리 양쪽 집합을 정렬하는 부담도 없습니다. 다만 해시 테이블을 생성하는 비용이 수반됩니다. 따라서 Build Input이 작을 때 효과적이라고 할 수 있습니다.

구체적으로 PGA메모리에 할당되는 Hash Area에 담길 정도로충분히 작아야 합니다. 만약 Build Input이 Hash Area 크기를 초과한다면 디스크에 썼다가 다시 읽어 들이는 과정을 거치기 때문에 성능이 많이 저하됩니다.

Build Input으로 선택된 테이블이 작은 것도 중요하지만 해시 키 값으로 사용되는 컬럼에 중복 값이 거의 없을 때라야 효과적입니다.

 

NL조인과 비교하면 Inner 루프가 Hash Area애 미리 생성해 둔 해시 테이블을 이용한다는 점만 다릅니다. 해시 테이블을 만드는 단계는 전체범위처리가 불가피하지만 반대쪽 Probe Input을 스캔하는 단계는 NL조인처럼 부분범위처리가 가능합니다.

 

해시조인이 인덱스 기반의 NL조인보다 빠른 결정적인 이유는, 해시 테이블이 PGA영역에 할당된다는 점입니다. NL조인은 Outer 테이블에서 읽히는 레코드마다 Inner 쪽 테이블 버퍼 캐시 탐색을 위한 래치 획득을 반복하지만, 해시 조인은 래치 획득 과정 없이 PGA에서 빠르게 데이터를 탐색합니다.

 

(2) 힌트를 이용한 조인 순서 및 Build Input 조정

아래는 해시 조인할 때의 실행계획이며 HASH JOIN(id=1) 자식 노드 중 위쪽(dept)이 Build Input이고 아래쪽이 Probe Input입니다.

 

    select /*+ use_hash(d e) */ d.deptno,d.dname,e.empno,e.ename

     from dept d, emp e

where d.deptno=e.deptno

 

 

Execution Plan
----------------------------------------------------------
Plan hash value: 615168685

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |    14 |   364 |     7  (15)| 00:00:01 |
|*  1 |  HASH JOIN         |      |    14 |   364 |     7  (15)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| DEPT |     4 |    52 |     3   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| EMP  |    14 |   182 |     3   (0)| 00:00:01 |
---------------------------------------------------------------------------

 

use_hash 힌트만을 사용했음으로 Build Input을 옵티마이저가 선택했습니다. deptp가 선택된 이유는 통계정보상 더 작은 테이블이기 때문입니다.

사용자가 직접 선택하고자 할 때는 swap_join_inputs힌트나 2개 테이블을 해시 조인할 때는 leading이나 ordered 힌트를 사용하면 됩니다.

 

(3) 두가지 해시 조인 알고리즘

(4) Build Input이 Hash Area를 초과할 때 처리 방식

만약, In-memory 해시 조인이 불가능할 때 오라클은 어떤방식으로 해시 조인을 처리할까요?

Grace 해시조인

1)파티션 단계

조인되는 양쪽 집합(-> 조인 이외 조건절을 만족하는 레코드) 모두 조인 컬럼에 해시 함수를 적용하고, 변환된 해시 값에 따라 동적으로 파티셔닝을 실시합니다. 독립적으로 처리할 수 있는 여러 개의 작은 서브 집합으로 분할함으로써 파티션 짝을 생성하는 단계입니다.

파티션 단계에서 양쪽 집합을 모두 읽어 디스크 상의 Temp 공간에 저장해야하므로 In-Memory 해시 조인보다 성능이 크게 떨어지게 됩니다.

 

2)조인 단계

파티션 단계가 완료되면 각 파티션 짝에 대해 하나씩 조인을 수행합니다. 이때 Build Input은 독립적으로 결정되고 해시테이블이 생성됩니다. 그러고 나면 반대 쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색하며 모든 파티션 짝에 대한 처리가 완료될 때까지 과정을 반복합니다.

Grace조인은 한마디로 분할,정복 방식이라 할 수 있습니다.

 

Hybrid 해시 조인

기본적인 Grace방식을 사용한다면 디스크 I/O가 상당히 심할 것입니다. 따라서 변형된 알고리즘이 사용됩니다.

 

Recursive 해시 조인(Nested-loops 해시조인)

 

비트- 백터 필터링

조인 성공 가능성이 없는 파티션 레코드는 아예 디스크에 기록되지 않게 하는 것입니다.

 

(5) Build input 해시 키 값에 중복이 많을 때 발생하는 비효율

해시 알고리즘의 성능은 충돌을 얼마나 최소화할 수 있느냐에 달렸으며 이를 방지하려면 그만큼 많은 해시 버킷을 할당해야합니다. 오라클은 가능하면 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력합니다.

그럼에도 불구하고 키 컬럼에 중복값이 많다면 하나의 버킷에 많은엔트리가 달릴 수 밖에 없고 그렇게 되면 해시 버킷을 스캔하는 단계에서 많은 시간을 허비하기 때문에 탐색 속도가 현저히 저하됩니다.

 

(6) 해시 조인 사용기준

해시 조인 성능을 좌우하는 두 가지 키 포인트는 다음과 같습니다.

- 한 쪽 테이블이 Hash Area에 담길 정도로 충분히 작아야 함

- Build Input 해시 키 컬럼에 중복 값이 거의 없어야 함

위 두가지 조건을 만족할 때 해시 조인이 가장 극적인 성능 효과를 낼 수있습니다.

선택기준으로는

조인컬럼에 적당한 인덱스가 없어 NL 조인이 비효율적일 때,

조인 컬럼에 인덱스가 있지만 NL 조인 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때

소트 머지 조인하기에는 두 테이블이 너무 커 소트 부하가 심할 때

수행빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인할 때