Oracle BLOOM过滤问题分析与解决


升入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,我们已经关闭前两种



相关阅读:
Javascript 浏览器事件小结
CSS元素的层叠与z-index设置
外部表在Oracle数据库中使用心得
JSP模板应用指南(上)
用缓冲技术提高JSP应用的性能和稳定性
用stack变量优化Java代码
关于CSS网页布局id与class的命名
影响Oracle中文显示的字符集分析
HTML5 CSS3新的WEB标准和浏览器支持
Asp备份与恢复SQL Server数据库
HTML5中div§ion&article之间的区别
Ajax获取页面被缓存的解决方案
帝国ECMS教程:上一篇下一篇自定义综合代码
PHP 中文乱码解决办法总结分析
快速导航

Copyright © 2016 phpStudy |