Capabilities lost with the legacy replacement search: maintenance-time exact operations, extension intents, nested folds, rate-maintained summaries and guards #735

Problem, by example

sum by (service) (count_over_time(metrics[5m])) at an exact target:

The legacy search (ASAPStrategies and its strategies in replacement.rs, rewrite.rs and exact_composition.rs) was deleted in #736. The user approved this as an exception to the "delete only what the stages implement" rule on 2026-10-16. Before the deletion, nothing in the planner called that search, so planning did not change. But these capabilities now have no implementation anywhere. Each item below names one query, what the legacy engine produced (from its tests, which were deleted with it), and what Pass 1 / Stage 2 produce now (from a run on the PR head).

1. Exact operation maintained at ingestion under a summary. quantile(0.99, deriv(latency[5m])).
   • Legacy: ExactCompositionStrategy placed deriv at ingestion time under a maintained KLL (OperationPlacement::Maintenance, test outer_summary_over_an_exact_function_composes_at_ingestion_time). The CostModel value-operation hooks gated it.
   • Now: Pass 1 offers the KLL over the plain deriv aggregate. Stage 2's ingestion_eligibility requires a build's child to be a TimeRange, so the KLL can only be built at query time (WindowNotFixed).
2. Extension aggregations. AggIntent::Extension { .. }.
   • Legacy: realized through the deployment's CostModel::realize_extension / evaluation_extension.
   • Now: computation_candidates_for_intent gives only [Exact]. The extension contract is Design the extension contract for new ASAP primitives and sketch algorithms #548.
3. Nested aggregate fusion beyond sum∘sum. sum(count_over_time(m[5m])), min(min_over_time(m[5m])), max(max_over_time(m[5m])).
   • Legacy: each folded into one aggregate (Count, Min, Max).
   • Now: two stacked accumulators, e.g. Finalize(Min) ← SummaryAgg(Min) ← Finalize(Min) ← SummaryAgg(Min). add_nested_sum_targets merges only a sum of sums.
4. Summary maintained over finalized per-window rates. topk(2, sum by (job) (rate(m[1m]))).
   • Legacy: retime_rate_finalize / fixed_window_rate_candidates built a CMS+heap or a Sum over the finalized per-window rates, as a maintained candidate.
   • Now: Pass 1 offers CmsWithHeap{272, 5, 100} over Finalize(Rate), but Stage 2 cannot maintain it at ingestion, for the same TimeRange reason as item 1.
5. Reset-aware counter proof for a CMS top-k over a rate. Same query as item 4.
   • Legacy: the heap update carried WeightDomain::NonNegative { proof: ResetAwareCounterDerivative } (realize_counter_value_summary_input).
   • Now: the update is UnknownOrSigned, so Stage 3 rejects the Count-Min heap as invalid for signed weights.
6. Top-k membership guarantee from a distinct-items bound. topk(5, sum by (job) (m)) with an evidence provider that bounds the distinct items.
   • Legacy: finish_weighted_topk read AccuracyEvidenceProvider::topk_max_distinct_items and the TopKSelection margin statistics, and gave the estimate a joint guarantee.
   • Now: Pass 1 gives a top-k estimate no guarantee (estimate_has_bound is false for TopK). Stage 3 then accepts it only with output_guarantee evidence. topk_max_distinct_items and propagation_stats were removed from AccuracyEvidenceProvider because nothing read them. PropagationStats' topk_* fields remain, read only by the TopKSelection rule.
7. UnivMon for an exact count. count by (job) (m) at an exact target.
   • Legacy: offered the exact Count accumulator and a UnivMon sized at ε = 0.
   • Now: only ExactAccumulator([Count]).
8. Sketch state cap. Any sketch whose state exceeds 512 MiB.
   • Legacy: sketch_realizations dropped it (sketch_state_bytes, DEFAULT_MAX_SKETCH_STATE_BYTES).
   • Now: Pass 1 keeps it. Stage 3 prices its memory and only cost model 3 (ClusterCapacity) enforces a limit.
9. Expected-case sizing. posterior_aware_size_params / ExpectedCaseSizing (Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239) sized a sketch below the worst case under a declared non-adversarial assumption. It was called only by its tests; the stages size with default_size_params.
10. No checked division inside a maintained state. quantile(0.9, avg_over_time(m[5m])).
    • Legacy: maintenance_exact_values refused to feed a maintained summary from a BinaryOp with checked_finite_division, because an invalid value cannot be removed from a sketch once it is in. The division stayed at read time.
    • Now: Pass 1 offers KLL ← BinaryOp(Div, checked) ← Finalize(Sum), Finalize(Count) with no such guard.
11. DDSketch operand-domain check. A DDSketch ratio quantile_over_time(0.9, d[5m]) / quantile_over_time(0.5, d[5m]) with a subnormal domain [f64::MIN_POSITIVE / 2, f64::MIN_POSITIVE / 2], or max_samples above 2^53.
    • Legacy: OperandDomain::supports_ddsketch rejected both. It also required the domain to lie within ddsketch_indexable_bounds(alpha) and the contract to be non-empty.
    • Now: Stage 3's division rule rejects zero-crossing, non-finite and inverted domains, but accepts these two.

Hydra grouping (HydraGroupingStrategy) is tracked in #703 (G7b). Maintained-population top-k (MaintainedPopulationStrategy in Pass 1) is tracked in #681. Neither is repeated here.

Why it isn't done today

Pass 1 (per_computation_candidates.rs) was built as a new candidate generator, not a port of ASAPStrategies. The parity list in #580 covered the strategies (rollup, avg rewrite, top-k reuse, sharing, reconciliation, Hydra, populations), but not these narrower shapes and guards inside the legacy realization engine.

Proposal

Add each capability in the stage that owns it:

• items 3 and 7: Pass 1 choices;
• items 1 and 4: Stage 2 materialization (a summary over a finalized per-window value maintained at ingestion);
• items 5, 6, 10 and 11: Pass 1 update contracts or the Stage 3 accuracy check;
• item 8: a Pass 1 prune with a PruneReason, or a deployment capability (Deployment inputs: one bundle for cost model, accuracy model and capabilities — after #511 #525);
• items 2 and 9: the extension contract (Design the extension contract for new ASAP primitives and sketch algorithms #548) and sizing.

Several of these change candidate sets and selections, so each needs its own PR with the example tests re-checked.

Scope and acceptance

One test per item that fails on the PR head and passes with the capability, using the query above.

Status and related work

• Deleted in refactor(asap-aware-mapping)!: delete the legacy replacement search and CostModel #736, user-approved exception (2026-10-16).
• Related: Pass 2 sharing and Stage 1 coverage parity with the retired MajorPass #580 (Pass 2 and Stage 1 parity), Hydra follow-ups: group totals in the executor, Pass 1 HydraCms candidates, Hydra top-k #703 (Hydra), Offer maintained-population top-k candidates in Pass 1 #681 (maintained populations), Design the extension contract for new ASAP primitives and sketch algorithms #548 (extension contract), Deployment inputs: one bundle for cost model, accuracy model and capabilities — after #511 #525 (deployment inputs), Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239 (expected-case sizing), Calibrate plan selection's costs from measured sketch costs #679 (measured costs).