首页 > 代码库 > 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值,就能降低误判率。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。