Good Site

(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 hash_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 에 씌이기 전에 생성되어 진다.