布隆过滤器 （Bloom Filter）
[English]
作者：
fuyuncat
来源：
www.HelloDBA.com
分享到
布隆过滤器（Bloom Filter）是用于判断一个元素是否属于一个数据集的数据结构。其基本思想就是用一个或多个hash函数对数据集中的每个成员做映射，映射结果不是存在完整的hash表中，而是一个位向量（bit vector）中。位向量所有位初始都为0，根据hash结果将位向量中相应位置1。对数据集中的所有成员的hash计算完成后，就得到了该数据集的位向量。当需要判断一个元素是否属于该数据集时，也用相同的hash函数对其映射得到它的位向量，然后将其位向量上所有为1的位与数据集位向量上相应位比较，如果发现数据集的位向量上某个位为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
而假设期望的误判率为p，那相应m值的计算就是
1/(1-(1-p^1/k)^1/(k*n)))
从上面的计算式可以看出，当m越大，误算的概率就越低。
我在这里用一段perl代码模拟了bloom filter。通过调整m值，可以看到m越大，误算率越低：
SQL代码
- HELLODBA.COM>host perl bloomfilter.pl 10 100
- array size:20; hash num:10; vector members:100
- 29 missed in 100(0.29)
- HELLODBA.COM>host perl bloomfilter.pl 10 150
- array size:20; hash num:10; vector members:150
- 5 missed in 100(0.05)
- HELLODBA.COM>host perl bloomfilter.pl 10 200
- array size:20; hash num:10; vector members:200
- 2 missed in 100(0.02)
代码可以在这里下载：
http://www.Hellodba.com/Download/bloomfilter.zip根据上面计算式，假如用10个hash函数判断一个元素是否在一个成员数为20的数据集当中，我们希望其误判率在0.01（1%）以内，那么m值最少为202
SQL代码
- HELLODBA.COM>select ceil(1/(1-power(1-power(p,1/k),1/(k*n)))) m from (select 0.01 p, 10 k, 20 n from dual);
- M
- ----------
- 202
oracle在做并行join、分区裁剪（bloom filter pruning，11g引入）时会用到bloom filter。
以下是10.2.0.3上的相关参数：
SQL代码
- HELLODBA.COM>select name, value, description from all_parameters where name like '%bloom%';
- NAME VALUE DESCRIPTION
- ------------------------------ ------------------------------ --------------------------------------------------
- _bloom_filter_enabled TRUE enables or disables bloom filter
- _bloom_filter_debug 0 debug level for bloom filtering
以下是11g上的相关参数：
SQL代码
- HELLODBA.COM>conn demo/demo@ora11
- Connected.
- NAME VALUE DESCRIPTION
- ------------------------------ ------------------------------ ----------------------------------------------------------
- _bloom_filter_enabled TRUE enables or disables bloom filter
- _bloom_filter_debug 0 debug level for bloom filtering
- _bloom_vector_elements 0 number of elements in a bloom filter vector
- _bloom_predicate_enabled FALSE enables or disables bloom filter predicate pushdown
- _bloom_pruning_enabled TRUE Enable partition pruning using bloom filtering
其中_bloom_vector_elements就是控制上面计算式中的m。
--- Fuyuncat ---