Repository navigation
rqe-optimizer: read accuracy at the largest group's sample count, not the average #189
Description
Motivating scenario
http_request_duration_seconds has 30,000 series across 5 services and 50 (service, endpoint) pairs, scraped every 15 s. A RAQE asks for p99 latency by service over 1 h, served by KLL.
The 50 endpoints are not spread evenly across the 5 services:
| service | endpoints | series |
|---|---|---|
| checkout | 46 | 27,600 |
| auth, search, cart, profile | 1 each | 600 each |
Today items_per_group (rqe-optimizer/src/saturation.rs) reads accuracy at the average group's sample count: 30,000 / 5 = 6,000 series → 1.44M samples per hour. checkout actually holds 27,600 series → 6.6M samples per hour, about 4.6× more. A fixed-size sketch's error grows with N, so the optimizer can accept a config that meets the SLA for the average service but misses it for checkout, the service people care about most.
MetricFacts carries only card(X) per label set, so the skew can't be expressed.
What to build
MetricFacts.largest_group_series: BTreeMap<LabelSet, u64>: series in the largest group of each label set. A missing label set means groups are taken as even (today's behavior).validate_facts: each key is also incardinality, andseries / card(X) <= value <= series.items_per_groupuses the largest group's series when known, else the average. This matchesDataShape, which is already fitted as the worst case over groups.- Fill the field in
examples/small_problem.rswith a skewed{service}entry.
Out of scope
- DD memory (
instance_memory_bytes) stays at the average: it is a total over groups, so the worst group is the wrong number there. - Per-group size histograms: considered and rejected as too complex for now. The worst group covers SLAs of the form "every group meets the SLA", which is what
relative_erroralready means.
Assumption
The largest group is the worst one. That holds when error doesn't fall as N grows, which is true for KLL, DD and HLL outside HLL's small-N regime.
Interface change
ASAPQuery builds MetricFacts literals, so it must add the field (an empty map keeps today's behavior) until it computes the value from its label index.
Acceptance criteria
-
validate_factsrejects out-of-range and unknown-label-set entries. - A test shows a skewed grouping reads accuracy at the larger N, and can reject a config the average would accept.
- Omitting the field leaves every existing plan unchanged.
Related
- rqe-optimizer: let mergeable finer-group deployments serve coarser RAQEs #187 reads roll-up accuracy through the same
items_per_group.
🤖 Generated with Claude Code
Activity
milindsrivastava1997 commentedon Oct 9, 2026
Fan-out has the same gap, once #187 lands. A KLL roll-up from
G_dtoG_rreads its merge curve at⌈card(G_d) / card(G_r)⌉ · L/xmerged instances, using the average number of children per coarse group. In the scenario above, that's 10 endpoints per service, whilecheckoutreally merges 46. The largest group's child count should feed this merge count too, not only its sample count N.zzylol commentedon Oct 10, 2026
Note from the AutoSketch-vs-ASAP eval (#196, e7d8a03): until this issue lands, the eval runner covers the gap without touching
items_per_group. For an RQE whose accuracy covers a set of groups (a share threshold, or every group), the runner reads each per-group sketch's accuracy twice and keeps the worse value (or unknown if either read is unknown):That covers this issue's case: error that doesn't fall as N grows makes the largest group the hardest. It also covers the opposite case, e.g. HLL's small-N regime, where the issue's assumption doesn't hold. Hydra candidates (#201) read measured max-over-covered-groups errors instead.
On the fan-out comment: in that eval's workload the child count per parent is uniform (the skew is in traffic), so the average fan-out equals the largest, and its roll-up merge counts are exact.
The
largest_group_seriesfield and theitems_per_groupchange stay as this issue designs them. The two-ended read above may be worth considering there too, for families whose error isn't monotone in N.🤖 Generated with Claude Code