Skip to content

[Design] Price CPU and latency from a measured cost table per state family (scan, update, merge), not built-in unit costs #1314

Open

Description

@zzylol

Example

sum by (job) (rate(requests_total[1h])), exact, evaluated every 300 s over 1,000 counter series sampled at 1 Hz, with default CostInputs:

Plan Predicted cost/s Predicted latency Measured latency p50 Measured total CPU
Query-time Rate over raw data (selected with raw data retained) 0.0936 28.1 ms 334 ms 1.12 ms/s
Stored 300 s Rate windows (selected with raw_data_retained: false) 0.0989 0.027 ms 7.4 ms 0.14 ms/s

The planner keeps the query-time plan because it predicts it 6% cheaper. The stored plan measures 45× faster and uses 8× less CPU. At the same default unit costs, using the measured CPU and the measured stored bytes, it is about 2.4× cheaper: 0.47/s against 1.12/s.

The default plan for quantile_over_time(0.99, latency[1h]) (1,000 series, 1 Hz, every 10 s) has the opposite problem:

  • The planner selects a DDSketch built from raw data at query time over the exact plan, predicting 1.2× less work.
  • It measures 2× more work: 780 ms against 388 ms per evaluation, because building a DDSketch costs 217 ns per row against 82 ns to scan a row exactly.

Across the measured grid, measured ÷ predicted (median) by plan kind:

Plan kind n Latency Query CPU Ingestion CPU
Exact, from raw data at query time 128 13.3 13.3 –
DDSketch, from raw data at query time 25 34.9 35.1 –
Stored exact-accumulator windows 106 146 150 29.8
Stored DDSketch windows 25 908 958 68

The error differs by plan kind by a factor of 70, so rankings flip. The predicted total CPU orders the exact plan and the selected plan the same way as the measurement in only 36 of 85 default cases, and in 58 of 85 with raw_data_retained: false.

How this was measured:

  • Planner and environment: main 59365ce80, plan_installable with default capabilities and cost inputs. Every plan ran in the executor, in a release build, serially, pinned to one core of an idle 56-core server.
  • Baseline: the same executor scanning raw data held in memory, not Prometheus.
  • Data: synthetic: a latency gauge and a requests_total counter, 10 jobs. All accuracy targets were 1% relative, δ = 0.01.
  • Scope: raw ingestion and storage were not measured. Ingestion runs as one batch per window.

Problem and why now

  • Every cost model ranks plans by CPU and latency, and neither comes from measurement by default.
  • CostInputs::measured_operation_costs defaults to an empty table (MeasuredOperationCosts::default(), crates/cost/src/model.rs). So every node is priced from its formula at ResourceSpeed::illustrative(): 1 ns per CPU operation and 0.1 ns per scanned byte (crates/cost/src/model.rs, line 130).
  • The formulas count each operation as one: one scan per sample, one update per row, one merge per state. The real unit costs differ by family and operation:
Operation, one core Measured Built-in assumption
Scan one raw row (exact, query time) 82–107 ns about 5 ns per sample
DDSketch update at query time 217 ns per row about 1 ns
Exact-accumulator merge 230 ns per state (Rate 350 ns) about 1 ns
DDSketch merge 2.0–3.1 µs per state about 1 ns
KLL merge 5.3 µs per state about 1 ns
Ingestion update 260 ns per sample (exact), 540 ns (DDSketch) –
  • A measured table can already be supplied. Its structure (OperatorCost: operator, phase, family, ns_per_unit, ns_per_invocation, memory_bytes_per_state, in crates/cost/src/measured.rs) can express all of the table above.
  • But nothing in the repository measures it. The only producer converts an external sketch benchmark (convert_rqe_atomic_costs), which covers sketch kernels, not the executor's scans or exact merges.
  • A partial table falls back to one global calibration factor, which A partial measured cost table can still mis-rank plans: calibrate per operator kind #791 shows can still mis-rank.

Intended users and MVP

  • Users: anyone running the planner with default inputs, including demos and evaluations.
  • MVP: a default measured table for the in-repo executor, covering scan, update (ingestion and query time) and merge for every state family the planner can select, plus Aggregate measures and SummaryEstimate.

