[SQL Join 시리즈2] 데이터베이스 Hash Join

SQL 에는 크게 3가지 조인 방식이 있다.

 

 

1. nested loop join

2. hash join

3. merge join

 

 

이번에는 그 중에서 Hash Join에 대해 살펴볼 것이다.

먼저 아래 Hash Join 사진을 보고 이해해보자

 

relation r과 s에 대해 hash함수를 적용해서 각 tuple들을 파티션으로 나눈다.

그렇게 되면, 단지 r relation의 i번째 파티션은 s relation의 i번째 파티션과 비교하면 된다.

그 이유는 조금만 생각해보면 알 수 있는데, r tuple과 s tuple 의 값이 같아야만 join이 가능할 것이기 때문이다.

(여기서 Hash Join은 equi join과 natural join일 때만 적용이 가능하다는 것을 알 수 있다!)

 

 

그럼 이제, r과 s의 파티션들을 비교하는 과정에 대해 살펴보자

먼저 s의 i번째 파티션을 메모리에 올리고 hash index를 생성한다.

그 다음 r의 i번째 파티션의 튜플들을 하나씩 읽어, 이 튜플이 (s의 i번째 파티션을 이용해서 만든) hash index를 사용하여 같은 값을 가지는지 비교한다.

같은 값을 가지면 해당 값들이 출력값이다.

 

 

여기서 relation s를 build input, relation r을 probe input이라고 한다.

(그 이유는 build는 미리 인덱스를 build해서 메모리에 올리기 때문에 build input,

probe(조사하다라는 뜻)는 relation r의 튜플들을 하나씩 조사하기 때문에 probe input이라고 한다)

 

 

Q. 그럼 hash index를 생성하는 해시 함수와 파티션을 만들기 위한 해시함수는 같아야할까? 달라야할까?

 

 

답은 당연히 달라야 한다.

왜냐하면, 만약에 같은 해시함수를 쓴다면, 같은 파티션에 있는 튜플들은 이미 다 같은 해시값을 가질 것이기 때문에 hash index의 해시함수의 결과값도 다 같을 것이다.

 

 

(Hash Index에 대해 알고 싶다면 아래 게시글을 참고하자)

https://durumiss.tistory.com/36

[인덱스 시리즈1] 데이터베이스 Hash Index(해시 인덱스)

---

Overflow가 발생한다면?

만약 join하는 attribute가 여러 개이거나, 해시함수가 별로여서 특정 파티션에만 값이 너무 많이 들어가있으면 overflow가 발생할 수 있다!

 

 

그럼 파티션 하나를 메모리에 올리기 힘들다.

따라서 미리 hash index를 만드는 build 과정에서 overflow가 발생하지 않도록 다른 해시함수를 쓰던가 해서 피해야한다.

 

 

그래도 overflow가 발생한다면? block nested join을 써야한다.

(Block nested join에 대해 알고 싶다면 아래 게시글을 참고하자)

https://durumiss.tistory.com/46

[SQL Join 시리즈1] 데이터베이스 nested loop join

 

---

Cost를 계산해보자

(참고로, SQL 쿼리 성능에서 block transfers 비용이 매우 크기 때문에 여기서는 block transfer 비용으로 비교한다)

 

 

결론부터 말하면, hash join의 cost는 3(br+bs) block transfers이다.

(br, bs는 relation r과 s의 block의 개수이다.)

 

 

여기서 2(br+bs)는 각 relation 전체를 읽는 cost과 partition들로 쓰는 cost이다.

build input과 probe input으로 비교하는 과정은 약 br+bs이다.

따라서 2(br+bs) + br+ bs = 3(br+bs)이다.

 

 

 

하지만 만약에, build input이 전체 main memory에 올라간다면 파티셔닝이 필요없기 때문에 비용은 br+bs이다.

 

 

한번 실제 예시로 생각해보자

 

 

memory에는 20 block이 들어갈 수 있다고 가정하고

depositor relation의 block 개수는 100,

customer relation의 block 개수는 400이라고 가정하자

 

 

결과적으로 cost는 3(100+400) = 1500 block transfers 이다.

 

 

하지만, 여기서 주의해야 할 것이 있다.

 

 

depositor를 build input으로 한다고 가정하고 파티션의 개수를 계산해보면,

100 / 20 = 5, 따라서 파티션의 개수는 5개다.

하지만 만약, 파티션의 개수 n이 메모리의 page frame의 개수(block의 개수)보다 크다면?

cost 계산은 위와 같은 과정으로 되지 않을 것이다.

이럴 때에는 recursive partitioning을 통해서 해야한다.

 

 

마지막으로, hash join을 PostgreSQL 15, MySQL 8.0, Oracle 19c에서 모두 지원하고 있다.

 

 

더 알고 싶다면 아래 글을 참고하자!

https://durumiss.tistory.com/30

MySQL, Oracle, PostreSQL 비교 분석하기

 

 

MySQL에서는 Hash join을 BNL과 NO_BNL(아마 block nested loop join의 약자인 것 같다(?)) hint를 사용해서 제어할 수 있다. 

더 자세한 내용을 아래 MySQL 공식 문서를 참고하자.

https://dev.mysql.com/doc/refman/8.0/en/hash-joins.html

MySQL :: MySQL 8.0 Reference Manual :: 8.2.1.4 Hash Join Optimization

 

 

 

참고 :

Database System Concepts 7th edition