Hash Join

by , under Oracle

Execution of Hash Join

Explanation

(1) 개요

JOIN 의 종류는 3가지로 나뉘는데, Sort merge join, Nested loop join, Hash join 이다. 이중 Hash Join (HJ) 은 7.3 부터 사용가능하며 그 주요 기능을 살펴보면
– index 가 여러 level 의 depth 를 가질 때 Sort Merge Join (SMJ) 이나 Nested Loops (NL)보다 좋은 효과를 낸다.
– sort 를 하지 않으므로 SMJ 보다 좋은 성능을 내며, 작은 table 과 큰 table 의 join 시에 유리하다.
– 주의해야 할 것은 hash join 은 equi join 에서만 가능하다는 것이다.
– HJ 은 driving table 에 index 를 필요로 하지 않는다.
– SMJ 나 NL 보다 효율적인데, 이는 SMJ 가 merge 단계에 들어가기 위해 양쪽 table 이 모두 sort 되어야 하기 때문이다. 또 NL은 driving table이 많은 row 의 data 를 갖는 경우 비효율적이서 inner table 을 여러번 probe(탐색)하게 한다. 이에 반해 HJ는 각 table 에 대해 1 번만 pass 한다.

(2) Cost의 비교

편의상 join 되는 sql 문이 다음과 같다고 가정하자.
SELECT S.a, B.a FROM S,B WHERE S.a = B.a
S는 small table 이고, B는 big table 이다.
(* analyze 를 수행하면 CBO 는 이미 S가 out table 이고 B 가 inner table 이며 , S 가 driving table 임을 인식한다. )
NLJ 는 S table 의 모든 row 에 대해 a column 을 B table 의 모든 column 을 match 하기 때문에 rS* rB key 비교가 요구된다.:
Cost(NLJ) 는 Read(S) + [ rS *Read(B) ] 에 비례
또 SMJ 는 S 와 B 를 memory 에 읽어와 join key 를 각각 sort 하고, join 을 수행하므로 cost 는

Cost(SMJ) 는 Read(S) + Write(SortRuns(S))
+ Read(B) + Write(SortRuns(B))
+ Merge(S,B)
+ CPUSortCost(S + B) 에 비례한다.

memory 에서 수행되는 HJ 의 algorithm 은 아래에서 설명된어 지는데 이의 cost 를 미리 check 해 보자면

Cost(HJ) = Read(S) + Build Hash Table in Memory (cpu)
+ Read(B) + Perform In memory Join(cpu)

이 경우 CPU costs를 무시하면, Cost(HJ)는 Read(S) + Read(B) 에 비례한다고 할 수 있다.

(3) Hash join 을 수행하기 위해 Oracle 은 다음의 과정을 거친다.:

이를 수행하기 위해 partition 단계와 join 단계를 거치며 이의 algorithm 을 grace join 이라 한다. 이의 한계는 join value 의 분배가 한쪽으로 치우침이 없이 partition 에 고르게 분포되어야 한다는 것이다. 이 algorithm 은 다음과 같다.

1. partiton 갯수를 결정한다.이를 fan out 이라한다.

high fan out 은 여러개의 작은 partition 을 만들어 i/o 의 효율을 떨어뜨리며,low fan out 은 커다란 partition 을 만들어 hash memory 의 hit율을 떨어뜨린다 . 그러므로 이를 적절히 가져가는 것이 performance 의 주 요점이며(이는 bit map 갯수를 결정) 이의 효율을 높이기 위해 hash area size를 늘리고, hash multi block io 를 줄인다.

2. driving table 을 결정한다.(작은 table 로 결정)

3. small table 의 필요 column 을 읽어들여 hash area 의 partition 에 분배하는데 이는 join column 으로 hash function1을 통과 시키면서 partition 에 hash function2 의 hash value 와 함께 분배한다. 이때 bitmap vector 를 만든다. 이 bitmap 은 2차원 bucket 인데 hash function 1 과 2 를 통과시켜 만든다.즉 partition 이 100 개라면 100* 100 의 10000 개의 cell 로 이루어진다.

4. 각 row 에 대해 bitmap 의 (a,b) 에 marking 을 한다.

