Skip to content

Commit 8ed8677

Browse files
fickluddfickludd
committed
Fix infinite planning of many disjunctive index seeks
Before this fix, the planner would consider both an index scan and the particular index seek for each ORed predicate, leading to a combinatorial explosion of 2^n combinations, where n is the number of predicates. This quickly becomes practically infinite for larger n. Here we solve this by dismissing index scans if the variable can be found using a seek, because the seek will always be faster.
1 parent 78fe373 commit 8ed8677

5 files changed

Lines changed: 167 additions & 8 deletions

File tree

‎community/cypher/cypher-planner-3.4/src/main/scala/org/neo4j/cypher/internal/compiler/v3_4/planner/logical/LogicalPlanningFunction.scala‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,6 @@ import org.neo4j.cypher.internal.ir.v3_4.QueryGraph
2424
import org.neo4j.cypher.internal.planner.v3_4.spi.PlanningAttributes.{Cardinalities, Solveds}
2525
import org.neo4j.cypher.internal.v3_4.logical.plans.LogicalPlan
2626

27-
// TODO: Return Iterator
2827
trait CandidateGenerator[T] extends ((T, QueryGraph, LogicalPlanningContext, Solveds, Cardinalities) => Seq[LogicalPlan])
2928

3029
trait PlanTransformer[-T] extends ((LogicalPlan, T, LogicalPlanningContext, Solveds, Cardinalities) => LogicalPlan)

‎community/cypher/cypher-planner-3.4/src/main/scala/org/neo4j/cypher/internal/compiler/v3_4/planner/logical/steps/OrLeafPlanner.scala‎

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@
2020
package org.neo4j.cypher.internal.compiler.v3_4.planner.logical.steps
2121

2222
import org.neo4j.cypher.internal.compiler.v3_4.planner.logical._
23-
import org.neo4j.cypher.internal.v3_4.logical.plans.LogicalPlan
23+
import org.neo4j.cypher.internal.v3_4.logical.plans._
2424
import org.neo4j.cypher.internal.frontend.v3_4.helpers.SeqCombiner.combine
2525
import org.neo4j.cypher.internal.ir.v3_4.{QueryGraph, Selections}
2626
import org.neo4j.cypher.internal.planner.v3_4.spi.PlanningAttributes.{Cardinalities, Solveds}
@@ -38,7 +38,9 @@ case class OrLeafPlanner(inner: Seq[LeafPlanFromExpressions]) extends LeafPlanne
3838
(e: Expression) =>
3939
val plansForVariables: Seq[LeafPlansForVariable] = inner.flatMap(_.producePlanFor(Set(e), qg, context))
4040
val qgForExpression = qg.copy(selections = Selections.from(e))
41-
plansForVariables.map(p =>
41+
val canDoIndexSeek = plansForVariables.exists(leafPlans => leafPlans.plans.exists(nodeIndexSeek))
42+
val withoutIndexScans = if (canDoIndexSeek) plansForVariables.filter(x => !x.plans.exists(nodeIndexScan)) else plansForVariables
43+
withoutIndexScans.map(p =>
4244
p.copy(plans = p.plans.map(context.config.applySelections(_, qgForExpression, context, solveds, cardinalities))))
4345
}
4446

@@ -88,4 +90,16 @@ case class OrLeafPlanner(inner: Seq[LeafPlanFromExpressions]) extends LeafPlanne
8890
case predicate => predicate
8991
}
9092
}
93+
94+
private def nodeIndexSeek(logicalPlan: LogicalPlan): Boolean =
95+
logicalPlan match {
96+
case _: NodeIndexSeek |
97+
_: NodeUniqueIndexSeek |
98+
_: NodeIndexEndsWithScan |
99+
_: NodeIndexContainsScan => true
100+
case _ => false
101+
}
102+
103+
private def nodeIndexScan(logicalPlan: LogicalPlan): Boolean =
104+
logicalPlan.isInstanceOf[NodeIndexScan]
91105
}

