Skip to content

Implement Spark-compatible percentile / median #181

Open

Description

@andygrove

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

What the function does

percentile(col, percentage [, frequency]) is an exact aggregate that returns the percentile of a numeric or ANSI
interval column at percentage, interpolating linearly between neighbouring values. percentage can be a single
value or an array of values. Every percentage must be foldable, non-NULL and in [0.0, 1.0]. frequency is an
optional integral column (default 1L) that gives a repeat count for each row. Since 2.1.0.

Input types (ImplicitCastInputTypes): col must be NUMERIC, INTERVAL DAY TO SECOND or INTERVAL YEAR TO MONTH.
STRING is implicitly cast to DOUBLE. BOOLEAN, DATE, TIMESTAMP, CALENDAR INTERVAL and VOID columns are
rejected. Numeric children are not cast. Each value is converted to double (Decimal.toDouble, Number.doubleValue)
only when the result is computed. percentage is cast to DOUBLE or ARRAY<DOUBLE>. frequency must be integral
(TINYINT..BIGINT). FLOAT/DOUBLE frequencies are rejected.

Return type: DOUBLE for numeric input. For interval input the result has the same interval kind, and the double
result is truncated with toInt / toLong. If percentage is an array, the result is ARRAY<that type> with
containsNull = false. The result is nullable, and an empty or all-NULL group returns NULL.
median(col) (since 3.4.0) is a RuntimeReplaceableAggregate that rewrites to percentile(col, 0.5), so implementing
percentile also covers median. percentile_cont / percentile_disc are tracked separately. They rewrite to the
same PercentileBase machinery.

Examples

SELECT percentile(col, 0.3) FROM VALUES (0), (10) AS tab(col);
-- 3.0
SELECT percentile(col, array(0.25, 0.75)) FROM VALUES (0), (10) AS tab(col);
-- [2.5,7.5]
SELECT percentile(col, 0.5) FROM VALUES (INTERVAL '0' MONTH), (INTERVAL '10' MONTH) AS tab(col);
-- 0-5
SELECT percentile(col, array(0.2, 0.5)) FROM VALUES (INTERVAL '0' SECOND), (INTERVAL '10' SECOND) AS tab(col);
-- [0 00:00:02.000000000,0 00:00:05.000000000]
SELECT median(col) FROM VALUES (0), (10) AS tab(col);
-- 5.0

-- From DataFrameAggregateSuite "percentile_like" (year values 2012, 2013):
SELECT percentile(y, 0.3) FROM VALUES (2012), (2013) AS t(y);
-- 2012.2999999999997   (formula is (hi - pos) * lo + (pos - lo) * hi, not lo + (hi - lo) * frac)
SELECT percentile(y, 0.3, 2) FROM VALUES (2012), (2013) AS t(y);
-- 2012.0
SELECT percentile(y, array(0.25, 0.75), 2) FROM VALUES (2012), (2013) AS t(y);
-- [2012.0,2013.0]
SELECT percentile(y, array(0.25, 0.75), 2) FROM VALUES (2012), (2012), (2013) AS t(y);
-- [2012.0,2012.75]

-- percentiles.sql.out, view aggr(k, v) with k=0: v in (0,10,20,30,40); k=4: v = NULL
SELECT k, median(v), percentile(v, 0.5) FROM aggr GROUP BY k ORDER BY k;
-- 0  20.0  20.0
-- 1  15.0  15.0
-- 2  22.5  22.5
-- 3  60.0  60.0
-- 4  NULL  NULL

