Stage 1 Pass 2 review: ASAP-aware CSE rules over memo groups and summary-state groups #1013

Part of #1010. Line numbers are on main at 958778400. loa/ = crates/logical-asap-optimization/src/.

Example: what Pass 2 produces

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). In the production planner, read from the stage-pipeline document tools/dag-viewer/examples/memo-ratio-of-quantiles.json (main at d728d05c):

Corrected 2026-10-28: production numbers from the stage-pipeline document; earlier numbers came from a test helper without the series-identity column.

The intended shape for this query, in the design's terms: G2 and G4 read the same data[5m] rows, so a summary-capability rule can add one shared KLL state group (one build sized for every reader) and a candidate in each of G2 and G4 that reads it, beside their own builds. A window-composition rule can add tumbling panes. Points to check against the measurement:

• 336 PaneChain groups for one query (7 summary configurations × 48 pane layouts, pane widths 20 ms to 60 s; window composition alone offers 20 widths, 1 s to 60 s). add_local_window_composition uses PaneWidthDomain::Complete (loa/memo/window_candidates.rs:21-22), every divisor width; then a state group is made for every build that occurs at least twice, "including within one result" (loa/memo/state_groups.rs:148-160). One hypothesis (not confirmed): each pane width's chain appears in a composite candidate and in its factored readout, so each width becomes a state group.
• 10 Pass1 candidates after Pass 2 vs 7 after Pass 1 (the 3 added are KLL candidates the state-configuration rule rewrote: one to the shared size k 1156, two keeping their size; one of those two, KLL k 1184, sized for half the budget, now has budget_share 1). rules/state_configurations.rs adds resized copies that keep their origin; to confirm.
• expanded_memo expands with SeedGrids after offering Complete panes, while production uses one domain for both (plan-selection/src/search/route.rs, search_domain), and does not run accuracy_configurations::add_scoped_candidates. So the measurement is close to, not equal to, the production memo.

Functionality

• Add candidates that share computation across sub-expressions and queries, keeping the independent candidates: identical expression (group identity), summary capability (one build, several estimates), window composition (tumbling panes, newest panes of a shared chain), rollup, exact top-k reuse, scan widening.
• Make each shared configuration concrete: one summary-state group per shared size or pane layout, read by the candidates that can use it.

Concepts (design doc term ↔ code)

Rule ↔ code (memo path, run in this fixed order by expand_with_state_index, state_groups.rs:102-111; window composition runs before it from Stage 3):

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 problems

• (a) Stages mixed. Stage 3 runs Pass 2 and decides its pane-width rounds (route.rs, PaneWidthDomain rounds). Stage 3's query_pruning::alone_violation (plan-selection/src/search/query_pruning.rs:316) runs the whole-workload Pass 2 plus Stage 2 (optimize_physical_asap) per query. State identity reads Stage 2 fields (timing, materialization) in state_groups.rs. (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 decisions 1–2.) [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047: the facade runs the pane-width rounds (P7, [Refactor] Pane-width rounds without cross-stage calls: rerun Pass 2 per round, or pass an incremental Pass 2 state #1048); per-stage pruning replaces alone_violation (P6); the Pass 2 entry runs every rule.
• (b) Not general. Window composition needs a SummaryAgg over a TimeRange and reads only Pass1 / SharedBuild candidates (window_candidates.rs); pane configurations need exactly one plain SummaryMerge (rules/state_configurations.rs); top-k reuse handles only exact TopK → Sort + Limit; scan widening only unfiltered PromQL scans; finer aggregate only SQL. Only state_configurations and topk use the SharedProducer abstraction (One shared-producer rule: cover every reader's need, derive each reader (top-k, summary size, panes, ranks, …) #954 proposes one shared-producer rule).
• (c) Definition of a memo group and the rule algorithm.
  • Group identity is "same logical result", and a summary state is a separate group made after the fact. Decide whether an ASAP memo group is "same output result or same summary state", and write it in planner-layering.md.
  • Rules run once, in a fixed order, with no fixpoint: a later rule sees earlier rules' candidates, never the reverse; expansion is one-shot (AlreadyExpanded, state_groups.rs:91-97) and is rebuilt per pane-width round.
  • The doc's coupling sites (shared-build size, pane chain, scan labels, raw horizon) are state groups or MILP terms in code. Decide which representation is intended (memo-milp: size summaries once (final config per reader set and summary count; Stage 3 never resizes) #929 sizes once per reader set).

1. Boundaries

• Pass 2 is implemented twice (whole-workload in asap_aware_cse.rs + workload_candidates.rs, memo in memo/rules/*), and the memo rules call the whole-workload code as a library. The equivalence test crates/integration-tests/tests/memo_covers_whole_workload_pass2.rs exists to close the gap before deletion (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, Remove dead Pass 2 / choice candidate metadata and labels #997). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P6b deletes workload_candidates.rs and the whole-workload entries after P6; the helpers the memo rules call stay here, to be rewritten as native memo rules (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).

2. Naming and over-abstraction

• Two files named state_configurations.rs (memo/ and memo/rules/); rollup in both memo/rules/rollup.rs and asap_aware_cse.rs (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).
• One concept, several names: summary-capability rule / CapabilitySharingCandidate / SharedBuild / shared_builds; window-composition rule / Panes / PaneCandidate / SharedPaneChain ([Refactor] Repo-wide naming survey: overloaded and misleading names #948).
• *Pass2Candidate wrappers and Pass2Candidate are rewritten root sets, not memo candidates ([Refactor] Repo-wide naming survey: overloaded and misleading names #948, Remove dead Pass 2 / choice candidate metadata and labels #997). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P6b deletes them.

3. Stale code and stale docs

• planner-layering.md lines 283-287 give the memo's code interface as crates/plan-selection/src/search/memo/ with Memo, CouplingSite, CouplingKind, brute_force::memo, brute_force::brute_force and Stage1ToStage3Search::memo_groups. None exist on main; the memo is in loa/memo*. Line 252 says the memo search is "not yet the default"; it is the only route (run_stage1_to_stage3_from_pass1, plan-selection/src/search/pipeline.rs:195).
• Whole-workload subset enumeration (identical_expression_pass2_candidates, summary_capability_pass2_candidates, topk_reuse_pass2_candidates, caps of 20 such as MAX_CAPABILITY_SHARING_MEMBERS) is reachable only from workload_candidates.rs, query_pruning.rs, devtools and tests. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P6b deletes them once query_pruning.rs is gone (P6).

4. "memo" / "cache"

• window_candidates.rs aliases CandidateMemo as Memo; ExpansionMemo (types/src/ir/operator/pane_chain.rs), CoverageMemo (summary_coverage.rs) and NodeKeys.memo (memo/groups.rs) are lookup caches, not the search memo. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 removes CandidateMemo; [Refactor] Rename memo-named caches and the memo types by stage #1050 renames ExpansionMemo, CoverageMemo and NodeKeys to *Cache names.

5. Rules over memo groups

• Each rule should state: which groups it reads, which group it adds a candidate to, and whether it creates a new group (state group, producer group). Check TopKReuse and SummaryResult, which create groups, against Memo: identical derived producers are duplicated, so a shared finalized result or top-k cannot be stored once #979 and One shared-producer rule: cover every reader's need, derive each reader (top-k, summary size, panes, ranks, …) #954.
• Every candidate a rule adds keeps the independent candidates (doc: "applying a rule adds a shared candidate and keeps the independent candidates").

Correctness and efficiency

• Explain the 336 pane-chain groups and 691 candidates per quantile group for one query; decide which are intended (the memo, not the MILP, should bound this).
• The memo path has no candidate caps (memo/state_configurations.rs, Complete uses every millisecond divisor); only deadlines and pane-width rounds bound it.

Input/output check with the DAG viewer

• Input: the Pass 1 memo. Output: the memo after each rule (groups, new state groups, candidates by origin) and the candidate DAGs (stage_pipeline: write the memo after each step, the selected choice and the enumeration #1003, DAG viewer: draw the memo after each step (groups with their candidates) #1005, DAG viewer: list the enumerated candidate DAGs and draw any of them #1006).
• Check: the shared KLL state group and the reader candidates exist for G2 and G4; per-origin counts match the table above or the difference is explained; rules match the doc's list.

Related issues

Sub-issues: #958, #954, #951, #997, #731, #522, #873, #891, #903, #278, #580, #623, #464, #463.

Referenced: #979 (group identity, under #1011), #929 (size once, under #1015), #1002 / #1003 / #1005 / #1006 (memo tooling, under #1008), #948 (naming).

🤖 Generated with Claude Code