Repository navigation
[Bug] An exact coarser grouping does not roll up the finer exact result #923
Description
Example
sum by (instance) can be computed from the already-computed sum by (instance, region) of the same input. Today the coarser query is rebuilt from raw data.
Workload base.json (exact sum by (instance, region) (avg_over_time(m_gauge[1m])) every 10 s):
{"query_workload":{"language":"promql","query_batch":null,"repeating_queries":[{"query":"sum by (instance, region) (avg_over_time(m_gauge[1m]))","demand":{"fixed_interval":10000},"requirements":{"accuracy":{"max_error":0.0,"failure_probability":0.0,"accuracy_scope":"whole_result"},"max_latency_ms":null},"predictability":{"predictable":{"known_at":null}}}]},"data_workload":{"arrival":{"ingesting":{"rows_per_second":200.0}},"sources":{"m_counter":{"series_count":1000,"metric_type":"counter","values_non_negative":true,"sample_interval":10000,"stream_norms":null,"max_distinct_per_evaluation":null,"distinct_values_per_label":{"instance":50,"job":5,"region":3}},"m_gauge":{"series_count":1000,"metric_type":"gauge","values_non_negative":true,"sample_interval":10000,"stream_norms":null,"max_distinct_per_evaluation":null,"distinct_values_per_label":{"instance":50,"job":5,"region":3}}}}}Workload related.json (adds exact sum by (instance) (avg_over_time(m_gauge[1m]))):
{"query_workload":{"language":"promql","query_batch":null,"repeating_queries":[{"query":"sum by (instance, region) (avg_over_time(m_gauge[1m]))","demand":{"fixed_interval":10000},"requirements":{"accuracy":{"max_error":0.0,"failure_probability":0.0,"accuracy_scope":"whole_result"},"max_latency_ms":null},"predictability":{"predictable":{"known_at":null}}},{"query":"sum by (instance) (avg_over_time(m_gauge[1m]))","demand":{"fixed_interval":10000},"requirements":{"accuracy":{"max_error":0.0,"failure_probability":0.0,"accuracy_scope":"whole_result"},"max_latency_ms":null},"predictability":{"predictable":{"known_at":null}}}]},"data_workload":{"arrival":{"ingesting":{"rows_per_second":200.0}},"sources":{"m_counter":{"series_count":1000,"metric_type":"counter","values_non_negative":true,"sample_interval":10000,"stream_norms":null,"max_distinct_per_evaluation":null,"distinct_values_per_label":{"instance":50,"job":5,"region":3}},"m_gauge":{"series_count":1000,"metric_type":"gauge","values_non_negative":true,"sample_interval":10000,"stream_norms":null,"max_distinct_per_evaluation":null,"distinct_values_per_label":{"instance":50,"job":5,"region":3}}}}}cargo run -p asap-devtools --bin stage_pipeline -- --workload base.json --enforce-accuracy-guarantees --out base.out.json
cargo run -p asap-devtools --bin stage_pipeline -- --workload related.json --enforce-accuracy-guarantees --out related.out.json
# same two commands with --exhaustive: identical selected plans and costs| Workload | Selected plan | Cost per second |
|---|---|---|
base.json |
P1 |
0.006655 |
related.json |
P54-m3 |
0.007761 |
Witness: base.json plan with the coarser query derived by an exact Sum grouped by (instance) over the finer query's result |
witness-m1 |
0.006685 |
Expected: related.json costs about 0.006685 (the witness), not 0.007761.
Re-verified on current main (stage_pipeline built at 65655b6); the numbers above are from that run.
Current behavior
The coarser query adds 0.001106 per second where the roll-up adds 0.000030. Same class in SQL: COUNT(*) GROUP BY city, host then GROUP BY city (seed 11 case 9): 0.002714 selected vs 0.002247 witness.
Second, smaller example, a sketch roll-up missed for a quantile over an inner range function (seed 12 case 57, s12-012, accuracy 0.05, failure probability 0.01): quantile by (job, region) (0.95, sum_over_time(m_gauge[5m])) then quantile by (job) (0.95, sum_over_time(m_gauge[5m])). Base 0.190019 (P5); with the coarser query 0.192036 (P120-m1); witness 0.190022, which merges the finer summary state with group_by = (job) and then estimates. The gap is small (0.0020) but it is the same missing roll-up, here for a sketch. Workload for this one:
base.json: {"query_workload":{"language":"promql","query_batch":null,"repeating_queries":[{"query":"quantile by (job, region) (0.95, sum_over_time(m_gauge[5m]))","demand":{"fixed_interval":10000},"requirements":{"accuracy":{"max_error":0.05,"failure_probability":0.01,"accuracy_scope":"whole_result"},"max_latency_ms":null},"predictability":{"predictable":{"known_at":null}}}]},"data_workload":{"arrival":{"ingesting":{"rows_per_second":1333.3333333333333}},"sources":{"m_counter":{"series_count":10000,"metric_type":"counter","values_non_negative":true,"sample_interval":15000,"stream_norms":null,"max_distinct_per_evaluation":null,"distinct_values_per_label":{"instance":50,"job":5,"region":3}},"m_gauge":{"series_count":10000,"metric_type":"gauge","values_non_negative":true,"sample_interval":15000,"stream_norms":null,"max_distinct_per_evaluation":null,"distinct_values_per_label":{"instance":50,"job":5,"region":3}}}}}
related.json: {"query_workload":{"language":"promql","query_batch":null,"repeating_queries":[{"query":"quantile by (job, region) (0.95, sum_over_time(m_gauge[5m]))","demand":{"fixed_interval":10000},"requirements":{"accuracy":{"max_error":0.05,"failure_probability":0.01,"accuracy_scope":"whole_result"},"max_latency_ms":null},"predictability":{"predictable":{"known_at":null}}},{"query":"quantile by (job) (0.95, sum_over_time(m_gauge[5m]))","demand":{"fixed_interval":10000},"requirements":{"accuracy":{"max_error":0.05,"failure_probability":0.01,"accuracy_scope":"whole_result"},"max_latency_ms":null},"predictability":{"predictable":{"known_at":null}}}]},"data_workload":{"arrival":{"ingesting":{"rows_per_second":1333.3333333333333}},"sources":{"m_counter":{"series_count":10000,"metric_type":"counter","values_non_negative":true,"sample_interval":15000,"stream_norms":null,"max_distinct_per_evaluation":null,"distinct_values_per_label":{"instance":50,"job":5,"region":3}},"m_gauge":{"series_count":10000,"metric_type":"gauge","values_non_negative":true,"sample_interval":15000,"stream_norms":null,"max_distinct_per_evaluation":null,"distinct_values_per_label":{"instance":50,"job":5,"region":3}}}}}Expected behavior and invariant
For the workload with the added query, the selected cost should not exceed the base cost plus the cost of deriving the added query from the base plan, within a small tolerance. The cheaper plan (the witness) is priced by Stage 2 and Stage 3 with the same models as the search and passes Stage 3's checks, but the search never selects it.
Minimal reproduction
The two stage_pipeline commands above. planner_fuzz found it (seeds and relation names are under Status and related work). Running with --exhaustive selects the same plan and the same cost, so no candidate rule generates the cheaper plan; it is a missing candidate, not a search miss.
Why it happens
Not diagnosed. No candidate rule derives a coarser grouping from the finer query's result or summary state, for exact aggregates (the docs say the exact roll-up exists) or for sketches over an inner range function.
Regression test
Plan base.json and related.json and assert cost(related) - cost(base) <= derive_cost + tolerance. Today it fails with the numbers above.
Status and related work
Related: #278 (accuracy-aware approximate Count roll-ups; this issue is the exact case plus a sketch case). Found by planner_fuzz seeds 11 and 12, relation c-coarser-grouping.
Activity
zzylol commentedon Oct 27, 2026
Confirmed a missing rollup candidate on main
7680b6bcafter the MILP migration.For the original PromQL example, the fine and coarse outer Sum candidates read per-series Avg nodes. Their source schemas project different label sets:
(instance, region, series identity)versus(instance, series identity).asap_aware_cse.rs::finer_keysrequiressame_rowsfor these inputs.same_rowsrecognizes compatible scans and follows TimeRange/TimeShift, but does not follow the identical per-series Avg reductions. Structural equality also fails because the projected schemas differ. Thereforememo/rules/rollup.rs::add_rollup_candidatesadds no coarse-root rollup candidate.A focused catalog regression fails with “coarse root has no rollup candidate” before the change. Conservatively recognizing equal, unfiltered per-series reductions of the implicit sample value makes that regression pass. A production run then selects a Sum over the 150 fine-group results followed by finalization to 50 groups: 0.0066901080 versus base 0.0066551003. This includes the shared-result projection/materialization overhead.
There is also a separate bounded-search concern: on unchanged main, one 30 s run returned a much worse seed (0.0646811503); run timing affects which incumbent is reached. The missing-candidate diagnosis above does not depend on that timing.
Changes are uncommitted in a fresh worktree. This confirms the primary PromQL Avg→Sum example; the SQL COUNT and sketch variants need their own validation. No claim of a full-workload optimality certificate or complete issue resolution.
zzylol commentedon Oct 27, 2026
Implemented in PR #943. Rollups recognize identical per-series reductions beneath different label projections, while refusing different windows/functions/predicates. SQL counts merge integer count states directly. The original coarse-sum workload costs 0.006690108/s; the inner-range sketch catalog regression passes. SQL count rollups execute correctly for NULL keys, empty grouped inputs and empty global counts.
Final local validation: 690 focused tests passed, plus workspace format and all-target/all-feature Clippy checks.