3. 해시 조인

조회 수 5284 추천 수 0 2011.03.22 19:44:25
휘휘 *.38.213.10


(1) 기본 메커니즘


  • 배경
    • 7.3 버전 최초 소개, 소트머지 조인과 NL조인이 효과적이지 못해서 개발
  • 원리
    • 둘중 작은 집합(Build Input)을 읽어 Hash Area에 해시 테이블을 생성하고 , 큰집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 조인


  • 해시테이블생성
    • 해시 함수를 통해 생성
    • 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인에 엔트리를 연결


  • 해시테이블탐색
    • 해시 함수 사용
    • 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾음


  • 장점
    • NL조인처럼 조인과정에서 Random 액세스 부하가 없음
      (양쪽집합을 읽는 과정에서 인덱스를 사용하면 발생)
    • 소트 머지조인처럼 조인전에 양쪽 집합을 미리 정렬할 필요가 없음
  • 단점
    • 해시 테이블을 생성하는 비용이 수반 (Build Input가 작을때 효과적)
    • PGA 메모리에서 할당되는 Hash Area(hash_area_size참조) 에 담길 정도로 충분히 작아야함
      ( In-Memory 해시 조인)
    • Build Input이 Hash Area 크기를 초과하면 디스크에 썼다가 다시 읽는 과정을 거치게됨
    • 해시  키 값으로 사용되는 컬럼에 중복값이 거의 없어야 함




-- 해시 조인
create cluster h# ( bucket number ) hashkeys 16
hash is mod(bucket, 16);

create table dept_hashtable (bucket number, deptno number(2), dname varchar2(14) )
cluster h# (bucket);

insert into dept_hashtable
select mod(deptno, 16) bucket, deptno, dname from dept;

declare
 l_bucket number;
begin
 for outer in (select deptno, empno, rpad(ename, 10) ename from emp)  
 loop    -- outer 루프
    l_bucket := mod(outer.deptno, 16);
    for inner in (select deptno, dname from dept_hashtable
                 where  bucket = l_bucket
                 and    deptno = outer.deptno)
    loop  -- inner 루프
     dbms_output.put_line(outer.empno||' : '||outer.ename||' : '||inner.dname);
    end loop;
 end loop;
end;
/



  • Inner 루프가 Hash Area에 미리 생성해 둔 해시 테이블을 이용
  • 해시 테이블 생성단계에서는 전체 범위처리가 불가능하지만
    Probe Input을 스캔하는 단계는 NL 조인처럼 부분 범위처리가 가능
  • 해시테이블이 PGA영역에 할당되어 NL조인보다 빠름
  • 해시 조인은 래치 획득 과정 없이 PGA 에서 빠르게 데이터를 탐색


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




SQL> select /*+ use_hash (d e) */ d.deptno, d.dname, e.empno, e.ename
 2  from dept d, emp e
 3  where d.deptno=e.deptno;

    DEPTNO DNAME               EMPNO ENAME
---------- -------------- ---------- ----------
       20 RESEARCH             7369 SMITH
       30 SALES                7499 ALLEN
…........

14 rows selected.


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

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




  • Build Input
    • HASH JOIN  자식 노드중 위쪽( dept)
  • Probe Input
    • HASH JOIN  자식 노드중  아래쪽 (EMP)
  • use_hash
    • 통계정보상 더 작은 table인 dept를 옵티마이저가 Build Input로 선택
  • Build Input 를 직접선택할경우
    • use_hash (d e) swap_join_inputs(e)
    • leading(d) use_hash(e)  (2 개의 테이블만 해시 조인할경우)


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


첫번째 알고리즘



SQL> select /*+ leading(r,c,l,d,e)
 2      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  3    4    5    6    7    8    9   10   11   12   13


106 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 3371449005

-----------------------------------------------------------------------------------------
| 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 |
-----------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

  1 - access("D"."DEPARTMENT_ID"="E"."DEPARTMENT_ID")
  2 - access("L"."LOCATION_ID"="D"."LOCATION_ID")
  3 - access("C"."COUNTRY_ID"="L"."COUNTRY_ID")
  4 - access("R"."REGION_ID"="C"."REGION_ID")






/*+ leading(r,c,l,d,e) use_hash(c) use_hash(l) use_hash(d) use_hash(e) */

  • “regions를 기준으로c->l->d->e (countries -> locations -> departments -> employees ) 순으로 조인하면서
    각각 해시 조인으로 처리”


  • 조인과정
