TreeNode — Node in Catalyst Tree-spark技术分享

TreeNode — Node in Catalyst Tree

TreeNode is the contract of nodes in Catalyst tree with name and zero or more children.



package org.apache.spark.sql.catalyst.trees

abstract class TreeNode[BaseType <: TreeNode[BaseType]] extends Product {
  self: BaseType =>

  // only required properties (vals and methods) that have no implementation
  // the others follow
  def children: Seq[BaseType]
  def verboseString: String
}

package org.apache.spark.sql.catalyst.trees

abstract class TreeNode[BaseType <: TreeNode[BaseType]] extends Product {

self: BaseType =>

// only required properties (vals and methods) that have no implementation

// the others follow

def children: Seq[BaseType]

def verboseString: String

}

TreeNode is a recursive data structure that can have one or many children that are again TreeNodes.

Tip	Read up on `<:` type operator in Scala in Upper Type Bounds.

Scala-specific, TreeNode is an abstract class that is the base class of Catalyst Expression and QueryPlan abstract classes.

TreeNode therefore allows for building entire trees of TreeNodes, e.g. generic query plans with concrete logical and physical operators that both use Catalyst expressions (which are TreeNodes again).

Note	Spark SQL uses `TreeNode` for query plans and Catalyst expressions that can further be used together to build more advanced trees, e.g. Catalyst expressions can have query plans as subquery expressions.

TreeNode can itself be a node in a tree or a collection of nodes, i.e. itself and the children nodes. Not only does TreeNode come with the methods that you may have used in Scala Collection API (e.g. map, flatMap, collect, collectFirst, foreach), but also specialized ones for more advanced tree manipulation, e.g. mapChildren, transform, transformDown, transformUp, foreachUp, numberedTreeString, p, asCode, prettyJson.

Table 1. TreeNode API (Public Methods)

Method

Description

apply



apply(number: Int): TreeNode[_]

apply(number: Int): TreeNode[_]

argString



argString: String

argString: String

asCode



asCode: String

asCode: String

collect



collect[B](pf: PartialFunction[BaseType, B]): Seq[B]

collect[B](pf: PartialFunction[BaseType, B]): Seq[B]

collectFirst



collectFirst[B](pf: PartialFunction[BaseType, B]): Option[B]

collectFirst[B](pf: PartialFunction[BaseType, B]): Option[B]

collectLeaves



collectLeaves(): Seq[BaseType]

collectLeaves(): Seq[BaseType]

fastEquals



fastEquals(other: TreeNode[_]): Boolean

fastEquals(other: TreeNode[_]): Boolean

find



find(f: BaseType => Boolean): Option[BaseType]

find(f: BaseType => Boolean): Option[BaseType]

flatMap



flatMap[A](f: BaseType => TraversableOnce[A]): Seq[A]

flatMap[A](f: BaseType => TraversableOnce[A]): Seq[A]

foreach



foreach(f: BaseType => Unit): Unit

foreach(f: BaseType => Unit): Unit

foreachUp



foreachUp(f: BaseType => Unit): Unit

foreachUp(f: BaseType => Unit): Unit

generateTreeString



generateTreeString(
  depth: Int,
  lastChildren: Seq[Boolean],
  builder: StringBuilder,
  verbose: Boolean,
  prefix: String = "",
  addSuffix: Boolean = false): StringBuilder

generateTreeString(

depth: Int,

lastChildren: Seq[Boolean],

builder: StringBuilder,

verbose: Boolean,

prefix: String = "",

addSuffix: Boolean = false): StringBuilder

map



map[A](f: BaseType => A): Seq[A]

map[A](f: BaseType => A): Seq[A]

mapChildren



mapChildren(f: BaseType => BaseType): BaseType

mapChildren(f: BaseType => BaseType): BaseType

nodeName



nodeName: String

nodeName: String

numberedTreeString



numberedTreeString: String

numberedTreeString: String



p(number: Int): BaseType

p(number: Int): BaseType

prettyJson



prettyJson: String

prettyJson: String

simpleString



simpleString: String

simpleString: String

toJSON



toJSON: String

toJSON: String

transform



transform(rule: PartialFunction[BaseType, BaseType]): BaseType

transform(rule: PartialFunction[BaseType, BaseType]): BaseType

transformDown



transformDown(rule: PartialFunction[BaseType, BaseType]): BaseType

transformDown(rule: PartialFunction[BaseType, BaseType]): BaseType

transformUp



transformUp(rule: PartialFunction[BaseType, BaseType]): BaseType

transformUp(rule: PartialFunction[BaseType, BaseType]): BaseType

treeString



treeString: String
treeString(verbose: Boolean, addSuffix: Boolean = false): String

treeString: String

treeString(verbose: Boolean, addSuffix: Boolean = false): String

