HelloDBA [English]
搜索Internet 搜索 HelloDBABA
  Oracle技术站。email: fuyuncat@gmail.com  MSN: fuyuncat@hotmail.com   acoug  acoug 

布隆过滤器 (Bloom Filter)

[English]

作者: fuyuncat

来源: www.HelloDBA.com

日期: 2010-03-25 08:22:14

分享到  新浪微博 腾讯微博 人人网 i贴吧 开心网 豆瓣 淘宝 推特 Facebook GMail Blogger Orkut Google Bookmarks

    布隆过滤器(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代码
  1. HELLODBA.COM>host perl bloomfilter.pl 10 100   
  2. array size:20; hash num:10; vector members:100   
  3. 29 missed in 100(0.29)   
  4.   
  5. HELLODBA.COM>host perl bloomfilter.pl 10 150   
  6. array size:20; hash num:10; vector members:150   
  7. 5 missed in 100(0.05)   
  8.   
  9. HELLODBA.COM>host perl bloomfilter.pl 10 200   
  10. array size:20; hash num:10; vector members:200   
  11. 2 missed in 100(0.02)   

    代码可以在这里下载:
    http://www.Hellodba.com/Download/bloomfilter.zip 

        根据上面计算式,假如用10个hash函数判断一个元素是否在一个成员数为20的数据集当中,我们希望其误判率在0.01(1%)以内,那么m值最少为202

SQL代码
  1. 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);       
  2.       
  3.          M       
  4. ----------       
  5.        202     

     oracle在做并行join、分区裁剪(bloom filter pruning,11g引入)时会用到bloom filter。 

    以下是10.2.0.3上的相关参数: 

SQL代码
  1. HELLODBA.COM>select name, value, description from all_parameters where name like '%bloom%';   
  2.   
  3. NAME                           VALUE                          DESCRIPTION   
  4. ------------------------------ ------------------------------ --------------------------------------------------   
  5. _bloom_filter_enabled          TRUE                           enables or disables bloom filter   
  6. _bloom_filter_debug            0                              debug level for bloom filtering   

    以下是11g上的相关参数: 

SQL代码
  1. HELLODBA.COM>conn demo/demo@ora11   
  2. Connected.   
  3. NAME                           VALUE                          DESCRIPTION   
  4. ------------------------------ ------------------------------ ----------------------------------------------------------   
  5. _bloom_filter_enabled          TRUE                           enables or disables bloom filter   
  6. _bloom_filter_debug            0                              debug level for bloom filtering   
  7. _bloom_vector_elements         0                              number of elements in a bloom filter vector   
  8. _bloom_predicate_enabled       FALSE                          enables or disables bloom filter predicate pushdown   
  9. _bloom_pruning_enabled         TRUE                           Enable partition pruning using bloom filtering   
 

    其中_bloom_vector_elements就是控制上面计算式中的m。 

    --- Fuyuncat ---

Top

Copyright ©2005,HelloDBA.Com 保留一切权利

申明
by fuyuncat