3. 해시 조인 (by iamheeya97) [2010.04.03]
03 해시조인
(1) 기본 메커니즘
- 해시조인은 소트머지조인과 NL조인의 효과적이지 못한 상황에 대한 대안으로서 개발됨
- 둘 중 작은 집합을 읽어 Hash Area에 해시 테이블을 생성하고, 반대쪽 큰 집합을 읽어 해시 테이블을 탐색하면서 조인하는 방식
- 해시테이블을 생성할 때 해시함수를 사용하고, 해시함수에서 리턴받은 버킷주소로 찾아가 해시체인에 엔트리 연결
- 해시테이블을 탐색할 때도 해시함수를 사용, 해시함수에서 리턴받은 버킷주소로 찾아가 해시체인을 스캔하면서 데이터를 찾음
- NL조인처럼 조인시 발생하는 Random엑세스 부하가 없고, 소트머지 조인처럼 정렬부하도 없다. 단 해시테이블을 생성하는 비용이 수반
- 그러므로 Build Input이 작을 때 효과적(PGA에 Hash Area에 담을 수 있는 충분히 작아야 함)
- 해시 키 값으로 사용되는 컬럼에 중복값이 거의 없을 때라야 효과적
- Inner 루프가 Hash Area에 생성해둔 해시테이블을 이용한다는 것 외에 NL조인과 유사
- 해시테이블 만들때는 전체범위처리가 불가피하나, Prob Input을 스캔하는 단계는 부분범위 처리가능
- 해시조인도 PGA를 이용하므로 래치 획득과정없이 빠르게 데이터를 탐색
(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
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------
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 | => Build Input
| 3 | TABLE ACCESS FULL| EMP | 14 | 182 | 3 (0)| 00:00:01 | => Probe Input
---------------------------------------------------------------------------
- 위쪽이 Build Input, 아래쪽이 Probe Input
- Build Input을 직접선택하고자 할때는 swap_join_inputs힌트를 사용하거나, 2개 테이블을 해시조인시는 ordered나 leading을 사용해도됨
(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 hr.regions r
, hr.countries c
, hr.locations l
, hr.departments d
, hr.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 |
----------------------------------------------------------------------------------------
두 번째 알고리즘
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 hr.regions r
, hr.countries c
, hr.locations l
, hr.departments d
, hr.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 |
-----------------------------------------------------------------------------------------
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 hr.regions r
, hr.countries c
, hr.locations l
, hr.departments d
, hr.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 |
-----------------------------------------------------------------------------------------
(4) Build Input이 Hash Area를 초과할 때 처리방식
Grace 해시조인
- In-Memory 해시조인이 불가능할때 오라클은 'Grace 해시조인'이라고 알려진 조인알고리즘을 사용하는데 두단계로 나누어 진행된다
- 파티션단계
조인되는 양쪽 집합모두 조인 컬럼에 해시함수를 저?하고, 반환된 해시값에 따라 동적으로 파티셔닝한다. - 조인단계
파티션 단계가 완료되면 각 파티션 짝에 대해 하나씩 조인을 수행한다. 파티션하기 전 어느쪽이 작은 테이블이었는지에 상관없이 각 파티션 짝별로 작은쪽이 Build Input으로 선택해서 해시테이블을 생성한다.
해시테이블이 생성되고나면 반대쪽 파티션로우를 하나씩읽으면서 해시테이블을 탐색. 모든 파티션 짝에 대한 처리가 완료될때까지 반복
- 파티션단계
Hybrid 해시조인
- 기본적인 Grace 해시조인은 디스크 I/O부하가 상당히 심할 것이다. 조인에 성공할 가능성없는 집합까지 일단 디스크에 쓰고, 나중에 디스크로부터 읽어야하기 때문이다, 이를 보완하기 위한 방법중 하나가 Hybrid 해시조인이다.
- 방법
책보자
Recursive 해시조인(Nested-loops 해시조인)
책보자
비트-벡터 필터링
책보자
(5) Build Input 해시키값에 중복이 많을 때 발생하는 비효율
- 해시 알고리즘의 성능은 해시 충돌을 얼마나 최소화할 수있느냐에 달렸음
- 가능하면 오라클은 충분히 많은 개수의 버킷을 할당하여 버킷 하나당 하나의 기값만 갖게 하려고 노력함.
- 해시버킷을 아무리 빨리찾아도 버킷에 많은 엔트리가 달리면 버킷을 스캔하는 단계에서 많은 시간을 허비하므로,Build Input의 해시 키 컬럼에는 중복값이 거의 없어야 해시조인이 빠르게 수행될수 있음
- 해시키는 '='조인 컬럼만으로 결정되므로 상품번호+체결일자가 해시키 임
- 특정 상품의 하루 체결건수는 평균 수천건에 이르므로 많은 비용이 소요
- 주문접수가 해시 키 값으로 사용되도록 하여 비용절감
- 복제테이블을 이용해 주문체결 데이터를 복제하는 방법을 쓸수 있음
(6) 해시조인사용기준
- 성능을 좌우하는 요소
- 한쪽테이블이 Hash Area에 담길 정도로 충분히 작아야 함
- Build Input 해시키 컬럼에 중복값이 거의 없어야 함
- 언제 사용하면 효과적인가?
- 조인 컬럼에 적당한 인덱스가 없어 NL조인이 비효율적일때
- 조인 컬럼에 인덱스가 있더라도 NL조인 드라이빙 집?에서 Inner로 조인액세스량이 많아 Random 액세스 부하가 심할때
- 소트머지조인하기에는 두테이블의 소트부하가 심할대
- 수행빈도가 낮고 쿼리수행이 오래걸리는 대용량 테이블을 조인할때
- 해시테이블은 단 하나의 쿼리를 위해 생성하고 조인이 끝나면 바로 소멸하는 자료구조이므로, 수행빈도가 높은 쿼리애서 사용하면 CPU와 메모리 사욜률을 크게 증가시키고, 래치 경합이 발생하여 시스템 동시성을 떨어뜨림
- 그러므로 수행빈도가 낮고, 쿼리수행시간이 오래걸리는, 대용량 테이블을 조인할때 주로 사용해야한다.