Oracle的Bloom Filter算法深入分析

 

Oracle12c引入了更多的bloom特性,本文对bloom算法做一个介绍,然后在对bloom算法和普通算法进行对比,从实践(代码)角度去理解,为什么bloom算法是一个优秀的算法。...



开篇

Bloom算法在Oracle10g就开始引入,但是一直以来,由于一些bug的存在,在由Oracle原厂工程师安装的数据库中,我们一般都会看到利用隐藏参数关闭了bloom相关特性。几年过去了,现在Oracle版本迈入了12c,大多数bloom算法相关的bug都已经得到了解决,并且Oracle引入了更多和bloom算法相关的特性。本文对bloom算法做一个介绍,然后在对bloom算法和普通算法进行对比,让大家从实践(代码)角度去理解,为什么bloom算法是一个优秀的算法。

注:本文用BLOOM来表示bloom filter算法,用HASH 来表hash filter算法。

Oracle 12.1.0.2 的BLOOM相关隐藏参数如下



介绍bloom算法

Bloom-Filter(布隆过滤算法),1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中。

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断,但不会漏掉判断。也就是BloomFilter可以精确判断元素不在集合,但如果判断元素存在集合中,有一定的概率误判。Bloom Filter比其他常见的算法极大节省了空间和时间。 它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

利用最简单语言来解释它的原理:

BLOOM的基本数据结构是一个数组,它的初始成员都是为0,长度为M.

【0,1,0,1,0,0,0,0,0,0,。。。。。。。。,0,0,0,0,0,0,0,0,0】

在初始化的时候,每一个要放置进去的元素,通过HASH计算出L个大小1到M的值,然后将数组的对应的成员赋值为1。关键的是同一个位置,可以重复的被多各元素赋值。

例如我的第一成员放入数组后,在数位1和3赋值为1。

【0,1,0,1,0,0,0,0,0,0,0。。。。。。。,0,0,0,0,0,0,0,0,0】

我的第二个成员放入数组后,数位0和3赋值为1,之后

【1,1,0,1,0,0,0,0,0,0,0。。。。。。。,0,0,0,0,0,0,0,0,0】

在进行过滤判断的时候,过程也是一样,通过HASH 算法将对应的位数算出来,然后去判断是否每一位都是1,如果是,那么就说明该元素包含在当前数据集。但是BLOOM是存在误判的可能,这个几率和几个因素有关, 1. 数组的大小M 2. HASH函数的产生映射位数L(把几个数组成员值0置为1) 3. 以及要加入数组的元素N

为什么会产生误判?一个通俗易懂解释,就是在M数组中加入大量的元素映射后,一部分的数组元素都变成1,那么很有可能一个并不存在于数组的中的元素,在进行判断的时候,它的算出的映射位置由几个其它元素的部分映射位置也同时占领了,这时候就会误判它存在于这个集合。而当M越大时,可以填充为1的位置越多越分散,误判就会减少。

BLOOM算法比普通算法的优势在哪里呢?

下面我们利用一段PL/SQL来分别实现BLOOM算法filter和传统的HASH算法filter,从空间和时间的角度进行对比。

CREATEOR REPLACE PACKAGE BODY BLOOM_FILTER IS

/*----------------------------------------------------

|introduction:对比bloom filter和 hash filter

|author      :王文杰

|from        :Oracle

*/----------------------------------------------------

TYPE T_BITARRAY IS TABLE OF BOOLEAN;

TYPE T_HASHLIST IS TABLE OF VARCHAR2(100)INDEX BY VARCHAR2(40);

TYPE T_poslist IS TABLE OF binary_integer;

G_BITARRAY T_BITARRAY;

G_HASHARRAY T_HASHLIST;

G_M        BINARY_INTEGER;

G_K        BINARY_INTEGER;

g_pos T_poslist;

TYPE t_value IS TABLE OF t.value%TYPE;

/*----------------------------------------------------

|introduction:初始化bloom数组

|author      :王文杰

|from        :Oracle

*/----------------------------------------------------

PROCEDURE INIT(P_M IN BINARY_INTEGER, P_N INBINARY_INTEGER) IS

BEGIN

G_M       := P_M;

G_BITARRAY := T_BITARRAY();

G_BITARRAY.EXTEND(P_M);

FOR I IN G_BITARRAY.FIRST ..G_BITARRAY.LAST LOOP

G_BITARRAY(I) := FALSE;

END LOOP;

G_K := CEIL(P_M / P_N * ln(2)); --确定多少位数赋值为1

dbms_output.put_line('G_K=' || G_K);

FOR I IN G_BITARRAY.FIRST ..G_BITARRAY.LAST LOOP

-- dbms_output.put_line(I);

IF NOT G_BITARRAY(I) THEN

NULL;

ELSE

dbms_output.put_line('YES');

END IF;

END LOOP;

END INIT;

/*----------------------------------------------------

|introduction:为bloom数组的数位进行位运算赋值,对即将进行过滤的数据进行位运算赋值

|author      :王文杰

|from        :Oracle

*/----------------------------------------------------

procedure add_value(p_n in number) is

a      number;

p_value varchar2(100);

pos    number:=1;

rown number:=0;

cursor c1 is

select value from t where rownum declare

2  nnumber;

