Memo: half of a group's candidates after concrete-state expansion compose to duplicate DAGs #1021

Production check (2026-10-28): not reproducible

Corrected 2026-10-28: production numbers from the stage-pipeline document; earlier numbers came from a test helper without the series-identity column. The measurement below the line was taken on the expanded_memo helper's memo, where the two quantile 0.5 are separate groups and quantile 0.9 is G5. In production it is G4.

Production memo: stage_pipeline on tools/dag-viewer/memo-examples/promql/ratio-of-quantiles-5m.json with the flags of tools/dag-viewer/examples/memo-ratio-of-quantiles.json (main at d728d05c), plus --max-memo-candidates 2000 so that every candidate is listed. After the last step (concrete_states), each candidate's dag (its node and everything below) was compared, with and without the schemas' closed flags:

• None of the helper's duplicate kinds appear. No two Pass1 candidates are equal: there is no closed-flag pair (removing closed changes no count) and no pair with different budget_share.
• Every equal-dag pair is one Pass1 or Panes candidate and one SharedBuild candidate with the same budget_share. The SharedBuild candidate reads a concrete summary-state group instead of G1 or G0. Each of those 343 state groups (336 PaneChain, 7 SummaryAgg) has two readers, G2 and G4. So each pair is the private build and the build shared between the q = 0.5 and q = 0.9 groups. The pair is equal only when one candidate is composed alone.
• The proposed key (recomposed node and children) finds no duplicates in production.

Closing as not reproducible in production. If the shared-build alternatives should be counted differently (for example, one candidate per state group rather than a copy per reader candidate), that is a Pass 2 question for #1013.

Problem, by example

Query, evaluated every minute, 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]))

After Pass 2 window composition and the concrete summary-state groups, group G5 (quantile_over_time(0.9, data[5m])) has 745 implementation candidates but only 367 distinct DAGs. We composed each candidate alone with memo::enumeration::compose (#1009), on the memo the expanded_memo integration-test helper builds. Each distinct DAG comes from 2 to 4 candidates, for example:

So about half of the candidate space the search sees is duplicates. Every duplicate is one more MILP choice, and each repeats in every enumeration of candidate DAGs (the DAG viewer, #1006). The 2 and 368 pair also suggests that budget_share on candidates added after Pass 1 doesn't describe how they are sized.

Why it happens (to confirm)

• Candidates 367–372 and 739–744 come after Pass 1's 13 and the 360 Panes candidates in G5's list. They look like the concrete-state expansion's copies (memo/state_groups.rs) of earlier candidates, with the sizes already applied and budget_share reset to 1.
• The schema difference (closed) is erased when recompose_guarantees rebuilds nodes, so the candidates were already the same plan.
• A SharedBuild candidate whose only reader is the group itself reads like a local build.

Proposal

1. Confirm on the memo production builds (crates/plan-selection/src/search/route.rs; stage_pipeline: write the memo after each step, the selected choice and the enumeration #1003 writes it to the stage-pipeline document), since expanded_memo differs slightly from production (all pane widths, no add_scoped_candidates).
2. Deduplicate candidates per group at insertion, by their recomposed node and children. Keep the earliest origin.
3. Set budget_share on expanded candidates to the share their sizes were computed for, or drop the field once concrete sizes are on the node.

Scope and acceptance

A test on this query: after the last memo step, every pair of G5's candidates composes to a different DAG (compose with {G5: i}), and the selected plan's cost is unchanged.

Related

• Found while reviewing feat(optimizer): enumerate a memo's candidate DAGs and compose each choice #1009 (Memo: convert memo-group candidates into the vector of all candidate DAGs #1002); part of Tracking: DAG viewer shows the memo after each step and every candidate DAG it stands for #1008.
• Stage 1 Pass 2 review: Stage 1 Pass 2 review: ASAP-aware CSE rules over memo groups and summary-state groups #1013.