2.3.4. 해쉬(Hash) 조인

해쉬 조인은 대용량 처리의 선결 조건인 램덤과 정렬에 대한 부담을 해결할 수 있는 대안으로서 등장하게 되었다.
우리의 요구는 바로 랜덤 액세스에 비해 현저하게 건당 연결비용이 적어야 하며,
데이터 량의 증가에 대해 극단적인 상승곡선이 나타나지 않아야 한다는 것으로 집약될 수 있겠다.
해쉬함수란 데이터의 컬럼에 있는 상수값을 입력으로 받아 '위치값'을 리턴하는 것을
해쉬함수라고 이해하면 된다.

중요 용어 정리
해쉬 영역(Hash Area)
해쉬 조인을 수행하기 위해 메모리 내에 만들어진 영역을 말한다.
이 영역은 비트맵 벡터와 해쉬 테이블, 그리고 파티션 테이블 영역으로 구성된다.
비트맵 벡터는 먼저 액세스 하는 빌드입력의 유일한 값을 생성해 두었다가
나중에 검색하는 검색입력을 필터링하는데 사용한다.
해쉬 테이블에는 파티션들의 위치정보(Address)를 가지고 있으며 조인의 연결 작업을
수행할 때나 디스크에 내려가 있는 파티션 짝들을 찾는데 사용된다.
파티션 테이블에는 여러 개의 파티션이 존재하여, 조인할 집합의 실제 로우들을 가지고 있는 영역이다.

파티션(Partition)
파티션이란 파티션을 결정하기 위해 수행하는 첫 번째 해쉬함수가 리턴하는 동일한 해쉬값을 갖는 묶음을 말한다. 즉, 동일한 해쉬값을 가지 로우들의 버켓(Bucket)을 말한다. 특히 빌드입력이 인-메모리에서 작업이 불가능하면
반드시 파티션으로 나뉘어져야 한다. 이렇게 만들어진 파티션 수를 팬아웃(Fan-out) 이라고 부른다.
하나의 파티션은 여러 개의 클러스터로 분리된다. 2차 해슁을 하면 저장할 클러스터의
위치가 결정되며, 이 단위는 I/O의 단위가 될 뿐만 아니라 검색의 단위로로 활용된다.

클러스터(Cluster)
파티션은 작지 않은 크기로 되어 있기 때문에 이를 다시 클러스터(Cluster)단위로 분할한다. 이 클러스터는 연속된 블록으로 되어 있으며 디스크와 I/O를 하는 단위가 된다.클러스터를 슬롯(Slot) 이라고도 부르며, 마치 캐비닛을 파티션이라고 한다면 슬롯은 서랍이라고 생각하면 이해가 빠를 것이다.

빌드입력(Build Input)과 검색입력(Probe Input)
조인을 위해 먼저 액세스하여 필요한 준비를 해두는 처리를 빌드입력이라 하며,
나중에 액세스하면서 조인을 수행하는 처리를 검증 혹은 검색입력이라고 한다.
파티션이란 조인 연결고리에 대해 동일한 해쉬값을 갖는 묶음이라고 정의 할 수 있다.
동일한 파티션에 위치하게 된다는 것은 나중에 구체적인 연결을 하는 연결처리 단위가
된다는 것을 의미 한다.

인-메모리(In-Memory)해쉬조인과 유예 해쉬조인
해쉬 조인에서는 전체 빌드입력이 해쉬영역(Hash_area_size)보다 적은 경우와 그렇지 않은 경우에 따라
처리 방식에 큰 차이가 있다.
빌드입력이 해쉬영역에 모두 위치할 수 있는 경우는 인-메모리(In-Memory) 해쉬조인을
수행하게 되고, 그렇지 못한 경우에는 유예 해쉬조인을 수행하게 된다.
유예 해쉬 조인은 먼저 전체를 빌드입력과 검색입력을 수행하여 여러 개의 파티션에
분할하고, 해쉬영역을 초과할 때마다 임시 세그먼트(Temporary segment)에 파티션을
저장한다. 해쉬 함수를 이용하여 파티션 하게 되면 각 조인 대상이 동일한 파티션에
위치하는 것이 보장되므로 각 파티션 별로 다시 빌드입력과 검색입력이 동적으로
결정되어 보다 효율적인 연결작업을 수행하게 된다.

비트맵 벡터(Bitmap Vector)
이것은 빌드입력에 대해 파티션을 구하는 작업 중에 생성되며, 빌드 입력값들에 대한
유일한 값(Unique Column Value)을 메모리 내에 해쉬영역에 정의하는 것을 말한다.
이 값들은 장자 검색입력의 파티션 생성 작업 시에 필터링(Filtering)을 하는데 사용한다.

해쉬영역에 만들어지는 비트맵 백터는 빌드입력의 전체 집합에 대해서 생성된다.
즉, 처리대상이 커서 해쉬영역을 초과하여 임시 세그먼트에 저장하게 되더라도 처리할
빌드입력의 모든 집합에 대해 조인 종료 시까지 유지된다.

