Added OLTP optimization where a barrier is added after a path processor to try and thin the stream. When we move to having LazyBarrierStrategy go prime time, we should move that code to there. Added more test cases to PrunePathStrategyTest to ensure proper compilation. Added an Ignore to a TinkerGraphPlay test that was live and thus, outputing System.out during testing.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/9d205f89 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/9d205f89 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/9d205f89 Branch: refs/heads/master Commit: 9d205f89d99c9c04ece93e4bdb713701a1010652 Parents: aa6059a Author: Marko A. Rodriguez <[email protected]> Authored: Fri Jul 8 16:28:59 2016 -0600 Committer: Marko A. Rodriguez <[email protected]> Committed: Fri Jul 8 16:28:59 2016 -0600 ---------------------------------------------------------------------- .../optimization/PrunePathStrategy.java | 13 +++++- .../process/traversal/util/PathUtil.java | 11 +++-- .../optimization/PrunePathStrategyTest.java | 42 +++++++++++++------- .../structure/TinkerGraphPlayTest.java | 2 +- 4 files changed, 47 insertions(+), 21 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/9d205f89/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java index ff56c96..7d6650f 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java @@ -23,7 +23,9 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor; import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.NoOpBarrierStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.ReducingBarrierStep; import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; import org.apache.tinkerpop.gremlin.process.traversal.util.PathUtil; @@ -40,6 +42,8 @@ import java.util.Set; */ public final class PrunePathStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy { + public static Integer MAX_BARRIER_SIZE = 1000; + private static final PrunePathStrategy INSTANCE = new PrunePathStrategy(); // these strategies do strong rewrites involving path labeling and thus, should run prior to PrunePathStrategy private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Arrays.asList(RepeatUnrollStrategy.class, MatchPredicateStrategy.class, PathProcessorStrategy.class)); @@ -103,6 +107,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal @Override public void apply(final Traversal.Admin<?, ?> traversal) { + final boolean onGraphComputer = TraversalHelper.onGraphComputer(traversal); final TraversalParent parent = traversal.getParent(); final Set<String> foundLabels = new HashSet<>(); final Set<String> keepLabels = new HashSet<>(); @@ -141,8 +146,14 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal foundLabels.add(label); } // add the keep labels to the path processor - if (currentStep instanceof PathProcessor) + if (currentStep instanceof PathProcessor) { ((PathProcessor) currentStep).setKeepLabels(new HashSet<>(keepLabels)); + // OLTP barrier optimization that will try and bulk traversers after a path processor step to thin the stream + if (!onGraphComputer && + !(currentStep.getNextStep() instanceof ReducingBarrierStep) && + !(currentStep.getNextStep() instanceof NoOpBarrierStep)) + TraversalHelper.insertAfterStep(new NoOpBarrierStep<>(traversal, MAX_BARRIER_SIZE), currentStep, traversal); + } } else { // if there is a PATH requiring step in the traversal, do not drop labels // set keep labels to null so that no labels are dropped http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/9d205f89/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java index 5a9bb0a..e621d00 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java @@ -34,9 +34,13 @@ import java.util.Set; */ public class PathUtil { + private PathUtil() { + // public static methods only + } + public static Set<String> getReferencedLabels(final Traversal.Admin<?, ?> traversal) { final Set<String> referencedLabels = new HashSet<>(); - for(final Step<?, ?> step : traversal.getSteps()) { + for (final Step<?, ?> step : traversal.getSteps()) { referencedLabels.addAll(getReferencedLabels(step)); } return referencedLabels; @@ -46,12 +50,11 @@ public class PathUtil { final Set<String> referencedLabels = new HashSet<>(); if (step instanceof Parameterizing) { - Parameters parameters = ((Parameterizing) step).getParameters(); + final Parameters parameters = ((Parameterizing) step).getParameters(); for (final Traversal.Admin trav : parameters.getTraversals()) { for (final Object ss : trav.getSteps()) { if (ss instanceof Scoping) { - Set<String> labels = ((Scoping) ss).getScopeKeys(); - for (String label : labels) { + for (String label : ((Scoping) ss).getScopeKeys()) { referencedLabels.add(label); } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/9d205f89/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java index c8ef0b7..9749971 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java @@ -41,6 +41,7 @@ import java.util.Set; import static org.apache.tinkerpop.gremlin.process.traversal.P.gte; import static org.apache.tinkerpop.gremlin.process.traversal.P.neq; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.as; +import static org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PrunePathStrategy.MAX_BARRIER_SIZE; import static org.junit.Assert.assertEquals; /** @@ -62,6 +63,9 @@ public class PrunePathStrategyTest { @Parameterized.Parameter(value = 1) public List<Set<String>> labels; + @Parameterized.Parameter(value = 2) + public Traversal.Admin optimized; + @Test public void doTest() { for (final TraversalStrategies currentStrategies : this.strategies) { @@ -70,6 +74,8 @@ public class PrunePathStrategyTest { currentTraversal.applyStrategies(); final List<Object> keepLabels = getKeepLabels(currentTraversal); assertEquals(this.labels, keepLabels); + if (null != optimized) + assertEquals(currentTraversal, optimized); } } @@ -102,27 +108,33 @@ public class PrunePathStrategyTest { public static Iterable<Object[]> generateTestParameters() { return Arrays.asList(new Object[][]{ - {__.out(), Arrays.asList()}, - {__.V().as("a").out().as("b").where(neq("a")).out(), Arrays.asList(Collections.emptySet())}, - {__.V().as("a").out().where(neq("a")).out().select("a"), Arrays.asList(Collections.singleton("a"), Collections.emptySet())}, - {__.V().as("a").out().as("b").where(neq("a")).out().select("a", "b").out().select("b"), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")), Collections.singleton("b"), Collections.emptySet())}, - {__.V().match(__.as("a").out().as("b")), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")))}, - {__.V().match(__.as("a").out().as("b")).select("a"), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")), Collections.emptySet())}, + {__.out(), Arrays.asList(), null}, + {__.V().as("a").out().as("b").where(neq("a")).out(), Arrays.asList(Collections.emptySet()), null}, + {__.V().as("a").out().where(neq("a")).out().select("a"), Arrays.asList(Collections.singleton("a"), Collections.emptySet()), null}, + {__.V().as("a").out().as("b").where(neq("a")).out().select("a", "b").out().select("b"), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")), Collections.singleton("b"), Collections.emptySet()), null}, + {__.V().match(__.as("a").out().as("b")), Arrays.asList(new HashSet<>(Arrays.asList("a", "b"))), null}, + {__.V().match(__.as("a").out().as("b")).select("a"), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")), Collections.emptySet()), null}, {__.V().out().out().match( as("a").in("created").as("b"), as("b").in("knows").as("c")).select("c").out("created").where(neq("a")).values("name"), - Arrays.asList(new HashSet<>(Arrays.asList("a", "b", "c")), Collections.singleton("a"), Collections.emptySet())}, - {__.V().as("a").out().select("a").path(), Arrays.asList()}, - {__.V().as("a").out().select("a").subgraph("b"), Arrays.asList(Collections.emptySet())}, - {__.V().as("a").out().select("a").subgraph("b").select("a"), Arrays.asList(Collections.singleton("a"), Collections.emptySet())}, - {__.V().out().as("a").where(neq("a")).out().where(neq("a")).out(), Arrays.asList(Collections.singleton("a"), Collections.emptySet())}, - {__.V().out().as("a").where(__.out().select("a").values("prop").count().is(gte(1))).out().where(neq("a")), Arrays.asList(Arrays.asList(Collections.singleton("a")), Collections.emptySet())}, + Arrays.asList(new HashSet<>(Arrays.asList("a", "b", "c")), Collections.singleton("a"), Collections.emptySet()), null}, + {__.V().as("a").out().select("a").path(), Arrays.asList(), null}, + {__.V().as("a").out().select("a").subgraph("b"), Arrays.asList(Collections.emptySet()), null}, + {__.V().as("a").out().select("a").subgraph("b").select("a"), Arrays.asList(Collections.singleton("a"), Collections.emptySet()), null}, + {__.V().out().as("a").where(neq("a")).out().where(neq("a")).out(), Arrays.asList(Collections.singleton("a"), Collections.emptySet()), null}, + {__.V().out().as("a").where(__.out().select("a").values("prop").count().is(gte(1))).out().where(neq("a")), Arrays.asList(Arrays.asList(Collections.singleton("a")), Collections.emptySet()), null}, {__.V().as("a").out().as("b").where(__.out().select("a", "b", "c").values("prop").count().is(gte(1))).out().where(neq("a")).out().select("b"), - Arrays.asList(Arrays.asList(new HashSet<>(Arrays.asList("a", "b", "c"))), Collections.singleton("b"), Collections.emptySet())}, - {__.outE().inV().group().by(__.inE().outV().groupCount().by(__.both().count().is(P.gt(2)))), Arrays.asList()}, - {__.V().as("a").repeat(__.out().where(neq("a"))).emit().select("a").values("test"), Arrays.asList(Arrays.asList(Collections.singleton("a")), Collections.emptySet())}, + Arrays.asList(Arrays.asList(new HashSet<>(Arrays.asList("a", "b", "c"))), Collections.singleton("b"), Collections.emptySet()), null}, + {__.outE().inV().group().by(__.inE().outV().groupCount().by(__.both().count().is(P.gt(2)))), Arrays.asList(), null}, + {__.V().as("a").repeat(__.out().where(neq("a"))).emit().select("a").values("test"), Arrays.asList(Arrays.asList(Collections.singleton("a")), Collections.emptySet()), null}, // given the way this test harness is structured, I have to manual test for RepeatUnrollStrategy (and it works) TODO: add more test parameters // {__.V().as("a").repeat(__.out().where(neq("a"))).times(3).select("a").values("test"), Arrays.asList(Collections.singleton("a"), Collections.singleton("a"), Collections.singleton("a"), Collections.emptySet())} + {__.V().as("a").out().as("b").select("a").out().out(), Arrays.asList(Collections.emptySet()), __.V().as("a").out().as("b").select("a").barrier(MAX_BARRIER_SIZE).out().out()}, + {__.V().as("a").out().as("b").select("a").count(), Arrays.asList(Collections.emptySet()), __.V().as("a").out().as("b").select("a").count()}, + {__.V().as("a").out().as("b").select("a").barrier().count(), Arrays.asList(Collections.emptySet()), __.V().as("a").out().as("b").select("a").barrier().count()}, + {__.V().as("a").out().as("b").where(P.gt("a")).out().out(), Arrays.asList(Collections.emptySet()), __.V().as("a").out().as("b").where(P.gt("a")).barrier(MAX_BARRIER_SIZE).out().out()}, + {__.V().as("a").out().as("b").where(P.gt("a")).count(), Arrays.asList(Collections.emptySet()), __.V().as("a").out().as("b").where(P.gt("a")).count()}, + {__.V().as("a").out().as("b").select("a").as("c").where(P.gt("b")).out(), Arrays.asList(Collections.singleton("b"), Collections.emptySet()), __.V().as("a").out().as("b").select("a").as("c").barrier(MAX_BARRIER_SIZE).where(P.gt("b")).barrier(MAX_BARRIER_SIZE).out()}, }); } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/9d205f89/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java ---------------------------------------------------------------------- diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java index d6dfa9a..90ddc59 100644 --- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java +++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java @@ -29,7 +29,6 @@ import org.apache.tinkerpop.gremlin.structure.Graph; import org.apache.tinkerpop.gremlin.structure.T; import org.apache.tinkerpop.gremlin.structure.Vertex; import org.apache.tinkerpop.gremlin.structure.io.graphml.GraphMLIo; - import org.apache.tinkerpop.gremlin.util.TimeUtil; import org.junit.Ignore; import org.junit.Test; @@ -292,6 +291,7 @@ public class TinkerGraphPlayTest { } @Test + @Ignore public void testBugs() { GraphTraversalSource g = TinkerFactory.createModern().traversal();
