"블룸필터 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. Bloom Filter 은 m비트 크기의 비트배열 구조와 , 서로 다른 K가지의 Hash 함수를 사용 하여 구현

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

이해 를 돕기 위해 예를 하나 들어 보도록 하겠다 . 10 비트 크기의 비트배열 구조를 가지고 있고 , 1 개의 Hash 함수를 가진 Bloom Filter 가 있다고 가정하자 . Hash 함수는 10 으로 나눈 후 나머 지 값을 구하는 함수 이다 . F ilter 의 기준이 되는 집합의 원소 가 34 하나 뿐이라면 ( 오라클에서 선행테이블 ), 10 으로 나눈 나머지는 4 이므로 네 번째 비트를 1 로 변경 한다

tech_img2212.png 기준 집합과 비교하는 대상의 ( 오라클에서 후행 테이블 ) 첫 번째 원소가 56 라고 가정하자 . 우선 56 에 대해 Hash 함수를 수행 한다 . 그러면 6 이란 결과를 얻을 것이다 . 따라서 , 여섯 번째 bit 를 확인해 보면 결과는 0 이다 . 나머지 값이 4 가 아니라면 기준 집합인 34 와 값이 동일할 수 있는 확률은 0% 이다 . 따라서 조인을 할 필요가 없는 대상이 된다 .

비교 대상의 두 번째 값은 54 라고 하자 . 54 를 Hash 함수를 수행하면 4 란 결과 값을 얻는다 . 따라서 네 번째 비트를 확인해 보았더니 값이 1 이다 . 우리는 단 번 에 34 와 54 는 같지 않다고 판단 하지만 , Bloom Filter 알고리즘 입장에서는 54 나 34 나 Hash 함수의 수행결과는 각각 4 로써 둘 다 참이다 .

54 는 네 번째 bit 가 1 이기 때문 에 , 일단 참 이지만 마지막에 값을 비교하는 연산을 할 때 거짓 이 된다 . Bloom Filter 거짓 인데 참인 경우 (Fa l se Negative) 는 발생하지 않 지만 , 54 처럼 참인 데 거짓인 경우는 (Fa l se Positive) 발생하게 된다 . 문제는 fa l se positive 가 많이 발생할수록 Bloom Filter 의 성능은 점점 떨어진다는 것 이다 .

Bloom Filter 의 성능을 좋게 하기 위해선 F al se positive 를 줄 여야 한다 . False pos itive 를 줄 이는 방법은 배열의 bit 수를 늘리거나 hash 함수를 늘리는 방법이 있다 . 배열의 bit 수 를 늘리면 memory 사용률이 올라가고 , hash 함수를 증가시키면 cpu 사용량이 올라 간다 . 따라서 bloom filter 의 성능을 향상 시키기 위해서는 적절한 m 과 k 를 유지하는 것이 매우 중요한 포인트이다 .

오라클 Bloom Filter 의 작동 요건

오라클에서도 Parallel Join 과 Partition Table Join 시 Bloom Fil ter 가 활용 되는데 , 이때 Bloom filte r 는 조인 이전에 대상건수를 줄여 성능을 최적화 하는 역 할 을 한다 . Bloom Filter 사 용 여부를 제어하는 관련 힌트로는 PX_JOIN_FILTER / NO_PX_JOIN_FILTER 가 있다 . 하지만 해당 힌트를 사용한다고 모든 SQL 에 대해 Bloom Filter 를 사용 하는 것은 아니다 . Bloom 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 를 사용하지 않을까 필자의 생각에는 Bloom Filter 를 사용함으로써 오히려 성능이 크게 저하 되는 부분을 막고자 하는 오라클의 노력이 아닐까 생각된다 .

