Chap02. 03 해시 조인

01. 기본 메커니즘

---

• NL 조인과 Sort Merge Join이 효과적이지 못한 상황에 대한 대안으로서 개발
• 둘 중 작은 Table(Build Input)을 읽어 Hash Area에 Hash Table을 생성하고, 반대쪽 큰 Table(Probe Input)을 읽어 Hash Table을 탐색하면서 Join 하는 방식
• Hash Join이 NL보다 빠른 이유
  • Hash Table이 PGA 영역에 할당된다는 데 있기 때문, NL 조인은 Outer 테이블에서 읽히는 레코드마다 Inner 쪽 테이블 버퍼 캐시 탐색을 위해 래치 획득을 반복하지만, Hash Join은 래치 획득 없이 PGA에서 빠르게 데이터를 탐색합니다.
• Hash Join이 가능한 Join 조건은 무조건 등치('=') 조건 일때

Hash Join

 

Hash Join 특징

• NL Join 처럼 Random Access 부하가 없고(양쪽 집합을 읽는과정에서 Index 존재 시 발생함)
• Sort Merge Join 처럼 조인 전에 미리 양쪽 집합을 정렬하는 부담도 없습니다.
• 단, 해시 테이블을 생성하는 비용이 수반 됩니다.
  • PGA 메모리에 할당되는 Hash Area에 담길 정도로 충분히 작아야 합니다.
  • 만약 Build Input이 Hash Area 크기를 초과한다면, 디스크에 썼다가 다시 읽어 들이는 과정을 거치기 때문에 성능이 많이 저하됩니다.
• Build Input으로 선택된 테이블이 작은 것도 중요하지만, 해시 키 값으로 사용되는 컬럼에 중복 값이 거의 없을 때 효과적

 

02. 힌트를 이용한 조인 순서 및 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;

 

• USE_HASH : 두 Table을 Hash Join으로 풀어라
• USE_HASH만 주었기에 Build Input은 옵티마이저의 판단에 의해 결정
• Hash Join 관련된 중요 Hint
  • SWAP_JOIN_INPUTS : Hash Join 시 사용자가 Build Input 지정
  • NO_SWAP_JOIN_INPUTS : Hash Join 시 사용자가 Probe Input 지정

Hash Join 실행계획

.

 

 

SELECT /*+ use_hash(d e) swap_join_inputs(e) */ d.deptno, d.dname, e.empno ....

SELECT /*+ leading(e) use_hash(d) */ d.deptno, d.dname, e.empno, e.ename ....

----------------------------------------------------------------------------------
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   |  EMP  |    14  |   182  |    3  (0)    | 00:00:01 
3   |      TABLE ACCESS FULL   |  DEPT |     4  |    52  |    3  (0)    | 00:00:01

 

 

03. 두 가지 해시 조인 알고리즘

---

 

• 오라클은 해시 조인을 위해 두 가지 알고리즘을 사용

첫번째

