Stage 3 MILP vs the memo formulation: one choice costs several binaries, sizes and targets are groups, and the group graph is cyclic #1199

Example

One query: rate(m[1m]), exact, evaluated every 10 s. m has 100 series sampled every second, and raw data is retained. This is the through_stages fixture in crates/plan-selection/src/milp/model/tests.rs. The numbers below come from a throwaway test on main 1b8289a2 that prints SelectionMilp::size(); the test was not committed.

In A the query has 26 real choices: build the rate state with one SummaryAgg over the window, or merge a tumbling-window chain at one of 25 widths. The MILP spends 54 p binaries and 26 e binaries on these choices:

• each width's SummaryMerge and the SummaryTumblingWindowChain below it are separate private operator nodes, so they are separate result slots with one p each;
• the chain has one producer and one reader, so its p always equals its merge's p.

Under the formulation below the same query has one candidate per choice and one edge per (consumer input, producer): 26 state candidates and 26 edges from the FinalizeExactAccumulator.

In B and C some operator nodes are identical (same operator and same input subtree, compared by Debug):

• B: 100 of the 125 private SummaryMerge nodes are 50 identical pairs, each pair in one memo group. Only 132 of the 232 nodes are distinct.
• C: 214 of the 506 nodes are distinct. Each query's group repeats 55 Project ← SummaryEstimate roots twice.

Stage 3 dominance pruning removes no candidate in any of the four cases.

The same quantile at two accuracy targets is two memo groups, G2 and G3. Its two KLL sizes are two more groups: G4 (k = 412) and G30 (k = 80).

1. Formulation and modeling

This is the model the Stage 3 MILP should mirror.

Memo group. A group is one logical result: schema, data selection, window and step. It does not depend on parameter configuration, timing or materialization. Equal expressions are one group: Stage 0 hash-conses them, and every group a Pass 2 rule adds is hash-consed too.

Candidate. As in Cascades, a candidate is $v = (e, p)$:

• $e = \mathrm{op}(G_1, \dots, G_n)$ is one operator over input groups;
• $p$ is the candidate's properties: the parameter configuration (Pass 1), plus timing and materialization (Stage 2).

Each input $i$ of $c$ states a required property $r_{c,i}$. Any $u \in G_{c,i}$ with $p(u) \succeq r_{c,i}$ may supply it.

Per stage.

• Stage 1, Pass 1. A group per result and per state family. A state's configuration, for example KLL $k = 200$, is a property of a candidate in the state group, not part of the group.

• Stage 1, Pass 2. A sharing rule adds only three kinds of things:

  • a producer group, such as a ranking, a widened scan or a shared tumbling-window chain;
  • a derivation candidate in each consumer's group that reads it;
  • property candidates in an existing group.

  Pass 2 records dependencies between groups only.

• Stage 2. Adds timing and materialization to each candidate. It derives the candidate-to-candidate edges $\mathcal E = {(u,c,i) : u \in P_{c,i}}$, where $P_{c,i}$ is the candidates of $G_{c,i}$ that meet $r_{c,i}$ and are compatible in timing and materialization.

• Stage 3. Chooses among those edges. Which consumers share a producer is the set of selected edges into it, not a memo object.

No redundancy.

1. No two groups compute the same logical result.
2. No two candidates of a group have the same $(e, p)$.
3. No candidate repeats another group's operators. A subtree that several candidates contain is a group they read.

MILP.

• Variables:
  • $x_v$: candidate $v$ is selected;
  • $y_{u,c,i}$: $u$ supplies input $i$ of $c$;
  • $z_{q,v}$: $v \in G_q$ gives query $q$'s result;
  • $t_v$: topological rank.
• Constraints:
  • (A) $\sum_{u \in P_{c,i}} y_{u,c,i} = x_c$;
  • (B) $y_{u,c,i} \le x_u$;
  • (C) $\sum_{v \in G_q} z_{q,v} = 1$;
  • (D) $z_{q,v} \le x_v$;
  • (E) $t_u + 1 \le t_c + |\mathcal C|(1 - y_{u,c,i})$;
  • (F) $x_v \le \sum y_{v,\cdot,\cdot} + \sum_q z_{q,v}$;
  • (G) $y_{u,c,i} \le \alpha_{u,c,i}$, where $\alpha_{u,c,i} = [p(u) \succeq r_{c,i}]$;
  • (H) domains.
