Repository navigation
Description
Example
c16_topk_rate_chain: one query, topk(5, sum by (host)(rate(c[5m]))), evaluated every 60 s and every 120 s, ε = 0.05. Stage 3 on #1237 (head baab8969a), release asap_planner --run-until stage3, bundled HiGHS 1.15.0 on one thread, median over HiGHS random_seed 0–4:
#1236 (dcfd69420) |
#1237 (baab8969a) |
|
|---|---|---|
| solve time | 29.7 s | 85.6 s (69–165 s) |
| B&B nodes (median) | 28 | 139 |
| simplex iterations (seed 0) | 125k | 326k |
| rows / cols built (seed 0) | 4,913 / 6,839 | 7,903 / 7,858 |
The optimal plan is found early; the time goes into proving it. With the cut below (simple form), the same workload solves at the root:
| #1237 | #1237 + cut (simple N) | |
|---|---|---|
| c16 | 85.6 s, 139 nodes | 2.5 s (2.5–2.7 s over 5 seeds), 1 node |
| c09_topk_rate_noacc | 21.4 s | 3.3 s |
| 197-workload review set, total MILP time (seed 0) | 223 s | 20 s |
The objective is unchanged on every workload (all 197 on seed 0; c09/c16/c21 on seeds 0–4). Measured with an environment-gated experiment on top of baab8969a, together with the retention row that #1237 adds (h_v ≥ least need · x_u); that row does not change c16.
Why it happens
The estimate's group can read any of hundreds of sketch θ variants (c16: 240 θ × {Lifetime None, OneEvaluation} per evaluation context; twin dominance in #1237 now removes the None copies). (A) spreads Σ y = 1 over them, and (B) bounds each edge alone, y_{κ,u,c,i} ≤ x_u. The LP can then select the producer u below every sketch at about 1/360 of a unit, so the whole subtree under the sketches, scans included, costs almost nothing in the relaxation (LP gap 0.998 on both heads). With two evaluation contexts the B&B tree must close this in both at once, which is why #1237 needs 5× the nodes of #1236 on c16. c09/c19/c20/c21 (one context) have the same structure and still spend most of their time there.
Proposal: the aggregated linking row
For each producer execution u, consumer memo group G, consumer context κ and input i:
where N_{κ,G} is an upper bound on how many executions of group G a plan selects in context κ. It is added only where the number of terms exceeds N. Per-edge (B) stays.
- Simple form (measured above): N_{κ,G} = the number of queries answered in κ (from the z variables), and no row for a context κ whose executions are read from another context. It holds on c16 but is not proven in general.
- Sound form (to prove): N_{κ,G} = Σ_q occ(R_q, G) over the queries whose executions reach κ, with occ(R, G) = [R = G] + max_{c ∈ R} Σ_{child} occ(child, G). Argument: under (A) each selected execution has exactly one producer per input and under (F) at least one use, so the selected executions of G number at most the root-to-G paths of one derivation per query.
- A looser sound bound (a pair recursion) was tried in an earlier review round and only reached 189 s on an earlier head of c16: the bound has to be tight to help.
Scope and acceptance
- In: the row, the proof (or a precise statement of when the simple N is valid), N computed in Stage 3 from the memo and the selectable executions, unit tests on N for a group occurring twice in one query tree and for a cross-context reader.
- Acceptance: c16 and c09 solve in a few seconds on seeds 0–4 with the same objective as without the row; the objective is unchanged on the round-4 review set and the 34
tools/dag-viewerexamples; a test where the simple N would be wrong (a group read twice in one query) keeps its optimum. - Out: other strengthenings of (R) and (X).
Status and related work
- Deferred from the refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 efficiency reviews (rounds 1 and 2) as follow-up "F4"; approved as a follow-up 2026-11-14.
- Related: refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 (execution contexts, twin dominance, the retention row h_v ≥ least need · x_u), Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207 (formulation refactor), [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 (Stage 3 MILP design).
Activity