Skip to content

[Bug] A top-k heap over a PromQL item (tuple or series identity) is costed as if every row's item differed #1387

Open

Description

@zzylol

Example

topk(10, sum by (url) (...)) over a source that declares distinct_values_per_label: {url: 5} and no max_distinct_per_evaluation, planned as a query-time Count-Min Sketch with heap (depth 10, heap size 10) over 10,000 rows into one state.

  • Today: the heap's item is a SummaryInputExpr::Tuple (or an EntityIdentity), not a single Column. folded_distinct_values in crates/cost/src/node/usage/mod.rs therefore finds no declared count and returns None, and the cost model assumes every row's item differs. The heap is charged 10 residents per update: 29 + (10 + 1) × (150 + 33 × 10) = 5,309 operations per row.
  • Expected: the 5 declared URLs bound the heap at 5 residents: 29 + (5 + 1) × 480 = 2,909 per row, about 1.8× less. The read (estimate_operations_per_group) and the merge (merge_operations_per_state) count residents the same way, so they are over-charged too.

These numbers come from the formulas in crates/cost/src/node/operations_per_unit.rs (update_operations_per_row, heap_residents_per_update, heap_residents), not from a run.

When the item count is at least the heap size and the state folds many rows, as in the 100-URL heavy-hitter workloads, the charge is about the same either way: 9.53 residents instead of 9.50, so #1382's 100-URL example is charged the same. The gap matters for heaps over few items, or over few rows per state.

Current behavior

ProducerOutput::unchanged_column(expr) resolves only SummaryInputExpr::Column. A PromQL top-k item never takes that form:

  • with a PromQL series identity, series_identity_item (crates/types/src/ir/schema/topk/mod.rs) lists the child's label columns and appends __series_identity;
  • a closed child (an aggregate's output) gets SummaryInputExpr::Tuple of its columns outside the partition, even when there is only one (crates/stage1-pass1-per-computation-candidates/src/summary_realization.rs, the Top-K item);
  • an open child gets an EntityIdentity.

Only a SQL top-k over one item column resolves today. Otherwise the cost falls back to the sources' max_distinct_per_evaluation, which the heavy-hitter workloads do not declare.

Expected behavior and invariant

A heap's charged residents are at most the distinct items its item expression can take, as far as the data facts bound them:

  • a Tuple: the product of its columns' declared distinct values, capped by the sources' series count;
  • __series_identity or an EntityIdentity: the series count;
  • None only when some column declares nothing.

Proposal

Resolve the item's distinct values in asap-cost next to folded_distinct_values. A Tuple gives the product of its columns' distinct_values_per_label, then the minimum with declared_series and with max_distinct_per_evaluation; the series identity and EntityIdentity give the series count. unchanged_column stays a single-column lookup.

The accuracy side does not read this value: heap guarantees use no distinct count, and distinct-count guarantees read only max_distinct_per_evaluation.

Scope and acceptance

  • In scope: the cost model's distinct item count for Tuple, series-identity and EntityIdentity items.
  • Out of scope: accuracy rules; the KMV weight path.
  • Regression test (fails today): the example above, through node_resource_usage_and_cost. A heap over a PromQL top-k item of 5 declared URLs is charged 5 residents per update, at read and at merge.

Related

Activity

  1. added
    bugSomething isn't working
    cost-modelCost formulas, statistics, ranking, and selection
    on Nov 16, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

bugSomething isn't workingcost-modelCost formulas, statistics, ranking, and selection

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions