Re: hashjoins vs. Bloom filters (yet again)

On 5/30/26 19:12, Andrew Dunstan wrote:
>
> On 2026-05-29 Fr 8:55 PM, Tomas Vondra wrote:
>> Hi,
>>
>> A random discussion at pgconf.dev made me revisit one of my ancient
>> patches, attempting to use Bloom filters to hash joins. I did work on
>> that twice in the past - first in 2015/6 [1], then in 2018 [2]. So let
>> me briefly revisit that, before I get to the new patch.
>>
>>
>> old patches
>> -----------
>>
>> Those old patches tried to do a fairly small thing during a hash join,
>> and that's building a Bloom filter on the inner relation (the one that
>> gets hashed), and then use that filter before probing the hash table.
>>
>> The benefits come from Bloom filters being (fairly) cheap, and a
>> negative answer (hash is not in the filter) may allows us to skip a much
>> more expensive operation.
>>
>> The old threads patches focused especially at two hash join cases:
>>
>> (a) A very selective join, i.e. a significant fraction of outer tuples
>> does not have a match in the hash table.
>>
>> (b) A selective hash join forced to do batching because the hash table
>> is too large, and thus forced to spill outer tuples to temporary files.
>>
>> For (a), the benefit comes from Bloom filters being much cheaper to
>> probe than a hash table. The exact cost depends on the implementation,
>> sizes, etc. We're in the ballpark of 50 vs. 500 cycles, maybe. But if
>> the filter discards 90% of tuples, it can be a big win.
>>
>> For (b), the filter (for all the batches at once) allows us to discard
>> some of the outer tuples without writing them to temporary files. Which
>> is way more expensive than probing a hash table.
>>
>> The patches got stuck mostly because deciding if it makes sense to
>> build/use the Bloom filter is somewhat hard. For cases where 100% of the
>> tuples have a match it's pointless - it's just pure cost, no benefit.
>> The regressions are relatively small, though (<10%).
>>
>> For (b) it's much less sensitive to this kind of issues, of course. The
>> cost of writing outer tuples to temporary files is much higher than
>> building/probing a Bloom filter.
>>
>> Clearly, a filter that discards 99% of tuples is great. And a filter
>> that keeps 99% of tuples is not great. But where exactly are the
>> thresholds is not quite clear.
>>
>> There's also a related question of sizing the filter. Bloom filters are
>> usually sized by specifying the number of distinct values and the
>> desired false positive rate. And we could try doing that - pick a
>> standard false positive rate (e.g. the built-in bloom_filter aims for
>> 1-2%), estimate the ndistinct, and get the size of the Bloom filter.
>>
>> However, chances are the filter is too big. We can't get work_mem, the
>> join is already using that for the hash table etc. We can maybe use a
>> fraction of it, and that may not be enough to fit the "perfect" filter.
>> We could bail out and not use any Bloom filter at all, but that seems a
>> bit silly. Maybe we can't fit the 2% filter, but 5% of 10% would be OK?
>>
>> Surely if the join selectivity is 1% (i.e. it discards 99% tuples), then
>> using a "worse" Bloom filter with 10% false positives would be a win?
>> It'd still discard ~89% of tuples.
>>
>> Yet another angle leading to this kind of questions is inaccurate
>> ndistinct estimates (and we all know those estimates can be quite
>> unreliable). Let's say we size the filter for 1M distinct values (and it
>> just about fits into the memory budget), but then during execution we
>> find there are 2M distinct values. Well, now we may have ~10% false
>> positive rate. Or maybe we got 5M, and it's 30%. Or 10M / 50%.
>>
>> At some point the filter stops being worth it, and we should either not
>> build it, or we should stop probing it. But when is that?
>>
>> I think we'd need some sort of cost model to make judgments about this.
>>
>> Anyway, this was just me summarizing the old threads, and what I think
>> got them stuck. Most of these questions are still open, although I think
>> we may be able to solve them better than we could ~10 years ago. We have
>> extended stats, we know about FK constraints during planning, ...
>>
>>
>> new patch
>> ---------
>>
>> Now let's talk about the new experimental/PoC patch that came from the
>> pgconf.dev discussions. It doesn't really solve the issues I just went
>> through, it's more of an attempt to take it one step further.
>>
>> One of the things mentioned in the 2018 thread was the possibility to
>> push the filter much deeper, instead of using it just in the hash join
>> node itself. It was merely discussed, but there was no code written, or
>> anything like that. But it's the thing I decided to take a stab at after
>> getting back from Vancouver.
>>
>> Consider a starjoin query
>>
>> SELECT + FROM f JOIN d1 (f.id1 = d1.id)
>> JOIN d2 (f.id2 = d2.id)
>> JOIN d2 (f.id3 = d3.id)
>> WHERE d1.x = 1
>> AND d2.y = 2
>> AND d3.z = 3;
>>
>> which will be planned using a left-deep plan like this one:
>>
>> HJ
>> / \
>> D3 HJ
>> / \
>> D2 HJ
>> / \
>> D1 F
>>
>> With hashes on "D" tables, and a scan on "F". With the "old" patches,
>> each HJ node would use a Bloom filter internally. But there's an
>> interesting opportunity to "push down" the filters to the scan on "F",
>> and evaluate them right there, a bit as if the scan had a local qual.
>>
>> The attached patch implements a PoC of this, and it's pretty effective.
>>
>> Of course, it depends on the selectivity of the joins (and thus how many
>> tuples get discarded by the filters). But because it moves all the
>> "cheap" filter probes *before* probing any of the hash tables, it has a
>> multiplication effect for the benefits.
>>
>> Yes, it still has most of the open issues discussed earlier, and those
>> will need to be addressed. But this "multiplication" may also make it
>> somewhat less sensitive to the regressions.
>>
>> In the example above, if each of the 3 joins has 20% selectivity (i.e.
>> 20% tuples go through), then the total selectivity is ~1%. So the "F"
>> scan produces only 1/100 of tuples. Maybe we got one of the joins wrong,
>> and it does not eliminate any tuples? That still means the overall
>> selectivity is only ~4%.
>>
>> Of course, this only works for larger joins, and maybe the joins are
>> correlated in some weird way, etc. Also, what does 4% selectivity mean
>> for the overall query duration?
>>
>> Attached is a PDF with results from a simple benchmark using joins like
>> the one above - fact + 1-3 dimensions. The scripts (in the .tgz) set a
>> couple GUCs to eliminate variations in the plan. The dimension joins are
>> independent and match a variable fraction of the fact (1% - 100%).
>>
>> The columns are for three branches - master, and "patched" with the
>> push-down disabled and enabled, for joins with 1-3 dimensions.
>>
>> The last two column groups are comparing the "patched" results to
>> master. With "off" there's no difference (other than random noise), just
>> as expected. But with the push-down enabled, there are fairly
>> significant speedups (up to ~3x). Of course, this is just a benchmark,
>> practical queries may do other stuff, making the gains smaller. OTOH, it
>> may also be much better, if there are expensive nodes in between.
>>
>>
>> The PoC patch is not very big or complex. 280KB seems like a lot, but
>> like 99% of that is changes in test output, because the patch adds some
>> info about the Bloom filters to EXPLAIN. The actual .c changes are only
>> ~1000 lines, and a half of that is comments.
>>
>> The most interesting stuff happens in create_hashjoin_plan(), where we
>> attempt to push-down the filter to a scan in the outer subtree. If that
>> succeeds, then ExecInitHashJoin initializes the filter so that the scan
>> can find it, and Hash builds the filter along with the hash table. And
>> then the scan nodes probe the pushed-down filter in ExecScanExtended().
>>
>> There's bunch of boilerplate so that setrefs does the right thing with
>> expressions, etc. But it's a couple lines here and there. I'm actually
>> surprised how little code this is.
>>
>> There's one detail I haven't mentioned yet - there's a simple adaptive
>> behavior, to deal with filters that are not selective enough. Per some
>> initial tests there's little benefit when the filter keeps >75% tuples,
>> and for >90% there were measurable regressions (~50%). This was very
>> consistent for different data types, etc.
>>
>> So the patch tracks number of matching tuples per 1000 probes, when it
>> exceeds 90% it switches to sampling. Only 1% of tuples gets probed in
>> the filter, and if the fraction drops <80%, all the tuples get probed
>> again. This is very simple, needs more thought. But for the purpose of
>> the testing it worked quite well. There still is a small regression
>> (~3%), which I assume is due to building the filter.
>>
>>
>> Aside from the issues with deciding if to use a filter at all, sizing
>> it, etc. - which are still valid (even with the adaptive thing), and
>> need to be solved, there's one more annoying issue specific to this new
>> push-down stuff.
>>
>>
>> Earlier, I mentioned the push-down happens in create_hashjoin_plan().
>> Which means it happens *after* planning and costing. There are reasons
>> for that, but it has some unfortunate & annoying consequences.
>>
>> Ideally, we'd know about the filters when constructing the scan nodes,
>> so we'd have a chance to estimate how many tuples will be eliminated by
>> probing the filters (which is about the same thing as estimating the
>> join sizes). But we can't do that, because our planner works bottom-up.
>> When constructing the scan nodes we know which tables we'll join with,
>> but we have no idea which of the join algorithms we'll pick.
>>
>> We'll consider all three join types, and the scan node has no say which
>> of those will win. But the Bloom filter push-down is specific to hash
>> joins. So what should the scan node do? Either it can assume it's under
>> hash join (and set rows/cost as if there's a Bloom filter), or it can
>> set costs in a join-agnostic way (like now).
>>
>> The only "correct" way I can think of dealing with this in the bottom-up
>> world is having two sets of paths - one set for a hash join, one set for
>> other joins. But that's not just for scans. We'd need that for all
>> paths, and for different combinations of joins. For the query with 3
>> joins, we'd end up with 2^3 combinations. That seems not great.
>>
>>
>> So I tend to see this as an opportunistic optimization. We do the
>> planning assuming there's no Bloom filter push-down, and then after the
>> fact we see if there's an opportunity after all. Which means we may not
>> pick a plan with hash joins, not realizing it might be made faster.
>>
>> But in my mind that's somewhat acceptable / defensible.
>>
>> The bigger issue for me is that it may make the EXPLAIN ANALYZE output
>> way harder to understand. The estimated "rows" are calculated before the
>> filter push-down happens, while the actual "rows" are with the filter
>> probing, of course. But it seems pretty easy to get confused by this,
>> and think it's just an incorrect estimate.
>>
>>
>> summary
>> -------
>>
>> I like the idea of pushing filters down to the scan nodes (or perhaps
>> even to some other intermediate nodes). But maybe it's too incompatible
>> with our bottom-up planning, and the issues with costing and/or EXPLAIN
>> output may be impossible to solve. I wonder what others think.
>>
>>
>> Now that I revisited the older threads, I think it probably makes sense
>> with using Bloom filters in the hash join, at least in the two cases
>> mentioned in the first section. It doesn't have the issues with
>> bottom-up planning/costing, because it happens in the hash join. And the
>> issues with that (deciding what fractions are OK, sizing the filter,
>> ...) apply to both that simpler case, and to the push-down.
>
>
>
> Hi, Tomas
>
> This is terrific and very timely from my POV.
>
> I've been experimenting with a table AM (implemented as a
> CustomScan scan provider), and bloom-filter pushdown from a hashjoin is one
> of the bigger wins available to it: a fact-table scan joined to a filtered
> dimension can use the filter to skip whole row groups and avoid
> decompressing columns entirely, rather than just rejecting a tuple after
> it's been produced. I'd hacked up a private version of this via a new
> table-AM callback (the hashjoin walks the outer subtree, builds a filter
> from the build side, and hands it to the AM's scan descriptor). Having now
> read your PoC, I think your framework is the better foundation, and I'd
> rather build on it than carry a parallel mechanism. But two things stand in
> the way of a storage-level consumer using it, and I think both are
> relatively
> small.
>

OK, good to hear. I was actually thinking about that use case too, i.e.
making it possible for the scan to do something smart with the filter
(like even pushing it even further down, to "storage"). Or maybe the
ForeignScan could push it to the remote side, so that it's actually
filtered there.

I didn't mention that my message, and there are some difficulties:

1) We only build the hash (and bloom) with a delay, after the scan
already produces some tuples. That complicates the pushdown, whiich may
need to happen when starting the scan. Presumably, we'd need to allow
disabling this optimization, optionally.

