Optimizer: move sketch-bench #129 MILP into asap-planner-rs (--planner milp)

[milindsrivastava1997]

Summary

sketch-bench PR #129 (rqe-optimizer) adds a HiGHS-backed MILP that picks sketch deployments (family, params, window, slide) for a repeating-query workload and shares deployments across compatible queries. Its output is meant to feed ASAPQuery's planner, so the solver should live in asap-planner-rs as mip_assign. That fills the Phase 3a slot in .design_docs/optimizer-v1-implementation-plan.md and closes the cross-AQE sharing gap (#650).

Goal

A production planner path, asap-planner --planner legacy|milp (default legacy), that solves the sharing-aware MILP over ASAPQuery's own candidates and cost model and emits deployable streaming_config.yaml / inference_config.yaml.

PR order

#	PR	Issues	Notes
1	Retention fix	#760	Standalone asap_types + translator bug. First: legacy already dedups configs across queries, so last-ref-wins may bite today.
2	Optimizer items + window rules	#755 + #758	Same code (AQE struct, extract_aqes, window_candidates); T % S needs per-item T. Base for the rest.
3	Label-set facts	#756	Independent of 2; can run in parallel.
4	SLA filters	#757	Needs 2 (items carry SLAs).
5	avg rewrite + remove EXACT	#419 + #759	One PR: removing EXACT alone makes every avg unservable.
6	Sketch families	#762 + #763	Both change the candidate family set; #763 is tiny.
7	Subtract cost	#765	After 2 (T ≠ W possible); before the MILP (objective depends on it).
8	Candidate dump + diff vs sketch-bench #129	#767	After 2, 4, 5, 6 so remaining diffs are real bugs.
9	MILP	#761 (+ #768 results in PR description)
10	Planner integration	#764	Last code PR.
—	Docs	#769	After 9.

• Parallel, any time: atomic-costs export: merge rqe-optimizer grid, add CountSketch+heap top-k, settle CMS-heap variant sketch-bench#132. Only 4 and 6 need its data; both can start with CMS/HLL/KLL.
• Not PRs yet: Optimizer: accuracy after merging n windows is unvalidated #766 (research), Optimizer MILP: explore memory as a hard bound instead of a weighted cost term #750 (exploration).
• Caveat on 5: a rewritten avg references two aggregations; the engine doesn't support Avg yet (Support Avg (and other multi-statistic aggregations) in query engine #463), so in production those queries fall back to Prometheus until Support Avg (and other multi-statistic aggregations) in query engine #463 lands.

#760 ─────────────────────────────────────────┐
#755+#758 ─┬─ #757 ─┐                         │
           ├─ #765  ├─ #767 ── #761(+#768) ── #764 ── #769
#756 ──────┤        │
#419+#759 ─┤        │
#762+#763 ─┘────────┘
sketch-bench#132 ──┘ (feeds #757/#762 data)

Related

#650, #649, #652, #750, #526, #525, #563, #533; sketch-bench #129

🤖 Generated with Claude Code

---

Tracking

Design decisions: first comment below (kept in sync with the issues listed here).

Cost data

• atomic-costs export: merge rqe-optimizer grid, add CountSketch+heap top-k, settle CMS-heap variant sketch-bench#132 atomic-costs export: merge rqe-optimizer grid, CountSketch+heap, CMS-heap variant

Model changes (before the MILP)

• Optimizer: assignment unit = (AQE, repeat interval, accuracy_sla, latency_sla) #755 Assignment unit = (AQE, T, accuracy_sla, latency_sla)
• Optimizer: accept externally provided label-set facts (series count, cardinality) #756 External label-set facts (series count, cardinality)
• Optimizer: enforce accuracy_sla and latency_sla in candidate eligibility #757 Enforce accuracy_sla / latency_sla in eligibility
• Optimizer: window compatibility = lookback%W, T%S, W%S per item #758 Window compatibility = lookback%W, T%S, W%S
• Optimizer: remove EXACT candidate; error on unservable items #759 Remove EXACT; error on unservable items
• planner/optimizer: decide support for multi-statistic AQEs (e.g. avg) #419 Rewrite avg → sum/count
• Add optimizer aggregation families and capability/SLA metadata #762 Add DDSketch, CountSketch(+heap), UnivMon to AggregationType
• Optimizer: HLL as the only cardinality candidate (drop Set/DeltaSet as cardinality values) #763 HLL as the only cardinality candidate
• Retention: take max across shared aggregation refs; sliding depth (n-1)*W/S+1 #760 Retention: max across shared refs; sliding depth

Verification before the MILP

• Optimizer: print candidates for a workload and diff against sketch-bench #129 #767 Print candidates for a workload and diff against sketch-bench Re-organize code in repo to be more OSS friendly #129

MILP

• Optimizer: mip_assign (good_lp + HiGHS) and asap-optimizer-cli --solver greedy|mip #761 mip_assign (good_lp + HiGHS) + asap-optimizer-cli --solver
• Optimizer: compare mip_assign against sketch-bench #129 MILP (one-off script) #768 Compare mip_assign against sketch-bench Re-organize code in repo to be more OSS friendly #129 (one-off)
• asap-planner: --planner legacy|milp integration #764 asap-planner --planner legacy|milp integration

Docs

• Docs: update optimizer-mip-formulation.md for the implemented MILP #769 Update optimizer-mip-formulation.md (with docs(optimizer): reconcile optimization and sketch-bench formulations #652)

Known model limitations / follow-ups

• Optimizer cost model: Subtract cost assumes T = W #765 Subtract cost assumes T = W
• Optimizer: accuracy after merging n windows is unvalidated #766 Accuracy after merging n windows unvalidated
• Optimizer MILP: explore memory as a hard bound instead of a weighted cost term #750 Memory as hard bounds instead of a cost term
• labels_compatible() is exact-match only, not superset matching #649 Label superset matching

[milindsrivastava1997]

Design decisions (revised)

Revised after follow-up scoping; each row links the issue that implements it.

Topic	Decision	Issue
Purpose	Production path behind --planner legacy|milp; default stays legacy. Greedy remains an asap-optimizer-cli baseline.	#764
Assignment unit	Item = (AQE, repeat interval T, accuracy_sla, latency_sla). RQEs agreeing on all four merge with frequency = count / T; no collapsing into Σ1/T / t_repeat_gcd across differing T or SLAs.	#755
Inputs	--atomic-costs, --atomic-cost-workload, and an externally provided label-set facts file: series_count per (metric, spatial filter) and cardinality per (metric, spatial filter, grouping labels); arrival rate derived as series_count / scrape_interval. Label schema from the workload's metrics: hints. Replaces --dataset / --rho / SUBPOPULATION_COUNT. Missing facts → error. Cardinality scales cost per sketch class (per-group, unbounded keyed Multiple*, bounded keyed CMS/HydraKLL); trivial accumulators use an analytical per-key memory estimate.	#756
Query languages	PromQL only. --planner milp with sql/elastic is an argument error.	#764
Legacy knobs	windowing, sketch_parameters, non-zero range_duration_ms/step_ms → error. aggregate_cleanup → honored. enable_punting, existing_*_config → ignored.	#764
Capability / labels	Reuse the engine's asap_types::capability_matching (exact labels; unfiltered config serves filtered queries). Label superset matching stays separate.	#649
Window compatibility	Config (W, S) serves item (lookback L, T) iff L % W == 0, T % S == 0, W % S == 0 (tumbling: S = W). Same as #129's is_eligible. Replaces the doc's FRESHt/FRESHs bounds.	#758
Candidate pool	ASAPQuery's enumerate_candidates, per item, unioned and deduplicated by config. Dominance pruning (from #129) later if solve time requires it.	#761
Accuracy	Eligibility filter: measured query_accuracy[metric(family)] vs accuracy_sla, via a fixed per-family metric table (CMS → relative_error_mean, KLL → mean_rank_err, HLL → relative_error, CMS-heap → 1 − recall_at_k, ...). 0.0 = unconstrained; missing measurement = ineligible; exact accumulators pass.	#757
Latency	Eligibility filter: estimated query CPU seconds ≤ latency_sla (seconds). 0.0 = unconstrained.	#757
EXACT	Removed. Every item must be served by a deployed config. An item with no eligible candidate → planner errors before solving, listing unservable items.	#759
Multi-statistic AQEs	Rewrite avg into sum / count AQEs (divide at query time).	#419
Objective	ASAPQuery's weighted cost_model: Σ u[g]·ingest_cost(g) + Σ z[i,g]·freq_i·query_cost(i,g). No peak-memory variable. Alternative (CPU-only + memory as hard bounds) explored separately.	#761, #750
MILP structure	Binary z[i,g], u[g]; Σ_g z[i,g] = 1, z ≤ u, u ≤ Σ_i z[i,g].	#761
Solver	good_lp + HiGHS. Add cmake (and clang if needed) to Dockerfile and CI. No cargo feature gate.	#761, #764
Time limit	--milp-time-limit-secs (default ~60): on timeout use the best incumbent and log the gap; no incumbent → error. No fallback to greedy/legacy.	#761
Output	Map OptimizerSolution → IntermediateAggConfig + query refs; reuse the legacy YAML writer (build_aggregation_entry, build_queries_yaml). Typed to_yaml deferred.	#764
Retention	Shared aggregation retains the max num_aggregates_to_retain across query refs (today: last one wins). Sliding Merge retains (n−1)·W/S + 1.	#760
Sketch families	Add DDSketch, CountSketch (+heap for top-k), UnivMon to AggregationType; engine returns "unsupported"; optimizer considers them only with --milp-allow-unsupported-sketches (default off).	#762
Cardinality	HLL is the only cardinality candidate in the optimizer; Set/DeltaSet dropped as cardinality values (planner-side only). DeltaSet stays as the key aggregator.	#763
Cost data	Merge #129's grid into sketch-bench export_atomic_costs.sh (one document, one profile); add CountSketch+heap top-k; settle CMS-heap fastpath vs regularpath from engine code.	sketch-bench#132
sketch-bench #129	Stays open as the reference implementation until ASAPQuery's behavior is verified against it.	—
Verification	(1) Before the MILP: print candidates for the same workload on both sides and diff. (2) After: one-off comparison of mip_assign vs #129, including the query-memory definition difference. PR 3 also tests mip_cost ≤ greedy_cost under identical weights.	#767, #768
Docs	Update optimizer-mip-formulation.md to the implemented MILP, coordinated with #652; fold this file in.	#769