Edge cases to test

  • Empty input and all-NULL groups return NULL. NULL col rows and NULL frequency rows are skipped.
    Rows with frequency = 0 are skipped. If every row has frequency 0 the result is NULL (PercentileSuite "null handling").
  • Negative frequency raises NEGATIVE_VALUES_IN_FREQUENCY_EXPRESSION (SQLSTATE 22003) at execution time:
    "Found the negative value in : , but expected a positive integral value."
  • Single row returns that value as a double for any percentage.
  • percentage NULL gives DATATYPE_MISMATCH.UNEXPECTED_NULL. An array containing NULL (array(0.1, null)) fails as
    UNEXPECTED_INPUT_TYPE. A non-literal percentage gives DATATYPE_MISMATCH.NON_FOLDABLE_INPUT. A value outside
    [0, 1] gives DATATYPE_MISMATCH.VALUE_OUT_OF_RANGE with valueRange [0.0, 1.0]. All of these are analysis
    errors.
  • Percentage exactly 0.0 / 1.0, and a percentage array whose order is not sorted. The output keeps the input order.
  • Interpolation formula: (higher - pos) * lower + (pos - lower) * upper in f64, where pos = (N - 1) * p and N
    is the sum of frequencies. The 2012.2999999999997 case above must match bit for bit.
  • Interval results are truncated, not rounded (0.25 of 0..10 months is 0-2). Also test negative intervals.
  • BIGINT values above 2^53 and DECIMAL(38, x) lose precision because each value goes through double.
  • NaN and -0.0: keys are compared with Spark's SQL ordering (NaN is largest, and -0.0 compares equal to 0.0), but
    the hash map keeps 0.0 and -0.0 as separate keys. DataFrameAggregateSuite SPARK-45599 expects
    percentile(val, 0.1) over [0.0, 2.0, 153.0, 168.0, 3252411229536261.0, 7.205759403792794e+16, 1.7976931348623157e+308, 0.25, NaN, NaN, -0.0, -128.0, NaN, NaN]
    to be -0.0. Infinity inputs can produce NaN or Inf through interpolation.
  • DISTINCT: percentile(DISTINCT col, p) is allowed and gives every distinct value a frequency of 1.
  • percentile(v, 0.5) WITHIN GROUP (ORDER BY v) raises INVALID_SQL_SYNTAX.FUNCTION_WITH_UNSUPPORTED_SYNTAX.
  • Use as a window aggregate (OVER (PARTITION BY ...)).
  • Partial/final merge: the buffer is a map from value to count, merged by adding counts, so the result does not depend
    on partitioning. The one exception is the order of keys that compare equal (0.0 / -0.0) after the stable sort.
    Test multi-partition input and compare with single-partition input.

Differences across Spark versions

  • 3.4.x: the OpenHashSet bug fixed by SPARK-45599 can drop 0.0 or -0.0 keys, so the result in the case above
    differs. The fix and test are present in 3.5.8 and later.
  • 3.4.x / 3.5.x: negative frequency raises _LEGACY_ERROR_TEMP_2013 ("Negative values found in ").
    4.0+ raises NEGATIVE_VALUES_IN_FREQUENCY_EXPRESSION, which adds the value.
  • NON_FOLDABLE_INPUT inputName is percentage in 3.x and `percentage` in 4.x.
  • Otherwise the calculation is the same from 3.4 to 4.2.

Implementation notes

  • Spark: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/percentiles.scala
    (PercentileBase, Percentile, Median). The buffer is an OpenHashMap[AnyRef, Long]
    (TypedAggregateWithHashMapAsBuffer). eval sorts the keys, builds cumulative counts, and binary-searches
    lower + 1 / higher + 1.

  • DataFusion core has percentile_cont and median in datafusion/functions-aggregate/src/percentile_cont.rs and
    median.rs. They use index = p * (n - 1), but they differ from Spark in several ways:

    • Interpolation is lower + (upper - lower) * weight, with the weight quantized to 1e-6 (INTERPOLATION_PRECISION).
    • The return type follows the input type (decimals stay decimal) instead of always being DOUBLE.
    • There is no frequency argument, no array of percentages, and no interval input.
    • p == 0 / p == 1 take a special path.

    Write a new accumulator rather than wrapping core. Comet currently maps only the single-percentage numeric form to
    core percentile_cont.

  • Belongs in crates/spark/src/function/aggregate/ (new percentile.rs), next to avg.rs / try_sum.rs. Also
    register median as an alias-style wrapper, or document that callers rewrite it. A value-to-count state lets
    percentile_cont / percentile_disc reuse the same accumulator with a reverse flag and a discrete getPercentile.

  • Tests: add crates/sqllogictest/test_files/aggregate/percentile.slt. 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.

Activity

  1. andygrove commented on Nov 15, 2026

    @andygrove
    MemberAuthor

    Note

    An LLM (Claude Code) wrote this comment. Check the details before you rely on them.

    Apache DataFusion Comet already has a native, Spark-compatible implementation of this, which can be ported here along with its tests. Comet source (at 3878424d9):

    (This was tracked in #168, now closed as a duplicate.)

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