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

Problem, by example

Workload tools/dag-viewer/memo-examples/promql/ratio-of-quantiles-5m.json: one query every minute, with ε = 0.01, δ = 0.001 and no metric set.

avg by (job) (quantile_over_time(0.5, data[5m]) / quantile_over_time(0.5, data[5m]) + quantile_over_time(0.9, data[5m]))

Measured on main (f49900b) with guarantees enforced and every Pass 1 DAG costed:

stage_pipeline --workload tools/dag-viewer/memo-examples/promql/ratio-of-quantiles-5m.json \
  --deployment-capabilities '{"raw_data_retained":true,"query_time_results_retained":false}' \
  --cost-model aws-fargate-us-east-1 --enforce-accuracy-guarantees --price-enumerated 49 --out ratio.json

Every DAG that uses a sketch (KLL or DDSketch) for either quantile is rejected:

Q1: the output has no guarantee, and the deployment has no evidence for it, so it cannot meet target AccuracyTarget { accuracy_metric: None, max_error: 0.01, failure_probability: Some(0.001), accuracy_scope: WholeResult }

In DAG E2 (KLL for quantile 0.9, the rest exact), the guarantee is lost at the +:

So with guarantees enforced, any query that does arithmetic on an approximate quantile can only be planned exact. Without enforcement, the same search picks sketch plans freely: 169 of 169 Pass 2 DAGs were valid, and the selected plan cost 78.93/s against 237.63/s for the exact plan (#1004 measurements).

Why

arithmetic_guarantee (crates/logical-asap-optimization/src/per_computation_candidates.rs:2735) composes value errors only. Its doc says so: "a relative error shifted by a constant or added to another, a rank error … has none".

• A rank error (KLL) says nothing about how far the returned value is from the true quantile's value. Adding it to another value gives no bound.
• A relative error (DDSketch) added to another value has no closed-form bound either.
• operand_domain_statistic already leaves products and quotients of value errors symbolic, so that Stage 3 can bind them from declared source facts. Rank errors are excluded ("an operand's error has no value form").

This is sound behaviour, not a wrong result. It does mean the planner never uses a sketch for these queries.

Options

1. Keep as is, and say so. Document in planner-layering.md that arithmetic over a rank or relative error has no guarantee, so such queries plan exact under enforcement. The viewer already shows the rejection reason per enumerated DAG.
2. Relative + value, through declared bounds. Leave x + y with a relative-error x symbolic on |x|'s upper bound, as operand_domain_statistic does for products. Stage 3 then binds the bound from declared source facts (for example a declared value range). This covers DDSketch.
3. Rank → value, through a declared distribution fact. Turn a rank error ε into a value error using a declared bound on the value distribution (for example the largest gap between the values at ranks q ± ε), then compose as an absolute error. This covers KLL, but needs a new source fact.

Recommendation: (1) now, since it costs nothing and is correct. (2) after that, since it reuses the existing symbolic-statistic path. (3) only with a workload that needs it.

Scope and acceptance

• For (1): the doc paragraph, plus a test that the ratio workload under --enforce-accuracy-guarantees selects the all-exact plan with the 48 no_accuracy_guarantee rejections.
• For (2): a unit test in per_computation_candidates.rs where DDSketch q0.9 + exact gets a symbolic absolute bound, and a stage-pipeline test where declaring the value bound makes a DDSketch DAG valid on this workload.

Related

• Found by --price-enumerated (stage_pipeline: price every enumerated candidate DAG and flag any cheaper than the selected plan #1004 / feat(devtools): stage_pipeline --price-enumerated prices each enumerated memo choice and flags any cheaper than the selected plan #1028).
• Workload from Memo: convert memo-group candidates into the vector of all candidate DAGs #1002 / stage_pipeline: write the memo after each step, the selected choice and the enumeration #1003; the memo example is in Tracking: DAG viewer shows the memo after each step and every candidate DAG it stands for #1008.