cloud-fan commented on code in PR #58656:
URL: https://github.com/apache/spark/pull/58656#discussion_r4281437494
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/subquery.scala:
##########
@@ -184,8 +188,12 @@ object RewritePredicateSubquery extends Rule[LogicalPlan]
with PredicateHelper {
// Use EXISTS if performance matters to you.
// Deduplicate conflicting attributes if any.
- val newSub = dedupSubqueryOnSelfJoin(p, sub, Some(values))
- val inConditions = values.zip(newSub.output).map(EqualTo.tupled)
+ val dedupSub = dedupSubqueryOnSelfJoin(p, sub, Some(values))
+ val inConditions = values.zip(dedupSub.output).map(EqualTo.tupled)
+ // The hoisted correlated predicates may carry existential
sub-queries that only the
+ // sub-query plan can evaluate, see
rewriteExistentialExprInJoinCondition.
+ val (subConditions, newSub) =
+ rewriteExistentialExprInSubqueryPlan(conditions, p, dedupSub)
Review Comment:
**Non-blocking (P2):** The NOT IN arm now routes its hoisted conditions
through `rewriteExistentialExprInSubqueryPlan`, which throws
`NESTED_IN_SUBQUERY_WITH_UNKNOWN_RESULT` for any nullable nested IN owned by
the subquery plan in a value position, whether it is correlated or not. At the
merge base this arm appended `conditions` unchanged to the null-aware LeftAnti
condition and returned a bare `Join`, which `RewritePredicateSubquery` does not
revisit. `PlanSubqueries` then evaluated an uncorrelated nested IN there
through `InSubqueryExec`, which is three-valued. So a query that used to return
the right rows now fails:
```sql
-- t1(a) = 1, 2, 3; t2(c1) = 1, 8, 9; t3n(col1) = 3, NULL
SELECT * FROM t1 WHERE a NOT IN (
SELECT c1 FROM t2 WHERE a = c1 OR ((c1 IN (SELECT col1 FROM t3n)) <=>
false));
```
The merge base returns 2 and 3, as standard SQL does; this PR raises 0A000.
`IS NULL`, `COALESCE(..., true)` and a nested NOT IN under `<=> false` behave
the same way. The rejection exists because an existence join's `exists` bit
cannot carry the unknown, but for an uncorrelated residual left in this
anti-join condition no existence bit is built, and there is no hoisted
condition to lose. The EXISTS, NOT EXISTS and IN arms are not affected: at the
merge base they rewrote such an IN on the outer plan and failed with
INTERNAL_ERROR. The new `NESTED_IN_SUBQUERY_WITH_UNKNOWN_RESULT` tests use only
an outer EXISTS, so nothing covers this arm.
**Recommended change:** Let the NOT IN arm keep uncorrelated,
unknown-sensitive, subquery-plan-owned nested INs (no hoisted joinCond and no
correlated descendant) as residuals in its anti-join condition, as at the merge
base, instead of rejecting them. Still reject correlated ones, and still
rewrite truth-only ones as now. Add SubquerySuite cases with an outer NOT IN
for the value-position shapes.
**Why this works:** The helper takes an arm-supplied policy for residuals
that stay three-valued. Under that policy an uncorrelated unknown-sensitive IN
is declined by canRewrite and excluded from the unknown-result rejection, so it
stays in the bare anti join and InSubqueryExec evaluates it, exactly as before
the PR.
**Scope:** Exempt uncorrelated three-valued residuals from the
unknown-result rejection in the NOT IN arm only, and test the NOT IN outer
shapes.
**Compatibility:** EXISTS, NOT EXISTS and IN arms keep their current
rejections.
**Risks:** If a future change makes the NOT IN arm's join revisitable, a
residual left in place could be rewritten two-valued by the join-condition
handler; a comment should tie the exemption to the bare-Join result.
**Constraints:** Do not exempt correlated residuals, whose hoisted condition
PlanSubqueries would drop. Leave EXISTS, NOT EXISTS and IN arm behavior
unchanged.
**Success:** `SELECT * FROM t1 WHERE a NOT IN (SELECT c1 FROM t2 WHERE a =
c1 OR ((c1 IN (SELECT col1 FROM t3n)) <=> false))` with t3n = (3, NULL) returns
2, 3 as at the merge base. The same predicate with a correlated nested IN under
an outer NOT IN is still rejected.
**Verification:**
- **Regression:** Under an outer NOT IN, uncorrelated nullable nested INs in
value positions (<=> false, IS NULL, COALESCE(.., true), nested NOT IN under
<=> false) return the standard SQL answer instead of an error.
- **Compatibility:** Correlated value-position nested INs under NOT IN are
still rejected, and truth-only nested INs under NOT IN still return correct
rows.
##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/statsEstimation/JoinEstimationSuite.scala:
##########
@@ -466,6 +466,51 @@ class JoinEstimationSuite extends StatsEstimationTestBase {
}
}
+ test("existence join") {
+ // table2 (key-1-2 int, key-2-4 int): (1, 2), (2, 3), (2, 4)
+ // table3 (key-1-2 int, key-2-3 int): (1, 2), (2, 3)
+ // An existence join returns every row of its left child with one extra
Boolean attribute, so
+ // its cardinality is the left child's and its width is the left child's
plus that attribute.
+ // The right child's cardinality must not enter either, as the generic
product estimate would
+ // have it, since that can disqualify a broadcast of an otherwise small
build side.
+ val exists = AttributeReference("exists", BooleanType, nullable = false)()
+ val join = Join(table2, table3, ExistenceJoin(exists),
+ Some(EqualTo(nameToAttr("key-2-4"), nameToAttr("key-2-3"))),
JoinHint.NONE)
+
+ val expectedStats = Statistics(
+ // Three rows of the left child, each widened by the Boolean, whose
default size is 1.
+ sizeInBytes = 3 * (8 + 4 * 2 + 1),
+ rowCount = Some(3),
+ // Only the left child's column stats: the right child's describe
attributes that an
+ // existence join does not output.
+ attributeStats = AttributeMap(Seq(nameToColInfo("key-1-2"),
nameToColInfo("key-2-4"))))
+ assert(join.stats == expectedStats)
+ }
+
+ test("existence join with an empty or unestimated right child") {
+ // Only the left child's row count enters the estimate, so a right child
with no row count,
Review Comment:
**Nit (P3):** This says a right child "with no row count, or with none" must
not stop the estimate, but every right child here reports a row count.
`StatsTestPlan` takes a required `rowCount: BigInt`, and its `computeStats`
always returns `rowCount = Some(rowCount)`, so `emptyRight` has 0 and
`noStatsRight` has 2; only its column statistics are missing. If
`estimateExistenceJoin`'s `rowCountsExist(join.left)` were tightened to
`rowCountsExist(join.left, join.right)`, this test would stay green, and so
would the BasicStatsEstimationSuite case, whose right child has rowCount 2000.
A fixture whose statistics have `rowCount = None` would pin the left-only
precondition that the scaladoc documents. The comment should also name the
cases the test actually builds: "or with none" has no referent.
**Verification:**
- **Regression:** An existence join whose right child reports no row count
is estimated from the left child exactly as for a right child with statistics.
- **Inspection:** The comment's listed cases match the fixtures the test
builds.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/subquery.scala:
##########
@@ -398,62 +406,481 @@ object RewritePredicateSubquery extends
Rule[LogicalPlan] with PredicateHelper {
(newExpr, newPlan)
}
+ /**
+ * 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 =
+ 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 = 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 = 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; attributing it to `outerPlan` instead would let a single
shared attribute
Review Comment:
**Nit (P3):** The two paragraphs describe different alternatives to
subquery-first attribution. This one says attributing a shared attribute to
`outerPlan` "instead" would satisfy both sides and get an inner-only nested
subquery rejected as referencing both. With the exclusive probes in
`planReferences`, a swap only sets `outerPlanOnlyReference`, so `bothPlans`
stays false; the claim holds only if the attribute counts for the outer plan as
well. The paragraph below says the RewriteSubquerySuite fixture ends in the
same error "whichever plan the shared attribute is attributed to". That holds
for a swap, but not for the 'as well' reading: there the fixture's nested IN,
whose joinCond `col1 = a` is non-empty, is rejected with
`NESTED_SUBQUERY_REFERENCING_OUTER_AND_INNER_QUERY` before `buildJoin`'s dedup
check. The fixture comment also uses the 'as well' reading. Please pick one
alternative and state its outcome consistently in both paragraphs and in the
fixture comment.
This extends an [existing
discussion](https://github.com/apache/spark/pull/58656#discussion_r4257086406).
**Verification:**
- **Inspection:** Each stated outcome matches the exclusive probe order in
planReferences and the error the fixture asserts.
##########
sql/core/src/test/scala/org/apache/spark/sql/SubquerySuite.scala:
##########
@@ -3227,4 +3224,540 @@ 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.
With EXISTS the rewrite
+ // returns a Project over the join, which that handling then rejects on
its own under the
+ // default configuration, and the assertion would hold either way.
Review Comment:
**Nit (P3):** The EXISTS half of this rationale no longer holds. Suppose the
outer predicate were EXISTS and the new throw were removed. The join-condition
handler would then reject with
`UNSUPPORTED_CORRELATED_EXPRESSION_IN_JOIN_CONDITION`, but this test asserts
`NESTED_SUBQUERY_REFERENCING_OUTER_AND_INNER_QUERY`, so the assertion would
fail rather than "hold either way". The explanation dates from when both
rejections raised the same condition. NOT IN is still a reasonable choice here;
only the explanation needs to change, or the EXISTS claim can be dropped.
This extends an [existing
discussion](https://github.com/apache/spark/pull/58656#discussion_r4046157775).
**Verification:**
- **Inspection:** The comment's discrimination claim matches the asserted
condition and the configurations the loop runs.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/subquery.scala:
##########
@@ -398,62 +406,481 @@ object RewritePredicateSubquery extends
Rule[LogicalPlan] with PredicateHelper {
(newExpr, newPlan)
}
+ /**
+ * 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 =
+ 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 = 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 = 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; attributing it to `outerPlan` instead would let a single
shared attribute
+ * satisfy both sides of the classification and have a nested sub-query
referencing only the
+ * inner query rejected as referencing both.
+ *
+ * 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:
`dedupSubqueryOnSelfJoin`'s pre-existing
+ * conflict check reports the duplicated attribute first, so it ends in the
same error whichever
+ * plan the shared attribute is attributed to.
+ *
+ * An attribute neither plan produces leaves both answers false, which
declines the rewrite
+ * without rejecting the sub-query, as a sub-query referencing neither plan
can be left in the
+ * join condition unharmed.
+ */
+ 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
+ * rewritten. NOT IN is rewritten with a null-aware join condition of its
own, which is equally
+ * two-valued, so it is rejected there too.
+ *
+ * Returns the rewritten condition along with the updated outer and
sub-query plans.
+ */
+ private def rewriteExistentialExprInJoinCondition(
+ conditions: Seq[Expression],
+ outerPlan: LogicalPlan,
+ subPlan: LogicalPlan): (Option[Expression], LogicalPlan, LogicalPlan) = {
+ val (subCond, newSubPlan) =
+ rewriteExistentialExprInSubqueryPlan(conditions, outerPlan, subPlan)
+ // The sub-queries that do not reference the sub-query plan are rewritten
against the outer
+ // plan, as they only reference attributes of the outer plan, if any. This
accepts on the
+ // negation of the test above rather than on a positive one, which rests
on the invariant that
+ // `effectiveReferences` sees every attribute the rewrite can put in a
join condition: one it
+ // cannot see would be rewritten here and end up in a condition the outer
plan cannot evaluate.
+ // A positive test is not available without also refusing the sub-queries
whose retained outer
+ // attributes no longer correspond to a condition, which must keep being
rewritten here.
+ val (newCond, newOuterPlan, _) = rewriteExistentialExprWithAttrs(
+ subCond.toSeq, outerPlan, e => !effectivelyReferencesPlan(e, subPlan))
+ (newCond, newOuterPlan, newSubPlan)
+ }
+
+ /**
+ * Rewrites the existential sub-queries in `conditions` that can only be
evaluated by the
+ * sub-query plan, that is those referencing the sub-query plan but not the
outer plan, into
+ * existence joins on top of the sub-query plan. See
+ * [[rewriteExistentialExprInJoinCondition]] for details.
+ *
+ * Returns the rewritten condition along with the updated sub-query plan.
+ */
+ private def rewriteExistentialExprInSubqueryPlan(
+ conditions: Seq[Expression],
+ outerPlan: LogicalPlan,
+ subPlan: LogicalPlan): (Option[Expression], LogicalPlan) = {
+ // The rejection collector below is a plain `collect`, which visits every
node of the hoisted
+ // conditions whether or not it can hold a sub-query, so skip the
classification entirely when
+ // they hold none at all, which is the common case for a correlated EXISTS
or IN.
+ // [[collectUnknownSensitiveInSubqueries]] prunes subquery-free subtrees
on its own, so this
+ // guard only saves it the top-level call.
+ if (!conditions.exists(_.containsAnyPattern(EXISTS_SUBQUERY,
IN_SUBQUERY))) {
+ return (conditions.reduceOption(And), subPlan)
+ }
+ // A sub-query left in the join condition loses its own join condition
when it is planned
+ // there, so a correlated one would silently return a wrong result: reject
it instead. The
+ // same holds for a correlated sub-query nested below one that is left
there, since the
+ // rewrite leaves a declined sub-query whole, children included, and
nothing else will reach
+ // it: see carriesCorrelatedSubquery. Note that this walks the whole
expression, including the
+ // join condition of a sub-query the rewrite declines to descend into,
which is deliberate for
+ // the same reason.
+ //
+ // Which plan a candidate references is asked of it up to three times
below, once for the
+ // rejection of a sub-query referencing both plans, once to keep only the
unknown-sensitive
+ // ones the sub-query plan owns, and once more by the rewrite itself. Both
answers come from
+ // the same reference set in a single pass over it, and the result is
memoised per candidate,
+ // so neither the set nor the scan is repeated. The memo is keyed by
identity: the candidates
+ // are nodes of the expressions being classified, and comparing two of
them structurally would
+ // compare the sub-query plans they hold.
+ val classified = new java.util.IdentityHashMap[Expression,
PlanReferences]()
+ def classify(sq: Expression): PlanReferences = {
+ var references = classified.get(sq)
+ if (references == null) {
+ references = planReferences(effectiveReferences(sq), outerPlan,
subPlan)
+ classified.put(sq, references)
+ }
+ references
+ }
+ def ownedBySubPlan(sq: Expression): Boolean = classify(sq).subPlanOnly
+ def referencesBothPlans(sq: Expression): Boolean = classify(sq).bothPlans
+ val referencingBothPlans = conditions.flatMap(_.collect {
+ case sq @ (_: Exists | _: InSubquery)
+ if referencesBothPlans(sq) &&
+ (hasCorrelatedCondition(sq) || carriesCorrelatedSubquery(sq)) => sq
+ })
+ if (referencingBothPlans.nonEmpty) {
+ throw
QueryCompilationErrors.nestedSubqueryReferencingOuterAndInnerQueryError(
+ referencingBothPlans)
+ }
+ // An IN sub-query whose result can be unknown cannot be represented by
the `exists` attribute
+ // of an existence join once that result is observable, see above.
+ val unknownResult = conditions
+ .flatMap(unknownSensitiveInSubqueries(_, truthOnly = true))
+ .filter(ownedBySubPlan)
+ if (unknownResult.nonEmpty) {
+ throw
QueryCompilationErrors.nestedInSubqueryWithUnknownResultError(unknownResult)
+ }
+ val (newCond, newSubPlan, _) =
+ rewriteExistentialExprWithAttrs(conditions, subPlan, ownedBySubPlan)
+ (newCond, newSubPlan)
+ }
+
+ /**
+ * Collects the IN sub-queries in `expr` whose result can be unknown and
whose value is observed
+ * beyond being TRUE, so that rewriting them into an existence join, whose
`exists` attribute is
+ * FALSE where IN is unknown, would be observable. See
[[rewriteExistentialExprInJoinCondition]].
+ *
+ * `truthOnly` states whether the value of `expr` is only ever tested for
being TRUE, which is
+ * where unknown and FALSE cannot be told apart. That holds for the operands
of AND and OR within
+ * a condition that ends up in a Filter or a join condition, and for the
positions
+ * [[ReplaceNullWithFalseInPredicate]] rewrites for the same reason: the
operand of an
+ * `EqualNullSafe` against TRUE, and the predicate of an `If` or of a
`CaseWhen` branch. The
+ * result branches of a conditional are consumed wherever the conditional
itself is, so they
+ * inherit its context rather than being value positions of their own.
+ *
+ * It does not hold under NOT, where `NOT FALSE` is TRUE while `NOT unknown`
is unknown. A NOT
+ * directly over an IN sub-query is still safe, but for another reason: it
is rewritten with a
+ * null-aware join condition of its own, which is TRUE where the comparison
is unknown, so the
+ * negation of its `exists` attribute is FALSE there, as SQL requires.
+ */
+ private def unknownSensitiveInSubqueries(
+ expr: Expression,
+ truthOnly: Boolean): Seq[Expression] = {
+ val reported = ArrayBuffer.empty[Expression]
+ collectUnknownSensitiveInSubqueries(expr, truthOnly, reported)
+ reported.toSeq
+ }
+
+ /**
+ * Appends what [[unknownSensitiveInSubqueries]] reports to `reported`, in
the order the
+ * expression is walked. The results are accumulated rather than
concatenated on the way back up,
+ * so a condition with many reportable sub-queries does not copy the prefix
at every node.
+ */
+ private def collectUnknownSensitiveInSubqueries(
+ expr: Expression,
+ truthOnly: Boolean,
+ reported: ArrayBuffer[Expression]): Unit = expr match {
+ case _ if !expr.containsAnyPattern(EXISTS_SUBQUERY, IN_SUBQUERY) =>
+ case And(left, right) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(right, truthOnly, reported)
+ case Or(left, right) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(right, truthOnly, reported)
+ // `null <=> true` and `false <=> true` are both FALSE, so only truth is
observed here whatever
+ // consumes the comparison.
+ case EqualNullSafe(left, Literal.TrueLiteral) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly = true, reported)
+ case EqualNullSafe(Literal.TrueLiteral, right) =>
+ collectUnknownSensitiveInSubqueries(right, truthOnly = true, reported)
+ // COALESCE(x, false) maps both unknown and FALSE to FALSE, so only truth
is observed. A
+ // different default does not: COALESCE(x, true) is TRUE where x is
unknown and FALSE where x
+ // is FALSE.
+ case Coalesce(child +: rest) if
rest.headOption.contains(Literal.FalseLiteral) =>
+ collectUnknownSensitiveInSubqueries(child, truthOnly = true, reported)
+ case If(predicate, trueValue, falseValue) =>
+ collectUnknownSensitiveInSubqueries(predicate, truthOnly = true,
reported)
+ collectUnknownSensitiveInSubqueries(trueValue, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(falseValue, truthOnly, reported)
+ case CaseWhen(branches, elseValue) =>
+ branches.foreach { case (condition, value) =>
+ collectUnknownSensitiveInSubqueries(condition, truthOnly = true,
reported)
+ collectUnknownSensitiveInSubqueries(value, truthOnly, reported)
+ }
+ elseValue.foreach(collectUnknownSensitiveInSubqueries(_, truthOnly,
reported))
+ // A NOT directly over an IN sub-query keeps its own null-aware rewrite,
so only its operands
Review Comment:
**Nit (P3):** This says a NOT directly over an IN "keeps its own null-aware
rewrite, so only its operands are examined", but the arm calls
`collectOrDescend(not, in, truthOnly, reported)`, which reports the NOT IN
itself when it sits in a value position and may be unknown. That is why `(c1
NOT IN (SELECT col1 FROM t3n)) <=> false` is rejected, and the test asserts a
reported expression starting with `(NOT `. The null-aware rewrite makes a NOT
IN safe only where just truth is observed, so the comment should say the NOT IN
is reported in a value position and descended into otherwise.
This extends an [existing
discussion](https://github.com/apache/spark/pull/58656#discussion_r4068594158).
**Verification:**
- **Inspection:** The comment matches collectOrDescend's behavior and the
rewriteExistentialExprInJoinCondition scaladoc.
##########
sql/core/src/test/scala/org/apache/spark/sql/SubquerySuite.scala:
##########
@@ -3227,4 +3224,540 @@ 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.
With EXISTS the rewrite
+ // returns a Project over the join, which that handling then rejects on
its own under the
+ // default configuration, and the assertion would hold either way.
+ 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: nested IN subquery whose result can be unknown") {
+ withTempView("t1", "t2", "t2n", "t3n", "t3", "t4", "tb", "t2r", "t2rn",
"t6", "t7") {
+ Seq((1), (2), (3)).toDF("a").persist().createOrReplaceTempView("t1")
+ Seq((1), (8), (9)).toDF("c1").persist().createOrReplaceTempView("t2")
+ // A nullable compared value, against a subquery column that is not
nullable.
+ Seq(Some(1), None).toDF("c1").persist().createOrReplaceTempView("t2n")
+ Seq((1, 1), (9, 9)).toDF("col1",
"k").persist().createOrReplaceTempView("t4")
+ // A boolean relation, to compare the result of a nested IN subquery
against.
+ Seq(false).toDF("b").persist().createOrReplaceTempView("tb")
+ // Row-valued shapes. t2r and t7 are not nullable anywhere; the
nullability of t2rn and of
+ // t6 sits in the second field, so the first pair of the comparison does
not expose it.
+ Seq((1, 1), (8, 8), (9, 9)).toDF("c1",
"c2").persist().createOrReplaceTempView("t2r")
+ Seq((1, Option.empty[Int]), (8, Some(8))).toDF("c1", "c2n").persist()
+ .createOrReplaceTempView("t2rn")
+ Seq((1, Option.empty[Int]), (5, Some(5))).toDF("col1", "col2").persist()
+ .createOrReplaceTempView("t6")
+ Seq((1, 1), (5, 5)).toDF("col1",
"col2").persist().createOrReplaceTempView("t7")
+ // The NULL matches no value of t2, so c1 IN (SELECT col1 FROM t3n) is
unknown there, and
+ // c1 NOT IN (SELECT col1 FROM t3n) is never true.
+ Seq(Some(3), None).toDF("col1").persist().createOrReplaceTempView("t3n")
+ Seq((3), (9)).toDF("col1").persist().createOrReplaceTempView("t3")
+
+ // An existence join only records whether a row matched, so its exists
attribute is false
+ // where IN is unknown. That is not observable while the value feeds a
predicate, but it is
+ // once it reaches anything else, so these are rejected rather than
rewritten. Both
+ // configurations are checked, as the rejection must not depend on the
rewrite of predicate
+ // subqueries in join conditions.
+ Seq(
+ "(c1 IN (SELECT col1 FROM t3n)) <=> false",
+ "(c1 IN (SELECT col1 FROM t3n)) IS NULL",
+ // COALESCE to a non-false default does tell unknown from false.
+ "COALESCE(c1 IN (SELECT col1 FROM t3n), true)",
+ "(c1 NOT IN (SELECT col1 FROM t3n)) <=> false").foreach { predicate =>
+ Seq("true", "false").foreach { decorrelateInJoinCondition =>
+
withSQLConf(SQLConf.DECORRELATE_PREDICATE_SUBQUERIES_IN_JOIN_CONDITION.key ->
+ decorrelateInJoinCondition) {
+ val e = intercept[AnalysisException] {
+ sql(s"SELECT * FROM t1 WHERE EXISTS (SELECT 1 FROM t2 WHERE a =
c1 OR $predicate)")
+ .collect()
+ }
+ assert(e.getCondition ==
"UNSUPPORTED_SUBQUERY_EXPRESSION_CATEGORY." +
+ "NESTED_IN_SUBQUERY_WITH_UNKNOWN_RESULT")
+ // A NOT IN must be reported as a NOT IN, not as the IN underneath
it.
+ val reported = e.getMessageParameters.get("subqueryExpression")
+ assert(reported.startsWith("(NOT ") == predicate.contains("NOT
IN"),
+ s"unexpected subqueryExpression for $predicate: $reported")
+ }
+ }
+ }
+
+ // The ordinary case: the value of the nested IN feeds a predicate,
where unknown and
+ // false cannot be told apart, so it is still rewritten even though it
can be unknown.
+ checkAnswerAndPlan(
+ """SELECT * FROM t1 WHERE EXISTS (
+ | SELECT 1 FROM t2 WHERE a = c1 OR c1 IN (SELECT col1 FROM
t3n))""".stripMargin,
+ Row(1) :: Nil)
+
+ // And a nested IN that cannot be unknown is rewritten even outside a
predicate.
+ checkAnswerAndPlan(
+ """SELECT * FROM t1 WHERE EXISTS (
+ | SELECT 1 FROM t2
+ | WHERE a = c1 OR ((c1 IN (SELECT col1 FROM t3)) <=>
false))""".stripMargin,
+ Row(1) :: Row(2) :: Row(3) :: Nil)
+
+ // Only truth is observed by `<=> true`, by an IF predicate and by a
CASE WHEN
+ // condition, so those are rewritten rather than rejected.
SimplifyConditionals folds
+ // the latter two into the first, so ordinary SQL reaches this position.
+ //
+ // The result branches of a conditional are consumed wherever the
conditional is, so
+ // under a filter predicate they are truth-only as well. The last two
cases do not
Review Comment:
**Nit (P3):** "The last two cases do not fold" points at the wrong entries.
`SimplifyConditionals` folds an `If` or `CaseWhen` only when its branches are
TRUE/FALSE literals, or null literals with a non-nullable condition. So all
three result-branch cases stay unfolded: `IF(c1 > 0, ..., false)`, `CASE WHEN
c1 > 0 THEN ... ELSE false END` and `CASE WHEN c1 > 100 THEN false ELSE ...
END`. The last two entries are the ELSE-branch CASE and `COALESCE(..., false)`,
which is not a conditional and has its own comment. Naming the three
conditional cases would match what they exercise.
**Verification:**
- **Inspection:** The cases named as non-folding are exactly those
SimplifyConditionals leaves unfolded.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/subquery.scala:
##########
@@ -398,62 +406,393 @@ object RewritePredicateSubquery extends
Rule[LogicalPlan] with PredicateHelper {
(newExpr, newPlan)
}
+ /**
+ * 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 =
+ 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 = 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 = 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, which allocates
nothing.
+ // AttributeSet.intersect materialises a set from its argument, so the
operand order there
+ // would decide whether this walks the references or the whole output of
`plan`.
+ 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)
+ }
+
+ /**
+ * Returns true if `e` effectively references an attribute that `plan`
produces and `sharedWith`
+ * does not, see [[effectiveReferences]].
+ *
+ * An attribute that both plans produce is attributed to `sharedWith` rather
than to `plan`.
+ * This matters when the outer and the sub-query plan share ExprIds, which a
self-join can leave
+ * for the optimizer to deduplicate (SPARK-21835): the EXISTS arms classify
against the raw
+ * sub-query plan, while the IN arms classify against the plan that
+ * `dedupSubqueryOnSelfJoin` has already separated from the outer plan.
Without this a single
+ * shared attribute would satisfy both sides of the classification, so a
nested sub-query that
+ * references only the sub-query it is nested in would be taken for one
referencing both plans
+ * and rejected. A nested sub-query resolves in the scope of that sub-query,
so a shared
+ * attribute is one of its own.
+ */
+ private def effectivelyReferencesPlanOnly(
+ e: Expression,
+ plan: LogicalPlan,
+ sharedWith: LogicalPlan): Boolean = {
+ effectiveReferences(e).exists { attr =>
+ plan.outputSet.contains(attr) && !sharedWith.outputSet.contains(attr)
+ }
+ }
+
+ /**
+ * 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.
+ */
+ private def effectiveReferences(e: Expression): AttributeSet = e match {
+ case Exists(_, _, _, joinCond, _) =>
AttributeSet(joinCond.flatMap(_.references))
+ case Not(in: InSubquery) => effectiveReferences(in)
+ case InSubquery(values, ListQuery(_, _, _, _, joinCond, _)) =>
+ AttributeSet(values.flatMap(_.references) ++
joinCond.flatMap(_.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 can be rewritten into an
existence join on
+ * neither side, so it is left 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 only with
+ *
`spark.sql.optimizer.decorrelatePredicateSubqueriesInJoinPredicate.enabled`
disabled.
+ *
+ * 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
+ * rewritten. NOT IN is rewritten with a null-aware join condition of its
own, which is equally
+ * two-valued, so it is rejected there too.
+ *
+ * Returns the rewritten condition along with the updated outer and
sub-query plans.
+ */
+ private def rewriteExistentialExprInJoinCondition(
+ conditions: Seq[Expression],
+ outerPlan: LogicalPlan,
+ subPlan: LogicalPlan): (Option[Expression], LogicalPlan, LogicalPlan) = {
+ val (subCond, newSubPlan) =
+ rewriteExistentialExprInSubqueryPlan(conditions, outerPlan, subPlan)
+ // The sub-queries that do not reference the sub-query plan are rewritten
against the outer
+ // plan, as they only reference attributes of the outer plan, if any. This
accepts on the
+ // negation of the test above rather than on a positive one, which rests
on the invariant that
+ // `effectiveReferences` sees every attribute the rewrite can put in a
join condition: one it
+ // cannot see would be rewritten here and end up in a condition the outer
plan cannot evaluate.
+ // A positive test is not available without also refusing the sub-queries
whose retained outer
+ // attributes no longer correspond to a condition, which must keep being
rewritten here.
+ val (newCond, newOuterPlan, _) = rewriteExistentialExprWithAttrs(
+ subCond.toSeq, outerPlan, e => !effectivelyReferencesPlan(e, subPlan))
+ (newCond, newOuterPlan, newSubPlan)
+ }
+
+ /**
+ * Rewrites the existential sub-queries in `conditions` that can only be
evaluated by the
+ * sub-query plan, that is those referencing the sub-query plan but not the
outer plan, into
+ * existence joins on top of the sub-query plan. See
+ * [[rewriteExistentialExprInJoinCondition]] for details.
+ *
+ * Returns the rewritten condition along with the updated sub-query plan.
+ */
+ private def rewriteExistentialExprInSubqueryPlan(
+ conditions: Seq[Expression],
+ outerPlan: LogicalPlan,
+ subPlan: LogicalPlan): (Option[Expression], LogicalPlan) = {
+ // Both collectors below match only Exists and InSubquery, and neither
prunes on tree
+ // patterns, so skip them when the hoisted conditions hold no sub-query at
all, which is the
+ // common case for a correlated EXISTS or IN.
+ if (!conditions.exists(_.containsAnyPattern(EXISTS_SUBQUERY,
IN_SUBQUERY))) {
+ return (conditions.reduceOption(And), subPlan)
+ }
+ // A sub-query left in the join condition loses its own join condition
when it is planned
+ // there, so a correlated one would silently return a wrong result: reject
it instead. Note
+ // that this walks the whole expression, including the join condition of a
sub-query that the
+ // rewrite below declines to descend into. That is deliberate: a
correlated sub-query hidden
+ // under a declined one would equally be planned without its join
condition, or reach
+ // execution unevaluable, so it must be rejected even though nothing would
have rewritten it.
+ val referencingBothPlans = conditions.flatMap(_.collect {
+ case sq @ (_: Exists | _: InSubquery)
+ if hasCorrelatedCondition(sq) && effectivelyReferencesPlan(sq,
subPlan) &&
+ effectivelyReferencesPlanOnly(sq, outerPlan, subPlan) => sq
+ })
+ if (referencingBothPlans.nonEmpty) {
+ throw
QueryCompilationErrors.nestedSubqueryReferencingOuterAndInnerQueryError(
+ referencingBothPlans)
+ }
+ // An IN sub-query whose result can be unknown cannot be represented by
the `exists` attribute
+ // of an existence join once that result is observable, see above.
+ val unknownResult = conditions
+ .flatMap(unknownSensitiveInSubqueries(_, truthOnly = true))
+ .filter(sq => effectivelyReferencesPlan(sq, subPlan) &&
+ !effectivelyReferencesPlanOnly(sq, outerPlan, subPlan))
+ if (unknownResult.nonEmpty) {
+ throw
QueryCompilationErrors.nestedInSubqueryWithUnknownResultError(unknownResult)
+ }
+ val (newCond, newSubPlan, _) = rewriteExistentialExprWithAttrs(conditions,
subPlan,
+ e => effectivelyReferencesPlan(e, subPlan) &&
+ !effectivelyReferencesPlanOnly(e, outerPlan, subPlan))
+ (newCond, newSubPlan)
+ }
+
+ /**
+ * Collects the IN sub-queries in `expr` whose result can be unknown and
whose value is observed
+ * beyond being TRUE, so that rewriting them into an existence join, whose
`exists` attribute is
+ * FALSE where IN is unknown, would be observable. See
[[rewriteExistentialExprInJoinCondition]].
+ *
+ * `truthOnly` states whether the value of `expr` is only ever tested for
being TRUE, which is
+ * where unknown and FALSE cannot be told apart. That holds for the operands
of AND and OR within
+ * a condition that ends up in a Filter or a join condition, and for the
positions
+ * [[ReplaceNullWithFalseInPredicate]] rewrites for the same reason: the
operand of an
+ * `EqualNullSafe` against TRUE, and the predicate of an `If` or of a
`CaseWhen` branch. The
+ * result branches of a conditional are consumed wherever the conditional
itself is, so they
+ * inherit its context rather than being value positions of their own.
+ *
+ * It does not hold under NOT, where `NOT FALSE` is TRUE while `NOT unknown`
is unknown. A NOT
+ * directly over an IN sub-query is still safe, but for another reason: it
is rewritten with a
+ * null-aware join condition of its own, which is TRUE where the comparison
is unknown, so the
+ * negation of its `exists` attribute is FALSE there, as SQL requires.
+ */
+ private def unknownSensitiveInSubqueries(
+ expr: Expression,
+ truthOnly: Boolean): Seq[Expression] = {
+ val reported = ArrayBuffer.empty[Expression]
+ collectUnknownSensitiveInSubqueries(expr, truthOnly, reported)
+ reported.toSeq
+ }
+
+ /**
+ * Appends what [[unknownSensitiveInSubqueries]] reports to `reported`, in
the order the
+ * expression is walked. The results are accumulated rather than
concatenated on the way back up,
+ * so a condition with many reportable sub-queries does not copy the prefix
at every node.
+ */
+ private def collectUnknownSensitiveInSubqueries(
+ expr: Expression,
+ truthOnly: Boolean,
+ reported: ArrayBuffer[Expression]): Unit = expr match {
+ case _ if !expr.containsAnyPattern(EXISTS_SUBQUERY, IN_SUBQUERY) =>
+ case And(left, right) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(right, truthOnly, reported)
+ case Or(left, right) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(right, truthOnly, reported)
+ // `null <=> true` and `false <=> true` are both FALSE, so only truth is
observed here whatever
+ // consumes the comparison.
+ case EqualNullSafe(left, Literal.TrueLiteral) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly = true, reported)
+ case EqualNullSafe(Literal.TrueLiteral, right) =>
+ collectUnknownSensitiveInSubqueries(right, truthOnly = true, reported)
+ case If(predicate, trueValue, falseValue) =>
+ collectUnknownSensitiveInSubqueries(predicate, truthOnly = true,
reported)
+ collectUnknownSensitiveInSubqueries(trueValue, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(falseValue, truthOnly, reported)
+ case CaseWhen(branches, elseValue) =>
+ branches.foreach { case (condition, value) =>
+ collectUnknownSensitiveInSubqueries(condition, truthOnly = true,
reported)
+ collectUnknownSensitiveInSubqueries(value, truthOnly, reported)
+ }
+ elseValue.foreach(collectUnknownSensitiveInSubqueries(_, truthOnly,
reported))
+ // A NOT directly over an IN sub-query keeps its own null-aware rewrite,
so only its operands
+ // are examined. Under any other NOT, unknown is observable and
`truthOnly` does not carry.
+ case not @ Not(in: InSubquery) => collectOrDescend(not, in, truthOnly,
reported)
+ case Not(child) =>
+ collectUnknownSensitiveInSubqueries(child, truthOnly = false, reported)
+ case in: InSubquery => collectOrDescend(in, in, truthOnly, reported)
+ case sq: SubqueryExpression =>
+ // Only the hoisted join condition of a sub-query expression is a
predicate, evaluated by
+ // the join it is rewritten into. Its outer attributes are value
expressions.
+ sq.getJoinCond.foreach(
+ collectUnknownSensitiveInSubqueries(_, truthOnly = true, reported))
+ sq.getOuterAttrs.foreach(
+ collectUnknownSensitiveInSubqueries(_, truthOnly = false, reported))
+ case other =>
+ other.children.foreach(
+ collectUnknownSensitiveInSubqueries(_, truthOnly = false, reported))
+ }
+
+ /**
+ * Appends `report` to `reported` if the IN sub-query `in` would lose an
observable unknown, and
+ * otherwise descends into the values it compares and into its list query.
The descent matters
+ * because [[InSubquery]] is a [[Predicate]] rather than a
[[SubqueryExpression]], so an IN
+ * sub-query nested in the values or in the hoisted join condition of
another one is only reached
+ * from here.
+ */
+ private def collectOrDescend(
+ report: Expression,
+ in: InSubquery,
+ truthOnly: Boolean,
+ reported: ArrayBuffer[Expression]): Unit = {
+ if (!truthOnly && inSubqueryMayBeUnknown(in)) {
+ reported += report
+ } else {
+ in.values.foreach(collectUnknownSensitiveInSubqueries(_, truthOnly =
false, reported))
+ collectUnknownSensitiveInSubqueries(in.query, truthOnly, reported)
+ }
+ }
+
+ /**
+ * Returns true if the row comparison of the IN sub-query `in` can evaluate
to unknown, that is
+ * if it can return NULL rather than only TRUE or FALSE. An existence join
cannot represent that
+ * third value, see [[rewriteExistentialExprInJoinCondition]].
+ *
+ * This deliberately does not use `InSubquery.nullable`, which under
+ * `spark.sql.legacy.inSubqueryNullability` (SPARK-43413) reports only the
nullability of the
+ * compared values and ignores that of the list query's columns. What is
protected here is the
+ * three-valued result the rewrite would drop, which does not depend on that
configuration, so
+ * the nullability is re-derived from both sides.
+ */
+ private def inSubqueryMayBeUnknown(in: InSubquery): Boolean = {
+ in.values.zip(in.query.childOutputs).exists { case (v, o) => v.nullable ||
o.nullable }
Review Comment:
Confirmed on 575528ff4b7: inSubqueryMayBeUnknown now zips
`in.values.iterator` with `in.query.childOutputs.iterator`, so it stops at the
first nullable pair.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4139416462","thread_id":"inline:4139416462","verdict_sha256":"666f73c8705c7fc517a3755f43545348abf6bf7b1b48ab8a7138d74dc04fbaa3"}
-->
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/subquery.scala:
##########
@@ -158,20 +159,23 @@ object RewritePredicateSubquery extends Rule[LogicalPlan]
with PredicateHelper {
// Filter the plan by applying left semi and left anti joins.
withSubquery.foldLeft(newFilter) {
case (p, Exists(sub, _, _, conditions, subHint)) =>
- val (joinCond, outerPlan) = rewriteExistentialExpr(conditions, p)
- val join = buildJoin(outerPlan,
rewriteDomainJoinsIfPresent(outerPlan, sub, joinCond),
+ val (joinCond, outerPlan, newSub) =
+ rewriteExistentialExprInJoinCondition(conditions, p, sub)
+ val join = buildJoin(outerPlan,
rewriteDomainJoinsIfPresent(outerPlan, newSub, joinCond),
LeftSemi, joinCond, subHint)
Project(p.output, join)
case (p, Not(Exists(sub, _, _, conditions, subHint))) =>
- val (joinCond, outerPlan) = rewriteExistentialExpr(conditions, p)
- val join = buildJoin(outerPlan,
rewriteDomainJoinsIfPresent(outerPlan, sub, joinCond),
+ val (joinCond, outerPlan, newSub) =
+ rewriteExistentialExprInJoinCondition(conditions, p, sub)
+ val join = buildJoin(outerPlan,
rewriteDomainJoinsIfPresent(outerPlan, newSub, joinCond),
LeftAnti, joinCond, subHint)
Project(p.output, join)
case (p, InSubquery(values, ListQuery(sub, _, _, _, conditions,
subHint))) =>
// Deduplicate conflicting attributes if any.
- val newSub = dedupSubqueryOnSelfJoin(p, sub, Some(values))
- val inConditions = values.zip(newSub.output).map(EqualTo.tupled)
- val (joinCond, outerPlan) = rewriteExistentialExpr(inConditions ++
conditions, p)
+ val dedupSub = dedupSubqueryOnSelfJoin(p, sub, Some(values))
+ val inConditions = values.zip(dedupSub.output).map(EqualTo.tupled)
+ val (joinCond, outerPlan, newSub) =
+ rewriteExistentialExprInJoinCondition(inConditions ++ conditions,
p, dedupSub)
Review Comment:
Thanks, confirmed on 575528ff4b7. Both SizeInBytesOnlyStatsPlanVisitor and
JoinEstimation now estimate an ExistenceJoin from its left child with the
Boolean width added, the statistics suites pin both modes, and the
SubquerySuite test keeps the enclosing semi join broadcast.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4139416473","thread_id":"inline:4139416473","verdict_sha256":"666f73c8705c7fc517a3755f43545348abf6bf7b1b48ab8a7138d74dc04fbaa3"}
-->
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/subquery.scala:
##########
@@ -398,62 +406,393 @@ object RewritePredicateSubquery extends
Rule[LogicalPlan] with PredicateHelper {
(newExpr, newPlan)
}
+ /**
+ * 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 =
+ 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 = 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 = 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, which allocates
nothing.
+ // AttributeSet.intersect materialises a set from its argument, so the
operand order there
+ // would decide whether this walks the references or the whole output of
`plan`.
+ 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)
+ }
+
+ /**
+ * Returns true if `e` effectively references an attribute that `plan`
produces and `sharedWith`
+ * does not, see [[effectiveReferences]].
+ *
+ * An attribute that both plans produce is attributed to `sharedWith` rather
than to `plan`.
+ * This matters when the outer and the sub-query plan share ExprIds, which a
self-join can leave
+ * for the optimizer to deduplicate (SPARK-21835): the EXISTS arms classify
against the raw
+ * sub-query plan, while the IN arms classify against the plan that
+ * `dedupSubqueryOnSelfJoin` has already separated from the outer plan.
Without this a single
+ * shared attribute would satisfy both sides of the classification, so a
nested sub-query that
+ * references only the sub-query it is nested in would be taken for one
referencing both plans
+ * and rejected. A nested sub-query resolves in the scope of that sub-query,
so a shared
+ * attribute is one of its own.
+ */
+ private def effectivelyReferencesPlanOnly(
+ e: Expression,
+ plan: LogicalPlan,
+ sharedWith: LogicalPlan): Boolean = {
+ effectiveReferences(e).exists { attr =>
+ plan.outputSet.contains(attr) && !sharedWith.outputSet.contains(attr)
+ }
+ }
+
+ /**
+ * 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.
+ */
+ private def effectiveReferences(e: Expression): AttributeSet = e match {
+ case Exists(_, _, _, joinCond, _) =>
AttributeSet(joinCond.flatMap(_.references))
+ case Not(in: InSubquery) => effectiveReferences(in)
+ case InSubquery(values, ListQuery(_, _, _, _, joinCond, _)) =>
+ AttributeSet(values.flatMap(_.references) ++
joinCond.flatMap(_.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 can be rewritten into an
existence join on
+ * neither side, so it is left 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 only with
+ *
`spark.sql.optimizer.decorrelatePredicateSubqueriesInJoinPredicate.enabled`
disabled.
+ *
+ * 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
+ * rewritten. NOT IN is rewritten with a null-aware join condition of its
own, which is equally
+ * two-valued, so it is rejected there too.
+ *
+ * Returns the rewritten condition along with the updated outer and
sub-query plans.
+ */
+ private def rewriteExistentialExprInJoinCondition(
+ conditions: Seq[Expression],
+ outerPlan: LogicalPlan,
+ subPlan: LogicalPlan): (Option[Expression], LogicalPlan, LogicalPlan) = {
+ val (subCond, newSubPlan) =
+ rewriteExistentialExprInSubqueryPlan(conditions, outerPlan, subPlan)
+ // The sub-queries that do not reference the sub-query plan are rewritten
against the outer
+ // plan, as they only reference attributes of the outer plan, if any. This
accepts on the
+ // negation of the test above rather than on a positive one, which rests
on the invariant that
+ // `effectiveReferences` sees every attribute the rewrite can put in a
join condition: one it
+ // cannot see would be rewritten here and end up in a condition the outer
plan cannot evaluate.
+ // A positive test is not available without also refusing the sub-queries
whose retained outer
+ // attributes no longer correspond to a condition, which must keep being
rewritten here.
+ val (newCond, newOuterPlan, _) = rewriteExistentialExprWithAttrs(
+ subCond.toSeq, outerPlan, e => !effectivelyReferencesPlan(e, subPlan))
+ (newCond, newOuterPlan, newSubPlan)
+ }
+
+ /**
+ * Rewrites the existential sub-queries in `conditions` that can only be
evaluated by the
+ * sub-query plan, that is those referencing the sub-query plan but not the
outer plan, into
+ * existence joins on top of the sub-query plan. See
+ * [[rewriteExistentialExprInJoinCondition]] for details.
+ *
+ * Returns the rewritten condition along with the updated sub-query plan.
+ */
+ private def rewriteExistentialExprInSubqueryPlan(
+ conditions: Seq[Expression],
+ outerPlan: LogicalPlan,
+ subPlan: LogicalPlan): (Option[Expression], LogicalPlan) = {
+ // Both collectors below match only Exists and InSubquery, and neither
prunes on tree
+ // patterns, so skip them when the hoisted conditions hold no sub-query at
all, which is the
+ // common case for a correlated EXISTS or IN.
+ if (!conditions.exists(_.containsAnyPattern(EXISTS_SUBQUERY,
IN_SUBQUERY))) {
+ return (conditions.reduceOption(And), subPlan)
+ }
+ // A sub-query left in the join condition loses its own join condition
when it is planned
+ // there, so a correlated one would silently return a wrong result: reject
it instead. Note
+ // that this walks the whole expression, including the join condition of a
sub-query that the
+ // rewrite below declines to descend into. That is deliberate: a
correlated sub-query hidden
+ // under a declined one would equally be planned without its join
condition, or reach
+ // execution unevaluable, so it must be rejected even though nothing would
have rewritten it.
+ val referencingBothPlans = conditions.flatMap(_.collect {
+ case sq @ (_: Exists | _: InSubquery)
+ if hasCorrelatedCondition(sq) && effectivelyReferencesPlan(sq,
subPlan) &&
+ effectivelyReferencesPlanOnly(sq, outerPlan, subPlan) => sq
+ })
+ if (referencingBothPlans.nonEmpty) {
+ throw
QueryCompilationErrors.nestedSubqueryReferencingOuterAndInnerQueryError(
+ referencingBothPlans)
+ }
+ // An IN sub-query whose result can be unknown cannot be represented by
the `exists` attribute
+ // of an existence join once that result is observable, see above.
+ val unknownResult = conditions
+ .flatMap(unknownSensitiveInSubqueries(_, truthOnly = true))
+ .filter(sq => effectivelyReferencesPlan(sq, subPlan) &&
+ !effectivelyReferencesPlanOnly(sq, outerPlan, subPlan))
+ if (unknownResult.nonEmpty) {
+ throw
QueryCompilationErrors.nestedInSubqueryWithUnknownResultError(unknownResult)
+ }
+ val (newCond, newSubPlan, _) = rewriteExistentialExprWithAttrs(conditions,
subPlan,
+ e => effectivelyReferencesPlan(e, subPlan) &&
+ !effectivelyReferencesPlanOnly(e, outerPlan, subPlan))
+ (newCond, newSubPlan)
+ }
+
+ /**
+ * Collects the IN sub-queries in `expr` whose result can be unknown and
whose value is observed
+ * beyond being TRUE, so that rewriting them into an existence join, whose
`exists` attribute is
+ * FALSE where IN is unknown, would be observable. See
[[rewriteExistentialExprInJoinCondition]].
+ *
+ * `truthOnly` states whether the value of `expr` is only ever tested for
being TRUE, which is
+ * where unknown and FALSE cannot be told apart. That holds for the operands
of AND and OR within
+ * a condition that ends up in a Filter or a join condition, and for the
positions
+ * [[ReplaceNullWithFalseInPredicate]] rewrites for the same reason: the
operand of an
+ * `EqualNullSafe` against TRUE, and the predicate of an `If` or of a
`CaseWhen` branch. The
+ * result branches of a conditional are consumed wherever the conditional
itself is, so they
+ * inherit its context rather than being value positions of their own.
+ *
+ * It does not hold under NOT, where `NOT FALSE` is TRUE while `NOT unknown`
is unknown. A NOT
+ * directly over an IN sub-query is still safe, but for another reason: it
is rewritten with a
+ * null-aware join condition of its own, which is TRUE where the comparison
is unknown, so the
+ * negation of its `exists` attribute is FALSE there, as SQL requires.
+ */
+ private def unknownSensitiveInSubqueries(
+ expr: Expression,
+ truthOnly: Boolean): Seq[Expression] = {
+ val reported = ArrayBuffer.empty[Expression]
+ collectUnknownSensitiveInSubqueries(expr, truthOnly, reported)
+ reported.toSeq
+ }
+
+ /**
+ * Appends what [[unknownSensitiveInSubqueries]] reports to `reported`, in
the order the
+ * expression is walked. The results are accumulated rather than
concatenated on the way back up,
+ * so a condition with many reportable sub-queries does not copy the prefix
at every node.
+ */
+ private def collectUnknownSensitiveInSubqueries(
+ expr: Expression,
+ truthOnly: Boolean,
+ reported: ArrayBuffer[Expression]): Unit = expr match {
+ case _ if !expr.containsAnyPattern(EXISTS_SUBQUERY, IN_SUBQUERY) =>
+ case And(left, right) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(right, truthOnly, reported)
+ case Or(left, right) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(right, truthOnly, reported)
+ // `null <=> true` and `false <=> true` are both FALSE, so only truth is
observed here whatever
+ // consumes the comparison.
+ case EqualNullSafe(left, Literal.TrueLiteral) =>
+ collectUnknownSensitiveInSubqueries(left, truthOnly = true, reported)
+ case EqualNullSafe(Literal.TrueLiteral, right) =>
+ collectUnknownSensitiveInSubqueries(right, truthOnly = true, reported)
+ case If(predicate, trueValue, falseValue) =>
+ collectUnknownSensitiveInSubqueries(predicate, truthOnly = true,
reported)
+ collectUnknownSensitiveInSubqueries(trueValue, truthOnly, reported)
+ collectUnknownSensitiveInSubqueries(falseValue, truthOnly, reported)
+ case CaseWhen(branches, elseValue) =>
+ branches.foreach { case (condition, value) =>
+ collectUnknownSensitiveInSubqueries(condition, truthOnly = true,
reported)
+ collectUnknownSensitiveInSubqueries(value, truthOnly, reported)
+ }
+ elseValue.foreach(collectUnknownSensitiveInSubqueries(_, truthOnly,
reported))
+ // A NOT directly over an IN sub-query keeps its own null-aware rewrite,
so only its operands
+ // are examined. Under any other NOT, unknown is observable and
`truthOnly` does not carry.
+ case not @ Not(in: InSubquery) => collectOrDescend(not, in, truthOnly,
reported)
+ case Not(child) =>
+ collectUnknownSensitiveInSubqueries(child, truthOnly = false, reported)
+ case in: InSubquery => collectOrDescend(in, in, truthOnly, reported)
+ case sq: SubqueryExpression =>
+ // Only the hoisted join condition of a sub-query expression is a
predicate, evaluated by
+ // the join it is rewritten into. Its outer attributes are value
expressions.
+ sq.getJoinCond.foreach(
+ collectUnknownSensitiveInSubqueries(_, truthOnly = true, reported))
+ sq.getOuterAttrs.foreach(
+ collectUnknownSensitiveInSubqueries(_, truthOnly = false, reported))
+ case other =>
+ other.children.foreach(
+ collectUnknownSensitiveInSubqueries(_, truthOnly = false, reported))
+ }
+
+ /**
+ * Appends `report` to `reported` if the IN sub-query `in` would lose an
observable unknown, and
+ * otherwise descends into the values it compares and into its list query.
The descent matters
+ * because [[InSubquery]] is a [[Predicate]] rather than a
[[SubqueryExpression]], so an IN
+ * sub-query nested in the values or in the hoisted join condition of
another one is only reached
+ * from here.
+ */
+ private def collectOrDescend(
+ report: Expression,
+ in: InSubquery,
+ truthOnly: Boolean,
+ reported: ArrayBuffer[Expression]): Unit = {
+ if (!truthOnly && inSubqueryMayBeUnknown(in)) {
+ reported += report
+ } else {
+ in.values.foreach(collectUnknownSensitiveInSubqueries(_, truthOnly =
false, reported))
+ collectUnknownSensitiveInSubqueries(in.query, truthOnly, reported)
+ }
+ }
+
+ /**
+ * Returns true if the row comparison of the IN sub-query `in` can evaluate
to unknown, that is
+ * if it can return NULL rather than only TRUE or FALSE. An existence join
cannot represent that
+ * third value, see [[rewriteExistentialExprInJoinCondition]].
+ *
+ * This deliberately does not use `InSubquery.nullable`, which under
+ * `spark.sql.legacy.inSubqueryNullability` (SPARK-43413) reports only the
nullability of the
+ * compared values and ignores that of the list query's columns. What is
protected here is the
+ * three-valued result the rewrite would drop, which does not depend on that
configuration, so
+ * the nullability is re-derived from both sides.
+ */
+ private def inSubqueryMayBeUnknown(in: InSubquery): Boolean = {
+ in.values.zip(in.query.childOutputs).exists { case (v, o) => v.nullable ||
o.nullable }
+ }
+
+ /**
+ * Returns true if `e` is an existential sub-query expression that still
carries a correlated
+ * condition, that is one that [[PullupCorrelatedPredicates]] hoisted into
it and that would be
+ * lost were the sub-query left in a join condition.
+ *
+ * This is decided from that condition rather than from `isCorrelated`,
which reports the outer
Review Comment:
Confirmed: the scaladoc now describes isCorrelated as `outerAttrs.nonEmpty`,
which makes it clear why the helper reads the surviving join condition instead.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4139416480","thread_id":"inline:4139416480","verdict_sha256":"666f73c8705c7fc517a3755f43545348abf6bf7b1b48ab8a7138d74dc04fbaa3"}
-->
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/subquery.scala:
##########
@@ -398,62 +406,393 @@ object RewritePredicateSubquery extends
Rule[LogicalPlan] with PredicateHelper {
(newExpr, newPlan)
}
+ /**
+ * 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 =
+ 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 = 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 = 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, which allocates
nothing.
+ // AttributeSet.intersect materialises a set from its argument, so the
operand order there
+ // would decide whether this walks the references or the whole output of
`plan`.
+ 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)
+ }
+
+ /**
+ * Returns true if `e` effectively references an attribute that `plan`
produces and `sharedWith`
+ * does not, see [[effectiveReferences]].
+ *
+ * An attribute that both plans produce is attributed to `sharedWith` rather
than to `plan`.
+ * This matters when the outer and the sub-query plan share ExprIds, which a
self-join can leave
+ * for the optimizer to deduplicate (SPARK-21835): the EXISTS arms classify
against the raw
+ * sub-query plan, while the IN arms classify against the plan that
+ * `dedupSubqueryOnSelfJoin` has already separated from the outer plan.
Without this a single
+ * shared attribute would satisfy both sides of the classification, so a
nested sub-query that
+ * references only the sub-query it is nested in would be taken for one
referencing both plans
+ * and rejected. A nested sub-query resolves in the scope of that sub-query,
so a shared
+ * attribute is one of its own.
+ */
+ private def effectivelyReferencesPlanOnly(
+ e: Expression,
+ plan: LogicalPlan,
+ sharedWith: LogicalPlan): Boolean = {
+ effectiveReferences(e).exists { attr =>
+ plan.outputSet.contains(attr) && !sharedWith.outputSet.contains(attr)
+ }
+ }
+
+ /**
+ * 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.
+ */
+ private def effectiveReferences(e: Expression): AttributeSet = e match {
+ case Exists(_, _, _, joinCond, _) =>
AttributeSet(joinCond.flatMap(_.references))
+ case Not(in: InSubquery) => effectiveReferences(in)
+ case InSubquery(values, ListQuery(_, _, _, _, joinCond, _)) =>
+ AttributeSet(values.flatMap(_.references) ++
joinCond.flatMap(_.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 can be rewritten into an
existence join on
+ * neither side, so it is left 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
Review Comment:
Confirmed: the scaladoc now names both paths, decorrelation disabled and an
uncorrelated IN with optimizeUncorrelatedInSubqueriesInJoinCondition.enabled
disabled.
<!-- SPARK_DEV_REVIEW_REPLY
{"feedback_id":"inline:4139416485","thread_id":"inline:4139416485","verdict_sha256":"666f73c8705c7fc517a3755f43545348abf6bf7b1b48ab8a7138d74dc04fbaa3"}
-->
--
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]