1. id 4
regions 를 해시 테이블로 빌드(Build)하고 countries를 읽어 해시 테이블을 탐색(Probe) 하면서 조인 수행
2. id 3
1의 결과를 해시테이블로 빌드하고, locations를 읽어 해시 테이블을 탐색하면서 조인수행
3. id 2
2의 결과를 해시테이블로 빌드하고, departments를 읽어 해시 테이블을 탐색하면서 조인
4. id 1
3의 결과를 해시테이블로 빌드하고 , employees를 읽어 해시 테이블로 탐색하면서 조인



  • ordered 나 leading 힌트는 조인순서를 결정하며 처음 조인되는 두집합 (r,c) 간에 build input을 정하는데
    영향을 미치며 (2 ~ 4) 번에 대한 build input을 직접 조정하려면 swap_join_inputs 힌트를 사용



두번째 알고리즘



SQL> select /*+ leading(r,c,l,d,e)
 2  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
 3    4    5    6    7    8  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;  9   10   11   12   13   14   15   16

106 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 1516572578

-----------------------------------------------------------------------------------------
| 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 |
-----------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

  1 - access("D"."DEPARTMENT_ID"="E"."DEPARTMENT_ID")
  3 - access("L"."LOCATION_ID"="D"."LOCATION_ID")
  5 - access("C"."COUNTRY_ID"="L"."COUNTRY_ID")
  7 - access("R"."REGION_ID"="C"."REGION_ID")

SQL>




1.해시 테이블 생성
employees, departments, locations, regions 테이블에대한 해시테이블 생성
2. id 7
countries에서 한건을 읽어 regions 해시 테이블을 탐색
3. id 5
2번에서 조인에 성공한 레코드로 locations해시 테이블 탐색
4. id 3
3번에서 조인에 성공한 레코드는 departments 해시 테이블을 탐색
5. id 1
4번에서 조인에 성공한 레코드는 employees 해시 테이블을 탐색

6.

2 ~ 5 번 과정을 countries 테이블을 모두 스캔할때까지 반복



  • 가장 큰 employees 테이블을 해시 테이블로 생성 하였으므로 첫 실행계획보다 비효율적




select /*+ leading(r,c,l,d,e)
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; 

106 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 2981629735

-------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name             | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                  |   106 | 10706 |    13  (16)| 00:00:01 |
|*  1 |  HASH JOIN                   |                  |   106 | 10706 |    13  (16)| 00:00:01 |
|   2 |   TABLE ACCESS BY INDEX ROWID| DEPARTMENTS      |     1 |    19 |     1   (0)| 00:00:01 |
|   3 |    NESTED LOOPS              |                  |    27 |  2241 |     9  (12)| 00:00:01 |
|*  4 |     HASH JOIN                |                  |    23 |  1472 |     8  (13)| 00:00:01 |
|   5 |      TABLE ACCESS FULL       | LOCATIONS        |    23 |   828 |     3   (0)| 00:00:01 |
|*  6 |      HASH JOIN               |                  |    25 |   700 |     5  (20)| 00:00:01 |
|   7 |       INDEX FULL SCAN        | COUNTRY_C_ID_PK  |    25 |   350 |     1   (0)| 00:00:01 |
|   8 |       TABLE ACCESS FULL      | REGIONS          |     4 |    56 |     3   (0)| 00:00:01 |
|*  9 |     INDEX RANGE SCAN         | DEPT_LOCATION_IX |     4 |       |     0   (0)| 00:00:01 |
|  10 |   TABLE ACCESS FULL          | EMPLOYEES        |   107 |  1926 |     3   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

  1 - access("D"."DEPARTMENT_ID"="E"."DEPARTMENT_ID")
  4 - access("C"."COUNTRY_ID"="L"."COUNTRY_ID")
  6 - access("R"."REGION_ID"="C"."REGION_ID")
  9 - access("L"."LOCATION_ID"="D"."LOCATION_ID")




  • departments 를 기준으로 employees-> locations -> countries -> regions 순으로 조인
    employees를 Probe Input으로 삼고 나머지는 Build Input이 되도록 실행계획을 조정


  • 오라클의 sample hr의 employees가 최하위 자식 엔틴티로서 가장 큼고 나머지들은 작은 코드성 테이블이므로
  • 위와 같은 알고리즘으로 수행되면 작은 테이블로 빠르게 해시 테이블을 생성하고 큰테이블에서 일부 레코드만
    스캔하다가 멈추는 부분범위처리의 장점을 가질수 있음



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


  • In-Memory 해시 조인이 불가능 할때 처리방법


Grace 해시 조인


1) 파티션 단계
  • 조인 되는 양쪽 집합모두 조인 컬럼에 해시 함수를 적용
  • 변환된 해시 값에 따라 동적으로파티셔닝을 실시
  • (독립적으로 처리할수 있는 여러개의 작은 서브 집합으로 분할함으로 파티션 짝을 생성)
    양쪽 집합을모두 읽어 디스크상의 Temp 공간에 일단저장하므로 In-Memory보다 성능이 떨어짐)

2) 조인 단계
  • 파 티션 단계 완료후 각 파티션 짝에 대해 하나씩 조인을 수행
    ( Build Input, Probe Input은 독립적으로 결정- 파티션 전 작은 테이블 순이아니라
    파티션 짝별로 작은 파티션을 Build Input으로 선택하여 해시 테이블을 생성)
  • 해시 테이블 생성후 반대쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색
    (모든 파티션 짝에 대한 처리가 완료될때까지 과정 반복)
  • 분학, 정복 (Divide & Conquer) 방식


Hybrid 해시 조인
    • Grace 해시 조인의 I/O 부하에 대한 단점을 보완하기 위한 변형된 최적화 알고리즘

오라클

1.

두 테이블중 작은 쪽을 Build Input으로 선택하고 Hash Area에 해시 테이블을 생성
이때 두개의 해시 함수 적용
첫번째 해시 값으로는 레코드를 저장할 파티션(=버킷)을 결정
두번째 해시 값은 나중(8번 단계)에 실제 조인할때를 위해 레코드와 함께 저장

2.

해시 테이블생성중에 Hash Area가 꽉 차면 그중 가장 큰 파티션(=버킷)을 디스크에 기록

3.

해시 테이블 완성을 위해 Build Input을 계속 읽는 동안 이미 디스크에 기록된 파티션에 해당되는 레코드는 디스크 파티션에 기록

4.

다시 Hash Area가 다 차면 가장 큰 파티션을 디스크에 기록

5.

첫번째 테이블에 대한 파티셔닝 단계가 끝나면 파티션 크기가 작은 순으로 메모리를 채움

6.

두번째 테이블을 읽기 시작
이때 두개의 해시 함수 사용
첫번째 해시 값에 해당하는 파티션이 현재 메모리에 있다면 그 파티션을 스캔(비트-벡터 필터링을 거쳐 선택된 레코드만 파티션 스캔) 하고 조인레코드를 찾으면 결과 집합에 포함,선택되지 않은 레코드는 버림

7.

비트-벡터 필터링을 통과했지만 메모리에서 매칭되는 파티션을 찾이 못하면 Build Input을 파티셔닝할때 와 같은 방식으로 해시 파티셔닝 진행
첫번째 해시값으로 레코드가 저장될 파티션을 결정
두번째 해시값과 함께 디스크로 저장, ( 6번 단계에서 비트-벡터 팔터링을 거진 레코드만 디스크에 기록)

8.

7번을 거치면 양쪽모두 같은 해시 함수로 파티셔닝했기 때문에 같은 해시값을 갑는 레코드끼리 같은 파티션 짝에 놓임
각 파티션 짝은 작은 쪽 파티션을 Build Input로 선택해 해시 테이블을 생성
1,7번 단계에서 저장해둔 두번째 해시 값이 이용

9.

모든 파티션에 대해 8번 과정을 반복하여 해시 조인을 마침





Recurisive 해시 조인 (= Nested-loops 해시 조인)

  • 디스크에 기록된 파티션 짝끼리 조인을 수행하려고 ‘작은 파티션을 메모리에 로드하는 과정에
    또 다시 가용 Hash Area를 초과 하는 경우가 발생할수 있으며 이때 추가적인 파티셔닝 단계를 거치게 되는 경우
  • Multipass 해시 조인 이라고도함
  • Onepass해시 조인
    • 디스크 쓰기가 발생했지만 Multipass 오프레이션을 거치지 않을경우는 이라고 한다
  • Optimal 해시 조인
    • 디스크를 전혀 사용하지않는 In-Memory 해시조인


비트-벡터 필터링
  • 조인 성공가능성이 없는 파티션 레코드는 아예 디스크에 기록되지 않게 함
  • 원리
  • Build Input 을 읽어 해시 테이블을 생성할 때 두개의 해시 함수를 사용하며 이때
    특정레코드가 저장될 해시 버킷이 결정되면 상응하는 비트벡터도 1로 설정하면서 파티셔닝을 완료
  • 두번째 테이블 역시 동일 과정을거쳐 동일 비트벡터에 1로 채크하면서 이미 값이 1로 채크된경우는
    저장하고 0일경우는 디스크에 기록하지 않음




         f(m)
f(n)

B0(=A)

B1(=B)

B2(=C)

B3(=D)

B4(=E)

B0(=1)


v



v

B1(=2)



v


v

B2(=3)

v

v


v




Build Input이 특정레코드가 f(m) 해시 함수로 부터 ‘C’, f(n)함수로부터 ‘2’를 리턴하므로
비트-벡터 2행 3열 에 1(positive)로 설정하는식으로 해시 테이블을 생성하면서 완료하고
두번째 테이블을 디스크로 파티셔닝 하면서 같은 방법으로 값을 구해 비트-벡터 테이블에 저장되어있는 값이 1일경우 조인 확률이 높으므로 저장하고 0이라면 기록하지 않는다.







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

  • 해시 알고리즠의 성능은 해시 충돌을 얼마나 최소화 할수 있느냐에 달려있으므로
  • 오라클은 최대한 많은 해시 버킷을 할당하려고 노력한다.
  • 테이블에 저장할 키 컬럼이 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달릴수 밖에 없고 속도 또한 저하된다.
  • 그러므로 쿼리 작상시 레코드를 유일하게 식별할수 있는 키값을 사용하도록 작성하는것이 중요하다.

  • 교제의 예는 상품번호,주문일자 를 사용하여 조인을 수행하였으나 주문 체결과정의 자료를 보면
  • 특정상품의 하루 체결일자는 수천건에 이러게 되어 해시 버킷 하나에 수천개의 체인을 이루게되어 수행속도가
  • 느려지게 되지만 동일 테이블을 union all을 사용하거나 connect by, 복제를 위한 임시테이블 등을 사용하여
  • 유니크한 조건을 사용할수 있도록 해주는 것이 중요하다.




(6) 해시 조인 사용기준

  • 성능을 좌우하는 두가지 키 포인트
    • 한쪽 테이블이 Hash Area에 담길 정도로 작아야 함
    • Build Input해시 키 컬럼에 중복 값이 거의 없어야함
  • 효과적인 선택 기준
    • 조인 컬럼에 적당한 인덱스가 없어 NL 조인이 비효율적일때
    • 조인 컬럼에 인덱스가 있떠라도 NL조인 드라이빙 집합에서 Inner쪽 집합으로의
      조인 액스량이 많아 Random 액셋 부하가 심할때
    • 소트 머지 조인하기에 두테이블이 너무 커 소트 부하가 심할때
    • 수행 빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블 조인




  • 오라클 고도화 원리와 해법 2 (bysql.net 2011년 1차 스터디)
  • 작성자: 남송휘 (tofriend)
  • 최초작성일: 2011년 3월 20일
  • 본문서는 bysql.net 스터디 결과입니다 .본 문서를 인용하실때는 출처를 밝혀주세요. http://www.bysql.net
  • 문서의 잘못된 점이나 질문사항은 본문서에 댓글로 남겨주세요. ^^