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]

Reply via email to