-- FULL Hint를 넣은 이유는 기존에 사용하던 Index 때문에 
SELECT /*+ LEADING(R, C, L, D, E) FULL(D) FULL(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;

 

 

• Leading Hint의 의도로 REGIONS -> COUNTRIES -> LOCATIONS -> DEPARTMENTS -> EMPLOYEES 순으로 각각 Hash Join으로 처리하라고 지시하고 있습니다.

1. REGIONS Table을 Build Input으로 Hash Area에 담고, Country Index를 읽어 Hash Table을 탐색하면서 Join 수행
2. 위결과를 Build Input으로 Hash Area 담고, Location Table을 읽어 Hash Table을 탐색하면서 Join 수행
3. ....
4. ...

 

 

두번째

• 첫번째 Build Input에 대한 지정을 제외한 나머지에 Build Input은 사용자가 직접 지정하는 방법

SELECT /*+ LEADING(R, C, L, D, E) FULL(D) FULL(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;

SWAP_JOIN_INPUTS로 사용자지정 Build Input

 

1. Hash Table 생성 : EMPLOYTEES, DEPARTMENTS, LOCATIONS, REGIONS 4개의 Table에 대한 Hash Table을 먼저 생성
2. id 7번 Hash Join : COUNTRIES에서 한건을 읽어 REGIONS Hash Table을 탐색
3. id 5번 Hash Join : 2번에서 Join 성공한 Record는 LOCATIONS Hash Table을 탐색
4. id 3번 Hash Join : 3번에서 Join 성공한 Record는 DEPARTMENTS Hash Table을 탐색
5. id 1번 Hash Join : 4번에서 Join 성공한 Record는 EMPLOYEES Hash Table을 탐색
6. 2~5번 과정을 COUNTRIES INDEX를 모두 SCAN할 때까지 반복

 

 

가장 큰 Table인 EMPLOYEES를 Probe Input 으로 두어 한건씩 읽을 때

• EMPLOYEES(PROBE TABLE)로 생성하고, 그 외 테이블을 HASH TABLE로 읽도록하여 JOIN을 수행해 가면,
  • 작은 테이블로 빠르게 해시 테이블을 생성하고 나서, 큰 테이블에서 일부 레코드만 스캔하다가 조인을 멈출 수 있는데, 이는 NL 조인의 가장 큰 장점인 부분범위처리를 해시 조인에서도 갖게 되는 것입니다.

 

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

---

• In-Memory 해시 조인이 불가능할 때 오라클은 어떤 방식으로 해시 조인을 처리할까??

1. Grace 해시 조인
   
   • 단계
     • ① 파티션 단계
     • ② 조인 단계
2. Hybrid 해시 조인
3. Recursive 해시 조인(=Nested-loops 해시 조인)
4. 비트-벡터 필터링

 

 

 

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

---

• 해시 알고리즘의 성능은 해시 충돌(collision)을 얼마나 최소화 할 수 있느냐에 달렸습니다.
  • 이를 방지하려면 그만큼 많은 해시 버킷을 할당해야만 합니다.
  • 오라클은 충분히 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력합니다.
  • 해시 버킷이 아무리 많이 할당하더라도 해시 테이블에 저장할 키 컬럼에 중복 값이 많으면 하나의 버킷에 많은 엔트리가 달릴 수 밖에 없으며, 해시 버킷을 빨리 찾다는다 하더라도 중복된 키 값을 스캔하는 단계에서 많은 시간을 허비하게 되어 탐색 속도가 현저히 저하됩니다.

 

예시 쿼리

주문 Table과 주문체결 Table 기억

주문체결 Table을 두번 읽어 하나는 매도주문접수번호, 하나는 매수주문접수번호로 UNION ALL 한 후 찾기

 

 

06. 해시 조인 사용기준

 

---

• 해시 조인 성능을 좌우하는 두 가지 키 포인트
  • 한 쪽 테이블이 Hash Area에 담길 정도로 충분히 작아야 함
  • Build Input 해시 키 컬럼에 중복 값이 거의 없어야 함

 

언제 효과적??

• 조인 컬럼에 적당한 인덱스가 없어 NL 조인이 비효율적일 때
• 조인 컬럼에 인덱스가 있더라도 NL 조인 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때
• 소트 머지 조인하기에는 두 테이블이 너무 커 소트 부하가 심할 때
• 수행빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인(배치 프로그램, DW, OLAP성 쿼리)할 때

 

4번째 경우 확인

• 해시 조인이 만능으로 보이나 이는 매우 위험한 사고
  • NL 조인에 사용되는 인덱스는 영구적으로 유지되면서, 다른 쿼리를 위해 공유 및 재사용되는 자료구조이며,
  • 해시 테이블은 단 하나의 쿼리를 위해 생성하고 조인이 끝나면 곧바로 소멸하는 자료구조 입니다.
• OLTP성 쿼리 처럼 수행시간이 짧으면서 빈도가 높을 경우 해시 조인 시 매번 생성하고 소멸되기에 CPU와 메모리 사용률을 크게 증가 시키며, SQL memory manager workarea, row cache objects, simulator hash latch, cache buffers chains 같은 래치 경합이 발생해 시스템의 동시성을 떨어트리게 됩니다.
• 무조건 사용하지 말라는 것 보다는, 1s 쿼리를 0.1s 단축 목적으로 사용하지 말란 의미 입니다.