首页 > 代码库 > Bloom filters 布隆过滤器

Bloom filters 布隆过滤器

在ITPUB上看到有人写到同一条语句连续执行两次,得出的结果截然不同,数据本身没有发生变化,关掉dynamic_sampling功能,多次查询结果是正常的。究竟是为什么?

oracle通过内部函数使用布隆过滤对并行JOIN进行过滤。但是布隆过滤的精确度是依赖hash函数的好坏以及使用的hash函数数量决定的。
你试试将_bloom_filter_enabled设为FALSE关掉布隆过滤;或者将_bloom_vector_elements设为一个稍大的数字。
SQL> alter session set optimizer_dynamic_sampling=0;

 

布隆过滤器:

布隆过滤器由2个组件构成:K个hash函数和m位的位向量(bit
vector),m就是向量的位数,_bloom_vector_elements就是决定该值的参数。
向量所有位初始都为0,用k个hash函数对一个集合的所有成员映射,根据映射结果将向量相应位置1。要判断一个数是否属于该集合,同样用这k个函数对其映射,如果得出的某个位在集合的向量上相应位为0,则说明该数不属于该集合。但是,如果相应位都为1,并不能说明它一定属于该集合,这就是布隆过滤的误判。

假如集合成员数为n,用k个函数映射后,m位向量上某个位为0的概率为
(1-1/m)^(k*n)
某个位为1的概率就是
1-(1-1/m)^(k*n)
而如果要判断一个数是否属于该集合,其所有映射位和集合向量的所有匹配的概率就是
(1-(1-1/m)^(k*n))^k

从计算式上看,增加M值,就能降低误判率。