• Objective: $\min_{\Pi} \sum_{v \in V_\Pi} \mathrm{cost}(v;\Pi)$. A node's cost is its read and compute cost, plus its retention cost when it is materialized.

2. Current implementation (#1144, #1095 §2–3)

The MILP in crates/plan-selection/src/milp/model.rs is built over MilpInputs (crates/plan-selection/src/groups.rs).

• Execution contexts (groups.rs:680, ContextKind):

  • one per query, at the query's rate;
  • one per ingestion pipeline $I_r$ (per refresh window);
  • one per shareable candidate $m$ (materialized, or a tumbling-window chain), at the rate of its schedule group.

  A NotMaterialized query-time candidate runs once in each context that selects it (RunKind::PerContext, groups.rs:330).

• Result slots (groups.rs:354–374). Row 2, "one candidate per slot per context", ranges over slots: a group's implementation roots form one slot (split by self-read depth), and each private operator node is a slot of its own.

• Variables (model.rs:5–15, choice_variables at model.rs:528):

  • p[ctx, c];
  • x[m] per shareable candidate;
  • a[q, m] for reach;
  • y ANDs;
  • e ("slot an input reads", model.rs:610), only for an input whose producers span more than one slot;
  • latency and held-time epigraphs;
  • g and the threshold levels;
  • acyclic ranks (model.rs:812, model.rs:868).

• Rows 1–10 follow [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 §3:

  • coverage, one candidate per slot, validity, used only if read, sharing, reach, latency;
  • accuracy (A1) as budget shares: $N_q \le \mathrm{parts}(c)$ for each approximate run $q$ depends on (accuracy_rows, model.rs:1589);
  • reader constraints, then executions, held time, retention and scan windows.

• Dominance pruning (prune_dominated_candidates, groups.rs:2099) deletes a candidate that another one equals or beats on every number.

• Objective. It is exact by construction ([Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 O9). Every reader-dependent term is a level choice, a threshold binary or an epigraph with a non-negative cost. One solve to proven optimality gives plan_cost's cost (fix(plan-selection): run the group selection MILP to proven optimality and cost exactly (#1185, part 1) #1188). There is no cut loop.

3. Duplication and misalignment

Each item below was checked on main 1b8289a2.

(a) Private nodes become slots, so one choice costs several binaries.

• Implementations keep their private operator nodes, and each private node is its own ResultSlot::PrivateNode with its own p (groups.rs:354–360). In A, 51 of the 54 slots are private.
• A chain under a merge has one reader and one producer, so its binary repeats the merge's binary.
• When a consumer's producers span several slots, the e variables (model.rs:600–612) then play the role of $y_{u,c,i}$: 26 in A, 127 in B.
• Under no-redundancy condition 3, the choice "merge the chain at width $w$" would be one candidate of the state group, with one $x$ and one edge.

The duplication starts in the memo, as #1160 describes: Pass 2's TumblingWindows and SharedBuild rules add whole implementations to the reader's group. In this fixture, Stage 2 already factors the identical terminal readers: one FinalizeExactAccumulator node in A (memo_candidates.rs:32). The merge and chain nodes below it stay private per candidate.

(b) Identical private subtrees within one group. In B, 50 pairs of identical SummaryMerge nodes (identical inputs included) sit in one group, each private to a different candidate. In C, each query group holds 55 pairs of identical Project ← SummaryEstimate roots. Each copy gets its own slot and its own p in every context that reaches it. Dominance pruning does not merge them, because their candidates differ elsewhere, for example in their readers or producers.

(c) A sketch size is a group, not a property.

• [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 O2 says "a summary state's size configurations are candidates of its group".
• On main they are separate groups: C has KLL k = 412 as G4 and k = 80 as G30. The shared chains are 25 more groups (G5–G29).
• So row 2's "one candidate per group" does not compare sizes against each other, and a reader's input lists producers from several groups.
• 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 (option B, size as a candidate property; design doc docs(planner-layering): state groups from Pass 1, size as a candidate property, two window orders #1183) makes O2 true.

(d) The accuracy requirement depends on the query, not only on the consumer.

• The same quantile at two targets is two groups (G2, G3), because the target is part of the lowered Aggregate's measure. That breaks "group = logical result".
• Once those two groups are one (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), a single consumer candidate, the Finalize of the shared quantile group, serves queries with different budgets. The formulation's $r_{c,i}$ (and $\alpha_{u,c,i}$) cannot then be a fixed property of $(c, i)$.
• The implementation already counts shares per query: A1 limits the approximate runs $q$ depends on to $\mathrm{parts}(c)$ (model.rs:1589–1640).
• The formulation must do one of two things:
  • index the requirement by query, $r_{q,c,i}$ with $\alpha_{q,u,c,i}$, enforced on $q$'s dependency (a/y) rather than on $y_{u,c,i}$; or
  • keep parts as the property a candidate delivers, and the query's share count as what it requires. This is what A1 does today.

(e) "Acyclic by construction" does not hold.

• [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 O7 says the group graph is acyclic and needs no ordering rows.
• On main, "a widened scan puts a Project in the memo group of the scan it reads, so a group's candidate may read its own group" (groups.rs:361–369). Slots are split by self-read depth to cope: depth 0 for the scan, depth 1 for the Project.
• Two kinds of ranks are still emitted:
  • per-context ranks for cyclic components (acyclic_rows, model.rs:812);
  • cross-context ranks, because "two shareable candidates of one memo group, each listed among the other's producers" can justify each other (model.rs:862–868).
• Under condition 1, the scan over the widened label set and the scan the query asked for are different logical results, so they are different groups. The Project is a candidate of the narrow group, reading the wide group, so the cycle cannot arise.

(f) The formulation has no execution contexts.

• In the formulation, $x_v$ selects a candidate once and $\mathrm{cost}(v;\Pi)$ is summed over $V_\Pi$.
• The implementation selects runs instead. A NotMaterialized query-time candidate costs once per context at that context's rate; a shareable candidate costs once on $x$, at its schedule group's rate. B has 360 p for 258 candidates.
• This is how the MILP models materialization and reuse across repeated evaluations: which context a candidate runs in, how often that context executes, and how long a kept result is held.
• The formulation needs this to be faithful. $V_\Pi$ should be the DAG of runs, (context, candidate), with $x$ for shareable candidates and $p$ per context for the rest.

(g) Edge costs exist.

• A reader's usage can depend on which producer it reads (CandidateData::usage_per_producers, inputs_changing_usage, groups.rs:181–187). The objective charges this on AND terms of the read and of the producer's output (t_producers, t_outputs, cost_terms.rs:215–262): 150 and 4 variables in B.
• This is the formulation's per-edge cost $h_{u,c,i}$, which the node-only objective in §1 leaves out. The objective should be $\sum_v w_v x_v + \sum_{(u,c,i)} h_{u,c,i}, y_{u,c,i}$ per context.

4. Proposal

1. Formulation. Update §1 with (d), (f) and (g): runs per context, a per-query accuracy requirement (or parts as the property), and edge costs. Keep the no-redundancy conditions as the contract between Stage 1/2 and Stage 3.
2. Memo (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). Let Pass 1 create state groups with size as a property, and let window composition add SummaryMerge ← SummaryTumblingWindowChain as a candidate of the state group. This removes (a)–(c) at the source; the MILP code does not change.
3. Accuracy target out of group identity. This is a follow-up to 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: the same expression at two targets should be one group, with the target carried as a requirement. This is (d).
4. Widened scans. Keep the widened scan in a group of its own, read by the Project. Then delete the self-read depth split and, if no other cycle remains, the acyclic rows. This is (e).

Acceptance. The size test above, committed as a regression test, shows the following on main after #1160:

• in A, one binary per choice (26 state candidates and 26 edges), no private-node slots for the chain;
• in B and C, no identical operator nodes within one group;
• in C, one KLL state group;
• the cost equality gate (the_optimum_costs_what_plan_cost_says) still passes.

Related

• [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095: the Stage 3 design these contexts come from.
• feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144: the MILP on main.
• Remove unnecessary deadlines and caps in the group selection MILP #1185: deadlines and caps (fix(plan-selection): run the group selection MILP to proven optimality and cost exactly (#1185, part 1) #1188, refactor(planner): plan without deadlines over every tumbling-window width (#1185, part 2) #1198).
• 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: Pass 1 state groups; design doc in docs(planner-layering): state groups from Pass 1, size as a candidate property, two window orders #1183.
• Rename PaneChain to SummaryTumblingWindowChain, and every pane name to the tumbling-window wording #1163: tumbling-window names.