Delivery order

1. sketch-bench#132 (cost export)
2. Model changes: Optimizer: assignment unit = (AQE, repeat interval, accuracy_sla, latency_sla) #755, Optimizer: accept externally provided label-set facts (series count, cardinality) #756, Optimizer: enforce accuracy_sla and latency_sla in candidate eligibility #757, Optimizer: window compatibility = lookback%W, T%S, W%S per item #758, Optimizer: remove EXACT candidate; error on unservable items #759, planner/optimizer: decide support for multi-statistic AQEs (e.g. avg) #419, Add optimizer aggregation families and capability/SLA metadata #762, Optimizer: HLL as the only cardinality candidate (drop Set/DeltaSet as cardinality values) #763, Retention: take max across shared aggregation refs; sliding depth (n-1)*W/S+1 #760
3. Optimizer: print candidates for a workload and diff against sketch-bench #129 #767 candidate diff vs Re-organize code in repo to be more OSS friendly #129
4. Optimizer: mip_assign (good_lp + HiGHS) and asap-optimizer-cli --solver greedy|mip #761 mip_assign + asap-optimizer-cli --solver greedy|mip, then Optimizer: compare mip_assign against sketch-bench #129 MILP (one-off script) #768
5. asap-planner: --planner legacy|milp integration #764 asap-planner integration
6. Docs: update optimizer-mip-formulation.md for the implemented MILP #769 docs

Known model limitations

• Optimizer cost model: Subtract cost assumes T = W #765 Subtract cost assumes T = W.
• Optimizer: accuracy after merging n windows is unvalidated #766 Accuracy after merging n windows is unvalidated; quantile rank error ≠ value error.
• Optimizer MILP: explore memory as a hard bound instead of a weighted cost term #750 Memory as hard bounds instead of a weighted cost term.
• labels_compatible() is exact-match only, not superset matching #649 Label superset matching.

References

• sketch-bench Re-organize code in repo to be more OSS friendly #129: rqe-optimizer/src/{milp,candidates,objectives}.rs, docs/rqe_sketch_deployment_v1.md
• No cross-AQE sharing — greedy deploys one sketch per AQE even when they could share #650 cross-AQE sharing, docs(optimizer): reconcile optimization and sketch-bench formulations #652 doc reconciliation, Optimizer: CMS accuracy constraint (ACC) using accuracy_sla #526 accuracy constraint, Support Avg (and other multi-statistic aggregations) in query engine #463 engine Avg, Planner reconfiguration ignores existing deployed configs, reassigns fresh aggregation IDs every run #533 stable aggregation ids
• .design_docs/optimizer-mip-formulation.md, .design_docs/optimizer-v1-implementation-plan.md

[milindsrivastava1997]

ASAPQuery optimizer vs sketch-bench rqe-optimizer: differences (as of 2026-10-05)

