해시 조인

해시 조인(hash join)은 조인 알고리즘의 한 예로써, 관계형 데이터베이스 관리 시스템의 구현에서 사용된다.

조인 알고리즘의 일은 해당 값을 갖고 있는 각각의 관계 튜플들의 집합으로부터 각각의 구별 가능한 조인 속성 값을 찾는 것이다.

해시 조인은 동일 조인의 결합 서술문을 필요로 한다 (한 테이블의 값을 다른 테이블의 값과 일치 연산자 '='를 이용해 비교하는 서술어)

클래식 해시 조인(Classic hash join)

클래식 해시 조인 알고리즘은 다음과 같이 진행되는 두 관계에 대한 내부조인을 위한 것이다.

먼저 작은 관계를 위한 해시 테이블을 준비한다. 해시 테이블 엔트리들은 조인 속성과 그 로우 전체로 구성되어있다. 왜냐하면 해시 테이블은 제공된 해시 함수를 통해 조인 속성에 접근 할 수 있고, 그것은 주어진 조인속성들의 로우들을 찾는데에 있어 해시테이블을 사용하는 것이 평범하게 오리지널 관계를 찾는것에 비해 훨씬 빠른 속도가 되도록 해 준다.
한번 해시 테이블이 만들어지면, 더 큰 사이즈의 관계들을 스캔하고 해시 테이블을 바탕으로 작은 사이즈의 관계들로부터 관련있는 로우들을 찾아낸다.

첫 번째 단계를 대개 '"빌드" 페이즈'라고 부르며, 두 번째 단계를 '"탐색" 페이즈'라고 부른다. 비슷하게, 조인 관계 중에 해시 테이블을 만드는 것을 "빌드" 인풋이라고 하고, 그에 반해 다른 인풋을 "탐색" 인풋이라고 부른다. 이것은 합병 조인과 비슷하다.

이 알고리즘은 간단하지만, 작은 조인 관계보다 메모리가 더 적을 때를 위한 과정(자주 일어나지는 않지만)이 필요하다. 해당 상황을 핸들링하기 위한 진행방식은 다음과 같다.

빌드 인풋 $R$ 내의 각 튜플 $r$ 에 대하여
1. $r$ 을 메모리 내의 해시 테이블에 추가한다.
2. 만약 해시 테이블의 사이즈가 메모리의 크기 한계와 같다면
  1. 탐색 인풋 $S$ 를 스캔하고, 매칭된 조인 튜플들을 아웃풋 관계에 추가한다.
  2. 해시 테이블을 리셋한다
탐색 인풋 $S$ 에 대해 최종 스캔을 진행하고 남은 나머지 조인 튜플들을 아웃풋 관계에 추가한다.

해당 과정은 거의 블록 중첩 루프 조인 알고리즘과 흡사하다. 이 알고리즘은 $S$ 만큼의 스캔을 더 필요로 한다.

그레이스 해시 조인(Grace hash join)

"그레이스 해시조인"은 GRACE 데이터베이스 머신에 처음 구현된 뒤에 더 나은 방법으로 알려졌다. 이 알고리즘은 $S$ 관계 전체를 다시 스캔하는 과정을 해시 함수를 이용한 $R$ 와 $S$ 양쪽의 첫 파티셔닝 단계로 회피하고, 이러한 파티션 조각들을 디스크에 기록한다. 알고리즘은 그러면 파티션 조각들의 짝을 메모리에 로드하고, 조각난 작은 관계를 위한 해시테이블을 생성하고, 현재 해시 테이블과 매치되는 다른 관계를 탐색한다. 왜냐하면 파티션 조각들은 조인 키에 대한 해싱으로 구성되었으며, 이것들은 반드시 같은 파티션 조각에 알맞은 조인 결과를 만들어 내기 때문이다. 이것은 하나 혹은 그 이상의 파티션 조각들이 아직 사용 가능한 메모리 공간에 적절히 들어가지 않았기 때문에 가능한 것으로, 알고리즘은 추가적인 해시 함수는 커다란 파티션 조각을 부분 파티션 조각으로 해시할 수 있는 것으로 전과 동일하게 행동할 수 있도록 선택되며 재귀적으로 적용된다. 이 과정에서 부하가 많기 때문에, 알고리즘은 해당 상황이 자주 일어나지 않도록 파티셔닝 단계의 초기부터 가능한한 많은 파티션 조각들을 만들 수 있도록 유도하게 된다.

하이브리드 해시 조인(Hybrid hash join)

하이브리드 해시 조인 알고리즘^[1]은 그레이스 해시 조인이 좀 더 메모리를 잘 사용할 수 있도록 개선하기 위해 강화된 알고리즘이다. 파티셔닝 단계 동안, 하이브리드 해시 조인은 다음과 같은 두 가지 방법으로 추가 메모리를 사용한다