예를 들면 , Bloom Filter 를 이용할 때 선행 테이블은 Filter 집합을 만드는데 사용된다 . 예를 들 어 아무 조건이 없어 추 출 된 집합에 1~10 까지의 데이터가 포함되어 있다고 가정하자 . 그리고 비트 배 열의 크기가 10 이라면 , 10 개의 배열 모두 1 로 세 팅 될 것이다 . 이는 모든 데이터가 fa l se positive 가 발생함으로써 , 조인 이전에 데이터를 미리 걸러 내려던 Bloom Filter 의 목적 을 퇴색시켜 버린다 . 즉 선행테이블에 조건이 없다면 , 많은 양의 데이터가 추출 될 것이고 , 이로 인해 비트배열의 대부분이 1 로 마킹 됨으로써 Bloom Filter 의 효율이 떨어 질 가능성이 크다는 것이다 .

하지만 데이의 배열 중 네 번째만 1 이 되므로 , f a l se po s itive 가 발생할 확률은 크게 줄 어든다 . 바로 이와 같은 상황이 우리가 dummy 조건을 추가하여서라도 Bloom Filter 를 사용하 도록 유도해야 하는 상황이다 . 그렇다면 Bloom Filter 를 언제 사용해야 하는가 답은 간단 명료 하다 . 효율성이 좋을 때 사용해야 한다 . 그렇다면 Bloom Filter 의 효율성은 어떻게 확인해야 하 는지 알아 보도록 하겠다 .

Bloom Filter 이점 및 모니터링 방법

오라클이 Bloom Filter 를 사용함으로써 얻는 이점들은 아래와 같다 .

1. Bloom Filter 는 (Join Filter Pruning) Hash Join 이나 Merge Join 을 하기에 앞서 조인 대상건수를 미리 줄 임 으로써 Join 의 부하 를 감소 시킨다 . 2. Parallel Processing 의 경우 Slave 에서 조인을 하기 위해 Co or dinate 로 전송하 는 통신 량을 감소 시키고 , 조인의 부하까지 감소 시킨다 . 3. EXADATA 에서는 Bloom Filter 를 offloading 으로 처리 함으로써 Cell Server 의 CPU 를 사용 해 DB 서버에 CPU 부하 를 감소 시킨다 .

Bloom Filter 는 위에서 언급하였듯 장점이 많 지만 False positive 발생 빈도가 높 을 경우 , 오히 려 더 비효율적 이기 때문에 현재 SQL 이 Bloom Filter 를 사용 하였다면 , 얼마나 효 율적인지를 모니터링을 할 필요성 이 있 다 . 지금 부터 오라클에서 Bloom Filter 가 사용되었는지에 대한 여부 와 그 효율성을 모니터 링 하는 방법에 대해 알아 보도록 하겠다 .

Bloom Filter 를 모니터링 하는 방법은 Parallel 사용 여부에 따라 달라진다 . 먼저 Parallel Processing 인 경우에 대해 알아 보도록 하자 . Parallel SQL 의 경우 DBMS_XPLAN 의 Predicate Information 을 통해 Bloom Filter 의 사용 여부는 알 수 있지만 , 실제 작업은 각각의 Slave Process 가 하므로 실제적인 일량을 알 수 없어 모니터링이 불가하다 . 따라서 Parallel 을 사용한 경우에는 V$SQL_JOIN_FILTER View 를 통해 관찰 해야 한다 .

tech_img2213.png FILTERED 는 Bloom Filter 를 통해 제거된 Row 를 의미하며 , PROBED 는 전체 대상을 의미한 다 . 즉 FILTERED 와 PROBED 의 수치가 비슷할수록 효율이 높다 고 볼 수 있다 .

즉 전체 PROBED 집합 대상은 10 만건인데 , 그 중 Bl oom Filter 로 99,993 건을 걸러낸 후 7 건 의 데이터만 Coordinate 에게 전송한 후 조인 연산을 했다는 것을 알 수 있다 .

Parallel SQL 의 경우는 위의 성능 뷰를 가지고 Bloom Filter 의 효율성을 체크하면 된다 . 한가 지 주의 할 점은 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