Обсуждение: Re: [HACKERS] Boom filters for hash joins (was: A design for amcheckheapam verification)

On Tue, Aug 29, 2017 at 10:22 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
> Indeed.  Thank you for working on this!  To summarise a couple of
> ideas that Peter and I discussed off-list a while back:  (1) While
> building the hash table for a hash join we could build a Bloom filter
> per future batch and keep it in memory, and then while reading from
> the outer plan we could skip writing tuples out to future batches if
> there is no chance they'll find a match when read back in later (works
> only for inner joins and only pays off in inverse proportion to the
> join's selectivity);

You could try to use this with LEFT JOINs also, I think.  If you find
that a row can't match later, don't write it to the batch file;
instead, return a null-extended row immediately.

> (2) We could push a Bloom filter down to scans
> (many other databases do this, and at least one person has tried this
> with PostgreSQL and found it to pay off[1]).

I think the hard part is going to be figuring out a query planner
framework for this, because pushing down the Bloom filter down to the
scan changes the cost and the row-count of the scan.  This is
essentially a less-tractable version of the problem of deciding how
many parallel workers to use; in that case, at least, the number of
works must be an integer, so we could resort to trying them all, if
the costing model were otherwise good enough.  But here the thing that
matters is selectivity, which is a continuous rather than discrete.
Consider:

SELECT * FROM A LEFT JOIN (B INNER JOIN C ON B.x = C.x) ON A.y = B.y
LEFT JOIN D ON A.z > D.z;

Since the A-D join is not an equijoin, we'll have to implement it as a
nested loop; a case could also arise where a nested loop is the only
efficient strategy even for an equijoin, for example if D is huge.

Now, suppose the join to B-C is going to knock out 90% of the rows and
the join to D is going to knock out 50% of the rows, and that these
two percentages are independent of each other.  Normally, it would be
a slam-dunk to perform the B-C join first, but the Bloom filter
muddies the waters, because it might well be the case that what we
should really do is build the Bloom filter, apply it, then do the A-D
join, and do the A-(B-C) join last.  However, in order for the planner
to find that plan, it's going to need to be able to cost the nestloop
with an outer path that corresponds to a scan of A with the Bloom
filter applied.  And where is that path going to come from?

Note that it can't use that Bloom-filtered path for A unconditionally
because we might not opt to implement the A-(B-C) join as a hash join
at all; we have to build paths for NestLoop(A,D) and
NestLoop(Bloom(A),D) and we have to keep track of the fact that the
latter path has a dependency on a future hash join.  Things get
rapidly more complicated if you've got 10 or so different joins.  We
have to consider generate scan paths for the driving table with every
combination of Bloom filters that could be generated by subsequent
joins, and then all of those scan paths have to be carried through all
of the possible joinrels that can be generated later.  I think it's
not crazy to think that this could increase the cost of planning a
factor by 2^(# of joins).

Presumably some other method needs to be found, but I'm not clear what
that other method is.  Our planner is fundamentally bottom-up, and
it's not at all clear how to make it capable of changing its mind
later about something like the number of rows that a scan of A will
return, or how much that scan will cost.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


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

Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Aug 29, 2017 at 10:22 PM, Thomas Munro
> <thomas.munro@enterprisedb.com> wrote:
>> (2) We could push a Bloom filter down to scans
>> (many other databases do this, and at least one person has tried this
>> with PostgreSQL and found it to pay off[1]).

> I think the hard part is going to be figuring out a query planner
> framework for this, because pushing down the Bloom filter down to the
> scan changes the cost and the row-count of the scan.

Uh, why does the planner need to be involved at all?  This seems like
strictly an execution-time optimization.  Even if you wanted to try
to account for it in costing, I think the reliability of the estimate
would be nil, never mind any questions about whether the planner's
structure makes it easy to apply such an adjustment.

Personally though I would not bother with (2); I think (1) would
capture most of the win for a very small fraction of the complication.
Just for starters, I do not think (2) works for batched hashes.
        regards, tom lane


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

On Mon, Sep 18, 2017 at 10:29 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Tue, Aug 29, 2017 at 10:22 PM, Thomas Munro
>> <thomas.munro@enterprisedb.com> wrote:
>>> (2) We could push a Bloom filter down to scans
>>> (many other databases do this, and at least one person has tried this
>>> with PostgreSQL and found it to pay off[1]).
>
>> I think the hard part is going to be figuring out a query planner
>> framework for this, because pushing down the Bloom filter down to the
>> scan changes the cost and the row-count of the scan.
>
> Uh, why does the planner need to be involved at all?  This seems like
> strictly an execution-time optimization.  Even if you wanted to try
> to account for it in costing, I think the reliability of the estimate
> would be nil, never mind any questions about whether the planner's
> structure makes it easy to apply such an adjustment.

That is how I think about it too, though I'm not at all confident of
being on the right track. (I'm pretty confident that the general idea
of using a Bloom filter for parallel hash join is a good idea,
though.)

I should point out that Bloom filters are quite insensitive to
misestimations in the total number of elements, an estimate of which
must be provided up-front (I suppose that a cardinality estimate might
make more sense for hash join bloom filters than an estimate of the
total number of elements in a batch). "Bloom Filters in Probabilistic
Verification" gives this as a key advantage for bloom filters over
other approaches to formal model verification [1]. If you can afford
to have significant misestimations and still not lose much benefit,
and if the additional overhead of having a Bloom filter is fixed and
reasonably low cost, then maybe it makes sense to apply bloom filters
as an opportunistic or optimistic optimization. Perhaps they can be
applied when there is little to lose but much to gain.

[1] http://www.ccs.neu.edu/home/pete/pub/bloom-filters-verification.pdf
-- 
Peter Geoghegan


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

On Mon, Sep 18, 2017 at 1:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Uh, why does the planner need to be involved at all?

Because it loses if the Bloom filter fails to filter anything.  That's
not at all far-fetched; consider SELECT * FROM a.x, b.x WHERE a.x =
b.x given a foreign key on a.x referencing b(x).

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


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

On Mon, Sep 18, 2017 at 2:07 PM, Robert Haas <robertmhaas@gmail.com> wrote:
> On Mon, Sep 18, 2017 at 1:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Uh, why does the planner need to be involved at all?
>
> Because it loses if the Bloom filter fails to filter anything.  That's
> not at all far-fetched; consider SELECT * FROM a.x, b.x WHERE a.x =
> b.x given a foreign key on a.x referencing b(x).

Wouldn't a merge join be a lot more likely in this case anyway? Low
selectivity hash joins with multiple batches are inherently slow; the
wasted overhead of using a bloom filter may not matter.

Obviously this is all pretty speculative. I suspect that this could be
true, and it seems worth investigating that framing of the problem
first.

-- 
Peter Geoghegan


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

On Mon, Sep 18, 2017 at 5:13 PM, Peter Geoghegan <pg@bowt.ie> wrote:
> On Mon, Sep 18, 2017 at 2:07 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>> On Mon, Sep 18, 2017 at 1:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> Uh, why does the planner need to be involved at all?
>>
>> Because it loses if the Bloom filter fails to filter anything.  That's
>> not at all far-fetched; consider SELECT * FROM a.x, b.x WHERE a.x =
>> b.x given a foreign key on a.x referencing b(x).
>
> Wouldn't a merge join be a lot more likely in this case anyway? Low
> selectivity hash joins with multiple batches are inherently slow; the
> wasted overhead of using a bloom filter may not matter.
>
> Obviously this is all pretty speculative. I suspect that this could be
> true, and it seems worth investigating that framing of the problem
> first.

ISTR Tomas Vondra doing some experiments with this a few years ago and
finding that it was, in fact, a problem.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


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

Hi,

On 09/19/2017 02:55 AM, Robert Haas wrote:
> On Mon, Sep 18, 2017 at 5:13 PM, Peter Geoghegan <pg@bowt.ie> wrote:
>> On Mon, Sep 18, 2017 at 2:07 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>>> On Mon, Sep 18, 2017 at 1:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>>> Uh, why does the planner need to be involved at all?
>>>
>>> Because it loses if the Bloom filter fails to filter anything.  That's
>>> not at all far-fetched; consider SELECT * FROM a.x, b.x WHERE a.x =
>>> b.x given a foreign key on a.x referencing b(x).
>>
>> Wouldn't a merge join be a lot more likely in this case anyway? Low
>> selectivity hash joins with multiple batches are inherently slow; the
>> wasted overhead of using a bloom filter may not matter.
>>
>> Obviously this is all pretty speculative. I suspect that this could be
>> true, and it seems worth investigating that framing of the problem
>> first.
> 
> ISTR Tomas Vondra doing some experiments with this a few years ago and
> finding that it was, in fact, a problem.
> 

You seem to have better memory than me, but you're right - I did some
experiments with this in 2015, the WIP patch and discussion is here:
 https://www.postgresql.org/message-id/5670946E.8070705@2ndquadrant.com

The whole idea was that with a bloom filter we can reduce the amount of
tuples (from the outer relation) written to batches.

The patch is fairly simple, and did not try to push the bloom filters to
scan nodes or anything like that. It might be a meaningful first step,
though, particularly for selective joins (where only small number of
rows from the outer relation has a match in the hash table).

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

On Tue, Sep 19, 2017 at 6:28 AM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> The patch is fairly simple, and did not try to push the bloom filters to
> scan nodes or anything like that. It might be a meaningful first step,
> though, particularly for selective joins (where only small number of
> rows from the outer relation has a match in the hash table).

I believe that parallelism makes the use of Bloom filter a lot more
compelling, too. Obviously this is something that wasn't taken into
consideration in 2015.


-- 
Peter Geoghegan


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

On 09/19/2017 06:03 PM, Peter Geoghegan wrote:
> On Tue, Sep 19, 2017 at 6:28 AM, Tomas Vondra
> <tomas.vondra@2ndquadrant.com> wrote:
>> The patch is fairly simple, and did not try to push the bloom filters to
>> scan nodes or anything like that. It might be a meaningful first step,
>> though, particularly for selective joins (where only small number of
>> rows from the outer relation has a match in the hash table).
> 
> I believe that parallelism makes the use of Bloom filter a lot more 
> compelling, too. Obviously this is something that wasn't taken into 
> consideration in 2015.
> 

I haven't thought about it from that point of view. Can you elaborate
why that would be the case? Sorry if this was explained earlier in this
thread (I don't see it in the history, though).

I can't quite remember why I haven't pursued the patch in 2015, but it
was probably clear it wouldn't get in in the last CF, and I never got
back to it.

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

On Tue, Sep 19, 2017 at 4:25 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> I haven't thought about it from that point of view. Can you elaborate
> why that would be the case? Sorry if this was explained earlier in this
> thread (I don't see it in the history, though).
>
> I can't quite remember why I haven't pursued the patch in 2015, but it
> was probably clear it wouldn't get in in the last CF, and I never got
> back to it.

IIRC, it was a clear loser performance-wise in the case where the
Bloom filter didn't end up helping, and we didn't have a way to avoid
doing it when it didn't help.  That may or may not be why you didn't
pursue it, but I'm fairly sure it was my motivation for being
unexcited about the whole idea.  I think if we can solve that problem
somehow, we have a winner.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


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

On Tue, Sep 19, 2017 at 1:25 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> On 09/19/2017 06:03 PM, Peter Geoghegan wrote:
>> I believe that parallelism makes the use of Bloom filter a lot more
>> compelling, too. Obviously this is something that wasn't taken into
>> consideration in 2015.
>>
>
> I haven't thought about it from that point of view. Can you elaborate
> why that would be the case? Sorry if this was explained earlier in this
> thread (I don't see it in the history, though).

Well, IPC and locking shared state to protect the state's structure is
potentially a big bottleneck for parallel hash join. I think that
Bloom filters were first used in distributed databases in the 1980s,
where a network round trip could be saved, which this is a little
like. That's why my guess is that Bloom filtering will be more
valuable when parallelism is used.

I think that right deep hash joins make this really compelling, if and
when they allow you to build multiple Bloom filters that can be
combined from multiple right deep hash table builds. I think you can
do fancy things like reduce the amount of I/O against a star schema
fact table considerably. You can use one Bloom filter (built against
some dimension table) to drive a bitmap index scan on a fact table
index, and then another Bloom filter (built against some other
dimension table) to drive another bitmap index scan. The executor then
does a bitmap AND to combine the two for a bitmap heap scan on the
fact table.

(Maybe this technique doesn't necessarily use a Bloom filter; it could
be some other type of bitmap.)

-- 
Peter Geoghegan


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