�ݺ�ߣ

132│2013 기술백서 White Paper
BLOOM FILTER의 이해와 활용방법
㈜엑셈 컨설팅본부/DB컨설팅팀 오 수영
개요
Bloom Filter 란 1970 년도에 Burton H. Bloom 이 고안한 것으로 구성요소가 집합의 구성원인
지 점검하는데 사용되는 확률적 자료 구조이다. Bloom Filter 는 두 집합의 원소가 한쪽은 적고
한쪽은 많은데, 그 교집합이 수는 적을 경우 탁월한 성능을 보인다. 교집합은 오라클의 조인에
해당하며, bloom filter 는 대용량 데이터를 조인 할 때 더욱 효과적이다.
오라클은 점점 대용량 데이터 베이스를 다루게 되고, 급기야 대용량 데이터를 효율적으로 처리
할 수 있는 방안이 필요하게 되었다. 그 결과 10g R2 에서는 Parallel Join 시 Slave 간의
communication 데이터 량과 Hash Join 시 부하를 감소 시키기 위해 처음으로 Bloom Filter 를
사용하였고, 그 결과는 매우 훌륭했다.
오라클은 여기서 그치지 않고, 11g R1 에서는 Join Filter Pruning 이나 Result Cache 를 지원
하는데도 활용되었고, 오라클에서 Bloom Filter 활용폭은 점점 넓어지고 있다. 특히 최근 출시
한 EXADATA 의 경우에는 Bloom Filter 가 offloading 으로 처리하도록 함으로써, 데이터베이스
의 부하를 줄일 수 있는 중요한 요소로 자리 잡았다.
앞으로도 계속 데이터는 방대해 질 것이고, 이로 인해 오라클 내 Bloom Filter 의 활용은 더욱 중
요시 될 것이라고 필자는 생각을 한다. 따라서 Bloom Filter 가 무엇인지, 또 오라클에서는 성능
을 개선하기 위해 Bloom Filter 를 어떻게 활용해야 하는지를 알아 보도록 하겠다. 이 문서는
Bloom Filter 의 알고리즘을 이해하고, 이를 오라클에서 효과적으로 활용하고자 하는 목적으로
만들어 졌다.

Part 1 ORACLE │133
Bloom Filter의 동작원리
Bloom Filter 은 m 비트 크기의 비트배열 구조와, 서로 다른 K 가지의 Hash 함수를 사용하여 구
현된다. 여기서 각 Hash 함수는 m 가지의 값을 균등한 확률로 출력해야만 한다.
이해를 돕기 위해 예를 하나 들어 보도록 하겠다. 10 비트 크기의 비트배열 구조를 가지고 있고,
1 개의 Hash 함수를 가진 Bloom Filter 가 있다고 가정하자. Hash 함수는 10 으로 나눈 후 나머
지 값을 구하는 함수이다.
Filter 의 기준이 되는 집합의 원소가 34 하나 뿐이라면 (오라클에서 선행테이블), 10 으로 나눈
나머지는 4 이므로 네 번째 비트를 1 로 변경 한다
0 0 0 1 0 0 0 0 0 0
기준 집합과 비교하는 대상의 (오라클에서 후행 테이블) 첫 번째 원소가 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 거짓인데 참인 경우(False Negative)는 발생하지 않지만, 54 처럼 참인
데 거짓인 경우는(False Positive) 발생하게 된다. 문제는 false positive 가 많이 발생할수록
Bloom Filter 의 성능은 점점 떨어진다는 것이다.
Bloom Filter 의 성능을 좋게 하기 위해선 False positive 를 줄여야 한다. False positive 를 줄
이는 방법은 배열의 bit 수를 늘리거나 hash 함수를 늘리는 방법이 있다. 배열의 bit 수를 늘리면
memory 사용률이 올라가고, hash 함수를 증가시키면 cpu 사용량이 올라간다. 따라서 bloom
filter 의 성능을 향상 시키기 위해서는 적절한 m 과 k 를 유지하는 것이 매우 중요한 포인트이다.

오라클 Bloom Filter의 작동 요건
오라클에서도 Parallel Join 과 Partition Table Join 시 Bloom Filter 가 활용 되는데, 이때
Bloom filter 는 조인 이전에 대상건수를 줄여 성능을 최적화 하는 역할을 한다. 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 로 세팅 될 것이다. 이는 모든 데이터가
false positive 가 발생함으로써, 조인 이전에 데이터를 미리 걸러 내려던 Bloom Filter 의 목적
을 퇴색시켜 버린다. 즉 선행테이블에 조건이 없다면, 많은 양의 데이터가 추출 될 것이고, 이로
인해 비트배열의 대부분이 1 로 마킹 됨으로써 Bloom Filter 의 효율이 떨어 질 가능성이 크다는
것이다.

