Skip to content

Implement Spark-compatible percentile_disc #183

Open

Description

@andygrove

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

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions