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

3. 해시 조인




* 해시조인

메커니즘
1. 소트머지조인도, NL조인도 안 통할 때를 위해 7.3 버전에 나타남
  * 소트머지조인의 정렬 부담 없다
  * NL조인의 Random 액세스 부담 없다
  * 대신, 해시 테이블 생성 부담 있다
2. 메커니즘
  A. 작은 집합(Build Input)을 읽어
  B. Hash Area 에 해시 테이블을 생성하고
  C. 반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색 하면서 조인
3. 해시함수
  * 해시 테이블 생성 (Build)
  * 해시 테이블 탐색 (Probe)
4. 해시 테이블 ( = 해시 맵)
  * 생성 비용이 있으므로, 해시 테이블을 생성하는 Build Input 이 작아야 효과적
    * PGA (래치 획득 없음) 의 Hash Area(hash_area_size)에 담길 정도 (In-memory 해시 조인)
  * Build Input 의 해시 키 값 컬럼에 중복이 거의 없어야 효과적
5. Probe Input 처리 단계에서 부분범위처리 가능
그림
데모 (PL/SQL) 데모 (전화번호부)
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 scott.dept;

commit;

declare
  l_bucket number;
begin
  for outer in (select deptno, empno, rpad(ename, 10) ename from scott.emp)
  loop -- outer loop
    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 loop
      dbms_output.put_line(outer.empno||' : '||outer.ename||' : '||inner.dname);
    end loop;
  end loop;
end;
/

-- 결과
7369 : SMITH      : RESEARCH
7499 : ALLEN      : SALES
7521 : WARD       : SALES
7566 : JONES      : RESEARCH
7654 : MARTIN     : SALES
7698 : BLAKE      : SALES
7782 : CLARK      : ACCOUNTING
7788 : SCOTT      : RESEARCH
7839 : KING       : ACCOUNTING
7844 : TURNER     : SALES
7876 : ADAMS      : RESEARCH
7900 : JAMES      : SALES
7902 : FORD       : RESEARCH
7934 : MILLER     : ACCOUNTING

* 힌트를 이용한 조인 순서 및 Build Input 조정

use_hash
select /*+ gather_plan_statistics use_hash(d e) */ d.deptno, d.dname, e.empno, e.ename
  from scott.dept d, scott.emp e
 where d.deptno = e.deptno;

----------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |     14 |00:00:00.01 |      15 |       |       |          |
|*  1 |  HASH JOIN         |      |      1 |     11 |     14 |00:00:00.01 |      15 |  1134K|  1134K|  653K (0)|
|   2 |   TABLE ACCESS FULL| DEPT |      1 |      4 |      4 |00:00:00.01 |       7 |       |       |          |
|   3 |   TABLE ACCESS FULL| EMP  |      1 |     14 |     14 |00:00:00.01 |       8 |       |       |          |
----------------------------------------------------------------------------------------------------------------

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

   1 - access("D"."DEPTNO"="E"."DEPTNO")
use_hash, swap_join_inputs
select /*+ gather_plan_statistics use_hash(d e) swap_join_inputs(e) */ d.deptno, d.dname, e.empno, e.ename
  from scott.dept d, scott.emp e
 where d.deptno = e.deptno;

----------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |     14 |00:00:00.01 |      15 |       |       |          |
|*  1 |  HASH JOIN         |      |      1 |     11 |     14 |00:00:00.01 |      15 |  1114K|  1114K|  556K (0)|
|   2 |   TABLE ACCESS FULL| EMP  |      1 |     14 |     14 |00:00:00.01 |       7 |       |       |          |
|   3 |   TABLE ACCESS FULL| DEPT |      1 |      4 |      4 |00:00:00.01 |       8 |       |       |          |
----------------------------------------------------------------------------------------------------------------

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

   1 - access("D"."DEPTNO"="E"."DEPTNO")
use_hash, leading
select /*+ gather_plan_statistics use_hash(d e) leading(e) */ d.deptno, d.dname, e.empno, e.ename
  from scott.dept d, scott.emp e
 where d.deptno = e.deptno;  