검색입력에서 엑세스한 것이 어차피 빌드입력에 존재하지 않는다면 굳이 파티션에
위치시킬 필요조차 없기 때문에 이를 필터링 하는 중요한 역할을 하게 된다.
일반적으로 이 영역은 메모리에 정의하는 해쉬영역의 5%로 생성된다.

해쉬 테이블(Hash Table)
이 테이블은 메모리 내에 만들어지며, 최종적으로 조인에서 조인의 연결작업에서 대응되는
로우를 찾기 위한 해쉬 인덱스로 사용된다.
데이터가 각 파티션에 해쉬 클러스터 개념으로 저정되어 있으므로 연결작업을 시도할 때
검색입력에 있는 연결고리 값으로 해쉬키 값을 찾고, 거기에 있는 클러스터 주소를 이용해
해당 클러스터를 찾아 스캔하면서 연결을 수행한다.

파티션 테이블(Partition Table)
만약 빌드입력이 메모리 크기를 초과하여 파티션을 생성하게 되면 '파티션 테이블'
에 관련정보가 저장된다. 또한 디스크의 임시 세그먼트로 이동하면 그 위치정보를
갖는다. 이 위치 정보는 나중에 다시 메모리로 올려서 처리할 대상을 선정할 때
활용된다. 또한 빌드입력과 검색입력에서 생성된 파티션 간에 서로 짝(Pair)을 찾는데도
활용된다.

같은 묶음으로 처리되는 단위마다 파티션들의 크기의 합이 적은 집합을 빌드입력으로
적용하고, 나머지는 검색입력의 역할을 맡게 된다.

비트맵 벡터나 파티션 테이블은 설사 처리량이 인-메모리를 초과하더라도 전체집합에
대한 정보를 가지고 있지만, 해쉬 테이블은 해당 처리단위의 빌드 입력에 대해서만
정보를 가지고 있다는 것에 차이가 있다.

2.3.4.1 인-메모리 해쉬조인

[VLDB: 그림 2-2-21 ]

1) 통계정보를 참조하여 보다 효과적인 카디널리티를 갖는 집합을 빌드입력으로 선택한다.
일반적으로 조인은 1:1 이나 1:M 관계에서 발생하므로 대부분의 경우 '1'쪽 집합이 빌드입력이 된다.
2) 팬아웃, 즉 파타션 수를 결정한다. 파티션의 수와 크기는 성능에 큰 영향을 미치게
되므로 히스토그램 정보에 입락하여 이를 동적으로 최적화하여 결정하게 된다.
3) 빌드입력의 조인키에 대하여 1차 해슁함수를 적용하여 저장할 파티션을 결정한다.
4) 2차 해슁함수를 적용하여 해쉬값(Hash Value)을 생성한다.
5) 이 값을 이용하여 해쉬 테이블을 만들고, 해당 파티션의 슬롯(Slot)에 저장한다.
이때 저장되는 컬럼은 SQL 의 SELECT-List 에 있는 컬럼들도 같이 저장된다.
즉, 쿼리를 위해 사용될 컬럼들만 저장된다.
6) 검색입력의 필터링을 위해 사용할 비트맵 백터를 생성한다. 이 값을 유일한 값으로
만들어지므로 처리할 값을 찾아본 후 없으면 생성하고 있으면 그대로 통과 하는 방식으로 생성된다.
7) 이러한 방식으로 빌드입력의 처리범위를 모두 처리할 때까지 반복해서 수행한다.
8) 이번에는 검색입력의 처리범위를 액세스하기 시작하여 조건을 만족하지 않으면 버리고 그렇지 않으면
다음을 실행한다.
9) 첫 번째 해슁함수를 적용하여 비트맵 벡터를 필터링 한다.
물론 여기에서 찾을 수 없다면 해당 처리는 종료되고 다음 검색입력 대상으로 넘어간다.
10) 필터링을 통과한 것은 2차 해슁함수를 적용하여 해쉬 테이블을 일고 해당 파티션을
찾아 슬롯(클러스터)에서 대응 로우를 찾는다.
11) 조인이 되면 SELECT-List 에 기술된 로우를 완성하여 운반단위에 태운다.
12) 이러한 작업을 반복해서 수행하여 계속 운반단위를 보낸다.
13) 정해진 운반단위가 채워지면 리턴한다. 여기서 알 수 있듯이 비록 빌드입력은
전체범위를 모두 처리했지만 검색입력은 운반단위가 채워지면 먼저 리턴을 할 수
있으므로 부분적으로나마 부분범위 처리가 가능해진다. 그러나, 실제로는 일반적으로
빌드입력은 크지 않으므로 거의 Nested Loops 조인과 유사한 부분범위 처리가 가능하다고 할 수 있다.
14) 이러한 방식으로 검색입력의 처리범위가 끝날 때까지 반복해서 수행한다.

인-메모리 해쉬조인의 특징과 적용기준

• 기존에 미리 생성되어 있는 인덱스를 전혀 사용하지 않는다.
• 부분범위 처리가 가능하다

