[3] Hash Join

• 둘 중 작은 집합(Build Input)을 읽어 해시 영역에 해시 테이블(= 해시 맵)을 생성하고,
  반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 조인하는 방식

(1) 기본 메커니즘

• 해시 함수는, 출력값을 미리 알 순 없지만, 같은 입력값에 대해 같은 출력값을 보장하는 함수이다.
• 해시 충돌 : 다른 입력값에 대한 출력값이 같을 때 일어난다.
  • 해시 테이블을 만들 때 해시 충돌이 발생하면, 입력값이 다른 엔트리가 한 해시 버킷에 담길 수 있다.

(2) Hash Join 과정

1단계 : 해시 테이블 생성

• 두 집합 중 작다고 판단되는 집합을 읽어 해시 함수를 사용해 해시 테이블을 만든다.
• 해시 테이블은 해시 버킷으로 구성된 배열이다.
• 해시 함수에서 리턴받은 해시 값이 같은 데이터를 같은 해시 버킷에 체인(연결 리스트)으로 연결한다.

2단계 : Probe Input을 스캔

• Probe Input을 스캔해시 테이블 생성을 위해 선택되지 않은 나머지 데이터 집합(Probe Input)을 스캔한다.

3단계 : 해시 테이블 탐색

• Probe Input에서 읽은 데이터로 해시 테이블을 탐색할 때도 해시 함수를 사용한다.
• 즉, 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다.

(3) Hash Join 특징

• NL Join처럼 조인 과정에서 발생하는 Random 액세스 부하가 없다.
• Sort Merge Join처럼 조인 전에 미리 양쪽 집합을 정렬하는 부담도 없다.
• 다만, 해시 테이블을 생성하는 비용이 수반된다. 따라서 Build Input이 작을 때 효과적이다.
• Hash Build를 위해 가용한 메모리 공간을 초과할 정도로 Build Input이 대용량 테이블이면 디스크에 썼다가 다시 읽어 들이는 과정을 거치기 때문에 성능이 많이 저하된다.
• Build Input으로 선택된 테이블이 작은 것도 중요하지만 해시 키 값으로 사용되는 칼럼에 중복 값이 거의 없을 때 효과적이다.
• 해시 테이블을 만드는 단계는 전체범위처리가 불가피하지만, 반대쪽 Probe Input을 스캔하는 단계는 NL Join처럼 부분범위처리가 가능하다

(4) Build Input이 가용 메모리 공간을 초과할 때 처리 방식

In-Memory Hash Join이 불가능할 때 DBMS는 ‘Grace Hash Join’이라고 알려진 조인 알고리즘을 사용한다.

1. Grace Hash Join

• 분할 정복(Divide & Conquer) 방식
• 두 개의 큰 테이블을 Hash Join하는 기본 알고리즘은 Grace Hash Join에 바탕을 둔다.

2. Grace Hash Join 처리 과정

1. 파티션 단계

• 조인되는 양쪽 집합(→ 조인 이외 조건절을 만족하는 레코드) 모두 조인 칼럼에 해시 함수를 적용하고
  반환된 해시 값에 따라 동적으로 파티셔닝을 실시한다.
• 독립적으로 처리할 수 있는 여러 개의 작은 서브 집합으로 분할함으로써 파티션 짝(pair)을 생성한다.
• 파티션 단계에서 양쪽 집합을 모두 읽어 디스크 상의 Temp 공간에 일단 저장해야 하므로 In-Memory Hash Join보다 성능이 크게 떨어지게 된다.

2. 조인 단계

• 각 파티션 짝(pair)에 대해 하나씩 조인을 수행한다.
• 이때, 각각에 대한 Build Input과 Probe Input은 독립적으로 결정된다.
• 즉, 파티션하기 전 어느 쪽이 작은 테이블이었는지에 상관없이 각 파티션 짝(pair)별로 작은 쪽 파티션을 Build Input으로 선택해 해시 테이블을 생성한다.
• 해시 테이블이 생성되고 나면 반대 쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색하며, 모든 파티션 짝에 대한 처리가 완료될 때까지 이런 과정을 반복한다.

