Producer–consumer edges (u, c, i): make the edge set explicit after Pass 2 and Stage 2, with α^log and α^phys, as the domain of y_{u,c,i} #1201

Example

Query A: quantile_over_time(0.95, latency[1m]), rank error 0.01. Query B: quantile_over_time(0.99, latency[1m]) / quantile_over_time(0.50, latency[1m]), relative error 0.01. A reads the KLL quantile state over latency[1m]. B's two operands read a DDSketch quantile state over the same input: KLL bounds rank error, which does not bound the relative error of a ratio (metric rule, concepts doc Section 4).

• The KLL state group's candidates take $\theta$ (k) from the predefined list, and the DDSketch state group's candidates take alpha (Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203). Accuracy is checked per query at its root (constraint (K), Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204), not per edge. A meets its target at k=200 or k=345; B needs a DDSketch alpha small enough for both operands.
• The DDSketch state group has, among others, a query-time candidate SummaryAgg(DDSketch alpha=a) with lifetime OneEvaluation(Memory).
• In the formulation, each of B's two operand inputs has an edge $(u, c, i)$ to that producer, with $\alpha^{\log} = \alpha^{\mathrm{phys}} = 1$. A KLL candidate has an edge to each operand input too, but with $\alpha^{\log} = 0$ (metric rule). If Stage 3 sets both $y_{u,c,i} = 1$ for the DDSketch candidate, B's two operands share one build.
• In code today, no edge exists as a value. Stage 2 stores, per input, an interned set of producer candidates filtered by timing only. Stage 3 has no $y$ variable: an edge is implied when the consumer and the producer are both chosen in one execution context.

This issue makes the producer–consumer edges explicit in the code: after Pass 2, at the logical level; after Stage 2, at the physical level, as the domain of $y_{u,c,i}$.

Representation, rules, enumeration

• (a) Representation. Edges are stored as values:
  • LogicalEdge after Pass 2 and PhysicalEdge after Stage 2, each $(u, c, i)$ with $\alpha^{\log}$ and $\alpha^{\mathrm{phys}}$;
  • a rejected edge keeps its reason;
  • today there are only per-input producer sets, filtered by timing.
• (b) Rules. No change. Rules stay group-level and never write edges. The edges are built once, after the last rule, and Stage 2 expands them.
• (c) Enumeration. The admissible edges are the domain of $y_{u,c,i}$. A DAG is the set of edges with $y = 1$: exactly one per used (consumer, input).

Formulation

• Producer group and requirement. Input $i \in \mathcal I(c)$ of consumer $c$ reads group $G_{c,i}$ and states $r_{c,i} = (r^{\log}{c,i}, r^{\mathrm{phys}}{c,i})$.
• Candidate edges. With $P_{c,i} = G_{c,i} \cap \mathcal C$, the physical candidates in the required group before checking requirements:
  $$\mathcal E = {(u, c, i) \mid c \in \mathcal C,\ i \in \mathcal I(c),\ u \in P_{c,i}}.$$
• Satisfaction indicators. $\alpha^{\log}{u,c,i}$ is 1 iff $p^{\log}u \succeq r^{\log}{c,i}$ (Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203); it is 0 when the producer's error metric cannot be converted to the metric the consumer needs (metric rule). $\alpha^{\mathrm{phys}}{u,c,i}$ is 1 iff producer_satisfies_physical_requirements$(\text{memo}, u, c)$ holds (Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200): timing and lifetime, and that a materialized producer delivers on the consumer's schedule.
• Choice. $y_{u,c,i} \in {0,1}$: producer $u$ supplies input $i$ of $c$, with:
  • (A) $\sum_{u \in P_{c,i}} y_{u,c,i} = x_c$;
  • (B) $y_{u,c,i} \le x_u$;
  • (G) $y \le \alpha^{\log}$;
  • (H) $y \le \alpha^{\mathrm{phys}}$.
• Sharing. Several $(c, i)$ may set $y_{u,c,i} = 1$ for the same $u$. $u$ is one candidate, and its cost $w_u x_u$ is counted once. Sharing is the set ${(c, i) : y_{u,c,i} = 1}$, never a separate candidate.

The physical compatibility $\alpha^{\mathrm{phys}}$, from #1200:

A materialized producer must also deliver on the consumer's schedule (PhysicalCandidate::delivers_on, #1200). Reusing an earlier evaluation's work is the producer's lifetime, not a requirement, so there is no "later evaluation" row.

Data structures and interfaces per stage

Stage 1, Pass 2's output (crates/types/src/stages/logical_memo_candidates.rs). Pass 2's rules stay group-level: a rule adds a candidate to a group, and every consumer of the group sees it. After the last rule, Pass 2 builds the logical edge set once:

/// (u, c, i) over logical candidates: u ∈ G_{c,i}, with α^log.
pub struct LogicalEdge {
    pub producer_candidate_id: CandidateForMemoGroupId,
    pub consumer_candidate_id: CandidateForMemoGroupId,
    pub input_index_of_consumer: usize,
    pub satisfies_logical_requirement: bool,     // α^log
}

pub struct LogicalASAPMemoCandidates {
    pub memo: Memo,
    /// Every (u, c, i) with u ∈ G_{c,i}, grouped by (c, i).
    pub edges: Vec<LogicalEdge>,
}

Stage 2 (crates/types/src/stages/physical). Each logical edge becomes the physical edges between those candidates' physical candidates. After #1203 there are no private nodes: every input of every candidate reads a group through ordinary edges.

pub struct PhysicalEdgeId(pub usize);

/// (u, c, i) over physical candidates, with both indicators.
pub struct PhysicalEdge {
    pub producer_candidate_id: PhysicalCandidateId,
    pub consumer_candidate_id: PhysicalCandidateId,
    pub input_index_of_consumer: usize,
    pub satisfies_logical_requirement: bool,     // α^log
    pub satisfies_physical_requirement: bool,    // α^phys
}

impl PhysicalASAPMemoCandidates {
    /// ℰ: every edge, in (consumer, input) order.
    pub fn edges(&self) -> impl Iterator<Item = (PhysicalEdgeId, PhysicalEdge)>;
    /// The admissible edges into input `input_index_of_consumer` of `consumer` (α^log = α^phys = 1).
    pub fn admissible_edges_into(&self, consumer: PhysicalCandidateId, input_index_of_consumer: usize) -> &[PhysicalEdgeId];
    /// The admissible edges out of `producer`: everyone who may share it.
    pub fn admissible_edges_out_of(&self, producer: PhysicalCandidateId) -> &[PhysicalEdgeId];
}

• Storage. Today's interned ProducerCandidates sets exist to save memory (ProducerStorageMetrics).
  • The edge list can keep them: an edge id is an offset per $(c, i)$ plus a position in the interned set, so edges() is a view, not a copy.
  • Only rejected edges ($\alpha = 0$), which exist for printing (DAG viewer / stage_pipeline: print memo candidates with properties, every producer–consumer edge with its feasibility and rejection reason, and every stage’s pruned candidates #1205), need their own storage.
• Requirements. producer_candidates_per_input becomes the admissible part of the per-input edges. Filtering adds $\alpha^{\log}$ (non-accuracy requirements, Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203) to today's timing filter; sizes are not filtered per edge.

Stage 3 (crates/plan-selection): reads the edges as the domain of $y$ (#1204).

Realizer / DagOfSelectedCandidates: no change. SelectedEdge { producer, consumer, input_index_of_consumer } is already one selected $(u, c, i)$ per run.

Current vs proposed

Scope and acceptance

In scope:

• LogicalEdge and the edge set built at the end of Pass 2;
• PhysicalEdge, edges(), admissible_edges_into, admissible_edges_out_of;
• moving producer_candidates_per_input's users onto them.

Out of scope:

• the MILP's variables (Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204);
• the representation of $\theta$ and $r^{\log}$ (Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203);
• the (timing, lifetime) types (Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200).

Acceptance:

• Deletes what it replaces in the same PR, with no dead code, fallback, flag, shim or reuse of an old abstraction; the PR body lists what it deleted (Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207, Policy).
• Order: see Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207, "Order (rewritten 2026-11-06: interfaces first, baseline before extensions)". This issue's parts are PRs 0, 4 and 5.
• For the example, stage_pipeline --text lists the edges into each Finalize input:
  • every KLL size is admissible on A's input ($\alpha^{\log} = 1$: accuracy is constraint (K)'s), and is rejected on B's two operand inputs ($\alpha^{\log} = 0$: rank error does not bound a relative ratio error); every DDSketch alpha is admissible on B's two operand inputs;
  • an ingestion-time producer appears on the query-time inputs as admissible only with lifetime AcrossEvaluations, and otherwise as rejected by $\alpha^{\mathrm{phys}}$.
• Every admissible edge's producer is in today's producer_candidates_per_input, and vice versa, until $\alpha^{\log}$ (non-accuracy requirements, Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203) lands.
• Memory: ProducerStorageMetrics on corpus_snapshots grows by at most the rejected edges.

Related

• Tracking: Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207.
• Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200: timing × lifetime.
• Stage 3 MILP vs the memo formulation: one choice costs several binaries, sizes and targets are groups, and the group graph is cyclic #1199: how the feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144 MILP encodes these edges today.
• Pass 2: tumbling-window builds as candidates of the state group, and merge-then-aggregate over raw tumbling windows (window-specific; memo representation is #1203) #1160 / docs(planner-layering): state groups from Pass 1, size as a candidate property, two window orders #1183: size as a candidate property, the requirement per input.
• [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095: execution contexts.