블룸필터 BLOOM FILTER
DB CAFE
- DBA { Oracle DBA 명령어 > DBA 초급 과정 > DBA 고급 과정 }
- 튜닝 { 오라클 튜닝 목록 }
- 모델링 { 데이터 모델링 가이드 }
목차
1 BLOOM FILTER의 이해와 활용방법[편집]
1.1 개요[편집]
- 구성요소가 집합의 구성원인지 점검하는데 사용되는 확률적 자료 구조
- 두 집합의 원소가 한쪽은 적고 한쪽은 많을때 , 조인하여 일치하는 교집합의 수는 적을 경우 탁월한 성능을 보인다 .
- 대용량 데이터를 조인 할 때 조인하는 대상을 미리 필터하여 줄여주는 효과
- Parallel Join 시 , Hash Join ,Merge Join 시 발생함
- Join Filter Pruning 이나 Result Cache를 지원 하는데도 활용 됨
- 엑사데이터(EXADATA)에서 Bloom Filter 가 offloading 으로 처리 하도록 함으로써 , 데이터베이스 부하를 감소하는 중요한 요소.
1.2 Bloom Filter 의 동작원리[편집]
- 10비트 크기의 배열 구조를 가지고 있고 , 1개의 Hash 함수를 가진 Bloom Filter 가 있다고 가정
- Hash 함수는 10 으로 나눈 후 나머지를 구하는 함수라고 가정
- 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
- 반드시 Hash Join 또는 Merge Join 시에만 적용됨
- Partition Table 조인이어야 한다 ( 조인 Key 는 Partition Key 여야 한다 ).
- Partition Table 조인이 아닌 경우라면 , Parallel Query 여야 함.
- Parallel Query 도 아니고 Partition Table 도 아닌 경우 라도 Inline View 안에 Group by절이 포함된 경우 Bloom Filter 를 사용할 수 있다
- 이때, 조인 칼럼 은 Group by 절에 사용된 칼럼 이어야 한다
- 주의 할 점) Parallel Query 에서 위 조건을 만족하고 , Bloom Filter 를 사용하도 록 힌트를 사용하였어도 "선행 테이블에 대한 상수 조건이 없을 경우에는 Bloom Filter 가 사용되지 않는다" 는 것 .
- Bloom Filter 를 사용하는 것이 효율적이라 판단 되면 , Dummy 조건을 추가 하여 강제로 Bloom Filter 로 유도할 수 있다 .
- 작동요건이 만족되고 힌트까지 부여해도 선행 집합에 상수 조건이 없다고 Bloom Filter가 작동되지 않는것은 성능적으로 않좋기 때문임.
1.4 선행집합에 상수 조건이 없다면 Bloom Filter가 작동되지 않는것 이유[편집]
- Bloom Filter 사용시 선행 테이블은 Filter 집합을 만드는데 사용됨
- 예를 들어 아무 조건이 없는경우 , 추출된 집합에 1~10 까지의 데이터가 포함되어 있다고 가정하고, 비트 배열의 크기가 10 이라면 , 10 개의 배열 모두 1 로 세팅 될 것이다.
- 즉, 모든 데이터가 false positive 가 발생함으로써 , 조인 이전에 데이터를 미리 걸러 내는 효과가 없음.
- 즉 선행테이블에 조건이 없다면 , 많은 양의 데이터가 추출 될 것이고 , 이로 인해 비트배열의 대부분이 1 로 마킹 됨으로써 Bloom Filter 의 효율이 떨어질 가능성이 크다는 것.
1.5 Bloom Filter 장점[편집]
- Hash Join 이나 Merge Join 을 하기에 젼에 조인 대상건수를 미리 줄여서 Join 의 부하를 감소 시킴.
- Parallel Processing 의 경우 Slave 에서 조인을 하기 위해 Coordinate 로 전송하는 통신량 감소, 조인시 의 부하 감소 시킴 .
- 엑사테이터에서 Bloom Filter 를 offloading 으로 처리하여 Cell Server 의 CPU 를 사용 해 DB 서버에 CPU 부하 를 감소 시킴 .
1.6 Bloom Filter 단점[편집]
- False positive 발생 빈도가 높을 경우 , 오히려 더 비효율적임.
1.7 Bloom Filter 모니터링 - V$SQL_JOIN_FILTER[편집]
- 우선 Parallel Processing이 되는지 확인
- DBMS_XPLAN 의 Predicate Information 을 통해 Bloom Filter 의 사용 여부는 알 수 있지만 , 실제 작업은 각각의 Slave Process가 하므로 실제적인 일량을 알수 없어 모니터링 불가
따라서 Parallel 을 사용한 경우에는 V$SQL_JOIN_FILTER View 를 통해 관찰 해야 한다 .
- 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