Search: certify lower bounds for query-time scans and builds #963

Problem, by example

Same workload as #964: q0 = p90 per city, q1 = p90 over city IN ('NYC','SF'). Both run every 10 s over 5 minutes of metrics (666.67 rows/s, 48 B rows), ε = 0.01, WholeResult. Numbers are from an instrumented run on main (d4152bce).

q1 has two plans that differ in two candidates:

The bound ranks the expensive plan first. In the seed round on main, the MILP proposes all 13 zero-bound combinations (5 priced at about 0.332, 8 rejected) before it reaches the ingestion path at evaluation 14–15. On the #952 branch the same ordering left about 150 zero-bound combinations, more than the 5 s seed round could evaluate, so the search returned 0.3320576/s instead of 0.2284651/s.

Why it happens

costing/lower_bounds.rs assigns a certified local cost only to:

• ingestion Scan, Project and TimeRange;
• exact or DDSketch ingestion PaneChains;
• query-time Project, SummaryEstimate and SummaryMerge.

Every other node gets 0 ("Unsupported pricing contexts contribute zero"):

• query-time Scan, TimeRange and Aggregate;
• query-time KLL SummaryAgg and PaneChain builds;
• Filter.

round_down_small_bounds also zeroes bounds smaller than MINIMUM_RELATIVE_COEFFICIENT of the largest one, which removes most KLL ingestion pane chains.

A query-time scan's cost does not depend on its readers: every evaluation of a query that reads it scans its window. A bound of query_rate_floor × rows_in_window × (cpu + bytes) is certifiable, the same way the ingestion scan's bound is.

A quick prototype that allowed query-time Scan in lower_bounds.rs still produced 0, because certified_price returned no price for it. Why was not investigated.

Proposal

• Certify lower bounds for query-time Scan and TimeRange: rows in the window × the minimum query rate × the unit prices. Do the same for query-time Aggregate and summary builds: their per-row CPU over the same rows.
• Find out why certified_price returns none for query-time nodes.
• Revisit the round-down threshold when bounds of very different sizes coexist.

Scope and acceptance

• In scope: lower bounds for query-time Scan, TimeRange, Aggregate, SummaryAgg and PaneChain builds.
• Acceptance:
  • in the example, the query-time q1 path's lower bound is at least 0.116/s;
  • the seed round on main reaches the 0.2284651 plan within at most 3 evaluations;
  • every lower bound stays at or below the evaluated cost on the existing suites. Add a check that asserts this for every priced proposal.

Related

• Search: exclude a rejected candidate itself, not only its query closure #964: candidate-level cuts.
• The plan-selection PR that seeds the search with the independent plan.
• feat(optimizer): reuse a finer aggregate through a compensating filter and a rollup of values or states #952 (example C).