memo-milp: size summaries once (final config per reader set and summary count; Stage 3 never resizes) #929

Problem, by example

Take rh8-q1h60 (RangeHeavy 8 users, the quantile queries over 1h at 60 s steps: five queries share one SummaryMerge, with a ratio of two quantiles on top; fargate prices, raw data retained, guarantees enforced) and plan it with --search memo-milp --milp-time-limit-s 280.

A sketch state's size is not known when the MILP picks a choice. Stage 3 sizes it afterwards: resize_for_failure_probability (crates/plan-selection/src/lib.rs) sets each state's per-value failure probability to the minimum over its readers of δ_q / (n_q · V_q), where n_q is the number of sketch states under query q's chosen root. n_q depends on which of q's other parts the plan makes approximate, and the reader set depends on the sharing choice, so the same memo choice is priced at one size by the model and evaluated at another by Stage 3. Memo pricing also resizes each part with only that part's entries (cost/per_node.rs), so its n can differ from Stage 3's whole-root n.

Today the model handles this with rules read at the largest size Stage 3 can give (resized_to_the_largest), which is exact but loose: rh8-q1h60 keeps proposing small-size ratio plans that Stage 3 rejects. On the integration branch before this work it stopped at the time limit at 8.53e-06 (gap 0.71) against the reference 3.832852e-06.

What should happen: every choice the MILP picks is already at its final size, the model's cost of that choice is the cost Stage 3 evaluates, and Stage 3 never resizes.

Why it happens

• n_q and the reader set are plan context, not a property of one memo choice.
• Site thresholds (u variables) cover only a shared state's size threshold, not the n_q axis.
• Stage 3 enlarges sizes after selection (enlarge only; Pass 1 and shared-size params are a floor).

Proposal (Option A, approved by the user 2026-10-23)

• A choice version carries its final config: one per distinct final config over (reader subset, n_q).
• Thresholds = the distinct final configs; u is linked to x through n_q (each query's summary count).
• Searches compose plans at their final sizes; Stage 3 no longer resizes.
• Rejected alternative (Option B): size every state for the largest possible n_q. Simpler, but not exact: it overprices plans with fewer approximate inputs.

Scope and acceptance

• In: memo-milp choice versions, coefficients, Stage 3 sizing for searches that pass final sizes, the legacy and brute-force searches composing at final sizes.
• Acceptance: the fixed regression set keeps its costs and certifies (q24h60 8.739e-05, w840 0.1477616, w840_4 / i840 0.1507878, j839 raw 113.9514 / no raw 115.6695, rh8-q1h60 3.832852e-06); a test asserting the model's cost of a choice equals Stage 3's cost of the decoded plan for a ratio over shared quantiles; the 20-seed and 60-seed three-way equivalence tests pass.

Status and related work

• In progress on branch feat/memo-sizing-once (head 4e7be4e, WIP): certified rows keep their costs and certify, but the model is 2–3x larger, so time-limited rows are worse (rh8-q1h60 1.34e-05 gap 0.81 vs 8.53e-06 gap 0.71 on the base; q24h60 and t11-5m unchanged). The newest test has not been run.
• Part of Tracking: plan every whole evaluation workload within 3 minutes (exact pruning, memo-group search) #879. Related: Sizing allocates far larger sketches than the workload needs #798 (sizing allocates larger sketches than needed), [Bug] Stage 3 sizes a sketch's memory by its full capacity, not by the samples it holds #726.