----------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |     14 |00:00:00.01 |      15 |       |       |          |
|*  1 |  HASH JOIN         |      |      1 |     10 |     14 |00:00:00.01 |      15 |  1114K|  1114K|  547K (0)|
|   2 |   TABLE ACCESS FULL| EMP  |      1 |     14 |     14 |00:00:00.01 |       7 |       |       |          |
|   3 |   TABLE ACCESS FULL| DEPT |      1 |      4 |      4 |00:00:00.01 |       8 |       |       |          |
----------------------------------------------------------------------------------------------------------------

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

   1 - access("D"."DEPTNO"="E"."DEPTNO")
use_hash ordered
select /*+ gather_plan_statistics use_hash(d e) ordered */ d.deptno, d.dname, e.empno, e.ename
  from scott.emp e, scott.dept d
 where d.deptno = e.deptno;  
 
----------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |     14 |00:00:00.01 |      15 |       |       |          |
|*  1 |  HASH JOIN         |      |      1 |     10 |     14 |00:00:00.01 |      15 |  1114K|  1114K|  534K (0)|
|   2 |   TABLE ACCESS FULL| EMP  |      1 |     14 |     14 |00:00:00.01 |       7 |       |       |          |
|   3 |   TABLE ACCESS FULL| DEPT |      1 |      4 |      4 |00:00:00.01 |       8 |       |       |          |
----------------------------------------------------------------------------------------------------------------

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

   1 - access("D"."DEPTNO"="E"."DEPTNO")

* 두 가지 해시 조인 알고리즘

ERD
첫 번째 알고리즘 (평범해시조인)
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      |                 |    10 |  1020 |    15  (14)| 00:00:01 |
|*  1 |  HASH JOIN            |                 |    10 |  1020 |    15  (14)| 00:00:01 | ⑨
|*  2 |   HASH JOIN           |                 |    27 |  2268 |    12  (17)| 00:00:01 | ⑦
|*  3 |    HASH JOIN          |                 |    23 |  1495 |     8  (13)| 00:00:01 | ⑤
|*  4 |     HASH JOIN         |                 |    25 |   725 |     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 |   375 |     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       |    91 |  1638 |     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")

  * 조인 과정
    1. Id[4] : REGIONS 로 해시 테이블 Build, COUNTRIES 로 해시 테이블 Probe 하면서 조인
    2. Id[3] : 위의 결과로 해시 테이블 Build, LOCATIONS 로 해시 테이블 Probe 하면서 조인
    3. Id[2] : 위의 결과로 해시 테이블 Build, DEPARTMENTS 로 해시 테이블 Probe 하면서 조인
    4. Id[1] : 위의 결과로 해시 테이블 Build, EMPLOYEES 로 해시 테이블 Probe 하면서 조인
두 번째 알고리즘 (NL조인처럼동작)
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        |                   |    10 |  2800 |    15  (20)| 00:00:01 |
|*  1 |  HASH JOIN              |                   |    10 |  2800 |    15  (20)| 00:00:01 | ⑫
|   2 |   VIEW                  | index$_join$_005  |   107 |  1926 |     3  (34)| 00:00:01 | ④
|*  3 |    HASH JOIN            |                   |       |       |            |          | ③
|   4 |     INDEX FAST FULL SCAN| EMP_DEPARTMENT_IX |   107 |  1926 |     1   (0)| 00:00:01 | ①
|   5 |     INDEX FAST FULL SCAN| EMP_NAME_IX       |   107 |  1926 |     1   (0)| 00:00:01 | ②
|*  6 |   HASH JOIN             |                   |     3 |   534 |    12  (17)| 00:00:01 | ⑪
|   7 |    TABLE ACCESS FULL    | DEPARTMENTS       |    27 |   513 |     3   (0)| 00:00:01 | ⑤
|*  8 |    HASH JOIN            |                   |     3 |   282 |     8  (13)| 00:00:01 | ⑩
|   9 |     TABLE ACCESS FULL   | LOCATIONS         |    23 |   828 |     3   (0)| 00:00:01 | ⑥
|* 10 |     HASH JOIN           |                   |     4 |   116 |     5  (20)| 00:00:01 | ⑨
|  11 |      TABLE ACCESS FULL  | REGIONS           |     4 |    56 |     3   (0)| 00:00:01 | ⑦
|  12 |      INDEX FULL SCAN    | COUNTRY_C_ID_PK   |    16 |   240 |     1   (0)| 00:00:01 | ⑧
---------------------------------------------------------------------------------------------

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

   1 - access("D"."DEPARTMENT_ID"="E"."DEPARTMENT_ID")
   3 - access(ROWID=ROWID)
   6 - access("L"."LOCATION_ID"="D"."LOCATION_ID")
   8 - access("C"."COUNTRY_ID"="L"."COUNTRY_ID")
  10 - access("R"."REGION_ID"="C"."REGION_ID")

  * 조인 과정
    1. 해시 테이블 생성
      1-1. EMPLOYEES
      1-2. DEPARTMENTS
      1-3. LOCATIONS
      1-4. REGIONS
    2. LOOP
      2-1. Id[10] : COUNTRIES 에서 한 건을 읽어 REGIONS 해시 테이블 탐색
      2-2. Id[8] : 위에서 조인에 성공한 레코드는 LOCATIONS 해시 테이블 탐색
      2-3. Id[6] : 위에서 조인에 성공한 레코드는 DEPARTMENTS 해시 테이블 탐색
      2-4. Id[1] : 위에서 조인에 성공한 레코드는 EMPLOYEES 해시 테이블 탐색