verboseString



verboseString: String

verboseString: String

verboseStringWithSuffix



verboseStringWithSuffix: String

verboseStringWithSuffix: String

withNewChildren



withNewChildren(newChildren: Seq[BaseType]): BaseType

withNewChildren(newChildren: Seq[BaseType]): BaseType

Table 2. (Subset of) TreeNode Contract
Method	Description
`children`	Child nodes
`verboseString`	One-line verbose description Used when `TreeNode` is requested for generateTreeString (with `verbose` flag enabled) and verboseStringWithSuffix

Table 3. TreeNodes
TreeNode	Description
Expression
QueryPlan

Tip

TreeNode abstract type is a fairly advanced Scala type definition (at least comparing to the other Scala types in Spark) so understanding its behaviour even outside Spark might be worthwhile by itself.



abstract class TreeNode[BaseType <: TreeNode[BaseType]] extends Product {
  self: BaseType =>

  // ...
}

abstract class TreeNode[BaseType <: TreeNode[BaseType]] extends Product {

self: BaseType =>

// ...

}

`withNewChildren` Method



withNewChildren(newChildren: Seq[BaseType]): BaseType

withNewChildren(newChildren: Seq[BaseType]): BaseType

withNewChildren…FIXME

Note	`withNewChildren` is used when…FIXME

Simple Node Description — `simpleString` Method



simpleString: String

simpleString: String

simpleString gives a simple one-line description of a TreeNode.

Internally, simpleString is the nodeName followed by argString separated by a single white space.

Note	`simpleString` is used when `TreeNode` is requested for argString (of child nodes) and tree text representation (with `verbose` flag off).

Numbered Text Representation — `numberedTreeString` Method



numberedTreeString: String

numberedTreeString: String

numberedTreeString adds numbers to the text representation of all the nodes.

Note	`numberedTreeString` is used primarily for interactive debugging using apply and p methods.

Getting n-th TreeNode in Tree (for Interactive Debugging) — `apply` Method



apply(number: Int): TreeNode[_]

apply(number: Int): TreeNode[_]

apply gives number-th tree node in a tree.

Note	`apply` can be used for interactive debugging.

Internally, apply gets the node at number position or null.

Getting n-th BaseType in Tree (for Interactive Debugging) — `p` Method



p(number: Int): BaseType

p(number: Int): BaseType

p gives number-th tree node in a tree as BaseType for interactive debugging.

Note	`p` can be used for interactive debugging.

Note	`BaseType` is the base type of a tree and in Spark SQL can be: LogicalPlan for logical plan trees SparkPlan for physical plan trees Expression for expression trees

Text Representation — `toString` Method



toString: String

toString: String

Note	`toString` is part of Java’s Object Contract for the string representation of an object, e.g. `TreeNode`.

toString simply returns the text representation of all nodes in the tree.

Text Representation of All Nodes in Tree — `treeString` Method



treeString: String  (1)
treeString(verbose: Boolean, addSuffix: Boolean = false): String

treeString: String (1)

treeString(verbose: Boolean, addSuffix: Boolean = false): String

Turns verbose flag on

treeString gives the string representation of all the nodes in the TreeNode.



import org.apache.spark.sql.{functions => f}
val q = spark.range(10).withColumn("rand", f.rand())
val executedPlan = q.queryExecution.executedPlan

val output = executedPlan.treeString(verbose = true)

