Re: hashjoins vs. Bloom filters (yet again)

On Mon Jul 13, 2026 at 5:17 PM -03, Tomas Vondra wrote:
> I'll discuss the things shared by most of the databases first, and then
> will talk about the interesting bits where the approaches differ.
>
>
> 1) filter types
>
> The main thing shared by most of the databases is the types of filters
> supported. Most of the databases support these three kinds of filters:
>
> * Bloom filters
> * exact "IN" list of values
> * min/max range filter
>
> There are some differences in how the filter type gets selected,
> sometimes the filter is "hybrid" and combines e.g. Bloom + min/max. Most
> of these differences seem minor, and depend on how exactly the database
> uses the filter.
>
> For example, min/max filter allows efficient pruning of zonemaps (which
> are pretty similar to our BRIN minmax indexes).
>
> That kind of stuff. I guess this would be up to the CustomScan to decide
> what kind of filters it can leverage.
>
> My conclusion from this is that we should aim for "generic" filter, not
> just for Bloom filters. Which just validates the points made earlier in
> this thread, so that's good.
>

+1. I think that a generic filter API make totatly sense.

>
> 2) impact on planning
>
> The main differences seem to be in how the filters affect planning, i.e.
> at which point are they selected, and how they affect the plan shape (if
> at all).
>
> While the databases do planning in different ways (some are top-down,
> other bottom-up), it seems all of them decide filters in some
> post-processing phase, after the overall plan shape was selected.
>
> For example DuckDB has a rule-based optimizer, which applies various
> optimization transformations on the plan, in a particular sequence. And
> the filter selection is one such "optimizer" pass, which runs after the
> join order has already been selected (so the filters probably can't
> affect that aspect).
>
> If you look at slide 137 "Order of Optimization Passes in DuckDB
> (version 1.5)" in [1], then it lists "join_filter_pushdown" as pass 31
> at the very end, including join_order etc.
>
> Note: There are two papers [1][2] about "Robust Predicate Transfer" in
> DuckDB, describing a much more elaborate way to decide filters, but
> AFAIK both are experimental/research implementations, not something
> DuckDB already does.
>
> The other databases seem to do planning in similar ways, i.e. as
> post-processing on already selected plan. Obviously, the exact point at
> which it happens is different.
>
>

Trino also have rule-based optmizer that apply the pushdown filtering
[1].

"Extensible query optimizers in practice" [2] book also briefly mention
Catalyst which is an extensinble query optmiser for Spark SQL which also
implement filtering pushdown using rules (section 3.4).

I am inclined to think that Postgres should do something similar and
have a post planning phase to create these filters (which IIUC it is the
architecture that the last patches is based on).

> 3) heuristics
>
> There seem to be different heuristics when deciding whether to create a
> filter or not, but I've been unable to compile a good overview. Some of
> the heuristics is very closely tied to details of the MPP plan (which
> fragments are "local" and "global", ...).
>
> But generally, the heuristics are pretty "expected" - estimate the
> filter selectivity, and if the filter does not eliminate enough tuples,
> then don't use the filter.
>

It seems to me that some implementations just assume that pushing down
filters is always beneficial, so at post-planning phase it always push
down the filters. I did not manage to play with the expected/actual
costing on Duckdb to see how the filtering pushdown changes the
expected/actual values, but for Trino it decide if it should push down
the filters after the costs are evaluated, so when filtering push down
is present on query plan we see a difference on expected / actual
costing values.

It also seems to me that another option is some kind of "rule based"
behavior to decide if the filtering push down should exists or not, e.g
if the join keys match some criteria just push the filter down and don't
care if it's worth or not. Paper "Materialization Strategies in the
Vertica Analytic Database: Lessons Learned" [3] present Sideways
Information Passing (SIP) (which is filtering push down generally
speaking) and it has some rules to decide if the push down should happen
or not.

>
> 4) partition pruning
>
> One interesting idea is that Apache Spark SQL apparently can use the
> filter to prune partitions (feature "dynamic partition pruning"). Which
> seem to be "partitions" in the sense we use. The other sysstems (like
> Impala) can of course use the filter to prune stuff at the storage level
> (so something a CustomScan would do).
>
> But the partition pruning seems like an interesting option. I haven't
> really considered using filters for that before.
>

IIRC Trino also implement partition pruning with dynamic filtering. I
think that is something that we can consider to discuss. Just don't know
yet how the current discussed architecture would fit for this.

[1] https://github.com/trinodb/trino/blob/master/core/trino-main/src/main/java/io/trino/sql/planner/PlanOptimizers.java#L584
[2] https://www.microsoft.com/en-us/research/wp-content/uploads/2024/12/Extensible-Query-Optimizers-in-Practice.pdf
[3] https://15721.courses.cs.cmu.edu/spring2020/papers/13-execution/shrinivas-icde2013.pdf

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