Repository navigation
Measure the downstream saving of an optional filter, instead of an estimate #25778
Description
Part of #22883. Follow-up to the optional filter gate in #25674.
Problem
The gate pauses an optional filter when eval_ns > removed_rows * saving_ns_per_row. Today, saving_ns_per_row is the work that the producer of the filter (for example a hash join) measures for each probe row without a match. If the producer has no measurement, the gate uses the tunable estimate optional_filter_min_saving_ns_per_row (default 20 ns).
A removed row can save much more than the producer work, or much less. The value depends on how far the row travels downstream:
| Plan | What a removed row saves | Real value (TPC-DS SF1) |
|---|---|---|
scan(store_sales) -> HashJoin(date_dim) (Q10, Q31) |
One hash and one lookup | 1.3 ns |
scan(lineitem) -> ... -> join -> aggregate (TPC-H Q17) |
Work of all operators up to the join | more than 12 ns |
scan(catalog_sales) -> join(inventory) (Q72) |
Output rows of a join with many matches | the query goes from 14.9 s to 0.28 s |
The producer cannot measure this:
- Starvation. A selective filter removes the rows before the producer sees them. In Q10 the date join saw 839 probe rows in total, fewer than
MIN_OBSERVED_ROWS, so the gate used the estimate. - Scope. The producer measures only its own work. It does not see the operators between the scan and the producer.
Evidence
Total CPU (EXPLAIN ANALYZE, ms, minimum of 3 runs). The columns show the leaf with the estimate set to 20, 5 and 0 ns:
| Query | pruning_only | est 20 | est 5 | est 0 |
|---|---|---|---|---|
| DS Q72 | 26655 | 279 | 396 | 14903 |
| DS Q54 | 60 | 21 | 58 | 61 |
| H Q17 | 477 | 295 | 471 | 464 |
| H Q20 | 159 | 110 | 160 | 151 |
| CB Q23 | 4891 | 1791 | 1641 | 2573 |
| DS Q10 | 68 | 75 | 80 | 75 |
The wins depend on the estimate. The estimate is also wrong where the regressions are:
| Filter | Saving that the gate used | Real work per removed row | Eval |
|---|---|---|---|
Q10 ss_sold_date_sk |
20 (estimate; producer starved) | 1.31 | 2.5 |
Q10 cd_demo_sk |
20 (estimate) | 4.55 | 7.7 |
Q69 ss_sold_date_sk |
20 (estimate) | 1.26 | 2.8 |
Prototype
| Part | Design |
|---|---|
| Measurement | For each input batch, the scan records the filter state (on or off), the input rows, the rows that the filter removed, and the time from the return of the batch to the next poll. |
| Estimate | saving = (median(off) - median(on)) / fraction removed while on, in ns for each input row |
| Probe | A site without an "off" sample pauses the filter once (initial_pause_batches), shared by all partitions and files |
| Floor | max(downstream, measured producer work), because the time stops at an exchange |
| Constants | None new |
Results (total CPU, ms, minimum of 3):
| Query | leaf est 20 | est 20 | est 5 | est 0 |
|---|---|---|---|---|
| DS Q72 | 279 | 617 | 540 | 718 |
| H Q17 | 295 | 347 | 304 | 346 |
| H Q20 | 110 | 124 | 119 | 121 |
| CB Q23 | 1791 | 1621 | 1611 | 1881 |
| DS Q54 | 21 | 57 | 57 | 57 |
| DS Q79 | 117 | 110 | 148 | 147 |
| DS Q10 | 75 | 76 | 75 | 78 |
For H Q17, H Q20, CB Q23 and DS Q72, the decisions no longer depend on the estimate. The prototype is not ready because of the failure modes below.
Failure modes
| Mode | Example | Numbers |
|---|---|---|
| The probe is not free | DS Q72: the probe lets catalog_sales rows into the join with inventory |
279 → 617 ms |
| The probe is not free | DS Q54: a probe on a filter that removes all rows of customer_address puts 32,770 rows into a build side, so store_sales is scanned and not skipped |
21 → 57 ms |
| The sample depends on the other filters of the scan | DS Q10: ss_customer_sk was sampled while the date filter was on (6.5 ns). The real value after the date filter paused is about 1.5 ns, against an eval of 3.1 ns |
filter kept by mistake |
| The sample depends on the other filters of the scan | DS Q79: the ss_sold_date_sk sample is 2.3 ns with est 20 and 34.8 ns with est 0 |
scan 93 → 133 ms |
| The sample depends on the other filters of the scan | DS Q31: date filters are paused correctly, but other filters change their state | 169 → 178 ms |
| Work not visible | The work after an exchange (RepartitionExec) or into a hash join build side is not in the time |
DS Q54 build side |
Open design questions
- Continuous sampling at a low rate, instead of one probe for each site. What rate, from what measurement?
- Take a new sample when another filter of the same scan changes its verdict.
- A bound on the cost of a probe, for example from the removed fraction and the producer work. It must come from a measurement, not from a new constant.
- How to measure the work after an exchange or into a build side (for example, the producer could report the rows that it sees for each input row of the scan).
🤖 Generated with Claude Code
Activity
mohitgurav20 commentedon Sep 27, 2026
Really glad you wrote this up — I've been staring at the Q72 regression in optional_filter_min_saving_ns_per_row for a while and the prototype numbers make the problem crystal clear. The gap between the 1.3 ns real saving on Q10 vs. the 20 ns estimate is exactly why a constant will always be a losing game.
I dug into the FilterExec stream and metrics code after reading this and had a few thoughts — dropping them here in case they're useful for the design questions.
The confounding-filter problem (failure modes 3–5)
All three of those failure modes share the same root: the off/on sample is polluted by other filters on the same scan changing state mid-measurement. One approach I kept coming back to is a monotone filter-state generation counter per scan site — a simple u64 that increments any time any filter on that site toggles. You only accept a timing sample if the generation number didn't change between when the batch was issued and when it was returned. It's cheap to check, requires no bitmask diffing, and would naturally discard the DS Q10 case (date filter active during ss_customer_sk sampling) and the DS Q79 case without needing continuous re-sampling.
If you want finer-grained isolation (e.g. attributing exactly which filter changed), a compact active-filter bitmask per batch works too — but the generation counter feels like the right starting point since it's a single atomic compare.
The "probe is not free" cases (Q72, Q54)
For Q54 specifically, the probe isn't just not free — it enables 32k rows on the build side that otherwise wouldn't exist. I noticed probe_hit_rate is already tracked in joins/utils.rs (JoinMetrics.probe_hit_rate). That's an observable signal: if build_rows_added_by_probe > 0, the probe is not free by definition and should never be treated as amortizable. Wiring that into the pausing decision seems tractable without new constants.
Work past an exchange
The elapsed_compute timer in FilterExecMetrics already stops at a RepartitionExec boundary — so any downstream saving past an exchange is invisible to the measurement. I wonder if we could propagate a "time credit" upward through the post-execution plan tree in a way similar to how statistics_from_inputs walks children today. The exchange node would expose its downstream elapsed time, the filter walks up to claim it. It avoids instrumenting every intermediate operator and fits naturally into the existing metrics architecture.
Quick scoping question
In the prototype branch — is the measurement hooked into FilterExec::poll_next or is it closer to the scan/datasource level? If it's at the filter, the off→on delta naturally includes the filter eval overhead which is what we want. If it's at the scan, we'd need to be careful not to double-count predicate evaluation time.
I'd genuinely like to help move one of the open design questions forward if you're open to it. The generation-counter approach for the confounding-filter failure modes feels like something that could be prototyped pretty quickly — happy to take a first pass at it if that's useful.