On 12/28/2015 11:52 AM, David Rowley wrote:
On 28 December 2015 at 23:44, Tomas Vondra <tomas.von...@2ndquadrant.com
<mailto:tomas.von...@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
        of Tuples. Are you saying this is not an assumption that we should

    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:

INSERT INTO t SELECT i FROM generate_series(1,1000000) s(i);

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).


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:

Reply via email to