Accuracy: guarantees for comparisons and top-k bands over estimates (#669 follow-up) #743

Problem, by example

rate(http_requests_total[5m]) > scalar(quantile(0.99, rate(http_request_duration_seconds[5m])))

The threshold is a KLL estimate of the p99, with rank error ε = 0.01. A series whose rate lies between the true p99 and the estimated p99 can be kept when it should be dropped, or dropped when it should be kept. The planner has no rule for what this means for the result: Stage 1 keeps the summary candidate, and the result's guarantee is None. So Stage 3 cannot check the entry's AccuracyTarget against it, and an approximate plan for this query can never be accepted as meeting a target.

The same applies to topk(k, …) over approximate values: an item whose true value is within the error band of the k-th value can be swapped in or out. No guarantee describes that band either.

Cause

Guarantee composition (crates/logical-asap-optimization/src/accuracy/composition.rs) covers arithmetic, folds and max/min (#687, #712). The leftovers listed in #687's limitations were never tracked:

1. comparison guarantees (>, <, bool, filters by an estimate) and the top-k band;
2. rank-interval guarantees (a quantile estimate as a rank interval rather than a value);
3. nested operand-domain operations, for example a quotient of quotients;
4. a constant-weight Count-Min norm (stream_row_count) has no binding statistic.

Proposal

• For a comparison against an estimate with absolute error ε: the result is exact for rows whose value is farther than ε from the threshold. The guarantee says "membership exact outside a band of width 2ε" (at failure probability δ). Top-k gets the same band around the k-th value.
• Express it as a new guarantee kind next to the value-error kinds, so Stage 3 can check it when the target asks for membership accuracy, and keeps None otherwise.
• Items 2–4 each get a rule or an explicit "no guarantee" with a test.

Scope and acceptance

• The example above gets a band guarantee, and a test checks it against an exact run.
• Column-level guarantees for filters and grouping by estimates stay in Track exact vs approximate per column so key-only filters over approximate inputs keep their guarantee #689. Counting a shared summary once in the δ split stays in Count a shared summary instance once in the failure-probability split (#669 follow-up) #711.

Related

Follow-up of #669 (closed: parts a and b merged in #687 and #712). #689, #711, #580.