Feed empirical sketch error, resource usage, and data distributions into planner estimates #322

Summary

Add an empirical evidence path from real workloads and/or sketch-bench into ASAPPlanner's cost and candidate estimation. The planner should be able to use measured sketch error, resource usage, and observed data-distribution characteristics instead of relying only on static/default heuristics.

Motivation

Current cost-model hooks make the planning boundary explicit, but most estimates are still supplied as hand-authored model inputs. Real benchmark and workload evidence would let the planner compare summary families and lifecycle alternatives using reproducible measurements, while retaining conservative behavior when evidence is absent or stale.

This task is distinct from:

• Feed observed posterior sketch error back into re-planning (execution-time → planning-time loop) #250, which feeds posterior runtime error back into later replanning;
• (dev-tools) Export and visualize planner cost/benefit annotations #286, which exports and visualizes modeled/measured annotations; and
• asap-aware-mapping: define optimization strategies, cost model, and nested-summary error propagation #301, which defines the broader cost vocabulary and optimization design.

This issue owns producing and consuming the empirical estimator inputs themselves.

Scope

Evidence to collect

From representative real workloads and/or sketch-bench, record at least:

• observed sketch error by algorithm, parameters, query type, and workload;
• build/update/merge/readout latency or CPU cost;
• peak and retained memory/state size;
• input volume, update rate, and query/evaluation rate;
• data-distribution characteristics such as skew, cardinality, heavy-hitter concentration, and temporal drift; and
• enough environment metadata to reproduce and compare measurements.

Artifact contract

Define a versioned machine-readable benchmark artifact with:

• benchmark and model version;
• sketch family/algorithm and parameters;
• workload/dataset identity and distribution descriptors;
• units for every metric;
• sample count and uncertainty/dispersion where available;
• hardware/runtime provenance; and
• collection timestamp or validity metadata.

Unknown measurements must remain unavailable rather than becoming zero.

Planner integration

• Add a loader/provider that maps compatible benchmark observations into CostModel estimates.
• Use empirical evidence for candidate ranking, sizing, and lifecycle cost inputs where the measurement's workload/distribution applicability is established.
• Keep existing conservative/default estimates as the fallback when no compatible evidence exists.
• Make modeled versus measured provenance explicit so downstream export ((dev-tools) Export and visualize planner cost/benefit annotations #286) can distinguish them.
• Avoid overfitting a measurement to an incompatible distribution, sketch configuration, or runtime environment.

Suggested first milestone

1. Select two or more representative sketch families already modeled by ASAPPlanner.
2. Run a reproducible benchmark matrix over at least uniform and skewed/Zipf-like inputs, ideally including a real trace.
3. Emit the versioned artifact.
4. Load it through a CostModel implementation.
5. Demonstrate that changing compatible empirical evidence changes a planner ranking or lifecycle decision.
6. Demonstrate conservative fallback for missing, stale, or incompatible evidence.

Acceptance criteria

• A checked-in schema and example empirical artifact exist.
• Benchmark commands and dataset provenance are documented and reproducible.
• Error, time/CPU, memory/state, and distribution evidence have explicit units and provenance.
• Planner estimates consume matching empirical records through a public cost-model boundary.
• Tests cover matching, mismatch, missing evidence, and a decision changed by empirical inputs.
• Generated explanations can identify the benchmark/model version that supplied a measured estimate.

Follow-up work: sketch error self-estimation

After empirical benchmark evidence is available to planning, add sketch-side/self-estimated error signals as another evidence source. Relevant directions include:

• Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239 / Chen et al., Precise Error Estimation for Sketch-based Flow Measurement (IMC '21), for posterior CMS/CU-Sketch/Count-Sketch error estimation;
• Feed observed posterior sketch error back into re-planning (execution-time → planning-time loop) #250, for feeding observed posterior errors into replanning; and
• Self-Mending Sketches (ACM paper), as a follow-up design/implementation direction for sketches that diagnose or adapt their own error behavior.

Self-estimation should remain distinguishable from offline benchmark measurements: both are empirical evidence, but they have different timing, provenance, and applicability guarantees.

Related

• Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239 — posterior sketch error estimation
• Feed observed posterior sketch error back into re-planning (execution-time → planning-time loop) #250 — execution-time error feedback into replanning
• (dev-tools) Export and visualize planner cost/benefit annotations #286 — measured/modeled cost annotations in DAG export and viewer
• asap-aware-mapping: define optimization strategies, cost model, and nested-summary error propagation #301 — cost definitions and optimization design