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/30 16:36:27 UTC
tinkerpop git commit: FilterRankStrategy now is smart about Scoping
steps and thus,
can rank labeled steps. order().as('a').dedup() is dedup().order().as('a'),
but order().as('a').dedup('a') is order().as('a').dedup('a'). Lots of test
cases in FilterRank
Repository: tinkerpop
Updated Branches:
refs/heads/TINKERPOP-1470 4a971d1fa -> 7e36f339b
FilterRankStrategy now is smart about Scoping steps and thus, can rank labeled steps. order().as('a').dedup() is dedup().order().as('a'), but order().as('a').dedup('a') is order().as('a').dedup('a'). Lots of test cases in FilterRankStrategyTest updated with more efficient reordering.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/7e36f339
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/7e36f339
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/7e36f339
Branch: refs/heads/TINKERPOP-1470
Commit: 7e36f339bfad5e911ee2667f7c93fa2cc3cc7956
Parents: 4a971d1
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Fri Sep 30 10:36:23 2016 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Fri Sep 30 10:36:23 2016 -0600
----------------------------------------------------------------------
.../optimization/FilterRankingStrategy.java | 86 ++++++++------------
.../process/traversal/util/TraversalHelper.java | 20 +++++
.../optimization/FilterRankingStrategyTest.java | 15 ++--
.../TinkerGraphStepStrategyTest.java | 10 +--
4 files changed, 68 insertions(+), 63 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/7e36f339/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 06726b1..2065ea1 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
@@ -22,6 +22,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
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.Scoping;
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;
@@ -39,17 +40,16 @@ 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.Collections;
-import java.util.Iterator;
+import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
- * FilterRankingStrategy reorders filter- and order-steps according to their rank. Labeled steps or lambda holders or
- * steps that contain child traversals, that have labeled steps or lambda holders, will not be reordered.
+ * FilterRankingStrategy reorders filter- and order-steps according to their rank. It will also do its best to push
+ * step labels as far "right" as possible in order to keep traversers as small and bulkable as possible prior to the
+ * absolute need for path-labeling.
* <p/>
* <table>
* <thead>
@@ -89,12 +89,14 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
@Override
public void apply(final Traversal.Admin<?, ?> traversal) {
boolean modified = true;
- while(modified) {
+ while (modified) {
modified = false;
+ final Set<String> currentLabels = new HashSet<>();
for (final Step<?, ?> step : traversal.getSteps()) {
- if (step instanceof FilterStep && !step.getLabels().isEmpty()) {
+ if (!step.getLabels().isEmpty()) {
+ currentLabels.addAll(step.getLabels());
final Step<?, ?> nextStep = step.getNextStep();
- if (nextStep instanceof FilterStep && !(nextStep instanceof TraversalParent)) {
+ if (validFilterStep(nextStep) && !usesLabels(nextStep, currentLabels)) {
TraversalHelper.copyLabels(step, nextStep, true);
modified = true;
}
@@ -104,7 +106,7 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
int prevRank = 0;
for (int i = steps.size() - 1; i >= 0; i--) {
final Step curr = steps.get(i);
- final int rank = rank(curr);
+ final int rank = usesLabels(curr, TraversalHelper.getLabelsUpTo(curr)) ? 0 : getStepRank(curr);
if (prevRank > 0 && rank > prevRank) {
final Step next = curr.getNextStep();
traversal.removeStep(next);
@@ -116,15 +118,6 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
}
}
- @Override
- public Set<Class<? extends OptimizationStrategy>> applyPrior() {
- return PRIORS;
- }
-
- public static FilterRankingStrategy instance() {
- return INSTANCE;
- }
-
/**
* Ranks the given step. Steps with lower ranks can be moved in front of steps with higher ranks. 0 means that
* the step has no rank and thus is not exchangeable with its neighbors.
@@ -159,47 +152,34 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
return 0;
}
- /**
- * If the given step has no child traversal that holds a lambda, then the actual rank determined by
- * {@link #getStepRank(Step)} is returned, otherwise 0.
- *
- * @param step the step to get a ranking for
- * @return The rank of the given step.
- */
- private static int rank(final Step step) {
- if (isNotOptimizableStep(step)) {
- return 0;
- }
- final int rank = getStepRank(step);
- if (rank > 0 && step instanceof TraversalParent) {
- final TraversalParent tp = (TraversalParent) step;
- final Iterator<Traversal.Admin<Object, Object>> childTraversalIterator = IteratorUtils.concat(
- tp.getLocalChildren().iterator(), tp.getGlobalChildren().iterator());
- while (childTraversalIterator.hasNext()) {
- if (TraversalHelper.anyStepRecursively(FilterRankingStrategy::isNotOptimizableStep, childTraversalIterator.next())) {
- return 0;
- }
- }
- }
- return rank;
+
+ private static boolean validFilterStep(final Step<?, ?> step) {
+ return ((step instanceof FilterStep && !(step instanceof LambdaHolder)) || step instanceof OrderGlobalStep);
}
- /**
- * 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 the step to check for optimizability
- * @return true if the given step is optimizable, otherwise false.
- */
- private static boolean isNotOptimizableStep(final Step<?, ?> step) {
+ private static boolean usesLabels(final Step<?, ?> step, final Set<String> labels) {
if (step instanceof LambdaHolder)
return true;
- else {
- for (final String label : step.getLabels()) {
- if (!Graph.Hidden.isHidden(label))
+ if (step instanceof Scoping) {
+ final Set<String> scopes = ((Scoping) step).getScopeKeys();
+ for (final String label : labels) {
+ if (scopes.contains(label))
return true;
}
- return false;
}
+ if (step instanceof TraversalParent) {
+ if (TraversalHelper.anyStepRecursively(s -> usesLabels(s, labels), (TraversalParent) step))
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public Set<Class<? extends OptimizationStrategy>> applyPrior() {
+ return PRIORS;
+ }
+
+ public static FilterRankingStrategy instance() {
+ return INSTANCE;
}
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/7e36f339/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 be1406d..1fb9fab 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
@@ -425,6 +425,16 @@ public final class TraversalHelper {
return false;
}
+ public static boolean anyStepRecursively(final Predicate<Step> predicate, final TraversalParent step) {
+ for (final Traversal.Admin<?, ?> localChild : step.getLocalChildren()) {
+ if (anyStepRecursively(predicate, localChild)) return true;
+ }
+ for (final Traversal.Admin<?, ?> globalChild : step.getGlobalChildren()) {
+ if (anyStepRecursively(predicate, globalChild)) return true;
+ }
+ return false;
+ }
+
public static <S> void addToCollection(final Collection<S> collection, final S s, final long bulk) {
if (collection instanceof BulkSet) {
((BulkSet<S>) collection).add(s, bulk);
@@ -582,6 +592,16 @@ 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/7e36f339/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 bd12e34..99e0cab 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,6 +21,7 @@ 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;
@@ -31,6 +32,7 @@ import org.junit.runners.Parameterized;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
+import java.util.function.Predicate;
import static org.apache.tinkerpop.gremlin.process.traversal.P.neq;
import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.filter;
@@ -77,15 +79,18 @@ public class FilterRankingStrategyTest {
@Parameterized.Parameters(name = "{0}")
public static Iterable<Object[]> generateTestParameters() {
-
+ final Predicate testP = t -> true;
return Arrays.asList(new Object[][]{
{__.dedup().order(), __.dedup().order(), Collections.emptyList()},
- {__.has("name", "marko").as("a").out().as("b").has("age", 32).where("a", neq("b")), __.has("name", "marko").as("a").out().as("b").has("age", 32).where("a", neq("b")), Collections.emptyList()},
+ {__.has("name", "marko").as("a").out().as("b").has("age", 32).where("a", neq("b")).as("c").out(), __.has("name", "marko").as("a").out().has("age", 32).as("b").where("a", neq("b")).as("c").out(), Collections.emptyList()},
{__.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).dedup().has("name", "bob").as("a"), Collections.emptyList()},
- {__.has("name", "marko").dedup().as("a").has("age", 32).has("name", "bob").as("b"), __.has("name", "marko").has("age", 32).dedup().has("name", "bob").as("a", "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()},
{__.order().dedup(), __.dedup().order(), Collections.emptyList()},
- {__.order().as("a").dedup(), __.order().as("a").dedup(), 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()},
{__.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/7e36f339/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 9f97466..35f936c 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
@@ -100,17 +100,17 @@ public class TinkerGraphStepStrategyTest {
{__.V().has("name", "marko").as("a").or(has("age"), has("age", gt(32))).has("lang", "java"),
g_V("name", eq("marko")).as("a").or(has("age"), has("age", gt(32))).has("lang", "java"), Collections.emptyList()},
{__.V().has("name", "marko").as("a").or(has("age"), has("age", gt(32))).has("lang", "java"),
- g_V("name", eq("marko"), "lang", eq("java")).as("a").or(has("age"), has("age", gt(32))), Collections.singletonList(FilterRankingStrategy.instance())},
+ g_V("name", eq("marko"), "lang", eq("java")).or(has("age"), has("age", gt(32))).as("a"), Collections.singletonList(FilterRankingStrategy.instance())},
{__.V().dedup().has("name", "marko").or(has("age"), has("age", gt(32))).has("lang", "java"),
g_V("name", eq("marko"), "lang", eq("java")).or(has("age"), has("age", gt(32))).dedup(), Collections.singletonList(FilterRankingStrategy.instance())},
{__.V().as("a").dedup().has("name", "marko").or(has("age"), has("age", gt(32))).has("lang", "java"),
- g_V("name", eq("marko"), "lang", eq("java")).as("a").or(has("age"), has("age", gt(32))).dedup(), Collections.singletonList(FilterRankingStrategy.instance())},
+ g_V("name", eq("marko"), "lang", eq("java")).or(has("age"), has("age", gt(32))).dedup().as("a"), Collections.singletonList(FilterRankingStrategy.instance())},
{__.V().as("a").has("name", "marko").as("b").or(has("age"), has("age", gt(32))).has("lang", "java"),
- g_V("name", eq("marko"), "lang", eq("java")).as("a", "b").or(has("age"), has("age", gt(32))), Collections.singletonList(FilterRankingStrategy.instance())},
+ g_V("name", eq("marko"), "lang", eq("java")).or(has("age"), has("age", gt(32))).as("b", "a"), Collections.singletonList(FilterRankingStrategy.instance())},
{__.V().as("a").dedup().has("name", "marko").or(has("age"), 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"), has("age", gt(32))).dedup(), Arrays.asList(InlineFilterStrategy.instance(), FilterRankingStrategy.instance())},
+ g_V("name", eq("marko"), "name", eq("bob"), "lang", eq("java")).or(has("age"), has("age", gt(32))).dedup().as("a"), 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"), "age", eq(10).or(gt(32)), "name", eq("bob"), "lang", eq("java")).as("a").dedup(), TraversalStrategies.GlobalCache.getStrategies(TinkerGraph.class).toList()},
+ g_V("name", eq("marko"), "age", eq(10).or(gt(32)), "name", eq("bob"), "lang", eq("java")).dedup().as("a"), 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()}
});