A DDSketch quantile's relative bound fails when the interpolated neighbours straddle zero #807

Problem, by example

max by (region) (quantile_over_time(0.5, x[100s])) over a gauge x with no sign declaration (values_non_negative: false). Plan selection accepts the per-series DDSketch candidate with a relative-error guarantee of alpha (a_non_negative_gauge_carries_a_ddsketch_relative_bound_through_avg: max is valid whatever the samples' sign). Since #802 the executor's DDSketch takes zero and negative samples.

Take one series whose window holds -100, -100, 99, 99, with alpha = 0.01. PromQL's median interpolates between ranks 1 and 2: 0.5 · (-100) + 0.5 · 99 = -0.5. The executor's DDSketch quantile (DdSketch::quantile_interpolated) reads each neighbour within alpha of its own magnitude, so the result is within alpha · (0.5 · 100 + 0.5 · 99) ≈ 1 of the exact value in absolute terms. Measured at 63e5655 (the current sketchlib pin):

The plan promises 0.01.

Why it happens

ddsketch_relative_error_alpha_v1 (crates/logical-asap-optimization/src/accuracy/estimators/ddsketch.rs) states a relative error of alpha on the value read, whatever the samples' sign. That holds for one order statistic, and for an interpolation between two order statistics of the same sign. When the two neighbours have strictly opposite signs (no zero sample between them), the interpolated value can be near zero while the error scales with the neighbours' magnitudes. The sketchlib doc for quantile_interpolated says so: across zero the bound is absolute, alpha · ((1 − f) |lower| + f |upper|).

Before the interpolation fix, the nearest-rank read was further off in these cases (it returns -100 for the first window), so this is not a regression of that fix. It became reachable when #802 let a DDSketch take negative samples while keeping the guarantee for any sign.

Proposal

Options, for a decision:

1. Grant the DDSketch quantile's relative bound only when the samples' sign is known (declared non-negative, or a counter). Without it, accept the candidate with an absolute bound or reject it for a relative target. This changes max over undeclared gauges (Declare non-negative gauges so per-series quantile sketches get a guarantee through avg #772), which is valid today.
2. Keep the relative bound and document that it holds except when an interpolated quantile straddles zero.
3. Keep the relative bound and read the nearest order statistic when the two neighbours have opposite signs. This keeps alpha relative to that order statistic, not to PromQL's interpolated value.

Acceptance

A plan-selection test: for an undeclared gauge and a relative target, the DDSketch candidate of max by (region) (quantile_over_time(0.5, x[100s])) is either rejected or carries the weaker guarantee chosen above. A runtime test over the window -100, -100, 99, 99 checks that the answer is within the stated guarantee.

Related

#802 (DDSketch takes zero and negatives), #803 (interpolated DDSketch quantiles), #772, #780, #795.