Feed observed posterior sketch error back into re-planning (execution-time → planning-time loop) #250

Summary

#239 / PR #248 implement Chen et al.'s posterior (query-time) error
estimator for CMS/CU-Sketch/Count-Sketch as a pure, execution-time
computation: given a sketch's actual counter values at readout, it
returns a tighter error bound than the traditional a priori worst-case
guarantee. That estimator is correctly scoped to execution time — it
needs real counter values a query only has once a (currently nonexistent)
sketch runtime has actually ingested data and been read out.

This issue is the natural follow-up: a feedback loop from that
execution-time observation back into planning time. If a workload is
replanned periodically (re-run through ASAPPlanner as data/traffic
patterns evolve), the posterior error estimates observed for past
executions of a query are exactly the kind of empirical, non-adversarial
signal posterior_aware_size_params's ExpectedCaseSizing (PR #248,
crates/asap-aware-mapping/src/boundary.rs) currently asks a caller to
supply as a bare assumption (width_relaxation, chosen with no
grounding). Recorded history could instead derive that assumption from
what the workload's sketches actually experienced last time:

• Record, per deployed sketch/query, the posterior error bound(s) observed
  at readout over some window (execution-time data, needs a real sketch
  runtime + some persistence this repo doesn't have yet — same
  prerequisite Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239 already named).
  Volcano/Cascades cost-based sharing (New feature: add common sub expr elimination #212/Design: pre-ASAP structural CSE via bottom-up hash-consing over Rc<QueryExpr> #223/CSE: decide rule-based vs. cost-based framework for whether to actually share a detected common subexpression #237)'s
  CostModel::cse_recompute_cost/cse_shared_maintenance_cost are a
  precedent for "cheap default heuristic, real deployment data overrides
  it" — this would be the same shape one level over: real observed
  accuracy history overriding ExpectedCaseSizing's bare assumption.
• On the next replan, feed that history into size_params (or a new
  CostModel hook) so a workload with a well-behaved, non-adversarial
  observed distribution can earn a tighter/cheaper sketch, while a
  workload that actually saw adversarial-ish behavior falls back toward
  default_size_params's worst-case guarantee automatically instead of
  via a caller's guess.

Why not now

Same blocker #239/#248 already hit: this repo has no sketch runtime, no
counter arrays, and (new for this issue) no persistence/history layer for
recording past execution outcomes at all. This is planning-adjacent
future work, not an immediate implementation task — filing to record the
idea and the concrete hook point (ExpectedCaseSizing/posterior_aware_size_params)
so it isn't lost.

Related

• Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239 — posterior (query-time) error estimation
• PR feat(sketch): posterior (query-time) error estimation for CMS/CU-Sketch/Count-Sketch (Chen et al. IMC'21) #248 — landed the estimator + posterior_aware_size_params/ExpectedCaseSizing
• New feature: add common sub expr elimination #212/Design: pre-ASAP structural CSE via bottom-up hash-consing over Rc<QueryExpr> #223/CSE: decide rule-based vs. cost-based framework for whether to actually share a detected common subexpression #237 — CSE's cost-based framework, a structural precedent for
  "cheap default, real data overrides it"