-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
LogicalPlan.scala
178 lines (149 loc) · 7.33 KB
/
LogicalPlan.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
/*
* Copyright (c) 2002-2017 "Neo Technology,"
* Network Engine for Objects in Lund AB [http://neotechnology.com]
*
* This file is part of Neo4j.
*
* Neo4j is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package org.neo4j.cypher.internal.compiler.v3_3.planner.logical.plans
import java.lang.reflect.Method
import org.neo4j.cypher.internal.frontend.v3_3.Foldable._
import org.neo4j.cypher.internal.frontend.v3_3.Rewritable._
import org.neo4j.cypher.internal.frontend.v3_3.ast._
import org.neo4j.cypher.internal.frontend.v3_3.{InternalException, Rewritable}
import org.neo4j.cypher.internal.ir.v3_3.{CardinalityEstimation, IdName, PlannerQuery, Strictness}
/*
A LogicalPlan is an algebraic query, which is represented by a query tree whose leaves are database relations and
non-leaf nodes are algebraic operators like selections, projections, and joins. An intermediate node indicates the
application of the corresponding operator on the relations generated by its children, the result of which is then sent
further up. Thus, the edges of a tree represent data flow from bottom to top, i.e., from the leaves, which correspond
to data in the database, to the root, which is the final operator producing the query answer. */
abstract class LogicalPlan
extends Product
with Strictness
with Rewritable {
self =>
def lhs: Option[LogicalPlan]
def rhs: Option[LogicalPlan]
def solved: PlannerQuery with CardinalityEstimation
def availableSymbols: Set[IdName]
def leaves: Seq[LogicalPlan] = this.treeFold(Seq.empty[LogicalPlan]) {
case plan: LogicalPlan
if plan.lhs.isEmpty && plan.rhs.isEmpty => acc => (acc :+ plan, Some(identity))
}
def updateSolved(newSolved: PlannerQuery with CardinalityEstimation): LogicalPlan = {
val arguments = this.children.toList :+ newSolved
try {
copyConstructor.invoke(this, arguments: _*).asInstanceOf[this.type]
} catch {
case e: IllegalArgumentException if e.getMessage.startsWith("wrong number of arguments") =>
throw new InternalException("Logical plans need to be case classes, and have the PlannerQuery in a separate constructor")
}
}
def copyPlan(): LogicalPlan = {
try {
val arguments = this.children.toList :+ solved
copyConstructor.invoke(this, arguments: _*).asInstanceOf[this.type]
} catch {
case e: IllegalArgumentException if e.getMessage.startsWith("wrong number of arguments") =>
throw new InternalException("Logical plans need to be case classes, and have the PlannerQuery in a separate constructor", e)
}
}
lazy val copyConstructor: Method = this.getClass.getMethods.find(_.getName == "copy").get
def updateSolved(f: PlannerQuery with CardinalityEstimation => PlannerQuery with CardinalityEstimation): LogicalPlan =
updateSolved(f(solved))
def dup(children: Seq[AnyRef]): this.type =
if (children.iterator eqElements this.children)
this
else {
val constructor = this.copyConstructor
val params = constructor.getParameterTypes
val args = children.toIndexedSeq
if ((params.length == args.length + 1) && params.last.isAssignableFrom(classOf[PlannerQuery]))
constructor.invoke(this, args :+ this.solved: _*).asInstanceOf[this.type]
else
constructor.invoke(this, args: _*).asInstanceOf[this.type]
}
def isLeaf: Boolean = lhs.isEmpty && rhs.isEmpty
override def toString = {
def indent(level: Int, in: String): String = level match {
case 0 => in
case _ => "\n" + " " * level + in
}
val childrenHeap = new scala.collection.mutable.Stack[(String, Int, Option[LogicalPlan])]
childrenHeap.push(("", 0, Some(this)))
val sb = new StringBuilder()
while (childrenHeap.nonEmpty) {
childrenHeap.pop() match {
case (prefix, level, Some(plan)) =>
val children = plan.lhs.toIndexedSeq ++ plan.rhs.toIndexedSeq
val nonChildFields = plan.productIterator.filterNot(children.contains).mkString(", ")
val prodPrefix = plan.productPrefix
sb.append(indent(level, s"""$prefix$prodPrefix($nonChildFields) {""".stripMargin))
(plan.lhs, plan.rhs) match {
case (None, None) =>
sb.append("}")
case (Some(l), None) =>
childrenHeap.push(("\n" + " " * level + "}", level + 1, None))
childrenHeap.push(("LHS -> ", level + 1, plan.lhs))
case _ =>
childrenHeap.push(("\n" + " " * level + "}", level + 1, None))
childrenHeap.push(("RHS -> ", level + 1, plan.rhs))
childrenHeap.push(("LHS -> ", level + 1, plan.lhs))
}
case (prefix, _, _) =>
sb.append(prefix)
}
}
sb.toString()
}
def satisfiesExpressionDependencies(e: Expression) = e.dependencies.map(IdName.fromVariable).forall(availableSymbols.contains)
def debugId: String = f"0x${hashCode()}%08x"
def flatten: Seq[LogicalPlan] = Flattener.create(this)
def indexUsage: Seq[IndexUsage] = {
import org.neo4j.cypher.internal.frontend.v3_3.Foldable._
this.fold(Seq.empty[IndexUsage]) {
case NodeIndexSeek(idName, label, propertyKeys, _, _) =>
(acc) => acc :+ SchemaIndexSeekUsage(idName.name, label.nameId.id, label.name, propertyKeys.map(_.name))
case NodeUniqueIndexSeek(idName, label, propertyKeys, _, _) =>
(acc) => acc :+ SchemaIndexSeekUsage(idName.name, label.nameId.id, label.name, propertyKeys.map(_.name))
case NodeIndexScan(idName, label, propertyKey, _) =>
(acc) => acc :+ SchemaIndexScanUsage(idName.name, label.nameId.id, label.name, propertyKey.name)
}
}
}
abstract class LogicalLeafPlan extends LogicalPlan with LazyLogicalPlan {
final val lhs = None
final val rhs = None
def argumentIds: Set[IdName]
}
abstract class NodeLogicalLeafPlan extends LogicalLeafPlan {
def idName: IdName
}
abstract class IndexLeafPlan extends NodeLogicalLeafPlan {
def valueExpr: QueryExpression[Expression]
}
case object Flattener extends TreeBuilder[Seq[LogicalPlan]] {
override protected def build(plan: LogicalPlan): Seq[LogicalPlan] = Seq(plan)
override protected def build(plan: LogicalPlan, source: Seq[LogicalPlan]): Seq[LogicalPlan] = plan +: source
override protected def build(plan: LogicalPlan, lhs: Seq[LogicalPlan], rhs: Seq[LogicalPlan]): Seq[LogicalPlan] = (plan +: lhs) ++ rhs
}
sealed trait IndexUsage {
def identifier:String
}
final case class SchemaIndexSeekUsage(identifier: String, labelId : Int, label: String, propertyKeys: Seq[String]) extends IndexUsage
final case class SchemaIndexScanUsage(identifier: String, labelId : Int, label: String, propertyKey: String) extends IndexUsage
final case class LegacyNodeIndexUsage(identifier: String, index: String) extends IndexUsage
final case class LegacyRelationshipIndexUsage(identifier: String, index: String) extends IndexUsage