"블룸필터 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로 변경 한다

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[편집]

select qc_session_id
     , sql_plan_hash_value
     , filtered
     , proved
     , probed- filtered AS send
  FROM V$SQL_JOIN_FILTER
 WHERE qc_session_id = 21

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

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

1. V$SQL_JOIN_FILTER 뷰로 확인
   1. FILTERED : Bloom Filter 를 통해 제거된 Row 를 의미
   2. PROBED : 전체 대상을 의미.
   3. FILTERED 와 PROBED 의 수치가 비슷할수록 효율이 높다고 판단.

• 예를 들언 전체 PROBED 집합 대상은 10 만건인데 , 그 중 Bloom Filter 로 99,993 건을 걸러낸 후 7 건의 데이터만 Coordinate 에게 전송한 후 조인 연산을 했다면 필터링 효율이 높은것임.
• 주의사항) V$SQL_JOIN_FILTER 성능뷰는 Parallel SQL 에 대해서만 성능이 수집된다는 것
  • Partition Join Pruning 의 경우에는 해당 뷰에 정보가 남지 않으므로 이때 는 DBMS_XPLAN 이나 Trace 결과를 통해 효율성을 모니터링 해야함.

XPLAN 을 통한 분석은 다음 내용인 Bloom Filter 사용 여부에 대한 테스트에서 자세히 다루도록 하겠다 .

Bloom Filter 사용 여부에 대한 테스트

지금부터는 Bloom Filter 가 어떤 상황에서 사용되는지 또 사용되었다면 그 효율성을 확인하는 방법에 대해 5 가지 테스트를 통해 알아보자 .

먼저 테스트 위한 테이블을 생성하여 보도록 하겠다 .

테스트 Scr ipt

tech_img2214.png tech_img2215.png tech_img2216.png tech_img2217.png No Parallel 이면서 힙 테이블인 경우

먼저 No Parallel 이며 일반 테이블인 경우에 대해 Bloom Filter 가 사용되는지 확인해 보도록 하 겠다 .

tech_img2218.png 힙 테이블이고 Parallel Query 가 아니라면 , PX_JOIN_FILTER 를 힌트를 사용하였지만 , 전제 조건을 만족 하지 못함으로써 Bloom Filter 를 사용하지 못 하였음을 알 수 있다 .

힙 테이블이지만 Parallel 처리를 하는 경우

힙 테 이블이지만 Parallel Processing 을 수행하는 경우에 대해 Bloom Filter 가 사용되는지 확 인해 보도록 하겠다 .

tech_img2219.png 우선 Outline Data 를 확인해 보면 , PX_JOIN_FILTER 힌트가 적용되어 있으며 , Bloom Filter 가 사용되었음을 알 수 있다 . 그리고 Predicate Information 의 존재하는 filter(SYS_OP_BLOOM_FILTER(:BF0000, ” B ” . ” C1 ” )) 조건도 Bloom Filter 가 사용되 었음을 의미한다 .

하지만 Bloom Filter 가 효과적인지는 DBMS_XPLAN 을 통해서는 확인할 수가 없다 . 왜냐하면 실제 일을 수행한 프로세스는 Slave 이기 때문에 일량에 대한 정보가 표시되지 않기 때문이다 . 위 예제와 같이 Parallel SQL 에 대한 Bloom Filter 의 효율성을 검토하기 위해서는 V$SQL_JOIN_FILTER 성능 View 를 통해 확인해 봐야 한다 .

위에서 언급되었던 Bloom Filter 효율성 모니터링 Scrip t 를 활용하여 위 SQL 에 대한 정보를 확인해 보면 아래의 그림과 같다 .

tech_img2220.png 전제 100,000 건 중에서 99,993 을 Bloom Filter 로 데이터를 걸러냈음을 알 수 있다 . 이는 Bloom Filter 가 매우 효과적으로 사용 되었음을 의미한다 . 만약 FILTERED 값이 매우 작다면 , Bloom Filter 의 효율성은 떨어지고 오히려 Bloom Filter 를 사용하기 위한 오버헤드만 증가하 므로 NO_PX_ JOIN_FILTER 힌트를 사용해서 Bloom Filter 를 사용하지 못하도록 해야 할 것이 다 .

No Parallel 이지만 파티션 테이블인 경우

No Parallel Processing 이지만 파티 보도 록 하겠다 . Outline Data 를 확인해 보면 PX_JOIN_FILTER 힌트가 적용되어 있으며 , 실행계획상 PART JOIN FILTER CREATE 오퍼레이션 이름인 :BF000 을 통해 해당 SQL 이 Bloom Filter 를 사용 하였음을 알 수 있다 .

