Planning one ratio of filtered increases went from about 1 minute to over 28 minutes and 12 GB on main #1023

Problem, by example

One query: the 5xx ratio of a payment service six hours ago. It is evaluated every minute over a one-hour range (step_ms 60000, span_ms 3600000), with max_error 0.01 and failure_probability 0.001. Its source is a 1000-series counter sampled every second.

sum(increase(http_requests_total{job="payment-service",status=~"5.."}[1h] offset 6h))
  / sum(increase(http_requests_total{job="payment-service"}[1h] offset 6h))

{"query_workload": {"language": "promql", "repeating_queries": [{
   "query": "sum(increase(http_requests_total{job=\"payment-service\",status=~\"5..\"}[1h] offset 6h)) / sum(increase(http_requests_total{job=\"payment-service\"}[1h] offset 6h))",
   "demand": {"fixed_interval": 60000},
   "requirements": {"accuracy": {"max_error": 0.01, "failure_probability": 0.001}},
   "predictability": {"predictable": {"known_at": null}},
   "range_evaluation": {"step_ms": 60000, "span_ms": 3600000}}]},
 "data_workload": {"arrival": {"ingesting": {"rows_per_second": 7000.0}},
   "sources": {"http_requests_total": {"sample_interval": 1000, "series_count": 1000, "metric_type": "counter"}}}}

cargo run --release -p asap-devtools --bin stage_pipeline -- --workload q18.json --enforce-accuracy-guarantees --out q18-doc.json

These were measured while reviewing the corpus snapshot CI in #956. That workload declares six more sources; only http_requests_total is read here.

Why (not bisected)

Commits between the two that change planning:

• feat(optimizer): reuse a finer aggregate through a compensating filter and a rollup of values or states #952 (reuse a finer aggregate through a compensating filter and a rollup), with fix(optimizer): an exact rollup reads the finer query's own result #984 (an exact rollup reads the finer query's own result). This query divides one sum of http_requests_total by another with a stricter filter, which is the shape feat(optimizer): reuse a finer aggregate through a compensating filter and a rollup of values or states #952 rewrites.
• fix(plan-selection): evaluate the queries' separate plans first in the seed round #973 (seed round evaluates the queries' separate plans first).
• fix(plan-selection): certify lower bounds for query-time scans, windows and builds #987 (certified lower bounds for query-time scans, windows and builds).

Proposal

1. Bisect 387de3cfe..0f7465c96 on the workload above, with a 120 s time limit.
2. Fix the cause: memo blow-up (group and candidate counts), the refinement loop, or a lower bound that never closes.
3. Add a regression test with a planning-time bound.

Scope and acceptance

The workload above plans within its previous 53–78 s on a release build, under 2 GB RSS, and selects a plan whose cost is no worse than at 387de3cfe.

Related

#956 (corpus snapshots: q18 is its slowest query), #1015 (Stage 3 review), #1013 (Pass 2 review).