Re: hashjoins vs. Bloom filters (yet again)

On 7/7/26 20:39, Tomas Vondra wrote:
> ...
>
>> i haven't hard time to read the paper to which you linked, but I do
>> sort of feel like knowing what the practical experience has been in
>> other systems might be important. Theoretically there are good
>> arguments for and against additional planning effort, but what happens
>> in practice is not clear to me.
>>
>
> That's a good idea, but I'm not aware of an open source database
> implementing this :-(
>

I still think the paper is the best source for what I'm trying to do in
this thread (more about that later). But your question regarding what
are the other databases doing, and the pros/cons of the approaches, is
perfectly reasonable.

I said I'm not aware of another open source database implementing this
stuff, but that's partially because I did not search for it. So over the
past couple days I did that - tried looking for databases (preferably
open source ones) implementing some variant of this feature ...

And indeed - I found databases implementing features like this. It may
be called "runtime filter", "dynamic filter" or "join filter" (and I'm
sure there are more names for this).

AFAIK none implements the approach described in the paper. Which is not
that surprising, as the paper is quite new (although, others might have
come up with the approach independently, ofc). But also because some of
the databases are not doing "our" bottom-up planning.

I did look at these databases: DuckDB, ClickHouse, Spark, Trino, Impala,
Hive and a couple others. Most of these are analytical databases, some
are MPP/distributed engines, etc. Which is not surprising, the filter
pushdown is irrelevant for OLTP workloads, it's analytical feature.

A lot of this is based on docs I found / googling stuff / ... I did try
to verify as much as humanly possible in acceptable amount of time,
including looking at the code doing that. Which was pretty difficult,
because most of the code seems pretty unreadable - maybe the C++ is
simply incomprehensible to me, or maybe I'd need more time to get
familiar with the various code bases. Or maybe we managed to make the
Postgres code very readable. Not sure.

Anyway, there still might be some mistakes / inaccuracies, sorry about
that. Please call them out.

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.

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.

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.

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.

That's all I have at this point. TBH I'm not sure how much useful stuff
we learned from this :-(

[1] https://blobs.duckdb.org/slides/DiDi.pdf

[2] https://duckdb.org/library/robust-predicate-transfer/

[3]
https://people.iiis.tsinghua.edu.cn/~huanchen/publications/rpt+-vldb26.pdf

--
Tomas Vondra