tech_img2221.png 위 SQL 은 parallel Processing 이 아니므로 , View 를 통해 효율성을 확인하는 것은 불가하다 . 따라서 이 경우에는 DBMS_XPLAN 을 통하여 확인 할 수 있다 . PART_TEST 테이블의 총 건수 는 200 만건이다 . 별도의 상수 조건이 존재하지 않는다면 , Hash Join 시 200 만건 전체에 대해 Hash Join 을 수행해야 할 것이다 . 그런데 PART_TEST 테이블 을 FULL SCAN 한 후의 A - Rows 부분을 보면 39,999 건이 되었다 . 이는 Bloom Filter 로 불필요한 조인 대상들을 제거하여 , 39,999 건에 대해서만 실제 Hash Join 을 수행한 것으로 볼 수 있다 .

만약 실행계획상 A - Rows 가 200 만에 가까웠다면 , 이는 Bloom Filter 를 사용한 이점이 거의 없 었다는 것을 의미한다 . 이와 같을 때에는 NO_PX_JOIN_FILTER 힌트를 사용하여 Bloom Filter 를 사용하지 않도록 함으로써 , Bloom Filter 에 의한 오버헤드를 제거해야 할 것이다 .

한가지 주의 해야 할 점이 있다 . Join Filter 기능은 11g 에서 추가된 기능으로써 10g 에서는 사 용할 수 없다는 것과 , 조인 칼럼 이 반드시 파티션 Key 칼럼 으로 조인되어야지만 사용 가능하다는 것이다 . ( 조인키로 쓰인 PART_TEST C1 은 파티션 Key 칼럼 이다 . 만약 C1 이 아닌 C2 칼럼 으로 조인을 한다면 Bloom Filter 를 사용할 수 없다 .)

No Para llel 이고 힙 테이블인 경우 (Group by 절 존재 )

No Parallel 이 고 , 힙 테이블이지만 Group By 가 있는 Inline View 가 존재할 때의 경우 , Bloom Filter 를 사용하는지에 대해 알아 보도록 하겠다 . 힙 테이블이고 No Paralle SQL 이므로 Bloom Filter 의 사용이 불가하여 보이지만 , Outline Data 를 확인해 보면 PX_JOIN_FILTER 가 힌트가 적용되어 있으며 , PLAN 이나 Predicate I nformation 에서도 Bloom Filter 를 사용한 흔적들을 확인 할 수 있다 .

tech_img2222.png Bloom Filter 의 효율성을 확인해 보면 전체 14 건중 6 건이 Bloom Filter 를 통해 조인 대상에 서 제거 된 것을 확인 할 수 있다 . 힙 테이블이면서 , No Parallel 임에도 불과하고 Bloom Filter 가 사용된 이유는 Inline View 안에 있는 Group by 절 때문이다 . Inline View 의 데이터를 보면 Deptno 별로 Max(sal) 을 구하고 있다 . 이는 즉 파티션 테이블처럼 데이터가 Deptno 를 기준으 로 명확하게 구분되어지기 때문이다 .

인라인 뷰를 파티션으로 비교해 보자면 , 파티션 Key 에 대응하는 부분은 Group by 절에 나열된 deptno 이다 . 파티션 테이블의 경우 , 조인이 조건이 파티션 키 이어야지만 Bloom Filter 를 사 용할 수 있었다 . Group by 절을 사용한 Inline View 도 마찬가지다 . 파티션 키에 해당하는 Group by 절에 해당하는 칼럼 De ptno 와 조인키가 존재해야지만 Bloom Filter 를 사용할 수 있 다 .

결론

지금까지 Bloom Filter 가 무엇인지 또 오라클에서 Bloom Filter 가 어떻게 사용되는지를 알아 보았다 . 더불어 오라클에서 사용된 Bloom Filter 가 효율적인지를 판단하는 방법에 대해 살펴 보 았다 . Bloom Filter 는 Slave 간의 communication 데이터 량은 물론 Join 에 의한 부하를 효과 적으로 줄 여 성능을 개선하는 방법이지만 , 항상 그러 한 것은 아니 다 . 따라서 우리가 효율성을 판 단 한 후 , 유리할 경우에만 사용하도록 하는 것이 바람직 하 다 . Bloom Filter 는 대 용량 데이터를 매우 효율적으로 처리할 수 있다 . 따라서 오라클도 버전이 올라 갈 때마다 활용 범위가 늘어가고 있는 추세이다 . 그리고 앞으로도 더 많은 곳에서 활용 될 것으로 예상된다 .

이처럼 활용폭이 커지는 Bloom Filter 에 대한 알고리즘을 이해하고 , 한발 더 나아가 Bloom Filter 의 사용이 효율적인지를 판단 하고 적시 적기에 활용한다면 , DB 의 성능을 개선함에 있어 많은 도움이 될 것으로 생각된다 .

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