Subject: Re: WIP: bloom filter in Hash Joins with batches
To: Simon Riggs <simon@2ndQuadrant.com>
References: <5670946E.8070705@2ndquadrant.com>
 <CANP8+jKT=Vzv92mSv1Lh2tmeHyhmNBfa5xG6r1msgBT5QDf1Aw@mail.gmail.com>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <5672DC2F.20205@2ndquadrant.com>
Date: Thu, 17 Dec 2015 17:00:47 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.1.0
MIME-Version: 1.0
In-Reply-To: 
 <CANP8+jKT=Vzv92mSv1Lh2tmeHyhmNBfa5xG6r1msgBT5QDf1Aw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

On 12/17/2015 11:44 AM, Simon Riggs wrote:
>
> My understanding is that the bloom filter would be ineffective in any of
> these cases
> * Hash table is too small

Yes, although it depends what you mean by "too small".

Essentially if we can do with a single batch, then it's cheaper to do a 
single lookup in the hash table instead of multiple lookups in the bloom 
filter. The bloom filter might still win if it fits into L3 cache, but 
that seems rather unlikely.

> * Bloom filter too large

Too large with respect to what?

One obvious problem is that the bloom filter is built for all batches at 
once, i.e. for all tuples, so it may be so big won't fit into work_mem 
(or takes a significant part of it). Currently it's not accounted for, 
but that'll need to change.

> * Bloom selectivity > 50% - perhaps that can be applied dynamically,
> so stop using it if it becomes ineffective

Yes. I think doing some preliminary selectivity estimation should not be 
difficult - that's pretty much what calc_joinrel_size_estimate() already 
does.

Doing that at dynamically is also possible, but quite tricky. Imagine 
for example the outer relation is sorted - in that case we may get long 
sequences of the same value (hash), and all of them will either have a 
match in the inner relation, or not have a match. That may easily skew 
the counters used for disabling the bloom filter dynamically.

regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers