Stage 2 review: physical optimization and materialization per candidate #1014

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

Example: what Stage 2 decides

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). After Pass 2 the memo has 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.) Stage 2 does not run as a pass over them. Stage 3 calls it per candidate while it builds its candidate graph:

• implement_candidate_operators (phys/lib.rs:1103) turns a candidate's nodes into physical operators (for example exact top-k → Sort + Limit).
• summary_materialization_eligibility (phys/lib.rs:261) says whether a summary build (a KLL SummaryAgg of G2, or one of the 336 PaneChains) may run at ingestion time, be kept across evaluations, or be materialized at query time.
• Stage 3 then lists each node's (Materialization, ExecutionTiming) modes itself (ps/search/candidates/configurations.rs:162-222).

For the 1-minute [5m] KLL, the design's options are NotMaterialized, MatAtIngestion(Memory) (tumbling 1-minute panes maintained as data arrives) and MatAtQuery(Memory) when two or more queries read it; here one query reads it, so Stage 2's eligibility says no MatAtQuery (may_materialize_at_query: readers.len() > 1, phys/lib.rs:318), while Stage 3's mode list offers MatAtQuery to every summary (configurations.rs:163-167) and no production code reads may_materialize_at_query (only tests at phys/lib.rs:1674, :1688).

Functionality

• Materialization: for each sub-DAG, not materialized / materialized at ingestion time / at query time (kept within one evaluation or across evaluations), and the medium; with the constraints "upstream of an ingestion-time node runs at ingestion time" and "stored while any reader needs it".
• Physical operator implementation of each node.
• (TODO in the design: parallelism, partitioning, resources.)

Concepts (design doc term ↔ code)

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: over-abstraction / concepts defined twice in the physical stage

• Materialization modes are generated in two places that disagree. Stage 2: materialization_candidates (phys/lib.rs:766) and summary_materialization_eligibility. Stage 3: configurations.rs:162-222, which also pairs (NotMaterialized, IngestionTime) for non-summary nodes while Materialization::timing() says NotMaterialized is query time: two sources of truth for timing. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P5: Stage 3's listing (configurations.rs) moves into Stage 2, leaving one place; the disagreement itself is reviewed here.
• MatAtQuery rule differs: Stage 2 needs two or more readers (phys/lib.rs:318); Stage 3 offers it to every summary (configurations.rs:163), and may_materialize_at_query is read only by tests. Check whether a later Stage 3 step applies the two-reader rule; if not, decide which rule is intended.
• Raw-data retention is enforced twice: configurations.rs:217 ("the same deployment restriction enforced by PlanSelector's raw_data_violation") and PlanSelector in ps/lib.rs. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047: raw_data_retained is read only by Stage 3 (PlanSelectionConstraints).
• Three forms of one assignment: MaterializationAssignment, PhysicalWorkloadPlan.materialization, PhysicalWorkloadPlan.assignment ([Refactor] Repo-wide naming survey: overloaded and misleading names #948).
• Two window-edge types: WindowEdgeCoverage (types/src/physical/summary_window.rs) and WindowEdgeCompatibility (types/src/ir/physical_export.rs).
• root_operators is written three times (phys/lib.rs:743, ps/lib.rs:2675, asap_aware_cse.rs).

1. Boundaries

• Decide the Stage 2 interface on the memo: "candidate → allowed (Materialization) set + physical operators", owned by Stage 2, with Stage 3 only choosing. Today Stage 3 builds the mode list. Decided in [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 (table above).
• DeploymentCapabilities comes from the Stage 1 crate (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 3). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047: Stage 2 receives only query_time_results_retained.
• Execution placement (ingestion vs query time) as a physical choice, not a logical restriction (Separate execution placement from logical semantics and cost ingestion-time alternatives #530); a node shared by queries with different timings (Timing: a node shared across batch queries with different timings fails with ConflictingTiming #654).

2. Naming

• "physical" names a timed logical DAG (PhysicalASAPDAG), a Stage 2 candidate (PhysicalWorkloadPlan, documented as "One CandidatePhysicalASAPDAG") and a Stage 3 graph node (PhysicalCandidate, ps/search/candidates/graph.rs:18) ([Refactor] Repo-wide naming survey: overloaded and misleading names #948).

3. Stale code

• Medium::Disk is never produced; disk is only priced in Stage 3. The doc's Materialization section still describes disk as an option.
• The whole-workload optimize_physical_asap enumeration is uncapped and has one production caller (alone_violation). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P6 removes its production caller.

4. "memo" / "cache"

• type Memo in phys/lib.rs:1132 is a rewrite cache. [Refactor] Rename memo-named caches and the memo types by stage #1050: NodeToImplementedNodeCache.

5. Rules over memo groups

• The doc says Stage 2 chooses a materialization "once for a group however many parents read it". Check that a state group (a shared KLL or PaneChain) gets one choice for all readers, and that a scan read through different windows may be read per reader.

Correctness and efficiency

• For each candidate, the allowed modes match the doc's rules (ingestion-time grid alignment, one new pane per evaluation for kept-across-evaluations).
• Stage 2 work per candidate is reused across Stage 3's pane-width rounds, or the cost of redoing it is measured. [Refactor] Pane-width rounds without cross-stage calls: rerun Pass 2 per round, or pass an incremental Pass 2 state #1048 decides this by measurement.

Input/output check with the DAG viewer

• Input: one implementation candidate of the expanded memo (e.g. a G2 KLL build or a PaneChain state group). Output: its physical operators and allowed materializations, and the chosen one in the selected plan.
• Check: the label says which chain is maintained at ingestion time (Physical candidate labels don't say which pane chain is maintained at ingestion time; distinct plans share a label #876); the allowed modes match between Stage 2 and Stage 3.

Related issues

Sub-issues: #530, #654.

Referenced: #876 (labels, under #1008), #754 (kept-across-evaluations results rarely chosen; cost model, under #1015), #747 and #656 (PhysicalASAPDAG::validate, under #1016), #701 (operators without an executor kernel), #948 (naming), #958 (deployment inputs by stage).

🤖 Generated with Claude Code