You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2016/09/28 00:19:21 UTC
tinkerpop git commit: found a insidious bug where FilterRankStrategy
wasn't sorting SubgraphStrategy filters. The reason -- SubgraphStrategy uses
hidden labels to communicate information between children. Given that hidden
step labels are for compilation
Repository: tinkerpop
Updated Branches:
refs/heads/master 24c14cf91 -> 317fb0c78
found a insidious bug where FilterRankStrategy wasn't sorting SubgraphStrategy filters. The reason -- SubgraphStrategy uses hidden labels to communicate information between children. Given that hidden step labels are for compilation purposes only, FilterRankStrategy does not consider hidden labels an reason notOptimizeStep(). Added a butt ton of test cases to finally expose the problem. This is related to the SubgraphStrategy merge work earlier. CTR.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/317fb0c7
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/317fb0c7
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/317fb0c7
Branch: refs/heads/master
Commit: 317fb0c7894412393f93b9e0ffaebedb9aa54c60
Parents: 24c14cf
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Tue Sep 27 18:19:13 2016 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Tue Sep 27 18:19:13 2016 -0600
----------------------------------------------------------------------
.../optimization/FilterRankingStrategy.java | 21 +++++++++++++++-----
.../optimization/FilterRankingStrategyTest.java | 20 +++++++++++++++----
.../TinkerGraphStepStrategyTest.java | 6 ++++++
3 files changed, 38 insertions(+), 9 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/317fb0c7/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
index 96843d9..04b789b 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
@@ -24,11 +24,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.AndStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.ClassFilterStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.CyclicPathStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.DedupGlobalStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.FilterStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.HasStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.IsStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.NotStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.OrStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.SimplePathStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TraversalFilterStep;
@@ -37,6 +39,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereTraversal
import org.apache.tinkerpop.gremlin.process.traversal.step.map.OrderGlobalStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.structure.Graph;
import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
import java.util.HashSet;
@@ -126,7 +129,7 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
private static int getStepRank(final Step step) {
if (!(step instanceof FilterStep || step instanceof OrderGlobalStep))
return 0;
- else if (step instanceof IsStep)
+ else if (step instanceof IsStep || step instanceof ClassFilterStep)
return 1;
else if (step instanceof HasStep)
return 2;
@@ -134,7 +137,7 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
return 3;
else if (step instanceof SimplePathStep || step instanceof CyclicPathStep)
return 4;
- else if (step instanceof TraversalFilterStep)
+ else if (step instanceof TraversalFilterStep || step instanceof NotStep)
return 5;
else if (step instanceof WhereTraversalStep)
return 6;
@@ -179,10 +182,18 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
* Returns true if the step is not optimizable, otherwise false. A step is not optimizable if it (or any of its
* child traversals) is a lambda holder or has a label.
*
- * @param step
+ * @param step the step to check for optimizability
* @return true if the given step is optimizable, otherwise false.
*/
- private static boolean isNotOptimizableStep(final Step step) {
- return step instanceof LambdaHolder || !step.getLabels().isEmpty();
+ private static boolean isNotOptimizableStep(final Step<?, ?> step) {
+ if (step instanceof LambdaHolder)
+ return true;
+ else {
+ for (final String label : step.getLabels()) {
+ if (!Graph.Hidden.isHidden(label))
+ return true;
+ }
+ return false;
+ }
}
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/317fb0c7/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
index 18ef6ca..dc0d17a 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
@@ -23,6 +23,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
+import org.apache.tinkerpop.gremlin.structure.Graph;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
@@ -31,7 +32,15 @@ import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.filter;
import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.has;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.in;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.inE;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.not;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.or;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.out;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.outE;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.properties;
import static org.junit.Assert.assertEquals;
/**
@@ -75,12 +84,15 @@ public class FilterRankingStrategyTest {
{__.identity().order().dedup(), __.dedup().order(), Collections.singletonList(IdentityRemovalStrategy.instance())},
{__.order().identity().dedup(), __.dedup().order(), Collections.singletonList(IdentityRemovalStrategy.instance())},
{__.order().out().dedup(), __.order().out().dedup(), Collections.emptyList()},
- {has("value", 0).filter(__.out()).dedup(), has("value", 0).filter(__.out()).dedup(), Collections.emptyList()},
- {__.dedup().filter(__.out()).has("value", 0), has("value", 0).filter(__.out()).dedup(), Collections.emptyList()},
- {__.filter(__.out()).dedup().has("value", 0), has("value", 0).filter(__.out()).dedup(), Collections.emptyList()},
- {has("value", 0).filter(__.out()).dedup(), has("value", 0).filter(__.out()).dedup(), Collections.emptyList()},
+ {has("value", 0).filter(out()).dedup(), has("value", 0).filter(out()).dedup(), Collections.emptyList()},
+ {__.dedup().has("value", 0).or(not(has("age")), has("age", 10)).has("value", 1), __.has("value", 0).has("value", 1).or(not(has("age")), has("age", 10)).dedup(), Collections.emptyList()},
+ {__.dedup().filter(out()).has("value", 0), has("value", 0).filter(out()).dedup(), Collections.emptyList()},
+ {filter(out()).dedup().has("value", 0), has("value", 0).filter(out()).dedup(), Collections.emptyList()},
+ {has("value", 0).filter(out()).dedup(), has("value", 0).filter(out()).dedup(), Collections.emptyList()},
{has("value", 0).or(has("name"), has("age")).has("value", 1).dedup(), has("value", 0).has("value", 1).or(has("name"), has("age")).dedup(), Collections.emptyList()},
+ {has("value", 0).or(out(), in()).as(Graph.Hidden.hide("x")).has("value", 1).dedup(), has("value", 0).has("value", 1).or(outE(), inE()).dedup(), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
{has("value", 0).and(has("age"), has("name", "marko")).is(10), __.is(10).has("value", 0).has("name", "marko").has("age"), Collections.singletonList(InlineFilterStrategy.instance())},
+ {has("value", 0).filter(or(not(has("age")), has("age", 1))).has("value", 1).dedup(), has("value", 0).has("value", 1).or(not(filter(properties("age"))), has("age", 1)).dedup(), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
});
}
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/317fb0c7/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/strategy/optimization/TinkerGraphStepStrategyTest.java
----------------------------------------------------------------------
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/strategy/optimization/TinkerGraphStepStrategyTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/strategy/optimization/TinkerGraphStepStrategyTest.java
index 89ca7ba..d2bc0ea 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/strategy/optimization/TinkerGraphStepStrategyTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/strategy/optimization/TinkerGraphStepStrategyTest.java
@@ -44,7 +44,11 @@ import java.util.Collections;
import static org.apache.tinkerpop.gremlin.process.traversal.P.eq;
import static org.apache.tinkerpop.gremlin.process.traversal.P.gt;
import static org.apache.tinkerpop.gremlin.process.traversal.P.lt;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.filter;
import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.has;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.not;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.properties;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.values;
import static org.junit.Assert.assertEquals;
/**
@@ -108,6 +112,8 @@ public class TinkerGraphStepStrategyTest {
g_V("name", eq("marko"), "name", eq("bob"), "lang", eq("java")).as("a").or(has("age"), has("age", gt(32))).dedup(), Arrays.asList(InlineFilterStrategy.instance(), FilterRankingStrategy.instance())},
{__.V().as("a").dedup().has("name", "marko").or(has("age", 10), has("age", gt(32))).filter(has("name", "bob")).has("lang", "java"),
g_V("name", eq("marko"), "name", eq("bob"), "lang", eq("java")).as("a").or(has("age", 10), has("age", gt(32))).dedup(), TraversalStrategies.GlobalCache.getStrategies(TinkerGraph.class).toList()},
+ {__.V().has("name", "marko").or(not(has("age")), has("age", gt(32))).has("name", "bob").has("lang", "java"),
+ g_V("name", eq("marko"), "name", eq("bob"), "lang", eq("java")).or(not(filter(properties("age"))), has("age", gt(32))), TraversalStrategies.GlobalCache.getStrategies(TinkerGraph.class).toList()}
});
}
}