cloud-fan commented on code in PR #58656:
URL: https://github.com/apache/spark/pull/58656#discussion_r4414366426
##########
sql/core/src/test/scala/org/apache/spark/sql/SubquerySuite.scala:
##########
@@ -3227,4 +3224,625 @@ class SubquerySuite extends SharedSparkSession
}
}
}
+
+ /**
+ * Checks the result of `query`, that every node of its optimized plan can
produce the attributes
+ * it references, and that the existence join a nested subquery was
rewritten into sits on the
+ * subquery side of the semi/anti join.
+ *
+ * The plan checks are what SPARK-59351 is about: an existence join whose
condition references an
+ * attribute produced by neither of its children can still return the right
answer when the
+ * nested relation is empty at runtime, because the invalid condition is
then never bound, and a
+ * rewrite that placed the join on the other side would return the right
answer here too. Note
+ * that missingInput cannot see a subquery expression that survives in a
condition, since
+ * QueryPlan.references folds only the outer attributes of one and collect
does not walk its
+ * plan, so it is not a substitute for asserting the shape.
+ */
+ private def checkAnswerAndPlan(
+ query: String,
+ expected: Seq[Row],
+ existenceJoinOnSubqueryPlan: Boolean = true): Unit = {
+ val df = sql(query)
+ val plan = df.queryExecution.optimizedPlan
+ val invalidNodes = plan.collect { case p if p.missingInput.nonEmpty => p }
+ assert(invalidNodes.isEmpty,
+ s"""Plan nodes reference non-reachable attributes:
+ |${invalidNodes.mkString("\n")}
+ |$plan""".stripMargin)
+ if (existenceJoinOnSubqueryPlan) {
+ val semiOrAnti = plan.collectFirst {
+ case j: Join if j.joinType == LeftSemi || j.joinType == LeftAnti => j
+ }
+ assert(semiOrAnti.nonEmpty, s"expected a semi or anti join in\n$plan")
+ val existenceJoins = plan.collect {
+ case j: Join if j.joinType.isInstanceOf[ExistenceJoin] => j
+ }
+ assert(existenceJoins.nonEmpty, s"expected an existence join in\n$plan")
+ // The existence join must be under the right side of the semi/anti
join, which is the
+ // subquery plan, and not under its left side, which is the outer plan.
+ assert(existenceJoins.forall(j =>
semiOrAnti.get.right.exists(_.fastEquals(j))),
+ s"the existence join must sit on the subquery side in\n$plan")
+ }
+ checkAnswer(df, expected)
+ }
+
+ test("SPARK-59351: nested subquery referencing the inner query becomes an
existence join") {
+ // SPARK-45580 covers the case where the nested subquery references the
outer query, in which
+ // case its existence join is built on top of the outer plan. Here the
nested subquery
+ // references the query it is nested in, so the existence join has to be
built on top of the
+ // subquery plan instead.
+ withTempView("t1", "t2", "t3", "t3n", "t4", "t5") {
+ Seq((1), (2), (3), (7),
(9)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ // t3 shares a value with t2, t5 does not, so the nested subquery
decides the answer below.
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+ Seq((3), (7)).toDF("col1").persist().createOrReplaceTempView("t5")
+ Seq(Some(3), Some(9),
None).toDF("col1").persist().createOrReplaceTempView("t3n")
+ // A correlated nested IN over t4 is false for every c1 in t2, while the
same IN without its
+ // correlated predicate is true for 1 and 9, so the correlation decides
the answer below.
+ Seq((1, 9), (9, 1)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+
+ // EXISTS rewritten as a left semi join. The correlated predicate is a
disjunction, so it
+ // is pulled up as a whole and carries the nested IN-subquery, which
references c1, out of
+ // the subquery plan.
+ val query1 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query1, Row(1) :: Row(2) :: Row(3) :: Row(7) ::
Row(9) :: Nil)
+
+ // Same over t5, which shares no value with t2, so the nested IN is
false for every c1 and
+ // only the correlated predicate can hold: a mistake making it true
would return every row.
+ val query2 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t5)
+ |)""".stripMargin
+ checkAnswerAndPlan(query2, Row(1) :: Row(9) :: Nil)
+
+ // NOT EXISTS rewritten as a left anti join.
+ val query3 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE NOT EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t5)
+ |)""".stripMargin
+ checkAnswerAndPlan(query3, Row(2) :: Row(3) :: Row(7) :: Nil)
+
+ // IN-subquery rewritten as a left semi join. The hoisted predicate is a
> c1 rather than
+ // the key equality a = c1, so the answer is a IN (t2 INTERSECT t3) and
depends on the
+ // nested subquery: dropping it would leave no row at all.
+ val query4 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR c1 IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query4, Row(9) :: Nil)
+
+ // NOT IN-subquery rewritten as a null-aware left anti join, with a
nested EXISTS. Only the
+ // nested EXISTS keeps 9 out of the answer, as a > c1 alone does not
hold for it.
+ val query5 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a NOT IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR EXISTS (SELECT 1 FROM t3 WHERE col1 = c1)
+ |)""".stripMargin
+ checkAnswerAndPlan(query5, Row(1) :: Row(2) :: Row(3) :: Row(7) :: Nil)
+
+ // A nested NOT IN-subquery keeps its null-aware semantics: c1 NOT IN
(3, 9, NULL) is never
+ // true, so only the correlated predicate can be satisfied. Compare with
query7, where the
+ // same NOT IN over a relation without NULL holds for c1 = 1 and returns
every row.
+ val query6 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 NOT IN (SELECT col1 FROM t3n)
+ |)""".stripMargin
+ checkAnswerAndPlan(query6, Row(1) :: Row(9) :: Nil)
+
+ val query7 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 NOT IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query7, Row(1) :: Row(2) :: Row(3) :: Row(7) ::
Row(9) :: Nil)
+
+ // A nested subquery correlated to the query it is nested in, on a
column it does not
+ // project, so its correlated predicate changes the answer: without it
the nested IN would
+ // hold for c1 = 1 and row 1 would be returned as well.
+ val query8 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR c1 IN (SELECT col1 FROM t4 WHERE k = c1)
+ |)""".stripMargin
+ checkAnswerAndPlan(query8, Row(2) :: Row(3) :: Row(7) :: Row(9) :: Nil)
+ }
+ }
+
+ test("SPARK-59351: nested subquery referencing both the outer and the inner
query") {
+ withTempView("t1", "t2", "t3", "t4") {
+ Seq((1), (2), (3)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+ // Correlated, this is false for every c1 in t2; without its correlated
predicate it holds
+ // for 1 and 9, so the correlation decides the answer below.
+ Seq((1, 9), (9, 1)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+
+ // The nested subquery references the outer query through its values and
the inner query
+ // through its own correlated predicate, so it can be rewritten into an
existence join on
+ // neither side and stays in the join condition. Planning it there as an
in-subquery filter
+ // drops its correlated predicate col1 = c1, which is why it is rejected
rather than left.
+ // These rows do not distinguish the two forms; the EXISTS form of this
shape does, and
+ // returned an extra row before the rejection was added.
+ //
+ // NOT IN is the outer predicate on purpose: its rewrite returns a bare
Join, which
+ // RewritePredicateSubquery does not offer to its own handling of
predicate subqueries in
+ // join conditions, so this rejection is the only one that can fire and
the assertion below
+ // pins it. With EXISTS the rewrite returns a Project over the join,
which that handling
+ // reaches under the default configuration and rejects with
+ // UNSUPPORTED_CORRELATED_EXPRESSION_IN_JOIN_CONDITION instead, so the
query would still
+ // fail but on a different condition than the one asserted here.
+ val correlated =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a NOT IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR a IN (SELECT col1 FROM t3 WHERE col1 = c1)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ val e = intercept[AnalysisException](sql(correlated).collect())
+ assert(e.getCondition == "UNSUPPORTED_SUBQUERY_EXPRESSION_CATEGORY."
+
+ "NESTED_SUBQUERY_REFERENCING_OUTER_AND_INNER_QUERY")
+ // The message must name the subquery that was rejected.
+ val reported = e.getMessageParameters.get("subqueryExpression")
+ assert(reported.contains("IN") && reported.contains("listquery"),
+ s"unexpected subqueryExpression: $reported")
+ }
+ }
+
+ // A correlated predicate that BooleanSimplification has eliminated:
+ // PullupCorrelatedPredicates retains c1 as an outer attribute of the
nested subquery for
+ // idempotency, but the subquery
+ // no longer reads it, so there is no condition to lose. It must still
be rewritten against
+ // the outer plan, which is the only plan it effectively references,
rather than be treated
+ // as referencing the subquery plan and rejected.
+ val simplifiedAwayCorrelation =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR a IN (SELECT col1 FROM t3 WHERE false AND col1 = c1)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ checkAnswer(sql(simplifiedAwayCorrelation), Row(1) :: Nil)
+ }
+ }
+
+ // A subquery that stays in the join condition stays there whole, since
the rewrite does
+ // not descend into one it declines, so a correlated subquery below it
is left as well.
+ // Its own references make it look routable, being owned by the subquery
plan, but
+ // nothing reaches it and planning a list query as an in-subquery filter
drops the
+ // predicate the pull-up hoisted into it. The enclosing subquery is
rejected for
+ // carrying it: PostgreSQL and DuckDB return 1 and 3 here, and losing
the correlation
+ // returns 2 as well.
+ val carriedCorrelation =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR (a + (CASE WHEN c1 IN (SELECT col1 FROM t4 WHERE k = c1) THEN
1 ELSE 0 END))
+ | IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ val e =
intercept[AnalysisException](sql(carriedCorrelation).collect())
+ assert(e.getCondition == "UNSUPPORTED_SUBQUERY_EXPRESSION_CATEGORY."
+
+ "NESTED_SUBQUERY_REFERENCING_OUTER_AND_INNER_QUERY")
+ }
+ }
+
+ // An uncorrelated nested subquery referencing both queries has no
correlated predicate to
+ // lose, so it stays in the join condition and is planned as an
in-subquery filter. The
+ // configuration is disabled because the rewrite of predicate subqueries
in join conditions
+ // rejects a subquery referencing both join inputs, which is what this
one becomes.
+ val uncorrelated =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR (a + c1) IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ withSQLConf(
+ SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
"false") {
+ // No existence join here: this subquery stays in the join condition,
which is the
+ // point of the case, so only the result and the reachability of the
plan are
+ // checked.
+ checkAnswerAndPlan(uncorrelated, Row(1) :: Row(2) :: Nil,
+ existenceJoinOnSubqueryPlan = false)
+ }
+ }
+ }
+
+ test("SPARK-59351: existential subquery carried by a rewritten nested
subquery") {
+ // The nested IN over t4 is owned by the subquery plan, so it is rewritten
into an existence
+ // join and the condition PullupCorrelatedPredicates hoisted into it is
grafted onto that
+ // join. That condition carries a third-level IN correlated to t4, which
references neither
+ // the outer nor the subquery plan and so is routed by neither of the
guards above. It has to
+ // be rewritten against the inputs of the join just built: left in place,
PlanSubqueries plans
+ // it as an in-subquery filter and drops its own correlated predicate col1
= k, which returns
+ // every row of t1 instead of the one row where the correlation holds.
+ withTempView("t1", "t2", "t4", "t5") {
+ Seq(1, 2, 3).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq(1, 8, 9).toDF("c1").persist().createOrReplaceTempView("t2")
+ // No k equals any c1, so only the third-level IN can satisfy the
hoisted disjunction, and
+ // its correlated predicate col1 = k is false for every row of t4:
dropping it makes the
+ // level-2 IN hold for c1 = 1 and returns 1, 2 and 3.
+ Seq((1, 100), (9, 7)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+ Seq(1).toDF("col1").persist().createOrReplaceTempView("t5")
+ val query =
+ """SELECT * FROM t1 WHERE EXISTS (
+ | SELECT 1 FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t4
+ | WHERE k = c1 OR col1 IN (SELECT col1 FROM t5 WHERE col1
= k)))""".stripMargin
+ // The routing must not depend on the rewrite of predicate subqueries in
join conditions,
+ // which is what used to make these two configurations disagree: it
reached the grafted
+ // condition only when enabled.
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ checkAnswerAndPlan(query, Row(1) :: Nil)
+ }
+ }
+ }
+ }
+
+ test("SPARK-59351: NOT IN keeps an uncorrelated three-valued residual") {
+ // The NOT IN rewrite returns a bare Join, which this rule does not offer
to its own handling
+ // of predicate subqueries in join conditions, so an uncorrelated nested
IN left in the
+ // anti-join condition stays there and InSubqueryExec evaluates it
three-valued. No existence
+ // join is built for it and it has no hoisted condition to lose, so it
must not be rejected:
+ // these queries returned the standard SQL answer before SPARK-59351 and
must keep doing so.
+ withTempView("t1", "t2", "t3n", "t4n") {
+ Seq(1, 2, 3).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq(1, 8, 9).toDF("c1").persist().createOrReplaceTempView("t2")
+ // The NULL matches no c1, so c1 IN (SELECT col1 FROM t3n) is unknown
for every row of t2.
+ Seq(Some(3), None).toDF("col1").persist().createOrReplaceTempView("t3n")
+ // Nullable col1 again, but correlated through k = c1.
+ Seq((Some(3), 1), (None, 8)).toDF("col1",
"k").persist().createOrReplaceTempView("t4n")
+
+ Seq(
+ "(c1 IN (SELECT col1 FROM t3n)) <=> false",
+ "(c1 IN (SELECT col1 FROM t3n)) IS NULL",
+ "COALESCE(c1 IN (SELECT col1 FROM t3n), true)",
+ "(c1 NOT IN (SELECT col1 FROM t3n)) <=> false").foreach { predicate =>
+ // Every such predicate is FALSE for every row of t2, so the subquery
reduces to a = c1
+ // and only 2 and 3 survive the NOT IN. Rejecting instead, or
rewriting the nested IN into
+ // a two-valued exists, would change this.
+ checkAnswer(
+ sql(s"SELECT * FROM t1 WHERE a NOT IN (SELECT c1 FROM t2 WHERE a =
c1 OR $predicate)"),
Review Comment:
Confirmed: with c1 > a hoisted, each residual case now tells the
three-valued residual apart from a two-valued rewrite, and the truth-only case
goes through checkAnswerAndPlan.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4346076727","thread_id":"inline:4346076727","verdict_sha256":"596d6ef5f193363401f54af770e62e1e49b3bfd27c84efadb74d430a0c108603"}
-->
##########
sql/core/src/test/scala/org/apache/spark/sql/SubquerySuite.scala:
##########
@@ -3227,4 +3224,625 @@ class SubquerySuite extends SharedSparkSession
}
}
}
+
+ /**
+ * Checks the result of `query`, that every node of its optimized plan can
produce the attributes
+ * it references, and that the existence join a nested subquery was
rewritten into sits on the
+ * subquery side of the semi/anti join.
+ *
+ * The plan checks are what SPARK-59351 is about: an existence join whose
condition references an
+ * attribute produced by neither of its children can still return the right
answer when the
+ * nested relation is empty at runtime, because the invalid condition is
then never bound, and a
+ * rewrite that placed the join on the other side would return the right
answer here too. Note
+ * that missingInput cannot see a subquery expression that survives in a
condition, since
+ * QueryPlan.references folds only the outer attributes of one and collect
does not walk its
+ * plan, so it is not a substitute for asserting the shape.
+ */
+ private def checkAnswerAndPlan(
+ query: String,
+ expected: Seq[Row],
+ existenceJoinOnSubqueryPlan: Boolean = true): Unit = {
+ val df = sql(query)
+ val plan = df.queryExecution.optimizedPlan
+ val invalidNodes = plan.collect { case p if p.missingInput.nonEmpty => p }
+ assert(invalidNodes.isEmpty,
+ s"""Plan nodes reference non-reachable attributes:
+ |${invalidNodes.mkString("\n")}
+ |$plan""".stripMargin)
+ if (existenceJoinOnSubqueryPlan) {
+ val semiOrAnti = plan.collectFirst {
+ case j: Join if j.joinType == LeftSemi || j.joinType == LeftAnti => j
+ }
+ assert(semiOrAnti.nonEmpty, s"expected a semi or anti join in\n$plan")
+ val existenceJoins = plan.collect {
+ case j: Join if j.joinType.isInstanceOf[ExistenceJoin] => j
+ }
+ assert(existenceJoins.nonEmpty, s"expected an existence join in\n$plan")
+ // The existence join must be under the right side of the semi/anti
join, which is the
+ // subquery plan, and not under its left side, which is the outer plan.
+ assert(existenceJoins.forall(j =>
semiOrAnti.get.right.exists(_.fastEquals(j))),
+ s"the existence join must sit on the subquery side in\n$plan")
+ }
+ checkAnswer(df, expected)
+ }
+
+ test("SPARK-59351: nested subquery referencing the inner query becomes an
existence join") {
+ // SPARK-45580 covers the case where the nested subquery references the
outer query, in which
+ // case its existence join is built on top of the outer plan. Here the
nested subquery
+ // references the query it is nested in, so the existence join has to be
built on top of the
+ // subquery plan instead.
+ withTempView("t1", "t2", "t3", "t3n", "t4", "t5") {
+ Seq((1), (2), (3), (7),
(9)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ // t3 shares a value with t2, t5 does not, so the nested subquery
decides the answer below.
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+ Seq((3), (7)).toDF("col1").persist().createOrReplaceTempView("t5")
+ Seq(Some(3), Some(9),
None).toDF("col1").persist().createOrReplaceTempView("t3n")
+ // A correlated nested IN over t4 is false for every c1 in t2, while the
same IN without its
+ // correlated predicate is true for 1 and 9, so the correlation decides
the answer below.
+ Seq((1, 9), (9, 1)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+
+ // EXISTS rewritten as a left semi join. The correlated predicate is a
disjunction, so it
+ // is pulled up as a whole and carries the nested IN-subquery, which
references c1, out of
+ // the subquery plan.
+ val query1 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query1, Row(1) :: Row(2) :: Row(3) :: Row(7) ::
Row(9) :: Nil)
+
+ // Same over t5, which shares no value with t2, so the nested IN is
false for every c1 and
+ // only the correlated predicate can hold: a mistake making it true
would return every row.
+ val query2 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t5)
+ |)""".stripMargin
+ checkAnswerAndPlan(query2, Row(1) :: Row(9) :: Nil)
+
+ // NOT EXISTS rewritten as a left anti join.
+ val query3 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE NOT EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t5)
+ |)""".stripMargin
+ checkAnswerAndPlan(query3, Row(2) :: Row(3) :: Row(7) :: Nil)
+
+ // IN-subquery rewritten as a left semi join. The hoisted predicate is a
> c1 rather than
+ // the key equality a = c1, so the answer is a IN (t2 INTERSECT t3) and
depends on the
+ // nested subquery: dropping it would leave no row at all.
+ val query4 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR c1 IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query4, Row(9) :: Nil)
+
+ // NOT IN-subquery rewritten as a null-aware left anti join, with a
nested EXISTS. Only the
+ // nested EXISTS keeps 9 out of the answer, as a > c1 alone does not
hold for it.
+ val query5 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a NOT IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR EXISTS (SELECT 1 FROM t3 WHERE col1 = c1)
+ |)""".stripMargin
+ checkAnswerAndPlan(query5, Row(1) :: Row(2) :: Row(3) :: Row(7) :: Nil)
+
+ // A nested NOT IN-subquery keeps its null-aware semantics: c1 NOT IN
(3, 9, NULL) is never
+ // true, so only the correlated predicate can be satisfied. Compare with
query7, where the
+ // same NOT IN over a relation without NULL holds for c1 = 1 and returns
every row.
+ val query6 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 NOT IN (SELECT col1 FROM t3n)
+ |)""".stripMargin
+ checkAnswerAndPlan(query6, Row(1) :: Row(9) :: Nil)
+
+ val query7 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 NOT IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query7, Row(1) :: Row(2) :: Row(3) :: Row(7) ::
Row(9) :: Nil)
+
+ // A nested subquery correlated to the query it is nested in, on a
column it does not
+ // project, so its correlated predicate changes the answer: without it
the nested IN would
+ // hold for c1 = 1 and row 1 would be returned as well.
+ val query8 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR c1 IN (SELECT col1 FROM t4 WHERE k = c1)
+ |)""".stripMargin
+ checkAnswerAndPlan(query8, Row(2) :: Row(3) :: Row(7) :: Row(9) :: Nil)
+ }
+ }
+
+ test("SPARK-59351: nested subquery referencing both the outer and the inner
query") {
+ withTempView("t1", "t2", "t3", "t4") {
+ Seq((1), (2), (3)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+ // Correlated, this is false for every c1 in t2; without its correlated
predicate it holds
+ // for 1 and 9, so the correlation decides the answer below.
+ Seq((1, 9), (9, 1)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+
+ // The nested subquery references the outer query through its values and
the inner query
+ // through its own correlated predicate, so it can be rewritten into an
existence join on
+ // neither side and stays in the join condition. Planning it there as an
in-subquery filter
+ // drops its correlated predicate col1 = c1, which is why it is rejected
rather than left.
+ // These rows do not distinguish the two forms; the EXISTS form of this
shape does, and
+ // returned an extra row before the rejection was added.
+ //
+ // NOT IN is the outer predicate on purpose: its rewrite returns a bare
Join, which
+ // RewritePredicateSubquery does not offer to its own handling of
predicate subqueries in
+ // join conditions, so this rejection is the only one that can fire and
the assertion below
+ // pins it. With EXISTS the rewrite returns a Project over the join,
which that handling
+ // reaches under the default configuration and rejects with
+ // UNSUPPORTED_CORRELATED_EXPRESSION_IN_JOIN_CONDITION instead, so the
query would still
+ // fail but on a different condition than the one asserted here.
+ val correlated =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a NOT IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR a IN (SELECT col1 FROM t3 WHERE col1 = c1)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ val e = intercept[AnalysisException](sql(correlated).collect())
+ assert(e.getCondition == "UNSUPPORTED_SUBQUERY_EXPRESSION_CATEGORY."
+
+ "NESTED_SUBQUERY_REFERENCING_OUTER_AND_INNER_QUERY")
+ // The message must name the subquery that was rejected.
+ val reported = e.getMessageParameters.get("subqueryExpression")
+ assert(reported.contains("IN") && reported.contains("listquery"),
+ s"unexpected subqueryExpression: $reported")
+ }
+ }
+
+ // A correlated predicate that BooleanSimplification has eliminated:
+ // PullupCorrelatedPredicates retains c1 as an outer attribute of the
nested subquery for
+ // idempotency, but the subquery
+ // no longer reads it, so there is no condition to lose. It must still
be rewritten against
+ // the outer plan, which is the only plan it effectively references,
rather than be treated
+ // as referencing the subquery plan and rejected.
+ val simplifiedAwayCorrelation =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR a IN (SELECT col1 FROM t3 WHERE false AND col1 = c1)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ checkAnswer(sql(simplifiedAwayCorrelation), Row(1) :: Nil)
+ }
+ }
+
+ // A subquery that stays in the join condition stays there whole, since
the rewrite does
+ // not descend into one it declines, so a correlated subquery below it
is left as well.
+ // Its own references make it look routable, being owned by the subquery
plan, but
+ // nothing reaches it and planning a list query as an in-subquery filter
drops the
+ // predicate the pull-up hoisted into it. The enclosing subquery is
rejected for
+ // carrying it: PostgreSQL and DuckDB return 1 and 3 here, and losing
the correlation
+ // returns 2 as well.
+ val carriedCorrelation =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR (a + (CASE WHEN c1 IN (SELECT col1 FROM t4 WHERE k = c1) THEN
1 ELSE 0 END))
+ | IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ val e =
intercept[AnalysisException](sql(carriedCorrelation).collect())
+ assert(e.getCondition == "UNSUPPORTED_SUBQUERY_EXPRESSION_CATEGORY."
+
+ "NESTED_SUBQUERY_REFERENCING_OUTER_AND_INNER_QUERY")
+ }
+ }
+
+ // An uncorrelated nested subquery referencing both queries has no
correlated predicate to
+ // lose, so it stays in the join condition and is planned as an
in-subquery filter. The
+ // configuration is disabled because the rewrite of predicate subqueries
in join conditions
+ // rejects a subquery referencing both join inputs, which is what this
one becomes.
+ val uncorrelated =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR (a + c1) IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ withSQLConf(
+ SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
"false") {
+ // No existence join here: this subquery stays in the join condition,
which is the
+ // point of the case, so only the result and the reachability of the
plan are
+ // checked.
+ checkAnswerAndPlan(uncorrelated, Row(1) :: Row(2) :: Nil,
+ existenceJoinOnSubqueryPlan = false)
+ }
+ }
+ }
+
+ test("SPARK-59351: existential subquery carried by a rewritten nested
subquery") {
Review Comment:
Confirmed: the new test covers the Filter-predicate, projection and
join-condition routes with a correlated nested IN whose predicate decides the
answer.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4346076746","thread_id":"inline:4346076746","verdict_sha256":"596d6ef5f193363401f54af770e62e1e49b3bfd27c84efadb74d430a0c108603"}
-->
##########
sql/core/src/test/scala/org/apache/spark/sql/SubquerySuite.scala:
##########
@@ -3227,4 +3224,625 @@ class SubquerySuite extends SharedSparkSession
}
}
}
+
+ /**
+ * Checks the result of `query`, that every node of its optimized plan can
produce the attributes
+ * it references, and that the existence join a nested subquery was
rewritten into sits on the
+ * subquery side of the semi/anti join.
+ *
+ * The plan checks are what SPARK-59351 is about: an existence join whose
condition references an
+ * attribute produced by neither of its children can still return the right
answer when the
+ * nested relation is empty at runtime, because the invalid condition is
then never bound, and a
+ * rewrite that placed the join on the other side would return the right
answer here too. Note
+ * that missingInput cannot see a subquery expression that survives in a
condition, since
+ * QueryPlan.references folds only the outer attributes of one and collect
does not walk its
+ * plan, so it is not a substitute for asserting the shape.
+ */
+ private def checkAnswerAndPlan(
+ query: String,
+ expected: Seq[Row],
+ existenceJoinOnSubqueryPlan: Boolean = true): Unit = {
+ val df = sql(query)
+ val plan = df.queryExecution.optimizedPlan
+ val invalidNodes = plan.collect { case p if p.missingInput.nonEmpty => p }
+ assert(invalidNodes.isEmpty,
+ s"""Plan nodes reference non-reachable attributes:
+ |${invalidNodes.mkString("\n")}
+ |$plan""".stripMargin)
+ if (existenceJoinOnSubqueryPlan) {
+ val semiOrAnti = plan.collectFirst {
+ case j: Join if j.joinType == LeftSemi || j.joinType == LeftAnti => j
+ }
+ assert(semiOrAnti.nonEmpty, s"expected a semi or anti join in\n$plan")
+ val existenceJoins = plan.collect {
+ case j: Join if j.joinType.isInstanceOf[ExistenceJoin] => j
+ }
+ assert(existenceJoins.nonEmpty, s"expected an existence join in\n$plan")
+ // The existence join must be under the right side of the semi/anti
join, which is the
+ // subquery plan, and not under its left side, which is the outer plan.
+ assert(existenceJoins.forall(j =>
semiOrAnti.get.right.exists(_.fastEquals(j))),
+ s"the existence join must sit on the subquery side in\n$plan")
+ }
+ checkAnswer(df, expected)
+ }
+
+ test("SPARK-59351: nested subquery referencing the inner query becomes an
existence join") {
+ // SPARK-45580 covers the case where the nested subquery references the
outer query, in which
+ // case its existence join is built on top of the outer plan. Here the
nested subquery
+ // references the query it is nested in, so the existence join has to be
built on top of the
+ // subquery plan instead.
+ withTempView("t1", "t2", "t3", "t3n", "t4", "t5") {
+ Seq((1), (2), (3), (7),
(9)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ // t3 shares a value with t2, t5 does not, so the nested subquery
decides the answer below.
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+ Seq((3), (7)).toDF("col1").persist().createOrReplaceTempView("t5")
+ Seq(Some(3), Some(9),
None).toDF("col1").persist().createOrReplaceTempView("t3n")
+ // A correlated nested IN over t4 is false for every c1 in t2, while the
same IN without its
+ // correlated predicate is true for 1 and 9, so the correlation decides
the answer below.
+ Seq((1, 9), (9, 1)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+
+ // EXISTS rewritten as a left semi join. The correlated predicate is a
disjunction, so it
+ // is pulled up as a whole and carries the nested IN-subquery, which
references c1, out of
+ // the subquery plan.
+ val query1 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query1, Row(1) :: Row(2) :: Row(3) :: Row(7) ::
Row(9) :: Nil)
+
+ // Same over t5, which shares no value with t2, so the nested IN is
false for every c1 and
+ // only the correlated predicate can hold: a mistake making it true
would return every row.
+ val query2 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t5)
+ |)""".stripMargin
+ checkAnswerAndPlan(query2, Row(1) :: Row(9) :: Nil)
+
+ // NOT EXISTS rewritten as a left anti join.
+ val query3 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE NOT EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t5)
+ |)""".stripMargin
+ checkAnswerAndPlan(query3, Row(2) :: Row(3) :: Row(7) :: Nil)
+
+ // IN-subquery rewritten as a left semi join. The hoisted predicate is a
> c1 rather than
+ // the key equality a = c1, so the answer is a IN (t2 INTERSECT t3) and
depends on the
+ // nested subquery: dropping it would leave no row at all.
+ val query4 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR c1 IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query4, Row(9) :: Nil)
+
+ // NOT IN-subquery rewritten as a null-aware left anti join, with a
nested EXISTS. Only the
+ // nested EXISTS keeps 9 out of the answer, as a > c1 alone does not
hold for it.
+ val query5 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a NOT IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR EXISTS (SELECT 1 FROM t3 WHERE col1 = c1)
+ |)""".stripMargin
+ checkAnswerAndPlan(query5, Row(1) :: Row(2) :: Row(3) :: Row(7) :: Nil)
+
+ // A nested NOT IN-subquery keeps its null-aware semantics: c1 NOT IN
(3, 9, NULL) is never
+ // true, so only the correlated predicate can be satisfied. Compare with
query7, where the
+ // same NOT IN over a relation without NULL holds for c1 = 1 and returns
every row.
+ val query6 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 NOT IN (SELECT col1 FROM t3n)
+ |)""".stripMargin
+ checkAnswerAndPlan(query6, Row(1) :: Row(9) :: Nil)
+
+ val query7 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 NOT IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query7, Row(1) :: Row(2) :: Row(3) :: Row(7) ::
Row(9) :: Nil)
+
+ // A nested subquery correlated to the query it is nested in, on a
column it does not
+ // project, so its correlated predicate changes the answer: without it
the nested IN would
+ // hold for c1 = 1 and row 1 would be returned as well.
+ val query8 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR c1 IN (SELECT col1 FROM t4 WHERE k = c1)
+ |)""".stripMargin
+ checkAnswerAndPlan(query8, Row(2) :: Row(3) :: Row(7) :: Row(9) :: Nil)
+ }
+ }
+
+ test("SPARK-59351: nested subquery referencing both the outer and the inner
query") {
+ withTempView("t1", "t2", "t3", "t4") {
+ Seq((1), (2), (3)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+ // Correlated, this is false for every c1 in t2; without its correlated
predicate it holds
+ // for 1 and 9, so the correlation decides the answer below.
+ Seq((1, 9), (9, 1)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+
+ // The nested subquery references the outer query through its values and
the inner query
+ // through its own correlated predicate, so it can be rewritten into an
existence join on
+ // neither side and stays in the join condition. Planning it there as an
in-subquery filter
+ // drops its correlated predicate col1 = c1, which is why it is rejected
rather than left.
+ // These rows do not distinguish the two forms; the EXISTS form of this
shape does, and
+ // returned an extra row before the rejection was added.
+ //
+ // NOT IN is the outer predicate on purpose: its rewrite returns a bare
Join, which
+ // RewritePredicateSubquery does not offer to its own handling of
predicate subqueries in
+ // join conditions, so this rejection is the only one that can fire and
the assertion below
+ // pins it. With EXISTS the rewrite returns a Project over the join,
which that handling
Review Comment:
Confirmed: the comment now states the EXISTS outcome as a counterfactual and
matches the asserted condition.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4346076758","thread_id":"inline:4346076758","verdict_sha256":"596d6ef5f193363401f54af770e62e1e49b3bfd27c84efadb74d430a0c108603"}
-->
##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/RewriteSubquerySuite.scala:
##########
@@ -161,4 +163,124 @@ class RewriteSubquerySuite extends PlanTest {
val existsExpected = LocalRelation(existsQuery.analyze.output).analyze
comparePlans(existsOptimized, existsExpected)
}
+
+ test("SPARK-59351: nested subquery of an EXISTS whose plan shares attributes
with the outer " +
+ "plan") {
+ // The EXISTS arms route the nested subquery against the raw subquery
plan, while the IN arms
+ // route it against the plan dedupSubqueryOnSelfJoin has already separated
from the outer
+ // plan. A self-join can leave an ExprId shared between the two plans for
the optimizer
+ // (SPARK-21835), and the analyzer is not involved here, so build that
state directly: `a` is
+ // the same attribute in the outer and in the subquery plan.
+ val a = $"a".int
+ val outer = LocalRelation(a, $"b".int)
+ val sub = LocalRelation(a)
+ val nested = LocalRelation($"col1".int)
+ assert(outer.outputSet.intersect(sub.outputSet).nonEmpty,
+ "the two plans must share an attribute for this test to mean anything")
+
+ // The nested subquery references `a`, which only the subquery plan is
meant to give it, and
+ // is correlated to it, so it must be rewritten against the subquery plan.
Classifying `a` as
Review Comment:
Confirmed: the fixture comment now describes the swap, matching the
planReferences scaladoc.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4346076766","thread_id":"inline:4346076766","verdict_sha256":"596d6ef5f193363401f54af770e62e1e49b3bfd27c84efadb74d430a0c108603"}
-->
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/subquery.scala:
##########
@@ -398,62 +414,615 @@ object RewritePredicateSubquery extends
Rule[LogicalPlan] with PredicateHelper {
(newExpr, newPlan)
}
+ /**
+ * Rewrites the existential sub-queries carried by the condition of an
existence join that this
+ * rule has just built, against whichever of that join's own inputs can
evaluate them.
+ *
+ * [[rewriteExistentialExprWithAttrs]] grafts the condition that
[[PullupCorrelatedPredicates]]
+ * hoisted into a nested sub-query onto the existence join it builds for
that sub-query, and
+ * replaces the sub-query atomically without descending into what the
condition carries. A
+ * correlated existential sub-query carried along references the plan of the
sub-query it was
+ * hoisted out of, which is an input of the join just built and of no plan
seen before it, so
+ * nothing else reaches it: left there, `PlanSubqueries` plans it as an
in-subquery filter and
+ * drops its own hoisted condition, which returns extra rows.
+ *
+ * This is what the handling of predicate sub-queries in join conditions
does for a join the user
+ * wrote, and doing it here too makes the result independent of
+ *
`spark.sql.optimizer.decorrelatePredicateSubqueriesInJoinPredicate.enabled`,
which gates that
+ * handling. The routing recurses, since the joins built here go through it
in turn.
+ *
+ * An uncorrelated sub-query is routed as well, rather than left for that
handling to rewrite
+ * under its default configuration: it has no hoisted condition to lose, but
it is subject to the
+ * same unknown-result guard as one on the sub-query-plan route, and that
handling has no such
+ * guard. Consuming it here is what keeps an IN whose result is observably
unknown from becoming
+ * a two-valued `exists` attribute.
+ *
+ * The classification mirrors [[rewriteExistentialExprInSubqueryPlan]], with
this join's inputs
+ * in place of the outer and the sub-query plan: a sub-query referencing
exactly one input is
+ * routed against it, one referencing both is rejected when it is correlated
or carries a
+ * correlated sub-query, since neither input alone can evaluate it, and one
whose unknown result
+ * is observable is rejected. A sub-query referencing both inputs or neither
and carrying no
+ * correlation is left where it is, as it is at the first level.
+ */
+ private def rewriteCarriedExistentialExprs(join: Join): LogicalPlan = {
+ if (!join.condition.exists(_.containsAnyPattern(EXISTS_SUBQUERY,
IN_SUBQUERY))) {
+ return join
+ }
+ val condition = join.condition.get
+ val carried = ArrayBuffer.empty[Expression]
+ collectCarriedExistentialExprs(condition, carried)
+ if (carried.isEmpty) {
+ return join
+ }
+ // A NOT IN is carried as the Not over the IN, which is the unit the
rewrite consumes and the
+ // unit the unknown-result collector reports, so both agree on the node
below.
+ def negatedIn(sq: Expression): Expression = sq match {
+ case Not(in: InSubquery) => in
+ case other => other
+ }
+ val unknownSensitive = unknownSensitiveInSubqueries(condition, truthOnly =
true)
+ def observesUnknown(sq: Expression): Boolean =
unknownSensitive.exists(_.fastEquals(sq))
+ def referencesInput(sq: Expression, input: LogicalPlan): Boolean =
+ effectiveReferences(sq).exists(input.outputSet.contains)
+ def referencesBothInputs(sq: Expression): Boolean =
+ referencesInput(sq, join.left) && referencesInput(sq, join.right)
+ def referencesOneInput(sq: Expression): Boolean =
+ referencesInput(sq, join.left) != referencesInput(sq, join.right)
+
+ // The two rejections of the sub-query-plan route apply here for the same
reasons, against the
+ // inputs of this join rather than against the outer and the sub-query
plan, and each raises
+ // the condition whose message describes it.
+ val referencingBothInputs = carried.filter { sq =>
+ referencesBothInputs(sq) &&
+ (hasCorrelatedCondition(sq) ||
carriesCorrelatedSubquery(negatedIn(sq)))
+ }
+ if (referencingBothInputs.nonEmpty) {
+ throw
QueryCompilationErrors.nestedSubqueryReferencingOuterAndInnerQueryError(
+ referencingBothInputs.toSeq)
+ }
+ val unknownResult = carried.filter(sq => referencesOneInput(sq) &&
observesUnknown(sq))
+ if (unknownResult.nonEmpty) {
+ throw
QueryCompilationErrors.nestedInSubqueryWithUnknownResultError(unknownResult.toSeq)
+ }
+ var newCondition = condition
+ def route(plan: LogicalPlan, isInput: Expression => Boolean): LogicalPlan
= {
+ carried.filter(sq => referencesOneInput(sq) &&
isInput(sq)).foldLeft(plan) {
+ case (p, sq) =>
+ val (rewritten, newInput, _) =
rewriteExistentialExprWithAttrs(Seq(sq), p)
+ newCondition = newCondition.transform {
+ case e if e.fastEquals(sq) => rewritten.get
+ }
+ newInput
+ }
+ }
+ val newLeft = route(join.left, referencesInput(_, join.left))
+ val newRight = route(join.right, referencesInput(_, join.right))
+ if (newLeft.fastEquals(join.left) && newRight.fastEquals(join.right)) {
+ join
+ } else {
+ // Drop the `exists` attributes the nested existence joins introduced,
keeping this join's
+ // own output, which already carries its own.
+ Project(join.output, join.copy(
+ left = newLeft, right = newRight, condition = Some(newCondition)))
+ }
+ }
+
+ /**
+ * Collects the existential sub-queries carried by the condition of an
existence join, as the
+ * units [[rewriteExistentialExprWithAttrs]] rewrites: a NOT IN is collected
as the [[Not]] over
+ * the [[InSubquery]], so the rewrite takes its null-aware arm and the
unknown-result collector,
+ * which reports the same node, can be compared against it.
+ *
+ * A collected sub-query is not descended into. One nested below it is
reached when it is
+ * rewritten, since the join built for it goes through the routing in turn,
and one below a
+ * sub-query left in place is left with it, as everywhere else in this rule.
+ */
+ private def collectCarriedExistentialExprs(
+ expr: Expression,
+ collected: ArrayBuffer[Expression]): Unit = {
+ if (!expr.containsAnyPattern(EXISTS_SUBQUERY, IN_SUBQUERY)) {
+ return
+ }
+ expr match {
+ case sq @ Not(_: InSubquery) => collected += sq
+ case sq: Exists => collected += sq
+ case sq: InSubquery => collected += sq
+ case other => other.children.foreach(collectCarriedExistentialExprs(_,
collected))
+ }
+ }
+
+ /**
+ * Same as [[rewriteExistentialExpr]], but it also returns the newly
introduced attributes, and
+ * it only rewrites the existential sub-queries for which `canRewrite`
returns true. A sub-query
+ * that is not rewritten stays in the returned expression as it is, and is
not descended into:
+ * rewriting an existential sub-query nested in its join condition would
graft an existence join
+ * onto the plan for an `exists` reference that the sub-query left in place
may never evaluate.
+ */
private def rewriteExistentialExprWithAttrs(
exprs: Seq[Expression],
- plan: LogicalPlan): (Option[Expression], LogicalPlan, Seq[Attribute]) = {
+ plan: LogicalPlan,
+ canRewrite: Expression => Boolean = _ => true): (Option[Expression],
LogicalPlan,
+ Seq[Attribute]) = {
var newPlan = plan
val introducedAttrs = ArrayBuffer.empty[Attribute]
- val newExprs = exprs.map { e =>
- e.transformDownWithPruning(_.containsAnyPattern(EXISTS_SUBQUERY,
IN_SUBQUERY)) {
- case Exists(sub, _, _, conditions, subHint) =>
- val exists = AttributeReference("exists", BooleanType, nullable =
false)()
- val existenceJoin = ExistenceJoin(exists)
- val newCondition = conditions.reduceLeftOption(And)
- newPlan =
- buildJoin(newPlan, rewriteDomainJoinsIfPresent(newPlan, sub,
newCondition),
- existenceJoin, newCondition, subHint)
- introducedAttrs += exists
- exists
- case Not(InSubquery(values, ListQuery(sub, _, _, _, conditions,
subHint))) =>
- val exists = AttributeReference("exists", BooleanType, nullable =
false)()
- // Deduplicate conflicting attributes if any.
- val newSub = dedupSubqueryOnSelfJoin(newPlan, sub, Some(values))
- val inConditions = values.zip(newSub.output).map(EqualTo.tupled)
- // To handle a null-aware predicate not-in-subquery in nested
conditions
- // (e.g., `v > 0 OR t1.id NOT IN (SELECT id FROM t2)`), we transform
- // `inCondition` (t1.id=t2.id) into `(inCondition) OR
ISNULL(inCondition)`.
- //
- // For example, `SELECT * FROM t1 WHERE v > 0 OR t1.id NOT IN
(SELECT id FROM t2)`
- // is transformed into a plan below;
- // == Optimized Logical Plan ==
- // Project [id#78, v#79]
- // +- Filter ((v#79 > 0) OR NOT exists#83)
- // +- Join ExistenceJoin(exists#83), ((id#78 = id#80) OR
isnull((id#78 = id#80)))
- // :- Relation[id#78,v#79] parquet
- // +- Relation[id#80] parquet
- val nullAwareJoinConds = inConditions.map(c => Or(c, IsNull(c)))
- val finalJoinCond = (nullAwareJoinConds ++
conditions).reduceLeft(And)
- val joinHint = JoinHint(None, subHint)
- newPlan = Join(newPlan,
- rewriteDomainJoinsIfPresent(newPlan, newSub, Some(finalJoinCond)),
- ExistenceJoin(exists), Some(finalJoinCond), joinHint)
- introducedAttrs += exists
- Not(exists)
- case InSubquery(values, ListQuery(sub, _, _, _, conditions, subHint))
=>
- val exists = AttributeReference("exists", BooleanType, nullable =
false)()
- // Deduplicate conflicting attributes if any.
- val newSub = dedupSubqueryOnSelfJoin(newPlan, sub, Some(values))
- val inConditions = values.zip(newSub.output).map(EqualTo.tupled)
- val newConditions = (inConditions ++
conditions).reduceLeftOption(And)
- val joinHint = JoinHint(None, subHint)
- newPlan = Join(newPlan, rewriteDomainJoinsIfPresent(newPlan, newSub,
newConditions),
- ExistenceJoin(exists), newConditions, joinHint)
- introducedAttrs += exists
- exists
+ // Builds the replacement of a sub-query expression under that
expression's origin and with
+ // its tags, as TreeNode.transformDownWithPruning does for the nodes a
rule replaces. Without
+ // it every node built below, the `exists` attribute and the join
conditions included, would
+ // take the origin of the enclosing operator, and a runtime error raised
from the rewritten
+ // condition would quote that operator rather than the sub-query fragment.
+ def replacing(sq: Expression)(replacement: => Expression): Expression = {
+ val newExpr = CurrentOrigin.withOrigin(sq.origin)(replacement)
+ newExpr.copyTagsFrom(sq)
+ newExpr
+ }
+ def rewrite(expr: Expression): Expression = {
+ if (!expr.containsAnyPattern(EXISTS_SUBQUERY, IN_SUBQUERY)) {
+ return expr
+ }
+ expr match {
+ case sq @ Exists(sub, _, _, conditions, subHint) if canRewrite(sq) =>
+ replacing(sq) {
+ val exists = AttributeReference("exists", BooleanType, nullable =
false)()
+ val existenceJoin = ExistenceJoin(exists)
+ val newCondition = conditions.reduceLeftOption(And)
+ newPlan = rewriteCarriedExistentialExprs(
+ buildJoin(newPlan, rewriteDomainJoinsIfPresent(newPlan, sub,
newCondition),
+ existenceJoin, newCondition, subHint))
+ introducedAttrs += exists
+ exists
+ }
+ case sq @ Not(InSubquery(values, ListQuery(sub, _, _, _, conditions,
subHint)))
+ if canRewrite(sq) =>
+ replacing(sq) {
+ val exists = AttributeReference("exists", BooleanType, nullable =
false)()
+ // Deduplicate conflicting attributes if any.
+ val newSub = dedupSubqueryOnSelfJoin(newPlan, sub, Some(values))
+ val inConditions = values.zip(newSub.output).map(EqualTo.tupled)
+ // To handle a null-aware predicate not-in-subquery in nested
conditions
+ // (e.g., `v > 0 OR t1.id NOT IN (SELECT id FROM t2)`), we
transform
+ // `inCondition` (t1.id=t2.id) into `(inCondition) OR
ISNULL(inCondition)`.
+ //
+ // For example, `SELECT * FROM t1 WHERE v > 0 OR t1.id NOT IN
(SELECT id FROM t2)`
+ // is transformed into a plan below;
+ // == Optimized Logical Plan ==
+ // Project [id#78, v#79]
+ // +- Filter ((v#79 > 0) OR NOT exists#83)
+ // +- Join ExistenceJoin(exists#83), ((id#78 = id#80) OR
isnull((id#78 = id#80)))
+ // :- Relation[id#78,v#79] parquet
+ // +- Relation[id#80] parquet
+ val nullAwareJoinConds = inConditions.map(c => Or(c, IsNull(c)))
+ val finalJoinCond = (nullAwareJoinConds ++
conditions).reduceLeft(And)
+ val joinHint = JoinHint(None, subHint)
+ newPlan = rewriteCarriedExistentialExprs(Join(newPlan,
+ rewriteDomainJoinsIfPresent(newPlan, newSub,
Some(finalJoinCond)),
+ ExistenceJoin(exists), Some(finalJoinCond), joinHint))
+ introducedAttrs += exists
+ Not(exists)
+ }
+ case sq @ InSubquery(values, ListQuery(sub, _, _, _, conditions,
subHint))
+ if canRewrite(sq) =>
+ replacing(sq) {
+ val exists = AttributeReference("exists", BooleanType, nullable =
false)()
+ // Deduplicate conflicting attributes if any.
+ val newSub = dedupSubqueryOnSelfJoin(newPlan, sub, Some(values))
+ val inConditions = values.zip(newSub.output).map(EqualTo.tupled)
+ val newConditions = (inConditions ++
conditions).reduceLeftOption(And)
+ val joinHint = JoinHint(None, subHint)
+ newPlan = rewriteCarriedExistentialExprs(
+ Join(newPlan, rewriteDomainJoinsIfPresent(newPlan, newSub,
newConditions),
+ ExistenceJoin(exists), newConditions, joinHint))
+ introducedAttrs += exists
+ exists
+ }
+ // A sub-query that `canRewrite` declined is left as it is, children
included.
+ case sq @ (_: Exists | Not(_: InSubquery) | _: InSubquery) => sq
+ case other => other.mapChildren(rewrite)
}
}
+ val newExprs = exprs.map(rewrite)
(newExprs.reduceOption(And), newPlan, introducedAttrs.toSeq)
}
+
+ /**
+ * Returns true if `e` references any of the attributes produced by `plan`.
+ */
+ private def referencesPlan(e: Expression, plan: LogicalPlan): Boolean = {
+ // Iterates the references and probes the output set, rather than
materialising the
+ // intersection: AttributeSet.intersect builds a set from its argument, so
the operand order
+ // there would decide whether this walks the references or the whole
output of `plan`. The
+ // membership probes still construct wrappers, so this is cheaper, not
allocation-free.
+ e.references.exists(plan.outputSet.contains)
+ }
+
+ /**
+ * Returns true if `e` effectively references any of the attributes produced
by `plan`, see
+ * [[effectiveReferences]].
+ */
+ private def effectivelyReferencesPlan(e: Expression, plan: LogicalPlan):
Boolean = {
+ effectiveReferences(e).exists(plan.outputSet.contains)
+ }
+
+ /**
+ * Which of an outer plan and a sub-query plan a set of references can be
evaluated by, as
+ * [[planReferences]] determines it.
+ */
+ private case class PlanReferences(subPlanOnly: Boolean, bothPlans: Boolean)
+
+ /**
+ * Classifies `references` against `outerPlan` and `subPlan` in a single
pass: whether they can
+ * only be evaluated by `subPlan`, and whether they need both plans.
+ *
+ * An attribute that both plans produce is attributed to `subPlan` rather
than to `outerPlan`,
+ * which is what the `subPlan` probe coming first does. A nested sub-query
resolves in the scope
+ * of the sub-query it is nested in, so an attribute both plans produce is
one of that
+ * sub-query's own.
+ *
+ * The probes are exclusive, so swapping their order would attribute such an
attribute to
+ * `outerPlan` alone: `subPlanOnly` and `bothPlans` would both be false, and
a nested sub-query
+ * whose only reference is the shared attribute would be declined and left
in the join condition
+ * rather than routed to the sub-query plan that can evaluate it.
+ *
+ * No plan the analyzer produces from SQL reaches this:
`DeduplicateRelations` has given the
+ * sub-query its own ExprIds, and the EXISTS arms classify against the raw
sub-query plan while
+ * the IN arms classify against the plan `dedupSubqueryOnSelfJoin` has
already separated from the
+ * outer plan. What does reach it is the shared-attribute fixture in
`RewriteSubquerySuite`,
+ * which builds the overlap directly because the analyzer is not involved
there. That fixture
+ * pins the shape, not the outcome of this ordering: under either order it
ends in the same
+ * error, since `dedupSubqueryOnSelfJoin`'s pre-existing conflict check
reports the duplicated
+ * attribute that the hoisted condition mentions.
+ *
+ * An attribute neither plan produces leaves both answers false, which
declines the rewrite here.
+ * That does not leave the sub-query unexamined: one carried by a nested
sub-query that is
+ * rewritten is routed against the inputs of the join built for it, see
+ * [[rewriteCarriedExistentialExprs]].
+ */
+ private def planReferences(
+ references: AttributeSet,
+ outerPlan: LogicalPlan,
+ subPlan: LogicalPlan): PlanReferences = {
+ var subPlanReference = false
+ var outerPlanOnlyReference = false
+ val attrs = references.iterator
+ // Stops as soon as both plans are known to be referenced, which is all
the two answers need.
+ while (attrs.hasNext && !(subPlanReference && outerPlanOnlyReference)) {
+ val attr = attrs.next()
+ if (subPlan.outputSet.contains(attr)) {
+ subPlanReference = true
+ } else if (outerPlan.outputSet.contains(attr)) {
+ outerPlanOnlyReference = true
+ }
+ }
+ PlanReferences(
+ subPlanOnly = subPlanReference && !outerPlanOnlyReference,
+ bothPlans = subPlanReference && outerPlanOnlyReference)
+ }
+
+ /**
+ * The attributes that `e` references and can still evaluate. For an
existential sub-query
+ * expression these are the ones of the values it compares and of the
correlated condition that
+ * [[PullupCorrelatedPredicates]] hoisted into it, rather than the ones of
`references`, which
+ * also include the outer attributes the pull-up retains for idempotency.
Those outlive the
+ * condition that referenced them once BooleanSimplification has eliminated
it, as in
+ * `a IN (SELECT col1 FROM t3 WHERE false AND col1 = c1)`, which keeps `c1`
as an outer
+ * attribute of a sub-query that no longer reads it, and which must still be
rewritten against
+ * the outer plan rather than treated as referencing the sub-query plan.
+ *
+ * The sets are merged with `AttributeSet.fromAttributeSets` rather than
built from a flattened
+ * sequence of attributes: `AttributeSet.apply` would take one allocation
per attribute of a
+ * sequence as long as the total number of references, which a row-valued IN
over a wide row
+ * makes unnecessarily large.
+ */
+ private def effectiveReferences(e: Expression): AttributeSet = e match {
+ case Exists(_, _, _, joinCond, _) =>
+ AttributeSet.fromAttributeSets(joinCond.map(_.references))
+ case Not(in: InSubquery) => effectiveReferences(in)
+ case InSubquery(values, ListQuery(_, _, _, _, joinCond, _)) =>
+ AttributeSet.fromAttributeSets(values.map(_.references) ++
joinCond.map(_.references))
+ case _ => e.references
+ }
+
+ /**
+ * Rewrites the existential sub-queries that are nested in the correlated
predicates which
+ * [[PullupCorrelatedPredicates]] hoisted out of a predicate sub-query, and
which therefore end
+ * up in the condition of the semi/anti join that replaces that sub-query.
+ *
+ * A hoisted predicate can carry a nested existential sub-query out of the
sub-query plan,
+ * because a correlated predicate is hoisted as a whole when it is a
disjunction. For example
+ *
+ * SELECT * FROM t1 WHERE EXISTS (
+ * SELECT 1 FROM t2 WHERE t1.a = t2.c1 OR t2.c1 IN (SELECT col1 FROM t3))
+ *
+ * hoists `a = c1 OR c1 IN (SELECT col1 FROM t3)` into the join condition.
Such a nested
+ * sub-query must be rewritten against the plan that produces the attributes
it references:
+ * the one above references `c1`, which is produced by the sub-query plan
and not by the outer
+ * plan, so its existence join has to be built on top of the sub-query plan.
Building it on top
+ * of the outer plan instead yields a join whose condition references an
attribute that neither
+ * of its children can produce (SPARK-59351).
+ *
+ * A nested sub-query that references both plans cannot be rewritten into an
existence join on
+ * either side, since neither alone can evaluate it, so it has to stay in
the join condition,
+ * where both plans are in scope. Leaving it there is only correct while it
is uncorrelated: the
+ * join condition of a correlated one is dropped when it is planned as an
in-subquery filter,
+ * which would silently change the result, so a correlated one is reported
as unsupported
+ * instead. Note that such a sub-query can be
+ * correlated only to the sub-query plan, as being correlated to the outer
plan as well would
+ * require two levels of correlation, which the Analyzer rejects.
+ *
+ * A sub-query left here is further subject to the rewrite of predicate
sub-queries in join
+ * conditions, which rejects one referencing both plans under the default
configuration. It
+ * survives that rewrite when
+ *
`spark.sql.optimizer.decorrelatePredicateSubqueriesInJoinPredicate.enabled` is
disabled, and
+ * also when it is an uncorrelated IN sub-query and
+ *
`spark.sql.optimizer.optimizeUncorrelatedInSubqueriesInJoinCondition.enabled`
is disabled,
+ * since it is then not among the sub-queries that rewrite considers.
+ *
+ * An existence join yields only whether a row matched, so its `exists`
attribute cannot tell
+ * FALSE from unknown, while `IN` is three-valued. The two are
indistinguishable while the value
+ * only feeds a predicate, which is what a hoisted condition normally does,
but not when it
+ * reaches something else, e.g. `(c1 IN (SELECT col1 FROM t3)) <=> false`,
which is FALSE for a
+ * NULL that matches nothing and TRUE for the `exists` attribute. An IN
sub-query whose row
+ * comparison can evaluate to unknown is therefore rejected in that position
rather than
Review Comment:
Confirmed: the scaladoc now limits the rejection to sub-queries the
sub-query plan owns and points the outer-only case at SPARK-59862.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4369134663","thread_id":"inline:4369134663","verdict_sha256":"596d6ef5f193363401f54af770e62e1e49b3bfd27c84efadb74d430a0c108603"}
-->
##########
sql/core/src/test/scala/org/apache/spark/sql/SubquerySuite.scala:
##########
@@ -3227,4 +3224,749 @@ class SubquerySuite extends SharedSparkSession
}
}
}
+
+ /**
+ * Checks the result of `query`, that every node of its optimized plan can
produce the attributes
+ * it references, and that the existence join a nested subquery was
rewritten into sits on the
+ * subquery side of the semi/anti join.
+ *
+ * The plan checks are what SPARK-59351 is about: an existence join whose
condition references an
+ * attribute produced by neither of its children can still return the right
answer when the
+ * nested relation is empty at runtime, because the invalid condition is
then never bound, and a
+ * rewrite that placed the join on the other side would return the right
answer here too. Note
+ * that missingInput cannot see a subquery expression that survives in a
condition, since
+ * QueryPlan.references folds only the outer attributes of one and collect
does not walk its
+ * plan, so it is not a substitute for asserting the shape.
+ */
+ private def checkAnswerAndPlan(
+ query: String,
+ expected: Seq[Row],
+ existenceJoinOnSubqueryPlan: Boolean = true): Unit = {
+ val df = sql(query)
+ val plan = df.queryExecution.optimizedPlan
+ val invalidNodes = plan.collect { case p if p.missingInput.nonEmpty => p }
+ assert(invalidNodes.isEmpty,
+ s"""Plan nodes reference non-reachable attributes:
+ |${invalidNodes.mkString("\n")}
+ |$plan""".stripMargin)
+ if (existenceJoinOnSubqueryPlan) {
+ val semiOrAnti = plan.collectFirst {
+ case j: Join if j.joinType == LeftSemi || j.joinType == LeftAnti => j
+ }
+ assert(semiOrAnti.nonEmpty, s"expected a semi or anti join in\n$plan")
+ val existenceJoins = plan.collect {
+ case j: Join if j.joinType.isInstanceOf[ExistenceJoin] => j
+ }
+ assert(existenceJoins.nonEmpty, s"expected an existence join in\n$plan")
+ // The existence join must be under the right side of the semi/anti
join, which is the
+ // subquery plan, and not under its left side, which is the outer plan.
+ assert(existenceJoins.forall(j =>
semiOrAnti.get.right.exists(_.fastEquals(j))),
+ s"the existence join must sit on the subquery side in\n$plan")
+ }
+ checkAnswer(df, expected)
+ }
+
+ test("SPARK-59351: nested subquery referencing the inner query becomes an
existence join") {
+ // SPARK-45580 covers the case where the nested subquery references the
outer query, in which
+ // case its existence join is built on top of the outer plan. Here the
nested subquery
+ // references the query it is nested in, so the existence join has to be
built on top of the
+ // subquery plan instead.
+ withTempView("t1", "t2", "t3", "t3n", "t4", "t5") {
+ Seq((1), (2), (3), (7),
(9)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ // t3 shares a value with t2, t5 does not, so the nested subquery
decides the answer below.
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+ Seq((3), (7)).toDF("col1").persist().createOrReplaceTempView("t5")
+ Seq(Some(3), Some(9),
None).toDF("col1").persist().createOrReplaceTempView("t3n")
+ // A correlated nested IN over t4 is false for every c1 in t2, while the
same IN without its
+ // correlated predicate is true for 1 and 9, so the correlation decides
the answer below.
+ Seq((1, 9), (9, 1)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+
+ // EXISTS rewritten as a left semi join. The correlated predicate is a
disjunction, so it
+ // is pulled up as a whole and carries the nested IN-subquery, which
references c1, out of
+ // the subquery plan.
+ val query1 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query1, Row(1) :: Row(2) :: Row(3) :: Row(7) ::
Row(9) :: Nil)
+
+ // Same over t5, which shares no value with t2, so the nested IN is
false for every c1 and
+ // only the correlated predicate can hold: a mistake making it true
would return every row.
+ val query2 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t5)
+ |)""".stripMargin
+ checkAnswerAndPlan(query2, Row(1) :: Row(9) :: Nil)
+
+ // NOT EXISTS rewritten as a left anti join.
+ val query3 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE NOT EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t5)
+ |)""".stripMargin
+ checkAnswerAndPlan(query3, Row(2) :: Row(3) :: Row(7) :: Nil)
+
+ // IN-subquery rewritten as a left semi join. The hoisted predicate is a
> c1 rather than
+ // the key equality a = c1, so the answer is a IN (t2 INTERSECT t3) and
depends on the
+ // nested subquery: dropping it would leave no row at all.
+ val query4 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR c1 IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query4, Row(9) :: Nil)
+
+ // NOT IN-subquery rewritten as a null-aware left anti join, with a
nested EXISTS. Only the
+ // nested EXISTS keeps 9 out of the answer, as a > c1 alone does not
hold for it.
+ val query5 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a NOT IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR EXISTS (SELECT 1 FROM t3 WHERE col1 = c1)
+ |)""".stripMargin
+ checkAnswerAndPlan(query5, Row(1) :: Row(2) :: Row(3) :: Row(7) :: Nil)
+
+ // A nested NOT IN-subquery keeps its null-aware semantics: c1 NOT IN
(3, 9, NULL) is never
+ // true, so only the correlated predicate can be satisfied. Compare with
query7, where the
+ // same NOT IN over a relation without NULL holds for c1 = 1 and returns
every row.
+ val query6 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 NOT IN (SELECT col1 FROM t3n)
+ |)""".stripMargin
+ checkAnswerAndPlan(query6, Row(1) :: Row(9) :: Nil)
+
+ val query7 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR c1 NOT IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ checkAnswerAndPlan(query7, Row(1) :: Row(2) :: Row(3) :: Row(7) ::
Row(9) :: Nil)
+
+ // A nested subquery correlated to the query it is nested in, on a
column it does not
+ // project, so its correlated predicate changes the answer: without it
the nested IN would
+ // hold for c1 = 1 and row 1 would be returned as well.
+ val query8 =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT c1
+ | FROM t2
+ | WHERE a > c1
+ | OR c1 IN (SELECT col1 FROM t4 WHERE k = c1)
+ |)""".stripMargin
+ checkAnswerAndPlan(query8, Row(2) :: Row(3) :: Row(7) :: Row(9) :: Nil)
+ }
+ }
+
+ test("SPARK-59351: nested subquery referencing both the outer and the inner
query") {
+ withTempView("t1", "t2", "t3", "t4") {
+ Seq((1), (2), (3)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+ // Correlated, this is false for every c1 in t2; without its correlated
predicate it holds
+ // for 1 and 9, so the correlation decides the answer below.
+ Seq((1, 9), (9, 1)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+
+ // The nested subquery references the outer query through its values and
the inner query
+ // through its own correlated predicate, so it can be rewritten into an
existence join on
+ // neither side and stays in the join condition. Planning it there as an
in-subquery filter
+ // drops its correlated predicate col1 = c1, which is why it is rejected
rather than left.
+ // These rows do not distinguish the two forms; the EXISTS form of this
shape does, and
+ // returned an extra row before the rejection was added.
+ //
+ // NOT IN is the outer predicate on purpose: its rewrite returns a bare
Join, which
+ // RewritePredicateSubquery does not offer to its own handling of
predicate subqueries in
+ // join conditions, so this rejection is the only one that can fire and
the assertion below
+ // pins it. The EXISTS form of this query fails on the same condition,
raised by the same
+ // rejection in rewriteExistentialExprInSubqueryPlan before any join
exists; were that
+ // rejection removed, the EXISTS form would instead reach the
join-condition handling, which
+ // rejects it with UNSUPPORTED_CORRELATED_EXPRESSION_IN_JOIN_CONDITION
under the default
+ // configuration, so only the NOT IN form pins this rejection on its own.
+ val correlated =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE a NOT IN (
+ | SELECT c1
+ | FROM t2
+ | WHERE a = c1
+ | OR a IN (SELECT col1 FROM t3 WHERE col1 = c1)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ val e = intercept[AnalysisException](sql(correlated).collect())
+ assert(e.getCondition == "UNSUPPORTED_SUBQUERY_EXPRESSION_CATEGORY."
+
+ "NESTED_SUBQUERY_REFERENCING_OUTER_AND_INNER_QUERY")
+ // The message must name the subquery that was rejected.
+ val reported = e.getMessageParameters.get("subqueryExpression")
+ assert(reported.contains("IN") && reported.contains("listquery"),
+ s"unexpected subqueryExpression: $reported")
+ }
+ }
+
+ // A correlated predicate that BooleanSimplification has eliminated:
+ // PullupCorrelatedPredicates retains c1 as an outer attribute of the
nested subquery for
+ // idempotency, but the subquery
+ // no longer reads it, so there is no condition to lose. It must still
be rewritten against
+ // the outer plan, which is the only plan it effectively references,
rather than be treated
+ // as referencing the subquery plan and rejected.
+ val simplifiedAwayCorrelation =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR a IN (SELECT col1 FROM t3 WHERE false AND col1 = c1)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ checkAnswer(sql(simplifiedAwayCorrelation), Row(1) :: Nil)
+ }
+ }
+
+ // A subquery that stays in the join condition stays there whole, since
the rewrite does
+ // not descend into one it declines, so a correlated subquery below it
is left as well.
+ // Its own references make it look routable, being owned by the subquery
plan, but
+ // nothing reaches it and planning a list query as an in-subquery filter
drops the
+ // predicate the pull-up hoisted into it. The enclosing subquery is
rejected for
+ // carrying it: PostgreSQL and DuckDB return 1 and 3 here, and losing
the correlation
+ // returns 2 as well.
+ val carriedCorrelation =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR (a + (CASE WHEN c1 IN (SELECT col1 FROM t4 WHERE k = c1) THEN
1 ELSE 0 END))
+ | IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ val e =
intercept[AnalysisException](sql(carriedCorrelation).collect())
+ assert(e.getCondition == "UNSUPPORTED_SUBQUERY_EXPRESSION_CATEGORY."
+
+ "NESTED_SUBQUERY_REFERENCING_OUTER_AND_INNER_QUERY")
+ }
+ }
+
+ // An uncorrelated nested subquery referencing both queries has no
correlated predicate to
+ // lose, so it stays in the join condition and is planned as an
in-subquery filter. The
+ // configuration is disabled because the rewrite of predicate subqueries
in join conditions
+ // rejects a subquery referencing both join inputs, which is what this
one becomes.
+ val uncorrelated =
+ """
+ |SELECT *
+ |FROM t1
+ |WHERE EXISTS (
+ | SELECT 1
+ | FROM t2
+ | WHERE a = c1
+ | OR (a + c1) IN (SELECT col1 FROM t3)
+ |)""".stripMargin
+ withSQLConf(
+ SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
"false") {
+ // No existence join here: this subquery stays in the join condition,
which is the
+ // point of the case, so only the result and the reachability of the
plan are
+ // checked.
+ checkAnswerAndPlan(uncorrelated, Row(1) :: Row(2) :: Nil,
+ existenceJoinOnSubqueryPlan = false)
+ }
+ }
+ }
+
+ test("SPARK-59351: existential subquery carried by a rewritten nested
subquery") {
+ // The nested IN over t4 is owned by the subquery plan, so it is rewritten
into an existence
+ // join and the condition PullupCorrelatedPredicates hoisted into it is
grafted onto that
+ // join. That condition carries a third-level IN correlated to t4, which
references neither
+ // the outer nor the subquery plan and so is routed by neither of the
guards above. It has to
+ // be rewritten against the inputs of the join just built: left in place,
PlanSubqueries plans
+ // it as an in-subquery filter and drops its own correlated predicate col1
= k, which returns
+ // every row of t1 instead of the one row where the correlation holds.
+ withTempView("t1", "t2", "t4", "t5") {
+ Seq(1, 2, 3).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq(1, 8, 9).toDF("c1").persist().createOrReplaceTempView("t2")
+ // No k equals any c1, so only the third-level IN can satisfy the
hoisted disjunction, and
+ // its correlated predicate col1 = k is false for every row of t4:
dropping it makes the
+ // level-2 IN hold for c1 = 1 and returns 1, 2 and 3.
+ Seq((1, 100), (9, 7)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+ Seq(1).toDF("col1").persist().createOrReplaceTempView("t5")
+ val query =
+ """SELECT * FROM t1 WHERE EXISTS (
+ | SELECT 1 FROM t2
+ | WHERE a = c1
+ | OR c1 IN (SELECT col1 FROM t4
+ | WHERE k = c1 OR col1 IN (SELECT col1 FROM t5 WHERE col1
= k)))""".stripMargin
+ // The routing must not depend on the rewrite of predicate subqueries in
join conditions,
+ // which is what used to make these two configurations disagree: it
reached the grafted
+ // condition only when enabled.
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ checkAnswerAndPlan(query, Row(1) :: Nil)
+ }
+ }
+ }
+ }
+
+ test("SPARK-59351: a carried subquery is classified as on the subquery-plan
route") {
+ // The carried router applies the same rules as
rewriteExistentialExprInSubqueryPlan, against
+ // the inputs of the existence join rather than the outer and the subquery
plan.
+ withTempView("t1", "t2", "t4", "t5", "t3n", "t5n") {
+ Seq(1, 2, 3).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq(1, 8, 9).toDF("c1").persist().createOrReplaceTempView("t2")
+ Seq((9, 7)).toDF("col1", "k").persist().createOrReplaceTempView("t4")
+ Seq(Some(3), None).toDF("x").persist().createOrReplaceTempView("t3n")
+ Seq((Some(3), 7)).toDF("x", "k").persist().createOrReplaceTempView("t5n")
+
+ // A carried NOT IN is collected as the Not over the IN, so the rewrite
takes its null-aware
+ // arm. Taking the positive-IN arm instead leaves NOT exists over a
condition that ignores
+ // NULL comparisons: 5 NOT IN (NULL) is unknown, so the t4 row is
excluded and the answer is
Review Comment:
Confirmed: the comment now names n4's (5, 100) and n1's 1 and 2, which match
the case's own fixtures.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4369134666","thread_id":"inline:4369134666","verdict_sha256":"596d6ef5f193363401f54af770e62e1e49b3bfd27c84efadb74d430a0c108603"}
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