‎community/cypher/cypher-planner-3.4/src/test/scala/org/neo4j/cypher/internal/compiler/v3_4/planner/logical/OrLeafPlanningIntegrationTest.scala‎

Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
/*
2+
* Copyright (c) 2002-2018 "Neo4j,"
3+
* Neo4j Sweden AB [http://neo4j.com]
4+
*
5+
* This file is part of Neo4j.
6+
*
7+
* Neo4j is free software: you can redistribute it and/or modify
8+
* it under the terms of the GNU General Public License as published by
9+
* the Free Software Foundation, either version 3 of the License, or
10+
* (at your option) any later version.
11+
*
12+
* This program is distributed in the hope that it will be useful,
13+
* but WITHOUT ANY WARRANTY; without even the implied warranty of
14+
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15+
* GNU General Public License for more details.
16+
*
17+
* You should have received a copy of the GNU General Public License
18+
* along with this program. If not, see <http://www.gnu.org/licenses/>.
19+
*/
20+
package org.neo4j.cypher.internal.compiler.v3_4.planner.logical
21+
22+
import org.neo4j.cypher.internal.compiler.v3_4.planner.LogicalPlanningTestSupport2
23+
import org.neo4j.cypher.internal.util.v3_4.test_helpers.CypherFunSuite
24+
import org.neo4j.cypher.internal.v3_4.logical.plans._
25+
26+
import scala.concurrent.Await
27+
import scala.concurrent.duration.Duration
28+
29+
class OrLeafPlanningIntegrationTest extends CypherFunSuite with LogicalPlanningTestSupport2 {
30+
31+
test("should not explode for many STARTS WITH") {
32+
val query =
33+
"""MATCH (tn:X) USING INDEX tn:X(prop)
34+
|WHERE (tn:Y) AND ((
35+
| tn.prop STARTS WITH {p3} OR
36+
| tn.prop STARTS WITH {p4} OR
37+
| tn.prop STARTS WITH {p5} OR
38+
| tn.prop STARTS WITH {p6} OR
39+
| tn.prop STARTS WITH {p7} OR
40+
| tn.prop STARTS WITH {p8} OR
41+
| tn.prop STARTS WITH {p9} OR
42+
| tn.prop STARTS WITH {p10} OR
43+
| tn.prop STARTS WITH {p11} OR
44+
| tn.prop STARTS WITH {p12} OR
45+
| tn.prop STARTS WITH {p13} OR
46+
| tn.prop STARTS WITH {p14} OR
47+
| tn.prop STARTS WITH {p15} OR
48+
| tn.prop STARTS WITH {p16} OR
49+
| tn.prop STARTS WITH {p17} OR
50+
| tn.prop STARTS WITH {p18} OR
51+
| tn.prop STARTS WITH {p19} OR
52+
| tn.prop STARTS WITH {p20} OR
53+
| tn.prop STARTS WITH {p21} OR
54+
| tn.prop STARTS WITH {p22} OR
55+
| tn.prop STARTS WITH {p23} OR
56+
| tn.prop STARTS WITH {p24} OR
57+
| tn.prop STARTS WITH {p25} OR
58+
| tn.prop STARTS WITH {p26} OR
59+
| tn.prop STARTS WITH {p27} OR
60+
| tn.prop STARTS WITH {p28} OR
61+
| tn.prop STARTS WITH {p29} OR
62+
| tn.prop STARTS WITH {p30} OR
63+
| tn.prop STARTS WITH {p31} OR
64+
| tn.prop STARTS WITH {p32} OR
65+
| tn.prop STARTS WITH {p33} OR
66+
| tn.prop STARTS WITH {p34} OR
67+
| tn.prop STARTS WITH {p35} OR
68+
| tn.prop STARTS WITH {p36} OR
69+
| tn.prop STARTS WITH {p37} OR
70+
| tn.prop STARTS WITH {p38} OR
71+
| tn.prop STARTS WITH {p39} OR
72+
| tn.prop STARTS WITH {p40} OR
73+
| tn.prop STARTS WITH {p41} OR
74+
| tn.prop STARTS WITH {p42} OR
75+
| tn.prop STARTS WITH {p43} OR
76+
| tn.prop STARTS WITH {p44} OR
77+
| tn.prop STARTS WITH {p45} OR
78+
| tn.prop STARTS WITH {p46} OR
79+
| tn.prop STARTS WITH {p47} OR
80+
| tn.prop STARTS WITH {p48} OR
81+
| tn.prop STARTS WITH {p49} OR
82+
| tn.prop STARTS WITH {p50} OR
83+
| tn.prop STARTS WITH {p51} OR
84+
| tn.prop STARTS WITH {p52} OR
85+
| tn.prop STARTS WITH {p53} OR
86+
| tn.prop STARTS WITH {p54} OR
87+
| tn.prop STARTS WITH {p55} OR
88+
| tn.prop STARTS WITH {p56} OR
89+
| tn.prop STARTS WITH {p57} OR
90+
| tn.prop STARTS WITH {p58} OR
91+
| tn.prop STARTS WITH {p59} OR
92+
| tn.prop STARTS WITH {p60} OR
93+
| tn.prop STARTS WITH {p61} OR
94+
| tn.prop STARTS WITH {p62} OR
95+
| tn.prop STARTS WITH {p63} OR
96+
| tn.prop STARTS WITH {p64} OR
97+
| tn.prop STARTS WITH {p65} OR
98+
| tn.prop STARTS WITH {p66} OR
99+
| tn.prop STARTS WITH {p67} OR
100+
| tn.prop STARTS WITH {p68} OR
101+
| tn.prop STARTS WITH {p69} OR
102+
| tn.prop STARTS WITH {p70} OR
103+
| tn.prop STARTS WITH {p71} OR
104+
| tn.prop STARTS WITH {p72} OR
105+
| tn.prop STARTS WITH {p73} OR
106+
| tn.prop STARTS WITH {p74} OR
107+
| tn.prop STARTS WITH {p75} OR
108+
| tn.prop STARTS WITH {p76} OR
109+
| tn.prop STARTS WITH {p77} OR
110+
| tn.prop STARTS WITH {p78} OR
111+
| tn.prop STARTS WITH {p79} OR
112+
| tn.prop STARTS WITH {p80} OR
113+
| tn.prop STARTS WITH {p81} OR
114+
| tn.prop STARTS WITH {p82} OR
115+
| tn.prop STARTS WITH {p83} OR
116+
| tn.prop STARTS WITH {p84} OR
117+
| tn.prop STARTS WITH {p85} OR
118+
| tn.prop STARTS WITH {p86} OR
119+
| tn.prop STARTS WITH {p87} OR
120+
| tn.prop STARTS WITH {p88} OR
121+
| tn.prop STARTS WITH {p89} OR
122+
| tn.prop STARTS WITH {p90} OR
123+
| tn.prop STARTS WITH {p91} OR
124+
| tn.prop STARTS WITH {p92}
125+
| ) AND
126+
| tn.processType IN {p0}
127+
| AND
128+
| tn.status IN {p1}
129+
| AND
130+
| tn.fileCollectionEnabled = $p2
131+
|)
132+
|RETURN tn""".stripMargin
133+
134+
val plan = runWithTimeout(10)((new given {
135+
indexOn("X", "prop")
136+
} getLogicalPlanFor query)._2)
137+
138+
plan.treeCount {
139+
case _: NodeIndexSeek => true
140+
} should be(90)
141+
}
142+
143+
private def runWithTimeout[T](timeout: Long)(f: => T) : T = {
144+
import scala.concurrent.ExecutionContext.Implicits.global
145+
Await.result(scala.concurrent.Future(f), Duration.apply(timeout, "s"))
146+
}
147+
}

