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).

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