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
