andygrove opened a new issue, #183:
URL: https://github.com/apache/datafusion-spark/issues/183

   Part of #173 and apache/datafusion-comet#7300.
   
   ### What the function does
   
   `percentile_disc(percentage) WITHIN GROUP (ORDER BY col [ASC|DESC])` returns 
a value that actually occurs in the input:
   the smallest value (in the requested sort order) whose `cume_dist()` is at 
least `percentage`. `PercentileDisc`
   extends `PercentileBase` with `frequency = 1L`. `col` must be `NUMERIC`, 
`INTERVAL DAY TO SECOND` or
   `INTERVAL YEAR TO MONTH` (`STRING` is implicitly cast to `DOUBLE`). 
`percentage` is a foldable `DOUBLE` in
   `[0.0, 1.0]`. The array form is also accepted by `PercentileBase` and 
returns an array.
   
   Return type: `DOUBLE` for numeric input, so the value is converted to double 
even for integer or decimal input. For
   interval input the result has the same interval kind. The result is 
nullable, and empty or all-NULL groups give NULL.
   `DISTINCT` is rejected. Exactly one `ORDER BY` item is required.
   
   Since 4.0.0 as a registered function (`PercentileDiscBuilder`). In 3.4 / 3.5 
the syntax is only a parser rule.
   
   ### Examples
   
   ```sql
   SELECT percentile_disc(0.25) WITHIN GROUP (ORDER BY col) FROM VALUES (0), 
(10) AS tab(col);
   -- 0.0
   SELECT percentile_disc(0.25) WITHIN GROUP (ORDER BY col)
   FROM VALUES (INTERVAL '0' MONTH), (INTERVAL '10' MONTH) AS tab(col);
   -- 0-0
   
   -- percentiles.sql.out, view aggr(k, v):
   --   
(0,0),(0,10),(0,20),(0,30),(0,40),(1,10),(1,20),(2,10),(2,20),(2,25),(2,30),(3,60),(4,NULL)
   SELECT k, percentile_disc(0.25) WITHIN GROUP (ORDER BY v),
             percentile_disc(0.25) WITHIN GROUP (ORDER BY v DESC)
   FROM aggr GROUP BY k ORDER BY k;
   -- 0  10.0  30.0
   -- 1  10.0  20.0
   -- 2  10.0  30.0
   -- 3  60.0  60.0
   -- 4  NULL  NULL
   
   -- p = 0.0, 0.1, ..., 1.0 (percentiles.sql.out)
   -- FROM VALUES (0), (1)                -> 0.0 0.0 0.0 0.0 0.0 0.0 1.0 1.0 
1.0 1.0 1.0
   -- FROM VALUES (0), (1), (2)           -> 0.0 0.0 0.0 0.0 1.0 1.0 1.0 2.0 
2.0 2.0 2.0
   -- FROM VALUES (0), (1), (2), (3), (4) -> 0.0 0.0 0.0 1.0 1.0 2.0 2.0 3.0 
3.0 4.0 4.0
   -- same, with spark.sql.legacy.percentileDiscCalculation=true
   --                                     -> 0.0 0.0 0.0 1.0 1.0 2.0 2.0 2.0 
3.0 3.0 4.0
   
   -- postgreSQL/aggregates_part4.sql.out (tenk1.thousand)
   SELECT percentile_disc(0.5) WITHIN GROUP (ORDER BY thousand) FROM tenk1;
   -- 499.0
   ```
   
   ### Edge cases to test
   
   - Algorithm (non-legacy): `N` is the row count, `higher = ceil(N * p)`, and 
the result is the first sorted key whose
     cumulative count is at least `higher`. For `p = 0` that is the first key.
   - `spark.sql.legacy.percentileDiscCalculation` (internal, default `false`, 
added in 3.3.4) switches to the old algorithm,
     which uses `percentile_cont` positions without interpolation (`pos = (N - 
1) * p`, take the lower key). The legacy row
     above shows where the two differ (p = 0.7 and p = 0.9). The flag is read 
when the expression is constructed.
   - `DESC` reverses the sort and then applies the same algorithm. It is not `1 
- p` on the ascending sequence: when
     `N * p` is an integer the two differ. From the code, 
`percentile_disc(0.25) WITHIN GROUP (ORDER BY v DESC)` over
     `(1),(2),(3),(4)` picks the 1st largest value (`4.0`), but 
`percentile_disc(0.75)` ascending picks the 3rd smallest
     (`3.0`).
   - Empty input, all-NULL groups, and a `FILTER` that removes every row give 
NULL. A single row gives that value as double
     for every `p` (first p-sweep row above).
   - Duplicates: each distinct value is stored once with a count, so ties are 
handled through cumulative counts.
   - Integer / decimal input is returned as `DOUBLE`. `BIGINT` values above 
2^53 and wide decimals lose precision. Interval
     input is returned exactly (`0-10` / `2-6` for the `intervals` view `dt` 
column).
   - NaN sorts largest, and `-0.0` / `0.0` compare equal but are separate keys 
(see the `percentile` issue).
   - Errors are the same as `percentile_cont`:
     - `INVALID_WITHIN_GROUP_EXPRESSION.DISTINCT_UNSUPPORTED`
     - `INVALID_WITHIN_GROUP_EXPRESSION.WITHIN_GROUP_MISSING`
     - `INVALID_WITHIN_GROUP_EXPRESSION.WRONG_NUM_ORDERINGS`
     - `WRONG_NUM_ARGS.WITHOUT_SUGGESTION`
     - `DATATYPE_MISMATCH.NON_FOLDABLE_INPUT` / `UNEXPECTED_NULL` / 
`VALUE_OUT_OF_RANGE` for the percentage
     - `INVALID_WINDOW_SPEC_FOR_AGGREGATION_FUNC` for windows with `ORDER BY` 
or a frame
   - Window use with `OVER (PARTITION BY ...)` (`basic_pays` cases in 
`percentiles.sql.out`, e.g. IT department
     `5186.0` ascending and `8113.0` DESC).
   - Merge path: the state is a value-to-count map merged by adding counts, so 
the result is independent of partitioning.
   
   ### Differences across Spark versions
   
   - 3.4 / 3.5: parser-only syntax (`#percentile` rule in `SqlBaseParser.g4`, 
`AstBuilder.visitPercentile`). There is no
     `FunctionRegistry` entry, and `DISTINCT` is a parse error.
   - 4.0+: `PercentileDiscBuilder` and `SupportsOrderingWithinGroup`, with the 
`INVALID_WITHIN_GROUP_EXPRESSION.*` errors.
   - The non-legacy algorithm and the legacy flag are the same in 3.4.3 through 
4.2.0.
   
   ### Implementation notes
   
   - Spark: 
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/percentiles.scala`
     (`PercentileDisc.getPercentile`, `PercentileDiscBuilder`, 
`PercentileBase`).
   - DataFusion core has no `percentile_disc`. Core `percentile_cont` / 
`approx_percentile_cont` are not usable here.
   - Share the value-to-count accumulator with the Spark `percentile` / 
`percentile_cont` implementations (separate
     issues), using a `discrete` flag and a `reverse` flag from the `WITHIN 
GROUP` sort direction
     (`AccumulatorArgs::order_bys`, `supports_within_group_clause`). Module: 
`crates/spark/src/function/aggregate/`.
   - Tests: add `crates/sqllogictest/test_files/aggregate/percentile_disc.slt`. 
The p-sweep and `aggr` cases from
     `percentiles.sql.out` port directly. 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