Jungtaek Lim created SPARK-61382:
------------------------------------

             Summary: Stream-stream full outer join joins rows whose equality 
keys are both NULL
                 Key: SPARK-61382
                 URL: https://issues.apache.org/jira/browse/SPARK-61382
             Project: Spark
          Issue Type: Bug
          Components: Structured Streaming
    Affects Versions: 5.0.0
            Reporter: Jungtaek Lim


A stream-stream full outer join can join a left row and a right row whose 
equality key is NULL on both sides. SQL {{=}} never matches NULL, so the 
correct output is two rows, each padded with nulls. A batch full outer join on 
the same data returns those two rows. The streaming join returns one joined row 
instead.

The streaming join finds matches by looking up the other input's state with the 
generated key row, and that lookup compares the key bytes. Two keys that are 
NULL in the same field have the same bytes, so they match. The batch joins skip 
a key with a NULL field, but the stream-stream join has no such check.

h3. Which join types are affected

For most join types, the optimizer keeps NULL keys from meeting. When 
{{spark.sql.constraintPropagation.enabled}} is true (the default), 
{{InferFiltersFromConstraints}} adds {{IS NOT NULL}} filters on the equality 
keys:
- on both inputs of an inner or left semi join;
- on the right input of a left outer join;
- on the left input of a right outer join.

A full outer join gets no such filter, so:

- *With the default setting, only full outer joins are affected.* In a left 
outer join, a left row with a NULL key cannot meet a right row with a NULL key, 
because the filter removes that right row. The left row is later emitted padded 
with nulls, which is correct. Right outer joins behave the same way, mirrored.
- *With {{spark.sql.constraintPropagation.enabled=false}}, inner, left outer 
and right outer joins are affected too.* No filter is added, so NULL keys meet 
in all of them. The reproducer below shows this for inner, left outer and right 
outer joins; left semi joins were not run.

Null-safe equality ({{<=>}}) is not affected. The planner rewrites it into keys 
that are never NULL.

h3. Reproducer

- Setup: Scala with {{MemoryStream}}, a 0-second watermark on both inputs, and 
the default settings.
- A negative key stands for a NULL key.

{code:scala}
val leftInput = MemoryStream[(Int, Int)]
val rightInput = MemoryStream[(Int, Int)]
val left = leftInput.toDF().toDF("k", "t")
  .select(when($"k" >= 0, $"k").as("lk"), timestamp_seconds($"t").as("lt"))
  .withWatermark("lt", "0 seconds")
val right = rightInput.toDF().toDF("k", "t")
  .select(when($"k" >= 0, $"k").as("rk"), timestamp_seconds($"t").as("rt"))
  .withWatermark("rt", "0 seconds")
val joined = left.join(right, expr("lk = rk AND lt = rt"), "full_outer")
  .select($"lk", $"lt".cast("long"), $"rk", $"rt".cast("long"))

// batch 1: left (NULL, 10); right (NULL, 10)
// batch 2: left (1, 100);   right (1, 100)   -> the watermark passes 10
// batch 3: left (2, 200);   right (2, 200)
{code}

- *Expected:* {{[1,100,1,100]}}, {{[2,200,2,200]}}, {{[null,10,null,null]}}, 
{{[null,null,null,10]}}.
- *Actual:* {{[1,100,1,100]}}, {{[2,200,2,200]}}, {{[null,10,null,10]}}.

The same reproducer was run for each join type, with constraint propagation on 
and off, in state formats 2 and 4. It was run on master at f90fdcb2802, and on 
the stream-stream join correctness fixes listed below. Both gave the same 
results:

||Join type||Constraint propagation on||Constraint propagation off||
|inner|correct: no NULL-key row|wrong: {{[null,10,null,10]}}|
|left outer|correct: {{[null,10,null,null]}}|wrong: {{[null,10,null,10]}}|
|right outer|correct: {{[null,null,null,10]}}|wrong: {{[null,10,null,10]}}|
|full outer|*wrong:* {{[null,10,null,10]}}|wrong: {{[null,10,null,10]}}|

h3. What the open fixes already change

The open stream-stream join correctness changes SPARK-61344 and SPARK-61345 
(#60279, #60280) handle one case. If the equality key that state is evicted on 
is NULL, the row can never match, so it is handled like a row that fails the 
pre-join filter:
- a preserved side emits it padded with nulls in the batch it arrives;
- no side stores it.

So two rows whose NULL is in that eviction key no longer pair. This ticket 
covers what remains: a NULL in any other equality key. In the reproducer, 
{{lk}} is NULL but the state is evicted on {{lt}} and {{rt}}, so the rows still 
pair with those changes applied.

h3. Possible direction

Handle a row whose generated equality key has a NULL field 
({{UnsafeRow.anyNull}}) like a row that fails the pre-join filter, in every 
join type:
- a preserved side emits it padded with nulls at once;
- no side probes the other input's state with it or stores it.

This makes the streaming join match batch semantics. It also removes NULL-key 
rows from state that would otherwise stay there until eviction.

Output changes only for rows that are now joined although {{=}} never matches 
them.

Rows with a NULL key that are already in a checkpoint stay in state after the 
upgrade and are evicted as today. They no longer pair with new rows, because a 
new NULL-key row does not probe state.

h3. How the affected versions were checked

I read the join code with {{git show <ref>:<path>}}, read-only, 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:

- *No NULL check in the join.* 
{{StreamingSymmetricHashJoinExec.OneSideHashJoiner.storeAndJoinWithOtherSide}} 
builds the key with {{keyGenerator(thisRow)}} and uses it to probe the other 
input's state and to store the row. Neither the exec nor 
{{SymmetricHashJoinStateManager}} checks the key for NULL; neither has 
{{anyNull}} or a key {{isNullAt}} check. The files are under 
{{sql/execution/streaming/}} in 3.5.9 and 4.0.5, and under 
{{sql/execution/streaming/operators/stateful/join/}} from 4.1.4 on.
- *Inferred filters.* In 
{{sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala}},
 {{InferFiltersFromConstraints}} runs only when 
{{conf.constraintPropagationEnabled}} is true. It has cases for {{InnerLike | 
LeftSemi}} (both sides), {{RightOuter}} (left side) and {{LeftOuter | 
LeftAnti}} (right side), and none for {{FullOuter}}.

So all seven refs behave the same way. The reproducer ran only on master and on 
the open fixes, not on the release tags.




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