3  mnumber;

4 begin

5 bloom_filter.init(10000,1000); --初始化bloom数组

6 bloom_filter.ADD_VALUE(1000); --初始化过滤数据1,计算后放入bloom数组

7 bloom_filter.CONTAIN;    --读取数据2,开始和数据1进行过滤

8  end;

9  /

G_K=7

ExecutionTime (secs)

---------------------

FORALL:   0.08           --过滤所用时间

RESULT:1549              --对比后,相等的数据数量

PL/SQL 过程已成功完成。

这里可以看出,实际我们数组2在数组1中,只有1000行数组有对应关系,但是最后的结果判断为1549行。发生了49行的误判。下面我们加大bloom数组的长度来避免误判。

SQL>set timing on

SQL>set serveroutput on size unlimited

SQL>declare

2  nnumber;

3  mnumber;

4 begin

5 bloom_filter.init(30000,1000);

6 bloom_filter.ADD_VALUE(1000);

7 bloom_filter.CONTAIN;

8  end;

9  /

G_K=21

ExecutionTime (secs)

---------------------

FORALL:   .06

RESULT:1000

/

G_K=21

ExecutionTime (secs)

---------------------

FORALL:   .06

RESULT:1000

/

G_K=21

ExecutionTime (secs)

---------------------

FORALL:   .05

RESULT:1000

PL/SQL过程已成功完成。

已用时间:  00: 00: 30.13

可以看出误判消除,测试中用了大约0.06秒完成了,50000行对1000行的过滤。

下面进行hash 算法的过滤,同样也是50000行对1000行的过滤。

SQL>set timing on

SQL>set serveroutput on size unlimited

SQL>declare

2  nnumber;

3  mnumber;

4 begin

5 bloom_filter.init_HASH(1000);--初始化数据1的hash数组

6 bloom_filter.contain_hash;  --读取数据2,计算hash 值,开始进行过滤

7  end;

8  /

ExecutionTime (secs)

---------------------

FORALL:  .08

RESULT:1000

SQL>/

ExecutionTime (secs)

---------------------

FORALL:   0.13

RESULT:1000

PL/SQL过程已成功完成。

已用时间:  00: 00: 01.32

SQL>/

ExecutionTime (secs)

---------------------

FORALL:   0.13

RESULT:1000

PL/SQL过程已成功完成。

已用时间:  00: 00: 01.33

SQL>/

ExecutionTime (secs)

---------------------

FORALL:   0.11

RESULT:1000

PL/SQL过程已成功完成。

可以看出hash 算法花费的时间更多。

总结

结果对比:

BLOOM                                              HASH

花费的时间             0.06s 0.06s 0.05s                              0.13s 0.13s 0.11s

时间对比上,我们仅仅对比了过滤的时间,没有把求hash映射值,计算bloom位数进行比较,因为PL/SQL中实现方式太少,性能上不具有对比性。

占用的内存             30K左右:30000bytes的bloom数组 6972K左右:(100bytes+40bytes)*51000

每次对比16~1000+bytes的临时空间

结论:可以看出从时间效率上BLOOM由于HASH,从空间效率上BLOOM同样由于HASH,而且随着数据量的增加HASH会快速增加,为BLOOM仅仅是增加bloom数组的长度。BLOOM算法同样也要优于另外一种常见的过滤算法:对折过滤。另外bloom filter的初始化时间是要长于hash filter的初始化间,至少在我的实现中是这样。但对于海量数据过滤来说,一般初始化时间并不是影响性能的主要因素。

最后我们再review一边12.1.0.2中的bloom相关参数

NAME                                     VALUE                DESCRIPTION

------------------------------------------------------------ ----------------------------------------------------------

布隆过滤需要的数据结构的参数设置一类的参数

_bloom_filter_debug

_bloom_filter_size

_bloom_folding_density

Bug9920533 : 11885 BF: _BLOOM_FOLDING_DENSITY==_BLOOM_FOLDING_MIN==0

_bloom_folding_min

_bloom_max_size

_bloom_minmax_enabled

_bloom_pushing_max

_bloom_pushing_total_max

_bloom_rm_filter

_bloom_serial_filter

_bloom_sm_enabled

布隆过滤的开关一类的参数:

_bloom_filter_enabled

_bloom_folding_enabled

_bloom_predicate_enabled

在11.2.0.1中曾经有wrong result bug,但现在已经修复

_bloom_predicate_offload

Exdata的相关特性

_bloom_pruning_enabled

布隆修剪的开关

_optimizer_inmemory_bloom_filter

Immemory数据库中引入了bloom特性。

作者简介:

 王文杰: 甲骨文公司资深数据库专家,多年Oracle&Java数据库项目构架,开发,实施和运维经验。实践经验丰富,技术全面,擅长于数据库性能调优、SQL优化,数据库疑难问题诊断,同时拥有丰富的软件开发经验。曾作为构架师独立设计开发某省电信工单激活系统,曾任美国某500强公司DBA Leader,在IBM和甲骨文任职期间为客户解决多次疑难杂症,优化核心数据库,深得客户好评。

Valen.wong81@gmail.com

Facebook nick name: Wj wang

                                       


    关注 西区O记重案实录


微信扫一扫关注公众号

0 个评论

要回复文章请先登录注册