Subject: Re: WIP: bloom filter in Hash Joins with batches
To: David Rowley <david.rowley@2ndquadrant.com>
References: <5670946E.8070705@2ndquadrant.com>
 <CACACo5Q0z9vQE8pHc+b6rzHr_TOTNg4=nc4eiQodtD1poOBCCQ@mail.gmail.com>
 <5672D617.9060601@2ndquadrant.com>
 <CAKJS1f8qTxf2nqFLQ-koXeUWNxJX0b63ceaRcDz-F68hNzy9dA@mail.gmail.com>
 <56810D8C.3020309@2ndquadrant.com>
 <CAKJS1f_aefsMQ0REQELgCysm=oLBryOO1S_YVSZq-mfixUYHxw@mail.gmail.com>
 <5681127F.9080301@2ndquadrant.com>
 <CAKJS1f-s0vsx6B0cftvT6HrjUmwJvKkX==MWzuZKLfeSPAC6NQ@mail.gmail.com>
Cc: "Shulgin, Oleksandr" <oleksandr.shulgin@zalando.de>,
 PostgreSQL Hackers <pgsql-hackers@postgresql.org>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <56811A8C.4020607@2ndquadrant.com>
Date: Mon, 28 Dec 2015 12:18:36 +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: 
 <CAKJS1f-s0vsx6B0cftvT6HrjUmwJvKkX==MWzuZKLfeSPAC6NQ@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/28/2015 11:52 AM, David Rowley wrote:
> On 28 December 2015 at 23:44, Tomas Vondra <tomas.vondra@2ndquadrant.com
> <mailto:tomas.vondra@2ndquadrant.com>> wrote:
>
>     On 12/28/2015 11:38 AM, David Rowley wrote:
>
>         If so, then a filter with all 1 bits set should be thrown away, as
>
>         it'll never help us, and the filter should generally become more
>         worthwhile as it contains a higher ratio of 0 bits vs 1 bits. Of
>         course we don't have a count of how many Tuples matched each bit, so
>         this is based on the assumption that each bit matches an equal
>         number
>         of Tuples. Are you saying this is not an assumption that we should
>         make?
>
>
>     Sure we should check that. All I'm saying is it has nothing to do
>     with the first problem described in the first part of the e-mail.
>
>
> Okay. I was merely suggesting this method as an alternative to checking
> tracking and checking the usefulness of the filter during the hash
> probe. I assumed that tracking and checking the usefulness during the
> hash probe won't be free, and that it may be better if we can estimate
> or determine the expected usefulness of the filter before the probe
> stage, and throw it away before we waste cycles using it.

Consider this example:

CREATE TABLE t (id INT);
INSERT INTO t SELECT i FROM generate_series(1,1000000) s(i);
ANALYZE;

SELECT * FROM t AS t1 JOIN t AS t2 ON (t1.id = t2.id)
  WHERE t1.id < 10000 AND t2.id < 10000;

This will be executed like this:

                               QUERY PLAN
-----------------------------------------------------------------------
  Hash Join  (cost=17046.26..34008.58 rows=94 width=8)
    Hash Cond: (t1.id = t2.id)
    ->  Seq Scan on t t1  (cost=0.00..16925.00 rows=9701 width=4)
          Filter: (id < 10000)
    ->  Hash  (cost=16925.00..16925.00 rows=9701 width=4)
          ->  Seq Scan on t t2  (cost=0.00..16925.00 rows=9701 width=4)
                Filter: (id < 10000)
(7 rows)

But of course the problem is that the two relations are (trivially) 
correlated, which means that in reality it works like this:

                        QUERY PLAN
---------------------------------------------------------
  Hash Join (actual rows=9999 loops=1)
    Hash Cond: (t1.id = t2.id)
    ->  Seq Scan on t t1 (actual rows=9999 loops=1)
          Filter: (id < 10000)
          Rows Removed by Filter: 990001
    ->  Hash (actual rows=9999 loops=1)
          Buckets: 16384  Batches: 1  Memory Usage: 480kB
          ->  Seq Scan on t t2 (actual rows=9999 loops=1)
                Filter: (id < 10000)
                Rows Removed by Filter: 990001
  Planning time: 0.316 ms
  Execution time: 176.283 ms
(12 rows)

So while we have very good estimates on the scan nodes, the final 
estimate is off - we expect about the bloom filter to eliminate ~99% of 
rows, in reality 100% of rows matches (due to the correlation). And 
that's even if the bloom filter is "perfect" in the sense that it has 
very low false probability etc.

This example illustrates that such cases can't be really solved before 
actually doing the lookups. Which does not make the checks you propose 
pointless, but they simply address different cases (and I indeed planned 
to implement them).

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