각 $k$ 파티션들의 현재 결과에 대한 버퍼용 페이지를 저장하는 용도
"파티션 0"이라고 불리는 모든 파티션들에 대한 정보를 메모리 상에 저장하는 용도

파티션 0은 디스크로부터 읽거나 쓰여지지 않기 때문에, 하이브리드 해시조인은 일반적으로 그레이스 해시조인에 비해 적은 디스크 I/O 실행횟수를 보이게 된다. 참고로, 이 알고리즘은 메모리 상태에 민감한 알고리즘이다. 왜냐하면 두 개의 경쟁적인 메모리 사용 요구(파티션 0을 위한 해시 테이블용과 남은 파티션 조각들의 결과를 저장하기 위한 용도)가 있기 때문이다. 너무 큰 크기의 해시 테이블을 고르는 것으로 알고리즘이 재귀할 수 있는데, 이는 파티션 0이 아닌 파티션 조각 중 하나가 메모리에 들어가기에 너무 큰 사이즈로 만들어질 수도 있기 때문이다.

해시 안티-조인(Hash anti-join)

해시 조인은 안티-조인의 술어부에 대해서도 유용하게 사용된다(술어부는 한 테이블로부터 다른 출력값과 관계가 없는 값들을 찾아내는 용도로 사용하는 값이다). 테이블의 크기에 따라서, 다른 알고리즘이 적용될 수 있다

해시 LEFT 안티-조인(Hash left anti-join)

조인 쪽 결과에 "NOT IN"을 위한 해시 테이블을 준비한다.
다른 테이블을 스캔하고, 조인 특성의 해시 값이 해시 테이블의 빈 칸에 들어가는 어떤 로우들을 선택한다.

이것은 "NOT IN"의 테이블이 조인하려는 테이블보다 더 작을 때 좀 더 유용하다.

해시 RIGHT 안티-조인(Hash right anti-join)

조인하려는 쪽의 테이블로부터 해시 테이블을 준비한다.
조인에 "NOT IN"의 테이블을 스캔하고, 해시 테이블의 해당하는 해시와 일치한 로우들을 해시 테이블로부터 제거한다.
해시 테이블의 왼쪽에 있는 모든 값을 리턴한다.

이 과정은 "NOT IN"의 테이블이 조인하려는 쪽의 테이블보다 더 클 때 좀 더 유용하다.

해시 세미-조인(Hash semi-join)

해시 세미-조인은 다른 테이블에서 찾은 로우들을 반환하는데 사용한다. 순수한 조인이 아니라면, 해시 세미-조인은 "IN"테이블에 얼마나 많은 매칭이 있었는지에 관계없이 리딩 테이블로부터 단 한 번의 매칭된 로우를 반환하게 된다. 해시 안티-조인처럼, 해시 세미-조인 역시 LEFT와 RIGHT 두 가지 방법으로 가능하다.

해시 LEFT 세미-조인(Hash left semi-join)

조인의 "IN"쪽에 들어갈 해시 테이블을 준비한다
다른 테이블을 스캔하고, 해시와 일치하는 어떤 로우들을 전부 반환한다.

로우들은 해시와 일치한 직후에 반환될 것이다. 해시 테이블로부터의 로우들은 무시된다. 이 알고리즘은 "IN"에 해당하는 테이블이 조인을 하려는 테이블보다 작을 때 좀 더 효율적이다.

해시 RIGHT 세미-조인(Hash right semi-join)

조인을 하려는 쪽의 테이블로부터 해시 테이블을 준비한다.
"IN"에 해당하는 테이블을 스캔하고, 해시 테이블로부터 해당하는 로우들을 반환한 뒤, 그것들을 조인 결과에서 제거한다.

이 알고리즘으로는 해시 테이블(조인하려는 테이블로부터 만들어진)의 각 로우가 반환하고 제거되는 것으로 인해 오직 한 번만 반환될 것이다. 이 알고리즘은 "IN"에 해당하는 테이블이 조인하려는 테이블보다 더 클 때 좀 더 효율적이다.

같이 보기

중첩 루프 조인

참조

↑ DeWitt, D.J.; Katz, R.; Olken, F.; Shapiro, L.; Stonebraker, M.; Wood, D. (June 1984). “Implementation techniques for main memory database systems”. 《Proc. ACM SIGMOD Conf》 14 (4): 1–8. doi:10.1145/971697.602261.

외부 링크

Hansjörg Zeller; Jim Gray (1990). “An Adaptive Hash Join Algorithm for Multiuser Environments” (PDF). 《Proceedings of the 16th VLDB conference》 (Brisbane): 186–197. 2012년 3월 11일에 원본 문서 (PDF)에서 보존된 문서. 2008년 9월 21일에 확인함.

[1] DeWitt, D.J.; Katz, R.; Olken, F.; Shapiro, L.; Stonebraker, M.; Wood, D. (June 1984). “Implementation techniques for main memory database systems”. 《Proc. ACM SIGMOD Conf》 14 (4): 1–8. doi:10.1145/971697.602261.

[1]