#1963 [Ideas] Implement Robust Predicate Transfer (RPT+) on top of Anser New discussion created by leborchuk Description The references, precisely | What | Where | Note | | ----------------------- | -------------------------------------------------------------------------------------------- | --------------------------------------------- | | RPT paper | Junyi Zhao et. all Debunking the Myth of Join Ordering: Toward Robust SQL Analytics | https://arxiv.org/pdf/2502.15181 | | DuckDB RPT extension | https://github.com/robust-sql/robust | this is the baseline RPT | | RPT+ paper | Yiming Qiao, Peter Boncz, Huanchen Zhang, Robust Predicate Transfer with Dynamic Execution | https://vldb.org/pvldb/vol19/p1278-qiao.pdf | | DuckDB RPT+ extension | https://github.com/embryo-labs/dynamic-predicate-transfer | this is RPT+ | Read both repos, but know which is which:

robust-sql/robust

implements plain Predicate Transfer (DuckDB's native bloom filter, 12 bits/key; reports 1.76× geomean on JOB), while the paper is specifically about fixing RPT's overhead and regressions. ⚠️ Licensing. Cloudberry is Apache-2.0. Check the license of both repos before reusing even a snippet, and prefer implementing from the paper. If you do reuse anything, it needs attribution plus `LICENSE`/`NOTICE` handling — raise it in the PR rather than deciding alone. What the paper actually proposes RPT (the baseline) makes Yannakakis' algorithm practical: model the query as a join graph

G(V,E)

where edge weight = number of shared join attributes, build a maximum spanning tree rooted at the largest table (

LargestRoot

), then propagate bloom filters over that tree in a forward pass (leaves→root) and a backward pass (root→leaves), fully reducing tables before the join phase. Its weakness: it ignores equivalence relationships between join keys, producing redundant and oversized filters, and pays heavy scan + BF-construction overhead — enough to cause real regressions. RPT+ adds three things: 1. Asymmetric Transfer Plan (ATP) — different tree shapes for the two passes, because they do different jobs. Forward = collect information, so a deep chaining tree is best (filter table i before building the filter for i+1, avoiding oversized BFs). Backward = distribute information, so a wide broadcast tree is best (build the final filter once and reuse it for every table in the same equivalence class). Chains for different equivalence classes are linked through "bridge tables" (the root of each class's induced subtree). 2. Cascade filters — min/max for block-level skipping plus a bloom filter for tuple-level filtering, applied coarse-to-fine. 3. Dynamic pipelines — runtime selectivity monitoring that abandons filter construction when it will not pay off (Algorithm 2 in §5.2). Reported speedups over DuckDB v1.3.0: 1.47× JOB, 1.28× SQLStorm, 1.17× TPC-H, 1.01× Appian, "avoid[ing] the significant performance regressions observed with the original RPT". Constants from §5.5, use these as starting values, do not invent your own: | Parameter | Value | Meaning | | ---------- | ------------------------------- | ----------------------------------------------------- | | γ | 100 K tuples | rows observed before deciding | | τ_sel | 0.35 | abandon if > 35% of tuples survive | | τ_prog | 0.6 | only abandon while < 60% through the scan | | M_avail | 64 GB | memory budget for materialization | | τ_stop | 0.9 | stop probing a filter that rejects too little | | filter | 20 bits/key, 7 hash functions | FPR 6.1×10⁻⁵ | | probe cost | 2.48 cycles/tuple | 64-byte cache-line blocks, 32-bit sectors, VPGATHERDD | Sampling is sequential, not random — random access breaks streaming execution. On JOB, τ_sel in 0.1-0.3 gave the best speedups; τ_sel = 0 (drop almost everything) hurt. Why Anser fits — and the one place it does not | RPT+ concept | Anser today | Gap | | ----------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------- | | equivalence class of join attributes | condition_key — anser.h documents it as exactly "the optimizer-generated equivalence-class symbols" | naming only | | backward pass: build the final filter once, broadcast to every table in the class | one channel per condition, union once at the coordinator, deliver to every registered consumer | already implemented | | combining filters built by different workers | gather service folds parts by bitwise OR | already implemented (the paper is single-node; this is our addition) | | forward pass: chaining, table i reduced before it builds the filter for i+1 | channels are independent, with no ordering between them | the hard part — see below | | dynamic pipeline abandonment (Alg. 2) | never abandons | overlaps Issue 2 task 2.4 | | cascade filter, blocked/sectorized BF | classic bloom: k random bitset accesses | overlaps Issue 2 tasks 2.1/2.3 | | one filter per (table, equivalence class) | plan pass injects one producer+consumer per hash join | needs join-graph analysis in anserplan.c | Anser's backward pass is essentially free — it is what the extension already does. The forward chaining pass is where this project lives or dies, for a reason that does not exist in DuckDB: • In DuckDB, a chain hop is an in-process pipeline breaker: microseconds of coordination. • In Anser, every hop is a global barrier: all segments publish → coordinator unions → all segments receive. One hop costs a full segment→QD→segment rendezvous. JOB queries join 5-10 tables, i.e. 4-9 sequential hops. If one hop costs ~30 ms, a 7-table chain adds ~200 ms of pure latency to a query whose total runtime may be under a second. That arithmetic, with a measured hop latency, decides whether M3 below is worth attempting at all. ⚠️ Correctness rule you must not get wrong. It is tempting to do the forward chaining locally on each segment and avoid the barrier. That is only correct when the tables are co-distributed on the join key. Otherwise segment s holds only part of table _j_'s key set, and filtering table j+1 with it drops row… apache/cloudberry