Hash Join

기본 메커니즘

1. build 단계 : 작은 쪽 테이블(build input)을 읽어 해시 테이블(해시 맵)을 생성한다.

2. probe 단계 : 큰 쪽 테이블(probe input)을 읽어 해시 테이블을 탐색하면서 조인한다.

* use_hash 힌트로 해시조인을 유도한다.

3. 해시 조인 - [종료]구루비 DB 스터디 - 개발자, DBA가 함께 만들어가는 구루비 지식창고! (gurubee.net)

SQL 수행과정

SELECT /*+ ordered use_hash(E) */ E.EMPNO, E.ENAME, E.SAL, D.DNAME
FROM DEPT D
	INNER JOIN EMP E
	ON D.DEPTNO = E.DEPTNO
	AND E.SAL > 1500
	AND E.JOB = 'SALESMAN'
WHERE D.DNAME = 'SALES'
;
Execution plan
-----------------------------------------------------------------
| Id | Operation           | Name   | Card  | Bytes | Cost (%CPU)|
-----------------------------------------------------------------
|   0| SELECT STATEMENT    |        |     1 |    32 |    8    (0)|
|*  1|  HASH JOIN          |        |     1 |    32 |    8    (0)|
|*  2|   TABLE ACCESS FULL | DEPT   |     1 |    13 |    4    (0)|
|*  3|   TABLE ACCESS FULL | EMP    |     2 |    50 |    4    (0)|
-----------------------------------------------------------------

Predicate Information (identified by operation id):
-----------------------------------------------------------------
   1 - access("D"."DEPTNO"="E"."DEPTNO")
-----------------------------------------------------------------

① BUILD 단계 : 아래 조건에 해당하는 DEPT 데이터를 읽어 해시 테이블을 생성한다.

SELECT D.DNAME, D.DEPTNO
  FROM DEPT D
 WHERE D.DNAME = 'SALES'

이때 조인 컬럼인 DEPTNO 를 해시 테이블 키값으로 사용한다. 즉, DEPTNO 를 해시 함수에 입력하면 반환된 값으로 해시 체인을 찾고, 그 해시 체인에 데이터를 연결한다. 해시 테이블은 PGA 영역에 할당된 Hash Area 에 저장한다. 해시 테이블이 너무 커서 PGA에 담을 수 없다면, Temp 테이블스페이스에 저장한다. 해시 테이블에는 조인 키 값뿐만이 아니라 SQL에 사용한 컬럼을 모두 저장한다.

 

② PROBE 단계 : 아래 조건에 해당하는 EMP 데이터를 하나씩 읽어 앞서 생성한 해시 테이블을 탐색한다.

SELECT E.EMPNO, E.ENAME, E.SAL, E.DEPTNO
FROM EMP E
WHERE E.SAL > 1500
AND E.JOB = 'SALESMAN'

즉, DEPTNO 를 해시 함수에 입력해서 반환도니 값으로 해시 체인을 찾고, 그 해시 체인을 스캔해서 값이 같은 DEPTNO 를 찾는다. 찾으면 조인에 성공한 것이고, 못찾으면 실패한 것이다.

이 과정은 NL 조인과 다르지 않다.

 

해시조인이 NL조인보다 빠른 이유

해시 테이블(=해시 맵)을 PGA 영역에 할당하기 때문에 래치 획득 과정 없이 데이터를 빠르게 탐색/조인한다.

 

해시조인이 소트 머지 조인보다 빠른 이유

서로 다른 사전 준비 작업으로 인한 Temp TBS 사용 유무

 

소트 머지 조인의 사전 준비작업은 '양쪽' 집합을 모두 정렬해서 PGA 에 담는 것이다.

PGA 는 그리 큰 메모리 공간이 아니므로 두 집합 중 어느 하나가 중대형 이상이면, Temp tbs, 즉 디스크에 쓰는 작업을 반드시 수반한다.

 

해시 조인의 사전 준비작업은 양쪽 집합 중 크기가 더 작은 '한쪽'을 읽어 해시 맵을 만드는 것이다. 

두 집합 모두 hash area 에 담을 수 없을 정도로 큰 경우가 아니라면, Temp tbs, 즉 디스크에 쓰는 작업은 전혀 일어나지 않는다. 그리고 설령 temp tbs 를 쓰게 되더라도 대량 데이터 조인할 때는 일반적으로 해시 조인이 가장 빠르다.

 

 

