You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by "Ma77Ball (via GitHub)" <gi...@apache.org> on 2026/07/14 05:47:27 UTC

[PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Ma77Ball opened a new pull request, #57241:
URL: https://github.com/apache/spark/pull/57241

   ### What changes were proposed in this pull request?
   
   The exact `percentile` aggregate interpolates linearly between the two values surrounding the target position. This changes that interpolation in `PercentileBase.getPercentile` from
   
   ```
   (higher - position) * lowerValue + (position - lower) * higherValue
   ```
   
   to the algebraically equivalent
   
   ```
   lowerValue + (position - lower) * (higherValue - lowerValue)
   ```
   
   The method is shared by `percentile`, `percentile_cont`, `median`, and their `WITHIN GROUP` forms.
   
   ### Why are the changes needed?
   
   The two forms are identical in exact arithmetic but differ under floating-point rounding. The old form scales both endpoint values (which can be very large) by the interpolation weights independently, so the two large products carry rounding error on the order of the spacing between adjacent `double`s. When that spacing exceeds the true difference between two nearby percentiles, the results round in inconsistent directions and the percentile stops being monotonically non-decreasing in the percentage.
   
   Reproduction:
   
   ```scala
   val df = (0 until 20).map(i => 1e18 + i * 128.0).toDF("x")
   df.selectExpr("percentile(x, 0.04) AS p04", "percentile(x, 0.05) AS p05").show(false)
   ```
   
   Before this change:
   
   ```
   +---------------------+------+
   |p04                  |p05   |
   +---------------------+------+
   |1.0000000000000001E18|1.0E18|
   +---------------------+------+
   ```
   
   Here `p04 > p05`, which is not monotonic. A negative interquartile range (`percentile(x, 0.75) - percentile(x, 0.25)`) is one user-visible consequence.
   
   The new form leaves the large magnitude in `lowerValue` untouched and scales only the small delta `(higherValue - lowerValue)`, so the rounding error is proportional to that small delta and the result stays non-decreasing in the fraction.
   
   ### Does this PR introduce _any_ user-facing change?
   
   Yes. Exact `percentile` / `percentile_cont` / `median` results may change in the last unit(s) in the last place for large-magnitude inputs, and are now non-decreasing as the percentage increases. After this change the reproduction above returns `p04 = p05 = 1.0000000000000001E18`. Results for normal-magnitude inputs are unchanged.
   
   ### How was this patch tested?
   
   - New regression test in `PercentileQuerySuite`: the reproduction above plus a 101-point sweep asserting the results are monotonically non-decreasing.
   - Existing `PercentileSuite`, `PercentileQuerySuite`, and the `percentiles.sql` golden-file suite pass unchanged (no result churn for normal-magnitude data).
   
   ### Was this patch authored or co-authored using generative AI tooling?
   
   Generated-by: Claude Code (Claude Opus 4.8)
   


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "Ma77Ball (via GitHub)" <gi...@apache.org>.
Ma77Ball commented on PR #57241:
URL: https://github.com/apache/spark/pull/57241#issuecomment-4994705958

   Thank you, @peter-toth and @yadavay-amzn, for reviewing and helping me finish my first contribution. I greatly appreciate your help. 
   
   JIRA ID: ma77ball


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #57241:
URL: https://github.com/apache/spark/pull/57241#issuecomment-4979753309

   Hey @Ma77Ball, thanks for the fix and quick iteration.
   Let me leave this PR open for one more day in case anyone else has any suggestions and then merge it tomorrow.


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "Ma77Ball (via GitHub)" <gi...@apache.org>.
Ma77Ball commented on PR #57241:
URL: https://github.com/apache/spark/pull/57241#issuecomment-4979646355

   Hello @peter-toth, thank you for the review. I've added the migration-guide bullet point as suggested under 4.2 to 4.3.


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #57241:
URL: https://github.com/apache/spark/pull/57241#issuecomment-4979380792

   The fix looks correct and the shape is right -- keeping it in the shared `getPercentile` covers `percentile` / `percentile_cont` / `median` and both `WITHIN GROUP` forms in one line, and `percentile_disc` / `percentile_approx` are untouched since they return observed values rather than interpolating.
   
   One thing the `DataFrameAggregateSuite` change surfaces: `percentile(year, 0.3)` on the `Java` group goes `2012.2999999999997` -> `2012.3`, i.e. this isn't only a large-value change -- ordinary inputs shift in the last ULP too. Since exact `percentile` / `percentile_cont` / `median` can now return a value that differs from earlier releases, it might be worth a `docs/sql-migration-guide.md` entry to call out the behavior change. It's only ~1 ULP and the new value is the more-correct one, so IMO no legacy config is needed -- just a note.
   
   IMO this reads more as a numerical-robustness improvement than a correctness bug fix: the old form was a standard, valid interpolation, results only move in the last ULP, and no documented monotonicity or exact-rounding guarantee is being broken. So shipping it in the next feature release without backporting to maintenance branches seems right.
   
   Suggested migration-guide bullet, under `## Upgrading from Spark SQL 4.2 to 4.3`:
   
   > - Since Spark 4.3, the exact `percentile`, `percentile_cont`, and `median` aggregate functions (including their `WITHIN GROUP (ORDER BY ...)` forms) compute the linear interpolation between two neighboring values as `lower + fraction * (higher - lower)` instead of `(1 - fraction) * lower + fraction * higher`. The two are equal in exact arithmetic, but the new form is monotonically non-decreasing in the requested percentage and avoids a rounding error the old form could introduce. As a result these functions may return a value that differs from earlier releases in the last ULP. `percentile_disc` and `percentile_approx` are unaffected.
   


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #57241:
URL: https://github.com/apache/spark/pull/57241#issuecomment-4991583309

   **Merge Summary:**
   - merged into master https://github.com/apache/spark/commit/73535081cbe5d0a572deac7a458d2db29f8ecb8f
   - merged into branch-4.x https://github.com/apache/spark/commit/d2d3a7546a66f9ba6c7273de836266e6132ef2a8
   
   *Posted by `merge_spark_pr.py`*


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth closed pull request #57241: [SPARK-57982][SQL] Make exact percentile monotonic for large values
URL: https://github.com/apache/spark/pull/57241


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "yadavay-amzn (via GitHub)" <gi...@apache.org>.
yadavay-amzn commented on code in PR #57241:
URL: https://github.com/apache/spark/pull/57241#discussion_r3584064925


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/percentiles.scala:
##########
@@ -224,7 +224,8 @@ abstract class PercentileBase
       toDoubleValue(lowerKey)
     } else {
       // Linear interpolation to get the exact percentile
-      (higher - position) * toDoubleValue(lowerKey) + (position - lower) * toDoubleValue(higherKey)
+      toDoubleValue(lowerKey) +
+        (position - lower) * (toDoubleValue(higherKey) - toDoubleValue(lowerKey))

Review Comment:
   Optional, non-blocking. Computing `higher - lower` here can overflow to Infinity when the two adjacent keys straddle zero with magnitudes near Double.MaxValue (e.g. lower=-9e307, higher=9e307 makes the delta overflow, so p50 comes back as Infinity where the old form returned a finite value). It's an extremely unlikely input and the old form had its own accuracy issues in that range, so I don't think it should block anything. Might be worth a one-line comment noting the tradeoff, or nothing at all. Your call.



-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "Yicong-Huang (via GitHub)" <gi...@apache.org>.
Yicong-Huang commented on PR #57241:
URL: https://github.com/apache/spark/pull/57241#issuecomment-4974433982

   cc @cloud-fan 


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "Ma77Ball (via GitHub)" <gi...@apache.org>.
Ma77Ball commented on code in PR #57241:
URL: https://github.com/apache/spark/pull/57241#discussion_r3584842882


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/percentiles.scala:
##########
@@ -224,7 +224,8 @@ abstract class PercentileBase
       toDoubleValue(lowerKey)
     } else {
       // Linear interpolation to get the exact percentile
-      (higher - position) * toDoubleValue(lowerKey) + (position - lower) * toDoubleValue(higherKey)
+      toDoubleValue(lowerKey) +
+        (position - lower) * (toDoubleValue(higherKey) - toDoubleValue(lowerKey))

Review Comment:
   Hello @yadavay-amzn, thank you for the review. I've added a comment noting the tradeoff so it's flagged if the overflow ever surfaces for values near Double.MaxValue.



-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "Ma77Ball (via GitHub)" <gi...@apache.org>.
Ma77Ball commented on PR #57241:
URL: https://github.com/apache/spark/pull/57241#issuecomment-4974407684

    Hi @MaxGekk/@peter-toth, PTAL at this small percentile monotonicity fix (SPARK-57982) when you get a chance? 


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-57982][SQL] Make exact percentile monotonic for large values [spark]

Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #57241:
URL: https://github.com/apache/spark/pull/57241#issuecomment-4991623839

   Thank you @Ma77Ball for the fix and congratulations to your first Apache Spark contribution!
   Please let me know your JIRA id so that I can assign https://issues.apache.org/jira/browse/SPARK-57982 to you.
   
   Thank you @yadavay-amzn for the review!


-- 
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org