DATOR

11g Partition Pruning - Bloom Filter 알고리즘

Document URL : http://www.dator.co.kr/msjung/270704
Oracle DB | Posted on March 18th, 2012 at 22:18 by 민수 | 조회수 : 55076

Bloom Filter 알고리즘이란?

 

Oracle 11g 부터 도입된 알고리즘으로,

Partion Pruning 시에 Join 대상을 줄이기 위한 기법으로 사용됩니다.

 

실행 계획 상에

PART JOIN FILTER CREATE ::BF0000

이런 식으로 나오면 Bloom Filter를 이용해서 동작한다고 볼 수 있습니다.

 

 

동작방식

 

- Join 대상 중 한쪽(A)에, 동일한 출력 범위를 갖는 여러 개의 Hash 함수를 적용합니다.

 

예) 0~99 까지의 결과를 내는 서로 다른 Hash 함수 2개

     1번 함수 : mod(대상컬럼, 100)

     2번 함수 : mod(ceil(대상컬럼/3), 100)

 

 

- 각각의 Hash 함수를 적용한 결과 값을 모두 합쳐서 기록합니다.

 

예)

  항목: 1,10,100,1000,10000, ...

   1번 함수 적용 결과 => 1,0,0,0,0,...

   2번 함수 적용 결과 => 1,4,34,34,34,...

 

  기록 -> 0, 1, 4, 34 

  (실제로는 값이 아닌 100개 비트의 1,0 값으로 기록됩니다.)

   012345678..34..99

   110010000...1....0

 

 

- 다른 쪽 Join 대상(B)에, 동일한 Hash 함수들을 적용해서, 매 결과를 A와 비교하고 Join 대상을 줄입니다.

  (실제 비교연산은 Bit 연산으로 수행됩니다.)

 

 각 비트별 비교표

  A B

  1  1 False Positive (Join 대상, 실제 Join에는 실패할 수도 있음)

  1  0 don't care

  0  1 Negative (Join 대상 아님)

  0  0 don't care

 

예)

105에 대한 Hash 함수 결과.

   1번 함수 적용 결과 => 1

   2번 함수 적용 결과 => 35

 

2번 함수 적용 결과가 위(A)에 없으므로 105는 Join 대상이 아닙니다.  - Negative

 

401에 대한 Hash 함수 결과

  1번 함수 적용 결과 => 1

  2번 함수 적용 결과 => 34

 

1과 34 모두 위(A)에 적용 결과가 있으므로, Join 대상이 됩니다.

하지만 401이란 값이 A쪽에 없으므로 연결에는 실패합니다. - False Positive

 

- 적용하는 Hash 함수가 많을수록, Hash 함수의 결과 범위가 넓을 수록(0~99 -> 0~999)

  연결에 실패할 확률은 낮아지나, 수행 속도가 느려질 것입니다.

 

참고. False Positive? Negative?

 

False = Wrong인가? 를 두고 지인들 간에 논란거리가 됐었습니다.

그 논의 결과를 기억하고자 여기에 남겨둡니다.

(틀린 부분이 있다거나 필요할 경우, 내용이 보강될 수 있습니다.)

 

Positive vs Negative

 

원하는 결과 = Positive

나머지 결과 = Negative

 

즉, <Hash 함수를 적용한 결과가 서로같다>라는 걸 원한다면

   B의 401란 값에 대한 결과를 놓고 보면 Positive 가 되고,

   B의 105란 값에 대한 결과를 보면 Negative 가 됩니다.

 

아니면, <Join 대상이냐 아니냐>라는 걸 원한다면

   B의 401과 105 모두 Negative 가 됩니다.

 

그럼 False Positive는 뭘까요?

False = Wrong 이면, Wrong but positive 로 해석됩니다.

 

즉, 실제로 잘못된 결과인지 확인한 뒤,

최종 단계까지 가야 False Positive란 해석을 붙일 수가 있게 됩니다.

 

하지만, 이렇게 되면, Negative와 다를게 없게 되는데요.

실제는 Wrong 이란 뜻으로 사용되는 용어가 아니라고 합니다.

 

False Positive vs True Positive

 

다음과 같은 코드가 있다고 할 때

if ( B의 항목이 A에 있는가?)  {

    Positive => Join 대상이다.

}

else  {

    Negative => Join 대상이 아니다.

}

 

Bloom Filter 알고리즘을 적용하면 아래처럼 바뀝니다.

if ( B의 hash 함수 결과가 A에도 있는가?) {

   // 여기가 False Positive 단계라고 합니다.

   // 여기까지 오면 실제로 Positive는 아니지만 Positive일 가능성이 상당히 높아지며,

   // 즉 False = Maybe란 해석이 됩니다.

    if ( B의 항목이 A에 있는가?)   {

        Positive  => Join 대상이다.

    }

    else  {

        Negative  => Join 대상이 아니다.

    }

}

else {

    Negative => Join 대상이 아니다.

}

 

그래서 얻어진 결론은.

False Positive = Maybe Positve

False Negative = Maybe Negative

 

Thx To Our Sunday.

Tagged :
 

Comments : 1

Author Oracler
2012.03.28 at 18:05:02
댓글 | |

하이~~

늦게 찾아봐서 미안허이~~

잘 정리했군~~


중간의 각 비트별 비교표에서 false positive를 이왕 썼다면 나머지 don't care와 negative는 true negative라고 해야 확실한 비교가 될 것으로 생각된다는 의견을 쓰고 싶었소..^^


그리고 maybe라고 했었지만 다시 읽다 보니 could be가 좀 더 정확인 뜻이 아닐까 싶다.