Repository navigation
Description
Example
The paper's RangeHeavy L1 quantiles component: 24 PromQL queries such as quantile_over_time(0.5, data[15m]), quantile_over_time(0.9, data[1h]) and quantile_over_time(0.9, data[15m]) / quantile_over_time(0.5, data[15m]), every 60 s, relative error 0.05 (δ = 0.01, whole result), over data (10,000 series, 2,000,000 rows/s, values non-negative), raw data kept, unit costs tools/dag-viewer/cost-inputs/aws-fargate-us-east-1.json:
asap_planner --workload quantiles.json --deployment-capabilities caps_raw.json \
--cost-inputs aws-fargate-us-east-1.json --run-until stage3
Stage 3 planning time, release build, one thread, median of 5 runs (range):
| Workload | main (59365ce80) |
Stage 3 over execution contexts (#1237, 796d43503) |
MILP variables / rows, main → #1237 |
|---|---|---|---|
| RangeHeavy L1 quantiles | 0.21 s (0.13–0.59) | 7.74 s (6.85–10.8), 37× | 5,579 / 3,817 → 3,731 / 4,322 |
| RangeHeavy-8users L1 quantiles | 0.31 s | 5.25 s, 17× | 5,585 / 3,827 → 3,701 / 8,427 |
| RollupHeavy-8users L1 http-p99 | 1.02 s | 7.04 s, 7× | |
| RollupHeavy L1 http-p99 | 2.08 s | 5.38 s, 2.6× | |
tools/dag-viewer/workloads/random-mixed-seed-862/workload-03.json, default capabilities (defcaps-03) |
2.83 s | 32.0 s, 11× | |
| defcaps-02 | 6.1 s | 23.7 s | |
| defcaps-01 | 5.2 s | 8.6 s | |
random-mixed-seed-862-x5 workload-02, default capabilities |
2.3 s | 13.8 s |
Both find the same optimum where they plan the same thing (defcaps-03: 230.4227/s on both). Other workloads are faster with #1237 (c16 29.8 → 10.4 s, c09 56.9 → 25.5 s, RollupHeavy L1 flows 5.6 → 0.85 s), so the slowdown is specific to some models, not general.
What should happen: Stage 3 over execution contexts should plan these workloads in about the time main takes.
Why it happens
The time goes to HiGHS's branch and bound, not to building the model (Stages 0–2, model construction and plan_cost take the same time on both trees, within ±0.2 s). From the HiGHS logs:
- RangeHeavy L1 quantiles. On
mainevery constraint coefficient is 1 (matrix range [1, 1]); presolve shrinks the model from 3,817 × 5,579 to 291 × 298 and HiGHS closes it at the root (1 node, 250 LP iterations, 0.14 s). With refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 the matrix range is [1, 9e4]; presolve removes only 17% (to 3,606 × 3,217, with 32 continuous columns), the root LP bound is 0.259 against a first solution of 973.95 (gap 99.97%), and the root cuts take 28,593 LP iterations (11.2 s) before the gap closes. - defcaps-03.
mainneeds 1 node and 6,936 LP iterations; refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 needs 268 nodes and 168,382 LP iterations, with a root gap of 95.6%.
Not yet confirmed which rows cause the weak relaxation. The likely ones are the rows #1237 adds over execution contexts, which fractional
- retention (R), $h_v \ge \operatorname{need}{\kappa,u,c,i} \cdot y{\kappa,u,c,i}$ (
stage3-plan-selection/src/milp/retention.rs,retention_constraints): its coefficients are needs in seconds (mainhas no such row, and its matrix range is [1, 1]), and a fractional$y$ keeps$h_v$ , and so$\pi_v h_v$ , low in the LP; - the θ fan-out: one sketch build per θ can feed many consumers, each through its own
$y$ , with no aggregated linking row ([Performance] Stage 3: aggregated θ linking row for the sketch fan-out (c16 85.6 s → 2.5 s) #1296); - the greedy upper bound does not prune as much as the bound
mainhad ([Performance] Stage 3: retention-aware greedy bound, and a lower bound that counts shared producers once #1297).
Proposal
First find which rows weaken the root bound (drop or tighten one family at a time on the workloads above). Then try the following, measuring each. Any change must keep the optimum: the stage3_objective pins and the 197-workload cost comparison stay unchanged.
- Tighten (R) under fractional
$y$ , or state$h_v$ in units of the producer's output interval so the coefficients of (R) stay near 1. - The aggregated θ linking row of [Performance] Stage 3: aggregated θ linking row for the sketch fan-out (c16 85.6 s → 2.5 s) #1296.
- The tighter greedy bound and the lower bound of [Performance] Stage 3: retention-aware greedy bound, and a lower bound that counts shared producers once #1297.
Scope and acceptance
In scope: Stage 3 MILP formulation tightness and presolve on the workloads above. Out of scope: Stages 0–2 and the cost model.
Done when, on the same host and build settings, each workload in the table plans within 2× of main (median of 5), with the same plan cost, and the stage3_objective tests and the 197-workload cost comparison are unchanged.
Status and related work
- Measured by the efficiency review of refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 at
796d43503againstmain59365ce80; that review's raw results and HiGHS logs are the source of every number above. - Whether refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 merges before this is tightened is the reviewer's decision.
- Related: [Performance] Stage 3: aggregated θ linking row for the sketch fan-out (c16 85.6 s → 2.5 s) #1296 (θ linking row), [Performance] Stage 3: retention-aware greedy bound, and a lower bound that counts shared producers once #1297 (greedy and lower bound), Planning is about 20x slower since the full tumbling-window-width domain (#1185) #1197 (planning slower since the full tumbling-window-width domain).
Activity