Repository navigation
rqe-optimizer: let mergeable finer-group deployments serve coarser RAQEs #187
Description
Activity
Design decisions (for review)
Notation: a deployment grouped by
G_dserves a RAQE grouped byG_r ⊂ G_dby merging eachG_rgroup's fine states into one (a roll-up).Lis the lookback,xthe window,Tthe query interval. Example used throughout: KLL by(service, endpoint)(card = 50) serving p99 by(service)(card = 5),L = 1h,x = 1m.Each answer below is the decision. Please approve or push back.
Scope
- Out of scope: top-k and Hydra. Top-k heaps don't roll up: an item can be outside every child's top-k but in the parent's. Hydra returns estimates, not mergeable per-key KLLs.
- ASAPQuery can't execute roll-ups yet. No feature flag: ASAPQuery pins a sketch-bench rev, and until it supports roll-ups it should error on a plan where a RAQE's grouping differs from its deployment's. Threading a flag into
is_eligiblewould touch about 8 signatures. - Uneven fan-out (e.g. one service owning 46 of 50 endpoints) is split out to rqe-optimizer: read accuracy at the largest group's sample count, not the average #189: worst-group sample count, plus fan-out (comment). This issue uses averages.
Q1. Which families can roll up?
New
FamilyProperties::mergeable_across_groups. The test for each family: does merging per-G_dstates give theG_ranswer?Family Merge across groups Decision exact-sum (Sum, Count), exact-min, exact-max add / min / max trueexact-increase (RateOrIncrease) add increases (a coarse rate is sum by (G_r))truehll, univmon-cardinality union truekll-percall, dd sketch merge truecms/countsketch heap top-k, univmon-topk heap merge loses items falsehydra-kll none falseis_eligible: groupings are equal, or the family ismergeable_across_groupsandr.grouping ⊂ d.grouping. A coarse deployment never serves a finer RAQE.Q2. Which RAQEs decide a fine deployment's candidate windows?
Today, windows, slides and heaps for grouping
Gcome only from RAQEs grouped exactly byG. A finexthat doesn't divide the coarse RAQE'sLcan't be shared.Decision: for families that merge across groups, derive them from every RAQE with the same capability, metric and filter whose grouping ⊆
G. Other families (top-k) keep exact-grouping inputs, so their candidate count doesn't grow. No new groupings are invented: candidates exist only for groupings some RAQE uses.Q3. How is a roll-up read priced?
Each merge folds two states into one. A query reads
card(G_d)·L/xstates and ends withcard(G_r), so:merges = card(G_d) · L/x − card(G_r)(Check with 2 services × 2 endpoints and
L/x = 3: 12 − 2 = 10. Folding windows takes 2 × 4 = 8 merges, then folding endpoints takes 1 × 2 = 2.)Phase Today Decision merge CPU card(G)·(L/x − 1)·c_mrg / T(card(G_d)·L/x − card(G_r))·c_mrg / Tmerge memory card(G)·m(L)card(G_r)·m(L)query CPU / output card(G)·…card(G_r)·…latency card(G)·c_qry + card(G)·(L/x−1)·c_mrgcard(G_r)·c_qry + merges·c_mrgingest, storage G_dunchanged - With
G_r = G_d, every row reduces to today's formula. - A direct query (
L == x) that rolls up still mergescard(G_d) − card(G_r)states. - DD's accumulator
m(L)is sized from a coarse group's values,λ·L / card(G_r). - Assumption: a cross-group merge costs the measured
c_mrg, the same as a cross-window merge.
Q4. How is roll-up accuracy computed?
Input Today Roll-up DataShapedata_shape[G_d]data_shape[G_r]N per group λ·L / card(G_d)λ·L / card(G_r)Merged instances (KLL only: it merges lossily, #131) L/x⌈card(G_d) / card(G_r)⌉ · L/xDD, HLL and exact families merge exactly, so only the shape and N change for them. Past the merge counts the study measured, the existing theory fallback or rejection applies.
Q5. How does the plan show a roll-up?
Decision: no new field. A RAQE is a roll-up exactly when
raqe.grouping_labels != deployment.grouping_labels.merged_instance_countstaysL/xwindows per fine group.small_problem.rsprintsrolls up G_d → G_ron the RAQE line.Q6. Validating facts
The merge count assumes
card(G_r) ≤ card(G_d). Bad facts (e.g.card(service) = 60 > card(service, endpoint) = 50) would give negative merge CPU, which the MILP would treat as a discount.Decision:
validate_factsrequirescard(X) ≤ card(Y)for every pairX ⊂ Yincardinality. This generalizes the existing "more groups than series" check rather than clamping in the cost model.Q7. Tests
Where Test tests/mixed_grouping.rsEnd to end, written first and failing on main: two quantile RAQEs by(service, endpoint)and(service)share one fine KLL deployment. Top-k at the same groupings keeps one deployment per grouping.candidates.rsRoll-up only to a subset grouping and only for mergeable families. Top-k serves only its own grouping. Fine candidates take windows from coarser RAQEs ( L = 1hfine withL = 90mcoarse gives a finex = 30m), but top-k candidates don't.analytical_cost_model.rsRoll-up merge count, accumulators and latency, including a direct ( L == x) roll-up.saturation.rsKLL roll-up reads the coarse shape, coarse N, and ⌈fan-out⌉·L/xmerges.lib.rsSubset-cardinality validation. Existing tests all use equal groupings and must pass unchanged, which shows that plans without roll-ups don't move.
🤖 Generated with Claude Code
Change to Q1 (design comment): exact-increase (RateOrIncrease) does not roll up. Its
mergeable_across_groupsisfalse, because a rate rolled up to a coarser grouping isn't a meaningful query.Updated Q1 table:
Family Roll up? exact-sum (Sum, Count), exact-min, exact-max yes hll, univmon-cardinality yes kll-percall, dd yes exact-increase (RateOrIncrease) no cms/countsketch heap top-k, univmon-topk no hydra-kll no The test
candidates::tests::a_rate_serves_only_its_own_groupingcovers it.- added a commit that references this issue
on Oct 9, 2026 - linked a pull request that will close this issuerqe-optimizer: let mergeable finer-group deployments serve coarser RAQEs #190
on Oct 9, 2026 - added a commit that references this issue
on Oct 9, 2026 - added a commit that references this issue
on Oct 9, 2026 - added a commit that references this issue
on Oct 10, 2026
What to build
Extend the optimizer so that a deployment keyed by a finer grouping can serve a RAQE at a coarser grouping when the sketch family has sound merge semantics for the roll-up. For example, a deployment by
(service, endpoint)may serve a query by(service)by merging its endpoint states per service. Treat this as a derived readout: the planner must choose it only when its modeled accuracy and latency satisfy the RAQE's SLAs and its total cost beats the alternatives.Do not make this a blanket subset-of-labels rule. Families without valid roll-up semantics remain ineligible.
Acceptance criteria
Related
Blocked by
None - can start immediately