두 번째 알고리즘 (NL조인처럼동작+부분범위처리)
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      |                 |    10 |  3000 |    15  (14)| 00:00:01 |
|*  1 |  HASH JOIN            |                 |    10 |  3000 |    15  (14)| 00:00:01 | ⑨
|   2 |   TABLE ACCESS FULL   | REGIONS         |     4 |    56 |     3   (0)| 00:00:01 | ①
|*  3 |   HASH JOIN           |                 |    10 |  1980 |    12  (17)| 00:00:01 | ⑧
|   4 |    INDEX FULL SCAN    | COUNTRY_C_ID_PK |    25 |   375 |     1   (0)| 00:00:01 | ②
|*  5 |    HASH JOIN          |                 |    10 |  1100 |    10  (10)| 00:00:01 | ⑦
|   6 |     TABLE ACCESS FULL | LOCATIONS       |    23 |   828 |     3   (0)| 00:00:01 | ③
|*  7 |     HASH JOIN         |                 |    10 |   370 |     7  (15)| 00:00:01 | ⑥
|   8 |      TABLE ACCESS FULL| DEPARTMENTS     |    27 |   513 |     3   (0)| 00:00:01 | ④
|   9 |      TABLE ACCESS FULL| EMPLOYEES       |    91 |  1638 |     3   (0)| 00:00:01 | ⑤
-----------------------------------------------------------------------------------------

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

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

  * 조인 과정
    1. 해시 테이블 생성
      1-1. REGIONS
      1-2. COUNTRIES
      1-3. LOCATIONS
      1-4. DEPARTMENTS
    2. LOOP
      2-1. Id[7] : EMPLOYEES 에서 한 건을 읽어 DEPARTMENTS 해시 테이블 탐색 * EMPLOYEES 주관 부분범위처리 가능
      2-2. Id[5] : 위에서 조인에 성공한 레코드는 LOCATIONS 해시 테이블 탐색
      2-3. Id[3] : 위에서 조인에 성공한 레코드는 COUNTRIES 해시 테이블 탐색
      2-4. Id[1] : 위에서 조인에 성공한 레코드는 REGIONS 해시 테이블 탐색

* SWAP_JOIN_INPUTS 테스트

use_hash
SELECT /*+ GATHER_PLAN_STATISTICS USE_HASH(D) */ D.DEPTNO, D.DNAME, E.EMPNO, E.ENAME
  FROM SCOTT.EMP E,
       SCOTT.DEPT D
 WHERE E.DEPTNO = D.DEPTNO(+);

----------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |     14 |00:00:00.01 |      15 |       |       |          |
|*  1 |  HASH JOIN OUTER   |      |      1 |     10 |     14 |00:00:00.01 |      15 |  1114K|  1114K|  540K (0)|
|   2 |   TABLE ACCESS FULL| EMP  |      1 |     14 |     14 |00:00:00.01 |       7 |       |       |          |
|   3 |   TABLE ACCESS FULL| DEPT |      1 |      4 |      4 |00:00:00.01 |       8 |       |       |          |
----------------------------------------------------------------------------------------------------------------

