[
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: [email protected]
For additional commands, e-mail: [email protected]
