Re: hashjoins vs. Bloom filters (yet again)

On 7/13/26 21:26, Matheus Alcantara wrote:
> ...
>
> 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.
>

OK, thanks. I didn't have much time to do a thorough review yet, but let
me share at least some general feedback.

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

Makes sense. I've been working on allowing building filters on joins,
not just on baserels (per my message from a couple days ago), and I
think that'll also need relaxing this in some way (there are likely
quite a few possible join rels, more than 3).

I don't know if these default thresholds are reasonable - e.g. 0.1 seems
rather high, if the relation happens to be large it may easily be a
couple million rows etc. Maybe it'd be better to base this on number of
rows, not as a fraction. But not sure. I wonder if we could base this
heuristic on some approximate cost/benefit ratio instead.

FWIW I think we could take inspiration from the SIGMOD paper I mentioned
a couple times already - the authors do propose a bunch of heuristics to
decide which filters to build etc. There's a nice overview in section
3.10 of the paper. Some are a bit debatable, but most seem sensible.

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

Hmm, not sure what to do about indexpaths. Maybe we could have a
"filter" variant that takes an existing IndexPath as a source, and
reuses the indexclaused/pathkeys (without recalculating it). But then
still does whatever other adjustments are necessary.

> 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.
I think this will need some more though. I don't think we want to run
the find_interesting_bloom_filters() from scratch multiple times, it can
be fairly expensive. It'd be good to "cache" the filters somewhere, so
that the CustomScan can pick the filters from there. Say, we could stash
it in the RelOptInfo, right?

This will matter much more for filters on joins, because for that we'll
have to run a simplified version of the join enumeration, and that's
certainly not free. That can also cache stuff more aggressively (e.g.
the valid join relids can be calculated just once).

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

Yeah. The good thing is the new paths with filters still compete among
each other, so hopefully that eliminates a fair number of them. But I
wonder how effective that is, and whether we could introduce some more
heuristics to discard more of them.

The paper does describe a bunch of heuristics when generating candidate
filters for joins, but I think it also describes heuristics when adding
filters to a scan. But I don't recall the details.

It might also be interesting to try constructing queries that would be
affected by this (e.g. a fact with a bunch of dimensions with filters),
and measuring the practical impact. Can you give that a try?

> 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?
>

Yeah, it does not make much sense to keep 0001 around - it's the initial
approach doing the pushdown in createplan.c, and IMHO we agree that's
not the right approach. I only kept it around to make the 0002 changes
obvious, but we can get rid of 0001.

One comment - let's include the changes in expected output in each of
the patches, so that "make check" passes after each individual patch. I
think it makes debugging simple. V4 did it like that, but v5 seems to
move some of the output changes to the last part.

> Appreciate comments on whether this make sense or not.
>

I think it does. But as you say, there's plenty of stuff to figure out
and polish.

regards

--
Tomas Vondra