Skip to content

Implement Spark-compatible percentile_cont #182

Open

Description

@andygrove

Part of #173 and apache/datafusion-comet#7300.

What the function does

percentile_cont(percentage) WITHIN GROUP (ORDER BY col [ASC|DESC]) returns the percentile of a numeric or ANSI
interval column, interpolated from a continuous distribution. It is a RuntimeReplaceableAggregate that rewrites to
Percentile(col, percentage, frequency = 1L, reverse = <DESC>). Its value semantics, input casts and return type are
therefore those of percentile. The result is DOUBLE for numeric col and the same interval kind (truncated) for
interval col. The result is nullable, and empty or all-NULL groups give NULL.

percentage must be foldable, non-NULL and in [0.0, 1.0]. It can also be an array, which returns an array, because
the replacement accepts the array form. Exactly one ORDER BY item is required. DESC sorts the values in reverse
before the same interpolation is applied. DISTINCT is rejected, and so is a window spec containing ORDER BY or a
frame. PARTITION BY windows are allowed.

Since 4.0.0 as a registered function (PercentileContBuilder). In 3.4 / 3.5 the same syntax is available only as a
parser rule (see version differences).

Examples

SELECT percentile_cont(0.25) WITHIN GROUP (ORDER BY col) FROM VALUES (0), (10) AS tab(col);
-- 2.5
SELECT percentile_cont(0.25) WITHIN GROUP (ORDER BY col)
FROM VALUES (INTERVAL '0' MONTH), (INTERVAL '10' MONTH) AS tab(col);
-- 0-2

-- 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
  percentile_cont(0.25) WITHIN GROUP (ORDER BY v),
  percentile_cont(0.25) WITHIN GROUP (ORDER BY v) FILTER (WHERE k > 0),
  percentile_cont(0.25) WITHIN GROUP (ORDER BY v DESC),
  percentile_cont(0.25) WITHIN GROUP (ORDER BY v DESC) FILTER (WHERE k > 0)
FROM aggr;
-- 10.0  15.0  30.0  27.5

SELECT k, percentile_cont(0.25) WITHIN GROUP (ORDER BY v),
          percentile_cont(0.25) WITHIN GROUP (ORDER BY v DESC)
FROM aggr GROUP BY k ORDER BY k;
-- 0  10.0  30.0
-- 1  12.5  17.5
-- 2  17.5  26.25
-- 3  60.0  60.0
-- 4  NULL  NULL

-- Same view: median(v), percentile(v, 0.5) and percentile_cont(0.5) WITHIN GROUP (ORDER BY v) all return 20.0.

-- Interval column (percentiles.sql.out, view intervals): dt is a YEAR-MONTH interval
SELECT percentile_cont(0.25) WITHIN GROUP (ORDER BY dt),
       percentile_cont(0.25) WITHIN GROUP (ORDER BY dt DESC) FROM intervals;
-- 0-10  2-6

Edge cases to test

  • Empty input and all-NULL groups give NULL (group k = 4 above). A single row gives that value. FILTER (WHERE ...)
    that removes every row gives NULL.
  • DESC is not simply 1 - p. Spark reverses the sort and computes pos = (n - 1) * p on the reversed sequence, which
    produces 26.25 for k = 2 above. Compare bit for bit with 1 - p on the ascending sequence. The two can differ in
    the last ulp.
  • Interpolation is (hi - pos) * lo + (pos - lo) * hi in f64 (see the percentile issue for the
    2012.2999999999997 case).
  • Errors (all analysis-time; names from percentiles.sql.out / error-conditions.json):
    • percentile_cont(DISTINCT 0.5) WITHIN GROUP (...) raises INVALID_WITHIN_GROUP_EXPRESSION.DISTINCT_UNSUPPORTED
      ("The function does not support DISTINCT with WITHIN GROUP.").
    • percentile_cont(0.5) without WITHIN GROUP raises INVALID_WITHIN_GROUP_EXPRESSION.WITHIN_GROUP_MISSING.
    • WITHIN GROUP (ORDER BY k, v) raises INVALID_WITHIN_GROUP_EXPRESSION.WRONG_NUM_ORDERINGS.
    • percentile_cont() or percentile_cont(k, 0.5) raises WRONG_NUM_ARGS.WITHOUT_SUGGESTION.
    • A non-literal percentage (percentile_cont(b) WITHIN GROUP (ORDER BY a DESC)) raises
      DATATYPE_MISMATCH.NON_FOLDABLE_INPUT.
    • NULL or out-of-range percentage raises DATATYPE_MISMATCH.UNEXPECTED_NULL / VALUE_OUT_OF_RANGE.
    • OVER (... ORDER BY ...) or OVER (... ROWS BETWEEN ...) raises INVALID_WINDOW_SPEC_FOR_AGGREGATION_FUNC.
  • Window use: OVER (PARTITION BY department) and a named WINDOW w AS (PARTITION BY ...) are both covered in
    percentiles.sql.out (basic_pays cases).
  • Interval inputs: day-time results are microseconds truncated with toLong, and year-month results are months
    truncated with toInt. percentiles.sql.out gives 0 00:00:26.250000000 (k = 2, DESC, SECOND column) and
    0 00:26:15.000000000 (MINUTE column).
  • NULLS FIRST / NULLS LAST in the sort item have no effect because NULLs are dropped.
  • NaN, -0.0 and +/-Infinity: same considerations as percentile (NaN sorts largest, so with DESC it sorts first).
  • Merge path: the state is a value-to-count map, so the result does not depend on partitioning.

Differences across Spark versions

  • 3.4 / 3.5: PERCENTILE_CONT / PERCENTILE_DISC are keywords handled by a dedicated parser rule (#percentile in
    SqlBaseParser.g4, AstBuilder.visitPercentile). percentile_cont(...) is not in FunctionRegistry. The grammar
    has no DISTINCT, so it is a parse error rather than DISTINCT_UNSUPPORTED. FILTER and OVER are supported.
    Results in percentiles.sql.out are the same as in 4.x.
  • 4.0+: registered through PercentileContBuilder with SupportsOrderingWithinGroup. The new
    INVALID_WITHIN_GROUP_EXPRESSION.* errors apply.
  • No calculation change from 4.0 to 4.2.

Implementation notes

  • Spark: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/percentiles.scala
    (PercentileCont, PercentileContBuilder, and Percentile / PercentileBase for the computation).

  • DataFusion core has percentile_cont(p) WITHIN GROUP (ORDER BY x)
    (datafusion/functions-aggregate/src/percentile_cont.rs, alias quantile_cont). It differs from Spark in these ways:

    • It quantizes the interpolation weight to 1e-6 and computes lo + (hi - lo) * w.
    • It returns the input type (decimal stays decimal, not DOUBLE).
    • It implements DESC as 1 - p.
    • It supports DISTINCT, while Spark rejects it.
    • It does not support interval input or an array of percentages.

    So core cannot be reused directly.

  • Implement this on top of the Spark percentile accumulator (separate issue), adding a reverse flag. In
    datafusion-spark the WITHIN GROUP ordering is passed to the UDAF (supports_within_group_clause), and
    AccumulatorArgs::order_bys gives the direction. Module: crates/spark/src/function/aggregate/.

  • Tests: add crates/sqllogictest/test_files/aggregate/percentile_cont.slt (the aggr and basic_pays 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