Stage 1 Pass 1 review: per-computation candidates over memo groups #1012

Part of #1010. Line numbers are on main at 958778400. Abbreviations: loa/ = crates/logical-asap-optimization/src/, pcc.rs = loa/per_computation_candidates.rs.

Example: what Pass 1 produces

Same query as the tracking issue (avg by (job) (quantile_over_time(0.5, data[5m]) / quantile_over_time(0.5, data[5m]) + quantile_over_time(0.9, data[5m])), every minute, max_error 0.01, failure_probability 0.001). In the production planner, read from the stage-pipeline document tools/dag-viewer/examples/memo-ratio-of-quantiles.json (main at d728d05c) (#1002):

Corrected 2026-10-28: production numbers from the stage-pipeline document; earlier numbers came from a test helper without the series-identity column. The whole-workload column is the earlier helper measurement and has not been re-measured in production.

Where the 7 candidates of a quantile group come from (read from the code, not from a run):

• computation_candidates_for_intent (pcc.rs:495) gives Quantile no exact accumulator, so its choices are Exact, Summary(Kll), Summary(DDSketch) (families from summary_candidates, loa/realization.rs:30).
• pass1_candidates (loa/memo/groups.rs:91) counts, for each query, the targets it reaches that offer a summary (here 2: G2, G4), and takes the maximum over the group's queries as max_budget_share (groups.rs:118-151).
• target_candidates emits one candidate per budget share 1..=max_budget_share for every sketch choice (groups.rs:204-215); the exact choice stops at share 1. In production the 7 are: exact; KLL k 345 and DDSketch alpha 0.01 for the whole budget; KLL k 746 and DDSketch alpha 0.004963 for half of it; and KLL k 567 (whole budget) and k 1184 (half) sized for the whole result over the source's 10,000 series (per-value failure_probability 1e-7 and 5e-8).

Open question (#1002): why the memo stands for more DAGs than the whole-workload path composes (production: 49, of which 16 whole-budget; helper: 343 vs 27). One hypothesis from reading the code: the whole-workload path splits the budget by the sketch states actually present in a composed candidate (budget_shares, pcc.rs:1302), while the memo offers every share up to the maximum, so the memo includes over-split variants that the whole-workload path never builds. Not confirmed; #1002 adds the memo-to-candidate-DAG enumeration that can check it.

Functionality

• Find each computation target (an Aggregate whose intent has an exact accumulator or a summary family), including fused computations (whole-expression top-k, nested sum).
• For each target, list its candidates on its own: exact, exact accumulator state, each summary family that can meet its accuracy requirement. Prune only what provably cannot, with a reason.
• Turn the targets' candidates into each memo group's ImplementationCandidates (CandidateMemo).

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

User's suspected problems

• (a) The intent → summary family table is duplicated. Places that encode intent ↔ family / exact state:
  • summary_candidates (loa/realization.rs:30): intent → families, written by hand; its comment says "one home". Theta is excluded by hand.
  • of_per_instance_sketch (types/src/ir/schema/family_capability.rs:150): family → readouts. This is the table the executor reads (executor/src/supported_summaries.rs). summary_candidates could be derived from it ([Refactor] Derive Pass 1's intent → family list (summary_candidates) from the family-capability table #953).
  • statistic (pcc.rs:3875): intent → SketchStatistic, used to check deployment support (pcc.rs:418); the executor maps readout → SketchStatistic again (executor/src/supported_summaries.rs:119).
  • computation_candidates_for_intent (pcc.rs:495) and loa/function_rules.rs:10: the same intent set (Sum, Min, Max, Avg, Rate, IRate, Increase) for exact accumulators and for accuracy composition.
  • sizing_target (realization.rs:72) and intent_metric (types/src/ir/properties/accuracy.rs:319): two intent → accuracy metric tables.
  • keeps_every_value (plan-selection/src/lib.rs:4963): intents whose exact state grows, in Stage 3.
  • agg_is_mergeable, agg_is_exact, agg_accuracy (types/src/ir/operator/agg_intent.rs:670, :682): no non-test caller found; agg_is_exact says Count has no sketch benefit, which summary_candidates contradicts.
• (b) Stages mixed in Pass 1. Only about the first 1,200 lines of pcc.rs (6,154 lines) generate candidates. The rest is whole-workload composition (compose_logical_candidate, pcc.rs:1203), sizing (budget_shares, sized), guarantee propagation including Pass 2 / Stage 2 shapes (PaneChain, rollup, merged panes), and substitution. Stage 3 imports guarantee functions from it (bind_guarantees, with_resized_summaries, root_guarantee, …).
• (b) Stage 3 drives Pass 1. try_populate_pass1 and accuracy_configurations::add_scoped_candidates (a plan-selection module that adds Stage 1 candidates, plan-selection/src/search/candidates/accuracy_configurations.rs:8) run inside Stage 3's search_domain (route.rs). Unsupported summaries are removed by the Stage 3 driver, not by Pass 1 (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 decisions 2–3). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P3: try_populate_pass1, add_scoped_candidates and without_unsupported_summaries move inside Pass 1; Stage 3 reads only Stage 2's output.
• (c) Not general. There is no pattern/template rule as in Algorithm 1.1. Families come from a fixed list; per-intent prunes are inline (nullable avg, relational count, quantile φ, top-k heap over one row per item); fused computations are bespoke passes (add_whole_expression_targets, add_nested_sum_targets); substitution has per-intent builders (ranked_as_topk, nested_sum, sql_avg). Adding an intent or family means editing several tables ([Refactor] Derive Pass 1's intent → family list (summary_candidates) from the family-capability table #953, Design the extension contract for new ASAP primitives and sketch algorithms #548).

1. Boundaries

• Decide whether budget-share variants are Pass 1 candidates or a sizing coupling decided later (memo-milp: size summaries once (final config per reader set and summary count; Stage 3 never resizes) #929 "size summaries once"). Today Pass 1 sizes, against its own module doc (pcc.rs:22).
• DeploymentCapabilities is defined here but read by Stages 1, 2 and 3 (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 decision 3). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047: each stage receives only its part (see the table above).

2. Naming and over-abstraction

• ComputationCandidate vs ImplementationCandidate vs PerComputationCandidates ("inventory" also names a Stage 3 type, [Refactor] Repo-wide naming survey: overloaded and misleading names #948). Decided: HowToComputeAggregateMeasure and CandidateForMemoGroup ([Refactor] Rename memo-named caches and the memo types by stage #1050); PerComputationLogicalMemoCandidates ([Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047).
• computation_candidates_for_intent is pub but used only inside pcc.rs.

3. Stale code

• generate_per_computation_candidates (non-memo, pcc.rs:599): callers found only in devtools (sketch_coverage) and tests. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P3: one entry, generate_per_computation_logical_memo_candidates, replaces both.
• Comments still refer to "legacy realization rules" (pcc.rs:3787).
• try_populate_pass1's doc says it "does not yet generate rules per group" (groups.rs:46-47). [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P3: try_populate_pass1 is folded into Pass 1.

4. "memo" / "cache"

• _with_memo uses the memo only as a cache key; LocalCandidateCache (pcc.rs:618) caches computation_candidates_for_intent, a pure function of the intent; type Memo in pcc.rs is a rewrite cache. [Refactor] Rename memo-named caches and the memo types by stage #1050 renames LocalCandidateCache → MemoGroupMeasureToComputationChoicesCache and type Memo → NodeToRewrittenNodeCache; [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047 P3 removes _with_memo.

5. Rules over memo groups

• Pass 1 still runs on whole query roots and maps targets to groups afterwards (targets_of in groups.rs). Decide whether Pass 1 should run per memo group, so a group shared by two queries is visited once. Decided ([Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047): Pass 1 walks memo groups; P3 implements it, and reviewing P3 settles this item.

Correctness and efficiency

• Resolve Memo: convert memo-group candidates into the vector of all candidate DAGs #1002's memo-vs-whole-workload count (production: 49 memo DAGs, 16 whole-budget) and decide which candidate set is intended.
• Each pruned candidate carries a reason that the viewer can show. [Refactor] One named type per stage boundary: PerComputationLogicalMemoCandidates → LogicalASAPMemoCandidates → PhysicalASAPMemoCandidates #1047: pruned_candidates: Vec<PrunedCandidate<HowToComputeAggregateMeasure>> with a PruneReason shared by all stages.

Input/output check with the DAG viewer

• Input: the Stage 0 memo of the example. Output: each group's Pass 1 candidates (origin, family, budget share), and the candidate DAGs they stand for (DAG viewer: draw the memo after each step (groups with their candidates) #1005, DAG viewer: list the enumerated candidate DAGs and draw any of them #1006).
• Check: the 7 candidates of G2 and G4 are the intended set; the enumeration matches the whole-workload path or the difference is explained (Memo: convert memo-group candidates into the vector of all candidate DAGs #1002).

Related issues

Sub-issues: #953, #735, #727, #703, #681, #664, #639, #750, #751, #743, #739, #711, #689, #798, #807, #788, #944, #459, #410, #422, #444, #443, #350, #172, #297.

Referenced: #1002 (memo → candidate DAGs; parent #1008), #958 (Stage 1 layout, under #1013), #929 (size once, under #1015), #548 and #131 (extension contract).

🤖 Generated with Claude Code