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]