apache / apache/datafusion

`approx_percentile_cont` with a large `centroids` argument panics with "capacity overflow"

Open
#24,900 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Describe the bug

`TDigest::merge_sorted_f64` and `TDigest::merge_digests` (`datafusion/functions-aggregate-common/src/tdigest.rs`) allocate the compressed centroid list with `Vec::with_capacity(max_size)`. `max_size` is the user supplied `centroids` argument of `approx_percentile_cont`, which `validate_input_max_size_expr` accepts for any positive integer. A large value therefore panics inside `Vec::with_capacity` (or aborts the process on allocation failure for values that fit but are still huge).

### To Reproduce

```sql
SELECT approx_percentile_cont(x, 0.5, 9223372036854775807) FROM (VALUES (1), (2)) t(x);
```

```text
thread 'main' panicked at library/alloc/src/raw_vec/mod.rs:28:5:
capacity overflow
```

### Expected behavior

The query returns a result. The compressed digest can never hold more centroids than the inputs being merged, so the allocation should be bounded by the input size rather than by `max_size` alone.

### Additional context

Found while running a corpus of extreme-value literals against a debug build of `datafusion-cli`.

Contributor guide

Open the contributing guide

Research direction

Start in datafusion/functions-aggregate-common/src/tdigest.rs at TDigest::merge_sorted_f64 and TDigest::merge_digests, then trace validate_input_max_size_expr for approx_percentile_cont. Reproduce the issue with the SQL query in the report and verify that an extreme positive centroids value no longer panics while the query still returns a result.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust, sql
Domain
databases
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
78/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.