‎community/cypher/cypher-planner-3.4/src/test/scala/org/neo4j/cypher/internal/compiler/v3_4/planner/logical/steps/OrLeafPlannerTest.scala‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -22,13 +22,12 @@ package org.neo4j.cypher.internal.compiler.v3_4.planner.logical.steps
2222
import org.mockito.ArgumentMatchers
2323
import org.mockito.ArgumentMatchers._
2424
import org.mockito.Mockito._
25-
import org.neo4j.cypher.internal.util.v3_4.test_helpers.CypherFunSuite
2625
import org.neo4j.cypher.internal.compiler.v3_4.planner.LogicalPlanningTestSupport
27-
import org.neo4j.cypher.internal.compiler.v3_4.planner.logical.{LeafPlanFromExpressions, LeafPlansForVariable, LogicalPlanningContext}
26+
import org.neo4j.cypher.internal.compiler.v3_4.planner.logical.{LeafPlanFromExpressions, LeafPlansForVariable}
2827
import org.neo4j.cypher.internal.ir.v3_4.{QueryGraph, Selections}
29-
import org.neo4j.cypher.internal.planner.v3_4.spi.PlanningAttributes.{Cardinalities, Solveds}
30-
import org.neo4j.cypher.internal.v3_4.logical.plans.{Distinct, Union}
28+
import org.neo4j.cypher.internal.util.v3_4.test_helpers.CypherFunSuite
3129
import org.neo4j.cypher.internal.v3_4.expressions.{Ors, Variable}
30+
import org.neo4j.cypher.internal.v3_4.logical.plans.{Distinct, Union}
3231

3332
class OrLeafPlannerTest extends CypherFunSuite with LogicalPlanningTestSupport {
3433

‎community/cypher/runtime-util/src/test/scala/org/neo4j/cypher/GraphIcing.scala‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -94,7 +94,7 @@ trait GraphIcing {
9494
}
9595

9696
def createIndex(label: String, properties: String*) = {
97-
graph.execute(s"CREATE INDEX ON :$label(${properties.mkString(",")})")
97+
graph.execute(s"CREATE INDEX ON :$label(${properties.map(p => s"`$p`").mkString(",")})")
9898

9999
inTx {
100100
graph.schema().awaitIndexesOnline(10, TimeUnit.MINUTES)

0 commit comments

Comments
 (0)