Inputs, outputs, and end-to-end outcome

  • Input: a measurement binary in asap-devtools runs each operator over synthetic data on one core and writes a MeasuredOperationCosts table. The table records provenance (executor commit, machine).
  • Output: that table becomes the default measured_operation_costs. A deployment can still pass its own.
  • Outcome: on the grid above, measured ÷ predicted is within 2× for every plan kind. Rankings follow the measurement.

Simplest viable approach

  1. Measure. Write the measurement binary, one entry per (operator kind, phase, family) the planner can emit, with the units OperatorKind already defines: per sample, per row, per state merged, per group.
  2. Ship. Check in the resulting JSON and load it as the default in CostInputs::default().
  3. Feed latency. query_latencies already uses a measured merge time when the table has one (merge_ms in crates/cost/src/plan/cost.rs). Make sure every query-time node's latency comes from the same table.
  4. Re-measure whenever the executor's per-operator costs change: for example after [Performance] Merging a stored state costs more than scanning a raw row, which caps stored-window speedups #1312. The provenance makes a stale table visible.

New concepts or interfaces requiring decisions

Alternatives and quality attributes

Acceptance behavior

  • On the grid of this measurement, measured ÷ predicted latency and query CPU are within 2× (median) for each of the four plan kinds above.
  • In the rate example, the planner selects stored windows when raw data is retained.
  • The exact-vs-selected ordering agrees with the measurement in at least 80 of the 85 default cases. That target is open for decision.

Human decisions required

Related

Activity

  1. added
    cost-modelCost formulas, statistics, ranking, and selection
    enhancementNew feature or request
    on Nov 15, 2026
  2. zzylol commented on Nov 15, 2026

    @zzylol
    ContributorAuthor

    Another mis-ranking from the same unit-cost gap. This one is a plain standing query, not a demo setting.

    Workload

    • Query: sum by (service,status)(rate(http_requests_total[5m])), fixed_interval_at {interval: 60000, evaluation_phase: 0}.
    • http_requests_total: counter, series_count 10000, sample_interval 1000.
    • Arrival: mixed {rows_per_second: 10000}. Target ε 0.05, δ 0.01.

    What the planner does (main 59365ce, default CostInputs)

    • It selects the query-time plan at 0.4705/s.
    • The ingestion-time chain plan is 0.5162/s.

    With measured unit costs, the order flips

    Query-time plan Chain plan
    Cost per series per second 625 ns 323 ns

    So the chain is about 1.9× cheaper. The measured unit costs are about 125 ns per query-time row, 260 ns per ingested sample, and 350 ns per state merge.

    Why

    • The built-in costs charge about 5–9 ns of CPU per row, against a measured 13–30× more.
    • They charge about 1 op per merge, against a measured ~350× more.
    • Memory is priced realistically, so the error biases the planner against stored state.
    • As a result, the planner switches to ingestion time only when r > 0.75·(P+1)/(P−1) samples/s, where P = W/I. Measured costs put the threshold near r > 0.17/s at P = 5, I = 60 s.

    At 15 s sampling, query-time is correct under both the built-in and the measured costs. A stored window holds only 1–4 samples, and merging it costs more than scanning them.

  3. zzylol commented on Nov 15, 2026

    @zzylol
    ContributorAuthor

    The MVP shape changed in #1355: instead of a default measured table, the built-in formulas now carry the reference executor's measured time per unit of work (crates/cost/src/node/operations_per_unit.rs: time-range rows, hash-aggregate keys and measures with the exact quantile's sort, updates, merges and readouts per state family, the chain's per-state emit). They are the fallback; a table measured on the deployment's machine (#1317's calibration) overrides them node by node through CostInputs::measured_operation_costs, as before.

    Why not a default table: some of the measured costs are not "units × ns" (the sort's 5.5 × log2(rows per group), the cost per grouping key, the chain's per-state emit, the cost per merged byte of unmeasured sketches), so they have to live in the formulas either way; the per-family constants sit next to them.

    What #1355 does not cover from this issue's MVP: the source scan is not measured (it keeps its formula), nor are Count-Min, Count Sketch, HyperLogLog, KMV and UnivMon on the executor (scaled from asap_sketchlib's own costs). #1355 is "partially addresses" for that reason; the per-machine table stays #1317.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

cost-modelCost formulas, statistics, ranking, and selectionenhancementNew feature or request

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions