행위

블룸필터 BLOOM FILTER

DB CAFE

Dbcafe (토론 | 기여)님의 2024년 3월 20일 (수) 23:16 판 (→‎Bloom Filter 모니터링 - V$SQL_JOIN_FILTER)
thumb_up 추천메뉴 바로가기

1 BLOOM FILTER의 이해와 활용방법[편집]

1.1 개요[편집]

  1. 구성요소가 집합의 구성원인지 점검하는데 사용되는 확률적 자료 구조
  2. 두 집합의 원소가 한쪽은 적고 한쪽은 많을때 , 조인하여 일치하는 교집합의 수는 적을 경우 탁월한 성능을 보인다 .
  3. 대용량 데이터를 조인 할 때 조인하는 대상을 미리 필터하여 줄여주는 효과
  4. Parallel Join 시 , Hash Join ,Merge Join 시 발생함
  5. Join Filter Pruning 이나 Result Cache를 지원 하는데도 활용 됨
  6. 엑사데이터(EXADATA)에서 Bloom Filter 가 offloading 으로 처리 하도록 함으로써 , 데이터베이스 부하를 감소하는 중요한 요소.

1.2 Bloom Filter 의 동작원리[편집]

  1. 해시 테이블이 20개 있다고 가정
  2. 두 개의 단어 ['apple', 'banana']를 해시 함수를 적용해서 테이블에 적용.
  3.  해시 함수는 1개 이상 적용할 수가 있다. 즉, 해시 테이블에 masking을 1개 이상 할 수 있다는 의미.
  4. 해시 함수를 2개를 적용해 보도록 하자. apple을 해시 함수 1에 통과 시켰을 때, 17을 리턴한다면 해시 테이블 17번째에 1을 masking 함
  5. apple을 해시 함수 2에 통과 시켰을 때, 3을 리턴한다면 해시 테이블 3번째에 1을 masking 함.


이런 식으로 banana에도 같이 masking을 해 준다. banana는 3, 15에 각각 1이 masking 되었다고 가정하자.


이제 단어를 찾아보자.apple을 입력하니 해시 함수 1에서 3,17을 각각 리턴해줬고, 해당 결과가 해시 테이블에 존재한다면(masking이 1), apple이란 단어는 목표 값에 존재한다고 생각할 수가 있다. 만약에 orange를 입력하고 결과 값 3, 13을 리턴받았다면, 3은 1이지만 13은 0이기 때문에 존재 안 함으로 판단할 수가 있다. 이런 식으로 처리를 함으로써 20개 이상의 많은 단어가 유입 된다고 하더라고 해시 테이블 20개만 써서 20개 이상의 단어에 대한 존재 유무를 판단 할 수가 있다. 물론 20개 테이블 전부 masking이 1이 된다거나 했을 경우에는 정상적인 동작을 한다고 판단 되지는 않을 것이다. 즉, 모든 해시 테이블이 masking 1이 되지 않도록, 또한 해시 충돌을 최소한으로 줄일 수 있도록 해시 테이블 크기와 해시 함수 개수 등의 적절한 조합이 필요하다. bloomFilter 같은 경우에는 false positive 요소는 있을 수 있으나, (해당 단어가 없는데 있다고 판단한 경우) false negative는 확실히 걸러낸다. (해당 단어가 있는데 없다고 판단한 경우) 해시 값 충돌이나 masking이 일치하는 경우 없는 단어도 있다고 판단할 수 있겠으나, 있는 단어인 경우는 확실히 매칭시키기 때문에 bloom Filter를 통해 한번 거르게 되면 많은 양의 데이터를 줄일 수가 있다.


  1. Bloom Filter 은 m비트 크기의 비트배열 구조와 , 서로 다른 K가지의 Hash 함수를 사용 하여 구현

. 여기서 각 Hash 함수는 m 가지의 값을 균등한 확률로 출력해야만 한다 .

이해 를 돕기 위해 예를 하나 들어 보도록 하겠다 .

  1. 10비트 크기의 배열 구조를 가지고 있고 , 1개의 Hash 함수를 가진 Bloom Filter 가 있다고 가정
  2. Hash 함수는 10 으로 나눈 후 나머지를 구하는 함수라고 가정
  3. Filter의 기준이 되는 집합의 원소 가 34 하나 뿐이라면 (오라클에서 선행테이블), 10으로 나누면 나머지는 "4" 이므로 4번째 비트를 1로 변경 한다
0 0 0 1 0 0 0 0 0 0

4. 기준 집합과 비교하는 대상의 (오라클에서 후행 테이블 ) 첫번째 원소가 56 라고 가정하고 Hash 함수 수행. 5. 10으로 나눈 후 나머지는 6 이고 여섯 번째 비트를 확인해 보면 결과는 0 임. 6. 즉 나머지 값이 "4" 가 아니면 기준 집합인 34 와 값이 동일할 수 있는 확률은 0% 임. 즉 조인을 할 필요가 없는 대상이 된다 . 7. 비교 대상의 두 번째 값은 54 라고 가정한다면 , 54를 10으로 나눈 Hash 함수를 수행하면 나머지는 "4" . 8. 네 번째 비트를 확인해 보았더니 값이 1 이다. 9. 우리는 34 와 54 는 같지 않다고 판단 하지만 , Bloom Filter 알고리즘에서는 54 나 34 나 10으로 나누는 Hash 함수의 수행결과 나머지가 "4" 로써 둘 다 참이 된다. 10. 54 는 4번째 비트가 1 이기 때문에 , 일단 참 이지만 마지막에 값을 비교하는 연산을 할 때 거짓 이 된다 . 11. Bloom Filter가 거짓 인데 참으로 판단하는 경우 False Negative 는 발생하지 않지만 , 54 처럼 Hash함수는 참인데 연산결과 거짓인 경우 False Positive 발생하게 된다 . 12. 문제는 False positive 가 많이 발생할수록 Bloom Filter 의 성능은 점점 떨어진다는 것.

  • Bloom Filter 의 성능을 좋게 하기 위해선 False positive 를 줄여야 함
  • False positive 를 줄이는 방법은 배열의 비트수를 늘리거나 hash 함수를 늘리는 방법이 있다 .
  • 배열의 비트수 를 늘리면 memory 사용률이 올라가고 , hash 함수를 증가시키면 cpu 사용량이 올라 간다 .