2.3.4.2 유예 해쉬조인

빌드입력이 해쉬영역을 초과하면 해쉬조인은 좀더 복잡합 과장을 거치게 된다.그 이유는 빌드입력이 해쉬영역을
초과하게 되면 어쩔 수 없이 디스크에 저장을 할 수 밖에 없기 때문이다.
이처럼 빌드입력의 일부라도 디스크에 저장을 할 수 밖에 없게 된다면 마치 정렬을
통해 연결을 하는 Sort Merge 조인처럼 무엇인가 정렬과 유사한 효과를 얻을 수 있는
방법이 있어야 한다. 정렬을 하지 않고서도 연결이 가능하도록 데이터를 위치시키는
방법은 바로 해슁함수를 적용하는 것이다.
Sort Merge 조인은 각각의 집합을 먼저 정렬을 한 후 그것을 머지하는 방식으로 연결을
수행한다. 해쉬조인은 각각의 집합에 대해 먼저 해슁함수를 적용하여 같은 해쉬값을
갖는 파티션에 저장을 한 후 그들의 짝을 찾아 연결을 수행한다.

[VLDB: 그림 2-2-22 ]
1) 통계정보를 참조하여 보다 효과적인 카디널러티를 갖는 집합을 빌드입력으로 선택한다.
2) 파티션 수를 결정한다.
3) 빌드입력의 조인키에 대하여 1차 해슁함수를 적용하여 저장할 파티션을 결정한다.
4) 2차 해슁함수를 적용하여 해쉬값(Hash Value)을 생성한다.
5) 이 값을 이용하여 해쉬 테이블을 만들고, 해당 파티션의 슬롯(Slot)에 저장한다.
이때 저장되는 컬럼은 SQL의 SELECT-List 에 있는 컬럼들도 같이 저정된다.
6) 검색입력의 필터링을 위해 사용할 비트맵 백터를 생성한다. 여기서 생서된 값을
이용해 다음에 검색입력의 필터링을 하게 되므로 유예 해쉬조인에서도 크기가 작은
집합이 빌드입력이 되는 것이 조인할 대상을 보다 효과적으로 줄일 수 있다.
여기까지는 인-메모리 해쉬조인과 거의 동일하다.
7) 이러한 방식으로 빌드입력의 처리범위를 처리하다가 해쉬영역을 초과하면
파티션 테이블에 위치정보를 남기고 디스크로 이동하게 된다. 파티션 테이블에 있는
정보는 나중에 파티션 짝을 찾아 연결작업을 수행할 때 사용된다.
8) 빌드입력의 모든 처리범위가 위의 방법으로 끝까지 수행한다.
9) 이번에는 검색입력의 처리범위를 액세스 하기 시작하여 조건을 만족하지 않으면
버리고, 만족한 것을은 1차 해슁함수를 적용하여 비트맵 벡터를 필터링 한다.
비트맵 벡터에서 찾을 수 없다면 해당 건의 처리는 종료되고 다음 검색입력 대상으로 넘어간다.
10) 필터링에 통과한 것은 2차 해슁함수를 적용한다. 만약 이때 검색입력에 대응되는
빌드입력이 메모리 내에 존재하면 해쉬 테이블을 읽어 연결을 수행하고, 그렇지
않으면 해당 파티션에 저장한다.
11) 연결을 수행할 수 없는 파티션들을 디스크에 저장한다.
12) 이러한 작업을 검색입력의 모든 처리범위에 대해 반복해서 수행한다.
13) 처리되지 않은 파티션들을 처리하기 위해 파티션 테이블의 정보를 이용하여
파티션 짝들을 디스크에서 메모리로 이동시킨다.
14) 새로 메모리에 이동한 집합 중에서 크기가 작은 직합으로 해쉬 테이블을 생성한다.
즉, 처리할 파티션 짝들을 모았을 때, 그 크기에 따라서 빌드입려과 검색입력을
다시 결정된다. 그러므로 경우에 따라서 최초에 결정되었던 빌드입력과 검색입력의 역할이 바뀔 수가 있다.
15) 검색입력으로 결정된 집합을 스캔하면서 해쉬 테이블을 이용하여 연결을 수행한다.
물론 운반단위에 모았다가 채워지면 리턴하는 것은 당연하다. 이러한 작업을 남아 있는 모든 대상에 실시한다.

유예 해쉬조인의 특징과 적용기준

• 인-메모리 해쉬조인과 마찬가지로 기존에 미리 생성되어 있는 인덱스를 전혀 사용하지 않는다.
• 인-메모리 해쉬조인과 달리 부분범위 처리가 불가능하게 된다.

문서에 대하여

• 이 문서는 오라클클럽 대용량 데이터베이스 스터디 모임에서 작성하였습니다.
• {*}이 문서의 내용은 이화식님의 새로쓴 대용량 데이터베이스 솔루션을 참고했습니다.*
• 이 문서를 다른 블로그나 홈페이지에 게재할 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^\^