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记重案实录
微信扫一扫关注公众号