by-nc-sa     개발자, DBA가 함께 만들어가는 구루비 지식창고!

3. 해시 조인




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와 메모리 사욜률을 크게 증가시키고, 래치 경합이 발생하여 시스템 동시성을 떨어뜨림
  • 그러므로 수행빈도가 낮고, 쿼리수행시간이 오래걸리는, 대용량 테이블을 조인할때 주로 사용해야한다.

문서정보

Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.