Jungtaek Lim created SPARK-61448:
------------------------------------

             Summary: Bound stream-stream join state by a window key over the 
first watermarked column in legacy mode
                 Key: SPARK-61448
                 URL: https://issues.apache.org/jira/browse/SPARK-61448
             Project: Spark
          Issue Type: Improvement
          Components: Structured Streaming
    Affects Versions: 5.0.0
            Reporter: Jungtaek Lim


With {{spark.sql.streaming.statefulOperator.allowMultiple=false}} (legacy 
mode), an input of a stream-stream join can keep both its event time {{ts}} and 
a time window over it. Both columns carry the watermark, and the join filters 
late rows by the first of them.

SPARK-61345 lets a window equality key bound the other input's state only when 
the window is that first column. Before it, Spark used any watermarked equality 
key. That was sound for a window over the first watermarked column: a row that 
passes late filtering on {{ts}} has a window that ends after the watermark. But 
it was unsound for a window over another watermarked column, where it could 
remove rows that could still match. SPARK-61345 cannot tell the two apart 
without plan lineage, so it drops the bound for both.

As a result, an input built with {{withColumn("window", window($"ts", ...))}}, 
which keeps {{ts}} before the window, gets no bound from the window key in 
legacy mode:

- Outer and left semi joins on the window fail analysis. The error says which 
column filters late rows and how to reorder the columns.
- Inner joins keep the other input's rows for the life of the query.

No result is wrong; the join only keeps more state than it needs, or is 
rejected.

This ticket asks Spark to recognize a window key whose window was computed from 
the input's first watermarked column, and to bound state by its end again, as 
before SPARK-61345. A window over another column must stay unrecognized.

h3. Reproducer

- Setup: Scala with {{MemoryStream}}, legacy mode, and no-data micro-batches 
disabled, so that each step below is one batch.
- Build: a build with SPARK-61345.

{code:scala}
spark.conf.set("spark.sql.streaming.statefulOperator.allowMultiple", "false")
spark.conf.set("spark.sql.streaming.noDataMicroBatches.enabled", "false")
val leftInput = MemoryStream[(Int, Int)]
val rightInput = MemoryStream[(Int, Int)]
def windowed(input: MemoryStream[(Int, Int)], side: String) =
  input.toDF().toDF(s"${side}k", "time")
    .select(col(s"${side}k"), timestamp_seconds($"time").as(s"${side}t"))
    .withWatermark(s"${side}t", "0 seconds")
    .withColumn(s"${side}w", window(col(s"${side}t"), "10 seconds"))
val left = windowed(leftInput, "l")
val right = windowed(rightInput, "r")
val joined = left.join(right, expr("lk = rk AND lw = rw"), "left_outer")

// batch 1: left (1, 5 s), (2, 6 s); right (1, 7 s)
// batch 2: left (3, 30 s); right (9, 30 s)   -> watermark becomes 30 s
// batch 3: right (9, 40 s)
{code}

- *Expected:* the query starts. Batch 1 outputs the match for key 1. Batch 3 
outputs {{(2, 6 s, null)}}, because the window [0 s, 10 s) of the unmatched 
left row ends at or below the 30-second watermark.
- *Actual:* the query fails analysis with {{Stream-stream LeftOuter join 
between two streaming DataFrame/Datasets is not supported: it requires a 
watermark on the right input and a time constraint ...}}. The error also says: 
{{With spark.sql.streaming.statefulOperator.allowMultiple=false, the right 
input filters late rows by its first watermarked column, rt, so its window key 
rw is not a time constraint. Put rw before rt in that input's columns, or drop 
rt, to bound state by the window.}}

An inner join of the same shape runs but never evicts either input's rows.

h3. Workaround

Put the window column before the event time column in each input, for example 
{{.select($"lk", $"lw", $"lt")}}, or drop the event time column. The window is 
then the input's first watermarked column, the join filters late rows by its 
end, and it bounds the other input's state by the window end.

h3. How the affected versions were checked

*The released lines.* I read {{StreamingJoinHelper.isWatermarkInJoinKeys}} (the 
admission check) and {{StreamingSymmetricHashJoinHelper}} (the eviction key 
ordinal) with {{git show <ref>:<path>}} at these tags:

||Tag||Commit||
|v3.5.9|7c14a3c28b1|
|v4.0.5|b472a3aa3c4|
|v4.1.4|45b9b176e6e|
|v4.2.1|61761839608|
|v4.3.0|98bc0212c94|

At every tag, both accept any equality key that carries watermark metadata, and 
a window copies that metadata from its time column. So these lines bound the 
reproducer by window end, and the gap is not there.

*The unreleased lines.* The gap starts with SPARK-61345, which its migration 
note places in Spark 4.4.0, without a backport to earlier releases. So the 
affected versions are 4.4.0 (branch-4.x) and 5.0.0 (master).

*The reproducer.* The analysis error and the workaround run are covered by the 
test {{legacy-mode join on a window after its event time names the column 
order}} in {{StreamingJoinWatermarkAdmissionSuite}}. It ran on the SPARK-61345 
branch with the error hint. The inner join's unbounded state comes from reading 
the code: it has no key ordinal and no range bound. It was not run.

h3. Possible direction

- *Shared lineage rule:* for each join input, find the watermarked window 
attributes that the time-window rewrite built over the column that reaches the 
join as the input's first watermarked column. Walk down by expression ID:
  - through the rewrite's marked alias for tumbling windows, and its {{Expand}} 
for sliding windows;
  - through nodes that pass values on unchanged: filters, projections of 
attributes and renames, and the watermark node.

  Any other node, including a union or an earlier join, leaves the window 
unrecognized. The output-watermark tracer in {{IncrementalExecution}}, which 
SPARK-61344 extends to follow {{Expand}} and unions, can be a starting point. 
But it runs on the physical plan only.
- *Same keys everywhere:* the analysis check, the state eviction predicates, 
and the V4 lookup key ordinal must accept exactly the same keys. A practical 
way is to walk the analyzed logical plan once in each place, and give each join 
exec the result, because execution chooses the V4 ordinal without the plan.
- *Accept a recognized key as the event time:* treat a recognized window key as 
the input's event time, bounded by its end, as a window that is the only 
watermarked column is today.
- *Tests:* legacy inner and left outer joins in both column orders; a window 
over the second watermarked column; a renamed {{ts}}; {{Union}}; a sliding 
window; and a V4 restart.




--
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