대용량 build input 처리

조인하려는 두 개의 테이블이 모두 대용량으로 인메모리 해시 조인이 불가능하다면?

divide & conquer (분할 정복) 방식을 사용한다.

 

① 파티션 단계 = divide

조인 대상 집합의 조인 컬럼에 해시함수를 적용하고, 반환된 해시 값에 따라 동적으로 파티셔닝한다. 독립적으로 처리할 수 있는 여러 개의 작은 서브 집합으로 분할함으로써 파티션 pair 를 생성하는 단계이다.

양쪽 집합을 읽어 disk temp tbs 에 저장해야 하므로 인메모리 해시 조인보다 성능이 많이 떨어진다.

② 조인 단계 = conquer

파티션 단계에서 만든 pair 에 대해 하나씩 조인을 수행한다.

이때, 2개의 파티션 중 더 작은 쪽이 build input, 큰쪽이 probe input으로 결정한다.(테이블 크기와 상관 x)

build input으로 해시 테이블을 생성한 후, 반대쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색한다. 모든 파티션 pair 에 대한 처리를 마칠 때까지 이 과정을 반복한다.

 

실행계획 제어

실행 계획에서 위쪽 데이터(HASH JOIN 바로 아래)가 build input 이고, 아래쪽이 probe input 이 된다. 

SELECT /*+ use_hash(D E) */ E.EMPNO, E.ENAME, E.SAL, D.DNAME
FROM DEPT D
	INNER JOIN EMP E
	ON D.DEPTNO = E.DEPTNO
	AND E.SAL > 1500
	AND E.JOB = 'SALESMAN'
WHERE D.DNAME = 'SALES'
;

Execution plan
-----------------------------------------------------------------
| Id | Operation           | Name   | Card  | Bytes | Cost (%CPU)|
-----------------------------------------------------------------
|   0| SELECT STATEMENT    |        |     1 |    32 |    8    (0)|
|*  1|  HASH JOIN          |        |     1 |    32 |    8    (0)|
|*  2|   TABLE ACCESS FULL | DEPT   |     1 |    13 |    4    (0)| --- build input
|*  3|   TABLE ACCESS FULL | EMP    |     2 |    50 |    4    (0)| --- probe input
-----------------------------------------------------------------

→ use_hash 힌트만 사용하면, build input을 옵티마이저가 선택하는데, 일반적으로 2개 테이블 중 카디널리티가 작은 테이블을 선택한다. 여기서 카디널리티(unique value 개수)는 테이블 전체 카디널리티가 아닌 각 테이블의 조건절에 대한 카디널리티를 의미한다.

 

build input을 사용자가 직접 선택하려면?

방법1) 조인 순서를 leading 이나 ordered 힌트로 먼저 지정하고, 먼저 읽은 테이블이 build input이 된다. 

SELECT /*+ leading(E) use_hash(D) */ E.EMPNO, E.ENAME, E.SAL, D.DNAME
FROM DEPT D
	INNER JOIN EMP E
	ON D.DEPTNO = E.DEPTNO
	AND E.SAL > 1500
	AND E.JOB = 'SALESMAN'
WHERE D.DNAME = 'SALES'
;

Execution plan
-----------------------------------------------------------------
| Id | Operation           | Name   | Card  | Bytes | Cost (%CPU)|
-----------------------------------------------------------------
|   0| SELECT STATEMENT    |        |     1 |    32 |    8    (0)|
|*  1|  HASH JOIN          |        |     1 |    32 |    8    (0)|
|*  2|   TABLE ACCESS FULL | EMP    |     2 |    50 |    4    (0)|
|*  3|   TABLE ACCESS FULL | DEPT   |     1 |    13 |    4    (0)|
-----------------------------------------------------------------

Predicate Information (identified by operation id):
-----------------------------------------------------------------
   1 - access("D"."DEPTNO"="E"."DEPTNO")
-----------------------------------------------------------------

방법2) swap_join_inputs 힌트를 사용해서 build input 을 명시적으로 선택한다.

