hashjoins vs. Bloom filters (yet again)

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.

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.

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'd be happy to work on patches for these.

cheers

andrew

--
Andrew Dunstan
EDB:https://www.enterprisedb.com

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

On 2026-05-30 Sa 2:14 PM, Tomas Vondra wrote:

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.

Here are 3 patches (developed using Claude) that sit on top of your POC.

Patch 1 enables the pushdown filters for custom scans. As you say it's
fairly mechanical and is enabled by a CUSTOMPATH_SUPPORT_BLOOM_FILTERS
path flag.

Patch 2 provides for building per-key filters in addition to the
multi-key filter if that flag is set. There may be other cases that
would want it, but this would suit my immediate use case.

Patch 3 provides for eager creation of the filter(s) in such cases,
disabling the optimization you mentioned in point 1 above.

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

I haven't dealt with that or other issues you raise, but I think this is
enough for me to begin testing. I have adapted my TAM to it and verified
that it acts as expected. I will start doing some benchmarks.

cheers

andrew

--
Andrew Dunstan
EDB: https://www.enterprisedb.com

Postgres is still gaining ground in this area. It’s helpful to see how other
databases handle these challenges.

On 30/05/2026 02:55, Tomas Vondra wrote:

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

We ran into the same problem when trying to estimate the number of 'generated'
NULLs on the nullable side. So, it makes sense to focus on the estimation method
for 'unmatched' tuples as a separate task.

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?

Looking at DuckDB’s code, using bloom filters during hash table construction
solves this issue.
From what I can tell, Apache Impala [1]https://impala.apache.org/docs/build/html/topics/impala_runtime_filtering.html and Spark [2]https://docs.aws.amazon.com/emr/latest/ReleaseGuide/emr-spark-performance.html use the same approach.

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.

In my experience, the outer side often has a complex subtree and is sometimes
capped by a GROUP BY statement, or even a HAVING clause, which can break all
estimations. A bloom filter might help if there is an accidental misestimate.

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.

This approach should not cause any issues. It is likely a reasonable way to
improve performance without expanding the optimisation scope, which would
increase planning time. We can always adjust it later if needed.
For example, I am designing the post-optimising NestLoop 'lazy join' [3]/messages/by-id/3d749085-72b6-46d6-a26a-7c95805c1adb@gmail.com using
the 'gating' concept.

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.

People are often confused when trying to understand the correctness of
estimation for parallel plans and, in some cases, MergeJoin plans. Personally, I
don't think it's a big issue.

Overall, I think there are even more useful ways to apply bloom filters in the
planner:
1. Real-time partition pruning
2. FDW pushed-down filters, which are especially helpful for sharded tables.
3. Skipping storage layer blocks. I know of at least one attempt to use the
BRIN+FSM approach to avoid reading parts of a large table that definitely don't
match the filter. Bloom filters could be used here as well.

So, I'm excited about your proposal. Even if you start with a simple case, just
make it available for extension modules.

[1]: https://impala.apache.org/docs/build/html/topics/impala_runtime_filtering.html
[2]: https://docs.aws.amazon.com/emr/latest/ReleaseGuide/emr-spark-performance.html
[3]: /messages/by-id/3d749085-72b6-46d6-a26a-7c95805c1adb@gmail.com
/messages/by-id/3d749085-72b6-46d6-a26a-7c95805c1adb@gmail.com

--
regards, Andrei Lepikhov,
pgEdge

On 30/05/2026 02:55, Tomas Vondra wrote:

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.

I overlooked this part of your first message, so let me add a quick comment.

In principle, the optimiser is not restricted to bottom-up planning. For
example, in extension modules, I sometimes use the create_upper_paths_hook to
add a 'Top-Down' iteration after 'bottom-up' planning [1]https://github.com/danolivo/conf/blob/main/2025-MiddleOut/MiddleOut.pdf.

This helps improve complex query plans, such as adding a Memoize node at the
head of a subplan when the number of distinct input parameter values is expected
to be low. It can also use the startup_cost-optimal subpaths in MergeJoin if
histogram comparisons indicate that only a small portion of the input will be
scanned. There are other possible cases involving LIMIT and sort propagation as
well.

I'm not sure whether this approach makes sense for the specific technique you
develop, since it's already quite complex. Also, additional planning iteration
is a pure overhead in most of cases except complex analytical queries. However,
it might provide an idea for future improvement.

