FilterRankStrategy is getting nasty solid at optimizing filters and itself, as a strategy, is now super efficient -- gutting code here and there as I realize that this is just a that.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/b8a92a30 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/b8a92a30 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/b8a92a30 Branch: refs/heads/TINKERPOP-1458 Commit: b8a92a30df8ce67a437c8484d950437d3a34cbca Parents: 56de652 Author: Marko A. Rodriguez <[email protected]> Authored: Fri Sep 30 13:42:33 2016 -0600 Committer: Marko A. Rodriguez <[email protected]> Committed: Mon Oct 3 08:24:17 2016 -0600 ---------------------------------------------------------------------- .../optimization/FilterRankingStrategy.java | 43 ++++++++------------ .../process/traversal/util/TraversalHelper.java | 10 ----- .../optimization/FilterRankingStrategyTest.java | 11 ++++- .../PathRetractionStrategyTest.java | 3 +- 4 files changed, 26 insertions(+), 41 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8a92a30/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 2065ea1..2f8061b 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 @@ -42,7 +42,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversal import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; import java.util.Collections; -import java.util.HashSet; import java.util.List; import java.util.Set; @@ -91,29 +90,24 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave boolean modified = true; while (modified) { modified = false; - final Set<String> currentLabels = new HashSet<>(); - for (final Step<?, ?> step : traversal.getSteps()) { - if (!step.getLabels().isEmpty()) { - currentLabels.addAll(step.getLabels()); - final Step<?, ?> nextStep = step.getNextStep(); - if (validFilterStep(nextStep) && !usesLabels(nextStep, currentLabels)) { - TraversalHelper.copyLabels(step, nextStep, true); - modified = true; - } - } - } final List<Step> steps = traversal.getSteps(); - int prevRank = 0; - for (int i = steps.size() - 1; i >= 0; i--) { - final Step curr = steps.get(i); - final int rank = usesLabels(curr, TraversalHelper.getLabelsUpTo(curr)) ? 0 : getStepRank(curr); - if (prevRank > 0 && rank > prevRank) { - final Step next = curr.getNextStep(); - traversal.removeStep(next); - traversal.addStep(i, next); - modified = true; + for (int i = 0; i < steps.size() - 1; i++) { + final Step<?, ?> step = steps.get(i); + final Step<?, ?> nextStep = step.getNextStep(); + if (!usesLabels(nextStep, step.getLabels())) { + final int nextRank = getStepRank(nextStep); + if (nextRank != 0) { + if (!step.getLabels().isEmpty()) { + TraversalHelper.copyLabels(step, nextStep, true); + modified = true; + } + if (getStepRank(step) > nextRank) { + traversal.removeStep(nextStep); + traversal.addStep(i, nextStep); + modified = true; + } + } } - prevRank = rank; } } } @@ -152,11 +146,6 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave return 0; } - - private static boolean validFilterStep(final Step<?, ?> step) { - return ((step instanceof FilterStep && !(step instanceof LambdaHolder)) || step instanceof OrderGlobalStep); - } - private static boolean usesLabels(final Step<?, ?> step, final Set<String> labels) { if (step instanceof LambdaHolder) return true; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8a92a30/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java index 1fb9fab..87d3479 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java @@ -592,16 +592,6 @@ public final class TraversalHelper { } } - public static Set<String> getLabelsUpTo(final Step<?, ?> stopStep) { - final Set<String> labels = new HashSet<>(); - Step<?, ?> step = stopStep.getPreviousStep(); - while (!(step instanceof EmptyStep)) { - labels.addAll(step.getLabels()); - step = step.getPreviousStep(); - } - return labels; - } - public static boolean hasAllStepsOfClass(final Traversal.Admin<?, ?> traversal, final Class<?>... classesToCheck) { for (final Step step : traversal.getSteps()) { boolean foundInstance = false; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8a92a30/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 99e0cab..ff72f8c 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 @@ -21,7 +21,6 @@ package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; -import org.apache.tinkerpop.gremlin.process.traversal.Traverser; 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; @@ -34,6 +33,7 @@ import java.util.Collection; import java.util.Collections; import java.util.function.Predicate; +import static org.apache.tinkerpop.gremlin.process.traversal.P.eq; import static org.apache.tinkerpop.gremlin.process.traversal.P.neq; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.filter; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.has; @@ -86,11 +86,18 @@ public class FilterRankingStrategyTest { {__.has("name", "marko").as("a").out().has("age", 32).as("b").where("a", neq("b")), __.has("name", "marko").as("a").out().has("age", 32).as("b").where("a", neq("b")), Collections.emptyList()}, {__.has("name", "marko").has("age", 32).dedup().has("name", "bob").as("a"), __.has("name", "marko").has("age", 32).has("name", "bob").dedup().as("a"), Collections.emptyList()}, {__.has("name", "marko").dedup().as("a").has("age", 32).has("name", "bob").as("b"), __.has("name", "marko").has("age", 32).has("name", "bob").dedup().as("b", "a"), Collections.emptyList()}, + {__.where("b", eq("c")).as("a").dedup("a").has("name", "marko"), __.has("name", "marko").where("b", eq("c")).as("a").dedup("a"), Collections.emptyList()}, + {__.where("b", eq("c")).has("name", "bob").as("a").dedup("a").has("name", "marko"), __.has("name", "bob").has("name", "marko").where("b", eq("c")).as("a").dedup("a"), Collections.emptyList()}, + {__.has("name","marko").as("a").out().has("name","bob").dedup().as("b").where(__.as("a").out().as("b")),__.has("name","marko").as("a").out().has("name","bob").dedup().as("b").where(__.as("a").out().as("b")),Collections.emptyList()}, + {__.has("name","marko").as("a").out().has("name","bob").as("b").dedup().where(__.as("a").out().as("b")),__.has("name","marko").as("a").out().has("name","bob").dedup().as("b").where(__.as("a").out().as("b")),Collections.emptyList()}, + {__.has("name","marko").as("a").out().has("name","bob").dedup().as("c").where(__.as("a").out().as("b")),__.has("name","marko").as("a").out().has("name","bob").where(__.as("a").out().as("b")).dedup().as("c"),Collections.emptyList()}, {__.order().dedup(), __.dedup().order(), Collections.emptyList()}, {__.order().filter(testP).dedup(), __.order().filter(testP).dedup(), Collections.emptyList()}, {__.order().as("a").dedup(), __.dedup().order().as("a"), Collections.emptyList()}, {__.order().as("a").dedup("a"), __.order().as("a").dedup("a"), Collections.emptyList()}, - // {__.order().as("a").dedup("a").has("name","marko"), __.has("name","marko").order().as("a").dedup("a"), Collections.emptyList()}, + {__.order().as("a").dedup("a").has("name", "marko"), __.has("name", "marko").as("a").dedup("a").order(), Collections.emptyList()}, + {__.order().as("a").dedup("a").has("name", "marko").out(), __.has("name", "marko").as("a").dedup("a").order().out(), Collections.emptyList()}, + {__.order().as("a").dedup("a").has("name", "marko").where("a", eq("b")).out(), __.has("name", "marko").as("a").where("a", eq("b")).dedup("a").order().out(), Collections.emptyList()}, {__.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()}, http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8a92a30/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java index 0063289..e95c729 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java @@ -60,8 +60,7 @@ public class PathRetractionStrategyTest { new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance()), new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance()), new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance()), - new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance()), - TraversalStrategies.GlobalCache.getStrategies(Graph.class)); + new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance())); @Parameterized.Parameter(value = 0) public Traversal.Admin traversal;
