[
https://issues.apache.org/jira/browse/SPARK-58442?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Josh Rosen updated SPARK-58442:
-------------------------------
Description:
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/function 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 observe
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.
was:
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
function 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 observe
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.
> IN/NOT IN subquery under a null-observing operator/function 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
> Priority: Major
> Labels: correctness
>
> 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/function 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 observe
> 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]
