Re: hashjoins vs. Bloom filters (yet again)

On Mon Jul 6, 2026 at 10:34 AM -03, Tomas Vondra wrote:
> I took a quick look at the v4 patches adding the earlier patches from
> Andrew,, and I think it looks sensible enough for a PoC. Thanks!
>
> I think it'd make sense to split some of these into separate commits, as
> it's not necessarily tied to just CustomScan nodes. And even if it is,
> it can be a separate easier-to-review change.
>
> I propose we move these two "features" into separate commits:
>
> - "eager" creation of filters
>
> - requesting per-key filters
>

Yes, I agree.

> I think it might be useful for other scans (or even non-scan nodes, if
> we choose to allow filter pushdown for these). And it should be a
> "generic" thing so that find_bloom_filter_recipient does not need to
> check if the recipient is CustomScan. In fact, I think this should be
> part of the information about expected filters "propagated" up during
> planning.
>

Agree.

> FWIW It might make sense to show these things in the explain, at least
> for development. AFAICS the CustomScan (used by the tests in 0003) does
> not actually print the filters, right? And I'm not sure if the per-key
> filters will be printed at all. But that's minor / easy to fix.
>

Yeah, it does not print the filters. Also agree with showing this on
explain.

> To move this whole thing forward, we'll need to figure out what to do
> about the *big* questions. The four main ones I can think of (based on
> memory and skimming the XXX comments in the patches) are:
>

I've been thinking about these CustomScan issues but I'll focus more on
it once we resolve the questions 1 and 2.

> For (1) and (2), I think we need to make this work more like how we
> build paths for pathkeys. Do some sort of initial selection of
> interesting filters, without trying to be very smart. So we'd maybe
> check the filter discards > 30% of tuples, but without trying to keep
> only the "top three" filters.
>
> Then we'd generate the paths for all the possible combinations of
> filters, not by cloning but by passing the expected filters to the
> create_ function, and constructing a new path. If the scan can do
> something smart - cool, it'd calculate the cost. In the worst case it'd
> apply the filter at the end, with the generic cost / rows adjustment.
>
> The paths with matching expected filters would still compete (just like
> for matching pathkeys), of course.
>
> There's still need to be some limits, though. If the table has 10 joins,
> we can't generate paths for each possible combination of filters, that'd
> be 2^10 combinations. But there are some inherent limits too, I think.
> For example, once we discard ~90% tuples it probably does not make much
> sense to keep applying additional filters. If each filter discards ~50%
> tuples, that's 3 filters. So even with 10 joins we'd be limited to ~120
> paths (which is still a lot, but way lower than 2^10).
>
> We could still have some "heuristics" limits too, e.g. don't keep all
> these paths, but prune them very aggressively and pick only the best
> ones - just like we do now by only picking 3 most selective filters,
> except that we'd do that based on proper costing (and not selectivity).
>
>

This make sense to me as a direction. I've been sketching this idea and
here is my attempt to implement. This is still a PoC, it still need more
polishment but I've wrote some comments and commit message to try to
explain the idea.

For (1), the candidate selection no longer picks the "top three" most
selective filters. It still requires a candidate to discard at least
bloom_filter_pushdown_threshold (30% by default) of the rel's tuples,
but every candidate clearing that bar is kept, with no count-based trim.

For (2), combinations are now generated breadth-first by increasing size
instead of enumerating every non-empty subset, and a combination stops
growing once its combined selectivity drops below a new
bloom_filter_pushdown_combination_floor GUC (0.1 by default).
bloom_filter_pushdown_max now caps how many filters can be combined into
one path rather than how many candidates survive. So, with ~50%
selective filters, growth stops around 3 deep regardless of how many
candidates exist, so 10 joins doesn't turn into 2^10 paths.

Each combination is passed straight into the real create_*_path
constructor for its scan type instead of being produced by cloning an
already-costed path. A new apply_expected_filters() helper is the
generic "cost/rows adjustment" fallback: it charges one
cpu_operator_cost per filter per tuple on top of shrinking the row
estimate, so filtering is no longer free. IndexPath is the one exception
still handled by cloning, since create_index_path() would just
redundantly re-derive indexclauses/pathkeys for no benefit, perhaps I
think that we can improve this. For CustomPath, core can't safely clone
or construct one at all. So it doesn't touch CustomPath for this anymore
— a provider that wants filter-aware CustomPaths builds them itself,
using the new exported filter-combination function and either costing
them for real or falling back to the same generic adjustment core uses.

Paths with differing expected filters still never dominate each other in
add_path, so they compete on cost exactly like paths with different
pathkeys do, same as in v4.

This is implemented in 0005; the other patches are the same as those in
v4. I think we can try combining some of these patches. Perhaps 0001 and
0002?

Appreciate comments on whether this make sense or not.

--
Matheus Alcantara
EDB: https://www.enterprisedb.com