Jungtaek Lim created SPARK-61381:
------------------------------------

             Summary: Stream-stream join range eviction counts a day as 24 
hours and truncating casts as exact
                 Key: SPARK-61381
                 URL: https://issues.apache.org/jira/browse/SPARK-61381
             Project: Spark
          Issue Type: Bug
          Components: Structured Streaming
    Affects Versions: 5.0.0
            Reporter: Jungtaek Lim


A stream-stream join with a time-range condition can remove a buffered row 
while a later row from the other input can still match it. The join then loses 
that match, and an outer join emits the removed row padded with nulls too early.

The join derives each input's state cutoff from the other input's watermark by 
solving the range condition. The solver counts the terms of the condition 
exactly, but two kinds of term are not exact:

- *Whole days.* The solver counts each whole day of an interval as 24 hours. 
Spark adds whole days in the session time zone, so across a daylight saving 
change a day lasts 23 or 25 hours. After a fall-back change, {{impressionTime + 
INTERVAL 1 DAY}} is 25 hours after {{impressionTime}}, but the cutoff assumes 
24. This is true both for day-time intervals and for calendar intervals with 
days.
- *Truncating casts.* The solver reads a cast to a numeric type, such as 
{{CAST(ts AS BIGINT)}}, as the time itself. A cast to an integral type drops 
the fraction of a second, so {{CAST(10.95 s AS BIGINT)}} is 10. The cutoff can 
then be up to one second above the value a later row can still match.

In both cases the cutoff can lie above a row that can still match, so the join 
evicts it too early. The V4 range-scan window that limits state lookups is 
derived from the same solver, so it can also be too narrow. That was not 
reproduced separately.

h3. What is already handled

The open stream-stream join correctness changes handle two related forms:

- *SPARK-61345, equality keys.* Whole days count as inexact in every time zone 
for keys such as {{lt = rt + INTERVAL 1 DAY}}. A shift that never moves a time 
backward uses the unshifted watermark as its cutoff; any other such shift gets 
no cutoff. A truncating key such as {{CAST(CAST(rt AS BIGINT) AS TIMESTAMP)}} 
gets no cutoff.
- *SPARK-61347, one-sided range eviction.* A column without its own watermark 
gets no cutoff from a condition with whole days in a time zone that is not 
fixed-offset, or with a truncating cast. The analysis check uses the same rule.

This ticket covers what remains: the range solver for a column with its own 
watermark. That covers every two-sided time-interval join that has evicted 
state since the solver was added. Its cutoffs still count whole days as 24 
hours and truncating casts as exact.

h3. Reproducer 1: whole-day bound across the fall-back change

- Setup: Scala with {{MemoryStream}}, a 0-second watermark on both inputs, 
no-data micro-batches disabled so that each step below is one batch, and 
session time zone America/Los_Angeles.
- Clocks fall back on 2024-11-03, so the local day after 2024-11-02 12:00 PDT 
lasts 25 hours.

{code:scala}
spark.conf.set("spark.sql.session.timeZone", "America/Los_Angeles")
spark.conf.set("spark.sql.streaming.noDataMicroBatches.enabled", "false")
val impressions = MemoryStream[(Int, Long)]
val clicks = MemoryStream[(Int, Long)]
val left = impressions.toDF().toDF("adId", "ms")
  .select($"adId", timestamp_millis($"ms").as("impressionTime"))
  .withWatermark("impressionTime", "0 seconds")
val right = clicks.toDF().toDF("clickAdId", "ms")
  .select($"clickAdId", timestamp_millis($"ms").as("clickTime"))
  .withWatermark("clickTime", "0 seconds")
val joined = left.join(right, expr("adId = clickAdId AND " +
  "clickTime BETWEEN impressionTime AND impressionTime + INTERVAL 1 DAY"), 
"left_outer")

// batch 1: impressions (1, 2024-11-02T19:00Z), (7, 2024-11-03T19:10Z); clicks 
(9, 2024-11-03T19:10Z)
//          -> watermark becomes 2024-11-03T19:10Z
// batch 2: clicks (8, 2024-11-03T19:11Z)
// batch 3: clicks (1, 2024-11-03T19:30Z)
{code}

