Accuracy budget is split by memo groups, not by reads: a quantile or count read twice gets only whole-budget sketches #1040

Problem, by example

The same quantile read twice in one query gets no smaller sketch, so the planner falls back to exact.

quantile_over_time(0.5, a[5m]) * quantile_over_time(0.5, a[5m])

Run on main 61ee27f30 with ε = 0.01, δ = 0.001, metric relative, guarantees enforced, and source a declared values_non_negative: true (10000 series, 15 s sample interval). The DDSketch relative bound needs that declaration for an interior quantile.

stage_pipeline --workload w_mm.json --enforce-accuracy-guarantees --out nn_mm.json

Stage 0 hash-conses the two operands into one memo group, so the BinaryOp group has children [2, 2]. In Pass 1, group 2 offers only whole-budget sketches:

The product of two estimates that are each within relative α is within 2α + α². So the DDSketch plan is rejected:

accuracy_target_missed: q1: the output guarantees a Relative bound Some(0.0201), failure probability Some(0.0), which misses target AccuracyTarget { accuracy_metric: Some(Relative), max_error: 0.01, … }

The plan selected is exact (hash aggregate, 0.000403/s).

Change one operand to a different quantile and keep everything else the same:

quantile_over_time(0.99, a[5m]) * quantile_over_time(0.5, a[5m])

Now the two operands are two groups. Each group also offers half-budget sketches (DDSketch(alpha=0.004962809790010847), Kll(… k=746), Kll(… k=1184) at budget_share 2). Pass 2 shares one DDSketch between the two quantiles, and the plan selected is that DDSketch plan at 0.000359/s.

What should happen: a group read twice by one value should get the same half-budget candidates as two distinct groups. "One half-budget DDSketch, read twice" is a valid plan for the first query, but the memo never offers it.

Counts show the same pattern (metric absolute, guarantees enforced, from --promql … --max-error 0.01 --failure-probability 0.001 --series-count 10000 --sample-interval-ms 15000):

For counts, the impact is hidden today. The exact plan does not compile (#1039), and a CMS count has no absolute bound (#743, item 4). So all evidence for counts is at the memo level. The quantile example above shows the end-to-end effect.

Why it happens

The share count comes from the number of distinct approximate groups or states, not from the number of times they are read:

• crates/logical-asap-optimization/src/memo/groups.rs:129-134 (pass1_candidates): most_approximate_inputs[q] += summaries adds the summaries of each target group once per group. A group that appears twice among the BinaryOp's children still adds once. With one group, max_budget_share is 1, and target_candidates (groups.rs:204) never builds share 2.
• crates/logical-asap-optimization/src/per_computation_candidates.rs:1302-1324 (budget_shares) and approximate_inputs (:1332) count "every sketch summary state reachable from root, each once". So the per-computation sizing has the same blind spot.
• Composition already counts the error per read. arithmetic_guarantee (per_computation_candidates.rs:2735-2777) adds l and r even when same_operand, which is correct: x̂ + x̂ has twice x̂'s error. Only the sizing side undercounts.

Proposal

Split the budget by reads for ε and by distinct sketches for δ:

• ε: n = the number of reads of approximate groups (a group read k times counts k), so each read gets ε/n. For x̂ + x̂ this means one sketch sized at ε/2.
• δ: count each distinct sketch once. arithmetic_guarantee already counts δ once when both sides are the same planned operator (same_operand, :2731-2745). Counting a shared summary once across separate readouts is Count a shared summary instance once in the failure-probability split (#669 follow-up) #711.

Apply the same count in pass1_candidates (memo) and in budget_shares / approximate_inputs (per computation), so the two stay consistent.

A related observation that is not confirmed: in the count run, the rejected plans report failure probabilities of 0.000414 and 0.000828 (exactly 2×). This may come from two separate SummaryEstimate operators over one summary, each counted once, as arithmetic_guarantee's doc says ("Two estimates count once each, even over one shared summary"). The fix should check which case produces the 2× value, and either link it to #711 or fix it.

Scope and acceptance

• In scope: the share count in memo/groups.rs and per_computation_candidates.rs for operands that hash-cons to one group or state.
• Out of scope: unequal splits; counting shared summaries once in δ (Count a shared summary instance once in the failure-probability split (#669 follow-up) #711).
• Regression test (fails today): a memo unit test next to a_ratio_operand_has_a_candidate_per_budget_share (groups.rs:858). For quantile_over_time(0.5, m[5m]) * quantile_over_time(0.5, m[5m]), the quantile group offers sketches at budget_share 1 and 2, as the two distinct groups of q0.99 * q0.5 do.
• End to end: with values_non_negative declared, the first query above selects a DDSketch plan instead of exact.

Related

• Found while reviewing PR fix(cse): share equal nodes that return the same rows for the same input, not only keyed ones #1032.
• Count a shared summary instance once in the failure-probability split (#669 follow-up) #711: count a shared summary once in the δ split.
• Exact plan for count by (job)(a) + count by (job)(a) does not compile: a vector-vector BinaryOp passes the Int64 count to the executor #1039: the exact plan for count by (job)(a) + count by (job)(a) does not compile.
• Accuracy: guarantees for comparisons and top-k bands over estimates (#669 follow-up) #743 (item 4): a CMS count's stream_row_count norm has no binding, so its absolute bound is None.
• Arithmetic over an approximate quantile has no accuracy guarantee, so with guarantees enforced the ratio-of-quantiles query plans only exact (1 of 49 Pass 1 DAGs valid) #1034: arithmetic over a rank error has no guarantee.
• Compose accuracy guarantees through arithmetic and comparisons over approximate values #669: the equal budget split this refines.

🤖 Generated with Claude Code