stage_pipeline: price every enumerated candidate DAG and flag any cheaper than the selected plan #1004

Problem, by example

Example workload: 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]))

The memo the production planner builds for it, read from the stage-pipeline document tools/dag-viewer/examples/memo-ratio-of-quantiles.json (main at d728d05c, made by stage_pipeline from tools/dag-viewer/memo-examples/promql/ratio-of-quantiles-5m.json):

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

The two quantile_over_time(0.5, data[5m]) are one group, G2: 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 the PromQL frontend's series-identity column ($promql_series_identity) gives the per-series quantile's output one (series identity, timestamp). A non-ASAP node without a unique key, such as a without(..) grouping, would still be one group per reader.

On a workload this size, nobody can check that the MILP's selected plan is the cheapest of the candidate DAGs the memo stands for. The search report has a lower bound and a gap, but it doesn't price the alternatives. On the Pass 1 memo alone there are 49 candidate DAGs.

Why

The default search (candidate-connection MILP) prices candidates through its own coefficients. Brute force over the memo was removed with the old memo search. The --exhaustive mode archives the assignments it evaluated, not every DAG of the memo.

Proposal

stage_pipeline --price-enumerated <n>:

1. For each of the first n choices from memo::enumerate on the final memo, compose the DAG and run it through Stage 2 and Stage 3, as is done for the selected plan.
2. Write each choice's validation result and cost into memo.enumeration.
3. Set cheaper_than_selected: true on any valid DAG that costs less than the selected plan. The viewer marks such a DAG red.

Off by default. The viewer examples and the CI tests turn it on for small workloads.

Depends on #1002 and #1003.

Scope and acceptance

• A test on planner-layering Example 1 and on the Pass 1 memo of the example above (49 DAGs): enumeration is complete, and no valid DAG is cheaper than the selected plan.
• A test that builds a selection one step worse than the cheapest and checks that cheaper_than_selected catches it.