Repository navigation
Optimizer: CMS accuracy constraint (ACC) using accuracy_sla #526
Description
Part of #523 (Track 3: non-empirical gap 2). Depends on #525's profiling pass for the sample/total-weight query.
- Implement
Error(a,g,θ_a) ≤ ε_afor CMS only (analytic ε-δ guarantee); every other sketch family stays unconstrained for now — same as today, not a regression. Extending sketch-bench's cardinality sweep to unlock empirical Error for other families is separate follow-up work. (Optimizer: extend sketch-bench cardinality sweep for empirical Error beyond CMS #566) - ε_a = the existing (currently dead)
ControllerOptions.accuracy_slafield, threaded throughextract_aqesontoAQE/QueryRequirements.0.0default (today's serde default, already flagged bywarn_default_slas) means "unconfigured" → treat as unconstrained, skip (ACC). - Semantics: accuracy_sla is relative-to-true-value percentage error, not CMS's native L1-relative ε. Converting requires
‖f‖₁/true-value — get both from a single live sample of the AQE's ownquery_stringsagainst Prometheus, in the same profiling pass as Optimizer: auto-infer N_g from Prometheus #525's N_g query (also needs the hints-fallback treatment for offline testing).
Activity
milindsrivastava1997 commentedon Jul 13, 2026
Implementation plan discussed:
Formula. CMS's
rows/colsnaming (confirmed via sketch-bench's BENCH_SWEEP.md, matchesdepth/widthincount_min.rs) is the standard Cormode–Muthukrishnan parameterization:ε = e/width(error relative to‖f‖₁),δ = e^-depth(failure probability). No bespoke reverse-engineering needed. δ isn't exposed as a separate user-facing knob for v1 — the existingCMS_DEPTHS = [3,5]grid already gives δ≈5%/0.7%, good enough without a dedicated confidence constant.Scope. Plain
CountMinSketchonly (Sum/Count statistics).CountMinSketchWithHeap(Topk) stays unconstrained like every other non-CMS family — its accuracy story is rank error, not frequency error, no closed form derived, and it isn't benchmarked in sketch-bench yet anyway (#524 / sketch-bench#30). A rank-error bound for CMS+Heap is separate future work if ever needed.ε_a source. The existing (currently dead)
ControllerOptions.accuracy_slafield, threaded throughextract_aqesontoAQE/QueryRequirements.0.0default = unconfigured → skip the (ACC) check entirely for that AQE, and skip its profiling queries (avoids burdening every query with extra Prometheus calls when nobody asked for an accuracy guarantee).true_value semantics. accuracy_sla is relative-to-true-value % error, not CMS's native L1-relative ε — needs
‖f‖₁and a true_value to convert. For a grouped AQE there's one true_value per group, each with a different ratio to the total; using the smallest observed group value (worst case) rather than an average, consistent with #524/#525's drop-rather-than-underestimate policy — makes accuracy_sla a real per-group guarantee, not just "on average." Skewed workloads may rule out CMS entirely even when large groups would've been fine; acceptable since EXACT is always the fallback.Profiling mechanism. Two live Prometheus instant queries per AQE (only when accuracy_sla is set), batched into the same per-AQE profiling pass as #525's N_g query, same hints-fallback treatment:
by(...)clause) →‖f‖₁, the total stream weight.Filter placement. New module (e.g.
optimizer/accuracy.rs) withcms_epsilon(width),cms_delta(depth),meets_accuracy(...), used to filter CMS candidates alongside #524's missing-cost-data filter.milindsrivastava1997 commentedon Oct 26, 2026
Superseded by the rqe-optimizer MILP (ProjectASAP/sketch-bench#129, #794); the greedy optimizer was removed in #807. Remaining work tracked under #790 / ProjectASAP/sketch-bench#143. The MILP takes accuracy from sketch-bench's saturation curves (#804).