Re: Bloom Filter lookup for hash joins

On Wed, Jun 26, 2013 at 5:01 AM, Atri Sharma <atri(dot)jiit(at)gmail(dot)com> wrote:

>
> > The problem here is that if the hash table is in memory, doing a hash
> > table lookup directly is likely to be cheaper than a bloom filter
> > lookup, even if the bloom filter fits into the processor cache and the
> > hash table doesn't (10 last level cache hits is slower than one cache
> > miss). Bloom filter will help when its not feasible to use an actual
> > hash table (lots of large keys), the real lookup is slow (e.g. an
> > index lookup), you are doing a lot of lookups to amortize the
> > construction cost and the condition is expected to be selective (most
> > lookups give a negative). There might be some dataware house types of
> > queries where it would help, but it seems like an awfully narrow use
> > case with a potential for performance regressions when the planner has
> > a bad estimate.
>
> Ok, sounds good. Cant we use bloom filters for the case where the hash
> table doesnt fit in memory? Specifically, when reading from disk is
> inevitable for accessing the hash table, we can use bloom filters for
> deciding which keys to actually read from disk.

I don't think that sounds all that promising. When the hash table does not
fit in memory, it is either partitioned into multiple passes, each of which
do fit in memory, or it chooses a different plan altogether. Do we know
under what conditions a Bloom filter would be superior to those options,
and could we reliably detect those conditions?

Cheers,

Jeff