M2c.3: Predicate transfer and runtime join filters
- Dominant language
- Mojo
- Stars
- 1
- Forks
- 0
- Avg merge
- 1h 31m
- Merged PRs (30d)
- 640
Description
Part of #372. Depends on #377. The design is `docs/specs/planner/04-predicate-transfer.md` and `docs/specs/planner/06-runtime-filters.md`.
This is the strategy, and it is why #379 is short. The classical answer to making joins fast is to find the right join order, finding the right order requires cardinality estimates, and the Join Order Benchmark result is that estimates for joins of three or more relations are wrong by orders of magnitude in every system tested. Predicate Transfer (CIDR 2024) and Robust Predicate Transfer (SIGMOD 2025) sidestep most of that: filter every table by what every other table implies about it before joining anything, and the join order then stops mattering very much. Their DuckDB integration measures the ratio between the worst and best random join order dropping to 1.6 on an acyclic query, and 1.5 times end to end as a geometric mean, over all of TPC-H, JOB and TPC-DS.
Two of the hand written TPC-H queries in our own driver are special cases of this done by hand, and they were worth a factor of two on q7 and a fifth on q19.
## The filter
One representation, shared with the runtime half below, chosen by distinct count.
- [ ] A blocked Bloom filter over the 64 bit hashes the join already computes, sized from the exact build count, one block resident in L1
- [ ] An IN list below about sixty four distinct keys, which is `firepanda/kernel/member.mojo` and already exists
- [ ] Minimum and maximum always, because they cost two comparisons during the build and they are what allows a whole morsel to be skipped rather than each row tested
- [ ] Applying a filter to a column as a mask, which the parallel filter kernel then compacts
- [ ] Applying a filter inside the probe loop when the consumer is adjacent, because producing a mask and compacting moves bytes and testing before the hash lookup does not
## The transfer
- [ ] The transfer graph, nodes are scans and edges are equality conditions, built from the bound plan after predicate pushdown so the pushed predicates are the seeds
- [ ] LargestRoot, a maximum spanning tree weighted by the smaller endpoint's cardinality and rooted at the largest relation
- [ ] The forward pass, leaves to root
- [ ] The backward pass, root to leaves
- [ ] The cyclic case, taking the spanning tree and accepting the weaker guarantee
- [ ] The escape hatch, skipping entirely when the query has fewer than two equality joins
## The runtime half
Same machinery, different decider. A runtime filter is free because the build side hash table was being built anyway, and it cannot reach a relation several joins away because those joins have not started. Predicate transfer can, and pays for extra passes to do it.
- [ ] Join filters built as a side effect of the hash join build and handed to the probe side
- [ ] The escape hatch, skipping when the build side is not meaningfully smaller than the probe side
## Done when
The ratio between the fastest and slowest execution of a query over randomly permuted join orders is under 2, measured on the six join heavy TPC-H queries, which are q5, q8, q9, q10, q20 and q21.
Contributor guide
Research direction
Start by reading docs/specs/planner/04-predicate-transfer.md and docs/specs/planner/06-runtime-filters.md, then inspect firepanda/kernel/member.mojo for the existing IN-list machinery. Trace the bound plan and hash-join build/probe paths before implementing the listed transfer and runtime-filter stages; done means the six specified TPC-H queries have a fastest-to-slowest randomized join-order ratio under 2.
Written by the indexing model from the issue text.
Assessment
- Domain
- data-engineering, databases, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100