Bloom Filters

In Oracle Database 11g, the performance of partition pruning has been enhanced by using bloom filtering instead of subquery pruning. While subquery pruning was activated on a cost-based decision and consumed internal (recursive) resources, pruning based on bloom filtering is activated all the time without consuming additional resources.

A Bloom Filter is a probabilistic algorithm that quickly tests membership in a large set using multiple hash functions into a single array of bits. A join filter can be used when an execution plan fetches all of the rows of one table before fetching any rows from another table that joins to it:

The join filter builds an array of bits, and turns on bits on for each row of the first table that matches the search conditions

When scanning the second table, rows that could not possibly join with the first table are rejected.

As already mentioned, in a parallel hash join with inter-node parallelism the interconnect can become a bottleneck. Pre filtering using bloom filter can reduce communication overhead.

example of an explain plan with bloom filter:

select count(*) from empp e, deptp d where e.deptno = d.deptno

In Oracle Database 11g, the Bloom Filter is enabled by default.