"블룸필터 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 동작원리 이해[편집]

• 블랙 리스트 기반 IP주소 검색 및 차단의 예시

4-1. IP x를 가져와 3개의 해싱 함수(f1,f2,f3)로 해싱. 
해싱함수별 해싱값 f1=1,f2=5,f3=13 

4-2. 각 해싱값에 해당되는 해당 배열 인덱스 값을 0에서 1로 수정

4-3. 18(N)개의 비트 배열, 그리고 3(J)개의 해싱 함수 사용함.

4-4. IP y로 4-1 ~ 4-3번 과정을 반복,
해싱함수별 해싱값 f1=4,f2=11,f3=16

4-5. IP z로 4-1 ~ 4-3번 과정을 반복 (이전 인덱스 값이 0이 아닌 1인경우 수정없이 1로 유지) , 해싱함수별 해싱값 f1=3,f2=5,f3=11

• 여기 까지가 블랙리스트 등록 끝.(오라클에서 선행테이블로 해시함수를 만든과정 완료)

5-1. w 라는 IP를 가진 패킷을 받음 

5-2. IP w를 위의 방식과 같이 3개의 해싱 함수(f1,f2,f3)로 해싱, 
f1=1,f2=13,f3=15 값이 나왔다면

5-3. 4,13 인덱스 값은 1이지만 15의 인덱스 값은 0 이므로 
w라는 IP는 블랙 리스트 IP가 아님

• Bloom Filter가 거짓 인데 참으로 판단하는 경우 - 거짓부정 => False Negative 는 발생하지 않지만 , 54 처럼 Hash함수는 참인데 연산결과 거짓인 경우 - 거짓긍정 => False Positive 발생하게 된다 .

• 문제는 거짓 긍정 (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. 주의 할 점) Parallel Query 에서 위 조건을 만족하고 , Bloom Filter 를 사용하도 록 힌트를 사용하였어도 "선행 테이블에 대한 상수 조건이 없을 경우에는 Bloom Filter 가 사용되지 않는다" 는 것.
2. Bloom Filter 를 사용하는 것이 효율적이라 판단 되면 , Dummy 조건을 추가 하여 강제로 Bloom Filter 로 유도할 수 있다 .
3. 작동요건이 만족되고 힌트까지 부여해도 선행 집합에 상수 조건이 없다고 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 를 통해 관찰 해야 한다 .
3. 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