andygrove opened a new issue, #184:
URL: https://github.com/apache/datafusion-spark/issues/184
Part of #173 and apache/datafusion-comet#7300.
### What the function does
`percentile_approx(col, percentage [, accuracy])` (alias
`approx_percentile`) returns an approximate percentile using a
Greenwald-Khanna quantile summary (`QuantileSummaries`) with relative error
`1.0 / accuracy`. The result is a value
from the input column: the smallest value such that no more than
`percentage` of the values are less than or equal to
it. `percentage` is a foldable `DOUBLE` or `ARRAY<DOUBLE>` in `[0.0, 1.0]`.
`accuracy` is a foldable integral literal
in `(0, 2147483647]` (default 10000). Since 2.1.0.
Accepted `col` types are `NUMERIC`, `DATE`, `TIMESTAMP`, `TIMESTAMP_NTZ`,
`INTERVAL YEAR TO MONTH` and
`INTERVAL DAY TO SECOND`. Every value is converted to `double` for the
summary.
The result type is the input type. The double result is cast back with
`toByte`, `toShort`, `toInt`, `toLong`,
`toFloat` or `Decimal(_)`. Date and year-month interval results go through
`toInt`; timestamp and day-time interval
results go through `toLong`. If `percentage` is an array, the result is
`ARRAY<input type>` (`containsNull = false`).
The result is nullable, and empty or all-NULL input gives NULL. `prettyName`
follows the name used, so result columns
show `percentile_approx(...)` or `approx_percentile(...)`.
### Examples
```sql
SELECT percentile_approx(col, array(0.5, 0.4, 0.1), 100) FROM VALUES (0),
(1), (2), (10) AS tab(col);
-- [1,1,0]
SELECT percentile_approx(col, 0.5, 100) FROM VALUES (0), (6), (7), (9), (10)
AS tab(col);
-- 7
SELECT percentile_approx(col, 0.5, 100)
FROM VALUES (INTERVAL '0' MONTH), (INTERVAL '1' MONTH), (INTERVAL '2'
MONTH), (INTERVAL '10' MONTH) AS tab(col);
-- 0-1
SELECT percentile_approx(col, array(0.5, 0.7), 100)
FROM VALUES (INTERVAL '0' SECOND), (INTERVAL '1' SECOND), (INTERVAL '2'
SECOND), (INTERVAL '10' SECOND) AS tab(col);
-- [0 00:00:01.000000000,0 00:00:02.000000000]
-- count.sql.out; testData.a = 1, 1, 2, 1, NULL, 1, NULL. Result type is INT.
SELECT count(distinct 0.8), percentile_approx(distinct a, 0.8) FROM testData;
-- 1 2
-- ApproximatePercentileQuerySuite, col = 1..1000 (INT)
SELECT percentile_approx(col, 0.25), percentile_approx(col, 0.5),
percentile_approx(col, 0.75d),
percentile_approx(col, 0.0), percentile_approx(col, 1.0) FROM t;
-- 250 500 750 1 1000
-- col = 1..10: percentile_approx(col, array(0.01, 0.1, 0.11)) -> [1,1,2]
SELECT ROUND(PERCENTILE_APPROX(2150 / 1000.0, 0.95), 3);
-- 2.15 (SPARK-54750 regression: used to return NULL for some decimal
values)
```
### Edge cases to test
- Empty input with no `GROUP BY` returns one row of NULL. With `GROUP BY`
there are no rows. `percentile_approx(NULL, 0.5)`
returns NULL per group. NULL rows are skipped.
- `accuracy` NULL raises `DATATYPE_MISMATCH.UNEXPECTED_NULL` (`exprName` =
`accuracy`), and `percentage` NULL raises
the same with `exprName` = `percentage` (SPARK-45079 tests). `accuracy <=
0` or `> Int.MaxValue` raises
`DATATYPE_MISMATCH.VALUE_OUT_OF_RANGE` with `(0, 2147483647]`. A
percentage outside `[0, 1]` raises
`VALUE_OUT_OF_RANGE` with `[0.0, 1.0]`. Non-literal percentage or accuracy
raises `DATATYPE_MISMATCH.NON_FOLDABLE_INPUT`.
These are all analysis errors.
- Constant folding is applied: `percentile_approx(col, array(0.25 + 0.25D),
200 + 800)` over 1..1000 gives `[500]`.
- Percentages `<= relativeError` return the minimum sample, and percentages
`>= 1 - relativeError` return the maximum
sample. This path is separate from the rank search.
- Accuracy matters: SPARK-32908 expects `percentile_approx(col, 0.77,
1000|10000|100000|1000000)` to give
`18, 17, 17, 17` on its test file. The error bound test requires `|result
- exact| <= floor(n / accuracy)`.
- Result cast back to input type: integer types truncate (`toInt`), `FLOAT`
narrows, and `DECIMAL` is rebuilt from the
double. Check the decimal precision / scale of the result and the
SPARK-54750 case.
- `DATE`, `TIMESTAMP`, `TIMESTAMP_NTZ` and both interval kinds
(`ApproximatePercentileQuerySuite` "different column
types", SPARK-37138).
- NaN, -0.0 and +/-Infinity as inputs. The summary uses `<` / `<=` on
doubles, so NaN placement follows those
comparisons, not SQL ordering.
- Input of at least 50,000 rows per partition: the head buffer
(`defaultHeadSize = 50000`) is flushed, and the summary
is compressed once `sampled.length >= 10000` (`defaultCompressThreshold`).
Cover single- and multi-partition plans.
- Merge path: the result depends on how rows are split into partial
aggregates and on merge order. `merge` adds
`floor(2 * relErr * count)` deltas and recompresses with threshold `2 *
relErr * mergedCount`.
`ApproximatePercentileQuerySuite` has a 4-partition case
(`1,1,2,1,1,3,1,1,4,1,1,5`) that must give `[1.0]`.
To match Spark exactly, port insert / compress / merge / query exactly.
The serialized buffer layout
(`compressThreshold` int, `relativeError` double, `count` long, `n` int,
then `n` x (`value` double, `g` long,
`delta` long), big-endian) matters only for engines that exchange partial
states with the JVM.
- `DISTINCT` is supported (generic distinct rewrite).
- Window use: `ApproximatePercentileQuerySuite` "works in window function".
### Differences across Spark versions
- `NON_FOLDABLE_INPUT` `inputName` is `percentage` / `accuracy` in 3.x and
`` `percentage` `` / `` `accuracy` `` in 4.x.
- Unexpected input types raise
`QueryExecutionErrors.dataTypeUnexpectedError` in 3.x and
`SparkException.internalError` in 4.x. These errors are internal only.
- The SPARK-54750 regression test is in 3.5.8, 4.0.4, 4.1.3 and 4.2.0 but
not in 3.4.3. Check the 3.4 behavior for
decimal input.
- The `QuantileSummaries` algorithm has not changed from 3.4.3 to 4.2.0.
### Implementation notes
- Spark:
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/ApproximatePercentile.scala`
(`ApproximatePercentile`, `PercentileDigest`,
`PercentileDigestSerializer`) and
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/util/QuantileSummaries.scala`.
- DataFusion core `approx_percentile_cont(p [, centroids]) WITHIN GROUP
(ORDER BY x)`
(`datafusion/functions-aggregate/src/approx_percentile_cont.rs`) uses a
t-digest (default 100 centroids) and
interpolates. It is a different algorithm, its third argument means
something else, and it handles DESC as `1 - p`.
Its results will not match Spark, so it cannot be reused.
- Write a new GK summary port in `crates/spark/src/function/aggregate/` (for
example `approx_percentile.rs`), registered
under both names. Comet already ships a native port of the same algorithm
for byte/short/int/long/float/double, which
is a useful reference. Decimal, date, timestamp and interval inputs still
need coverage.
- Tests: add
`crates/sqllogictest/test_files/aggregate/approx_percentile.slt` (the
`ExpressionDescription` examples,
the 1..1000 cases, and DISTINCT). Document with `#[user_doc]`.
---
_This issue was generated by an LLM (Claude) from the Apache Spark source
code and tests. Examples come from Spark's `ExpressionDescription` examples,
test suites and `.sql.out` golden files, but please verify them against Spark
before relying on them._
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]