Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207

Problem

Query A: quantile_over_time(0.95, latency[1m]) with a rank-error target 0.01. Query B: quantile_over_time(0.99, latency[1m]) / quantile_over_time(0.50, latency[1m]) with a relative-error target 0.05.

In the formulation below, the plan is stated in a few objects:

• State groups. A KLL state group holds candidates with sizes from a predefined list, e.g. k=200 and k=345; a DDSketch state group holds alpha=0.01 and alpha=0.02. Each candidate has a guarantee derived from its parameters, a timing and a lifetime.
• Edges. A reads the KLL state (rank error). B's two operands read the DDSketch state (relative value error): rank error does not bound a ratio's relative error, so KLL edges into B's operands do not exist (metric rule). Accuracy is checked per query at its root (constraint (K)): A's error within 0.01, and B's composed ratio error within 0.05.
• Stage 3 choice. B's two operands may read one DDSketch candidate $u$: $x_u = 1$, two $y_{u,c,i} = 1$, and its cost is paid once.

In the code today, none of these is a value you can point at:

• Size. k lives inside each candidate's operator node, sized for a fixed share of one query's budget (accuracy_budget_parts).
• Timing and lifetime. They are folded into one Materialization enum.
• Edges. There are no edge objects; Stage 2 stores per-input producer sets filtered by timing only.
• Edge variables. Stage 3 has no $y$; an edge is implied by two choices in one execution context.
• Sharing. It comes from extra SharedBuild candidates and per-size state groups that Pass 2 copies into the memo.

This tracking issue makes each notation and variable of the formulation a named type, field or function in the code, stage by stage. Where the code must differ, the formulation says so.

Representation, rules, enumeration (after this refactor)

• (a) Representation: what is stored.
  • A memo of groups. A group $G$ is one logical result, or one state family, over specified input data. Groups are hash-consed, so an identical subexpression of two queries is one group.
  • A candidate of a group is $v = (e_v, p_v)$: one operator over child groups, plus properties. The logical property is $\theta$ (summary parameters from a predefined list, with precomputed $\varepsilon$, $\delta$). The physical property is (timing, lifetime).
  • Sizes and physical properties are properties of a candidate, not part of a group's identity. So a mergeable state with several sizes is one group with several candidates.
  • Explicit producer–consumer edges $(u, c, i)$, each with $\alpha^{\log}$ and $\alpha^{\mathrm{phys}}$.
  • The memo stores the set of possible DAGs compactly: a DAG is one producer choice per (consumer, input), starting from each query's root group.
• (b) Rules: how the stored set is extended.
  • Pass 1 inserts each query's ways to compute (exact, exact accumulator, each summary family with its $\theta$ list) as candidates.
  • Pass 2 rules add candidates to existing groups, or add new groups. A rule never copies a consumer. For example, a new window candidate (tumbling 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, sliding or subtraction [future work] Stage 1: window candidates with properties — tumbling window, sliding window with merge, sliding window with subtraction #1206) is a rule that adds a candidate to the window's state group, and every consumer of that group sees it.
  • Sharing comes from hash-consing alone. There are no SharedBuild candidates or per-size groups.
  • Stage 2 expands each logical candidate into its valid (timing, lifetime) alternatives. The edges are built once, after the last rule.
• (c) Enumeration: how a DAG is drawn from it.
  • DAGs are not listed one by one. The Stage 3 MILP picks $x_v$ (candidate used) and $y_{u,c,i}$ (edge used), with these constraints:
    • every used consumer input picks exactly one producer that satisfies $\alpha^{\log}$ and $\alpha^{\mathrm{phys}}$;
    • a producer is used whenever an edge reads it;
    • each query's root group is covered;
    • acyclic;
    • accuracy per query at its root (K), retention (R), latency (L), resource budgets (B);
    • minimize $\sum w_v x_v$.
  • The chosen DAG is ${v : x_v = 1}$ with edges ${y = 1}$. A producer read by several edges is shared, and its cost is counted once.
  • On small workloads, a reference enumerator (one producer per consumer input) checks the MILP's answer.

Each sub-issue states which of (a), (b), (c) it changes.

Notation → code, and which sub-issue owns it

Sub-issues

Each sub-issue has the same structure: the formulation for its scope, the data structures and interfaces to change per stage, and a table of today's code against what it should become.

• 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 · Window-specific (re-scoped 2026-11-04): tumbling-window builds as candidates of the state group, and merge-then-aggregate over raw tumbling windows. It does not change the memo group representation (that is Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203).
• Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203 · Logical memo candidate as $(e, p^{\log})$ with a requirement $r^{\log}_{c,i}$ per input (Stage 1).
• Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200 · Physical properties: Materialization → (timing, lifetime) enums (no schedule, decided 2026-11-06); $r^{\mathrm{phys}}$, $\alpha^{\mathrm{phys}}$ (Stage 2).
• 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 · Producer–consumer edges: explicit $\mathcal E$ after Pass 2 (logical) and Stage 2 (physical), the domain of $y_{u,c,i}$.
• Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204 · Stage 3 MILP: variables $x, y, z, t$ and constraints (A)–(I) as named code; contexts, consumer constraints and accuracy stated in the formulation.
• 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 · DAG viewer / stage_pipeline: memo groups with properties, every edge with $\alpha$ and its rejection reason, every stage's pruned candidates.
• [future work] Stage 1: window candidates with properties — tumbling window, sliding window with merge, sliding window with subtraction #1206 · [future work] Stage 1 window candidates with properties: tumbling, sliding with merge, sliding with subtraction.

Policy: refactors delete what they replace (decided 2026-11-04)

Interfaces (decided 2026-11-05). The data structures and interfaces of each stage are the ones defined in this issue, its sub-issues, and the concepts doc memo-groups-properties-requirements.md, section 3 (#1224). Each PR:

• implements those interfaces and deletes the old interfaces and abstractions they replace;
• lists, under New abstractions not in Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207 or the doc, every type, trait, field or public function it adds that they do not define, and gets the user's approval before keeping it.

These PRs are refactors toward the formulation. Each one:

• deletes the old implementation it replaces in the same PR: no old code path kept beside the new one, no feature flag or environment switch to fall back, no compatibility shim, wrapper or alias of an old type or name;

• leaves no dead code: every type, field, function, variant and test helper the PR makes unused is deleted, and the PR body lists them;

• does not reuse an old or stale abstraction for a new concept. For example:

  • lifetime is a new Lifetime, not Materialization renamed;
  • an edge is a PhysicalEdge, not ProducerCandidates re-documented;
  • a context is not a ResultSlot.

• models every property and requirement as a product of dimensions (decided 2026-11-05): one field per dimension, each its own type, with a checked constructor that rejects the invalid combinations. Never a flat enum that lists the combinations.

  • $p^{\mathrm{phys}}$ = PhysicalProperties { timing, lifetime };
  • $p^{\log}$ = LogicalProperties { parameters, window_layout };
  • $r^{\log}$ is LogicalRequirements { parameter_floor_for_required_accuracy }; $r^{\mathrm{phys}}$ is a function of the consumer's own $p^{\mathrm{phys}}$, not a stored struct.

  A dimension may carry data that only some of its values need, e.g. Lifetime::OneEvaluation(StorageMedium).

• changes producers and consumers of a changed format together: export and backend, viewer documents, snapshots. No code that parses the old format is kept.

• Terminology (decided 2026-11-05). Consumer c is the candidate reading an input; query q (or its execution context κ) is who needs a result on a schedule 𝒯_q. Issues, the doc and new code do not use "reader".

Order (rewritten 2026-11-06: interfaces first, baseline before extensions)

Source of truth for every interface: the concepts doc docs/design_docs/concepts/memo-groups-properties-requirements.md (#1224). PR 0 defines every data structure and interface of the doc and deletes the old ones they replace; each later PR fills in one part. No PR adds a temporary abstraction. Tests may fail until the PR that makes them pass; each PR says which.

• Crates (decided 2026-11-06). PR 0b makes each stage and pass its own crate before any stage logic is filled in, so PRs 2–8 land in their final crates. Crate names decided 2026-11-06.
• One merge unit. PRs 0–9 (with 0b) merge into main together, after PR 9; each is stacked on the previous one for review.
• Replaced work. The earlier stacks (refactor(types, stages): replace Materialization with PhysicalProperties (timing, lifetime) #1214, refactor(types, stages): physical properties off the logical IR (OperatorNode has no timing or lifetime) #1223, refactor(types, stages): every valid timing × lifetime state explicit; PhysicalRequirement, satisfies_physical, no named states #1216, feat(types): an unmaterialized summary build runs at its consumer's timing; one α^phys error at export #1219 and the Part 2 branch; refactor(stage1): Pass 1 adds a memo group for every intermediate result (#1203 PR 2a-1) #1215, refactor(stage1): summary readouts and inputs as one operator over groups; Memo::add_candidate; one node equality in Pass 1 (#1203 2a-2) #1218, refactor(stage1): top-k reuse and finer-aggregate reads as one operator over groups (#1203 2a-3) #1220, refactor(stage1): rollups as one operator over groups (#1203 2a-4) #1221, refactor(stage1): scan widening as one operator over groups; one exact-guarantee strip (#1203 2a-5) #1222, refactor(plan-selection): row (K) terms per path of edges, interim until step 6 (#1203 2a) #1225 and the 2a-6 and squash branches) are closed once PR 0 is open; their code is reused in PRs 1–8.
• Not in this unit: constraint (J) is deleted (2026-11-06); latency (L) and resource budgets need their own design; [future work] Stage 1: window candidates with properties — tumbling window, sliding window with merge, sliding window with subtraction #1206 (sliding and subtractive windows); 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 (viewer).
• Abstractions not in this issue or the doc are listed in the PR that adds them as pending the user's approval.
• Plan checks. Plans may change between PRs 6 and 8 as contexts and (K) arrive; PR 9 lists every change. Plans are checked by hand with asap-planner --output text.
• From PR 6 on, each PR reports MILP size and solve time per snapshot (Planning is about 20x slower since the full tumbling-window-width domain (#1185) #1197), and checks that the reference enumeration (doc, Appendix A) and the MILP agree on small workloads.

Acceptance

• Every notation has a home. Every row of the notation table names a type, field or function in the code.
• Stage handoff. Each stage's boundary type carries the notation that stage defines.
• Plans unchanged. Every corpus and sketch-plan snapshot selects a plan of the same cost, or the PR that changes it lists each difference.
• Nothing old left. After the last step, none of the "Deletes" column exists in the code, and no PR added a fallback, flag or alias.

Related

• Stage 3 MILP vs the memo formulation: one choice costs several binaries, sizes and targets are groups, and the group graph is cyclic #1199: feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144 MILP vs this formulation (duplication and misalignment).
• [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 / feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144: execution contexts and the merged MILP.
• 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: tumbling-window builds in the state group, sub-window order (b). docs(planner-layering): state groups from Pass 1, size as a candidate property, two window orders #1183 (its design doc) was closed 2026-11-04; each PR updates planner-layering.md for its own part.
• feat(devtools): stage_pipeline --text prints every planner stage's output as text #1159: stage_pipeline --text.