（原创）Oracle's BLOOM feature 布隆过滤

feiyang10086

（原创）Oracle's BLOOM feature 布隆过滤

升入11.2.0.1遇到一个BLOOM过滤器导致的问题。 系统里面发生大量死锁，但是这个ORA-60伴随着另一个错误ORA-10387 ORA-00060: deadlock detected while waiting for resource ORA-10387: parallel query server interrupt (normal) 通过和ORACLE SUPPORT 沟通后，认为是由bug 9124206 和 bug 8361126引起。通过设置如下参数 NAME TYPE VALUE ------------------------------------ ----------- ------------------ _bloom_filter_enabled boolean FALSE _bloom_pruning_enabled boolean FALSE 来避免这个bug。 我在metalink想查询这两个bug，一个是no fix， 一个是not publish（杯具）。不过通过设置这个参数，我就没有看见过ORA-10387了，虽然ORA-60仍然很多（我OPEN了另外一个SR关于11g is more sensitive on deadlock） 那么什么是BLOOM 过滤呢，下面稍作解释。 BLOOM算法不是ORACLE发明的新算法，它是由Burton在1970年提出的。 BLOOM过滤是一个数据结构和算法，用于判断一个元素是否在它的集合内。 BLOOM的基本数据结构是一个数组，它的初始成员都是为0，长度为M. 【0，0，0，0，0，。。。。。。。。。。。。。。。0，0，0，0，0】 在初始化的时候，每一个要放置进去的元素，通过HASH计算出L个大小1到M的值，然后将数组的对应的成员赋值为1.一个位置，可以重复赋值。 【0，1，0，1，0，。。。。。。。。。。。。。。。0，1，0，0，1】 在进行过滤判断的时候，过程也是一样，通过HASH 算法将对应的位数算出来，然后去判断是否每一位都是1，如果是，那么就说明该元素包含在当前数据集。 但是BLOOM是存在误判的可能，这个几率和几个因素有关， 1. 数组的大小M 2. HASH函数的产生映射位数L（把几个数组成员值0置为1） 3. 以及要加入数组的元素N 为什么会产生误判？一个通俗易懂解释，就是在M数组中加入大量的元素映射后，一部分的数组元素都变成1，那么很有可能一个并不存在于数组的中的元素，在进行判断的时候，它的算出的映射位置恰好由几个其它元素的映射位置占领了，这时候就会误判它存在于这个集合。 而当M越大时，误判就会减少。 我在网上找到一段由Christian写的PL/SQL代码，可以模拟这一过程，如下： CREATE OR REPLACE PACKAGE BODY BLOOM_FILTER IS TYPE T_BITARRAY IS TABLE OF BOOLEAN; G_BITARRAY T_BITARRAY; G_M BINARY_INTEGER; G_K BINARY_INTEGER; ---------------------------------------- PROCEDURE INIT(P_M IN BINARY_INTEGER, P_N IN BINARY_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)); 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; -- dbms_output.put_line('NO'); ELSE dbms_output.put_line('YES'); END IF; END LOOP; END INIT; ---------------------------------------- FUNCTION ADD_VALUE(P_VALUE IN VARCHAR2) RETURN BINARY_INTEGER IS A NUMBER; BEGIN DBMS_RANDOM.SEED(P_VALUE); FOR I IN 0 .. G_K LOOP A:=DBMS_RANDOM.VALUE(1, G_M); dbms_output.put_line(A); G_BITARRAY(A) := TRUE; END LOOP; RETURN 1; END ADD_VALUE; ---------------------------------------- FUNCTION CONTAIN(P_VALUE IN VARCHAR2) RETURN BINARY_INTEGER IS L_RET BINARY_INTEGER := 1; BEGIN DBMS_RANDOM.SEED(P_VALUE); -- dbms_output.put_line('G_K='||G_K); FOR I IN 0 .. G_K LOOP IF NOT G_BITARRAY(DBMS_RANDOM.VALUE(1, G_M)) THEN L_RET := 0; EXIT; END IF; END LOOP; RETURN L_RET; END CONTAIN; PROCEDURE show_nest_table IS t NUMBER:=1; BEGIN FOR I IN G_BITARRAY.FIRST .. G_BITARRAY.LAST LOOP -- dbms_output.put_line(I); IF NOT G_BITARRAY(I) THEN NULL; dbms_output.put_line(I||'IS NO'); ELSE dbms_output.put_line(I||' IS YES'); t:=t+1; END IF; END LOOP; -- END; END BLOOM_FILTER; 测试过程 创建测试表 create table t as select dbms_random.string('u',100) As VALUE from dual connect by level <=10000; BLOOM数组初始化，数组大小为15000exec bloom_filter.init(15000,1000); 加入1000个元素 （表的前1000行） select count(bloom_filter.add_value(value)) from t where rownum<=1000; 判断表中数据有多少在BLOOM数组中 select count(*) from t where bloom_filter.contain(value)=1; 实际为1000，但结果会大于1000，说明产生了误判。 通过增加数组的大小可以观察，误判逐渐消失为0.本例，大概38000的数组大小，就可以100%成功过滤1000个元素。 ORACLE在11g中支持三类类型BLOOM特性 BLOOM filter BLOOM partition pruning Support result cache 但是不幸的是，由于bug，我们已经关闭前两种。

忻芯相印

嘻嘻嘻分享