Skip to content

Cost model derives value signs separately from the memo group's column_signs #1287

Open

Description

@zzylol

Problem, by example

quantile by (job) (0.99, rate(http_requests_total[1m])), with http_requests_total declared a counter, gets a DDSketch build whose input is the rate result. The rate of a counter is never negative, and the state group's column_signs says so (ValueSign::NonNegative), which is what Stage 2 reads to decide whether a Count-Min build is allowed.

The cost model does not read that sign. It derives its own (crates/cost/src/node/usage.rs, raw_data_samples_non_negative): a summary's input is non-negative only when its producer is a Scan or a TimeRange and every source is declared_non_negative. Here the producer is the rate aggregate, so the cost model takes the input as signed and sizes the DDSketch with a negative-value store too (StateInputRows::non_negative = false, crates/cost/src/node/state_bytes/mod.rs, DdSketch::estimated_memory_bytes(..., !non_negative)).

Today: two derivations of "the values are non-negative" that disagree for any build whose producer is not a scan or a range. Wanted: one derivation, the group's column_signs, read by both Stage 2 and the cost model.

This is derived from the code; no plan was found where the difference changes the selected plan.

Why it happens

The cost model predates value signs as a memo-group property. It prices a PhysicalASAPDAGNode and looks only at the node's producer payload and the declared source facts, not at the memo group's column_signs.

Proposal

The cost model reads the sign of the build's input from the memo: the state group's state column in column_signs (as count_min_weights_not_proven_non_negative in Stage 2 does), carried to the priced node, and raw_data_samples_non_negative is deleted.

Scope and acceptance

In scope: asap-cost sizing inputs (StateInputRows::non_negative) and how they reach the priced node. Acceptance: a unit test where a DDSketch over rate of a declared counter is priced with the non-negative store only, which fails today.

Related

Found in the review of the Stage 2 PR of the #1207 formulation refactor. Part of #1207.

Activity

  1. zzylol commented on Nov 16, 2026

    @zzylol
    ContributorAuthor

    Update from the accuracy side of the #1207 refactor (PR 8, #1238), which makes this issue a little sharper. Since #1324, main's cost model no longer has raw_data_samples_non_negative. It now reads the sign in crates/cost/src/node/usage/mod.rs (folded_values): a summary's values count as non-negative only when the build folds an unchanged source column (ProducerOutput::unchanged_column) and every scanned source declares that column non-negative (declared_non_negative).

    #1238 makes the accuracy rules read the memo group's sign instead. DDSketch's quantile guarantee holds only when the state column's sign (GroupProperties::state_column_sign) is one sign (ValueSign::is_one_sign: NonNegative or NonPositive). Stage 2's Count-Min check now reads the same state_column_sign.

    That leaves two derivations that disagree on computed columns. These examples come from reading the code, not from a run:

    DDSketch over state_column_sign (accuracy, Stage 2) cost model's non_negative stores priced
    latency, declared non-negative NonNegative true 1
    -latency (negation) NonPositive: one sign, guarantee holds false (computed column) 2
    rate(http_requests_total[1m]) NonNegative false (computed column) 2

    Proposal, unchanged in spirit: the cost model reads state_column_sign() of the build's state group. It prices one store when is_one_sign() holds, and two otherwise. That covers NonPositive too: a sketch over one-signed negative values fills only its negative store.

    Acceptance: a unit test where a DDSketch over -latency (or over rate of a declared counter) is priced with one store. That test fails on main.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    cost-modelCost formulas, statistics, ranking, and selectionrefactor

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions