布隆过滤(Bloom Filter)-必须了解的优化器算法
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
吴军博士,在《数学之美》一书中,曾经介绍过这个算法,以下内容转引自吴军博士的文章:
假定我们存储一亿个电子邮件地址,我们先建立一个十六亿二进制(比特),即两亿字节的向量,然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X,我们用八个不同的随机数产生器(F1,F2, ...,F8) 产生八个信息指纹(f1, f2, ..., f8)。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。(见下图)
现在,让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器(F1, F2, ..., F8)对这个地址产生八个信息指纹 s1,s2,...,s8,然后将这八个指纹对应到布隆过滤器的八个二进制位,分别是 t1,t2,...,t8。如果 Y 在黑名单中,显然,t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址,我们都能准确地发现。
布隆过滤能够使用极低的存储空间,存储海量数据的映射,从而可以提供快速的过滤机制。
这一算法在Oracle Database 10gR2中被引入到Oracle数据库中,在类似如下的执行计划中,就可以看到布隆过滤的作用:
-----------------------------------------------------------------------------------------------
| Id | Operation | Name | Pstart| Pstop |IN-OUT| PQ Distrib |
-----------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | | |
| 1 | PX COORDINATOR | | | | | |
| 2 | PX SEND QC (RANDOM) | :TQ10002 | | | P->S | QC (RAND) |
|* 3 | FILTER | | | | PCWC | |
| 4 | HASH GROUP BY | | | | PCWP | |
| 5 | PX RECEIVE | | | | PCWP | |
| 6 | PX SEND HASH | :TQ10001 | | | P->P | HASH |
| 7 | HASH GROUP BY | | | | PCWP | |
|* 8 | HASH JOIN | | | | PCWP | |
| 9 | PART JOIN FILTER CREATE | :BF0000 | | | PCWP | |
| 10 | PX RECEIVE | | | | PCWP | |
| 11 | PX SEND PARTITION (KEY) | :TQ10000 | | | P->P | PART (KEY) |
| 12 | PX BLOCK ITERATOR | | | | PCWC | |
| 13 | TABLE ACCESS FULL | CUSTOMERS | | | PCWP | |
| 14 | PX PARTITION HASH JOIN-FILTER| |:BF0000|:BF0000| PCWC | |
|* 15 | TABLE ACCESS FULL | SALES |:BF0000|:BF0000| PCWP | |
-----------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - filter(COUNT(SYS_OP_CSR(SYS_OP_MSR(COUNT(*)),0))>100)
8 - access("S"."CUST_ID"="C"."CUST_ID")
15 - filter("S"."TIME_ID"<=TO_DATE(\' 1999-10-01 00:00:00\', \'syyyy-mm-dd hh24:mi:ss\') AND
"S"."TIME_ID">=TO_DATE(\' 1999-07-01 00:00:00\', \'syyyy-mm-dd hh24:mi:ss\'))
在以上执行计划中,BF0000 即 Bloom Filter的缩写提示。
而PART JOIN FILTER CREATE 这个步骤,是创建Bloom Filter的过程,在14,15 PX PARTITION HASH JOIN-FILTER中,过滤器被使用。
Oracle的很多新特性在最初引入时,都可能带来BUG,影响性能,所以了解Oracle数据库在不同版本中引入的新特性,对于DBA来说非常重要。
以下两个链接,可以作为参考:
http://www.acoug.org/wp-content/uploads/2010/04/ACOUG-OracleSortAndBloomFilter-Fuyuncat.pdf
http://antognini.ch/papers/BloomFilters20080620.pdf
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:eygle@eygle.com(eygle) 来源: Oracle Life
- 标签: 优化器 布隆过滤
- 发布时间:2012-09-03 13:49:15
- [52] 图书馆的世界纪录
- [52] IOS安全–浅谈关于IOS加固的几种方法
- [51] 如何拿下简短的域名
- [50] android 开发入门
- [49] Oracle MTS模式下 进程地址与会话信
- [49] Go Reflect 性能
- [47] 【社会化设计】自我(self)部分――欢迎区
- [45] 读书笔记-壹百度:百度十年千倍的29条法则
- [37] 程序员技术练级攻略
- [28] 视觉调整-设计师 vs. 逻辑