Tracking: stage-by-stage review of ASAPPlanner — functionality, concepts, abstractions, interfaces #1010

Problem, by example

One query, evaluated every minute, with max_error 0.01 and failure_probability 0.001:

avg by (job) (quantile_over_time(0.5, data[5m]) / quantile_over_time(0.5, data[5m]) + quantile_over_time(0.9, data[5m]))

What each stage produces for it in the production planner, read from the stage-pipeline document tools/dag-viewer/examples/memo-ratio-of-quantiles.json (main at d728d05c) (#1002, #1008):

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

Even for this one query, we cannot yet say whether each number is intended: why the memo stands for 49 Pass 1 DAGs, 33 of them with a summary sized for half the budget; why one query gets 336 pane-chain groups; whether the selected plan is the cheapest. Several stages also do work that the design doc assigns to another stage (Stage 3 runs Pass 1 and Pass 2, Pass 2 exists twice). This issue tracks a stage-by-stage review of ASAPPlanner on main: for each stage, its functionality, concepts, abstractions and interfaces as designed in docs/design_docs/proposals/planner-layering.md and as implemented, with a checklist of what to fix.

Ideal concepts

• One IR for every stage. Every stage reads and writes the same DAG IR (OperatorNode, QueryRoot), with non-ASAP operators (the logical query) and ASAP operators (summary build, merge, estimate, PaneChain). A stage adds choices; it does not convert to a stage-private representation.
• Every stage's output is defined over memo groups.
  • Before the memo: each stage output a Vec of whole-workload candidate DAGs (CandidateLogicalDAGs, CandidateLogicalASAPDAGs, CandidatePhysicalASAPDAGs).
  • With the memo: each stage outputs a memo (groups, each with its implementation candidates), which can be converted to that enumeration of candidate DAGs (Memo: convert memo-group candidates into the vector of all candidate DAGs #1002). Stage 3 receives a complete memo and only selects.
• One named type per stage boundary (decided in [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047, 2026-10-29). DagOfLogicalMemoGroups → (Pass 1) PerComputationLogicalMemoCandidates → (Pass 2) LogicalASAPMemoCandidates → (Stage 2) PhysicalASAPMemoCandidates → (Stage 3) Selection.
  • A stage or pass reads only the previous step's output type and calls no other stage.
  • The asap-planner facade runs the stages, including 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).
  • Each stage prunes only what its own knowledge rules out, as PrunedCandidate<C>.
  • Each stage issue below has an "Interface decided in [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047" section. Names follow [Refactor] Rename memo-named caches and the memo types by stage #1050.
• Memo group. One distinct logical sub-expression (same output result). For ASAP sharing, a group may also stand for one summary state (same summary state), e.g. one shared KLL state group with a candidate in each reader group that reads it. The definition is reviewed in Stage 1 Pass 2 review: ASAP-aware CSE rules over memo groups and summary-state groups #1013.

Milestones

Each milestone is reviewed for three goals: abstractions (one concept, one name, in the right stage), correctness (the right candidates, the right plan), efficiency (planning time and memory).

Review checklist applied to every stage

1. Functionality implemented in a stage that does not belong to it (boundary and concept placement).
2. Naming and over-abstraction.
3. Stale code, including code from before the memo groups and the Stage 0–3 design.
4. "memo" / "cache" used for things that are not the memo; dynamic-programming code or comments that are stale.
5. Functionality as rules over memo groups.

Debugging process

1. Go stage by stage, in the order below, then the end-to-end asap-planner crate.
2. For each stage: check boundaries and concepts, stale code, over-abstraction and naming; then correctness and efficiency by checking the stage's (or crate's) input and output.
3. End to end, per stage: run the DAG viewer (tools/dag-viewer, fed by stage_pipeline) on different workloads (the example above, the paper workloads), look at each stage's memo and candidate DAGs, and file one issue per problem with its example.

Tooling: #1008 tracks the DAG viewer showing the memo after each step and every candidate DAG it stands for (#1002–#1007).

Stage issues (in review order)

1. Stage 0 review: frontends and the logical memo (hash-consed groups) #1011
2. Stage 1 Pass 1 review: per-computation candidates over memo groups #1012
3. Stage 1 Pass 2 review: ASAP-aware CSE rules over memo groups and summary-state groups #1013
4. Stage 2 review: physical optimization and materialization per candidate #1014
5. Stage 3 review: plan selection, the MILP over the memo, cost and accuracy constraints #1015
6. Deployment interface review: InstallablePlan, materialized views, DataStore and the executor #1016
7. asap-planner facade review: orchestration and deployment input assembly #1017

Cross-cutting: #1008 (DAG viewer memo tooling), #948 (repo-wide naming survey), #1047 (one named type per stage boundary; sub-issue #1048, pane-width rounds), #1054 (crate organization by stage: asap-accuracy, asap-cost, enforced crate boundaries, visibility), #1050 (memo/cache and memo-type renames), #1046 (dead and test-only code).

Related

#958 (reorganize by stage; decisions of 2026-10-27), #954 (one shared-producer rule), #879 (plan whole workloads within minutes), #685 (end-to-end use cases), #671 (planning roadmap), #546 / #547 / #531 (documenting strategies and extensions), #545 / #548 / #131 (extension contract), #550 (query/readout terms).

🤖 Generated with Claude Code