Stage 0 review: frontends and the logical memo (hash-consed groups) #1011

Part of #1010. Line numbers are on main at 958778400.

Example: what Stage 0 produces

One 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]))

In the production planner, read from the stage-pipeline document tools/dag-viewer/examples/memo-ratio-of-quantiles.json (main at d728d05c) (see #1008): the PromQL frontend lowers it to one logical root, and LogicalMemo::from_roots hash-conses it into 7 memo groups:

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 an ASAP node, or a non-ASAP node for which NonASAPOp::is_shareable_when_equal() holds: every execution over the same input rows returns the same output rows (#1032). A unique key is no longer required, so a without(..) grouping is one group too, and the lower_promql test helper (no series-identity column) now also gives 7 groups. Only order-dependent row picks stay one group per reader: a Limit/offset not over a Sort with the same partitions, a Dedup on some but not all columns, and position-reading window functions without ORDER BY. #979 describes a related gap for derived producers (a finalized result, a top-k).

Functionality

• Parse each query in its language (PromQL, SQL dialects, MetricsQL), resolve names and types, and lower it to the common logical IR without any ASAP choice. Reject what cannot be represented faithfully.
• Keep source-language semantics: series identity, evaluation timing, missing data.
• Build the logical memo: hash-cons the workload's roots so that each distinct logical sub-expression is one memo group with its parents and the queries that reach it.

Concepts (design doc term ↔ code)

Interfaces: designed vs implemented

Interface decided in #1047 (2026-10-29)

Decided in #1047, the stage-boundary types. Its sub-issue is #1048. Names follow #1050 within #1047's scope. Principles: a stage or pass reads only the previous step's output type and calls no other stage; the asap-planner facade runs the stages in order; each stage prunes only what its own knowledge rules out and records it as PrunedCandidate<C> { group, candidate, reason: PruneReason }; queries are entry indices. Planning stays as fast as on main: P6 and P7 report before/after stage_pipeline runs.

Review checklist

1. Boundaries: what is in Stage 0 but belongs elsewhere

• Group identity (CSE legality) lives in asap-types (cse.rs:218-245), with a hard-coded intent list for global aggregates. Decide whether it belongs to the memo (Stage 1 crate) and whether the list should come from the IR's key properties. Done in fix(cse): share equal nodes that return the same rows for the same input, not only keyed ones #1032: stays in asap-types as a property of the IR operator; the list is replaced by NonASAPOp::is_shareable_when_equal().
• The frontends put the AccuracyTarget inside the intents, and the PromQL histogram catalog decides which quantiles are "sketchable" (frontend-promql/src/histogram.rs). Check that Stage 0 makes no ASAP choice beyond carrying the requirement, also check the histogram_quantile is not sketchable is not a special field/label in the requirement. Also review how the requirement is expressed.
• canonicalize (types/src/ir/canonicalize.rs) is a logical rewrite run inside the frontends. Decide whether it is Stage 0 or a Stage 1 rule.

2. Naming and over-abstraction

• The frontend entry points do not share a shape: PromQL has four (lower_promql_workload, lower_promql_query_workload and their _with_histograms variants; the doc names the one the facade does not call), MetricsQL takes a workload, SQL takes one query and is async. The doc's table says each returns "a QueryRoot per query".
• "lowering" means frontend → IR here and logical → physical elsewhere ([Refactor] Repo-wide naming survey: overloaded and misleading names #948).
• QueryExpr represents filters in three ways (QueryExpr represents filters three different ways (Scan.predicates, Filter.pred, Aggregate.having) #195, Enforce Filter -> Aggregate.having pushdown as a canonicalization invariant #204, SQL front end never populates Aggregate.having from a real HAVING clause #201).

3. Stale code and stale docs

• (Fixed in fix(cse): share equal nodes that return the same rows for the same input, not only keyed ones #1032: planner-layering.md now states the is_shareable_when_equal rule.) planner-layering.md line 261 said "a node without a unique key (e.g. a range window) is one group per reader". On main a TimeRange over a Scan is shared (cse.rs legality), as G1 in the example shows; the per-series aggregate is shared too (series-identity unique key), and a node without a unique key, such as a without(..) grouping, is not.

4. "memo" / "cache"

• cse.rs keeps hash_cache and eq_memo, canonicalize.rs has a type Memo rewrite cache, TimingMemo is in types/src/ir/properties/timing.rs:196. None of these is the search memo. Rename the caches so "memo" means the memo of groups only ([Refactor] Repo-wide naming survey: overloaded and misleading names #948). [Refactor] Rename memo-named caches and the memo types by stage #1050 renames these caches (NodeToStructuralHashCache, NodePairToIsSameNodeCache, NodeToCanonicalNodeCache, NodeToTimedNodeCache).

5. Rules over memo groups

• Group identity = same logical result. Decide whether two equal sub-expressions without a provable unique key (for example two equal without(..) groupings) should be one group with several parents, since each reader reads the same rows (Memo: identical derived producers are duplicated, so a shared finalized result or top-k cannot be stored once #979). Done in fix(cse): share equal nodes that return the same rows for the same input, not only keyed ones #1032: yes, one group; an unordered LIMIT stays unshared. Follow-up: the accuracy budget is split per group, not per read (Accuracy budget is split by memo groups, not by reads: a quantile or count read twice gets only whole-budget sketches #1040).
• Check that every root keeps its position (roots_of) after hash-consing, so the output stays aligned with QueryWorkload::entries(). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047: roots_of is replaced by DagOfLogicalMemoGroups.query_roots: Vec<QueryRoot<MemoGroupId>> in entry order; check that instead.

Correctness and efficiency

• Each frontend's output for the example matches the source language's semantics (series identity, [5m] window, evaluation time).
• from_roots is linear in the number of nodes (structural hash + equality confirmation).

Input/output check with the DAG viewer

• Input: the example query (and the paper workloads). Output to inspect: the logical DAG per query, and the memo groups after hash-consing (DAG viewer: draw the memo after each step (groups with their candidates) #1005 draws the memo after each step).
• Check: every equal sub-expression is one group, or the reason it is not is shown; group count and parents match the table above.

Related issues

Sub-issues: #979, #195, #204, #201, #468, #130, #127, #784, #748, #981, #914, #796, #661, #658, #657, #655, #653, #652, #650, #670, #517, #415, #409, #405, #306, #305, #289, #280, #245, #125, #120, #108, #388.

Referenced: #1008 (DAG viewer memo tracking), #1005 (draw the memo), #948 (naming survey), #534 (MetricsQL in the facade, see #1017).

🤖 Generated with Claude Code