Re: hashjoins vs. Bloom filters (yet again)

On 7/14/26 00:51, Matheus Alcantara wrote:
> On Mon Jul 13, 2026 at 5:17 PM -03, Tomas Vondra wrote:
>> ...
>>
>> 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).
>

Which last patch you mean? The v4 creates the scan paths with filters at
the beginning of the planning, which seems exactly the opposite to the
post-processing approach. Which means it can change the join order, it
can change which join algorithms we selected, etc.

The approach in v1 is what I'd call post-processing, as it made the
decisions in createplan, after everything else was already decided. It
could not change join order or join algorithms, it was entirely
opportunistic.

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

Some engines may do that unconditionally in the post-planning phase. It
can't change the plan anyway, so why bother with costing, right? But
then they still do some cost/benefit decisions at execution time, either
when deciding to build the filters, or to disable filters that turn out
to be ineffective.

As for the expected vs actual difference, I think this would be a big
issue, because it'd make EXPLAIN output utterly confusing. I don't think
I could convince myself to commit that into core ...

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

Yeah. I don't think we need to support "partition pruning" right away,
more like an interesting future improvement. In a way, it's not all that
different from pruning blocks in a CustomScan or something, except it'd
be done by a node somewhere higher in the plan.

regards

--
Tomas Vondra