feat: Optimization-based sketch/streaming config selection

[milindsrivastava1997]

Overview

Replaces the hardcoded decisions in planner/sketch.rs, planner/window.rs, and planner/promql.rs:is_supported() with an optimization-based approach that jointly selects sketch type, parameters, window config, and query method for a given RQE workload.

Design doc: .design_docs/sketch-config-optimization-formulation.md

Problem statement

The planner currently hardcodes:

• Sketch choice — fixed Statistic → AggregationType map in planner/sketch.rs
• Sketch parameters — constants like CMS depth=3/width=1024 in planner/sketch.rs:6-14
• Window size — always tumbling, size = repeat interval (planner/window.rs)
• Query support — boolean AST-pattern match with no cost/accuracy tradeoff (planner/promql.rs:163-169)

There is also no mechanism for one streaming config to serve multiple queries (amortizing ingestion cost), and no connection between sketch-bench measurements and planner decisions.

Formulation

The problem is modeled as an uncapacitated facility-location MIP:

Inputs: List of RQEs r = (QE_r, T_r). Each QE decomposes into AQEs (atomic query expressions, deduplicated across RQEs). Each AQE has a profiled cardinality/skew θ_a, query frequency f_a = Σ 1/T_r, lookback range range_a, and accuracy tolerance ε_a.

Decision variables:

• y_g ∈ {0,1} — whether streaming config g is deployed
• x_{a,g} ∈ {0,1} — whether AQE a is served by config g

Each config g = (sketch_type, params, ingest_type, W, S, retention_windows, metric, label_set, spatial_filter). Every AQE also has a dedicated EXACT_a config (no sketch, queries raw data directly, IngestCost=0, Error=0) ensuring the problem is always feasible.

Objective:

minimize  Σ_g y_g · IngestCost(g)  +  Σ_{a,g} x_{a,g} · f_a · QueryCost(a,g)

Both terms are cost-per-second. IngestCost covers ingestion CPU + memory (steady-state). QueryCost covers per-query CPU + memory (transient).

Constraints:

Σ_{g: Feasible(a,g)} x_{a,g} = 1     for all a   (each AQE assigned to exactly one config)
x_{a,g} ≤ y_g                         for all a,g  (can't use an undeployed config)
x_{a,g}, y_g ∈ {0,1}

Feasible(a,g) encodes: capability matching (label/metric/window/statistic), retention coverage (retention × W ≥ range_a), valid (ingest type, query method) combination, accuracy (Error(a,g,θ_a) ≤ ε_a), and optional latency SLA.

Analytical cost model

Three boolean sketch properties determine cost structure: mergeable, subtractable, subpopulation_aware. Let N(s,g) = 1 if subpopulation_aware(s), else N_g (distinct label-group count from θ_a). Let n = ⌈range_a/W⌉.

The query method is determined (not a free variable) by ingest type + sketch algebra:

Ingest type	Condition	Query method
Tumbling	W = range_a	Neither (direct read)
Tumbling	W < range_a, subtractable	Subtract
Tumbling	W < range_a, mergeable	Merge
Tumbling	W < range_a, neither	Infeasible
Sliding	W = range_a (forced)	Neither
Sliding	W < range_a	Infeasible

Window constraints: W ≤ range_a (no over-coverage), W ≤ T_r (freshness).

Ingestion memory = Mem_active + Mem_retain:

• Tumbling: N(s,g)·mem(s,p) active + n·N(s,g)·mem(s,p) retained
• Sliding: ⌈W/S⌉·N(s,g)·mem(s,p) active + N(s,g)·mem(s,p) retained (n=1 forced)

Ingestion CPU: ρ_g · insert_cpu(s,p) (tumbling) or ρ_g · ⌈W/S⌉ · insert_cpu(s,p) (sliding). Does not scale with N(s,g).

Query CPU:

• Neither: N(s,g) · query_cpu(s,p)
• Merge: N(s,g) · ((n-1) · merge_cpu(s,p) + query_cpu(s,p))
• Subtract: N(s,g) · (subtract_cpu(s,p) + query_cpu(s,p))

Query memory (transient):

• Neither: N(s,g) · mem(s,p)
• Merge: n · N(s,g) · mem(s,p)
• Subtract: 2 · N(s,g) · mem(s,p)

Atomic costs (mem, insert_cpu, merge_cpu, query_cpu) come from sketch-bench.

Implementation plan

Phase 1 — Scaffolding (all-EXACT end-to-end)

• Define OptimizerSolution type: deployed configs + AQE→config assignments + query method per assignment + cost estimates. This is a permanent first-class output type; a thin translator converts it to StreamingConfig + InferenceConfig.
• AQE extraction: parse RQE PromQL → QueryRequirements, decompose QEs into AQEs, deduplicate, compute f_a.
• Wire full pipeline with every AQE assigned to its EXACT_a config. Validates plumbing before real optimization logic is added.

Phase 2 — Per-AQE sketch selection (greedy, no sharing)

• Candidate generation (G enumeration): per AQE, combine compatible_agg_types × parameter grid × window-size grid (W ≤ range_a, W ≤ T_r) × slide interval × retention depth. Reactive: only propose label granularities existing AQEs need.
• Sketch algebraic property catalogue: define mergeable, subtractable, subpopulation_aware for each AggregationType. Encode as a lookup.
• Analytical cost model: implement IngestCost(g) and QueryCost(a,g) formulas. Use stub/hardcoded atomic costs initially; real sketch-bench values come later.
• Feasible(a,g) predicate: reuse window_compatible, spatial_filter_compatible, topk_weighting_compatible from asap_types::capability_matching (PR 258 add capability based matching to asap query engine instead of matching incoming queries against pre configured queries in inference config #259). Label matching stays exact for now. Accuracy check stubbed to always pass.
• Greedy assignment: per AQE independently, pick feasible config minimizing IngestCost(g) + f_a · QueryCost(a,g).

Phase 3 — Full MIP with sharing and accuracy

• MIP solver: replace greedy with good_lp + coin_cbc facility-location MIP. Enables cross-AQE config sharing.
• Label superset matching: extend labels_compatible in asap_types::capability_matching (currently exact-match only, TODO at line 86) to support finer-grained configs serving coarser AQEs via merge.
• sketch-bench cardinality sweep: add cardinality as a swept axis in BENCH_SWEEP.md; add CountMinSketchWithHeap wrapper (currently missing). Needed for real Error(a,g,θ_a) lookups and atomic cost values.
• Accuracy constraint + θ_a profiling: implement Error(a,g,θ_a) ≤ ε_a using analytic bounds (CMS ε-δ) and sketch-bench empirical lookup. Add profiling step to estimate cardinality/skew per AQE before optimizer runs.

Out of scope for v1

• Hard cluster resource budget constraints
• Workload drift / re-planning (static one-shot only)
• OneTemporalOneSpatial pipeline decomposition into two sharing stages
• Per-AQE weight vectors (global w₁..w₄ only)
• Binary-op evaluation cost

[milindsrivastava1997]

v1 Phase 1 and Phase 2 done in #407. Need to fix bugs: issues 411-423, and then implement Phase 3