2) We'd need some sort of "portable" Bloom filter, with serialization
and deserialization, etc.

Both of these seem rather solvable.

> 1) A CustomScan can't currently be a recipient.
>
> find_bloom_filter_recipient() only recognizes the stock scan tags, and the
> probe itself lives in ExecScanExtended(), which a CustomScan never calls
> (it dispatches to the provider's ExecCustomScan). The second part is
> actually a feature, not a bug: if a CustomScan provider does its own
> probing, it can choose the granularity -- per dictionary entry, per row
> group, or per row -- instead of being locked into the per-row,
> post-materialization probe that the stock nodes get. So all that's needed
> on your side is to let the planner attach a filter to a base-relation
> CustomScan; the provider takes care of consuming it.
>
> Concretely, that's adding T_CustomScan to the scan-leaf case in
> find_bloom_filter_recipient() (CustomScan embeds Scan first, so the
> scanrelid test is identical; non-leaf custom nodes have scanrelid == 0 and
> fall through to NULL), plus the matching fix_scan_bloom_filters() call in
> set_customscan_references(). The provider then calls ExecInitBloomFilters()
> in BeginCustomScan and ExecBloomFilters() (or a coarser-grained variant)
> inside its scan loop. Everything else -- producer registration, the
> es_bloom_producers lookup, the adaptive sampling, EXPLAIN -- is reused
> unchanged.
>

Yes, that should work and it's a mostly mechanical change.

Maybe we'd want some sort of opt-in, so that the CustomScan can indicate
it can handle Bloom filters. Like, setting
CUSTOMPATH_SUPPORT_BLOOM_FILTERS to flags.

> 2) The combined-hash filter can't be tested against a single column.
>
> You build one filter keyed on hash32() of all the join keys combined. For a
> single-key join that's ideal, and a column store can use it directly: hash
> each distinct dictionary value once per row group and skip groups whose
> values are all absent. For a multi-column join, though, the combined hash
> mixes the keys, so it can only ever be tested per-row (with all key columns
> in hand) -- it can't be checked against any one column's dictionary. The
> per-row probe is still useful, but the row-group/dictionary skipping, which
> is where most of the storage win comes from, isn't available.
>
> The obvious thought is to key a filter per column instead. But I don't
> think that should *replace* the combined filter, because per-column filters
> are strictly less selective on multi-column joins: they only test whether
> each column's value appears *somewhere* in the build side, not whether the
> combination does. With build pairs {(1,10),(2,20)}, an outer (1,20) passes
> both per-column filters even though it matches no build row, whereas the
> combined filter rejects it. So for the row-level probe -- and especially
> for plain heap -- the combined filter is the better one, and replacing it
> would be a regression.
>
> What I think would actually help is to let the framework *optionally* emit
> per-column filters in addition to the combined one, when a recipient
> signals it can use them. The combined filter stays the default and does the
> precise per-row rejection (unchanged for heap, and usable per-row by a
> column store too); the per-column filters are extra, built only on demand,
> and let a storage consumer cheaply eliminate whole row groups before the
> combined filter does the exact work. The cost is the build CPU and memory
> for the extra filters -- but only for consumers that ask, so your design is
> untouched when nobody does. For a single-key join the two filters
> coincide, so
> there'd be no reason to build both.
>

I think I speculated about this (having per-key filters) in some of the
comments in the patch, although the use case was different. I haven't
thought about TAM, but about different joins where the join keys come
from both sides. Consider a join like

HJ
/ \
A HJ
/ \
B C

where A-(BC) is on (A.x = B.x AND A.y = C.y), so the complete filter
can't be pushed to either side. But we could:

(1) Push the filter on top of the BC join (which in this example is not
really a push-down).

(2) Build filters on (x) and (y) separately, and push-down these.

Or we could do both, really.

I suppose a variation of (2) would work for your use case too, except
we'd push all three filters (x,y), (x) and (y) to the same scan.

I guess this could also be opt-in, enabled by some CUSTOMPATH_ flag.

The question is how efficient can the smaller filters be. The complete
filter can be very selective, while the per-key filters are terrible.

>
> I'd be happy to work on patches for these.
>

Great. It's and interesting experiment / area to explore.

FWIW I think the main difficulty for this PoC is going to be the
planning/costing stuff, and the impact on EXPLAIN.

regards

--
Tomas Vondra