Subject: Re: WIP: bloom filter in Hash Joins with batches
To: Peter Geoghegan <pg@heroku.com>
References: <5670946E.8070705@2ndquadrant.com>
 <CANP8+jKT=Vzv92mSv1Lh2tmeHyhmNBfa5xG6r1msgBT5QDf1Aw@mail.gmail.com>
 <5672DC2F.20205@2ndquadrant.com>
 <CANP8+jK+rSLrDVFvkNngGa7BT0ML7d=dUkk+DappRKMTp4bRBw@mail.gmail.com>
 <5691594B.4070209@2ndquadrant.com>
 <CAM3SWZQkrQZTKvXkcGsBDginH+KODsuPXAhqhOW5zCKZBTtCTQ@mail.gmail.com>
Cc: Simon Riggs <simon@2ndquadrant.com>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <5692AD27.6010300@2ndquadrant.com>
Date: Sun, 10 Jan 2016 20:12:39 +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: 
 <CAM3SWZQkrQZTKvXkcGsBDginH+KODsuPXAhqhOW5zCKZBTtCTQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

Hi,

On 01/10/2016 01:08 AM, Peter Geoghegan wrote:
> On Sat, Jan 9, 2016 at 11:02 AM, Tomas Vondra
> <tomas.vondra@2ndquadrant.com> wrote:
>> So, this seems to bring reasonable speedup, as long as the selectivity is
>> below 50%, and the data set is sufficiently large.
>
> What about semijoins? Apparently they can use bloom filters
> particularly effectively. Have you considered them as a special case?

You mean to handle them in a special way in the code, or just to perform 
benchmark semijoins (and not just regular joins)?

> Also, have you considered Hash join conditions with multiple
> attributes as a special case? I'm thinking of cases like this:
>
> regression=# set enable_mergejoin = off;
> SET
> regression=# explain analyze select * from tenk1 o join tenk2 t on
> o.twenty = t.twenty and t.hundred = o.hundred;
>                                                         QUERY PLAN
> ──────────────────────────────────────────────────────────────────────
>   Hash Join  (cost=595.00..4103.00 rows=50000 width=488) (actual
> time=12.086..1026.194 rows=1000000 loops=1)
>     Hash Cond: ((o.twenty = t.twenty) AND (o.hundred = t.hundred))
>     ->  Seq Scan on tenk1 o  (cost=0.00..458.00 rows=10000 width=244)
> (actual time=0.017..4.212 rows=10000 loops=1)
>     ->  Hash  (cost=445.00..445.00 rows=10000 width=244) (actual
> time=12.023..12.023 rows=10000 loops=1)
>           Buckets: 16384  Batches: 1  Memory Usage: 2824kB
>           ->  Seq Scan on tenk2 t  (cost=0.00..445.00 rows=10000
> width=244) (actual time=0.006..3.453 rows=10000 loops=1)
>   Planning time: 0.567 ms
>   Execution time: 1116.094 ms
> (8 rows)
>
> (Note that while the optimizer has a slight preference for a merge
> join in this case, the plan I show here is a bit faster on my
> machine).

The patch I posted actually does not build bloom filter on the values 
directly, but on the hashvalue we already use. So it handles hashjoins 
with arbitrary number of attributes just fine.

Or perhaps you're thinking about some special optimization that might 
improve such cases (I can't think of any)?

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