Memo: convert memo-group candidates into the vector of all candidate DAGs #1002

Problem, by example

One query, evaluated every minute, with max_error 0.01, 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]))

The planner keeps this workload's candidates as a memo: groups of logical sub-expressions, each with its implementation candidates (CandidateMemo). We measured it on main (0f7465c96) with a throwaway test that calls LogicalMemo::from_roots, try_populate_pass1 and the expanded_memo test helper:

In Pass 1, the three quantile groups have 7 candidates each, and the other five groups have one each.

Nothing in the planner can turn the memo back into the representation used before the memo: the vector of every candidate DAG, one complete DAG per query set. So today:

• the DAG viewer can't list the candidate DAGs the memo stands for, or draw any of them except the selected plan;
• no test can check that the memo stands for the same candidate set the whole-workload path enumerated (for Pass 1 here, the same 343 DAGs);
• for a small workload, nobody can price every candidate DAG and check that the MILP's selected plan is the cheapest.

What should exist:

let dags: Vec<Vec<QueryRoot>> = memo::enumerate(&memo, limit)   // every choice: one candidate per needed group
    .choices
    .iter()
    .map(|choice| memo::compose(&memo, choice))                  // one complete DAG per choice
    .collect::<Result<_, _>>()?;
assert_eq!(dags.len(), 343);                                     // Pass 1 memo of the example

Why it isn't done today

• Composition exists only in two non-reusable places.
  • compose_memo_plan in crates/integration-tests/src/lib.rs is a test helper. It composes one choice (a group → candidate index map) by replacing each candidate's child-group nodes with their composed children, so each child group is built once and shared.
  • reconstruct_selected_candidates in crates/plan-selection/src/search/candidates/reconstruction.rs decodes the MILP's selection. It is pub(in crate::search) and works on the solver's candidate connections, not on a CandidateMemo choice.
• Nothing enumerates choices. The count is not a product over groups: a group several candidates read must take one candidate per plan, a fused candidate implements several groups at once, and which groups are needed depends on the candidates chosen above them.
• The whole-workload path did enumerate. That is stage1_candidates_of_choice in crates/logical-asap-optimization/src/workload_candidates.rs, which is being deleted under 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. Once it is gone, nothing produces the "before" representation.

Proposal

The interfaces go in crates/logical-asap-optimization/src/memo/, next to CandidateMemo.

• memo::compose(memo: &CandidateMemo, choice: &MemoChoice) -> Result<Vec<QueryRoot>, ComposeError>. It builds one complete DAG for every query from one choice. It is the production version of compose_memo_plan: the test helper is deleted and its callers call this instead. Plan reconstruction should share it or be checked equal to it.
• MemoChoice. It maps each needed group to one candidate index. A fused candidate sets every group it implements.
• memo::enumerate(memo: &CandidateMemo, limit: usize) -> MemoEnumeration { choices: Vec<MemoChoice>, complete: bool }.
  • It walks from the query roots and picks one candidate per needed group. A group's choice is shared by every candidate that reads it.
  • It skips choices that are inconsistent with an earlier fused candidate.
  • It stops at limit, with complete: false.
  • Choices that compose to structurally equal DAGs are counted once.
• Validity stays where it is. enumerate produces every composable choice. Accuracy at the query roots, Stage 2 legality and Stage 3 cost stay with the existing validator and stages, as with the whole-workload candidates.

Open choice: should the enumeration also report an exact count past limit? A count needs its own walk (no DAGs built); an upper bound is the product of each group's candidate count. Proposed: report complete and the product as an upper bound in v1, and add an exact count only if the viewer needs it.

Scope and acceptance

In scope: compose, enumerate, MemoChoice, deleting compose_memo_plan, and a "memo to candidate DAGs" algorithm section in docs/design_docs/proposals/planner-layering.md.

Out of scope: drawing the memo and the enumerated DAGs in the DAG viewer (the viewer PR that uses this), and enumerating whole evaluation workloads (the limit binds there).

Acceptance tests:

1. Example above, Pass 1 memo. enumerate returns 343 choices with complete: true. Their composed DAGs equal, as a set, the candidates stage1_candidates_of_choice builds for the same workload, on main before 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 deletes it.
2. planner-layering Examples 1–4. Same set equality at Pass 1. After Pass 2, every composed DAG passes the existing plan validator or is rejected with a reason.
3. Selected plan. Composing the MILP's selected choice gives the selected plan's logical DAG.
4. Small-workload optimality cross-check (devtools, optional). Price every enumerated DAG with Stage 2 and Stage 3. No valid one is cheaper than the MILP's selected plan.

Status and related work

• Planned 2026-10-28 together with the DAG viewer change that draws the memo per stage and lists the enumerated candidate DAGs.
• Related:
  • 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 deletes the whole-workload path, so test 1 must land before that deletion or pin its expected set.
  • Memo search solver: MILP over the memo for all cost models #888 is the MILP over the memo; test 4 cross-checks it.
  • docs(planner-layering): stage inputs and outputs, whole-workload candidates and memo #977 documents each stage's inputs and outputs with and without the memo.
  • test: snapshot planner output over real-world queries in CI #956 adds stage-pipeline snapshots in CI.
• Observed while measuring, to be filed separately: Stage 0 keeps the two quantile_over_time(0.5, data[5m]) as two groups (G2 and G3, structurally equal). share_common_sub_dags (crates/types/src/ir/cse.rs) shares a non-ASAP node only when its schema has a provable unique key, and this per-series quantile's output schema has none.