하지만 데이터 건수가 많더라도, 14, 24, 34, 54, 104, 204, .....식으로 모두 끝자리가 4 인 데
이터뿐이라면, 10 개의 배열 중 네 번째만 1 이 되므로, false positive 가 발생할 확률은 크게 줄
어든다. 바로 이와 같은 상황이 우리가 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 에서 조인을 하기 위해 Coordinate 로 전송하는 통신
량을 감소 시키고, 조인의 부하까지 감소 시킨다.
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 를 통해 관찰해야 한다.

Bloom Filter 효율성 모니터링 Script
<<V$SQL_JOIN_FILTER View 를 통한 관찰>>
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 에게 전송한 후 조인 연산을 했다는 것을 알 수 있다.
Parallel SQL 의 경우는 위의 성능 뷰를 가지고 Bloom Filter 의 효율성을 체크하면 된다. 한가
지 주의 할 점은 V$SQL_JOIN_FILTER 성능 뷰는 Parallel SQL 에 대해서만 성능이 수집된다는
것이다. Partition Join Pruning 의 경우에는 해당 뷰에 정보가 남지 않으므로 이때는
DBMS_XPLAN 이나 Trace 결과를 통해 효율성을 모니터링 해야 한다. XPLAN 을 통한 분석은
다음 내용인 Bloom Filter 사용 여부에 대한 테스트에서 자세히 다루도록 하겠다.
Bloom Filter 사용 여부에 대한 테스트
지금부터는 Bloom Filter 가 어떤 상황에서 사용되는지 또 사용되었다면 그 효율성을 확인하는
방법에 대해 5 가지 테스트를 통해 알아보자.
먼저 테스트 위한 테이블을 생성하여 보도록 하겠다.

테스트 Script
<< FUNCTION_TABLE 테이블 생성>>
CREATE TABLE FUNCTION_TABLE AS
SELECT LEVEL C1,
MOD(LEVEL, 2) C2,
CHR(65+MOD(LEVEL,26)) C3,
MOD(LEVEL, 3) +1 C4
FROM DUAL
CONNECT BY LEVEL <= 100000;
-- 각 칼럼에 인덱스 생성 및 통계정보 수집
CREATE UNIQUE INDEX IDX_FUNCTION_TABLE_C1 ON FUNCTION_TABLE(C1);
CREATE INDEX IDX_FUNCTION_TABLE ON FUNCTION_TABLE(C2,C3);
CREATE INDEX IDX_FUNCTION_TABLE_C4 ON FUNCTION_TABLE(C4);
EXEC
dbms_stats.gather_table_stats(OWNNAME=>'SCOTT',TABNAME=>'FUNCTION_TABLE',CASCADE=>TRUE,ESTIM
ATE_PERCENT=>100) ;
<< C1_CODE_NAME 테이블 생성>>
-- 칼럼 C1 에 대한 코드성 테이블 생성 및 인덱스 생성]
-- C1_CODE_NM 테이블 생성
CREATE TABLE C1_CODE_NM AS
SELECT LEVEL C1,
LEVEL||'C2 CODE VALUE' C2,
CHR(65+MOD(LEVEL,20)) C3,
MOD(LEVEL,5) C4
FROM DUAL
CONNECT BY LEVEL <= 100000;
-- 인덱스 생성 및 통계정보 수집
CREATE UNIQUE INDEX IDX_C1_CODE_NM ON C1_CODE_NM(C1);
EXEC
dbms_stats.gather_table_stats(OWNNAME=>'SCOTT',TABNAME=>'C1_CODE_NM',CASCADE=>TRUE,ESTIMATE_

PERCENT=>100) ;
<<PART_TEST 파티션 테이블 생성 >>
CREATE TABLE SCOTT.PART_TEST
( C1 NUMBER,
C2 VARCHAR2(4),
C3 NUMBER,
C4 VARCHAR2(4),
BIG_ADDR VARCHAR2(3000)
) PCTFREE 10 PCTUSED 40 INITRANS 1 MAXTRANS 255
STORAGE(
BUFFER_POOL DEFAULT FLASH_CACHE DEFAULT CELL_FLASH_CACHE DEFAULT)
TABLESPACE USERS
PARTITION BY RANGE (C1)
(PARTITION TB1 VALUES LESS THAN (40000)
PCTFREE 10 PCTUSED 40 INITRANS 1 MAXTRANS 255
STORAGE(INITIAL 65536 NEXT 1048576 MINEXTENTS 1 MAXEXTENTS 2147483645
PCTINCREASE 0 FREELISTS 1 FREELIST GROUPS 1 BUFFER_POOL DEFAULT FLASH_CACHE DEFAULT
CELL_FLASH_CACHE DEFAULT)
TABLESPACE USERS NOCOMPRESS ,
PARTITION TB2 VALUES LESS THAN (600000)

PARTITION SYS_P21 VALUES LESS THAN (20000000)
TABLESPACE USERS NOCOMPRESS ) ;
insert into part_test value (select level, CHR(65+MOD(LEVEL,26)), level+99999,
CHR(65+MOD(LEVEL,26)), null from dual connect by level <=2000000);
dbms_stats.gather_table_stats(OWNNAME=>'SCOTT',TABNAME=>'PART_TEST',CASCADE=>TRUE,ESTIMATE_
PERCENT=>100) ;

