Define consistent fallible semantics for sketch query APIs

[tisonkun]

Context

The Rust implementations currently use different error models for distribution queries:

• T-Digest returns Option when querying an empty sketch and panics for invalid ranks, NaN rank inputs, or invalid split points.
• KLL and REQ return Result, but currently classify an empty sketch as InvalidArgument alongside malformed query arguments.
• Deserializers separately report malformed serialized state as InvalidData.

An empty sketch is a valid object state: it can be created, serialized, merged, and updated. However, quantile, rank, CDF, and PMF values are undefined until the sketch has observed data. That condition is distinct from an invalid query argument and from corrupted serialized data.

The C++ and Java implementations preserve this distinction with exception categories:

• DataSketches C++ T-Digest and KLL throw std::runtime_error for queries on empty sketches and std::invalid_argument for invalid query parameters.
• DataSketches Java T-Digest throws SketchesStateException for queries on empty sketches and SketchesArgumentException for invalid query parameters.
• DataSketches Java KLL is a notable inconsistency: it reports empty-query failures as SketchesArgumentException.

References:

• C++ T-Digest query behavior: https://github.com/apache/datasketches-cpp/blob/master/tdigest/include/tdigest_impl.hpp
• C++ KLL query behavior: https://github.com/apache/datasketches-cpp/blob/master/kll/include/kll_sketch_impl.hpp
• Java T-Digest query behavior: https://github.com/apache/datasketches-java/blob/main/src/main/java/org/apache/datasketches/tdigest/TDigestDouble.java
• Java KLL query behavior: https://github.com/apache/datasketches-java/blob/main/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java

Problem

The crate does not yet have a documented policy for these independent conditions:

1. The sketch is valid but contains no data.
2. The caller supplies an invalid rank, NaN value, or invalid split points.
3. Serialized input is malformed.
4. An internal invariant fails, indicating an implementation bug.

As a result, similar query APIs differ in return types, panic behavior, and error classification. Adding more batch query APIs will make that inconsistency more visible.

Design questions

We should decide which Rust model applies consistently to T-Digest, KLL, and REQ queries.

A. Keep absence separate from caller errors

fn quantile(&self, rank: f64) -> Result<Option<f64>, Error>;

• Ok(Some(value)): query succeeded.
• Ok(None): the sketch is empty.
• Err(InvalidArgument): the rank is invalid.

This is precise but introduces nested handling for every query.

B. Model an undefined query as a distinct recoverable error

fn quantile(&self, rank: f64) -> Result<f64, Error>;

For example, extend ErrorKind with a distinct category such as EmptySketch or UndefinedOperation:

• Ok(value): query succeeded.
• Err(EmptySketch): the sketch is valid but the requested statistic is undefined.
• Err(InvalidArgument): the query parameter is invalid.
• Err(InvalidData): serialized input is malformed.

This is the closest Rust analogue to the C++ and Java T-Digest distinction while keeping one return layer.

C. Treat invalid query parameters as programming errors

fn quantile(&self, rank: f64) -> Option<f64>;

• Some(value): query succeeded.
• None: the sketch is empty.
• Panic: the query parameter violates the documented precondition.

This matches the current T-Digest API and is compact, but it makes runtime-provided query parameters non-recoverable without prevalidation.

D. Make invalid inputs unrepresentable

Validated NormalizedRank and split-point wrapper types could leave queries returning Option, but the additional public types and conversion steps may be disproportionate to the problem.

The discussion should also decide:

• Whether min_value and max_value should remain Option, following ordinary Rust collection accessors, even if statistical query methods return Result.
• Whether query arguments are validated before checking emptiness, so invalid input has deterministic behavior independent of sketch state.
• Whether internal invariant failures remain assertions or unreachable! rather than becoming public recoverable errors.
• Whether the policy applies only to quantile sketches initially or to all sketch families.

Desired outcome

Agree on and document a crate-wide error policy for sketch queries, then apply it consistently to the affected APIs with tests covering empty sketches, invalid arguments, malformed serialized data, and internal invariants at the appropriate boundaries.

