3. 해시 조인 (by kdw1763) [2017.04.14]
02 조인의 원리와 활용
03. 해쉬 조인
h5.(1)기본 메커니즘
- 7.3 버전에서 처음소개, 소트 머지 조인과 NL 조인이 효과적이지 못한 상황에 대한 대안으로 개발
- 둘 중 작은 집합(Build Input,Driving TaBle)를 읽어 Hash Area에 해시 테이블을 생성하고, 반대쪽 큰 집합(Probe Input)를 읽어 조인하는 방식
- NL조인처럼 조인 과정에서 발생하는 Ramdom 액세스 부하가 없다.(단, 양쪽집합을 읽는 과장에서 인덱스를 이용한다면 Random 엑세스 발생)
- 소트 머지 조인 처럼 조인 전에 미리 양쪽 집할을 정렬하는 부담도 없다.
- NL조인과 달리 래치획등 과정없이 PGA에서 빠르게 데이터를 탐
- 가장 비용이 많이 들어가는 조인방법으로 Driving Table이 작을 때 효과적이다.
- 드라이빙 조건과 상관없이 좋은 성능을 발휘할 수 있는 조인 방법이며 대체로 제일 빠르다.
h5.(2)힌트를 이용한 조인 순서 및 Build Input 조정
select /*+ use_hash(d e) */
d.deptno, d.dname, e.empno, e.ename
from dept d, emp e
where d.deptno = e.deptno
---------------------------------------------------------------------------
| 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을 옵티마이저가 선택했다. dept가 선택된 이유는 통계정보상 더 작은 테이블이기 때문이다.
select /*+ use_hash(d e) swap_join_inputs(e) */
d.deptno, d.dname, e.empno, e.ename
from dept d, emp e
where d.deptno = e.deptno
select /*+ leading(e) use_hash(d) */
d.deptno, d.dname, e.empno, e.ename
from dept d, emp e
where d.deptno = e.deptno
---------------------------------------------------------------------------
| 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| EMP | 14 | 182 | 3 (0)| 00:00:01 |
| 3 | TABLE ACCESS FULL| DEPT | 4 | 52 | 3 (0)| 00:00:01 |
---------------------------------------------------------------------------
Driving Table을 직접 선택할 때 : swap_join_inputs
2개이상 테이블을 해시 조인 할때는 ordered, leading 힌트를 사용함.
h5.(3)두 가지 해시 조인 알고리즘
select /*+ leading(r, c, l, d, e)
use_hash(c) use_hash(l) use_hash(d) use_hash(e) */
e.first_name, e.last_name, d.department_name
, l.street_address, l.city, c.country_name, r.region_name
from regions r
, countries c
, locations l
, departments d
, employees e
where d.department_id = e.department_id
and l.location_id = d.location_id
and c.country_id = l.country_id
and r.region_id = c.region_id;
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 106 | 10706 | 15 (14)| 00:00:01 |
| 1 | HASH JOIN | | 106 | 10706 | 15 (14)| 00:00:01 |
| 2 | HASH JOIN | | 27 | 2241 | 12 (17)| 00:00:01 |
| 3 | HASH JOIN | | 23 | 1472 | 8 (13)| 00:00:01 |
| 4 | HASH JOIN | | 25 | 700 | 5 (20)| 00:00:01 |
| 5 | TABLE ACCESS FULL| REGIONS | 4 | 56 | 3 (0)| 00:00:01 |
| 6 | INDEX FULL SCAN | COUNTRY_C_ID_PK | 25 | 350 | 1 (0)| 00:00:01 |
| 7 | TABLE ACCESS FULL | LOCATIONS | 23 | 828 | 3 (0)| 00:00:01 |
| 8 | TABLE ACCESS FULL | DEPARTMENTS | 27 | 513 | 3 (0)| 00:00:01 |
| 9 | TABLE ACCESS FULL | EMPLOYEES | 107 | 1926 | 3 (0)| 00:00:01 |
-----------------------------------------------------------------------------------------
1. id 4번 해시 조인 : regionsj를 해시 테이블로 빌드(Build)하고， countries 읽어 해시 테이블을 탐색(Probe)하면서 조인 수행
2. id 3번 해시 조인 : regions와 countries 조인 결과를 해시 테이블로 빌드하고， locations를 읽어 해시 테이블을 탐색하면서 조인수행
3. id 2번 해시 조인 : regions & countries & locations 조인 결과를 해시 테이블로 빌드하고, departments를 읽어 해시 테이블을 탐색하면서 조인 수행
4. id 1번 해시 조인 : regions & countries & locations & departments 조인 결과를 해시테이블로 빌드하고, employees를 읽어 해시 테이블을 탐색하면서 조인 수행
ordered 나 leading 힌트는 조인 순서를 결정하기 위한 것이지 해시 조인의 Build Input을 결정하기 위한 것은 아니어서 위 실행계획을 보면 Build Input이 옵티마이저에 의해 자유롭게 결정
select /*+ leading(r, c, l, d, e)
use_hash(c) use_hash(l) use_hash(d) use_hash(e)
swap_join_inputs(l)
swap_join_inputs(d)
swap_join_inputs(e) */
e.first_name, e.last_name, d.department_name
, l.street_address, l.city, c.country_name, r.region_name
from regions r
, countries c
, locations l
, departments d
, employees e
where d.department_id = e.department_id
and l.location_id = d.location_id
and c.country_id = l.country_id
and r.region_id = c.region_id;
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 106 | 10706 | 15 (14)| 00:00:01 |
| 1 | HASH JOIN | | 106 | 10706 | 15 (14)| 00:00:01 |
| 2 | TABLE ACCESS FULL | EMPLOYEES | 107 | 1926 | 3 (0)| 00:00:01 |
| 3 | HASH JOIN | | 27 | 2241 | 12 (17)| 00:00:01 |
| 4 | TABLE ACCESS FULL | DEPARTMENTS | 27 | 513 | 3 (0)| 00:00:01 |
| 5 | HASH JOIN | | 23 | 1472 | 8 (13)| 00:00:01 |
| 6 | TABLE ACCESS FULL | LOCATIONS | 23 | 828 | 3 (0)| 00:00:01 |
| 7 | HASH JOIN | | 25 | 700 | 5 (20)| 00:00:01 |
| 8 | TABLE ACCESS FULL| REGIONS | 4 | 56 | 3 (0)| 00:00:01 |
| 9 | INDEX FULL SCAN | COUNTRY_C_ID_PK | 25 | 350 | 1 (0)| 00:00:01 |
-----------------------------------------------------------------------------------------
위 실행계획도 네 번의 조인 과정을 거치지만 앞에서와는 사뭇 다른 방식으로 처리되며， NL 조인처럼 순차적으로 진행하는 것이 특징이다.
1. 해시 테이블 생성 : employees, departments, locations, regions 4개 테이블에 대한 해시테이블을 먼저 생성한다.
2. id 7번 해시 조인 : countries에서 한 건을 읽어 regions 해시 테이블을 탐색한다.
3. id 5번 해시 조인 :2번에서 조인에 성공한 레코드는 locations 해시 테이블을 탐색한다.
4. id 3번 해시 조인 :3번에서 조인에 성공한 례코드는 departments 해시 테이블을 탐색한다.
5. id 1번 해시 조인 :4번에서 조인에 성공한 레코드는 employees 해시 테이블을 탐색한다
6. 2~5 번 과정을 countries 테이블(여기서는 인텍스)을 모두 스캔할 때까지 반복한다.
select /*+ leading(d, e, l, c,r)
use_hash(e) use_hash(l) use_hash(c) use_hash(r)
swap_join_inputs(l)
swap_join_inputs(c)
swap_join_inputs(r) */
e.first_name, e.last_name, d.department_name
, l.street_address, l.city, c.country_name, r.region_name
from regions r
, countries c
, locations l
, departments d
, employees e
where d.department_id = e.department_id
and l.location_id = d.location_id
and c.country_id = l.country_id
and r.region_id = c.region_id
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 106 | 10706 | 15 (14)| 00:00:01 |
| 1 | HASH JOIN | | 106 | 10706 | 15 (14)| 00:00:01 |
| 2 | TABLE ACCESS FULL | REGIONS | 4 | 56 | 3 (0)| 00:00:01 |
| 3 | HASH JOIN | | 106 | 9222 | 12 (17)| 00:00:01 |
| 4 | INDEX FULL SCAN | COUNTRY_C_ID_PK | 25 | 350 | 1 (0)| 00:00:01 |
| 5 | HASH JOIN | | 106 | 7738 | 10 (10)| 00:00:01 |
| 6 | TABLE ACCESS FULL | LOCATIONS | 23 | 828 | 3 (0)| 00:00:01 |
| 7 | HASH JOIN | | 106 | 3922 | 7 (15)| 00:00:01 |
| 8 | TABLE ACCESS FULL| DEPARTMENTS | 27 | 513 | 3 (0)| 00:00:01 |
| 9 | TABLE ACCESS FULL| EMPLOYEES | 107 | 1926 | 3 (0)| 00:00:01 |
--------------------------------------------------------------------수---------------------
h5.(4)Build Input Hash Area를 초과할 때 처리 방식
해시 조인은 해시 테이블을 Hash Area에 담을 수 있을 정도로 Build Input이 충분히 작을때 효과적, In-Memory 해시 조인이 불가능 할때 처리 방법
h6.Grace 해시 조인
1)파티션 단계
조인되는 양쪽 집합 모두 조인컬럼에 해시 함수를 적용, 동적 파티셔닝을 실시
독립적으로 처리할 수 있는 여러 개의 작은 서브 집합으로 분할함으로써 파티션 짝(pair)을 생성
2)조인 단계
파티션 단계가 완료되면 각 파티션 짝(pair)에 대 해 하나씩 조인을 수행
해시 테이블이 생성되면 나면 반대쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색하며, 모든 파티션 짝에 대한 처리가 완료될때까지 반복한다.
분할&정복(Divide & Conquer) 방식
h6.Hybrid 해시 조인
Grace 해시 조인은 디스크 I/O 부하가 상당히 심하다. 단점을 보안하기 위해 사용
1.두 테이블 중 작은 쪽을 Build Input으로 선택하고 Hash Area에 해시 테이블을 생성
두 개의 해시 함수를 적용하는데， 첫 번째 해시 값으로는 레코드를 저장할 파티션을 결정하고, 두 번째 해시 값은 나중에 실제 조인할 때를 위해 레코드와 함께 저장
2.해시 테이블을 생성하는 도중에 Hash Area가 꽉 차면 그 중 가장 큰 파티션(=버킷)을 디스크에 기록
3.해시 테이블을 완성하기 위해 Build Input을 계속 읽는 동안 이미 디스크에 기록된 파티션에 해당되는 레코드는 디스크 파티션에 기록
4.다시 Hash Area가 다 차면 이번에도 가장 큰 파티션을 디스크에 기록
5.파티션 크기가작은순으로 메모리를 채움
6.두번째 테이블 타피션이 현재 메모리에 있다면 그 파티션을 스캔하고 거기서 레코드 찾으면 즉시 결과 집합에 포함, 선택되지 않은 레코드는 버림
7.메모리에 매칭되는 파티션 찾지 못하면 해시 파티셔닝 함.
8.양쪽 테이블을 모두 같은 해시 함수로 파티셔닝 했기 때문에 같은 값을 갖는 레코드들끼리는 같은 파티션 짝에 놓이게 되었다.
9.모든 파티션에 대해 1번 ~ 8번 과정을 반복한다.
h5.Recursive 해시 조인(=Nested-Ioops 해시 조인)
디스크에 기록된 파티션 짝(Pair)끼리 조인을 수행하려고 '작은 파티션' 을 메모리에 로드하는 과정에서 또다시 가용 Hash Area를 초과히는 경우가 발생할 수 있다 그럴 때는 추가적인 파티셔닝 단계를거치게 되는데 이를 'Recursive 해시 조인'이라고한다.
h5.비트-벡터 필터링
Hybrid 조인 5 ~6번 단계를 거치는 동안 가능한 메모리 상에서 조인을 완료하므로 두 번째 테이블이 디스크에 기록되는 양을 상당히 줄일 수 있다
조인가능성이 없는 파티션 레코드는 아예 디스크에 기록하지 않는다.
h5.(5)Build Input 해시 키 값에 중복이 많을 대 발생하는 비효율
Build Input의 해시 카 컬럼에는 중복 값이 (거의) 없어야 해시 조인이 빠르게 수행펼 수 있음을 이해
h5.(6)해시 조인 사용기준
- 한쪽 테이블이 Hash Area에 담길 정도로 충분히 작아야함
- Build Input 해시 키 컬럼에 중복 값이 거의 없어야함
- 조인 컬럼에 인덱스가 없어 NL조인이 비효율적일때
- 인덱스가 있더라도 NL조인 드라이빙 집합에서 INNER쪽 집합으로의 조인 액세스량이 많아 Random액세스 부하가 심할때
- 소트 머지 조인하기에는 두 테이블이 너무 커 소트 부하가 심할때
- 수행빈도가 낮고 쿼리수행시간이 오래 걸리는 대용량 테이블을 조인할때