Skip to content

Implement Spark-compatible approx_percentile / percentile_approx #184

Open

Description

@andygrove

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

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.

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):

    Spark uses Greenwald-Khanna quantile summaries, so results match only if the algorithm is ported exactly.

    (This was tracked in #169, 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