cost model: estimate CPU, memory, and scan costs from algorithm complexity

[zzylol]

Summary

Implement an analytical planner cost estimator that derives CPU work, memory/state usage, disk or object-store scan I/O, and related costs from algorithm complexity plus workload/data characteristics. This gives ASAPPlanner a principled modeled estimate when compatible empirical benchmark evidence (#322) is unavailable.

Motivation

The current DAG annotations can use RelativeStructuralUnits, which primarily reflect plan structure. That proxy cannot explain cases where a plan has more operators but is substantially cheaper in practice—for example, replacing a raw aggregation over a large input with a compact sketch update/readout path.

The planner needs resource-aware mathematical estimates rather than treating every DAG node as roughly equal. Unknown inputs must remain unavailable; the model must not invent row counts, cardinalities, update rates, state sizes, or hardware throughput.

Scope

Resource dimensions

Estimate at least:

• CPU work for build, update, merge, raw aggregation, and summary readout;
• peak and retained memory/state size;
• disk/object-store bytes scanned and I/O operations where applicable;
• network/materialization bytes where a plan crosses an explicit boundary; and
• recurring rates versus finite-horizon/one-shot totals without mixing their units.

Analytical inputs

Use explicit, unit-tagged inputs where relevant:

• input rows and bytes;
• distinct/group cardinality and distribution/skew descriptors;
• update and query/evaluation rates;
• sketch algorithm and concrete parameters (width, depth, k, HLL precision, reservoir size, Hydra dimensions, etc.);
• key/value widths and per-group state layout;
• merge fan-in and number of consumers;
• storage scan bandwidth/latency and CPU throughput calibration; and
• an explicit evaluation horizon when rates and one-shot work must be combined.

Complexity-to-cost formulas

Define versioned formulas for the currently supported exact and approximate families. Examples include:

• raw scan/aggregation: O(input_rows) CPU plus input_bytes scanned;
• grouped exact aggregation: state proportional to group cardinality and accumulator width;
• CMS/Count Sketch: update CPU proportional to depth and state proportional to width * depth * counter_width;
• KLL: state/update/readout estimates derived from k and compaction behavior;
• HLL: state proportional to register count and readout proportional to registers;
• merge costs proportional to state size and merge fan-in; and
• shared summaries counted once for state/build/maintenance while consumer readout costs remain per consumer.

Asymptotic notation alone is insufficient for plan comparison. Each supported formula must produce a dimensional estimate (operations, bytes, or time/rate after applying an explicit calibration), carry model version and inputs, and document constants/assumptions.

Planner integration

• Add a public analytical CostModel implementation or provider.
• Produce structured CostAnnotation values with units, inputs, model version, baseline, delta, and benefit ratio for DAG export/viewer ((dev-tools) Export and visualize planner cost/benefit annotations #286).
• Allow empirical records from Feed empirical sketch error, resource usage, and data distributions into planner estimates #322 to calibrate or override compatible analytical coefficients while keeping Modeled and Measured provenance distinct.
• Fail closed to Unavailable when required statistics or calibration inputs are missing, invalid, stale, or incompatible.
• Ensure candidate selection and displayed annotations use the same cost calculation rather than independent formulas.

Initial demonstration

Include a generated query/workload in which a sketch aggregation has more DAG nodes than the raw aggregation but is estimated cheaper because it processes/retains less state or avoids repeated raw scans. The exported viewer comparison should identify exactly which CPU, memory, and scan terms produce the positive benefit; no hand-edited JSON values.

Acceptance criteria

• A design/reference table defines formulas, units, assumptions, and required inputs for every initially supported family.
• Tests validate formulas against hand-computed examples and cover monotonicity in rows, bytes, groups, consumers, and sketch parameters.
• CPU, memory, and scan costs remain separate dimensions until an explicit, versioned calibration converts them to a comparable objective.
• Shared state and shared scans are counted once; per-consumer readouts are counted per effective consumer.
• Rate and one-shot values cannot be combined without an explicit horizon.
• Missing or non-finite inputs produce Unavailable or a typed error, never zero or a fabricated estimate.
• At least one planner choice changes when analytical resource inputs change.
• dag_export and the viewer show a generated positive sketch-vs-raw benefit with complete inputs and model provenance.
• Analytical output can be compared with Feed empirical sketch error, resource usage, and data distributions into planner estimates #322 benchmark observations, with documented error/residuals, without relabeling modeled values as measured.

Related

• (dev-tools) Export and visualize planner cost/benefit annotations #286 — export and visualize structured modeled/measured costs
• Recurrence-aware optimization: cost shared maintenance by query repetition #287 — recurrence-aware cost rates and horizons
• asap-aware-mapping: define optimization strategies, cost model, and nested-summary error propagation #301 — cost vocabulary and optimization-design umbrella
• Feed empirical sketch error, resource usage, and data distributions into planner estimates #322 — empirical errors, resource usage, and data-distribution evidence

[zzylol]

The core analytical cost model landed in #332. I split the remaining acceptance gaps into explicit follow-ups:

• CPU, peak-memory, and scan-byte formulas over evidenced physical DAGs — feat(cost): estimate physical DAG resources analytically #332
• Separate resource dimensions with explicit versioned calibration — feat(cost): estimate physical DAG resources analytically #332
• Shared-node accounting, horizon handling, fail-closed validation, planner selection, and exported provenance — feat(cost): estimate physical DAG resources analytically #332
• Disk/object-store I/O operation counts — cost model: estimate disk and object-store I/O operation counts #345
• Network/materialization bytes at explicit boundaries — cost model: estimate network and materialization bytes at explicit boundaries #346
• Comparison with Feed empirical sketch error, resource usage, and data distributions into planner estimates #322 observations and documented residuals — cost model: validate analytical estimates against empirical benchmark evidence #347

Closing this parent implementation issue; the unchecked work remains tracked by the linked follow-ups.