[tisonkun]

This can be related to #27

[tisonkun]

After reviewing the public APIs across the current sketch families, I lean toward A: keep absence separate from caller errors, with the return type chosen according to the actual failure modes of each query rather than mechanically applying Result<Option<_>> everywhere.

The repository-wide pattern supports that distinction. Most existing Result APIs are justified: constructors validate configuration, deserializers validate an external representation, and unions/merges reject incompatible sketches. The main inconsistency is specifically in distribution queries: REQ currently treats an empty sketch as InvalidArgument, while T-Digest uses Option for emptiness but panics on invalid runtime parameters.

I suggest the following policy:

• Option<T> when the only non-success condition is that a valid sketch has no result yet.
• Result<T, Error> when a result always exists for a non-empty sketch but the caller can supply an invalid argument.
• Result<Option<T>, Error> when emptiness and invalid caller input are independent conditions.
• InvalidData only at representation boundaries such as deserialization. Once deserialize returns Ok, queries should not surface serialized-data errors.
• Panics only for internal invariant failures that cannot be produced through safe public APIs, not for ranks or split points that may reasonably come from runtime input.

Applied concretely, this would likely mean:

// No independently invalid query argument.
fn rank(&self, item: &T, criteria: SearchCriteria) -> Option<f64>;

// Empty is ordinary absence; an invalid rank is a caller error.
fn quantile(&self, rank: f64, criteria: SearchCriteria)
    -> Result<Option<T>, Error>;

fn cdf(&self, split_points: &[T], criteria: SearchCriteria)
    -> Result<Option<Vec<f64>>, Error>;

T-Digest rank is slightly different from generic REQ rank because NaN is an invalid input, so its natural shape is also Result<Option<f64>, Error>. min_value and max_value should remain plain Option: that matches collection-style Rust APIs and there is no separate invalid argument to report.

Arguments should be validated before checking whether the sketch is empty. Otherwise the same invalid rank would return None on an empty sketch and Err(InvalidArgument) after the first update, making validation depend on unrelated state. With Result<Option<_>>, the deterministic contract is:

• invalid argument: Err(InvalidArgument);
• valid argument plus empty sketch: Ok(None);
• valid argument plus non-empty sketch: Ok(Some(value)).

The main cost of A is nested handling. In practice, ? removes the Result layer cleanly and the remaining Option is the state the caller genuinely needs to handle:

let Some(value) = sketch.quantile(rank)? else {
    // no observations yet
    return Ok(...);
};

I would not recommend B as the primary model. EmptySketch would provide a single return layer and mirror the Java/C++ exception distinction, but it would make a normal, serializable, mergeable sketch state exceptional and enlarge the crate-wide error taxonomy mainly to avoid one level of nesting. We may still want separate kinds such as IncompatibleSketch or CapacityExceeded elsewhere, but that is independent of query absence.

C keeps the current T-Digest API compact, but ranks and split points are commonly supplied by users, configuration, or query engines. Requiring every caller to duplicate prevalidation to avoid a process-level panic is a poor library boundary. D is attractive for workloads that reuse validated ranks, especially batch queries, but a public NormalizedRank plus generic split-point wrappers adds substantial API surface. It can remain a future ergonomic layer without being required to settle the base contract.

For scope, I would first apply this policy to distribution-query families (T-Digest, REQ, and KLL) and to their sorted views. It should not be imposed mechanically on unrelated families: for example, an empty membership sketch can still answer membership queries, and an intersection that has not received its first input has its own existing state semantics.

Since changing the existing REQ and T-Digest signatures is breaking, the cleanest path before 1.0 is to make the change once in a coordinated release. If an additive transition is needed first, T-Digest can gain checked try_* query methods while retaining the documented panic wrappers temporarily. I would avoid inventing asymmetric names such as quantile_opt for REQ solely to postpone the breaking change; that would leave the inconsistency in the long-term API.