The impression at 2024-11-02T19:00Z (12:00 PDT) can match clicks until 
2024-11-03T20:00Z (12:00 PST). In batch 2, the left cutoff is the watermark 
minus 24 hours and 1 ms, 2024-11-02T19:09:59.999Z, which is above the 
impression.

- *Expected:* batch 2 outputs nothing. Batch 3 outputs {{(1, 2024-11-02T19:00Z, 
1, 2024-11-03T19:30Z)}}.
- *Actual:* batch 2 outputs {{(1, 2024-11-02T19:00Z, null, null)}}. Batch 3 
outputs nothing, because the impression has already left state.

h3. Reproducer 2: truncating cast

The setup is the same, with the default session time zone.

{code:scala}
val left = leftInput.toDF().toDF("lk", "ms")
  .select($"lk", timestamp_millis($"ms").as("lt"))
  .withWatermark("lt", "0 seconds")
val right = rightInput.toDF().toDF("rk", "ms")
  .select($"rk", timestamp_millis($"ms").as("rt"))
  .withWatermark("rt", "0 seconds")
val joined = left.join(right,
  expr("lk = rk AND CAST(lt AS BIGINT) >= CAST(rt AS BIGINT) + 5"), 
"left_outer")

// batch 1: left (1, 15.5 s), (7, 20 s); right (9, 10.9 s)  -> watermark 
becomes 10.9 s
// batch 2: right (8, 10.91 s)
// batch 3: right (1, 10.95 s)
{code}

The right row at 10.95 s is above the 10.9 s watermark, and {{CAST(15.5 s AS 
BIGINT) = 15 >= CAST(10.95 s AS BIGINT) + 5 = 15}}, so it matches the left row. 
In batch 2, the left cutoff is the watermark plus 5 seconds less 1 ms, 15.899 
s, which is above the left row.

- *Expected:* batch 2 outputs nothing. Batch 3 outputs {{(1, 15.5 s, 1, 10.95 
s)}}.
- *Actual:* batch 2 outputs {{(1, 15.5 s, null, null)}}. Batch 3 outputs 
nothing.

An inner join of the same shape loses the match in batch 3 and emits no null 
row.

h3. How the affected versions were checked

*The solver.* I read 
{{sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/analysis/StreamingJoinHelper.scala}}
 with {{git show <ref>:<path>}} at these refs:

||Ref||Version||Commit||
|v3.5.9|3.5.9|7c14a3c28b1|
|v4.0.5|4.0.5|b472a3aa3c4|
|v4.1.4|4.1.4|45b9b176e6e|
|v4.2.1|4.2.1|61761839608|
|v4.3.0|4.3.0|98bc0212c94|
|branch-4.x|4.4.0-SNAPSHOT|106f81f8891|
|master|5.0.0-SNAPSHOT|f35395086c9|

At every ref, {{collectTerms}} behaves the same way:

- It converts a calendar interval's days with {{MICROS_PER_DAY}} and a day-time 
interval literal to its microseconds.
- It collects both operands of {{TimeAdd}} (3.5.9 and 4.0.5) or 
{{TimestampAddInterval}} (4.1.4 and later) without reading the time zone.
- It treats {{Cast(child, NumericType | TimestampType)}} as its child.

*The interval addition.* At the same refs, 
{{DateTimeUtils.timestampAddDayTime}} adds the whole days of a day-time 
interval with {{ZonedDateTime.plusDays}} in the session time zone. So all seven 
refs have the same behavior.

*The reproducers.* Both reproducers were run on master (f35395086c9) in state 
formats 2, 3 and 4: in all 6 runs, every batch produced exactly the actual 
output above, checked batch by batch. Earlier, during the review triage, the 
same shapes also failed on f90fdcb2802. They were not run on the release tags.

h3. Possible direction

- Count each whole day conservatively in a time zone that is not fixed-offset: 
24 hours plus or minus the largest UTC-offset change in the zone's rules, 
taking whichever end keeps more state for the term's sign.
- Widen a non-strict bound over an integral cast by one unit.
- Keep exact forms unchanged: sub-day intervals, and any interval in a 
fixed-offset zone.
- Use the same counts for the V4 range-scan window.

The cost is that two-sided joins with whole-day bounds in such zones keep 
state, and emit unmatched outer rows, up to the zone's largest offset change 
later.




--
This message was sent by Atlassian Jira
(v10.3.26#10030026)

---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to