1.3 오라클 Bloom Filter 의 작동 요건[편집]

  • Parallel Join 과 Partition Table Join 시 조인 이전에 대상건수를 줄여 성능을 최적화 하는 역할.
  • 관련 힌트 : PX_JOIN_FILTER / NO_PX_JOIN_FILTER
  1. 반드시 Hash Join 또는 Merge Join 시에만 적용됨
  2. Partition Table 조인이어야 한다 ( 조인 Key 는 Partition Key 여야 한다 ).
  3. Partition Table 조인이 아닌 경우라면 , Parallel Query 여야 함.
  4. Parallel Query 도 아니고 Partition Table 도 아닌 경우 라도 Inline View 안에 Group by절이 포함된 경우 Bloom Filter 를 사용할 수 있다
    1. 이때, 조인 칼럼 은 Group by 절에 사용된 칼럼 이어야 한다
  • 주의 할 점) Parallel Query 에서 위 조건을 만족하고 , Bloom Filter 를 사용하도 록 힌트를 사용하였어도 "선행 테이블에 대한 상수 조건이 없을 경우에는 Bloom Filter 가 사용되지 않는다" 는 것 .
  • Bloom Filter 를 사용하는 것이 효율적이라 판단 되면 , Dummy 조건을 추가 하여 강제로 Bloom Filter 로 유도할 수 있다 .
  • 작동요건이 만족되고 힌트까지 부여해도 선행 집합에 상수 조건이 없다고 Bloom Filter가 작동되지 않는것은 성능적으로 않좋기 때문임.

1.4 선행집합에 상수 조건이 없다면 Bloom Filter가 작동되지 않는것 이유[편집]

  1. Bloom Filter 사용시 선행 테이블은 Filter 집합을 만드는데 사용됨
  2. 예를 들어 아무 조건이 없는경우 , 추출된 집합에 1~10 까지의 데이터가 포함되어 있다고 가정하고, 비트 배열의 크기가 10 이라면 , 10 개의 배열 모두 1 로 세팅 될 것이다.
  3. 즉, 모든 데이터가 false positive 가 발생함으로써 , 조인 이전에 데이터를 미리 걸러 내는 효과가 없음.
  4. 즉 선행테이블에 조건이 없다면 , 많은 양의 데이터가 추출 될 것이고 , 이로 인해 비트배열의 대부분이 1 로 마킹 됨으로써 Bloom Filter 의 효율이 떨어질 가능성이 크다는 것.

1.5 Bloom Filter 장점[편집]

  1. Hash Join 이나 Merge Join 을 하기에 젼에 조인 대상건수를 미리 줄여서 Join 의 부하를 감소 시킴.
  2. Parallel Processing 의 경우 Slave 에서 조인을 하기 위해 Coordinate 로 전송하는 통신량 감소, 조인시 의 부하 감소 시킴 .
  3. 엑사테이터에서 Bloom Filter 를 offloading 으로 처리하여 Cell Server 의 CPU 를 사용 해 DB 서버에 CPU 부하 를 감소 시킴 .

1.6 Bloom Filter 단점[편집]

  1. False positive 발생 빈도가 높을 경우 , 오히려 더 비효율적임.

1.7 Bloom Filter 모니터링 - V$SQL_JOIN_FILTER[편집]

  1. 우선 Parallel Processing이 되는지 확인
  2. DBMS_XPLAN 의 Predicate Information 을 통해 Bloom Filter 의 사용 여부는 알 수 있지만 , 실제 작업은 각각의 Slave Process가 하므로 실제적인 일량을 알수 없어 모니터링 불가

따라서 Parallel 을 사용한 경우에는 V$SQL_JOIN_FILTER View 를 통해 관찰 해야 한다 .

  1. V$SQL_JOIN_FILTER 뷰로 확인
select qc_session_id
     , sql_plan_hash_value
     , filtered
     , probed
     , probed - filtered AS send
  FROM V$SQL_JOIN_FILTER
 WHERE qc_session_id = 21
  • FILTERED : Bloom Filter 를 통해 제거된 Row 를 의미
  • PROBED : 전체 대상을 의미.
  • FILTERED 와 PROBED 의 수치가 비슷할수록 효율이 높다고 판단.
  • 예를 들언 전체 PROBED 집합 대상은 10 만건인데 , 그 중 Bloom Filter 로 99,993 건을 걸러낸 후 7 건의 데이터만 Coordinate 에게 전송한 후 조인 연산을 했다면 필터링 효율이 높은것임.
  • 주의사항) V$SQL_JOIN_FILTER 성능뷰는 Parallel SQL 에 대해서만 성능이 수집된다는 것
    • Partition Join Pruning 의 경우에는 해당 뷰에 정보가 남지 않으므로 이때 는 DBMS_XPLAN 이나 Trace 결과를 통해 효율성을 모니터링 해야함.

참조: https://dataonair.or.kr/db-tech-reference/d-lounge/technical-data/?mod=document&uid=235922

원본 주소 "http://dbcafe.co.kr/wiki/index.php?title=블룸필터_BLOOM_FILTER&oldid=11153"