[1]: https://github.com/danolivo/conf/blob/main/2025-MiddleOut/MiddleOut.pdf

--
regards, Andrei Lepikhov,
pgEdge

Hi,

I kept thinking about the various issues discussed after I posted the v1
pshdown patch. Some of the issues are specific to the pushdown (to scan
nodes), but a lot of the issues seem to be shared with using Bloom
filters within the hashjoin (which is what the old threads were about).

We'd need to do something about these issues no matter where we place
the filter, so it's a bit of prerequisite for using Bloom in hash joins
in general. And they seem somewhat more limited / easier to solve than
the planning/costing issues.

So I decided it'd be interesting to see how beneficial can the Bloom
filters be in the scope of a single hashjoin, without pushing it all the
way to the scan nodes, and see what we can do about the issues.

Attached is a PoC patch series optinally adding Bloom filters to a hash
join, both for serial and parallel joins. It's labeled as v2, but it's
really independent of the v1 pushdoown patch posted last week. Some of
the ideas implemented in this could be applied to the pushdown patch too
(in particular all the adaptive behavior).

I'm not sure if we should try to merge these two things into a single
patch series, or whether it'd be better to split those into two threads
(otherwise it'll just keep confusing both people and cfbot).

how the patch works
-------------------

Anyway, let me briefly explain what the patch does (see the commit
messages and comments for more details, I tried to keep those
comprehensive). I suggest focusing on the serial case (in 0001), the
parallel joins are a direct extension of that - but inherently harder to
understand, due to the parallel hash build, shmem etc.

In principle, using Bloom filters is pretty simple - while adding tuples
from the inner relation to the hash table, build also a Bloom filter and
then use it to discard outer tuples cheaply, without having to do an
expensive lookup in a hash table. It does not depend if the hash table
is in private or shared memory.

The difficulty is to figure out whether it makes sense to build/probe
the filter. For that to be the case, the filter needs to eliminate
enough outer tuples, so that the hash table lookup is not needed, and/or
the tuple can be discarded without spilling it to disk (with nbatch>1).

Note: With the pushdown, the benefits "compound" by combining multiple
filters (if there are multiple joins) and/or by skipping some
intermediate operators (between the scan and the hashjoin). So it's
maybe less risky, but the issue still exists.

adaptive build / probing
------------------------

I see two complementary ways to deal with this - during planning (based
on estimates and a cost model), and adaptively during execution (based
on probe/lookup stats). The v2 patch does the latter, mostly because I
think it's beneficial even if we eventually add some smarts to the
planning phase.

The adaptive behavior decides (a) when a filter is built, and (b) if a
filter is probed before hash table lookups.

For builds, we don't want to build filters when ~100% of lookups in the
hash table find a match. It'd not pay for itself. So when the hash table
fits into memory (nbatch=1), we wait for the first 1000 lookups, and
only build the filter only if <90% have a match (and recheck once in a
while, so the filter may be built later).

But with batched joins (nbatch>1) we can't delay building the filter, we
have to decide before spilling some of the tuples to disk (otherwise the
filter would be incomplete, and we couldn't reject tuples from later
batches - which is the main benefit with batched joins). So with batched
joins we build the filter, and hope that either it helps, or the
overhead is negligible overall.

Then when probing, we don't want to use filter that does not reject any
tuples. To deal with this, the patch tracks number of probes and number
of rejections, and if fewer than 10% of probes reject the tuple (i.e.
the filter is ineffective), it gets temporarily "disabled". When
disabled, a filter samples 1% of probes, and then may get enabled again
if the fraction of rejected tuples gets >20%.

Overall, this seems to work pretty well. Of course, it can be improved
in various ways. For example, the thresholds 10% and 20% are somewhat
arbitrary - it's based on earlier experiments, and it works OK on a
number of machines, with different queries / data types. But having a
more formal "cost model" for Bloom filters might help.

Another possible improvement is about maybe doing some decisions during
planning, particularly when the decisions are reliable. I'm rather
skeptical about deciding to build a Bloom filter based on estimates. I
think it's better to do that decision during execution, as explained in
the preceding sections. We could still consider the "expected" Bloom
filter for costing purposed, but leave the decision for execution.

However, in some cases we may be able to know for sure a Bloom filter is
useless. For example, if we know a given join is on a FK, every outer
tuple will have a match. In that case the filter can't help. The patch
won't build it anyway (at least for nbatch=1), thanks to the adaptive
build heuristics. But we could short-circuit that entirely.

perf evaluation
---------------

Now, some numbers. Attached is a .tgz with benchmark script running a
hashjoin on two tables (fact-dimension), varying the selectivity of the
join (5%-100%), work_mem, number of parallel workers, data types of the
join keys, and size of the tables. There's a .csv with more complete
results of the tests, I'll focus on results for scale 100, i.e. fact
100M rows, dimension 10M rows.

The two attached PDFs show timings for master + patched branch, with
enable_hashjoin_bloomm=on/off. And then columns showing timing relative
to master (<1.0 speedup / green, >1.0 regression / red). Green = good.
BTW this is from my ryzen machine (Ryzen 9 9900X).

The results for serial queries (workers=0) seem pretty nice. For
selective joins (>50% outer tuples discarded) it's about 20% faster, and
with 5% selectivity (95% discarded), it's ~2x faster. Which seems nice.
The adaptive thresholds seem to about match reality.

For parallel queries it's a bit worse. There are some nice speedups, but
the benefits are clearly more limited. One interesting observation is
that while for serial queries, the cases that most benefit are with
batching, while with parallel joins it's exactly the opposite. See the
hashjoin-bloom-batched.pdf, which shows timings only for queries with
batched joins.

I'm not sure why is that, but it's entirely possible it's due to a bug
in the patch - the parallel join is fairly complex, I can't rule this
out. Or it might be due to some hardware bottlenecks or whatever?

I'd definitely welcome some review and ideas what might be causing this.

One thing I realized when looking at the results is that this may need
some different trade offs regarding the size of the filter. The library
lib/bloomfilter.c aims for 1-2% false positive rate, but we sometimes
end up with a filter like this:

Bloom Filter: Size: 16384kB Hash Functions: 10
False Positive Rate: 0.077%

This is for work_mem=64MB, with batched join:

Buckets: 2097152 Batches: 16 Memory Usage: 82784kB

so maybe it's not that large. But maybe it'd be better to accept
somewhat higher false-positive rate (e.g. ~10%) in exchange for a much
smaller filter, and fewer hash functions (i.e. fewer bits to check)?

regards

--
Tomas Vondra

On 5/31/26 17:03, Andrew Dunstan wrote:

..>
Here are 3 patches (developed using Claude) that sit on top of your POC.

Patch 1 enables the pushdown filters for custom scans. As you say it's
fairly mechanical and is enabled by a CUSTOMPATH_SUPPORT_BLOOM_FILTERS
path flag.

Patch 2 provides for building per-key filters in addition to the multi-
key filter if that flag is set. There may be other cases that would want
it, but this would suit my immediate use case.

Patch 3 provides for eager creation of the filter(s) in such cases,
disabling the optimization you mentioned in point 1 above.

Thanks. I'll take a look when I have time.

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

I haven't dealt with that or other issues you raise, but I think this is
enough for me to begin testing. I have adapted my TAM to it and verified
that it acts as expected. I will start doing some benchmarks.

OK. I think it's enough for testing, i.e. to see if it's actually worth
pursuing further. But I think we'll eventually need to solve the issues
planning/costing somehow. I'm not sure it'll be committable without
having some sort of solution.

I happened to find this 2025 paper:

Including Bloom Filters in Bottom-up Optimization
https://arxiv.org/html/2505.02994v1

I read it over the weekend, and interestingly enough it's exactly about
the planning issues I outlined last week, i.e. difficulties with costing
paths that might include pushed-down Bloom filters.

They even describe a solution that kinda looks a bit like "tracking a
separate set of paths" from my e-mail, although they use somewhat
different terminology (sub-plan == our path, etc.). But if you squint a
little bit, it talks about the costing issue, path explosion, etc.

Their solutions is some sort of two-phase process, which I'm not sure we
can do. It'd require a fundamental rework of how we construct join rels
and all that, and TBH I don't have an ambition to do that.

But while reading the paper, I kept thinking about how we deal with
pathkeys. I wonder if we could do something similar to that? That is,
have a concept of "potentially interesting" filters, and construct the
extra paths only for those, to limit the number of extra paths.

Imagine we construct the the baserels (essentially scan nodes), and then
do a pass over those. Each scan would look at what joins it participates
in, and which of those could benefit from a Bloom filter (some can't,
because it's a FK join, or we don't expect many rejected tuples, or
maybe it's a LEFT JOIN, ... etc.).

And then we'd maybe have some additional heuristics to pick which "Bloom
filters" to attach to the path. And then later, when planning that
particular join involving that path, we'd reject the join if it's not a
hash join. The scan would always have to construct a "clean path" not
requiring any filters, similarly to what custom scans need to do for
parallel paths.

It's just a rough idea, but I think it would work. Worth a try.

regards

--
Tomas Vondra

On 6/1/26 11:30, Andrei Lepikhov wrote:

Postgres is still gaining ground in this area. It’s helpful to see how other
databases handle these challenges.

On 30/05/2026 02:55, Tomas Vondra wrote:

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

We ran into the same problem when trying to estimate the number of 'generated'
NULLs on the nullable side. So, it makes sense to focus on the estimation method
for 'unmatched' tuples as a separate task.

Not sure how treating it as a separate task solves that? In any case,
the patches I posted a couple minutes ago (for filters in the scope of a
single hashjoin, but the problem is the same) deal with this by delaying
the build until execution time, when we have better idea how many outer
tuples match the hash table.

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?

Looking at DuckDB’s code, using bloom filters during hash table construction
solves this issue.
From what I can tell, Apache Impala [1] and Spark [2] use the same approach.

It's not clear how any of these solve the issue I described (about
sizing the filter and the trade offs). The links just say that the
feature exist.

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.

In my experience, the outer side often has a complex subtree and is sometimes
capped by a GROUP BY statement, or even a HAVING clause, which can break all
estimations. A bloom filter might help if there is an accidental misestimate.

Perhaps, but with substantial misestimates all bets are off. Maybe it'd
be better to discuss a particular example.

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.

This approach should not cause any issues. It is likely a reasonable way to
improve performance without expanding the optimisation scope, which would
increase planning time. We can always adjust it later if needed.
For example, I am designing the post-optimising NestLoop 'lazy join' [3] using
the 'gating' concept.

I agree, except that it also makes EXPLAIN pretty difficult to
interpret, because it "breaks" the row counts.

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.

People are often confused when trying to understand the correctness of
estimation for parallel plans and, in some cases, MergeJoin plans. Personally, I
don't think it's a big issue.

I disagree. The fact that people may be confused by plans does not mean
we can just make plans confusing for everyone.

Overall, I think there are even more useful ways to apply bloom filters in the
planner:
1. Real-time partition pruning
2. FDW pushed-down filters, which are especially helpful for sharded tables.
3. Skipping storage layer blocks. I know of at least one attempt to use the
BRIN+FSM approach to avoid reading parts of a large table that definitely don't
match the filter. Bloom filters could be used here as well.

Could be. I speculated about options (2) and (3) myself elsewhere in
this thread.

regards

--
Tomas Vondra

On Sat, May 30, 2026, 01:56 Tomas Vondra <tomas@vondra.me> 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.

Bloom filters have two rather different roles here.

For a local Hash Join optimization, Bloom does not require any particular
physical ordering of the heap. It can be useful simply when the join is
selective enough, or when batching/spilling makes failed probes expensive:
the Bloom filter rejects many outer tuples before a full hash-table probe
or before writing them to temporary batches.

But once we talk about pushing a runtime filter down to the scan/storage
layer, the physical preconditions become crucial. To get more than a cheap
per-row check, the scan must have something coarse-grained to skip:
partitions, row groups, chunks, block ranges, dictionaries, min/max
metadata, BRIN-like summaries, etc. Without that, the filter is still
correct, but the benefit is mostly CPU/probe reduction rather than avoiding
data production.

So for me the most interesting part of this thread is not Bloom itself, but
the architectural idea: pushing runtime knowledge down to the scan node,
against the normal direction of data flow. The build side of a join
produces compact knowledge about admissible keys, and lower layers may use
it before rows are materialized and sent upward.

I saw this in my own experiments with zone/chunk-oriented storage for
Postgres: static predicates could prune zones nicely, but joins were the
hard case because the useful filtering knowledge was produced above the
scan. A runtime semi-join filter pushed from the Hash Join build side into
the scan could turn join-derived knowledge into scan-level pruning.

For example:

SELECT sum(e.cost)
FROM events e
JOIN accounts a ON e.account_id = a.id
WHERE a.region = 'NP'; -- Nepal

The events scan does not know which account_id values are EU accounts. That
knowledge is produced above it, on the build side of the join. A runtime
semi-join filter pushed from the Hash Join build side down into the events
scan could let the scan reject impossible account_id values before
producing tuples.

For a plain heap scan this may mostly save hash probes. But with
zone/chunk-oriented storage, where chunks have dictionaries, min/max
metadata, Bloom summaries, or tenant ranges, the same runtime filter can
skip whole chunks. That is the part I find most interesting: turning
join-derived knowledge into scan-level pruning, against the normal
direction of data flow.

Bloom is just one carrier for that knowledge. The real feature is a
pluggable runtime-filter mechanism that heap, CustomScan, FDW,
columnar/table AMs, partitioned storage, or chunk/cold storage can consume
at the level they understand.

This may be a topic for a separate thread, because it quickly becomes less
about Hash Join Bloom filters and more about runtime knowledge pushdown
into storage.

On 6/3/26 11:20, Oleg Bartunov wrote:

...

Bloom filters have two rather different roles here.

For a local Hash Join optimization, Bloom does not require any
particular physical ordering of the heap. It can be useful simply when
the join is selective enough, or when batching/spilling makes failed
probes expensive: the Bloom filter rejects many outer tuples before a
full hash-table probe or before writing them to temporary batches.

Right. Adding a filter within a hash join is certainly less ambitious,
and the possible benefits are smaller.

But once we talk about pushing a runtime filter down to the scan/storage
layer, the physical preconditions become crucial. To get more than a
cheap per-row check, the scan must have something coarse-grained to
skip: partitions, row groups, chunks, block ranges, dictionaries, min/
max metadata, BRIN-like summaries, etc. Without that, the filter is
still correct, but the benefit is mostly CPU/probe reduction rather than
avoiding data production.

Maybe, but there's also ongoing work on adding batches to the executor,
in which case we'd eliminate "row groups" even when using a filter in
the scope of a hashjoin operator. Of course, the tuples will flow all
the way up to that operator.

So for me the most interesting part of this thread is not Bloom itself,
but the architectural idea: pushing runtime knowledge down to the scan
node, against the normal direction of data flow. The build side of a
join produces compact knowledge about admissible keys, and lower layers
may use it before rows are materialized and sent upward.

I saw this in my own experiments with zone/chunk-oriented storage for
Postgres: static predicates could prune zones nicely, but joins were the
hard case because the useful filtering knowledge was produced above the
scan. A runtime semi-join filter pushed from the Hash Join build side
into the scan could turn join-derived knowledge into scan-level pruning.

For example:

  SELECT sum(e.cost)
  FROM events e
  JOIN accounts a ON e.account_id = a.id <http://a.id&gt;
  WHERE a.region = 'NP'; -- Nepal

The events scan does not know which account_id values are EU accounts.
That knowledge is produced above it, on the build side of the join. A
runtime semi-join filter pushed from the Hash Join build side down into
the events scan could let the scan reject impossible account_id values
before producing tuples.

Yes. This is known as "predicate transfer" in academic papers.

For a plain heap scan this may mostly save hash probes. But with zone/
chunk-oriented storage, where chunks have dictionaries, min/max
metadata, Bloom summaries, or tenant ranges, the same runtime filter can
skip whole chunks. That is the part I find most interesting: turning
join-derived knowledge into scan-level pruning, against the normal
direction of data flow.

Bloom is just one carrier for that knowledge. The real feature is a
pluggable runtime-filter mechanism that heap, CustomScan, FDW, columnar/
table AMs, partitioned storage, or chunk/cold storage can consume at the
level they understand.

This may be a topic for a separate thread, because it quickly becomes
less about Hash Join Bloom filters and more about runtime knowledge
pushdown into storage.

Right, there's a general concept of a "filter", and Bloom filters are
just one example of that. And maybe we could build other types of
filters more suitable for the scan. But I think it'll still be tied to a
hash join, because what other nodes / joins can build the filter?

regards

--
Tomas Vondra