Josh Rosen created SPARK-58384:
----------------------------------
Summary: OptimizeJoinCondition rewrites the null-safe-equality
pattern under NOT, returning wrong rows
Key: SPARK-58384
URL: https://issues.apache.org/jira/browse/SPARK-58384
Project: Spark
Issue Type: Improvement
Components: SQL
Affects Versions: 4.0.0
Reporter: Josh Rosen
This is a report of a correctness bug present in Spark 4.0.0 and later
(introduced by SPARK-47810).
The {{OptimizeJoinCondition}} optimizer rule rewrites
{{ (l = r) OR (l IS NULL AND r IS NULL)}}
to
{{l <=> r}}
inside join conditions.
The two expressions agree on whether they evaluate to TRUE, but differ in
three-valued logic: when exactly one side is NULL, the OR-pattern evaluates to
NULL while {{l <=> r}} evaluates to FALSE.
At the top level of a join condition the difference is unobservable (filter
conditions evaluating to NULL and FALSE both reject the row), but the rule
applies the rewrite via an unrestricted {{transform}} over the entire filter
condition tree, including under {{{}NOT{}}}, where the difference _is_
observable: {{NOT(NULL) = NULL}} (row rejected) vs {{NOT(FALSE) = TRUE}} (row
accepted).
Writing {{P}} for the original pattern {{(l = r) OR (l IS NULL AND r IS NULL)}}
(a join keeps a row only when its condition is TRUE; NULL and FALSE both
reject):
||l||r||P||l <=> r||NOT(P)||NOT(l <=> r)||row kept under NOT?||
|0|0|TRUE|TRUE|FALSE|FALSE|no / no|
|0|1|FALSE|FALSE|TRUE|TRUE|yes / yes|
|0|NULL|*NULL*|*FALSE*|*NULL*|*TRUE*|*no / yes – WRONG*|
|NULL|NULL|TRUE|TRUE|FALSE|FALSE|no / no|
h3. Repro
{code:java}
CREATE TABLE tl(a INT, b INT) USING parquet;
INSERT INTO tl VALUES (0, 10), (NULL, 11);
CREATE TABLE tr(x INT, y INT) USING parquet;
INSERT INTO tr VALUES (NULL, 20), (0, 21), (1, 22);
SELECT * FROM tl JOIN tr ON NOT (tl.a = tr.x OR (tl.a IS NULL AND tr.x IS
NULL));
-- outputs: [0,10,null,20], [null,11,0,21], [null,11,1,22], [0,10,1,22]
-- WRONG (expected: only [0,10,1,22]) {code}
Every pair with exactly one NULL side must be excluded, but the join keeps
those pairs because the condition was rewritten:
{code:java}
== Analyzed Logical Plan ==
Join Inner, NOT ((a#20 = x#22) OR (isnull(a#20) AND isnull(x#22)))
== Optimized Logical Plan ==
Join Inner, NOT (a#20 <=> x#22) {code}
h3. Fix
To fix this: the rewrite is only sound at positions where nothing can
distinguish NULL from FALSE, i.e. positions reachable from the condition root
through AND/OR only, never under NOT and not in value positions of conditional
expressions.
The pre-existing [{{ReplaceNullWithFalseInPredicate}} rule
|https://github.com/apache/spark/blob/5ce51a624421acceec378e0170da24a8fc2a96eb/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/ReplaceNullWithFalseInPredicate.scala#L31-L53]performs
a structurally identical NULL-vs-FALSE substitution and restricts itself to
exactly those positions by explicit recursion (its scaladoc calls out NOT as
the hazard); {{OptimizeJoinCondition}} should mirror that traversal instead of
an unrestricted {{{}transform{}}}.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
