Tracking: make rqe-optimizer the solver for ASAPQuery's planner #143

Goal

Make rqe-optimizer's MILP the solver behind ASAPQuery's asap-planner-rs. ASAPQuery calls it as a library (git dependency, pinned rev), converts its query workload into Raqes, and converts the returned plan into StreamingConfig / InferenceConfig. ASAPQuery side: see the linked ASAPQuery tracker.

Out of scope for this round: Subtract query method (follow-up), spatial-filter sharing (ASAPQuery errors on spatial filters for now), memory bounds.

TODO

• S1. Raqe input model
  • Rename Rqe → Raqe with fields: id, capability, metric, grouping_labels, spatial_filter, lookback_ms, interval_ms, accuracy_metric, accuracy_sla, accuracy_direction, latency_sla.
  • Latency limit moves from MilpBounds into Raqe.
  • Units: milliseconds instead of whole seconds.
  • Stream identity for eligibility and sharing = (metric, spatial filter, grouping labels).
• S2. Workload facts input (replaces LabelSetInfo) (sketch-bench#145)
  • Per metric: full label list and arrival_rate_per_sec.
  • Cardinality per (metric, label set); input/output cardinality of a Raqe come from this.
• S3. Objective cleanup (sketch-bench#145)
  • Keep only minimize_cost (EC2 machine family); remove minimize_tco.
  • Remove the peak query-memory bound.
• S4a. Capabilities and families (sketch-bench#144)
  • Capabilities: SumOrCount, MinOrMax, RateOrIncrease, Quantile (+ HydraKLL), Cardinality, TopK. Freq removed.
• S4b. Family properties and key tracker (includes the cost-model part of sketch-bench#142)
  • Per-family property table: mergeable, subtractable, subpopulation-aware, needs key tracker.
  • Non-mergeable families eligible only when L == x.
  • Subpopulation-aware families: one instance, not × cardinality, in CPU and memory.
  • Key tracker: deployments of families that need one also pay a DeltaSet's ingest CPU and retained memory (∝ output cardinality); the plan flags it.
• S5. Cost rows
  • Exact families' accuracy: already in place. The aggregate comparator (rqe-optimizer: exact sum/min-max/increase accumulators, CountSketch+heap and UnivMon top-k #144) measures relative_error / relative_error_mean against per-group truth, so exact rows report ≈0. No work.
  • HydraKLL: benchmark exists (hydra-kll lib + polars, rows in aqpbm-cli/src/rows/hydra.rs, comparator subpop-rank-error reporting mean_rank_err / max_rank_err, the same names as KLL/DD). To do: add a hydra-kll entry (or a point_hydra helper) to scripts/export_rqe_optimizer_costs.sh with grouped datagen (configs/datagen/hydra_columns.yaml), comparator subpop-rank-error, and a small param grid. If rqe-optimizer: support shared multi-subpopulation sketches (HydraKLL) in the cost model #142 needs accuracy at several cardinalities (fixed-size Hydra degrades as groups grow), measure those points here.
  • DeltaSet: no code exists yet. To do:
    • wrapper mirroring ASAPQuery's DeltaSetAggregator (key set per window, added/removed keys), registered like the exact-* variants;
    • aqpbm-cli row for insert / merge / query costs;
    • memory normalized per key, the same way rqe-optimizer: exact sum/min-max/increase accumulators, CountSketch+heap and UnivMon top-k #144 normalizes exact types per group in aqpbm-core/src/atomic_costs.rs;
    • a trivial exact comparator (keys found vs true keys, ≈0 error), since reduce_one requires query_accuracy.
  • Run the export (scripts/export_rqe_optimizer_costs.sh; not yet run since rqe-optimizer: exact sum/min-max/increase accumulators, CountSketch+heap and UnivMon top-k #144), check reduce_all's skipped rows, and publish the JSON where ASAPQuery reads it.
• S6. Candidate generation inputs
  • scrape_interval_ms: candidate x and y must be multiples.
  • Allowed families: only listed variants become candidates.
• S7. Retained memory (sketch-bench#145)
  • Closed windows (L − x)/y + 1 plus open x/y (today: (x + L)/y).
• S8. Plan output (sketch-bench#168)
  • Per deployment: variant, sketch_config, metric, grouping_labels, x, y, key tracker, retained instance count (max over the Raqes it serves).
  • Per Raqe: deployment index, merged instance count n = L/x.
  • Objectives including $/h.

Follow-ups

• S9 (follow-up). Subtract query method (needs subtract_cpu_secs; asap_sketchlib has no subtract yet).

Order and dependencies (both repos)

Labels: S1–S8 = 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 ProjectASAP/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)

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.

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 via an allowed-families input; --allow-undeployable-families prints the plan and $/h without writing 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