3-4-3. 해시 조인
과목3. SQL 고급 활용 및 튜닝
제4장 조인 튜닝
제3절 해시 조인
1. 기본 메커니즘
Hash Join은 NL Join이나 Sort Merge Join이 효과적이지 못한 상황을 해결하고자 나온 조인 방식이다. 아래는 Oracle과 SQL Server 각각에서 Hash Join으로 유도했을 때의 실행계획이다.
[예제] Oracle
0
SELECT STATEMENT Optimizer = CHOOSE (Cost = 5 Card = 654 Bytes = 35K)
1
0
HASH JOIN (Cost = 5 Card = 654 Bytes = 35K)
2
1
TABLE ACCESS (FULL) OF 'DEPT' (Cost = 2 Card = 654 Bytes = 14K)
3
1
TABLE ACCESS (FULL) OF 'EMP' (Cost = 2 Card = 327 Bytes = 11K)
[예제] SQL Server
--Hash Match(Inner Join, HASH:([d].[deptno]) =([e].[deptno]))
| --Table Scan(OBJECT:([SQLPRO].[dbo].[dept] AS [d]))
| --Table Scan(OBJECT:([SQLPRO].[dbo].[emp] AS [e]))
Hash Join은 둘 중 작은 집합(Build Input)을 읽어 해시 영역(Hash Area)에 해시 테이블(= 해시 맵)을 생성하고, 반대쪽 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 조인하는 방식이다.([그림 Ⅲ-4-30] 참조)
해시 함수는, 출력값을 미리 알 순 없지만, 같은 입력값에 대해 같은 출력값을 보장하는 함수다. 다른 입력값에 대한 출력값이 같을 수는 있는데, 이를 '해시 충돌'이라고 한다. 해시 테이블을 만들 때 해시 충돌이 발생하면, 입력값이 다른 엔트리가 한 해시 버킷에 담길 수 있다. 이런 원리를 바탕으로 Hash Join 과정을 좀 더 자세히 살펴보자.
1단계 : 해시 테이블 생성두 집합 중 작다고 판단되는 집합을 읽어 해시 테이블을 만든다. 해시 테이블을 만들 때 해시 함수를 사용한다. 해시 테이블은 해시 버킷으로 구성된 배열이라고 생각하면 된다. 해시 함수에서 리턴받은 해시 값이 같은 데이터를 같은 해시 버킷에 체인(연결 리스트)으로 연결한다.
2단계 : Probe Input을 스캔해시 테이블 생성을 위해 선택되지 않은 나머지 데이터 집합(Probe Input)을 스캔한다.
3단계 : 해시 테이블 탐색Probe Input에서 읽은 데이터로 해시 테이블을 탐색할 때도 해시 함수를 사용한다. 즉 해시 함수에서 리턴받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾는다.
Hash Join은, NL Join처럼 조인 과정에서 발생하는 random 액세스 부하가 없고 Sort Merge Join처럼 조인 전에 미리 양쪽 집합을 정렬하는 부담도 없다. 다만, 해시 테이블을 생성하는 비용이 수반된다. 따라서 Build Input이 작을 때라야 효과적이다. 만약 Hash Build를 위해 가용한 메모리 공간을 초과할 정도로 Build Input이 대용량 테이블이면 디스크에 썼다가 다시 읽어 들이는 과정을 거치기 때문에 성능이 많이 저하된다. Build Input으로 선택된 테이블이 작은 것도 중요하지만 해시 키 값으로 사용되는 칼럼에 중복 값이 거의 없을 때라야 효과적이다. 이유는 잠시 후 자세히 설명한다. 해시 테이블을 만드는 단계는 전체범위처리가 불가피하지만, 반대쪽 Probe Input을 스캔하는 단계는 NL Join처럼 부분범위처리가 가능하다는 사실도 기억하자.
2. Build Input이 가용 메모리 공간을 초과할 때 처리 방식
Hash Join은 Hash Build를 위한 가용한 메모리 공간에 담길 정도로 Build Input이 충분히 작아야 효과적이라고 했다. 만약 In-Memory Hash Join이 불가능할 때 DBMS는 'Grace Hash Join'이라고 알려진 조인 알고리즘을 사용하는데, 이는 아래 두 단계로 나누어 진행된다.
1) 파티션 단계
조인되는 양쪽 집합(→ 조인 이외 조건절을 만족하는 레코드) 모두 조인 칼럼에 해시 함수를 적용하고, 반환된 해시 값에 따라 동적으로 파티셔닝을 실시한다. 독립적으로 처리할 수 있는 여러 개의 작은 서브 집합으로 분할함으로써 파티션 짝(pair)을 생성하는 단계다. 파티션 단계에서 양쪽 집합을 모두 읽어 디스크 상의 Temp 공간에 일단 저장해야 하므로 In-Memory Hash Join보다 성능이 크게 떨어지게 된다.
2) 조인 단계
파티션 단계가 완료되면 각 파티션 짝(pair)에 대해 하나씩 조인을 수행한다. 이때, 각각에 대한 Build Input과 Probe Input은 독립적으로 결정된다. 즉 파티션하기 전 어느 쪽이 작은 테이블이었는지에 상관없이 각 파티션 짝(pair)별로 작은 쪽 파티션을 Build Input으로 선택해 해시 테이블을 생성한다. 해시 테이블이 생성되고 나면 반대 쪽 파티션 로우를 하나씩 읽으면서 해시 테이블을 탐색하며, 모든 파티션 짝에 대한 처리가 완료될 때까지 이런 과정을 반복한다. Grace Hash Join은 한마디로, 분할 정복(Divide & Conquer) 방식이라고 말할 수 있다. 실제로는 DBMS 벤더마다 조금씩 변형된 형태의 하이브리드(Hybrid) 방식을 사용하지만 두 개의 큰 테이블을 Hash Join하는 기본 알고리즘은 Grace Hash Join에 바탕을 두고 있다.
Recursive Hash Join(=Nested-loops Hash Join)
디스크에 기록된 파티션 짝(pair)끼리 조인을 수행하려고 '작은 파티션'을 메모리에 로드하는 과정에서 또다시 가용 메모리를 초과하는 경우가 발생할 수 있다. 그럴 때는 추가적인 파티셔닝 단계를 거치게 되는데, 이를 'Recursive Hash Join'이라고 한다.
3. Build Input 해시 키 값에 중복이 많을 때 발생하는 비효율
잘 알다시피 해시 알고리즘의 성능은 해시 충돌(collision)을 얼마나 최소화할 수 있느냐에 달렸으며, 이를 방지하려면 그만큼 많은 해시 버킷을 할당해야만 한다. [그림 Ⅲ-4-30]에는 개념적으로 설명하기 위해 하나의 버킷에 여러 키 값이 달리는 구조로 표현하였지만, DBMS는 가능하면 충분히 많은 개수의 버킷을 할당함으로써 버킷 하나당 하나의 키 값만 갖게 하려고 노력한다. 그런데 해시 버킷을 아무리 많이 할당하더라도 해시 테이블에 저장할 키 칼럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달릴 수 밖에 없다. 그러면 해시 버킷을 아무리 빨리 찾더라도 해시 버킷을 스캔하는 단계에서 많은 시간을 허비하기 때문에 탐색 속도가 현저히 저하된다. Build Input의 해시 키 칼럼에는 중복 값이 (거의) 없어야 Hash Join이 빠르게 수행될 수 있음을 이해할 것이다.
4. Hash Join 사용기준
Hash Join 성능을 좌우하는 두 가지 키 포인트는 다음과 같다.
한 쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야 함
Build Input 해시 키 칼럼에 중복 값이 거의 없어야 함
위 두 가지 조건을 만족할 때라야 Hash Join이 가장 극적인 성능 효과를 낼 수 있음을 앞에서 살펴보았다. 그러면 Hash Join을 언제 사용하는 것이 효과적인지 그 선택 기준을 살펴보자.
조인 칼럼에 적당한 인덱스가 없어 NL Join이 비효율적일 때
조인 칼럼에 인덱스가 있더라도 NL Join 드라이빙 집합에서 Inner 쪽 집합으로의 조인 액세스량이 많아 random 액세스 부하가 심할 때
Sort Merge Join 하기에는 두 테이블이 너무 커 소트 부하가 심할 때
수행빈도가 낮고 조인할 때
앞쪽 세 가지 사항은 앞에서 이미 설명한 내용이므로 생략하기로 하고, 마지막 항목을 강조하면서 Hash Join에 대한 설명을 마치려고 한다. Hash Join이 등장하면서 Sort Merge Join의 인기가 많이 떨어졌다고 했는데, 그만큼 Hash Join이 빠르기 때문이다. Hash Join이 워낙 빠르다 보니 모든 조인을 Hash Join으로 처리하려는 유혹에 빠지기 쉬운데, 이는 매우 위험한 생각이 아닐 수 없다. 수행시간이 짧으면서 수행빈도가 매우 높은 쿼리(→ OLTP성 쿼리의 특징이기도 함)를 Hash Join으로 처리한다면 어떤 일이 발생할까? NL Join에 사용되는 인덱스는 (Drop하지 않는 한) 영구적으로 유지되면서 다양한 쿼리를 위해 공유 및 재사용되는 자료구조다. 반면, 해시 테이블은 단 하나의 쿼리를 위해 생성하고 조인이 끝나면 곧바로 소멸하는 자료구조다. 따라서 수행빈도가 높은 쿼리에 Hash Join을 사용하면 CPU와 메모리 사용률을 크게 증가시킴은 물론, 메모리 자원을 확보하기 위한 각종 래치 경합이 발생해 시스템 동시성을 떨어뜨릴 수 있다. 따라서 Hash Join은 ①수행 빈도가 낮고 ②쿼리 수행 시간이 오래 걸리는 ③대용량 테이블을 조인할 때(→ 배치 프로그램, DW, OLAP성 쿼리의 특징이기도 함) 주로 사용해야 한다. OLTP 환경이라고 Hash Join을 쓰지 못할 이유는 없지만 이 세 가지 기준(①~③)을 만족하는지 체크해 봐야 한다
Last updated
Was this helpful?
