Re: hashjoins vs. Bloom filters (yet again)

On Mon, Jul 13, 2026 at 10:17:28PM +0200, Tomas Vondra wrote:
> 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.

One topic that came up in the Pittsburgh AI Workshop was the idea of
combining indexes. For example, right now, all indexes point to heap,
and we usually go from index to heap. We can combine indexes using
bitmap scans of heap tids. Would there be any value of improving our
ability to combine indexes beyond bitmap scans?

--
Bruce Momjian <bruce(at)momjian(dot)us> https://momjian.us
EDB https://enterprisedb.com

Do not let urgent matters crowd out time for investment in the future.