Recursive Hash Join(=Nested-loops Hash Join)

• 디스크에 기록된 파티션 짝(pair)끼리 조인을 수행하려고 ‘작은 파티션’을 메모리에 로드하는 과정이다.
• 또 다시 가용 메모리를 초과하는 경우가 발생하는 경우 추가적인 파티셔닝 단계가 일어난다.

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

• 해시 알고리즘의 성능은 해시 충돌을 얼마나 최소화할 수 있느냐에 달려있다.
  • 해시 충돌 방지 : 버킷 하나당 하나의 키 값만 갖게 하려고 노력한다.
• 해시 버킷을 아무리 많이 할당하더라도 해시 테이블에 저장할 키 칼럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달릴 수 밖에 없다.
  • 그러면 해시 버킷을 아무리 빨리 찾더라도 해시 버킷을 스캔하는 단계에서 많은 시간을 허비. 탐색 속도가 현저히 저하된다.
• 따라서 Build Input의 해시 키 칼럼에는 중복 값이 (거의) 없어야 Hash Join이 빠르게 수행될 수 있다.

(6) Hash Join 사용기준

1. Hash Join 성능을 좌우하는 두 가지 키 포인트

<1> 한 쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야 한다.

<2> Build Input 해시 키 칼럼에 중복 값이 거의 없어야 한다.

2. Hash Join을 언제 사용하는 것이 효과적인지에 대한 선택 기준

• 조인 칼럼에 적당한 인덱스가 없어 NL Join이 비효율적일 때
• 조인 칼럼에 인덱스가 있더라도 NL Join 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 Random 액세스 부하가 심할 때
• Sort Merge Join 하기에는 두 테이블이 너무 커 소트 부하가 심할 때
• 수행빈도가 낮고 조인할 때

(7) 수행시간이 짧으면서 수행빈도가 매우 높은 쿼리를 Hash Join으로 처리하는 경우

• 수행시간이 짧으면서 수행빈도가 매우 높은 쿼리는 OLTP성 쿼리의 특징이기도 하다.
• NL Join에 사용되는 인덱스는 (Drop하지 않는 한) 영구적으로 유지되면서 다양한 쿼리를 위해 공유 및 재사용되는 자료구조이다.
• 해시 테이블은 단 하나의 쿼리를 위해 생성하고 조인이 끝나면 곧바로 소멸하는 자료구조이다.

수행빈도가 높은 쿼리에 Hash Join을 사용하면...

1. CPU와 메모리 사용률을 크게 증가시킨다.
2. 메모리 자원을 확보하기 위한 각종 래치 경합이 발생해 시스템 동시성을 떨어뜨릴 수 있다.

결론

Hash Join은 아래와 같은 상황에서 주로 사용해야한다.

① 수행 빈도가 낮고

② 쿼리 수행 시간이 오래 걸리는

③ 대용량 테이블을 조인할 때(→ 배치 프로그램, DW, OLAP성 쿼리의 특징이기도 함)

OLTP 환경이라고 Hash Join을 쓰지 못할 이유는 없지만 이 세 가지 기준(①~③)을 만족하는지 체크해 봐야 한다.

[4] Scalar Subquery

• 서브쿼리 중에서 함수처럼 한 레코드당 정확히 하나의 값만을 리턴하는 서브쿼리

(1) Scalar Subquery의 캐싱 효과

• 내부적으로 캐시를 생성하고, 여기에 서브쿼리에 대한 입력 값과 출력 값을 저장한다.
• 쿼리로부터 같은 입력 값이 들어오면 서브쿼리를 실행하는 대신 캐시된 출력 값을 리턴한다.
• 캐시에서 찾지 못할 때만 쿼리를 수행하며, 결과는 버리지 않고 캐시에 저장한다.