Repository navigation
Accuracy: guarantees for comparisons and top-k bands over estimates (#669 follow-up) #743
Description
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:
- comparison guarantees (
>,<,bool, filters by an estimate) and the top-k band; - rank-interval guarantees (a quantile estimate as a rank interval rather than a value);
- nested operand-domain operations, for example a quotient of quotients;
- 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
Noneotherwise. - 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.
Activity
zzylol commentedon Oct 29, 2026
New evidence for item 4 (a constant-weight Count-Min norm,
stream_row_count, has no binding statistic), measured on main61ee27f30.Example.
count by (job)(a) + count by (job)(a)with--max-error 0.01 --failure-probability 0.001 --accuracy-metric absolute --enforce-accuracy-guarantees --series-count 10000 --sample-interval-ms 15000. Pass 1 offersCms(depth=7 width=272)andCms(depth=17 width=272). Every CMS plan is rejected with an unbound bound:Declaring
stream_norms: {"l1": 10000}on sourceadoes not change this. The run with the declaration reports the samebound Nonein all 12accuracy_target_missedrejections.Cause. The count's CMS weight is the constant 1. So
operand_guarantee→stream_norm(crates/logical-asap-optimization/src/per_computation_candidates.rs:2555-2606) picksStreamNorm::ConstantWeight, andadditive_as_absolute(accuracy/composition.rs:526-572) turns the bound into(e/w) · 1 · stream_row_count[a]. Stage 3'sworkload_statistic(crates/plan-selection/src/lib.rs:2739-2775) bindsstream_l1_norm[…]andstream_l2_norm[…]throughparse_source_norm_statistic, which knows only those two norms (composition.rs:66-75). No code bindsstream_row_count[…], so the bound staysNoneeven though the run knows the row count: the scan reads 10000 samples, fromseries_count× window /sample_interval.Two related observations from the same runs:
count by (job)(a)with--accuracy-metric absolute, the root guarantee is not converted at all. The CMS plan is rejected with "guarantees a Absolute { scale: Some(StreamL1) } bound Some(0.009993683192864136) … misses target … Absolute { scale: None }": a metric mismatch, not an unbound norm.realization.rs:81-83,sizing_target), so width 272 gives about 0.01 × 10000 ≈ 100 in absolute terms, against a target of 0.01. Bindingstream_row_countmainly turnsNoneinto a real number that the target can be compared with.Also, with
--accuracy-metric absolute_stream_l1, the only rejections are compile errors. The CMS candidate fails with "node 2: invalid DAG: unsupported weighted frequency family". The UnivMon candidate fails with "node 3: … native output type differs from Planner output". Socount by (job)never runs on a sketch today.Acceptance for item 4 (fails today). A plan-selection test where the bound of
count by (job)(m) + count by (job)(m)evaluates to a number from the workload'sseries_countandsample_interval(or from a declared row-count fact), instead ofNone.Related: #1039 (budget split by reads; its count evidence depends on this), #1040 (the exact plan of that query does not compile), #727 (CountSketch count in the executor).
🤖 Generated with Claude Code