Candidate generation ignores saturation: deployments whose instances never reach N_sat are planned #156

Problem

rqe-optimizer's candidate generation ignores the saturation study (#133, #140). A (family, config, x, y) deployment becomes a candidate whether or not its instances receive enough items to reach that config's saturation point.

The cost table's accuracy values are measured on one instance with 1,000,000 items (#147). The saturation study shows that below the saturation point, error still changes with N, so the measured value doesn't hold there. In a real deployment, each window instance gets about one window's items per group (arrival rate × window ÷ number of groups), which is often far fewer. The MILP can then pick a deployment whose accuracy is based on a value that doesn't apply to it, and the accuracy SLA check passes when it shouldn't.

Some points never saturate in the grid at all: many distinct keys with zipf skew ≤ 0.5 for CMS, CountSketch and top-k (#140: 35 of 240 points with ≥ 1e4 distinct keys are still changing at N = 1e8). For these, the measured saturation point is only a lower bound.

Where saturation is used today

• scripts/export_autosketch_eval_table.py (Export the AutoSketch vs ASAP evaluation table from saturation curves #136) computes saturated = max_N ≥ n_sat. rqe-optimizer/data/autosketch-eval/README.md notes that ASAP "may only use a config's value when this is true". That table only feeds the Synthetic workload results: reproduction steps and ASAP's profiling time #141 evaluation.
• scripts/recommend_config.py flags configs that are "not saturated".
• Neither rqe-optimizer/src nor the cost export (scripts/export_rqe_optimizer_costs.sh) reads saturation.csv or n_sat.

Not covered elsewhere

• Tracking: make rqe-optimizer the solver for ASAPQuery's planner #143 S6 / refactor(rqe-optimizer): Raqe input model in ms, spatial filter, per-RAQE latency SLA, deployable families #148 limit candidates to DEPLOYABLE_FAMILIES. That is about what the engine can run, not about saturation.
• rqe-optimizer: per-phase cost model, workload facts, weighted AUCCost objective #145 requires x and y to be multiples of the scrape interval. It adds no saturation condition.
• Tracking: make the rqe-optimizer cost export fit the per-phase cost model #147 lists "items inserted per instance" as a condition the model can't see, but treats it as something that shifts accuracy and cost, not as a reason to exclude a candidate.

Related: #143, #145, #147, #133, #140, #136.

Design decisions (Q&A)

Reference: ASAPQuery docs/evaluation/autosketch-vs-planner.md, "ASAPQuery: saturated values, because it merges".

Inputs: out_grid_1e7_cost/{saturation,saturation_curve}.csv and out_1e9/{saturation,saturation_curve}.csv, copied from clnode109 /mydata/sketch-bench-results/from-node0/saturation/. SHA-256 matches the values recorded in rqe-optimizer/data/autosketch-eval/README.md.

Q1. Which N do we compare against the saturation point?

Example: an RAQE asks for a quantile over the last 1 hour (lookback 1h), per group. A candidate deployment builds a sketch every 1 minute (window 1m) and answers by merging 60 of them. Each group gets 1,000 items/minute, and the config's saturation point is 10,000 items. Each 1-minute sketch holds 1,000 items (below the saturation point); the merged answer covers 60,000 (above the saturation point). Is this deployment allowed for this RAQE?

• (A) Yes: check the merged total (60,000). For CMS, CountSketch, HLL and DDSketch, merging 60 small sketches gives exactly the same sketch as one over all 60,000 items. This is what the ASAPQuery doc says. The same deployment could be allowed for a 1-hour query and rejected for a 2-minute query.
• (B) No: check each 1-minute sketch (1,000). A deployment is rejected whenever its panes are too small, whatever query it serves. This is what this issue originally said.

Answer: A.

Q2. What about KLL and top-k, which lose accuracy when merged?

KLL and top-k: the merged result is worse than one sketch built over the same items. #131: KLL error rises 1.0–1.3× when panes are saturated and up to 3–4× when panes are small; top-k loses up to 40% precision at large K. The cost table's accuracy comes from a single un-merged sketch.

• (A) Treat them like the other four. Check only the merged total; ignore the merge penalty.
• (B) Also require every pane to be saturated. Removes the 3–4× small-pane case; the remaining ≤1.3× / ≤40% penalty is left for a follow-up.
• (C) Use the merged accuracy curves from Measure accuracy after merging m shards #131. Most accurate, but the data isn't in the repo yet, covers only up to 64 merged windows, and replaces the accuracy value rather than filtering.

Answer: B now, C as a follow-up (#158).

Amended 2026-10-07 (#171): no pane check. KLL and top-k read the curve at the lookback's item count (after merging), like every other sketch; the merge penalty stays #158.

Q3. Where does each config's saturation point come from?

the saturation point depends on the data (zipf skew and distinct keys for CMS/top-k/CountSketch/HLL; tail index for KLL/DDSketch). WorkloadFacts only has arrival rate and group counts. Taking the worst case across the grid, almost every CMS, CountSketch, HLL and KLL config has a data shape that never saturates, even at 1e9.

• (A) Add data parameters per metric (zipf skew, distinct keys, tail index), fit from the dataset, and look up the saturation point at that point.
• (B) Use the point the cost table was measured at (zipf skew 1.1, distinct keys 1e5).
• (C) Worst case over the grid. Rejects almost everything.

Answer: A.

Q4. Many cost-table configs have no saturation-curve row. What do we do with them?

Matched: HLL lg_k 12/14, KLL k=200, DDSketch α 0.01/0.02. Missing: KLL k=500; CMS-heap top-k cols=2048; CountSketch-heap top-k; UnivMon; HydraKLL. Exact accumulators have no error.

• (A) Change the cost export to use grid configs (KLL 500 → 800, cols 2048 → 1024/4096). Families the grid never studied are not eligible. Exact rows are always allowed.
• (B) Keep the cost table and borrow the saturation point from a neighbouring grid config.
• (C) Allow configs that have no row.

Answer: A. A sketch config with no row is never eligible. (All of DEPLOYABLE_FAMILIES have grid rows under A.)

Q5. What about points that never saturate?

• (A) Never eligible.
• (B) Use the largest measured N as the saturation point (a lower bound).
• (C) Allow it, but flag it in the output.

Answer: superseded by Q5b (the lookup design reads the curve at the lookback's item count, so these points no longer need special handling).

Q5b. Filter or lookup?

Proposed rule under discussion: "if you don't have sketches to merge, you don't need to know the saturation point N; if you have sketches to merge, use the largest window's N and get the parameter." Both readings use N = the lookback's item count. They differ in what we do with it:

• (A) Filter: allow the deployment only if the lookback's item count ≥ the saturation point, and use the cost table's plateau value. Needs only saturation.csv.
• (B) Lookup: accuracy = the curve's error at the lookback's item count. No saturation point needed; never-saturating points work while the lookback's item count ≤ the largest measured N. Replaces the cost table's accuracy column. Needs saturation_curve.csv.

Answer: B.

Q6. How do we read the error at the lookback's item count when it doesn't land exactly on a checkpoint?

Checkpoints are 4 per decade (1000, 1778, 3162, …). Error doesn't always move the same way with N (CMS ARE rises, KLL error falls).

1. Between checkpoints: take the worse of the two neighbouring errors.
2. Below 1,000: not eligible.
3. Above the largest measured N: the error at the largest N if the point saturated; otherwise not eligible.

Alternative offered: linear interpolation in log N for case 1.

Answer: OK (1–3 as proposed).

Q7. What do zipf skew and distinct keys mean for a real Prometheus metric?

Items per group: the lookback's item count = series in the group × scrapes per lookback, from WorkloadFacts. Distinct keys per group, on average, are the series per group, but the worst group may be much larger. Zipf skew: if each series is inserted once per scrape with weight 1, the skew is 0; if weighted by sample value, it is the skew of values across series.

Proposed: one per-(metric, grouping) input, data_shape (zipf skew, distinct keys, tail index), fit from the dataset as the worst case over windows and groups; the lookback's item count from existing facts.

1. Does the engine insert CMS-heap with weight = sample value, or once per sample?
2. Is a fitted data_shape input acceptable?

Answer: the engine can do either; add the fitted data_shape input. zipf skew describes whichever insertion mode the engine uses; the planner doesn't choose the mode.

Q8. What happens when data_shape falls between grid points?

Grid: zipf skew ∈ {0, 0.5, 0.8, 1.0, 1.2, 1.5, 2.0}; distinct keys ∈ {1e3, 1e5, 1e7}; tail index ∈ {1.1, 1.5, 2.0, 3.0}.

• Between grid points: read the error at every bracketing grid point (each at the lookback's item count using Q6) and take the worst.
• Outside the grid (distinct keys > 1e7, zipf skew > 2.0, tail index < 1.1 or > 3.0): not eligible.

Answer: OK.

Q9. Which accuracy metric?

Each sketch's curve records one metric: CMS and CountSketch are_top100; CMS-heap top-k precision_at_k; KLL mean_rank_err; HLL relative_error. DDSketch: value relative error (|estimate − true quantile| / |true quantile| on the 101-point quantile grid), not mean_rank_err. DDSketch's guarantee is on value error; its rank error is ≈ α·a/2 and depends on the tail index.

• Sketch rows: accuracy comes only from the curves. If the RAQE's accuracy_metric isn't that sketch's curve metric, the deployment is not eligible.
• Exact rows: keep the cost table's value (0 error).
• Drop query_accuracy from sketch rows in the cost table.

Answer: OK, with DDSketch on value relative error (amended 2026-10-06).

Follow-up work this implies:

• aqpbm-core/src/accuracy/quantile.rs has only RankErrorGT; add a DDSketch-only relative-value-error comparator reporting mean_relative_value_error (no max field; see Report mean_relative_error for DDSketch (paper's relative-accuracy metric) #162 scope decisions).
• scripts/study_saturation.py runs dd with rank-error / mean_rank_err; switch it and re-run the dd saturation points (out_grid_1e7_cost, out_1e9).
• Tracked in Report mean_relative_error for DDSketch (paper's relative-accuracy metric) #162, implemented in Report DDSketch relative value error #164. Until the dd points are re-run, the local CSVs still carry mean_rank_err for dd, so DDSketch rows fail the metric check above; the optimizer reads the metric from the CSV's error_metric column, so no code change is needed when the regenerated CSVs land.

Q10. How does the optimizer get the curves?

• (A) The optimizer reads the four raw CSVs from one input directory (--saturation-dir containing out_grid_1e7_cost/ and out_1e9/); the 1e9 data wins; parsed in Rust.
• (B) A Python script merges them into one JSON that the optimizer reads.

Answer: A.

Q11. How does the KLL/top-k rule from Q2 fit the lookup design?

• no merging (window = lookback): read the error at the lookback's item count. No saturation check.
• merging: each pane must be saturated: each window's item count ≥ the saturation point at all Q8 bracketing grid points; then read the error at the lookback's item count. A never-saturating point is not eligible when merging.

Answer: OK.

Amended 2026-10-07 (#171): the per-window check when merging is dropped; the curve is read at the lookback's item count whatever the window size.

Q12. Should AutoSketch-Adapted use the same lookup?

autosketch::search takes an accuracy oracle. The ASAP doc says AutoSketch reads the measured value at its own input size, the lookback's item count. Proposed: callers pass a closure that calls the same curve lookup at the lookback's item count with no merging; autosketch.rs itself stays unchanged.

Answer: OK.

Open

• The cost table's CPU and memory are still measured at zipf skew 1.1, distinct keys 1e5, not at data_shape. Proposed out of scope (per-item costs are roughly flat in N).
• Q4 requires re-running scripts/export_rqe_optimizer_costs.sh after the config change.
• Q9 / DDSketch below 1,000 items: asap_sketchlib's DDSketch has no bucket cap, so value relative error should be ≤ α at every N; the curve is expected to be flat from the first checkpoint. Should Q6.2 (below 1,000: not eligible) still apply to DDSketch?
• Q9 / tail index: with DDSketch on value error, nothing may depend on a (KLL rank error is reported independent of a, docs/saturation_study.md). If saturation_curve.csv confirms it for KLL, data_shape in Q7/Q8 can drop a.
• Q9 / KLL vs DDSketch: with one metric per sketch, a quantile RAQE gets only KLL (rank error) or only DDSketch (value error); they never compete. Option: allow several curve metrics per sketch and keep DDSketch's existing mean_rank_err curve alongside value error.
• Q11 / which group: each window's item count uses the average series per group, while Q7 fits data_shape as the worst group. Use the smallest group's series count instead?
• Q4 / HydraKLL, UnivMon: with no grid rows they are never eligible. Confirm this is intended.