5 위의 step 이 모두 끝나면 driving table 이 아닌 큰 table 을 읽어들여 function1,2 를 통과한다. 이때 나온 hash value 를 driving table 이 만들어 놓은 bitmap 과 대조하여 1 이면 join 을 해야 하는 column 으로 인식하고 아니면 join할 필요가 없는 row 이므로 버린다. 이를 bit vector filtering 이라한다. 이때 hash table 을 구성하기 위해 항상 full table 을 scan 하는 것은 아니다. 먼저 where 조건의 index 를 타서 조건에 맞게 row 를 걸러낸 다음 그 결과에 대해 hash table 을 구성한다. 또 hash array size 가 크면 문제가 안되는데, 작으면 disk 의 temp segment 에 내려 보내야 하므로 problem 이 발생한다.

6. B 의 joined value 를 hash function 1 을 통과시켜 이 row 가 bit vector에 있고, memory 위의 partition 에 있으면 join 이 수행되고 결과가 return 된다. memory 에 있지 않으면 disk 에 있는 적절한 S partition 에 씌여진다. 7. 1번째 B 가 pass 된후 S 의 수행되지 않는 partition 들이 최대한 temp segment 에서 memory 로 올려지고 hash table 이 생성된다. 그리고 B 의 partition 이 다시 읽혀져 memory join 이 실행된다. 즉 수행되지 않는 disk 의 partition (S,B) 이 읽혀진다.

(4) parameter

-HASH_JOIN_ENABLED : true 로 지정시 사용가능
-HASH_AREA_SIZE : sort_area_size 의 2배가 기본
-HASH_MULTIBLOCK_IO_COUNT : DB_BLOCK_READ_COUNT 가 기본
-USE_HASH : hint

(5) partition 갯수 결정

첫번째로 우리는 partition (bucket) 의 갯수를 결정해야 한다. 여기에 우리는 hashed row 를 넣을 것이다. 이는 hash_area_size, db_block_size and ash_multiblock_io_count parameters에 의해 결정된다. 또 이 값은 20% 정도의 overhead 를 고려해야 한다.
– storing partitions, the bitmap of unique left input and the hash table

함수 : Partitions 갯수 = (0.8 x hash_area_size) / (db_block_size x hash_multiblock_io_count)

row 가 가장 작은 table 이 읽혀지고 (R 이라고 부르자) , 각 row 는 hash algorithm 을 따른다. 각 row 를 bucket 에 골고루 펼쳐지게 하기 위해 2가지의 algorithm을 따른다. hash 되는 row 가 partition 에 골고루 분산되기 위해 1 번째 hash function 을 따르며, 2 번째 hash value 는 다음 hash 되는 경우를 위해 row 와 함께 저장된다. 이와 동시에 두가지의 hash value 를 이용한 bitmap 이 만들어진다.

(6) Bitmap building 예제 :

Hash
Algorithm 1 ->
1 2 3 4
1 0 0 0 0
Second
Hash 2 0 0 0 0 ------>
Algorithm
| 3 0 0 0 0
V
4 0 0 0 0

driving table 은 hash function 1, 2 를 통과하여 bitmap 을 만든다. 만일 hash area 가 모두 차면 가장 큰 partition 이 disk 로 내려간다. disk 의 partition 은 partition 에 할당되는 row 에 의해 disk 에서 update 되어진다. 만일 hash area 의 부족으로 1 partition 만이 memeory에 올라간다면 나머지 partition 은 모두 disk 에 놓여지게 된다. 이런 경우는 생기지 않도록 조심하여야 한다.
이 작업이 R table 의 모든 row 에 대해 행해진다. 이 작업시 가능한 모든 partition 이 memeory 에 위치하도록 해야 한다.
이 작업이후 B table 을 읽어들인다.이도 역시 hash function 을 통과시켜 hash value 가 memory 에 있는 partition 을 hit 하는지 check 한다.

만일 그러면 이 row 는 joined row 로 반환한다. 만일 아니면 해당 row 를 새로운 partiion 에 write 한다. 이때 S 와 같은 hash function 을 사용하며 이의 의미는 S와 B 의 같은 value는 같은 partition number 를 갖게 하기 위함이다.

(7) unique join keys 의 bitmap

bitmap 은 partition 에 들어있는 value 의 flag 이라 할수 있다. 이는 S 의 row 가 disk 의 partititon 에 씌이기 전에 생성되어 진다.

 

Leave a Reply