Tracking: use sketch-bench rqe-optimizer MILP in asap-planner-rs

[milindsrivastava1997]

Goal

asap-planner-rs calls sketch-bench's rqe-optimizer MILP (minimize_cost) as a library instead of carrying its own optimizer. The planner converts its query workload into Raqes, passes facts, costs, scrape interval, allowed families and machine family, and converts the returned plan into StreamingConfig / InferenceConfig. A full refactor (moving the model into ASAPQuery) can come later.

sketch-bench side: ProjectASAP/sketch-bench#143

Supersedes the port plan in #753.

TODO

• A1. Dependency and build
  • Git dependency on ProjectASAP/sketch-bench rqe-optimizer, pinned rev (local [patch] for development).
  • HiGHS build deps (cmake, maybe clang) in asap-planner-rs/Dockerfile and CI.
• A2a. avg rewrite
  • Rewrite avg into sum / count items before building Raqes.
• A2b. Inputs → Raqe (refactor(planner): rename latency_sla to optional latency_sla_ms #797, feat(planner): build rqe-optimizer Raqes and facts from the workload config #798)
  • ControllerConfig query groups → items → Raqe.
  • Statistic → Capability mapping.
  • accuracy_sla → (accuracy_metric, accuracy_direction) per capability; latency_sla; lookback / interval in ms.
  • Error if a query has a spatial filter (for now).
  • Facts file reshaped: per metric (labels, arrival_rate_per_sec), cardinality per (metric, label set).
  • Cost table: keep the profile-selecting loader; use aqpbm_core::AtomicCostEntry and drop ASAPQuery's copy.
  • --ec2-pricing <snapshot.json> and --machine-family <name> for minimize_cost.
  • Pass scrape interval and the allowed-families list (families the engine can deploy).
• A3. Plan → StreamingConfig / InferenceConfig (fix(planner): bump rqe-optimizer to S8 and split Sum/Count/TopK capabilities #801, feat(planner): emit streaming and inference configs from the MILP plan #803)
  • Variant + sketch_config → AggregationType + params. Extend sketch_bench_key (asap-planner-rs/src/optimizer/atomic_costs.rs): it maps only CMS, HLL and KLL today. Add cms-heap-topk-fastpath-vector2d → CountMinSketchWithHeap, which sketch-bench's DEPLOYABLE_FAMILIES already plans (sketch-bench#148), plus the exact families (exact-sum → MultipleSum, exact-min/exact-max → MultipleMinMax with sub_type, exact-increase → MultipleIncrease).
  • Paired DeltaSet key aggregation where the plan flags a key tracker.
  • Direct (n = 1) / Merge{n}; retention from the deployment's retained instance count; cleanup; aggregation ids.
  • By default sketch-bench plans only its hardcoded DEPLOYABLE_FAMILIES (sketch-bench#148), and a plan variant without a mapping is an error. --allow-undeployable-families passes allow_undeployable_families: true to build_all_candidates, then prints the plan and $/h and writes no YAML.
• A3b. avg queries in InferenceConfig (later)
  • After A2a an avg query maps to two assignments (sum and count), but the translator pins each query to one aggregation_id. Decide how an avg query is emitted (engine has no Avg yet, Support Avg (and other multi-statistic aggregations) in query engine #463).
• A4. Disable the old optimizer
  • Comment out candidate_gen, cost_model, sketch_properties, constants, greedy (delete later).
• A5. Wire into asap-optimizer-cli (feat(planner): build rqe-optimizer Raqes and facts from the workload config #798, feat(planner): emit streaming and inference configs from the MILP plan #803: --milp, --output-dir, --allow-undeployable-families)
• A5′. asap-planner --planner legacy|milp (default legacy)
• A6. Housekeeping
  • Close or re-scope Optimizer: move sketch-bench #129 MILP into asap-planner-rs (--planner milp) #753 and its child issues.
  • As the engine gains DD / CountSketch / UnivMon: add the AggregationType and the variant mapping here, and the family to sketch-bench's DEPLOYABLE_FAMILIES, together.

Order and dependencies (both repos)

Labels: S1–S8 = sketch-bench ProjectASAP/sketch-bench#143 items in order (S1 Raqe model, S2 facts, S3 objective cleanup, S4a capabilities, S4b properties + key tracker, S5 cost rows, S6 candidate inputs, S7 retained memory, S8 plan output). A1–A6 = ASAPQuery #790 items (A1 dependency/build, A2a avg rewrite, A2b inputs → Raqe, A3 plan → configs, A4 disable old optimizer, A5 wiring, A6 housekeeping).

sketch-bench                                   ASAPQuery
S3 objective cleanup ──┐                       A1 dependency + HiGHS build (vs current main)
                       │                       A2a avg → sum/count rewrite
S1+S2 Raqe + facts ────┼─► S6 scrape / allowed families ─┐
S4a capabilities ──────┤                                 ├─► S8 plan output ─┐
S5 cost rows ──────────┴─► S4b properties + key tracker ─┘                   │
                               + S7 retained memory                          ▼
                                        A2b inputs → Raqe ◄── S1, S2, S4a, S6
                                        A3 plan → configs ◄── S8
                                        A4+A5 disable old + wire CLI ◄── A2b, A3
                                        A5' asap-planner --planner milp
                                        A6 housekeeping (any time)

Phase	Work	Depends on
0 (now, parallel)	S3; S4a (commit first: S1/S4b conflict with it); S5; A1 (via [patch] path dep); A2a	—
1	S1+S2 (one PR), then S6	S3, S4a
2	S4b+S7 (one PR: same per-deployment memory/CPU formulas)	S4a, S5, S1
3	S8 plan output → pin sketch-bench rev in ASAPQuery	S4b, S7, S6
4	A2b and A3 in parallel; then A4+A5 (one PR, keeps CLI runnable); then A5′ --planner milp	S1, S2, S4a, S6 / S8
any	A6 housekeeping	—

Critical path: S1+S2 → S4b+S7 → S8 → A3 → A4+A5. Pin the sketch-bench rev only after S8; until then ASAPQuery uses a [patch] path dependency.

Sessions (for agents)

If you are an agent told "you are session X": find your row, check that the PRs for everything in Needs are merged (gh pr list --state merged, and the ticked boxes above), read the merged PRs' descriptions for interface changes, then do Items. Don't edit files belonging to other sessions' items.

Session	Phase	Start in	Items	Needs
0a	0	sketch-bench	finish + merge sketch-bench#144 (S4a), then S3	—
0b	0	sketch-bench	S5 remainder: run the export, DeltaSet benchmark, HydraKLL benchmark (benchmark part of sketch-bench#142)	—
0c	0	ASAPQuery	A1, A2a, A6	—
1a	1	parent dir with both repos	S1+S2, then S6	0a
2a	2	sketch-bench	S4b+S7 (includes the cost-model part of sketch-bench#142)	1a, 0b
2b	2	ASAPQuery, [patch] path dep on local sketch-bench	A2b	1a, 0c
3a	3	parent dir with both repos	S8 + A3, then pin the sketch-bench rev in ASAPQuery	2a, 2b
4a	4	ASAPQuery	A4+A5, then A5′ (--planner legacy|milp)	3a

Done means: tests and clippy pass; one PR per item group; Conventional Commit title; tick the item here; describe any interface change later sessions depend on in the PR description. Use a git worktree per session. Follow ASAPQuery AGENTS.md. Never git commit --amend after a failed pre-commit hook; re-run the commit.

Decisions (don't revisit)

• ASAPQuery calls sketch-bench's rqe-optimizer as a library: git dependency pinned to a rev (pin after S8); [patch] path dependency during development.
• Objective: minimize_cost (EC2 machine family) only; minimize_tco and the peak-memory bound are removed.
• The Freq capability was removed on purpose. CMS/CountSketch appear only as top-k heaps.
• Subtract is deferred: query methods are Direct (L == x) and Merge only.
• Spatial filters: ASAPQuery errors on them for now; sharing across filters is later.
• Arrival rate is an explicit per-metric input (not derived from cardinality). Units are milliseconds.
• x and y must be multiples of the scrape interval (sketch-bench input).
• Families the engine can't deploy are excluded by sketch-bench's hardcoded DEPLOYABLE_FAMILIES (not a caller input; sketch-bench#148). --allow-undeployable-families lifts the filter: it prints the plan and $/h and writes no YAML.
• Exact families report their accuracy metrics as 0.
• Accuracy: ASAPQuery maps accuracy_sla to one (accuracy_metric, accuracy_direction) per capability; families within a capability share metric names.
• Every family has properties: mergeable, subtractable, subpopulation-aware, needs key tracker. Non-mergeable → only L == x. HydraKLL needs a DeltaSet key tracker, costed in the MILP.
• Merged instance count n = L/x is per Raqe (query CPU, Direct/Merge, read counts). Retained instance count is per deployment: open x/y plus closed (L−x)/y + 1 for the longest L it serves (memory cost, store retention).
• ASAPQuery's old optimizer modules (candidate_gen, cost_model, sketch_properties, constants, greedy) are commented out, not deleted, for now.

🤖 Generated with Claude Code

[milindsrivastava1997]

Session 2b (A2b) design decisions

Settled before implementing A2b. Items marked ⚠ differ from the issue text above.

#	Decision
1 ⚠	No [patch] path dep: cargo update -p rqe-optimizer to sketch-bench main (43d604f, has #145/#148).
2 ⚠	sketch-bench has no minimize_cost / EC2 pricing any more; the objective is Objective::AUCCost { w_cpu, w_mem }. A2b adds --w-cpu / --w-mem instead of --ec2-pricing / --machine-family.
3	A merged optimizer item with occurrence count > 1 becomes that many identical Raqes (ids "{leaf}#{k}"), since Raqe has no frequency weight and query CPU is charged once per Raqe per interval.
4	Statistic → Capability: Sum/Count→SumOrCount, Rate/Increase→RateOrIncrease, Min→Min, Max→Max, Quantile, Cardinality, Topk→TopK.
5	accuracy_sla is required accuracy (e.g. 0.99). Exact families and Cardinality: relative_error ≤ 1 − sla; Quantile: max_rank_err ≤ 1 − sla; TopK: precision_at_k ≥ sla.
6	latency_sla → latency_sla_ms (optional; missing = no limit). ControllerOptions gets deny_unknown_fields so old configs fail loudly; test configs, sample and asap-tools generators updated.
7	Only non-empty spatial filters are rejected.
8	New facts file (new loader; old label_set_facts stays for greedy until A4): metrics: [{metric, groups: [{labels, cardinality}]}]. Series count = the all-labels entry. Labels come from the workload metrics: hints, scrape interval from the CLI.
9	TopK Raqe.grouping_labels = topk_by_labels ({} for bare topk), not the all-labels output set. k and topk_count_events are not modeled.
10 ⚠	AtomicCostEntry is re-exported from rqe_optimizer. The MILP path reads the flat-array export (out/rqe_atomic_costs.json) directly; the profile-selecting loader stays only for greedy.
11	asap-optimizer-cli --milp builds Raqes + facts, runs build_all_candidates + milp::minimize, and prints the plan and cost. No YAML (A3). A4+A5 makes it the default.

[milindsrivastava1997]

Session 2b PRs: #797 (rename latency_sla → optional latency_sla_ms), then #798 (A2b, stacked on #797). Interface notes for 3a/4a are in #798's description. Decisions are as in the comment above, plus: accuracy_sla is required accuracy (error ≤ 1 − sla; TopK precision ≥ sla), and the MILP CLI reads the flat cost export via --atomic-costs.

[milindsrivastava1997]

Blocker for A3 / avg queries: sketch-bench's SumOrCount lets one exact-sum deployment serve both the sum and the count from the avg rewrite (found in review of #798). Fix tracked in ProjectASAP/sketch-bench#161 (split into Sum and Count; also adds deny_unknown_fields to AtomicCostEntry). Bump the rqe-optimizer rev after it lands.

[milindsrivastava1997]

A4 deletes the old optimizer instead of commenting it out: candidate_gen, cost_model, greedy, sketch_properties, constants, translator, label_set_facts, pipeline, the profile-selecting cost loader, and candidate-gen-dump. Git history keeps them. asap-optimizer-cli is now MILP-only. PR: #807. A5′ (asap-planner --planner legacy|milp) will be stacked on it.