Repository navigation
DAG viewer: list the enumerated candidate DAGs and draw any of them #1006
Description
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 planner builds for it on main (0f7465c96), measured with LogicalMemo::from_roots, try_populate_pass1 and the expanded_memo test helper:
| Group | Logical sub-expression | Reads |
|---|---|---|
| G0 | Scan data |
– |
| G1 | TimeRange 5m |
G0 |
| G2 | per-series quantile 0.5 |
G1 |
| G3 | per-series quantile 0.5 (structurally equal to G2, but a separate group; see below) |
G1 |
| G4 | G2 / G3 |
G2, G3 |
| G5 | per-series quantile 0.9 |
G1 |
| G6 | G4 + G5 |
G4, G5 |
| G7 | avg by (job) |
G6 |
| After | Groups | Implementation candidates | Full candidate DAGs |
|---|---|---|---|
| Stage 0 | 8 | – | 1 |
| Stage 1, Pass 1 | 8 | 26 (G2, G3 and G5 have 7 each) | 343 = 7 × 7 × 7 |
| Pass 2 window composition + concrete state groups | 378 (360 are PaneChain shared-build groups) |
2614 (G2, G3 and G5 have 745 each: 13 Pass 1, 360 Panes, 372 SharedBuild) |
> 1,000,000 (a naive enumerator stopped there) |
G2 and G3 are separate groups because 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.
The Pass 1 memo alone stands for 343 complete candidate DAGs. The viewer's Stage 3 list shows the selected plan and the rejections Stage 3 recorded under the default search. It can't show the other 342 DAGs, how many there are in all, or how each one differs from the selected plan.
Proposal
An Enumerated DAGs panel in tools/dag-viewer, reading memo.enumeration:
- Header: the count, plus "≥" and the limit when
completeis false. - One row per choice: for each group whose candidate differs from
selected_choice, its candidate and origin; then its cost and validation result, when the DAGs were priced. A row withcheaper_than_selectedis red. - Clicking a row composes nothing in the browser: the document already holds the composed DAG for the first
--max-enumeratedchoices. The existing lanes draw it, the same as a Stage 3 row.
Scope and acceptance
stages.test.mjscovers the validation ofmemo.enumeration.test_viewer.pychecks, on the example above, that the panel says 343 for the Pass 1 tab and that clicking a row redraws the lanes.
Activity
zzylol commentedon Oct 28, 2026
Corrected 2026-10-28: production numbers from the stage-pipeline document; earlier numbers came from a test helper without the series-identity column.
The example in this issue was measured with
asap_integration_tests::fixtures::lower_promql/expanded_memo. That lowering omits the PromQL series-identity column, so the per-series quantile had no unique key and the twoquantile_over_time(0.5, data[5m])stayed two groups (G2, G3). The production frontend adds$promql_series_identity, which gives the per-series output a unique key (series identity, timestamp), so they share one group. Production numbers, fromtools/dag-viewer/examples/memo-ratio-of-quantiles.json(mainatd728d05c):Scan dataTimeRange 5mquantile 0.5(both occurrences)G2 / G2quantile 0.9G3 + G4avg by (job)budget_share1)Panes)PaneChainshared-build groups)Panes, 345SharedBuild)For this issue: the Pass 1 memo stands for 49 candidate DAGs (the selected plan and 48 others), not 343.