Outline Data
-------------

  /*+
      BEGIN_OUTLINE_DATA
      IGNORE_OPTIM_EMBEDDED_HINTS
      OPTIMIZER_FEATURES_ENABLE('11.2.0.1')
      DB_VERSION('11.2.0.1')
      OPT_PARAM('optimizer_index_cost_adj' 25)
      OPT_PARAM('optimizer_index_caching' 90)
      FIRST_ROWS(10)
      OUTLINE_LEAF(@"SEL$1")
      FULL(@"SEL$1" "E"@"SEL$1")
      FULL(@"SEL$1" "D"@"SEL$1")
      LEADING(@"SEL$1" "E"@"SEL$1" "D"@"SEL$1")
      USE_HASH(@"SEL$1" "D"@"SEL$1")
      END_OUTLINE_DATA
  */

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

   1 - access("E"."DEPTNO"="D"."DEPTNO")
use_hash, swap_join_inputs(Build Input)
SELECT /*+ GATHER_PLAN_STATISTICS USE_HASH(D) SWAP_JOIN_INPUTS(E) */
       D.DEPTNO, D.DNAME, E.EMPNO, E.ENAME
  FROM SCOTT.EMP E,
       SCOTT.DEPT D
 WHERE E.DEPTNO = D.DEPTNO(+);

----------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |     14 |00:00:00.01 |      15 |       |       |          |
|*  1 |  HASH JOIN OUTER   |      |      1 |     10 |     14 |00:00:00.01 |      15 |  1114K|  1114K|  518K (0)|
|   2 |   TABLE ACCESS FULL| EMP  |      1 |     14 |     14 |00:00:00.01 |       7 |       |       |          |
|   3 |   TABLE ACCESS FULL| DEPT |      1 |      4 |      4 |00:00:00.01 |       8 |       |       |          |
----------------------------------------------------------------------------------------------------------------

Outline Data
-------------

  /*+
      BEGIN_OUTLINE_DATA
      IGNORE_OPTIM_EMBEDDED_HINTS
      OPTIMIZER_FEATURES_ENABLE('11.2.0.1')
      DB_VERSION('11.2.0.1')
      OPT_PARAM('optimizer_index_cost_adj' 25)
      OPT_PARAM('optimizer_index_caching' 90)
      FIRST_ROWS(10)
      OUTLINE_LEAF(@"SEL$1")
      FULL(@"SEL$1" "E"@"SEL$1")
      FULL(@"SEL$1" "D"@"SEL$1")
      LEADING(@"SEL$1" "E"@"SEL$1" "D"@"SEL$1")
      USE_HASH(@"SEL$1" "D"@"SEL$1")
      END_OUTLINE_DATA
  */

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

   1 - access("E"."DEPTNO"="D"."DEPTNO")
use_hash, swap_join_inputs(Probe Input)
SELECT /*+ GATHER_PLAN_STATISTICS USE_HASH(D) SWAP_JOIN_INPUTS(D) */
       D.DEPTNO, D.DNAME, E.EMPNO, E.ENAME
  FROM SCOTT.EMP E,
       SCOTT.DEPT D
 WHERE E.DEPTNO = D.DEPTNO(+);

-------------------------------------------------------------------------------------------------------------------
| Id  | Operation             | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
-------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |      1 |        |     14 |00:00:00.01 |      15 |       |       |          |
|*  1 |  HASH JOIN RIGHT OUTER|      |      1 |     10 |     14 |00:00:00.01 |      15 |  1134K|  1134K|  649K (0)|
|   2 |   TABLE ACCESS FULL   | DEPT |      1 |      4 |      4 |00:00:00.01 |       7 |       |       |          |
|   3 |   TABLE ACCESS FULL   | EMP  |      1 |     10 |     14 |00:00:00.01 |       8 |       |       |          |
-------------------------------------------------------------------------------------------------------------------

