Josh Rosen created SPARK-58442:
----------------------------------
Summary: IN/NOT IN subquery under a null-observing operator
returns wrong results: RewritePredicateSubquery collapses NULL to FALSE
Key: SPARK-58442
URL: https://issues.apache.org/jira/browse/SPARK-58442
Project: Spark
Issue Type: Bug
Components: SQL
Affects Versions: 4.0.0
Reporter: Josh Rosen
This is a report of a longstanding query correctness bug in Spark, affecting
all 4.x versions (and likely earlier versions, too).
An {{IN (subquery)}} predicate is three-valued: it evaluates to NULL when no
match is found and either the probe value is NULL or the subquery result
contains NULL. When such a predicate appears in a WHERE clause under an
operator that can observe NULL (such as {{{}IS NULL{}}}, {{{}IS NOT NULL{}}},
{{<=>}} ) Spark returns wrong results in default configuration.
For example (reproduced on current master c7b2f1a865c):
{code:sql}
CREATE TABLE t(c INT) USING PARQUET; INSERT INTO t VALUES (1), (2);
CREATE TABLE tn(c INT) USING PARQUET; INSERT INTO tn VALUES (1), (2), (NULL);
-- For the NULL row of tn: NULL IN {1,2} is NULL, so IS NULL is TRUE and the
row must be kept.
SELECT c FROM tn WHERE (c IN (SELECT c FROM t)) IS NULL;
-- Expected: [NULL] Actual: empty
SELECT c FROM tn WHERE (c NOT IN (SELECT c FROM t)) IS NULL;
-- Expected: [NULL] Actual: empty
SELECT c FROM tn WHERE (c IN (SELECT c FROM t)) IS NOT NULL;
-- Expected: [1], [2] Actual: [1], [2], [NULL]
SELECT c FROM tn WHERE (c IN (SELECT c FROM t)) <=> CAST(NULL AS BOOLEAN);
-- Expected: [NULL] Actual: empty{code}
(The expected results follow directly from three-valued logic as described in
Spark's own NULL-semantics documentation: {{IN}} returns NULL when no match is
found and either operand side involves NULL. Spark evaluates all four correctly
when the same predicates are placed where the {{RewritePredicateSubquery}}
rewrite does not apply, e.g. in a join ON condition.)
{*}Suspected root cause{*}:
* {{RewritePredicateSubquery}} gives dedicated, correct semi/anti-join
rewrites to filter conjuncts of the exact shapes {{{}Exists{}}},
{{{}Not(Exists){}}}, {{{}InSubquery{}}}, {{{}Not(InSubquery){}}}.
* Any other conjunct shape goes through {{{}rewriteExistentialExpr{}}}, which
transforms the conjunct and replaces each subquery predicate leaf with an
{{exists}} attribute from an {{{}ExistenceJoin{}}}, declared
{{{}AttributeReference("exists", BooleanType, nullable = false){}}}.
* That substitution preserves only the is-TRUE projection of the predicate:
the NULL outcome becomes FALSE.
* The collapse is sound at the condition root and under AND/OR (where NULL and
FALSE both reject the row), but the replacement is applied via unrestricted
{{transformDown}} at any depth, including under null-observing operators where
NULL-vs-FALSE is observable.
* Downstream folding then compounds it: {{NullPropagation}} (same batch, after
the rewrite) folds {{isnull(exists)}} on the non-nullable attribute to
{{{}false{}}}, so the first query above optimizes to an empty {{LocalRelation}}
— e.g.:
{code:java}
== Optimized Logical Plan ==
Project [c#9]
+- Join ExistenceJoin(exists#13), (c#9 = c#10)
:- LocalRelation <empty>, [c#9]
+- Relation spark_catalog.default.t[c#10] parquet {code}
* The defect is not the null-aware join condition (the {{(a=b) OR
isnull(a=b)}} construction is correct where used); it is representing a
three-valued predicate by a two-valued attribute in contexts that can tell the
difference.
*Related issues.*
* SPARK-43413 fixed the adjacent ListQuery-nullability layer, and its
description already acknowledged this residual defect in passing: "this rewrite
can also incorrectly discard NULLs, which is another bug." This report is that
bug, with concrete witnesses. Its tests (in-nullability.sql,
in-null-semantics.sql) probe only WHERE-position {{<=> true}} (the one
null-observing shape the collapse happens to get right, since NULL and FALSE
agree there) and ON-condition positions (which this rule does not rewrite).
* SPARK-58384 is the same defect pattern in a different rule
({{{}OptimizeJoinCondition{}}} rewriting {{(l = r) OR (l IS NULL AND r IS
NULL)}} to {{l <=> r}} under {{{}NOT{}}}): a truth-value-only rewrite applied
by an unrestricted traversal. {{ReplaceNullWithFalseInPredicate}} is the one
rule that implements the required position-restricted traversal, and its
approach is the model — but see below.
* SPARK-58365: same function, different bug (join condition built from
pre-dedup subquery output); verified not to fix this issue.
*Fix considerations:*
* Unlike SPARK-58384's rule, this rewrite is mandatory
({{{}RewritePredicateSubquery{}}} is in {{{}nonExcludableRules{}}}; physical
planning cannot execute a residual {{{}InSubquery{}}}), so it cannot simply
decline unsafe positions.
* In null-observing contexts it needs a three-valued encoding — e.g. alongside
{{{}exists{}}}, a null-presence signal from the subquery side, combining to
{{IF(exists, TRUE, IF(<probe is null OR subquery has null> AND <subquery
non-empty>, NULL, FALSE))}} — or an equivalent rewrite to a form whose NULL
behavior is preserved.
* Making the {{exists}} attribute's nullability honest is not sufficient on
its own (the three-valued information is already lost at the substitution
point), though the position-aware traversal from
ReplaceNullWithFalseInPredicate is the right shape for deciding _where_ the
cheap two-valued encoding remains safe.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
