peter-toth commented on a change in pull request #23531: [SPARK-24497][SQL]
Support recursive SQL query
URL: https://github.com/apache/spark/pull/23531#discussion_r252004832
##########
File path:
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/analysis/Analyzer.scala
##########
@@ -205,33 +206,170 @@ class Analyzer(
CleanupAliases)
)
+ object ResolveRecursiveReferneces extends Rule[LogicalPlan] {
+ def apply(plan: LogicalPlan): LogicalPlan = {
+ val recursiveTables = plan.collect {
+ case rt @ RecursiveTable(name, _, _, _) if rt.anchorResolved => name
-> rt
+ }.toMap
+
+ plan.resolveOperatorsUp {
+ case UnresolvedRecursiveReference(name) if
recursiveTables.contains(name) =>
+ // creating new instance of attributes here makes possible to avoid
complex attribute
+ // handling in FoldablePropagation
+ RecursiveReference(name,
recursiveTables(name).output.map(_.newInstance()))
+ case other => other
+ }
+ }
+ }
+
/**
* Analyze cte definitions and substitute child plan with analyzed cte
definitions.
*/
object CTESubstitution extends Rule[LogicalPlan] {
def apply(plan: LogicalPlan): LogicalPlan = plan.resolveOperatorsUp {
- case With(child, relations) =>
+ case With(child, relations, allowRecursion) =>
substituteCTE(child, relations.foldLeft(Seq.empty[(String,
LogicalPlan)]) {
case (resolved, (name, relation)) =>
- resolved :+ name -> executeSameContext(substituteCTE(relation,
resolved))
- })
+ val recursiveTableName = if (allowRecursion) Some(name) else None
+ val (substitutedPlan, recursiveReferenceFound) =
+ substituteCTE(relation, resolved, recursiveTableName)
+ val analyzedPlan = executeSameContext(substitutedPlan)
+ resolved :+ name -> (
+ if (recursiveReferenceFound) {
+ insertRecursiveTable(analyzedPlan, recursiveTableName.get)
+ } else {
+ analyzedPlan
+ })
+ }, None)._1
case other => other
}
- def substituteCTE(plan: LogicalPlan, cteRelations: Seq[(String,
LogicalPlan)]): LogicalPlan = {
- plan resolveOperatorsDown {
+ def substituteCTE(
+ plan: LogicalPlan,
+ cteRelations: Seq[(String, LogicalPlan)],
+ recursiveTableName: Option[String]): (LogicalPlan, Boolean) = {
+ var recursiveReferenceFound = false
+
+ val newPlan = plan resolveOperatorsDown {
case u: UnresolvedRelation =>
- cteRelations.find(x => resolver(x._1, u.tableIdentifier.table))
- .map(_._2).getOrElse(u)
+ val table = u.tableIdentifier.table
+
+ val recursiveReference = recursiveTableName.find(resolver(_,
table)).map { name =>
+ recursiveReferenceFound = true
+
+ UnresolvedRecursiveReference(name)
+ }
+
+ recursiveReference
+ .orElse(cteRelations.find(x => resolver(x._1, table)).map(_._2))
+ .getOrElse(u)
+ case w @ With(_, cteRelations, _) =>
+ w.copy(cteRelations = cteRelations.map {
+ case (name, sa @ SubqueryAlias(_, plan)) =>
+ val (substitutedPlan, recursiveReferenceFoundInCTE) =
+ substituteCTE(plan, Seq.empty, recursiveTableName)
+ recursiveReferenceFound |= recursiveReferenceFoundInCTE
+
+ (name, sa.copy(child = substitutedPlan))
+ })
case other =>
// This cannot be done in ResolveSubquery because ResolveSubquery
does not know the CTE.
other transformExpressions {
case e: SubqueryExpression =>
- e.withNewPlan(substituteCTE(e.plan, cteRelations))
+ val (substitutedPlan, recursiveReferenceFoundInSubQuery) =
+ substituteCTE(e.plan, cteRelations, recursiveTableName)
+ recursiveReferenceFound |= recursiveReferenceFoundInSubQuery
+
+ e.withNewPlan(substitutedPlan)
}
}
+
+ (newPlan, recursiveReferenceFound)
+ }
+
+ def insertRecursiveTable(plan: LogicalPlan, recursiveTableName: String):
LogicalPlan =
+ plan match {
+ case sa @ SubqueryAlias(name, u: Union) if name.identifier ==
recursiveTableName =>
+ def combineUnions(union: Union): Seq[LogicalPlan] =
union.children.flatMap {
+ case u: Union => combineUnions(u)
+ case o => Seq(o)
+ }
+
+ val (anchorTerms, recursiveTerms) =
combineUnions(u).partition(!_.collectFirst {
+ case UnresolvedRecursiveReference(name) if name ==
recursiveTableName => true
+ }.isDefined)
+
+ if (!recursiveTerms.isEmpty) {
+ if (anchorTerms.isEmpty) {
+ throw new AnalysisException("There should be at least 1 anchor
term defined in the " +
+ s"recursive query ${recursiveTableName}")
+ }
+
+ // Recursion according to SQL standard comes with several
limitations due to the fact
+ // that only those operations are allowed where the new set of
rows should be computed
+ // from the result of the previous iteration only (the so far
cumulated results is not
+ // required).
+ // This implies that a recursive reference can't be used in some
kinds of joins,
+ // aggregation, distinct and subqueries.
+ def traversePlanAndCheck(
Review comment:
moved it to a dedicated rule
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