SELECT /*+ leading(E) use_hash(D) swap_join_inputs(D) */ E.EMPNO, E.ENAME, E.SAL, D.DNAME
FROM DEPT D
	INNER JOIN EMP E
	ON D.DEPTNO = E.DEPTNO
	AND E.SAL > 1500
	AND E.JOB = 'SALESMAN'
WHERE D.DNAME = 'SALES'
;


Execution plan
-----------------------------------------------------------------
| Id | Operation           | Name   | Card  | Bytes | Cost (%CPU)|
-----------------------------------------------------------------
|   0| SELECT STATEMENT    |        |     1 |    32 |    8    (0)|
|*  1|  HASH JOIN          |        |     1 |    32 |    8    (0)|
|*  2|   TABLE ACCESS FULL | DEPT   |     1 |    13 |    4    (0)|
|*  3|   TABLE ACCESS FULL | EMP    |     2 |    50 |    4    (0)|
-----------------------------------------------------------------

Predicate Information (identified by operation id):
-----------------------------------------------------------------
   1 - access("D"."DEPTNO"="E"."DEPTNO")
-----------------------------------------------------------------

 

세 개 이상 테이블 해시 조인

1. 조인 연결고리르 따라 순방향 또는 역방향으로 LEADING 힌트에 기술한다

2. build input 으로 선택하고 싶은 테이블을 swap_join_inputs 힌트에 지정한다.

3. build input으로 선택하고 싶은 테이블이 조인된 결과집합인 경우, no_swap_join_inputs 힌트 사용해서 반대쪽 probe input을 지정해준다.

-- build input 순서를 옵티마이저가 선택한다.
SELECT /*+ use_hash(TAB1 TAB2 TAB3) */ *
  FROM EDU.TAB1, EDU.TAB2, EDU.TAB3
 WHERE TAB1.C3 = TAB2.C3
   AND TAB1.C4 = TAB3.C4
   ;
   

-- leading 힌트 첫 번째 파라미터로 지정한 테이블은 무조건 build input이다.
-- (TAB1+TAB2) 와 TAB3 중에 build input은 옵티마이저가 선택한다
SELECT /*+ leading(TAB1, TAB2, TAB3) use_hash(TAB2) use_hash(TAB3) */ *
  FROM EDU.TAB1, EDU.TAB2, EDU.TAB3
 WHERE TAB1.C3 = TAB2.C3
   AND TAB1.C4 = TAB3.C4
 ;
 
-- leading 힌트의 첫 번째 파라미터가 build input 이었으나,
-- swap_join_inputs 로 build_input 을 지정하여 TAB2 가 build input 이고 TAB1 이 probe input 이다.
-- (TAB2+TAB1) 와 TAB3 중에 build input은 옵티마이저가 선택한다
SELECT /*+ leading(TAB1, TAB2, TAB3) swap_join_inputs(TAB2) */ *
  FROM EDU.TAB1, EDU.TAB2, EDU.TAB3
 WHERE TAB1.C3 = TAB2.C3
   AND TAB1.C4 = TAB3.C4
 ;
 
-- TAB1 -> TAB2 와 조인하며, 2개 테이블에 대한 역할 지정 힌트가 없으므로
-- TAB1 이 build input TAB2가 probe input 이다. (TAB1+TAB2)
-- TAB3 는 build input 으로 수행하라고 했으므로 (TAB3 + (TAB1+TAB2)) 이다.
SELECT /*+ leading(TAB1, TAB2, TAB3) swap_join_inputs(TAB3) */ *
  FROM EDU.TAB1, EDU.TAB2, EDU.TAB3
 WHERE TAB1.C3 = TAB2.C3
   AND TAB1.C4 = TAB3.C4
 ;
 
 

-- TAB1 -> TAB2 와 조인하며, 2개 테이블에 대한 역할 지정 힌트가 없으므로
-- TAB1 이 build input TAB2가 probe input 이다. (TAB1+TAB2)
-- TAB3 는 probe input 으로 수행하라고 했으므로 ((TAB1+TAB2)+TAB3) 이다.
SELECT /*+ leading(TAB1, TAB2, TAB3) no_swap_join_inputs(TAB3) */ *
  FROM EDU.TAB1, EDU.TAB2, EDU.TAB3
 WHERE TAB1.C3 = TAB2.C3
   AND TAB1.C4 = TAB3.C4
 ;