Compared: ASAPQuery main (after #776, #780; #781 and #786 still open) vs sketch-bench main (after #129, #131, #135, #137).

Inputs

	sketch-bench rqe-optimizer	ASAPQuery optimizer
Workload unit	Rqe {capability, labels, lookback_secs, interval_secs, accuracy_metric, accuracy_tolerance, accuracy_direction}, built by the caller (no query parser)	OptimizerItem {requirements (metric, statistics, range, grouping labels, spatial filter, topk), query_strings, query_frequency_hz = count/T, t_repeat_ms, accuracy_sla, latency_sla}, parsed from PromQL
Stream identity	label set only; no metric, no spatial filter	(metric, spatial filter, grouping labels)
Label-set facts	LabelSetInfo {cardinality, arrival_rate_per_sec} per label set	facts YAML: series_count per (metric, filter) + cardinality per (metric, filter, labels) → ItemFacts {output_group_count, topk_by_group_count, arrival_rate_per_sec}
Cost table	aqpbm_core::AtomicCostEntry directly; sketches named by sketch-bench variant string	copy of AtomicCostEntry in a versioned document with workload-profile selection; mapped to AggregationType + params via sketch_bench_key
Accuracy	per-RQE metric name + tolerance + direction	one accuracy_sla per item, metric chosen per family by the planner (#781)
Latency	optional per-RQE bound (MilpBounds)	latency_sla per item (#781)
Memory bound	optional peak query-memory bound	none
Pricing	optional MachineFamily (EC2 vCPU, GiB, $/h)	CostWeights (w_ingest_mem, w_ingest_cpu, w_query_mem, w_query_cpu)
Units	whole seconds	milliseconds, plus scrape-interval alignment

Candidates and constraints

	sketch-bench	ASAPQuery
Window rules	x%y, L%x, T%y	same three (#758), plus W and S multiples of the scrape interval; separate Tumbling/Sliding types; DeltaSet tumbling-only
Query method	always merge L/x instances	Direct / Merge / Subtract
Keyed sketches	no key tracker modeled	CMS-family candidates paired with a key aggregator (DeltaSet), costed via key_tracker_ingest_cost
Spatial filter sharing	n/a	unfiltered config can serve filtered queries
Families	CMS, CountSketch, KLL, DD, HLL, UnivMon, CMS-heap (fastpath)	Sum, Increase, MinMax (+ Multiple*), CMS, CMS-heap, KLL, HydraKLL, HLL, Set, DeltaSet
Multi-statistic (avg)	n/a	currently unservable (EXACT removed in #776; #419 open)
Unservable items	caller checks with enumerate::unservable	error listing unservable items
Dominance pruning	yes	no

Objective

	sketch-bench	ASAPQuery
minimize_tco / weighted	ingest CPU + query CPU + merge CPU (normalized by a reference plan)	w·ingest_mem + w·ingest_cpu + w·query_mem + w·query_cpu (+ key-tracker cost). #750 closed: memory stays in the objective
minimize_cost	$/h on one EC2 family: fractional instances n ≥ CPU/vCPU, n ≥ retained GiB / instance GiB	none
Ingest CPU	λ × (x/y) × insert	λ × ceil(W/S) × insert (same shape)
Query CPU	card × (query + (n−1)·merge) / T	same for Merge; Subtract = merge + subtract + query
Memory	peak query card × mem; retained card × mem × (x+L)/y, max over RQEs a deployment serves	active ingest n_concurrent × groups × mem; query n × groups × mem (Merge) / 2× (Subtract)

MILP

	sketch-bench	ASAPQuery
Solver	good_lp + HiGHS	none yet (greedy, no sharing)
Variables	z[i,d], u[d], plus retained-GiB per deployment and instances when pricing	—
Constraints	Σz = 1, z ≤ u, u ≤ Σz; latency/memory bounds fix z = 0; family: cpu/vCPU ≤ n, Σ retained GiB / GiB ≤ n, retained·z ≤ retained_gib[d]	—

Outputs

	sketch-bench	ASAPQuery
Plan	Mapping (deployment index per RQE) + Deployment list	OptimizerSolution: AggregationConfigs with ids, item → aggregation (+ key aggregation) refs, query method
Metrics	Objectives: CPU breakdown, peak query memory, retained memory, per-RQE latency; $/h via MachineFamily	estimated ingest / total cost rate
Deployable artifacts	none	StreamingConfig + InferenceConfig (cleanup: read-based, #786)
Baselines	brute force, Pareto, AutoSketch-adapted	greedy

🤖 Generated with Claude Code

[milindsrivastava1997]

Direction changed: instead of porting the MILP into ASAPQuery, asap-planner-rs will call sketch-bench's rqe-optimizer as a library. New plan: #790 (sketch-bench side: ProjectASAP/sketch-bench#143).