Repository navigation
Description
Problem, by example
Stage 3's MILP prices some plans it does not select higher than asap_cost::plan_cost prices the same plans once built. The selected plan's objective still equals its plan_cost. But a cheaper plan can lose, because the model overprices it. Two patterns, both measured by building enumerated selections with plan_of and costing them with plan_cost:
(b) Twin executions read by different queries in one context. Example (v04): over the gauge m (1,000 series, 1 sample/s), these four queries:
sum_over_time(m[1m])as a range query (60 s steps over 10 min), every 60 s and every 120 s;count_over_time(m[1m]), every 60 s and every 120 s.
In one evaluation context, the two queries can read different twin executions of the TimeRange(1m) group: one reads its ℓ = None candidate, the other its OneEvaluation candidate.
- In one such selection, the model costs the
TimeRangeexecution at 0.0165/s;plan_costcosts the same node at 0.011/s. - The same pattern shows on v04n, v13, v13n, v20 and v07, with the model up to 109% higher.
- On v04n and v13n, the selected plan is not the
plan_costoptimum. A plan cheaper by 7.3e-10/s exists (relative 6.8e-9 and 4.1e-9) that the model priced higher.
(c) A OneEvaluation query-time Scan read by readers of different windows. Example (v05): count_over_time(m[1m]) and max_over_time(m[1h]), every 60 s and every 600 s.
- A plan in which the shared
OneEvaluationscan's selected reader reads 1 min costs 0.00042/s inplan_cost. - The model costs it at 0.0256/s, as if the scan read 1 h on every run.
- The same pattern shows on v12, with the model up to 60% higher.
Both patterns come from the functional review of #1237 at 813ecaef5. Out of 3.98 million enumerated plans over 38 workloads, the selected plan was the plan_cost optimum in 36 of 38.
Why it happens
-
(b) An execution's rate
$\rho_\kappa$ is fixed before solving (stage3-plan-selection/src/cost.rs,executions_per_second). It comes from every query whose walk reaches the group in the context (asap_types::stages::queries_of_contextoverSelectableExecutions::readers_of), not from the queries that actually read that execution. When two twins split the readers, each is charged at the rate of all of them.plan_costrates each node by the queries reading it in the built plan (execution_demand::consumers). -
(c) A materialized query-time
Scanexecution's read window is fixed before solving at the most any of its possible readers reads (cost.rs,execution_read_ms: "one materialized, shared by its readers, reads the most any of them reads in one run"). It is not the most its selected readers read. A not-materialized scan's read is already on its edges (one reader per context), which is exact.
Proposal
Both are formulation changes, so they are out of scope for #1237:
-
(c), exact and linear. Treat the scan's read window like
$h_v$ : add a variable $w_e \ge \mathrm{read}{e,c}, y{e,c}$ per selected reader edge, and price the scan's run linearly in$w_e$ (its cost per run is affine in the rows it reads). This mirrors (R). -
(b). Rate an execution by its selected readers. Options:
- (1) Split a context's executions per reader set. This means more executions.
- (2) Charge each reader's share of the run rate on its edge or output. This is exact only when the rate is additive over readers. It is not when two readers on one grid share runs.
- (3) Keep today's rule and document the bound: the model is never below
plan_costfor these patterns. So it can only miss a cheaper plan, never select an infeasible one.
Scope and acceptance
- In scope: (b) and (c) only.
- Acceptance:
- On v04n, v13n and v05, every enumerated plan's model cost equals its
plan_costwithin 1e-9 relative. - v04n and v13n select the
plan_costoptimum. - The plan_cost-optimality contract test (draft PR test: installable selection and plan_cost optimality contract (tests only) #1334) covers these workloads.
- On v04n, v13n and v05, every enumerated plan's model cost equals its
Related
- refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 (PR 7, selection over execution contexts) found and documents these.
- test: installable selection and plan_cost optimality contract (tests only) #1334 (draft) adds the plan_cost-optimality contract test.
- Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207 tracks the selection refactor.
Activity