#title Hash Join
[[TableOfContents]]

==== Hash ? ====
예를 들어 고객테이블의 고객번호가 PK라고 가정하자. 만약 고객의 주문이력을 보관한다고 할 경우 주문이력이 너무 많아 이래저래 따져보니 3개의 테이블에 분산저장하는 것이 유리하다는 판단하에 분산저장한다고 생각해보자. 어떻게 분산저장할 것인가? 트랜잭션은 고객단위로 일어난다. 그러므로 Hash 분할을 시도한다. Hash 분할? 개뿔도 아니다. 해쉬함수는 다음과 같이 결정하였다. 

 해쉬함수 = 고객번호 % 3

그러면 우리는 다음과 같은 알고리즘으로 3개의 테이블에 분산저장할 것이다. (해쉬 수평분할의 기본적인 방법이다. 책에 나온것은 아니고 내가 평소에 써먹는 방법이다)
{{{
 if 고객번호%3 = 1 then 
  주문이력1 테이블에 저장
 if 고객번호%3 = 2 then
  주문이력2 테이블에 저장
 else 
  주문이력3 테이블에 저장
}}}
==== Hash Join의 개념 ====
Merge Join은 정렬이 들어가므로 임시 저장공간을 필요로 할 수도 있다. 메모리는 한정되어 있으므로 대부분 Merge Join을 위해 Tempdb의 공간을 필요로 한다. 그러므로 Disk I/O가 발생하여 수행성능이 저하되는 현상을 볼 수[* 볼 수도 있지 성능 저하가 있다는 것은 아니다]도 있다. 이러한 Disk I/O를 줄여보자는 취지에서 Hash Join이 나온 것이다. Hash Join은 비교되는 컬럼에 대해서 메모리에 파티션짝을 생성한다. 파티션짝은 Hash Function의 리턴값으로 결정한다. 함수 연산은 CPU에서 하면 되므로 Disk I/O를 필요로 하지 않으므로 CPU성능이 좋은 시스템의 경우는 많이 유리해 진다. (요즘같이 CPU자원이 풍부하다면 웬만하면 Merge Join보다는 Hash Join이 유리한 경우가 많다)

두 테이블에 대해 파티션짝이 만들어지면 둘 중에 작은 것이 메모리에 Hash Table로 생성된다. 메모리로 올려지지 못한 큰 파티션이 읽혀지면서 메모리에 생성된 Hash Table과 비교를 하게 된다. 이러한 과정을 계속 반복해서 수행한다. 

attachment:hash_join.jpg

Hash Join을 하기 위해서는 메모리의 공간을 필요로 하지만 큰 테이블과 작은 테이블을 비교할 때 연결고리에 인덱스가 없으면 Hash Join이 유리해지는 경우가 많이 있다. 그러므로 아래와 같은 경우처럼 인덱스가 없는 테이블끼리 조인을 하게 되면 대부분 Hash Join으로 풀리게 된다. 

{{{
use pubs
go
 
select * into #employee from employee
select * into #jobs from jobs
 
select *
from #employee a inner join #jobs b
on a.job_id = b.job_id
}}}

attachment:hash_join02.jpg

==== 어떤 경우에 유리한가? ====
Hash Join은 언제 유리할까? 인터넷의 많은 문서에서 Loop Join, Merge Join, Hash Join의 비교를 해 놓은 자료들이 많이 있지만 비교는 그 때의 그 상황에서만을 이야기 한다. Disk는 매우 느린데 CPU가 상대적으로 너무 빠르다면 대부분은 Merge Join보다는 Hash Join이 빠를 것이며, 데이터 액세스의 양이 적고, 인덱스가 잘 설계되어 있는 OLTP라면 Loop Join이 단연 우세일 것이다. 또한 Disk는 매우 빵빵한데 CPU가 허접스러운데 대용량 처리를 한다면 Merge Join이 유리할 확률이 크다. 물론 각 Join방식을 논할 만큼의 가치가 없는 경우도 있다. 즉, 무조건적인 공식은 없다. 다만 일반적으로 큰 크기를 가지는 테이블과 작은 크기의 테이블을 서로 연결할 경우는 Hash Join이 다른 데이터 연결방식에 비해서 빠르다고 이야기 한다. 이것도 상황에 따라서 달라진다. Hash Join의 부분집합으로 볼 수 있는 [Star Join]이 있는데, 이것은 다른 문서에서 살펴볼 것이다. (요즘은 귀찮아서 측정은 안해봤는데.. 대용량 처리에서는 Hash Join이 Merge Join보다 빠른거 같더라..)
==== Hash에 대한 참고 사항들 ====
 * [Hash의 이용]
 * [Hash Match/Cache]
 * [Hash Join]
 * [Star join]

==== 참고자료 ====
 * attachment:LoopJoin/Join_Algorithm.pdf
 * [http://www.sql-server-performance.com/articles/dba/physical_join_operators_hash_p1.aspx Physical Join Operators in SQL Server - Hash Operator]