Query engine: merge sketches across subpopulations (roll-up to a coarser grouping) #839

Activity

1. milindsrivastava1997

   added

   enhancementNew feature or requestNew feature or request

   asap-query-engine

   on Oct 13, 2026
2. milindsrivastava1997 commented on Oct 13, 2026

   

   milindsrivastava1997

   on Oct 13, 2026

   ContributorAuthor

   More actions

   Resolved design (v1)

   Terms. G is the value config's grouping_labels. Q is the query's output labels (query_output_labels).

   1. No new config field. The engine infers a roll-up from G ⊋ Q, and QueryConfig doesn't change. Capability matching is not involved: it only runs when no query_config matches the query string.
   2. Scope: single-subpopulation configs only. These have empty aggregated_labels and no separate key aggregation, i.e. KLL, DDSketch, HLL, Sum and MinMax. Increase is excluded. Keyed configs (Multiple*, CMS, CMS+heap, HydraKLL, topk-by) keep today's path; their roll-ups are Query engine: roll-ups over keyed aggregations (aggregated_labels) #846.
   3. Where. Re-key the read output. Right after the store read, map each G-key in ComposedRangeRead.groups to its Q-projection and append its buckets into the same BucketMap slot (start_ts → Vec). estimate_range_query stays unchanged: one batch get_merged() per (Q-key, step) merges across time and subpopulations together, fallback_key becomes the Q-key so output labels are right, and instant queries share the path. Rejected alternatives: inside the store (leaks query semantics into the store trait), a second merge after the per-key time merge (restructures the step loop and costs N+1 merges), and query_time_aggregations (a quantile of quantiles is wrong).
   4. Sliding completeness. The range per-step check counts distinct start timestamps, not buckets, for every query. A window that hasn't been computed yet is missing for all subpopulations at once, so it's still caught. A subpopulation with no data in a window just contributes nothing. This also fixes a latent bug where duplicate buckets from same-key fan-in could mask a missing window. The instant all-or-nothing check (per raw G-key) stays as is.
   5. Errors. A single rollup_plan(G, Q, type) -> Result<Option<Projection>, _> in the shared context path covers PromQL, SQL and Elastic, gated on single-subpopulation configs. G == Q returns None (today's path). G ⊋ Q with a v1 type returns a projection. Q ⊄ G and an unsupported type both return Err(Native), not a fall-through to Prometheus, because both mean the planner or config is wrong.
   6. Producers. v1 covers the engine and the MILP planner. The capability-matcher superset change stays in labels_compatible() is exact-match only, not superset matching #649.
      • KLL / DD / HLL: a query_config pointing at the G-grouped aggregation. The engine infers the roll-up.
      • exact-sum / min / max: these are emitted as keyed Multiple* types, but final-value regrouping is exact for them, so the MILP writes planned_subquery (the by clause rewritten to G on the AST) plus query_time_aggregations = [{Sum|Min|Max, by Q}]. Count uses Sum. No engine change is needed.
      • exact-increase / cms-heap: keep RollupUnsupported. sketch-bench's mergeable_across_groups never proposes them anyway.
      • Labels: aggregation_config takes its labels from deployment.grouping_labels, not the first served item.

   Tests

   1. Unit: rollup_plan and the re-key, covering label reordering, Q = ∅, same-projection appends at the same start_ts, and the error cases.
   2. Equivalence through SimpleEngine (instant and range): compare a (service, endpoint) config against a (service) config fed the same samples. Sum and MinMax must be exactly equal. For KLL, DD and HLL, the result must equal a manual merge_with of the stored sketches and be within the sketch's error bound of the truth.
   3. Regression: the distinct-timestamp Sliding check (duplicate bucket plus a missing window gets skipped), topk and keyed queries unchanged, G == Q output identical to before.
   4. PromQL compliance: a new optional Suite.planner_output (fixed streaming and inference YAML, skipping the planner), plus a rollup.yaml suite compared against Prometheus. Its dataset includes an endpoint that appears mid-range.

   PR plan

   1. Sliding check counts distinct start timestamps, plus its regression test.
   2. Engine roll-up: rollup_plan, the re-key, and test layers 1–3.
   3. Compliance harness: planner_output override plus the rollup.yaml suite (layer 4). Depends on 2.
   4. MILP lift for sketches: labels from the deployment, allow KLL/DD/HLL, replace the rollup_is_refused test.
   5. MILP lift for exact types: planned_subquery plus query_time_aggregations.

   PRs 4 and 5 are independent of 1–3. Follow-ups: #649 (matcher superset) and #846 (keyed roll-ups).
3. milindsrivastava1997

   linked a pull request that will close this issuefix(query-engine): judge a Sliding range step's cover by distinct windows #847on Oct 13, 2026
4. milindsrivastava1997

   closed this as completedin #847on Oct 13, 2026