Incorrect approx_percentile / approx_median results for small datasets due to unnecessary t-digest interpolation

[aryan-212]

Describe the bug

DataFusion’s approx_percentile_cont and approx_median use a t-digest internally. However, when the number of input rows is small enough that no centroid compression occurs, each centroid represents exactly one data point (weight = 1).

In this scenario, the t-digest interpolation step is still applied, even though it assumes centroids represent clusters of multiple points. This leads to incorrect results that:

• Do not match exact continuous percentiles (percentile_cont)
• Do not match expected discrete nearest-rank semantics (as in Databricks)
• Drift away from actual observed values

This behavior is particularly surprising for small datasets and unit tests, where users expect percentile outputs to correspond to real data points.

To Reproduce

Steps to reproduce the behavior:

Create a small dataset (e.g., TPC-DS call_center table with ~14 rows)

Run:

select approx_percentile(cc_sq_ft, 0.85) from call_center;

Observe the output

Another example:

select approx_median(value)
from (values (-85), (-72), (-56), (-48), (-43), (-25), (-12), (-5), (45), (83)) t(value);

Expected behavior

For small datasets where no t-digest compression occurs:

Results should follow nearest-rank semantics (e.g., ceil(q * n) - 1)
Returned values should be actual observed data points
Behavior should align with systems like Databricks (percentile_approx)

Examples:

• approx_percentile(cc_sq_ft, 0.85) → 84336
• approx_median(...) → should return a valid input value (not interpolated like -32)

Additional context

Currently, DataFusion applies t-digest interpolation even when:

number_of_centroids == number_of_input_rows

This indicates no compression has occurred, making interpolation both unnecessary and incorrect.

The issue stems from using the interpolation path in estimate_quantile regardless of centroid structure. In the no-compression regime, the algorithm should instead switch to an exact nearest-rank computation.

This inconsistency leads to unintuitive and incorrect results, especially in:

• Small datasets
• Window functions with small frame sizes
• Unit tests expecting deterministic outputs

[asolimando]

I don't think this is necessarily a bug, there are two types of semantics for similar approximate UDFs in SQL (you can see a similar description in Postgres' doc for the non-approx functions):

• discrete: where you are guaranteed to have output values from the universe of input values,
• continuous: where any intermediate value can be used and expected.

The _cont suffix in approx_percentile_cont explicitly mirrors SQL's percentile_cont which is interpolating, and approx_median is an alias for approx_percentile_cont(0.5), so the same argument applies.

Note also that the same behaviour applies to percentile_cont, that is not an approximation and doesn't even use t-digest, it's part of the contract of such functions.

Switching between the two semantics based on the amount of values doesn't seem desirable, this is part of the contract of the function, independently from the values you feed to it.

You cite determinism, and I agree that's a property we must preserve, but that's orthogonal to discrete vs continuous, and I believe that results are still deterministic even when compression kicks in, so unless you can reproduce a non-deterministic example, I'd remove that from the current discussion.

What I suggest is to open an issue to introduce an approx_percentile_disc function and discuss the best way to keep the discrete behaviour even under approximation (possibly building on top approx_percentile_cont with a post-processing step to match the discrete semantics).

WDYT?