Search: exclude a rejected candidate itself, not only its query closure #964

Problem, by example

Two SQL queries over metrics (666.67 rows/s, 100 series), each evaluated every 10 s over a 5-minute window, ε = 0.01, δ = 0.001, WholeResult:

-- q0
SELECT city, percentile_cont(0.9) WITHIN GROUP (ORDER BY value) FROM metrics
WHERE ts > now() - INTERVAL '5 minutes' GROUP BY city;
-- q1
SELECT percentile_cont(0.9) WITHIN GROUP (ORDER BY value) FROM metrics
WHERE ts > now() - INTERVAL '5 minutes' AND city IN ('NYC', 'SF');

On the finer-aggregate reuse branch at 83c87c05 (#952), with the seed-round cap lifted in an instrumented run, the joint search made 154 evaluations:

• 137 proposals used one of the new candidates, and all 137 were rejected:
  • 40 by the executor compile check: unsupported scalar expression: InList { … 'NYC', 'SF' }, in every case the same Filter-over-State candidate;
  • 74 by accuracy_target_missed for q0 reading a city-grouped KLL state;
  • the rest by no_accuracy_guarantee.
• The best plan, 0.2284651/s, was found at evaluation 152 after 215 s.
• Under the real seed-round cap of 5 s, the search returns 0.3320576/s instead.

Each rejection names the candidate that caused it, but the search only excludes the query closure it was found in. So every other closure containing the same Filter-over-State candidate is proposed again.

#952 will stop generating these particular candidates. The search behavior stays: any candidate that is rejected for a reason of its own is retried once per closure it can appear in.

Why it happens

search_with_solver (plan-selection/src/search/refinement/search.rs) adds one of two cuts after each evaluation:

• Priced plan: an exact cut, total_cost ≥ cost_o · (1 − mismatch_o), which binds only the identical assignment.
• Rejected plan: a query-subgraph cut, RejectedQuerySubgraph::from_query_outputs, which forbids exactly that query's closure (its edges and root assignment).

The MILP has no accuracy or compile constraints. A rejection caused by one candidate's own property is therefore relearned for every combination of that candidate with other producers and consumers. In the example, the Filter-over-State candidate can be fed by 10 TimeRange versions, each fed by 5 scans.

Proposal

When a rejection is attributable to one candidate independent of its inputs and readers, add a candidate cut x_c = 0 instead of, or in addition to, the closure cut:

• Executor compile failure: the failing node's candidate. The compile check reports the expression; map it to the candidate whose private nodes contain it.
• Accuracy failure: only when the candidate's composed guarantee alone cannot meet the target, whatever its children are. Otherwise keep the closure cut.

The fallback remains the closure cut, so no valid plan is excluded.

Scope and acceptance

• In scope: candidate-level cuts for compile failures and for input-independent accuracy failures in the refinement search.
• Out of scope: encoding accuracy composition in the MILP.
• Acceptance: with a candidate whose node always fails to compile, added to a two-query workload, the number of rejected proposals is at most one per such candidate, instead of one per closure. The joint cost and selected plan of the existing suites are unchanged.

Related

• feat(optimizer): reuse a finer aggregate through a compensating filter and a rollup of values or states #952: stops generating the infeasible candidates of this example.
• The plan-selection PR that seeds the search with the independent plan.
• Search: certify lower bounds for query-time scans and builds #963: lower bounds that rank these proposals.