Stage 3 review: plan selection, the MILP over the memo, cost and accuracy constraints #1015

Part of #1010. Line numbers are on main at 958778400. ps/ = crates/plan-selection/src/.

Example: what Stage 3 receives and returns

Same query as the tracking issue (avg by (job) (quantile_over_time(0.5, data[5m]) / quantile_over_time(0.5, data[5m]) + quantile_over_time(0.9, data[5m])), every minute, max_error 0.01, failure_probability 0.001). Stage 3 receives a memo of 354 groups and 1738 implementation candidates (#1008; corrected 2026-10-28: production numbers from the stage-pipeline document; earlier numbers came from a test helper without the series-identity column.) It must pick one candidate per needed group (and one producer per input), check accuracy and latency, price the plan, and return one plan.

How many candidate DAGs that memo stands for is not known: a naive enumerator stopped at 1,000,000 (#1002). So today nobody can check, even for this one query, that the selected plan is the cheapest the memo allows (#1004).

Functionality

• Reject candidates that miss an accuracy target, a latency bound or a deployment capability; pick the cheapest valid plan for the whole workload under the deployment's cost model.
• It is the only stage that uses the cost and accuracy models and the only one that discards valid candidates.

Concepts (design doc term ↔ code)

The MILP (ps/search/milp/model.rs, solved with HiGHS through good_lp): a binary candidate_selected per physical candidate configuration (:325), an integer topological_rank for acyclicity (:335), a binary connection per (consumer, input, compatible producer), a binary query-root assignment; each active consumer has exactly one producer per input (:388), each root is assigned once (:417), a selected candidate must be used (:637); the objective is a lower bound on local costs, tightened by cuts from evaluated plans and no-good cuts from rejected ones. The proposed plan is then validated and priced by PlanSelector (Stage 2 + pricing + accuracy + executor compile check), so the search is a propose–validate loop.

Interfaces: designed vs implemented

Interface decided in #1047 (2026-10-29)

Decided in #1047, the stage-boundary types. Its sub-issue is #1048. Names follow #1050 within #1047's scope. Principles: a stage or pass reads only the previous step's output type and calls no other stage; the asap-planner facade runs the stages in order; each stage prunes only what its own knowledge rules out and records it as PrunedCandidate<C> { group, candidate, reason: PruneReason }; queries are entry indices. Planning stays as fast as on main: P6 and P7 report before/after stage_pipeline runs.

Review checklist

User's suspected problem: does the MILP find the optimal candidate?

• Budgets, not proof, by default. 30 s total (route.rs:75, milp_time_limit_ms.unwrap_or(30_000)), at most 128 evaluated plans (:103, :168), a seed round of at most 5 s and 128/4 evaluations (:115, :123), non-final pane-width rounds of at most 5 s and 16 evaluations (:212, :217). When a budget stops the search, the status becomes time_or_evaluation_limit_with_validated_incumbent (:386). The design doc's "3. Plan selection" section says "picks the cheapest remaining plan" and does not describe the MILP, the rounds or these limits. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047: the total budget moves to the facade; Stage 3 gets a deadline.
• Lower bounds must be certified for every candidate the MILP can cut: query-time scans and builds (Search: certify lower bounds for query-time scans and builds #963, [Bug] Search: a query-time scan's lower bound takes the shortest possible reader window, so the cheaper plan is never proposed (#987) #994), and a rejected candidate must be excluded itself, not its whole query closure (Search: exclude a rejected candidate itself, not only its query closure #964). memo-milp misses rh8-q1h60 at 280 s (1.34e-05 vs 3.83e-06): suspected decode cut of a valid stricter site threshold #928 is a suspected wrong cut.
• Check against enumeration on small workloads: price every candidate DAG the memo stands for and compare with the MILP's choice (Memo: convert memo-group candidates into the vector of all candidate DAGs #1002, stage_pipeline: price every enumerated candidate DAG and flag any cheaper than the selected plan #1004).
• Sizing inside the search: a sketch's size is not known when the MILP picks; decide "size once per reader set" (memo-milp: size summaries once (final config per reader set and summary count; Stage 3 never resizes) #929).

1. Boundaries

• Stage 3 runs Stage 1: try_populate_pass1, accuracy_configurations::add_scoped_candidates (ps/search/candidates/accuracy_configurations.rs:8, a Stage 3 module that adds Stage 1 candidates), extend_local_window_composition and expand_concrete_summary_state_groups_before, all in search_domain; run_with_initial_memo filters unsupported summaries (pipeline.rs:214). (Reorganize by stage: one memo-based Pass 2, Stage 1 finishes the memo, deployment inputs split by stage, asap-planner as the only entry point #958 decision 2.) [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P3, P4, P7.
• Stage 3 lists materialization modes itself (ps/search/candidates/configurations.rs:162-222; see Stage 2 review: physical optimization and materialization per candidate #1014). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P5.
• query_pruning::alone_violation (ps/search/query_pruning.rs:316) runs whole-workload Pass 2 and Stage 2 per query before the joint search. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P6 replaces it with per-stage pruning.
• Stage 3 holds sketch-library byte-size models for KLL, DDSketch and UnivMon at the end of ps/lib.rs (about :5074-5190). Decide whether runtime library sizes belong to the deployment's cost model (Plan selection and the executor disagree on summary state memory #947, Plan selection underestimates top-k heap memory by about 9× #946, [Bug] Stage 3 sizes a sketch's memory by its full capacity, not by the samples it holds #726).
• The executor compile check runs once per evaluated plan and builds a full InstallablePlan each time (PlannerExecutorCompileCheck, crates/planner/src/installable.rs); Remove ExecutorCompileCheck from plan selection #949 proposes removing it from plan selection.
• The crate also holds the planner's public API (OptimizationPass, optimize, PlanningModels, ps/search/mod.rs) and orchestration (pipeline.rs); see asap-planner facade review: orchestration and deployment input assembly #1017. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P7 / Reorganize by stage: one memo-based Pass 2, Stage 1 finishes the memo, deployment inputs split by stage, asap-planner as the only entry point #958: orchestration moves to the facade.

2. Naming and over-abstraction

• "price" names in Stage 3 (price_node ps/lib.rs:3717, PricedNode, NodePriceSource in ps/cost/measured.rs, supplier_price_options, direct_price_options) where the repo term is "cost".
• "supplier" (SupplierCandidates, ps/search/candidates/suppliers.rs) and "producer" (compatible_producers) name one concept; PhysicalCandidate.local_cost is an objective weight; PlanSelector validates and prices, the MILP selects ([Refactor] Repo-wide naming survey: overloaded and misleading names #948).
• pub use search as pass; (ps/lib.rs:297) gives one module two public paths.
• ps/lib.rs is 11,440 lines: about 5,190 production lines (settings, reports, PlanSelector, statistics bounds, accuracy checks and resizing, per-node pricing, latency, sketch byte sizes) and about 6,250 lines of tests from :5194. Split by concern.

3. Stale code

• ps/lib.rs:30: "Dynamic-programming compression is outside the current implementation" (no DP code exists).
• Whole-workload enumeration select_plan over optimize_physical_asap: no Stage 3 production caller; used by planner_fuzz, integration tests and tests. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047: the name select_plan goes to the new Stage 3 entry over PhysicalASAPMemoCandidates; the whole-workload one is deleted.
• SearchAlgorithm with one variant and its CLI flag; the viewer still maps old memo-milp / memo-brute-force names ([Refactor] Repo-wide naming survey: overloaded and misleading names #948). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P2 deletes it and stage_pipeline --search.

4. "memo" / "cache"

• CompatibilityMemo (ps/search/candidates/factoring.rs:26) is a cache; "memo" in the viewer means the joint search ([Refactor] Repo-wide naming survey: overloaded and misleading names #948). [Refactor] Rename memo-named caches and the memo types by stage #1050: MemoGroupOutputToCompatibleProducersCache.

5. Rules over memo groups

• Stage 3 should take the memo as given: groups, candidates, and the choices several groups share (state groups today, coupling sites in the doc). List which inputs the MILP reads that are not in the memo (pane-width rounds, accuracy configurations). Decided in [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 (table above).

Cost and accuracy constraints

• Cost model correctness: top-k heap memory (Plan selection underestimates top-k heap memory by about 9× #946), summary state memory vs the executor (Plan selection and the executor disagree on summary state memory #947), sketch memory by capacity vs samples held ([Bug] Stage 3 sizes a sketch's memory by its full capacity, not by the samples it holds #726), KMV update cost (KMV update cost is not one operation per row #945), relabeled group keys (A relabeled or renamed group key is priced at its old label's declared count #898), kept-across-evaluations results almost never chosen (Stage 3 almost never selects query-time results kept across evaluations (Example 4 B3 costs 8,884.5/s vs 2.1/s) #754).
• Cost model scope: memory/disk/latency trade-offs (Stage 3: memory, disk and latency trade-offs per candidate, and cost models beyond cloud billing #660), storage I/O and hand-offs (Stage 3: evidence-driven cost (storage I/O, hand-off bytes) #615, Plan selection: price storage I/O, handoffs and cache, from deployment evidence with provenance #733), calibration (A partial measured cost table can still mis-rank plans: calibrate per operator kind #791, Plan selection: warn when the measured cost table is missing or has no Scan, TimeRange or Aggregate entry #843), validation against benchmarks (cost model: validate analytical estimates against empirical benchmark evidence #347, Feed empirical sketch error, resource usage, and data distributions into planner estimates #322).

Efficiency

• Plan every whole evaluation workload in minutes (Tracking: plan every whole evaluation workload within 3 minutes (exact pruning, memo-group search) #879, memo-milp: certify whole evaluation workloads within 300 s #927); scaling (Scaling families: planning time, rounds and gap as one sharing structure grows #918); compile check quadratic in panes ([Performance] Stage 3's compile check is quadratic in panes since #988 (scan_window, time_range_window) #993); long-offset planning time ([Performance] A 30-day offset trend exceeds 90s planning at a 30s refresh cadence #896).

Review of the group MILP (#1095, #1144), 2026-11-02

The checklist above reviews today's engine. #1144 replaces it with #1095's group MILP. That MILP becomes the default search, and cost models 2 and 3 return UnsupportedCostModel. This section reviews the group MILP against the same goals.

• Code reviewed: feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144 rebased onto main, commit 582ae71f8.
• Paths: relative to crates/plan-selection/src/.
• Method: read-only. Items marked unverified come from reading the code.
• Worked example: in the comment below, together with the debug-printer format.

The pipeline: select_plan_with_milp (select.rs) → prepare_milp_inputs_with (groups.rs) → build_selection_milp (milp/model.rs, rows 1–9 and cost_terms::encode_objective) → solve_selection_milp (warm start, Completion, one HiGHS solve per independent part) → decode → validate → realize → plan_cost == objective, accuracy and latency checks.

1. Code-level abstraction

• H1, correctness: note_inexact mixes three kinds of note, and every one of them disables the cost-equality gate. SelectionMilp::inexact counts:

  • cost terms encoded approximately (scan read at more than 4 window kinds, pane retention, schedules);
  • feasibility restrictions that forbid plans but are exact for cost ("(forbidden)", e.g. AllowedOutputs over part of a query);
  • terms set to zero (compaction).

  select.rs turns objective ≠ plan_cost into ObjectiveDiffersFromPlanCost only when that list is empty. So one "forbidden" note anywhere in the model turns a real cost bug into a reported InexactObjective. The notes are not tied to a run either.

  • Fix: typed InexactCost { run, reason } and LostPlans { reason }; only the first excuses a mismatch, and only by its term.

• H2: one rule written four times. The rule maps a read of candidate c in context ctx to its run: computed in ctx, the shareable's own context, or the reading context's I_r. Copies: decode::run_of, cost_terms::producer_run, model::node_read, warm_start::runs_reached. There are also two representations of a run.

  • Fix: one RunId and one MilpInputs::run_read(ctx, c).

• H3: a redundant filter. The "producer not in the reader's own slot" filter is re-applied in six places (model.rs ×3, cost_terms.rs, decode.rs, warm_start.rs). CandidateLinks::new already removes those links. Keep it in groups.rs only.

• H4: ownership.

  • groups.rs imports milp::cost_terms::window_union, and binds a second function to the same local name window_union (scan_window_read_at as window_union). These are two different rules under one name.
  • request_ms is computed in three places.
  • The per-query evaluation rate is computed twice, and warm_start.rs silently maps errors to 1.0.
  • The debug logger lives in warm_start.rs.

• H5: Completion has implicit contracts. It depends on hard-coded row-family strings (CHECK_ONLY_FAMILIES) and on "the defining variable is the one created last". Renaming a family silently changes the warm start's cost and the incumbent's recomputed objective.

  • Fix: record RowRole::{Defines(var), CheckOnly} when a row is created.

• M1: large functions:

  • candidate_data (~490 lines);
  • solve_selection_milp (~250);
  • encode_objective (~200);
  • window_terms (~195);
  • reader_constraint_rows (~175);
  • structural_rows (~170);
  • execution_contexts (~160).

• M2: test code in production. The test hook tests_loose_big_m() changes production big-M values. Delete it; its comparison was measured in feat(plan-selection): selection MILP solved per independent part, LP gap diagnosis, tighter big-M bounds (#1095 §5 3a, §6.1) #1155.

• M3: dead family. Compaction is dead: compaction_ms always returns 0, so K[q] is never created. Encode it or delete it.

• M4: stale docs.

  • groups.rs's module doc still describes the owner model (OwnerRegion, "Nothing calls it yet").
  • The doc of runs_at_query_time describes another function.
  • crates/types/src/stages/physical/graph.rs still mentions "two shared instances", which O5 removed.

• M6: names.

  • class holds a candidate id, a leftover of the deleted class layer.
  • choice, selected and reach hold the p, x and a variables, and selected is also a set of candidates in the solution.
  • Latency values carry no unit (latency_max, most, slack, units).
  • CandidateData::usage is "the usage in the first costed context".

• M7: tolerances. Inline constants include the latency scale 1_000.0, the objective scales 1_000.0/1e7, and five different tolerances (1e-12, 1e-9, 1e-7, 1e-6); [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 §9 asks for one tolerance. The local MAX_SHIFTS and the warm-start budget "deadline / 5" are also inline.

• M8: duplicated derivations.

  • "The output references of query q" is recomputed about 11 times; add MilpInputs::references_of_query.
  • select.rs clones three solution fields into ChosenCandidates.

• M9: implicit precedence. run_terms checks window, then producers, then plain + retention. A scan whose usage depends on both window and producer cannot be represented, and this is not flagged (unverified whether Stage 2 produces such a scan).

2. Variables and connections over memo groups

• No variable or row is keyed by MemoGroupId.

  • p is (context, candidate); the group is implied by slot[c].
  • A context's options are a set of candidates, not a set of groups.
  • Row 2 runs per ResultSlot = Group(g, self_read_depth) | PrivateNode(operator node).
  • The e, y, t_* and σ/δ variables are per candidate.

  This matches [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 wherever slot == group. It diverges in three places:

• Private-node slots: principled, but in the wrong stage. A private node is an anonymous result. Stage 2 should give each operator node a result id: the group for a root, a fresh id for a private node. Then Stage 3 needs no ResultSlot.

• Multi-slot inputs (e binaries): a workaround for Stage 2 factoring across implementations whose inputs differ by private node. The special case reaches rows 3–4, producer_terms, decode, the warm start and slot_reads. The upstream fix is one reader candidate per implementation, or a group for the shared sub-result.

  • Probable gap (unverified): slot links exist only for readers computed in a context. A shareable candidate's own multi-slot input is justified in row 4 by x[own] for every producer in every slot, so the phantom-reader case (feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144 design point 2) can come back there. It would be caught by validate as an error, not silently.
  • Test T2c below.

• Widened-scan self-reads (self_read_depth, two rank families): a workaround.

  • Root cause: the widened scan's Project gives a different result (a different window) but sits in the scan's own memo group, which breaks acyclicity ([Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 O7).
  • Cost of the workaround: depth is capped at 1, which loses Project∘Project plans. The rank rows are big-M rows, which weaken the LP.
  • Fix in Stage 1: give it its own group. Then delete self_read_depth and both rank families, and assert acyclicity in prepare_milp_inputs.

• Producer-dependent outputs (ProducerChoice, t_outputs/t_producers):

  • Principled for scans: rows follow the window.
  • Elsewhere: if O2 holds for every non-scan group, the producer table can shrink to scans plus summary configurations, and producer_usage_ambiguous goes away.

3. Tests for MILP correctness

What exists: about 19 tests in milp/model/tests.rs, plus groups/tests.rs, select/tests.rs and stage_pipeline tests. They check consistency: decode, validate, realize, and objective == plan_cost of that same plan. None checks optimality. The --exhaustive comparisons in the #1144 body were manual. Planned tests:

• T1, differential test against brute force on random small memos.
  • Generator: 3–8 operator nodes, 2–4 groups, 1–3 queries, using the groups/tests.rs builders.
  • Reference: enumerate every valid DagOfSelectedCandidates and cost each with plan_cost. Requires a tiny test realizer.
  • Assert: MILP ≤ the reference minimum, and equal unless the reference optimum is a plan O4/O5 deliberately excludes; tag such runs with the excluded class.
  • Also: --exhaustive on example1, ratio-of-quantiles and rangeheavy-t5-q05-q09, in CI.
• T2, row-level tests on a hand-built catalog. Fix binaries and check feasibility with Completion, no solver needed:
  • (a) row 2;
  • (b) row 3 boundary;
  • (c) row 4 phantom on a shareable's own multi-slot input;
  • (d) row 5;
  • (e) row 6 from above;
  • (f) each ReaderConstraint variant, including forbid_reach and HighestSharedQueryMaterialization.
• T3, decode round trip. Selection → decode → validate → realize; plan_cost == completion objective; re-encoding gives the same binaries. Negative cases: an unserved output, an input with no producer.
• T4: Completion::complete equals the HiGHS LP with the binaries fixed.
• T5, infeasibility mapping. Contradictory MinimumQueryReaders, outputs whose candidates are all pruned, and an exact target with only approximate candidates each map to NoValidCandidate / Infeasible.
• T6, the equality gate (H1). A "forbidden" note plus a wrong coefficient must still give ObjectiveDiffersFromPlanCost.
• T7, metamorphic properties. Adding a dominated candidate keeps the cost; permuting queries keeps the cost; parts on and off give the same cost; tightening the latency bound to the optimum's latency keeps the plan.
• T8: A1 ⊆ satisfies on the memo examples ([Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 §4 step 5).

4. Printing and debugging

What exists today:

• ASAP_STAGE3_REPORT: one JSON line of sizes per run, written after the solve, so nothing for an infeasible model.
• ASAP_STAGE3_DEBUG: free-text stderr.
• Readable p/x labels: only behind the lp-diagnosis feature.
• Rows: identified by index and family only. Variables: unnamed, so there is no readable .lp export.

To add:

• ASAP_STAGE3_DUMP=<path>. One text file per run, in pipeline order: memo (group → slot → candidates) → contexts → variables → labelled rows → objective terms → solution with inexact notes per run → decoded DAG with plan_cost per node beside its objective share. Sample format in the comment below.
  • Labels move from lp_diagnosis.rs into Display for ContextKind.
  • A RowLabel is kept beside each row.
• On Infeasible: print the labelled rows of an IIS, or drop row families one at a time as lp_diagnosis does.
• On ObjectiveDiffersFromPlanCost: print the per-run objective share next to plan_cost.per_node.

5. Data structures

• One selection type. The selection has three encodings: SelectionMilpSolution { chosen, selected, slot_reads }, decode::ChosenCandidates, and warm_start::Plan. Use one Selection { per_context: Vec<BTreeMap<ResultSlot, PhysicalCandidateId>>, selected, slot_reads }; keying by slot also makes row 2 a type invariant.
• CandidateData as an enum. It has 12 fields that are mostly mutually exclusive variants, checked in an implicit order in run_terms. Use enum UsageVariation { Fixed, PerProducer, PerScanWindow, PerRetainedPanes } plus approximate and parts.
• Split SelectionMilp. It holds variables, topology, numerics, output and build caches. Split into Vars { p, x, a, e, L }, Topology (derivable from MilpInputs) and TermCache.
• Smaller items:
  • ExecutionContext::options should be grouped by slot, which row 2, the warm start and the printer all rebuild today.
  • Four structs (IndependentPart, PartModel, SolvedPart, PartSolve) describe one concept.
  • InexactObjective.inexact_terms should have typed reasons, not strings.
  • DominatedCandidate.reason is the same text for every entry.

6. Inputs, constraints, objective and output, with an example. See the comment below. It instantiates every variable, each row family (1–9) and the cost terms on the hand-built catalog shared_middle (groups/tests.rs), extended by one recompute candidate. It then shows the decoded DagOfSelectedCandidates, and maps #1095's q1–q4 example onto the code's structures.

• Add that example as a test (shared_middle plus the c5 candidate). It is not in the suite today.

Input/output check with the DAG viewer

• Input: the expanded memo of a workload. Output: the selected candidate per group, the search report (status, rounds, evaluations, bound), and rejected candidates with reasons.
• Check: on small workloads, the selected plan's cost equals the cheapest enumerated candidate DAG (stage_pipeline: price every enumerated candidate DAG and flag any cheaper than the selected plan #1004); on the paper workloads, the status says whether the result is proven optimal.

Related issues

Sub-issues: #888, #929, #928, #927, #879, #964, #963, #994, #993, #949, #673, #946, #947, #726, #945, #898, #754, #660, #615, #733, #791, #843, #896, #918, #349, #347, #322, #250, #436, #454.

Referenced: #1002, #1004 (enumeration and pricing every candidate DAG, under #1008), #917 and #919 (planner_fuzz tooling), #958 (layout), #948 (naming).

🤖 Generated with Claude Code