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]