PromQL topk over a grouped sum of sum_over_time or count_over_time gets no heap candidate #832

Problem, by example

This query ranks groups by the sum of their raw samples:

topk(3, sum by (region) (sum_over_time(data[1m])))

It ranks groups, not series. The ASAPQuery top-k-sum templates (q06-topk-sum, q07-topk-sum) render the series-ranking form, topk by (region, service) (4, sum_over_time(data[20m])) (checked in random_workloads.py and the seed-862 manifests), which already gets the fused heap.

Here data is a gauge (10,000 series, sampled every 100 ms), and the query has max_error 0.05, failure_probability 0.3. Each raw sample adds its value to its region, and the top 3 regions are ranked. That is exactly what a fused Count-Min or Count Sketch heap answers in one pass over the samples.

The PromQL frontend lowers it today (show_logical_dag, on the #831 branch) to an exact sort and limit:

Limit{3}
  Sort{value desc}
    Aggregate{[Sum], by (region)}
      Aggregate{[Sum], PerEntity}        -- sum_over_time
        TimeRange{1m}
          Scan{data}

The counter form, topk(3, sum by (region) (increase(reqs[1m]))), lowers to Aggregate{[TopK{3}], by ()} over the same two aggregates. Pass 1 gives it the fused whole-expression heap. The gauge form has no TopK measure, so Pass 1 has no top-k target and offers no heap candidate. The count_over_time form, topk(3, sum by (region) (count_over_time(data[1m]))), behaves the same way.

Observed: a plan with guarantees ignored and only CmsWithHeap plans allowed (the HeapPlansOnly check in crates/planner/tests/runtime_install.rs), values_non_negative: true, and no raw data kept fails:

plan selection: no valid candidate: [
  P1-m1 ExecutorCannotCompile "this deployment runs only CmsWithHeap top-k plans",
  P1    RawDataNotRetained   "scans raw data at query time, but the deployment does not retain raw data"]

There are only two candidates, and neither one has a heap.

Expected: the query gets a TopK target. That target keeps Exact, and it gets a fused computation with CmsWithHeap and CountSketchWithHeap. Each heap reads the TimeRange rows directly, keyed by region and weighted by the sample value. A count_over_time heap is weighted by 1 instead. The answer has the exact top-k's columns: region and the value, without __name__.

Why it happens

• Frontend (root cause). build_over_sub_dag (crates/frontend-promql/src/promql.rs) promotes topk(k, <sum>) to AggIntent::TopK only when the summed child is rate, increase or irate. It lowers every other argument with ranked_by_value (Sort + Limit). canonicalize's try_promote_additive_top_ranking (crates/types/src/ir/canonicalize.rs) does not promote it either: it refuses a Sum whose child is an Aggregate.
• Pass 1. Promoting the query is not enough, because two pieces in Pass 1 have to change too:
  • realize_keyed_additive_summary_input (crates/logical-asap-optimization/src/realization.rs) would build the heap over the per-series sum's output, one row per series. It needs to read the raw samples beneath it, since a grouped sum of per-series sums (or counts) is the sum (or count) of those samples by group.
  • FusedComputation.absorbs names one target. A heap over the samples absorbs two: the grouped sum and the per-series sum or count.
• The fix(planner): Stage 3 rejects plans the executor cannot compile; no PromQL top-k heap over its instant vector #805 prune (TopKHeapOverOneRowPerItem) is not the cause. It never sees this query, because there is no TopK target. It also runs after the fused heaps have moved out of a top-k's own candidates.

topk by (G) (k, sum_over_time(m[W])) (q06) and the counter forms already get the fused heap after #815 and #831.

Proposal

• Frontend: lower topk(k, sum by (G) (sum_over_time|count_over_time(m[W]))) (descending only) to Aggregate{[TopK{k}]} over the unchanged sum, as the counter forms are lowered. bottomk keeps Sort + Limit.
• Pass 1: the keyed-additive rule reads the per-series aggregate's input rows when the grouped sum is over a per-series sum or count of raw samples. A sum is weighted by the sample value, with the open SamplesOfMetric requirement that plan selection confirms (fix(plan-selection): prove Count-Min weights over a gauge declared non-negative #815). A count is weighted by 1, which is proven non-negative. The rule refuses a grouping by __name__, which the per-series result drops.
• FusedComputation.absorbs becomes the list of targets the fusion absorbs. The grouped sum keeps its own nested-sum merge, so the exact top-k is not made more expensive.

Scope and acceptance

In scope: the sum_over_time and count_over_time forms. The counter forms (increase, rate) are already covered. Out of scope: bottomk, other range functions (avg_over_time, max_over_time, …), and SQL nested aggregates.

Acceptance:

• A Pass 1 test: the shapes above get a TopK target with Exact and a fused CmsWithHeap and CountSketchWithHeap over the TimeRange. This test fails today.
• A plan_installable plus stand-in runtime test (runtime_install.rs pattern): a forced heap plan of each algorithm compiles, recalls the true top 3 on skewed data, keeps each estimate within the heap's ε bound and close to query_time_reference, and names each answer by region alone.

Related

#692 (whole-expression heap), #805 (prune heaps over one row per item), #815 (Count-Min weights over a gauge declared non-negative), #831 (heap top-k plans compile and answer per ranked item; its body lists this shape as not covered).