No Parallel이면서 힙 테이블인 경우
먼저 No Parallel 이며 일반 테이블인 경우에 대해 Bloom Filter 가 사용되는지 확인해 보도록 하
겠다.
힙 테이블이고 Parallel Query 가 아니라면, PX_JOIN_FILTER 를 힌트를 사용하였지만, 전제
조건을 만족 하지 못함으로써 Bloom Filter 를 사용하지 못 하였음을 알 수 있다.
힙 테이블이지만 Parallel 처리를 하는 경우
힙 테이블이지만 Parallel Processing 을 수행하는 경우에 대해 Bloom Filter 가 사용되는지 확
인해 보도록 하겠다.

우선 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 효율성 모니터링 Script 를 활용하여 위 SQL 에 대한 정보를
확인해 보면 아래의 그림과 같다.
[그림] V$SQL_JOIN_FILTER 결과
전제 100,000 건 중에서 99,993 을 Bloom Filter 로 데이터를 걸러냈음을 알 수 있다. 이는
Bloom Filter 가 매우 효과적으로 사용 되었음을 의미한다. 만약 FILTERED 값이 매우 작다면,
Bloom Filter 의 효율성은 떨어지고 오히려 Bloom Filter 를 사용하기 위한 오버헤드만 증가하
므로 NO_PX_JOIN_FILTER 힌트를 사용해서 Bloom Filter 를 사용하지 못하도록 해야 할 것이
다.
No Parallel이지만 파티션 테이블인 경우
No Parallel Processing 이지만 파티션 테이블인 경우 Bloom Filter 가 사용되는지 확인해 보도
록 하겠다.

Outline Data 를 확인해 보면 PX_JOIN_FILTER 힌트가 적용되어 있으며, 실행계획상 PART
JOIN FILTER CREATE 오퍼레이션 이름인 :BF000 을 통해 해당 SQL 이 Bloom Filter 를 사용
하였음을 알 수 있다.
위 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 Parallel이고 힙 테이블인 경우 (Group by 절 존재)
No Parallel 이고, 힙 테이블이지만 Group By 가 있는 Inline View 가 존재할 때의 경우, Bloom
Filter 를 사용하는지에 대해 알아 보도록 하겠다.
힙 테이블이고 No Paralle SQL 이므로 Bloom Filter 의 사용이 불가하여 보이지만, Outline
Data 를 확인해 보면 PX_JOIN_FILTER 가 힌트가 적용되어 있으며, PLAN 이나 Predicate
Information 에서도 Bloom Filter 를 사용한 흔적들을 확인 할 수 있다.
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 절에 해당하는 칼럼 Deptno 와 조인키가 존재해야지만 Bloom Filter 를 사용할 수 있
다.
결론
지금까지 Bloom Filter 가 무엇인지 또 오라클에서 Bloom Filter 가 어떻게 사용되는지를 알아
보았다. 더불어 오라클에서 사용된 Bloom Filter 가 효율적인지를 판단하는 방법에 대해 살펴 보
았다. Bloom Filter 는 Slave 간의 communication 데이터 량은 물론 Join 에 의한 부하를 효과
적으로 줄여 성능을 개선하는 방법이지만, 항상 그러한 것은 아니다. 따라서 우리가 효율성을 판
단 한 후, 유리할 경우에만 사용하도록 하는 것이 바람직하다. Bloom Filter 는 대용량 데이터를
매우 효율적으로 처리할 수 있다. 따라서 오라클도 버전이 올라 갈 때마다 활용 범위가 늘어가고
있는 추세이다. 그리고 앞으로도 더 많은 곳에서 활용 될 것으로 예상된다.
이처럼 활용폭이 커지는 Bloom Filter 에 대한 알고리즘을 이해하고, 한발 더 나아가 Bloom
Filter 의 사용이 효율적인지를 판단하고 적시 적기에 활용한다면, DB 의 성능을 개선함에 있어
많은 도움이 될 것으로 생각된다.

�ݺ�ߣ

BlOOM FILTER의 이해와 활용방법_Wh oracle

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

Similar to BlOOM FILTER의 이해와 활용방법_Wh oracle (9)

More from 엑셈 (9)

BlOOM FILTER의 이해와 활용방법_Wh oracle