[Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047

Example

A two-query PromQL workload:

q1: quantile_over_time(0.9, latency[5m])
q2: quantile_over_time(0.5, latency[5m])

On main (cef05d2), these queries pass through these values between stages:

Vec<(Id, QueryRoot)>                                                                     Stage 0 output
LogicalMemo                      groups: latency[5m], q1, q2                             Stage 0 → 1
PerComputationCandidates<Id>     targets: q1 -> [Exact, Summary(KLL), ...], q2 -> [...]  Pass 1
CandidateMemo                    same groups, Pass 1 candidates attached                 Pass 1 (again)
CandidateMemo                    + pane candidates                                       Pass 2
CandidateMemo                    + shared group S = "KLL build over latency[5m]",        Pass 2 (end)
                                   q1/q2 gain "read S" candidates
CandidateConfigurationInventory  physical candidates x materialization/timing            Stage 2 (private to plan-selection)
Selection                                                                                Stage 3

Three problems are visible here:

• One type, CandidateMemo, stands for three different stage outputs.
• Stage 2's real output is crate-private inside Stage 3's crate.
• Stage 3 calls Pass 2 and Stage 2 itself.

The target is one named type per stage boundary, with each stage or pass calling no other stage:

PlanningWorkload
   │  Stage 0: frontends + hash-consing
   ▼
DagOfLogicalMemoGroups
   │  Stage 1, Pass 1: per-computation candidates
   ▼
PerComputationLogicalMemoCandidates
   │  Stage 1, Pass 2: sharing across computations
   ▼
LogicalASAPMemoCandidates
   │  Stage 2: physical implementation, timing, materialization
   ▼
PhysicalASAPMemoCandidates
   │  Stage 3: check, price, select
   ▼
Selection

Status (2026-10-31)

Stages 0–2 are done on refactor/stage-boundaries. The blocks below show the code on that branch; where it differs from what was decided on 2026-10-29, the block says so with a // code: note. Stage 3 internals are out of scope here: the #1095 owner-scoped MILP redesign was removed in #1133 (kept at the tag stage3-owner-milp-redesign), the old engine is Stage 3's only engine, and only the frozen select_plan interface below is part of this issue.

Open (Stages 0–2):

• Memo layout across crates (D1). MemoCandidates (renamed from CandidateMemo in refactor: #1047 remaining renames (budget_share → accuracy_budget_parts, CandidateMemo → MemoCandidates) #1137) is a public struct with public fields groups, query_roots, candidates, and it is the public memo field of PerComputationLogicalMemoCandidates and LogicalASAPMemoCandidates. The issue's crate-private MemoCandidates { groups, candidates_by_group } inside newtypes is impossible as written, because asap-types defines it and the logical crate builds it. Decide: keep it as is (and update this text), or give the newtypes private fields with constructors and accessors in asap-types.
• Gates before merging to main: planner and sketch-plan snapshots, plus a retro-check of main vs the branch head (plans and costs identical or each difference explained; planning time and peak RSS within 10%; guarantees both ignored and enforced). See "Planner performance (acceptance)".
  • code: decided 2026-10-31, the planning-time threshold does not apply to this merge. Stage 3 now takes only a deadline (no evaluation cap), so the pane-width rounds run through Complete; plans and costs are unchanged and more of them are proven optimal, but slow corpus queries plan 5–15× longer. [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 replaces the engine. Stage 3 search-quality losses found by the retro-check are accepted until [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 and listed in the merge PR.

Closed by a decision (no code change): MemoGroup.parents / queries stay pub fields with the "Stage 1 maintains" doc comment, and parent_groups() / reached_by_queries() are the read API (D3, #1146). Stage 2's pruned key is PhysicalCandidateKey { operator_node, timing, materialization }. OperatorNodeOfCandidateForMemoGroup.accuracy_budget_parts stays as part of the boundary (#1133).

Concrete maintenance problem

1. Pass 1 has two output shapes. PerComputationCandidates is a list of targets. Deployment pruning, early query pruning, Stage1ToStage3Run and run_stage1_to_stage3_from_pass1 use it. CandidateMemo is the same set of candidates attached to memo groups, and it is what Pass 2 reads. try_populate_pass1 converts between the two from inside route.rs.

2. One type serves three boundaries. CandidateMemo is the Pass 1 output, an intermediate value inside Pass 2, and the Pass 2 output. Nothing at compile time stops a memo that Pass 2 has not processed from reaching Stage 2.

3. Stage 2's output is private to Stage 3's crate. Stage 3 searches over CandidateConfigurationInventory, which is pub(in crate::search) in asap-plan-selection. PhysicalWorkloadPlan reads like the Stage 2 output but is rebuilt only for an assignment the search has evaluated.

4. Stages call each other. About a dozen non-test files in asap-plan-selection call Stage 1 or Stage 2 functions (optimize_physical_asap*, try_populate_pass1, extend_local_window_composition, expand_concrete_summary_state_groups*, …). Two examples:

   • Stage 3 runs Pass 2 inside its pane-width search loop.
   • prune_query_candidates runs Pass 2, Stage 2 and Stage 3 checks right after Pass 1.

5. Pruned candidates are recorded in four shapes, or not at all. The four shapes are:

   • ComputationTarget.choices.pruned (Pass 1)
   • QueryCandidatePruningReport.removed (crate-private; only the first 8 are kept)
   • PrunedCandidate { from_logical, reason } (Stage 2; only with keep_every_candidate)
   • Selection.rejected (Stage 3)

   Stage 2's structural pruning keeps only counts.

6. Names don't say what they hold. Examples: expand_concrete_summary_state_groups, MemoGroup.roots_of, budget_share (which holds n, not 1/n), Selection.front.

Before and after structure

Decided 2026-10-29.

Overview

Principles

• No calls across stages.
  • A stage or pass reads only the previous step's output type, so dependencies point one way. It never calls another stage's functions, earlier or later.
  • The asap-planner facade calls the stages in order. This overrides 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's "plan selection may call Stage 2 per candidate".
• Stage crates never depend on each other ([Refactor] Crate organization by stage: per-crate functionality, cross-stage code into asap-accuracy / asap-cost / asap-types, enforced crate boundaries, public vs private #1054). Every type in this issue's "Shared types" and every stage output type lives in asap_types::stages. A stage may use the shared asap-accuracy and asap-cost crates. A cross-stage call is therefore a compile error.
• Each stage prunes only what its own knowledge rules out, or what is provably dominated under the shared cost model (asap-cost). Dominated means the pruned candidate's cost lower bound is ≥ the kept candidate's upper bound, for the same output, a guarantee at least as strong, and the same sharing (the memo design's "keep the cheapest per sharing signature").
  • It records each removal in its own pruned_candidates, using one shape: PrunedCandidate<C>.
  • Stage 0 and Pass 2 have none: Stage 0 fails with an error, and Pass 2 only adds candidates.
  • This replaces prune_query_candidates.
• Queries are entry indices. Every type identifies a query by its index in QueryWorkload::entries(). The caller's Id stays in the facade.
• Stage outputs move by value. Memos are cloned only when inspection (exhaustive, memo steps) is on.

Shared types

Names follow #1050 within #1047's scope. PR #1052 implements #1050's renames, which are the type names below plus the cache renames. #1047 renames only the fields and functions listed in P2–P4:

ComputationCandidate becomes HowToComputeAggregateMeasure, as in #1050. It is an enum of computation kinds (Exact, ExactAccumulator(kinds), Summary(family)), not a concrete, sized candidate, so it does not take the *Candidate suffix. The concrete candidates are the CandidateForMemoGroups built from it. (today: …) comments use the names on main before #1050.

pub struct MemoGroupId(pub u32);

/// One distinct logical sub-expression of the workload.
pub struct MemoGroup {
    pub logical_node: Rc<OperatorNode>,       // children are other groups' nodes      (today: node)
    pub child_groups: Vec<MemoGroupId>,       //                                       (today: children)
    // Derived indexes (built once, O(1) lookups). code: public fields, so Stage 1,
    // which builds and extends the memo in another crate, can maintain them;
    // later stages read them through the methods (D3, decided for #1146).
    pub parents: Vec<MemoGroupId>,            // inverse of child_groups
    pub queries: Vec<usize>,                  // queries whose DAG reaches this group
    // `roots_of` deleted: derived from the memo type's `query_roots`
}
impl MemoGroup {
    pub fn parent_groups(&self) -> &[MemoGroupId];
    pub fn reached_by_queries(&self) -> &[usize];
}

/// One implementation candidate: index `index` in group `group`'s candidates.
pub struct CandidateForMemoGroupId { pub group: MemoGroupId, pub index: usize }

/// One way to implement a group.
pub struct CandidateForMemoGroup {
    pub fused_groups: Vec<MemoGroupId>,       // groups a fused computation also implements; empty otherwise
                                              // (today: implements, whose first entry is the owner group)
    pub root_node: Rc<OperatorNode>,          // its nodes down to `input_groups` are private (today: node)
    pub input_groups: Vec<MemoGroupId>,       // implementations chosen separately     (today: children)
    pub origin: OriginOfCandidateForMemoGroup, // Pass1 | SharedBuild | SummaryResult | SummaryInput
                                              // | Panes | Rollup | TopKReuse | WidenedScans
                                              // (today: origin: CandidateOrigin)
    pub accuracy_budget_parts: usize,         // n: its summaries are sized for 1/n of the budget
                                              //                                       (today: budget_share)
}

/// One candidate a stage removed, and why. `C` is the stage's candidate type.
pub struct PrunedCandidate<C> {
    pub group: MemoGroupId,
    pub candidate: C,
    pub reason: PruneReason,
}

/// One enum for every stage. It merges today's Pass 1 `PruneReason`
/// (RequiresExact, NullableAvgInput, UnsupportedByDeployment, …) and
/// Stage 3's `RejectionCause` (AccuracyTargetMissed, …).
pub enum PruneReason { /* … */ }

/// Shared layout of the memo-candidate types (was CandidateMemo; renamed in #1137).
/// code: public, with public fields, since asap-types defines it and the
/// logical crate builds it; open question D1 (Status).
pub struct MemoCandidates {
    pub groups: Vec<MemoGroup>,
    pub query_roots: Vec<QueryRoot<MemoGroupId>>,         // one per query, over groups
    pub candidates: Vec<Vec<CandidateForMemoGroup>>,      // index = MemoGroupId
}
impl MemoCandidates {
    /// Groups in dependency order; None when the reads form a cycle, a group reading itself included (#1138).
    pub fn topological_order(&self) -> Option<Vec<MemoGroupId>>;
}

Stage 0: query-language frontends and hash-consing

Functionality

1. Lower each query entry to one Pre-ASAP QueryRoot. This is language-specific and needs no deployment input.
2. Hash-cons all roots into DagOfLogicalMemoGroups, with one group per distinct logical sub-expression.

Input

Output: DagOfLogicalMemoGroups

// asap_types::stages (moved from the logical crate in #1146)
pub struct DagOfLogicalMemoGroups {
    pub groups: Vec<MemoGroup>,                          // children before parents
    /// One per query, over groups, built during hash-consing.
    /// (today: original_roots, as nodes)
    pub query_roots: Vec<QueryRoot<MemoGroupId>>,
    // `group_of` (node pointer → group) is a private field: Pass 1 walks
    // the memo groups (an Aggregate group is a target), not nodes (#1012).
    group_of: HashMap<*const OperatorNode, MemoGroupId>,
    // `build_duration` deleted: no non-test code reads it
}
impl DagOfLogicalMemoGroups {
    /// Builds it from its parts; only Stage 1's hash-consing calls it.
    pub fn new(groups: Vec<MemoGroup>, query_roots: Vec<QueryRoot<MemoGroupId>>,
               group_of: HashMap<*const OperatorNode, MemoGroupId>) -> Self;
    pub fn group_for_node(&self, node: &Rc<OperatorNode>) -> Option<MemoGroupId>;
    pub fn roots_over_groups(&self) -> Vec<QueryRoot>;
}

Functions

fn lower_promql_query_workload(&PlanningWorkload /*, HistogramCatalog */) -> Result<Vec<QueryRoot>, PromqlError>; // unchanged
// asap_logical_asap_optimization: a free function, since the type is in asap-types and
// hash-consing (`share_common_sub_dags`) stays in the logical crate (#1146; was the
// `from_roots` method, whose `Id` parameter #1139 dropped). Query i is roots[i].
pub fn generate_dag_of_logical_memo_groups(query_roots: &[QueryRoot]) -> DagOfLogicalMemoGroups;

Prunes: nothing. A query that cannot be lowered fails planning with an error.

Today → after: LogicalMemo::from_roots is called from run_stage1_to_stage3_with in asap-plan-selection. After the change, the facade calls generate_dag_of_logical_memo_groups as part of Stage 0.

Stage 1, Pass 1: per-computation candidates

Functionality

For every computation target, meaning one measure of an Aggregate with a realization other than plain exact execution, Pass 1:

1. Lists how it can be computed (HowToComputeAggregateMeasure):
   • Exact
   • ExactAccumulator(Vec<ExactKind>), e.g. [Sum, Count] for avg
   • Summary(SketchAlgorithm)
   • a fused computation that absorbs the targets beneath it
2. Turns each into sized CandidateForMemoGroups on the target's memo group. All sizing happens here ([Refactor] Crate organization by stage: per-crate functionality, cross-stage code into asap-accuracy / asap-cost / asap-types, enforced crate boundaries, public vs private #1054): ε, the budget share accuracy_budget_parts 1…n, and the whole-result δ split over the group count G. The δ split moves here from add_scoped_candidates (plan-selection) and from Stage 3's resize_for_failure_probability. Pass 2 only inherits sizes (panes) or takes the strictest reader's size (shared builds), and Stage 3 never resizes. The sizing functions are in asap-accuracy.
3. Prunes:
   • summaries the deployment does not support
   • candidates provably unable to run or to meet the requirement (RequiresExact, NullableAvgInput, …)
   • candidates whose composed guarantee cannot meet the query's accuracy target in any combination within that query. This check is new and moves here from prune_query_candidates. code: without_summaries_no_query_can_use (feat: Pass 1 prunes summaries no reading query can use for its accuracy target #1116, fix(stage3): A1 accuracy rows match satisfies; Pass 1 prunes unusable summaries; parts record the sized shares (#1095) #1129), reason NoErrorBoundForQueryTarget; it composes each summary with every other target exact (the most favorable combination), runs only when the accuracy model and evidence cannot accept an output without its guarantee, and keeps a summary another aggregate over the same source may reuse in Pass 2.
     For example, take quantile_over_time(0.9, data[5m]) / quantile_over_time(0.5, data[5m]) with max_error 0.01 and no operand-domain evidence. No summary combination has a guarantee at the root, so only Exact remains.

Pass 1 does not consider sharing across computations; that is Pass 2.

Input

Output: PerComputationLogicalMemoCandidates

// asap_types::stages, with ComputationTarget, FusedComputation, HavingEntry, HavingPlacement
// and HowToComputeAggregateMeasure (moved from the logical crate in #1146)
pub struct PerComputationLogicalMemoCandidates {
    /// Groups moved (not copied) from DagOfLogicalMemoGroups; every candidate has origin = Pass1.
    /// code: `memo.query_roots` holds the query roots (one per query, over groups: an operator
    /// query is `Operator(group)`; a scalar query (`sum(a) / sum(b)`) is `Scalar(expression)`
    /// referencing several groups); there is no separate `query_roots` field (D1).
    pub memo: MemoCandidates,
    /// One per aggregate measure: what Pass 1 chose among. Kept for inspection
    /// and `combinations()`; whether it can be removed is decided in #1012.
    /// Most of it is already in the implementation candidates: the measure
    /// filter as SummaryAgg.filter, HAVING as a Filter above, sizes as candidates,
    /// absorbed targets as fused_groups.
    pub computation_targets: Vec<ComputationTarget>,  // (today: PerComputationCandidates::targets)
    pub pruned_candidates: Vec<PrunedCandidate<HowToComputeAggregateMeasure>>,
}

pub struct ComputationTarget {
    pub aggregate_group: MemoGroupId,             // (today: aggregate: Rc<OperatorNode>)
    pub measure_index: usize,                     // (today: measure)
    pub ways_to_compute: Vec<HowToComputeAggregateMeasure>, // (today: choices.candidates; choices.pruned → pruned_candidates)
    pub measure_filter: Option<Predicate>,        // (today: filter)
    pub having_filters: Vec<HavingEntry>,         // (today: having)
    pub fused_computation: Option<FusedComputation>, // (today: fused)
    // `raw_data_samples_of` removed from the output (#1139): composition derives it
    // from the aggregate's input
}

pub struct FusedComputation {
    pub absorbed_targets: Vec<usize>,             // indices into computation_targets (today: absorbs)
    pub ways_to_compute: Vec<HowToComputeAggregateMeasure>, // (today: candidates; pruned → pruned_candidates)
}

This is also the Pass 2 input; there is no separate Pass 2 input type.

Function

pub fn generate_per_computation_logical_memo_candidates(
    dag_of_logical_memo_groups: DagOfLogicalMemoGroups,
    accuracy_targets: &[AccuracyTarget],
    accuracy: &dyn AccuracyModel,
    evidence: &dyn AccuracyEvidenceProvider,
    data: &DataWorkload,
    supported_summaries: Option<&[SupportedSummary]>,
    deadline: Option<Instant>,                          // code: the sizing step stops at the deadline
) -> Result<PerComputationLogicalMemoCandidates, PerComputationLogicalMemoCandidatesError>;
// code: the error enum (#1139) is PerComputation(PerComputationCandidateError) (bad input),
// Population(CandidatePopulationError) and Sizing(SchemaDerivationError) (internal bugs),
// Timeout(CandidateGenerationTimeout) (budget ran out).

Today → after

Stage 1, Pass 2: ASAP-aware sharing across computations

Functionality

The single entry generate_logical_asap_memo_candidates calls each rule explicitly, in this order. Today steps 2–9 run hidden inside expand_concrete_summary_state_groups*.

1. Local window composition: pane candidates for this round's pane widths (extend_local_window_composition).
2. Scan widening (scan_labels::add_scan_label_candidates).
3. Summary inputs (summary_inputs::factor_summary_inputs).
4. Top-k reuse (topk::add_topk_candidates).
5. Finer aggregate (finer_aggregate::add_finer_aggregate_candidates).
6. Rollup (rollup::add_rollup_candidates).
7. Window rollup (rollup::add_window_rollup_candidates).
8. Summary results (summary_results::factor_summary_results).
9. Shared configurations (shared_configuration_readers::add_state_configuration_candidates_in_domain).
10. Last step, add_shared_summary_state_groups: give each summary build its own group (S in the example), and add a "read S" candidate in each reader group, so that Stage 2 and Stage 3 can choose one shared build. It does only this step.

Pass 2 only adds groups and candidates. It prunes nothing.

Input

Output: LogicalASAPMemoCandidates

// asap_types::stages
pub struct LogicalASAPMemoCandidates {
    /// The Pass 1 groups plus the groups Pass 2 adds (pane chains, shared
    /// summary states). Per group: the Pass 1 candidates plus every Pass 2
    /// rule's (`origin`), including "read the shared state" candidates.
    /// code: public, and `memo.query_roots` holds the query roots passed
    /// through from Pass 1 (D1).
    pub memo: MemoCandidates,
    // `StateGroupExpansion` deleted; Pass 2 returns the memo directly. Its
    // `state_groups` and `added_reader_candidates` are read only by tests, and a
    // shared-state group is recognized by its node (`SummaryAgg` / `PaneChain`)
}

Functions

pub fn generate_logical_asap_memo_candidates(
    round: &mut Pass2RoundState,                 // code: was `pass1: &PerComputationLogicalMemoCandidates`
    entries: &[QueryWorkloadEntry],
    domain: PaneWidthDomain,
    deadline: Option<Instant>,
) -> Result<LogicalASAPMemoCandidates, LogicalASAPMemoCandidatesError>;

// Inside Pass 2, after the rules 1–9 above:
fn add_shared_summary_state_groups(memo: &mut MemoCandidates, pane_widths, deadline) -> Result<(), …>;

Today → after

Stage 2: physical ASAP-aware optimization

Functionality

For every implementation candidate, Stage 2:

1. Implements its operators physically.
2. Enumerates the allowed timing (ingestion or query time) and materialization:
   • not materialized
   • at ingestion
   • at query time, shared within one evaluation
   • at query time, kept across evaluations
3. Records which candidates can produce each input, and the legality that depends on which readers are selected.
4. Prunes:
   • candidates it cannot implement
   • materializations the data or deployment cannot support (no ingesting data, query-time results not retained)

Stage 2 does not price anything.

Input

Output: PhysicalASAPMemoCandidates

pub struct PhysicalASAPMemoCandidates {
    /// One per operator node of an implementation, before Stage 2 chose its timing and materialization.
    pub operator_nodes_of_candidates_for_memo_groups: Vec<OperatorNodeOfCandidateForMemoGroup>,
    /// One per (operator node, timing, materialization): what Stage 3 selects; Stage 3 decides how many times it runs.
    /// (today: CandidateDependencyGraph::candidates + CandidateConfigurationInventory::configurations
    ///  + CandidateOperatorTemplates)
    pub candidates: Vec<PhysicalCandidate>,
    pub query_roots: Vec<QueryRoot<MemoGroupId>>,                // passed through from Pass 2
    pub reader_constraints: Vec<ReaderConstraint>,               // legality depending on the selected readers
    /// What Stage 2 pruned, with Stage 2's PruneReasons (P6, #1104). A pruned candidate has no
    /// PhysicalCandidateId (kept candidates are renumbered), so its key names what it would have been.
    pub pruned_candidates: Vec<PrunedCandidate<PhysicalCandidateKey>>,
    implementation_roots_of_group: Vec<Vec<PhysicalCandidateId>>, // private index over `candidates`, built once by `new`
    output_reference_groups: Vec<MemoGroupId>,                    // private: each output reference's group
}

/// The key of a Stage 2 pruned candidate: unique, since Stage 2 makes no copies.
pub struct PhysicalCandidateKey {
    pub operator_node: OperatorNodeOfCandidateForMemoGroupId,
    pub timing: ExecutionTiming,
    pub materialization: Materialization,
}
impl PhysicalASAPMemoCandidates {
    /// Builds the private index. Stage 3's component search uses it to build one smaller catalog per component.
    pub fn new(/* the public fields */) -> Self;
    /// The implementation roots of `group`. (today: CandidateInventory::group_candidates)
    pub fn implementation_roots(&self, group: MemoGroupId) -> &[PhysicalCandidateId];
    /// The candidates that may produce output reference `output_reference`
    /// (each group reference of `query_roots`, in order; a scalar query has
    /// several): its group's roots with `may_produce_query_output`.
    /// (today: graph.query_roots)
    pub fn query_output_candidates(&self, output_reference: usize) -> impl Iterator<Item = PhysicalCandidateId>;
}

/// One operator node of one or more candidates for a memo group, before Stage 2
/// chose its timing and materialization. (today: an inventory candidate + its template)
pub struct OperatorNodeOfCandidateForMemoGroup {
    pub candidates_for_memo_group: Vec<CandidateForMemoGroupId>, // every candidate of the group this node can
                                                  // implement: identical terminal readers are factored into one
                                                  // node; the selected producers decide which one it implements
    pub is_implementation_root: bool,             // false for the implementation's private nodes
    pub physical_node: Rc<OperatorNode>,          // one operator node, with Stage 2's physical implementation
    pub accuracy_budget_parts: usize,             // how many equal shares of a query's accuracy budget this node's
                                                  // sketch sizes meet (CandidateForMemoGroup::accuracy_budget_parts;
                                                  // the largest among a factored node's candidates, whose sizes are
                                                  // equal; 1 when exact). Kept as part of the boundary for
                                                  // Stage 3's redesign (#1095); no production reader yet (#1133)
}

/// One operator node with one timing and materialization: what Stage 3 selects (no scope copies; 2026-10-30).
pub struct PhysicalCandidate {
    pub operator_node: OperatorNodeOfCandidateForMemoGroupId, // (today: CandidateConfiguration::source_candidate)
    pub timing: ExecutionTiming,                  // IngestionTime | QueryTime
    pub materialization: Materialization,         // NotMaterialized | MatAtIngestion(Medium) | MatAtQuery(Medium) | …
                                                  // both kept: a node that is not materialized under an
                                                  // ingestion-time build still runs at ingestion time
    pub producer_candidates_per_input: Vec<ProducerCandidates>, // per input, the candidates that may produce it
                                                  // (today: producer_requirements); depends on timing
                                                  // (code: "producer", not "supplier", #1100)
    pub may_produce_query_output: bool,           // a root at query time whose output matches its group's
                                                  // logical node (today: computed into graph.query_roots)
    pub may_keep_across_evaluations_per_sole_reader_query: Vec<bool>, // per query: may this pane chain be kept
                                                  // across evaluations when that query is its only reader (#1054 X3;
                                                  // today: may_keep_with_sole_reader)
}

Functions

pub fn generate_physical_asap_memo_candidates(
    logical: &LogicalASAPMemoCandidates,
    entries: &[QueryWorkloadEntry],
    data: &DataWorkload,
    query_time_results_retained: bool,
    raw_data_retained: bool,             // no raw data → no query-time raw scans (deployment cannot support them)
    deadline: Option<Instant>,
) -> Result<PhysicalASAPMemoCandidates, ErrorGeneratingPhysicalASAPMemoCandidates>;

// Called by the facade after Stage 3, not by Stage 3. Builds the one copy of
// the selected plan: its DAG and its query roots (PlanOutput's roots are
// derived from it), with Stage 3's confirmed weight proofs applied.
// superseded 2026-10-30: the facade calls AssignmentRealizer::realize (Stage 3 section)
pub fn build_selected_physical_plan(
    physical: &PhysicalASAPMemoCandidates,
    selection: &Selection,               // selected_candidates + weight_confirmed_candidates
) -> Result<PhysicalWorkloadPlan, PhysicalASAPOptimizationError>;

Today → after

PhysicalWorkloadPlan (one evaluated assignment rebuilt as a DAG) is not a stage-boundary type, and it keeps its name.

Stage 3: plan selection

Functionality

1. Check each physical candidate and each assignment:
   • accuracy: check only, against the sizes Stage 1 chose; no resizing and no DAG recompilation ([Refactor] Crate organization by stage: per-crate functionality, cross-stage code into asap-accuracy / asap-cost / asap-types, enforced crate boundaries, public vs private #1054)
   • latency
   • raw-data retention: a Stage 2 prune reason (RawDataNotRetained, P6); Stage 3 no longer checks it
2. Price valid assignments under the cost model: cost model 1, 2 or 3, with measured operation costs and calibration.
3. Select one assignment with the joint search (MILP over the memo).
4. Prune single candidates that fail every assignment before the joint search, and reject whole plans that fail a check or lose under the cost model.

Input

Decided interface (2026-10-30 naming and redundancy review; the same block is in #1047 and #1095). Implemented in P7 (#1107) and frozen; Stage 3's internals behind it are the old engine (#1133) until the Stage 3 redesign.

// asap-plan-selection: the only public entry
pub fn select_plan(
    physical: &PhysicalASAPMemoCandidates,
    entries: &[QueryWorkloadEntry],              // accuracy target, latency bound, recurrence per query
    data: &DataWorkload,                         // with its bounds (rows, G, source rates)
    accuracy_checks: &AccuracyCheckInputs<'_>,
    cost_inputs: &CostInputs,                    // asap-cost
    realizer: &dyn AssignmentRealizer,           // asap_types::stages, implemented by Stage 2, built by the facade
    deadline: Option<Instant>,                   // the only budget: one MILP solve, one realization
) -> Result<Selection, ErrorSelectingPlan>;      // Err: infeasible, no plan by the deadline, or the realizer
                                                 // rejected the decoded plan (RealizerRejected: a Stage 2
                                                 // catalog bug, never a cut and re-solve)

/// Inputs of the composed-accuracy check. `raw_data_retained` is a Stage 2 input only
/// (decided 2026-10-30); `ignore_accuracy_guarantees` is an accept-all `model` from the facade.
pub struct AccuracyCheckInputs<'a> {
    pub model: &'a dyn AccuracyModel,
    pub evidence: &'a dyn AccuracyEvidenceProvider,
}

pub struct Selection {
    pub selected_dag: DagOfSelectedCandidates,
    /// Selected candidates whose open count-min weight requirement Stage 3 proved;
    /// the facade applies the proof when it builds the plan.
    pub nodes_with_proven_non_negative_weights: Vec<SelectedNodeId>,
    pub cost: PlanCost,                                   // asap_cost::plan_cost (was CandidateCost)
    pub accepted_accuracy_per_query: Vec<AcceptedAccuracy>,
    pub pruned_candidates: Vec<PrunedCandidate<PhysicalCandidateId>>,
    pub search_report: SearchReport,
    // deleted: selected_plan_id, plan, cost_by_plan / costs, accepted_accuracy_by_plan / accepted,
    // front / pareto_front (C4), pane_retention_ms (moves to RealizedPlan),
    // rejected / rejected_plans (one validation; a realizer rejection is an Err)
}

pub struct SearchReport {
    pub status: SearchStatus,                             // Optimal | DeadlineReached (HiGHS time limit:
                                                          // validated incumbent, gap > 0)
    pub cost_lower_bound_per_second: Option<f64>,         // HiGHS dual bound; relative_gap() is a method
    pub milp_variables: usize,                            // one model, one solve
    pub milp_constraints: usize,
    pub model_construction_ms: u64,
    pub solver_ms: u64,
    pub validation_ms: u64,
    // deleted: evaluations / candidates_checked / refinements, milp_solves, EvaluationLimitReached
    // and max_evaluations (one solve, no evaluation loop), runner_up_cost_per_second (no runner-up),
    // rejected_by_cause and search_rejected (now pruned_candidates), pane_widths_pending (the facade
    // reads Pass 2's round state)
}

// asap_types::stages: the selection is DagOfSelectedCandidates (#1095 §2.0, "Stage 2 emits no copies")

/// One method. The facade builds the realizer with the planning context (original roots,
/// entries, data, query_time_results_retained). Stage 3 calls it once to validate its plan, and the
/// facade calls the same method to build the final plan (replaces build_selected_physical_plan).
pub trait AssignmentRealizer {
    fn realize(&self, physical: &PhysicalASAPMemoCandidates, selected: &DagOfSelectedCandidates)
        -> Result<RealizedPlan, PhysicalCandidateError>;
}
/// was SelectedPhysicalCandidate; holds the PhysicalWorkloadPlan and pane_retention_ms
/// (keyed by node id, derived from the plan and its readers' range spans)
pub struct RealizedPlan { /* … */ }

Today → after

Facade (asap-planner)

Functionality

1. Validate the input.
2. Run Stage 0 → Pass 1.
3. For each pane-width round, run Pass 2 → Stage 2 → Stage 3. Stop when Stage 3 reports the domain complete or the budget runs out.
4. Keep the best validated selection across rounds, together with that round's Pass 2 and Stage 2 outputs: its PhysicalCandidateIds are valid only in the PhysicalASAPMemoCandidates of the round that produced it.
5. Call AssignmentRealizer::realize (Stage 2's Stage2AssignmentRealizer) with the selected round's Stage 2 output (the one copy of the plan: DAG and query roots; pane_retention_ms mapped to node ids), then installable_plan_of.
6. Own the total time budget and the caller's query Ids.
7. Copy memos only when inspection is on (PlanSearchSettings::inspect, refactor(planner): copy memos only when inspecting (#1047) #1140).

Input: UserInput { workload, frontend_specific, models: PlanningModels, pass }, unchanged. The facade splits PlanningModels and DeploymentCapabilities by stage; for Stage 3 into AccuracyCheckInputs and CostInputs.

Output

pub async fn e2e_plan(input: UserInput<'_>) -> Result<PlanOutput, PlanError>;   // unchanged signature

/// How the facade searches.
pub struct PlanSearchSettings {
    pub time_limit_ms: Option<u64>,   // the whole planning budget; default 30 s
    pub inspect: bool,                // keep per_computation_candidates and memo_steps; default false (#1140)
}

/// Every stage's output, for stage_pipeline. (today: Stage1ToStage3Run<Id>)
pub struct PlanningRun {
    // no `logical_memo`: Stage 0's groups are per_computation_candidates' groups without candidates
    /// Pass 1's output; None when Pass 1 failed or without `inspect` (#1139, #1140). (was: pass1)
    pub per_computation_candidates: Option<PerComputationLogicalMemoCandidates>,
    /// The selected round's (or the last round's when none is selected), moved, not copied;
    /// None when no round ran that far. (was: pass2, stage2)
    pub logical_asap_candidates: Option<LogicalASAPMemoCandidates>,
    pub physical_asap_candidates: Option<PhysicalASAPMemoCandidates>,
    pub selection: Result<Selection, SelectionError>,
    pub selected_physical_plan: Option<RealizedPlan>,   // the plan with its pane retention
    pub selected_plan: Option<Vec<QueryRoot>>,          // the roots to run, with Stage 3's weight proofs applied
    /// The memo after each step of the selected round, and the selected plan's choice
    /// over it; only with `inspect`.
    pub memo_steps: Option<MemoSteps>,
    pub report: PlanningReport,                         // per round: counts and Pass 2 / Stage 2 / Stage 3 times
    // `evaluated_plans` deleted: the devtools reference pricer enumerates plans itself
}

/// The memo after each step of the selected round (only with `inspect`).
pub struct MemoSteps {
    pub pass2: MemoCandidates,                          // after local window composition
    pub concrete_states: MemoCandidates,                // the memo Stage 2 implements
    pub stage2_operator_nodes: Vec<OperatorNodeOfCandidateForMemoGroup>,
    pub stage2_pruned_candidates: Vec<PrunedCandidate<PhysicalCandidateKey>>,
    pub selected_chosen_candidates: Result<ChosenCandidatePerMemoGroup, String>,
    // deleted: stage0 (= per_computation_candidates' groups), pass1 and pass1_pruned_candidates
    // (= per_computation_candidates) (#1139, #1140)
}

Today → after:

• run_stage1_to_stage3{,_with,_from_pass1}, candidate_connection_search and search_domain (in asap-plan-selection) become facade orchestration.
• The stage work they do now moves into the stage functions above.

Behavior that must remain unchanged

• Selected plans and their costs stay the same.
• A pruned candidate may now be recorded in the stage that rules it out, instead of in today's crate-private report.
• stage_pipeline documents change only in field names and in the new per-stage pruned_candidates lists.

Planner performance (acceptance)

The refactor must not make planning slower or larger.

Measure before and after on the same host with a release stage_pipeline, on:

• every workload under tools/dag-viewer/memo-examples/: promql/ratio-of-quantiles-5m.json, the five promql/rangeheavy-*.json, and sql/rollupheavy-t11-service-endpoint-5m.json (with sql/tables.json)
• the random mixed workloads behind tools/dag-viewer/examples/random-mixed-seed-862-*.json

Report:

• the selected plan and its cost: must be identical
• total planning time and the time of each stage
• peak RSS
• memo groups and candidates after each step

Threshold: total planning time and peak RSS within 10% of main. (code: planning time waived for the Stages 0–2 merge, see Status.)

Performance constraints:

• Stage outputs move by value. Memos are cloned only when inspection is on (done in refactor(planner): copy memos only when inspecting (#1047) #1140: PlanSearchSettings::inspect); before, route.rs cloned the memo on every run.
• The newtypes over MemoCandidates cost nothing at run time (code: they hold it as a public memo field, D1).
• Pass 1's accuracy pruning is per query, with no Cartesian product across queries.
• Pane-width round reuse is decided by measurement ([Refactor] Pane-width rounds without cross-stage calls: rerun Pass 2 per round, or pass an incremental Pass 2 state #1048).

Why the proposed structure is minimally complex

There is one type per stage boundary, and each name says what it holds:

• DagOfLogicalMemoGroups → PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates → Selection
• *Candidates for anything the planner chooses among

Removed:

• CandidateMemo
• the separate target-list form of the Pass 1 output
• fields no non-test code reads: LogicalMemo.build_duration, StateGroupExpansion::state_groups, and raw_data_samples_of in the output
• derived copies:
  • MemoGroup.roots_of
  • the owner group in implements
  • Stage 2's group_candidates and query_roots (they become methods over candidates)
  • Selection.plan (the facade builds the one plan)
  • PlanningRun.logical_memo
  • LogicalMemo's node-pointer map in the public type (Pass 1 walks groups; Stage 1 Pass 1 review: per-computation candidates over memo groups #1012)
  • PhysicalCandidate.group + an implicit index, replaced by one CandidateForMemoGroupId
• SearchAlgorithm, which has a single value
• keep_every_candidate, which every caller sets equal to exhaustive

Derived indexes that rules need often (parent_groups, reached_by_queries, Stage 2's per-group index) are read through methods, and lookups stay O(1). Stage 2's per-group index is a private field. MemoGroup's two indexes are public fields named parents and queries, because Stage 1 maintains them across the crate boundary (D3).

No new layers are added.

Existing unit and end-to-end protection

• asap-logical-asap-optimization and asap-plan-selection --lib
• asap-integration-tests
• stage_pipeline document tests in asap-devtools

Changed modules need their own tests to pass before merge.

Compatibility or migration impact

• Public types and fields are renamed with no compatibility aliases.
• Stage1ToStage3Run<Id> becomes PlanningRun.
• Selection field renames change JSON keys read by ASAPQuery-backend and the DAG viewer.
• PerComputationCandidates / CandidateMemo are referenced today in logical-asap-optimization (17 files), plan-selection (6), integration-tests (6) and devtools (5).

Execution plan (decided 2026-10-29). Each PR must:

• keep the planner snapshots unchanged
• pass the tests of the parts it changes, plus fmt, clippy and asap-plan-selection --lib
• pass an independent review that also checks names against this issue

PRs:

• P2: done in refactor: rename memo group, candidate and computation-target fields (#1047 P2) #1058 (merged 2026-10-29), after PR refactor: rename memo-named caches and the memo types by stage #1052 ([Refactor] Rename memo-named caches and the memo types by stage #1050). Deleting SearchAlgorithm and stage_pipeline --search was split out as P2b, done in refactor: delete SearchAlgorithm and stage_pipeline --search (#1047 P2b) #1059. It does only the pure renames and deletions of [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 that refactor: rename memo-named caches and the memo types by stage #1052 does not do:

  • MemoGroup.node → logical_node, .children → child_groups
  • CandidateForMemoGroup.node → root_node, .children → input_groups, .budget_share → accuracy_budget_parts
  • ComputationTarget.measure → measure_index, .filter → measure_filter, .having → having_filters, .fused → fused_computation; FusedComputation.absorbs → absorbed_targets
  • delete DagOfLogicalMemoGroups.build_duration; delete SearchAlgorithm and stage_pipeline --search (docs updated)

  The structural changes go to P3 and P4: parent_groups / reached_by_queries as methods, roots_of → query_roots, implements → fused_groups, aggregate → aggregate_group, choices → ways_to_compute + pruned_candidates, and StateGroupExpansion removed.

• P3 (done: P3a refactor: query roots over memo groups; MemoGroup parents/queries as methods (#1047 P3a) #1070, P3b refactor: one Pass 1 entry and output type (#1047 P3b) #1081, P3c refactor: Pass 1 walks memo groups; HAVING placed per group; fusions are memo candidates (#1047 P3c, #1089) #1106; the single Pass 1 entry and dropping Id landed with P6 in refactor(logical): one Pass 1 entry; the target list is Pass 1's working form (#1047 P6) #1139) (P3c is option C, decided 2026-10-30: it runs after P6/P6b. Pass 1 makes one target per occurrence; walking memo groups merges duplicates, which changes the target count, pass1_pruned and HAVING placement. Those three are decided together once the legacy path and query pruning are gone. P3a done in refactor: query roots over memo groups; MemoGroup parents/queries as methods (#1047 P3a) #1070; P3b done in refactor: one Pass 1 entry and output type (#1047 P3b) #1081, with aggregate_group and dropping Id moved to P3c, and the single entry for all of Pass 1 moved to P6. Split into P3a: query_roots over memo groups, with parent_groups / reached_by_queries as methods and roots_of removed; P3b: one Pass 1 entry and output type, pruned_candidates, aggregate_group / ways_to_compute / fused_groups, Id dropped; P3c: Pass 1 walks memo groups): Pass 1: one PerComputationLogicalMemoCandidates; DagOfLogicalMemoGroups { groups, query_roots }; Pass 1 walks memo groups. This PR decides Stage 1 Pass 1 review: per-computation candidates over memo groups #1012's group-walk question.

• P4 (done in refactor: one Pass 2 entry; LogicalASAPMemoCandidates (#1047 P4) #1084; Pass2RoundState keeps today's incremental rounds, and [Refactor] Pane-width rounds without cross-stage calls: rerun Pass 2 per round, or pass an incremental Pass 2 state #1048 decides later whether to keep them): Pass 2: the single entry generate_logical_asap_memo_candidates, returning LogicalASAPMemoCandidates.

• P5: Stage 2: generate_physical_asap_memo_candidates in asap-physical-asap-optimization; PhysicalASAPMemoCandidates and CandidateForMemoGroupId in asap_types::stages ([Refactor] Crate organization by stage: per-crate functionality, cross-stage code into asap-accuracy / asap-cost / asap-types, enforced crate boundaries, public vs private #1054). This also counts as 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's Stage 2 move.

• P6: per-stage pruning replaces prune_query_candidates (refactor: Pass 1 and Stage 2 record pruned_candidates; per-entity and raw-data rules move to Stage 2 (#1047 P6) #1104; Pass 1's accuracy pruning feat: Pass 1 prunes summaries no reading query can use for its accuracy target #1116, fix(stage3): A1 accuracy rows match satisfies; Pass 1 prunes unusable summaries; parts record the sized shares (#1095) #1129). Remainder: one Pass 1 entry and output, the target list crate-private, pass1_pruned and ComputationTarget.raw_data_samples_of removed, from_roots without Id (refactor(logical): one Pass 1 entry; the target list is Pass 1's working form (#1047 P6) #1139). Behavior change: compare planning time before and after.

• P6b (done in refactor: delete the legacy whole-workload Pass 2 path and early query pruning (#1047 P6b) #1105): delete the legacy whole-workload Pass 2 path that P6 leaves unused: workload_candidates.rs (stage1_candidates_of_choice, Pass2Candidate, Stage1Candidate), LogicalCandidate.pass2, and the *_pass2_candidates whole-workload entry points (identical expression, summary capability, top-k reuse). Include a table mapping each capability to the memo rule that replaces it.

  • The asap_aware_cse helpers that the memo rules are built on stay where they are: pane_candidates, window_composition_*, rollup_pass2_candidates, rollup_candidate_for, topk_reuse_candidates, with_pane_chain, with_resized_build, with_union_scan_labels. Rewriting them as native memo rules is 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 / Stage 1 Pass 2 review: ASAP-aware CSE rules over memo groups and summary-state groups #1013 work.
  • This replaces the earlier P1. Before P6, prune_query_candidates (query_pruning.rs:325) still calls this path.

• P7 (done in refactor: facade runs the stages; Stage 3's frozen select_plan interface (#1047 P7) #1107, with follow-ups test: area B tests pass on the stage-boundaries branch; fix decoded-output validation (plan-selection, planner) #1110, fix: quantile operand count survives memo sharing; Pass 1 deadline reports the planning budget #1113, refactor: Stage 2 emits no scope copies; the selection is DagOfSelectedCandidates (#1095) #1119; memos copied only with inspect in refactor(planner): copy memos only when inspecting (#1047) #1140) (2026-10-30: implements the Stage 3 interface decided in the Stage 3 section and [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 §1, with no transition period. Users read only Stages 0–2, so Stage 3 outputs that the interface drops, and the tests asserting them, are removed rather than kept. After P7 the interface is frozen and [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 rewrites Stage 3's internals): the facade runs the pane-width rounds ([Refactor] Pane-width rounds without cross-stage calls: rerun Pass 2 per round, or pass an incremental Pass 2 state #1048 option A, measured) and builds the selected plan; PlanningRun, PlanSearchSettings, Selection.selected_candidates. Behavior change: compare planning time before and after.

• P8: Selection field renames, with the matching DAG viewer change (other repos follow on their own). The Rust fields got their names in P7; refactor(devtools, dag-viewer): name reference_pricing keys as Stage 3's Selection (#1047 P8) #1147 renamed the devtools reference_pricing keys and the viewer's reads.

• Remaining renames (refactor: #1047 remaining renames (budget_share → accuracy_budget_parts, CandidateMemo → MemoCandidates) #1137): budget_share → accuracy_budget_parts in the stage_pipeline JSON, the DAG viewer and the logical crate's internal names; CandidateMemo → MemoCandidates.

• Stage 0 and Pass 1 boundary types in asap_types::stages (refactor: Stage 0 and Pass 1 boundary types in asap_types::stages (#1054) #1146): DagOfLogicalMemoGroups, PerComputationLogicalMemoCandidates and the types it holds; generate_dag_of_logical_memo_groups replaces from_roots.

• Memo layout across crates (D1): see Status.

No separate performance-baseline PR for now. P6 and P7 report before/after stage_pipeline runs on the workloads listed above.

Related

• Sub-issue: [Refactor] Pane-width rounds without cross-stage calls: rerun Pass 2 per round, or pass an incremental Pass 2 state #1048 (pane-width rounds without cross-stage calls)
• 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 (reorganize by stage; decision 2: Stage 1 completes the memo, and plan selection is Stage 3 only. Its "may call Stage 2 per candidate" is overridden here.)
• Tracking: plan every whole evaluation workload within 3 minutes (exact pruning, memo-group search) #879 (plan whole workloads within minutes)
• [Refactor] Repo-wide naming survey: overloaded and misleading names #948 (naming survey)
• Stage reviews Stage 0 review: frontends and the logical memo (hash-consed groups) #1011, Stage 1 Pass 1 review: per-computation candidates over memo groups #1012, Stage 1 Pass 2 review: ASAP-aware CSE rules over memo groups and summary-state groups #1013, Stage 2 review: physical optimization and materialization per candidate #1014, Stage 3 review: plan selection, the MILP over the memo, cost and accuracy constraints #1015, asap-planner facade review: orchestration and deployment input assembly #1017