scala> println(output)
*(1) Project [id#0L, rand(6790207094253656854) AS rand#2]
+- *(1) Range (0, 10, step=1, splits=8)

import org.apache.spark.sql.{functions => f}

val q = spark.range(10).withColumn("rand", f.rand())

val executedPlan = q.queryExecution.executedPlan

val output = executedPlan.treeString(verbose = true)

scala> println(output)

*(1) Project [id#0L, rand(6790207094253656854) AS rand#2]

+- *(1) Range (0, 10, step=1, splits=8)

Note	`treeString` is used when: `TreeNode` is requested for the numbered text representation and the text representation `QueryExecution` is requested for simple, extended and with statistics text representations

Verbose Description with Suffix — `verboseStringWithSuffix` Method



verboseStringWithSuffix: String

verboseStringWithSuffix: String

verboseStringWithSuffix simply returns verbose description.

Note	`verboseStringWithSuffix` is used exclusively when `TreeNode` is requested to generateTreeString (with `verbose` and `addSuffix` flags enabled).

Generating Text Representation of Inner and Regular Child Nodes — `generateTreeString` Method



generateTreeString(
  depth: Int,
  lastChildren: Seq[Boolean],
  builder: StringBuilder,
  verbose: Boolean,
  prefix: String = "",
  addSuffix: Boolean = false): StringBuilder

generateTreeString(

depth: Int,

lastChildren: Seq[Boolean],

builder: StringBuilder,

verbose: Boolean,

prefix: String = "",

addSuffix: Boolean = false): StringBuilder

Internally, generateTreeString appends the following node descriptions per the verbose and addSuffix flags:

verbose description with suffix when both are enabled (i.e. verbose and addSuffix flags are all true)
verbose description when verbose is enabled (i.e. verbose is true and addSuffix is false)
simple description when verbose is disabled (i.e. verbose is false)

In the end, generateTreeString calls itself recursively for the innerChildren and the child nodes.

Note	`generateTreeString` is used exclusively when `TreeNode` is requested for text representation of all nodes in the tree.

Inner Child Nodes — `innerChildren` Method



innerChildren: Seq[TreeNode[_]]

innerChildren: Seq[TreeNode[_]]

innerChildren returns the inner nodes that should be shown as an inner nested tree of this node.

innerChildren simply returns an empty collection of TreeNodes.

Note	`innerChildren` is used when `TreeNode` is requested to generate the text representation of inner and regular child nodes, allChildren and getNodeNumbered.

`allChildren` Property



allChildren: Set[TreeNode[_]]

allChildren: Set[TreeNode[_]]

Note	`allChildren` is a Scala lazy value which is computed once when accessed and cached afterwards.

allChildren…FIXME

Note	`allChildren` is used when…FIXME

`getNodeNumbered` Internal Method



getNodeNumbered(number: MutableInt): Option[TreeNode[_]]

getNodeNumbered(number: MutableInt): Option[TreeNode[_]]

getNodeNumbered…FIXME

Note	`getNodeNumbered` is used when…FIXME

`foreach` Method



foreach(f: BaseType => Unit): Unit

foreach(f: BaseType => Unit): Unit

foreach applies the input function f to itself (this) first and then (recursively) to the children.

`collect` Method



collect[B](pf: PartialFunction[BaseType, B]): Seq[B]

collect[B](pf: PartialFunction[BaseType, B]): Seq[B]

collect…FIXME

`collectFirst` Method



collectFirst[B](pf: PartialFunction[BaseType, B]): Option[B]

collectFirst[B](pf: PartialFunction[BaseType, B]): Option[B]

collectFirst…FIXME

`collectLeaves` Method



collectLeaves(): Seq[BaseType]

collectLeaves(): Seq[BaseType]

collectLeaves…FIXME

`find` Method



find(f: BaseType => Boolean): Option[BaseType]

find(f: BaseType => Boolean): Option[BaseType]

find…FIXME

`flatMap` Method



flatMap[A](f: BaseType => TraversableOnce[A]): Seq[A]

flatMap[A](f: BaseType => TraversableOnce[A]): Seq[A]

flatMap…FIXME

`foreachUp` Method



foreachUp(f: BaseType => Unit): Unit

foreachUp(f: BaseType => Unit): Unit

foreachUp…FIXME

`map` Method



map[A](f: BaseType => A): Seq[A]

map[A](f: BaseType => A): Seq[A]

map…FIXME

`mapChildren` Method



mapChildren(f: BaseType => BaseType): BaseType

mapChildren(f: BaseType => BaseType): BaseType

mapChildren…FIXME

`transform` Method



transform(rule: PartialFunction[BaseType, BaseType]): BaseType

transform(rule: PartialFunction[BaseType, BaseType]): BaseType

transform…FIXME

Transforming Nodes Downwards — `transformDown` Method



transformDown(rule: PartialFunction[BaseType, BaseType]): BaseType

transformDown(rule: PartialFunction[BaseType, BaseType]): BaseType

transformDown…FIXME

`transformUp` Method



transformUp(rule: PartialFunction[BaseType, BaseType]): BaseType

transformUp(rule: PartialFunction[BaseType, BaseType]): BaseType

transformUp…FIXME

`asCode` Method



asCode: String

asCode: String

asCode…FIXME

`prettyJson` Method



prettyJson: String

prettyJson: String

prettyJson…FIXME

Note	`prettyJson` is used when…FIXME

`toJSON` Method



toJSON: String

toJSON: String

toJSON…FIXME

Note	`toJSON` is used when…FIXME

`argString` Method



argString: String

argString: String

argString…FIXME

Note	`argString` is used when…FIXME

`nodeName` Method



nodeName: String

nodeName: String

nodeName returns the name of the class with Exec suffix removed (that is used as a naming convention for the class name of physical operators).

Note	`nodeName` is used when `TreeNode` is requested for simpleString and asCode.

`fastEquals` Method



fastEquals(other: TreeNode[_]): Boolean

fastEquals(other: TreeNode[_]): Boolean

fastEquals…FIXME

Note	`fastEquals` is used when…FIXME