Outline Data
-------------

  /*+
      BEGIN_OUTLINE_DATA
      IGNORE_OPTIM_EMBEDDED_HINTS
      OPTIMIZER_FEATURES_ENABLE('11.2.0.1')
      DB_VERSION('11.2.0.1')
      OPT_PARAM('optimizer_index_cost_adj' 25)
      OPT_PARAM('optimizer_index_caching' 90)
      FIRST_ROWS(10)
      OUTLINE_LEAF(@"SEL$1")
      FULL(@"SEL$1" "E"@"SEL$1")
      FULL(@"SEL$1" "D"@"SEL$1")
      LEADING(@"SEL$1" "E"@"SEL$1" "D"@"SEL$1")
      USE_HASH(@"SEL$1" "D"@"SEL$1")
      SWAP_JOIN_INPUTS(@"SEL$1" "D"@"SEL$1")
      END_OUTLINE_DATA
  */

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

   1 - access("E"."DEPTNO"="D"."DEPTNO")
결론
  • swap_join_inputs 는 오른쪽(Probe Input)을 왼쪽(Build Input)으로 만들어 준다?

* Build Input 이 Hash Area 를 초과할 때 처리 방식

Grace 해시 조인 (Divide & Conquer)
  1. 파티션단계
    • 양쪽 집합 조인 컬럼의 해시 값에 따라 동적으로 파티셔닝 하여 Temp 에 저장 (조인 안될 놈까지 저장하는 비효율 있음)
  2. 조인단계
    • 파티션 짝 별로 조인 수행 (Build Input 선정은 파티션 짝 내에서 선정하며, 원 집합 크기와 관계 없음)
Hybrid 해시 조인
  1. 첫번째 테이블 처리
    1. 두 테이블중 작은 쪽을 Build Input 으로 선택 후, Hash Area 에서 해시 테이블을 생성 시작.
      • 두개의 해시 함수 사용
        • 레코드를 저장할 파티션(버킷) 결정용
        • 조인용
    2. 해시 테이블 생성 중, Hash Area 가 꽉차면, 그중 가장 큰 파티션(버킷)을 디스크에 기록
      • 디스크에 기록된 파티션에 해당하는 레코드는 디스크에 기록
      • Hash Area 가 또 꽉차면, 그중 가장 큰 파티션(버킷)을 또 디스크에 기록
    3. 완료 후, 파티션 크기가 작은 순으로 메모리를 채운다.
  2. 두번째 테이블 처리
    1. 두개의 해시 함수 사용해 테이블을 읽는다.
      1. 비트-벡터 필터링
      2. 통과 한 레코드는
        1. 레코드가 속한 파티션이 메모리에 있다면
          • 파티션을 스캔하여 조인에 성공하면 바로 결과 집합에 포함
        2. 레코드가 속한 파티션이 메모리에 없다면
          • Build Input 처럼 해시 파티션 한다. (두개 해시 함수)
      3. 통과 못한 레코드는 버림
  3. 조인(LOOP)
    1. 파티션 짝 별로 작은 쪽이 Build Input 이 되어 해시 테이블을 생성한다.
      • 앞에서 저장해둔 두번째 해시 값을 사용
Recursive 해시 조인 (= Nested-loops 해시 조인)
  • Recursive 해시 조인(=Nested-loops 해시 조인)
    • 파티션 짝 별로 조인 수행을 위해서 파티션을 메모리에 로드하는 과정에서 Hash Area 가 부족할때, 추가적인 파티셔닝 발동 하는데...
    • 구분
      • Optimal Hash Join (In-Memory Hash Join)
      • Onepass Hash Join (디스크 사용)
      • Multipass Hash Join (Recursive Hash Join)
비트-벡터 필터링 (bit-vector filtering)
  • 비트-벡터 필터링 (bit-vector filtering)
    • 조인 성공 가능성 없는 파티션 레코드는 아예 디스크에 기록 안한다
    • 동작
      1. 첫번째 테이블(Build Input)을 읽어 해시 파티션/테이블 생성시
        1. 해시 버킷이 첫번째 해시 함수 값에 의해서 결정 되면,
        2. 두번째 해시 함수 값을 참조 해서 해당 비트-벡터도 1(positive)로 설정
      2. 두번째 테이블(Probe Input)을 읽어 해시 파티션 생성시
        1. 첫번째, 두번째 해시 함수 값에 의한 해당 비트-벡터의 위치를 얻는다.
        2. 비트 값이 1(positive)이면 사용, 비트 값이 0(negative)이면 버린다.

