[jira] [Updated] (SPARK-60196) Optimize DataFrame nearest ASOF scans and support DATE/TIMESTAMP keys

["Nikolina Vraneš (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/SPARK-60196?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Nikolina Vraneš updated SPARK-60196:
------------------------------------
    Description: 
This issue covers DataFrame ASOF joins (joinAsOf / _joinAsOf) when spark.sql.join.sortMergeAsOfJoin.enabled=true. The public pandas-on-Spark merge_asof API also uses this path.

h3. Why

For each left row, the nearest scan starts at the beginning of the sorted right group and evaluates a distance for each eligible row until the distance stops decreasing. Instead, use key comparisons to find the closest eligible predecessor and successor, then compare their two gaps. Eligibility includes tolerance, excluded exact matches and residual ON conditions.

The old stopping rule can miss closer rows after duplicate keys: left key 10 and right keys [1, 1, 9] stop at the second 1 before reaching 9. Distance arithmetic can also overflow or round unequal gaps into a tie. For DOUBLE left key 1.0 and right keys -1.0e20 and 1.0e20, both DOUBLE gaps round to 1.0e20 although the positive right key is closer.

DATE/TIMESTAMP DataFrame joins fail during planning because analysis rewrites subtraction to SubtractDates / SubtractTimestamps, which the planner does not recognize. Mixed LTZ/NTZ keys also need a guard: subtraction and comparison coerce them differently, so sorting can disagree with matching around DST.

Nearest STRING keys compare as text but subtract as numbers. These orderings disagree for values such as "10" and "2". With ANSI off, non-numeric strings produce NULL distances, which the fallback's MIN_BY ignores. Reject nearest STRING keys in sort-merge planning.

h3. Changes

* Find the nearest eligible candidate on each side and compare exact gaps. Exact matches win when allowed; equal gaps prefer the predecessor.
* Support DATE, TIMESTAMP, TIMESTAMP_NTZ and DATE/TIMESTAMP key pairs in DataFrame sort-merge planning for all three directions.
* Read the nearest scanner's keys from the planner's sort expressions, including swapped and constant keys. TIMESTAMP nearest gaps measure elapsed time.
* Reject mixed LTZ/NTZ DataFrame keys during analysis when sort-merge is enabled, and reject nearest STRING keys during sort-merge planning.

Each left row still scans the right group from its start, so worst-case work remains O(left rows * right rows). Performance has not been benchmarked.

h3. Testing

Regression coverage includes numeric precision and overflow, duplicate keys, DATE and timestamp combinations, nanosecond keys, tolerance, excluded exact matches, residual conditions, spilling, both analyzers and the nearest scan's early stop.

PR: https://github.com/apache/spark/pull/59479


  was:
DataFrame sort-merge ASOF joins fail during planning with DATE and TIMESTAMP keys. Nearest joins can also select the wrong row when distance arithmetic overflows or rounds, or when the scan stops at duplicate keys.

h3. Changes

* Support DATE, TIMESTAMP, TIMESTAMP_NTZ and DATE/TIMESTAMP key pairs in sort-merge planning for all three directions.
* Compare nearest gaps using exact key values to avoid integral overflow, decimal precision loss and floating-point rounding. TIMESTAMP gaps measure elapsed time.
* Keep the closest eligible predecessor and stop at the first eligible successor. Exact matches win when allowed, and equal gaps prefer the predecessor.
* Read the nearest scanner's keys from the planner's sort expressions, including swapped and constant ASOF keys.
* Reject mixed TIMESTAMP_LTZ/TIMESTAMP_NTZ key families during analysis when sort-merge ASOF is enabled, because sorting and comparison can otherwise disagree around daylight saving time transitions.

h3. Testing

Regression coverage includes numeric precision and overflow, DATE and timestamp combinations, nanosecond keys, tolerance, excluded exact matches, residual conditions, spilling, both analyzers and the nearest scan's early stop.

        Summary: Optimize DataFrame nearest ASOF scans and support DATE/TIMESTAMP keys  (was: Fix nearest matching and support DATE/TIMESTAMP keys in sort-merge ASOF joins)

> Optimize DataFrame nearest ASOF scans and support DATE/TIMESTAMP keys
> ---------------------------------------------------------------------
>
>                 Key: SPARK-60196
>                 URL: https://issues.apache.org/jira/browse/SPARK-60196
>             Project: Spark
>          Issue Type: Bug
>          Components: SQL
>    Affects Versions: 5.0.0
>            Reporter: Nikolina Vraneš
>            Priority: Major
>              Labels: pull-request-available
>
> This issue covers DataFrame ASOF joins (joinAsOf / _joinAsOf) when spark.sql.join.sortMergeAsOfJoin.enabled=true. The public pandas-on-Spark merge_asof API also uses this path.
> h3. Why
> For each left row, the nearest scan starts at the beginning of the sorted right group and evaluates a distance for each eligible row until the distance stops decreasing. Instead, use key comparisons to find the closest eligible predecessor and successor, then compare their two gaps. Eligibility includes tolerance, excluded exact matches and residual ON conditions.
> The old stopping rule can miss closer rows after duplicate keys: left key 10 and right keys [1, 1, 9] stop at the second 1 before reaching 9. Distance arithmetic can also overflow or round unequal gaps into a tie. For DOUBLE left key 1.0 and right keys -1.0e20 and 1.0e20, both DOUBLE gaps round to 1.0e20 although the positive right key is closer.
> DATE/TIMESTAMP DataFrame joins fail during planning because analysis rewrites subtraction to SubtractDates / SubtractTimestamps, which the planner does not recognize. Mixed LTZ/NTZ keys also need a guard: subtraction and comparison coerce them differently, so sorting can disagree with matching around DST.
> Nearest STRING keys compare as text but subtract as numbers. These orderings disagree for values such as "10" and "2". With ANSI off, non-numeric strings produce NULL distances, which the fallback's MIN_BY ignores. Reject nearest STRING keys in sort-merge planning.
> h3. Changes
> * Find the nearest eligible candidate on each side and compare exact gaps. Exact matches win when allowed; equal gaps prefer the predecessor.
> * Support DATE, TIMESTAMP, TIMESTAMP_NTZ and DATE/TIMESTAMP key pairs in DataFrame sort-merge planning for all three directions.
> * Read the nearest scanner's keys from the planner's sort expressions, including swapped and constant keys. TIMESTAMP nearest gaps measure elapsed time.
> * Reject mixed LTZ/NTZ DataFrame keys during analysis when sort-merge is enabled, and reject nearest STRING keys during sort-merge planning.
> Each left row still scans the right group from its start, so worst-case work remains O(left rows * right rows). Performance has not been benchmarked.
> h3. Testing
> Regression coverage includes numeric precision and overflow, duplicate keys, DATE and timestamp combinations, nanosecond keys, tolerance, excluded exact matches, residual conditions, spilling, both analyzers and the nearest scan's early stop.
> PR: https://github.com/apache/spark/pull/59479



--
This message was sent by Atlassian Jira
(v8.20.10#820010)

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