* Build Input 해시 값에 중복이 많을 때 발생하는 비효율

해시충돌
데모준비
drop table hj_order;

create table hj_order
(
  product_cd varchar2(3),
  order_dt varchar2(8),
  order_no varchar2(5),
  order_type varchar2(1)
);

insert into hj_order
select '000' as product_cd,
       '20100825' as order_dt,
       level as order_no,
       ROUND(DBMS_RANDOM.VALUE(1, 2)) as order_type
  from dual
 connect by level < 10000

create unique index hj_order_pk on hj_order (product_cd, order_dt, order_no);

drop table hj_fill;

create table hj_fill
(
  product_cd varchar2(3),
  fill_dt varchar2(8),
  fill_no varchar2(5),
  order_no_buy varchar2(5),
  order_no_sell varchar2(5)
);

insert into hj_fill
select /*+ use_hash(o1 o2) */ '000' as product_cd, '20100825' as fill_dt,
       rownum as fill_no,
       o1.order_no as order_no_buy,
       o2.order_no as order_no_sell
  from (select rownum as rnum, order_no from hj_order where order_type = '1') o1,
       (select rownum as rnum, order_no from hj_order where order_type = '2') o2
 where o1.rnum = o2.rnum
   
create unique index hj_fill_pk on hj_fill (product_cd, fill_dt, fill_no);

데모#1 - 버킷1개당 모든엔트리
select /*+ gather_plan_statistics use_hash(o f) */
       COUNT(*)
  from hj_order o,
       hj_fill f
 where o.product_cd = f.product_cd
   and o.order_dt = f.fill_dt
   and o.order_no in (f.order_no_buy, f.order_no_sell);   
------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation           | Name     | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |  OMem |  1Mem | Used-Mem |
------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |          |      1 |        |      1 |00:00:35.79 |      69 |      2 |       |       |          |
|   1 |  SORT AGGREGATE     |          |      1 |      1 |      1 |00:00:35.79 |      69 |      2 |       |       |          |
|*  2 |   HASH JOIN         |          |      1 |      4 |   9962 |00:00:32.41 |      69 |      2 |   972K|   972K|  849K (0)|
|   3 |    TABLE ACCESS FULL| HJ_FILL  |      1 |   4981 |   4981 |00:00:00.01 |      31 |      0 |       |       |          |
|   4 |    TABLE ACCESS FULL| HJ_ORDER |      1 |   9999 |   9999 |00:00:00.01 |      38 |      2 |       |       |          |
------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O"."PRODUCT_CD"="F"."PRODUCT_CD" AND "O"."ORDER_DT"="F"."FILL_DT")
       filter(("O"."ORDER_NO"="F"."ORDER_NO_BUY" OR "O"."ORDER_NO"="F"."ORDER_NO_SELL"))
데모#2 - 버킷1개당 1개엔트리 (UNION ALL)
select /*+ gather_plan_statistics use_hash(o f) */
       COUNT(*)
  from hj_order o,
       (select product_cd, fill_dt, order_no_buy as order_no from hj_fill
        union all
        select product_cd, fill_dt, order_no_sell as order_no from hj_fill) f
 where o.product_cd = f.product_cd
   and o.order_dt = f.fill_dt
   and o.order_no = f.order_no;
-----------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation             | Name        | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |  OMem |  1Mem | Used-Mem |
-----------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |             |      1 |        |      1 |00:00:00.04 |     102 |      7 |       |       |          |
|   1 |  SORT AGGREGATE       |             |      1 |      1 |      1 |00:00:00.04 |     102 |      7 |       |       |          |
|*  2 |   HASH JOIN           |             |      1 |     22 |   9962 |00:00:00.04 |     102 |      7 |  1208K|  1208K| 1588K (0)|
|   3 |    VIEW               |             |      1 |     22 |   9962 |00:00:00.01 |      62 |      5 |       |       |          |
|   4 |     UNION-ALL         |             |      1 |        |   9962 |00:00:00.01 |      62 |      5 |       |       |          |
|   5 |      TABLE ACCESS FULL| HJ_FILL     |      1 |     11 |   4981 |00:00:00.01 |      31 |      5 |       |       |          |
|   6 |      TABLE ACCESS FULL| HJ_FILL     |      1 |     11 |   4981 |00:00:00.01 |      31 |      0 |       |       |          |
|   7 |    INDEX FULL SCAN    | HJ_ORDER_PK |      1 |   9999 |   9999 |00:00:00.01 |      40 |      2 |       |       |          |
----------------------------------------------------------------------------------------------------------------------------------- 
Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O"."PRODUCT_CD"="F"."PRODUCT_CD" AND "O"."ORDER_DT"="F"."FILL_DT" AND "O"."ORDER_NO"="F"."ORDER_NO")
데모#3 - 버킷1개당 1개엔트리 (COPY_T)
select /*+ gather_plan_statistics use_hash(o f) */
       COUNT(*)
  from hj_order o,
       (select product_cd, fill_dt, decode(y.key, 1, order_no_buy, order_no_sell) as order_no
          from hj_fill x,
               (select level as key from dual connect by level <= 2) y
       ) f
 where o.product_cd = f.product_cd
   and o.order_dt = f.fill_dt
   and o.order_no = f.order_no;
-------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                        | Name        | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
-------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                 |             |      1 |        |      1 |00:00:00.04 |      71 |       |       |          |
|   1 |  SORT AGGREGATE                  |             |      1 |      1 |      1 |00:00:00.04 |      71 |       |       |          |
|*  2 |   HASH JOIN                      |             |      1 |   4981 |   9962 |00:00:00.04 |      71 |  1280K|  1205K| 1637K (0)|
|   3 |    MERGE JOIN CARTESIAN          |             |      1 |   4981 |   9962 |00:00:00.01 |      31 |       |       |          |
|   4 |     VIEW                         |             |      1 |      1 |      2 |00:00:00.01 |       0 |       |       |          |
|   5 |      CONNECT BY WITHOUT FILTERING|             |      1 |        |      2 |00:00:00.01 |       0 |       |       |          |
|   6 |       FAST DUAL                  |             |      1 |      1 |      1 |00:00:00.01 |       0 |       |       |          |
|   7 |     BUFFER SORT                  |             |      2 |   4981 |   9962 |00:00:00.01 |      31 |   337K|   337K|  299K (0)|
|   8 |      TABLE ACCESS FULL           | HJ_FILL     |      1 |   4981 |   4981 |00:00:00.01 |      31 |       |       |          |
|   9 |    INDEX FULL SCAN               | HJ_ORDER_PK |      1 |   9999 |   9999 |00:00:00.01 |      40 |       |       |          |
-------------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O"."PRODUCT_CD"="PRODUCT_CD" AND "O"."ORDER_DT"="FILL_DT" AND
              "O"."ORDER_NO"=DECODE("Y"."KEY",1,"ORDER_NO_BUY","ORDER_NO_SELL"))

* 해시 조인 사용 기준

  • 키포인트
    • 한 쪽 집합이 Hash Area에 담길 정도로 충분히 작아야 함
    • Build Input 해시 키 컬럼에 중복 값이 거의 없어야 함
  • 언제?
    • 조인 컬럼에 인덱스가 없어 NL 조인 불가할 때
    • NL 조인시, Inner 쪽 집합으로 Random 액세스 부하가 심할 때
    • 소트머지조인시 소트 부하가 심할 때
    • 수행 빈도가 낮고, 오래 걸리는 대용량 테이블 조인할 때
  • 주의
    • 해시 테이블은 재사용 불가 고비용 자료구조
    • 수행 빈도가 높은 쿼리에 적용하면 CPU, 메모리 사용률, 래치 경합 매우 증가
  • 최초작성자 : 오화균
  • 최초작성일 : 2010년 08월 27일
  • 이 문서는 오라클클럽 대용량 데이터베이스 스터디 모임에서 작성하였습니다.
  • 이 문서의 내용은 (주)비투엔컬설팅에서 출간한 '오라클 성능 고도화 원리와 해법II'를 참고하였습니다.

문서정보

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