added a butt load more test cases verifying will crazy corner cases.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/989237fd Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/989237fd Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/989237fd Branch: refs/heads/master Commit: 989237fd07a5693121400fe60bb3890c6573543d Parents: f6b6697 Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Thu Jan 26 15:02:05 2017 -0700 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Fri Jan 27 14:24:18 2017 -0700 ---------------------------------------------------------------------- .../optimization/SingleIterationStrategy.java | 22 ++++++++----- .../SingleIterationStrategyTest.java | 34 ++++++++++++++------ .../SparkSingleIterationStrategy.java | 17 +++++----- .../SparkSingleIterationStrategyTest.java | 26 ++++++++++++++- 4 files changed, 73 insertions(+), 26 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/989237fd/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategy.java index efcbe9a..19d9854 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategy.java @@ -29,9 +29,11 @@ import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTrav import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; import org.apache.tinkerpop.gremlin.process.traversal.step.Barrier; import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder; +import org.apache.tinkerpop.gremlin.process.traversal.step.SideEffectCapable; import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; import org.apache.tinkerpop.gremlin.process.traversal.step.branch.LocalStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeVertexStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.LambdaFlatMapStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.LambdaMapStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.VertexStep; @@ -41,6 +43,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.Adja import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.FilterRankingStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.InlineFilterStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; import org.apache.tinkerpop.gremlin.structure.Direction; import org.apache.tinkerpop.gremlin.structure.Graph; @@ -93,22 +96,25 @@ public final class SingleIterationStrategy extends AbstractTraversalStrategy<Tra final boolean beyondStarGraph = TraversalHelper.hasStepOfAssignableClassRecursively(Scope.global, LambdaHolder.class, computerTraversal) || !TraversalHelper.isLocalStarGraph(computerTraversal); - if (!beyondStarGraph && // if we move beyond the star graph, then localization is not possible. - !(computerTraversal.getStartStep().getNextStep() instanceof EmptyStep) && // if its just a g.V()/E(), then don't localize - !(computerTraversal.getStartStep().getNextStep() instanceof LocalStep) && // removes the potential for the infinite recursive application of the traversal - !(computerTraversal.getStartStep().getNextStep() instanceof Barrier) && // if the second step is a barrier, no point in trying to localize anything - !(TraversalHelper.getStepsOfAssignableClass(TraversalParent.class, computerTraversal). // this is a strict precaution that could be loosed with deeper logic on barriers in global children + if (!beyondStarGraph && // if we move beyond the star graph, then localization is not possible. + (computerTraversal.getStartStep() instanceof GraphStep) && // while GraphComputer requires GraphStep starts, this is just a precaution when inject() starts are supported + !(computerTraversal.getStartStep().getNextStep() instanceof EmptyStep) && // if its just a g.V()/E(), then don't localize + !(computerTraversal.getStartStep().getNextStep() instanceof LocalStep) && // removes the potential for the infinite recursive application of the traversal + !(computerTraversal.getStartStep().getNextStep() instanceof Barrier) && // if the second step is a barrier, no point in trying to localize anything + !computerTraversal.getTraverserRequirements().contains(TraverserRequirement.LABELED_PATH) && // this is to alleviate issues with DetachedElement in paths (TODO: when detachment is dynamic, remove this) + !computerTraversal.getTraverserRequirements().contains(TraverserRequirement.PATH) && // this is to alleviate issues with DetachedElement in paths (TODO: when detachment is dynamic, remove this) + TraversalHelper.getStepsOfAssignableClassRecursively(SideEffectCapable.class, computerTraversal).isEmpty() && // this is to alleviate issues with DetachedElement in paths (TODO: when detachment is dynamic, remove this) + !(TraversalHelper.getStepsOfAssignableClass(TraversalParent.class, computerTraversal). // this is a strict precaution that could be loosed with deeper logic on barriers in global children stream(). filter(parent -> !parent.getGlobalChildren().isEmpty()).findAny().isPresent())) { final Traversal.Admin<?, ?> newComputerTraversal = step.computerTraversal.getPure(); final Traversal.Admin localTraversal = new DefaultGraphTraversal<>(); final Step barrier = (Step) TraversalHelper.getFirstStepOfAssignableClass(Barrier.class, newComputerTraversal).orElse(null); - final Step endStep = null == barrier ? newComputerTraversal.getEndStep() : barrier.getPreviousStep(); - if (!(endStep instanceof VertexStep || endStep instanceof EdgeVertexStep)) { + if (null == barrier || !(barrier instanceof TraversalParent && (barrier.getPreviousStep() instanceof VertexStep || barrier.getPreviousStep() instanceof EdgeVertexStep))) { TraversalHelper.removeToTraversal(newComputerTraversal.getStartStep().getNextStep(), null == barrier ? EmptyStep.instance() : barrier, localTraversal); assert !localTraversal.getSteps().isEmpty(); // given the if() constraints, this is impossible - if (localTraversal.getSteps().size() > 1) { // if its just a single step, a local wrap will not alter its locus of computation + if (localTraversal.getSteps().size() > 1) { // if its just a single step, a local wrap will not alter its locus of computation if (null == barrier) TraversalHelper.insertTraversal(0, (Traversal.Admin) __.local(localTraversal), newComputerTraversal); else http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/989237fd/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategyTest.java index 612fb9d..09887f3 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/SingleIterationStrategyTest.java @@ -27,6 +27,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTrav import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy; import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; +import org.apache.tinkerpop.gremlin.structure.Column; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; @@ -35,6 +36,10 @@ import java.util.Arrays; import java.util.Collection; import java.util.Collections; +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.__.out; +import static org.apache.tinkerpop.gremlin.structure.Column.keys; import static org.junit.Assert.assertEquals; /** @@ -77,8 +82,9 @@ public class SingleIterationStrategyTest { {__.V().id(), __.V().id(), Collections.emptyList()}, {__.V().out().count(), __.V().out().count(), Collections.emptyList()}, {__.V().out().label().count(), __.V().out().label().count(), Collections.emptyList()}, - {__.V().in().id(), __.V().local(__.in().id()), Collections.emptyList()}, - {__.V().out().id(), __.V().local(__.out().id()), Collections.emptyList()}, + {__.V().in().id(), __.V().local(in().id()), Collections.emptyList()}, + {in().id(), in().id(), Collections.emptyList()}, // test inject + {__.V().out().id(), __.V().local(out().id()), Collections.emptyList()}, {__.V().both().id(), __.V().local(__.both().id()), Collections.emptyList()}, {__.V().outE().inV().id().count(), __.V().local(__.outE().inV().id()).count(), Collections.emptyList()}, {__.V().map(__.outE().inV()).count(), __.V().map(__.outE().inV()).count(), Collections.emptyList()}, @@ -86,15 +92,25 @@ public class SingleIterationStrategyTest { {__.V().outE().map(__.inV()).id().count(), __.V().outE().map(__.inV()).id().count(), Collections.emptyList()}, {__.V().outE().map(__.inV()).count(), __.V().outE().map(__.inV()).count(), Collections.emptyList()}, {__.V().outE().map(__.inV()).values("name").count(), __.V().outE().map(__.inV()).values("name").count(), Collections.emptyList()}, - {__.V().outE().inV().count(), __.V().outE().inV().count(), Collections.emptyList()}, - {__.V().out().id().count(), __.V().local(__.out().id()).count(), Collections.emptyList()}, - {__.V().in().id().count(), __.V().local(__.in().id()).count(), Collections.emptyList()}, - {__.V().in().id().select("id-map").dedup().count(), __.V().local(__.in().id().select("id-map")).dedup().count(), Collections.emptyList()}, + {__.V().outE().inV().count(), __.V().local(__.outE().inV()).count(), Collections.emptyList()}, + {__.V().out().id().count(), __.V().local(out().id()).count(), Collections.emptyList()}, + {__.V().in().id().count(), __.V().local(in().id()).count(), Collections.emptyList()}, + {__.V().in().id().select("id-map").dedup().count(), __.V().local(in().id().select("id-map")).dedup().count(), Collections.emptyList()}, + {__.V().in().id().groupCount().select(keys).unfold().dedup().count(), __.V().local(in().id()).groupCount().select(keys).unfold().dedup().count(), Collections.emptyList()}, {__.V().outE().values("weight"), __.V().outE().values("weight"), Collections.emptyList()}, {__.V().outE().values("weight").sum(), __.V().outE().values("weight").sum(), Collections.emptyList()}, - {__.V().inE().values("weight"), __.V().local(__.inE().values("weight")), Collections.emptyList()}, - {__.V().inE().values("weight").sum(), __.V().local(__.inE().values("weight")).sum(), Collections.emptyList()}, - {__.V().inE().values("weight").sum().dedup().count(), __.V().local(__.inE().values("weight")).sum().dedup().count(), Collections.emptyList()}, + {__.V().inE().values("weight"), __.V().local(inE().values("weight")), Collections.emptyList()}, + {__.V().inE().values("weight").sum(), __.V().local(inE().values("weight")).sum(), Collections.emptyList()}, + {__.V().inE().values("weight").sum().dedup().count(), __.V().local(inE().values("weight")).sum().dedup().count(), Collections.emptyList()}, + {__.V().as("a").out("knows").as("b").select("a", "b"), __.V().as("a").out("knows").as("b").select("a", "b"), Collections.emptyList()}, + {__.V().out().groupCount("x").cap("x"), __.V().out().groupCount("x").cap("x"), Collections.emptyList()}, + {__.V().outE().inV().groupCount().select(Column.values).unfold().dedup().count(), __.V().outE().inV().groupCount().select(Column.values).unfold().dedup().count(), Collections.emptyList()}, + {__.V().outE().inV().groupCount(), __.V().outE().inV().groupCount(), Collections.emptyList()}, + {__.V().outE().inV().groupCount().by("name"), __.V().outE().inV().groupCount().by("name"), Collections.emptyList()}, + {__.V().inE().id().groupCount(), __.V().local(inE().id()).groupCount(), Collections.emptyList()}, + {__.V().inE().values("weight").groupCount(), __.V().local(inE().values("weight")).groupCount(), Collections.emptyList()}, + {__.V().outE().inV().tree(), __.V().outE().inV().tree(), Collections.emptyList()}, + {__.V().in().values("name").groupCount(), __.V().in().values("name").groupCount(), Collections.emptyList()} }); } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/989237fd/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategy.java ---------------------------------------------------------------------- diff --git a/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategy.java b/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategy.java index 2abb9b8..1288b0d 100644 --- a/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategy.java +++ b/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategy.java @@ -33,14 +33,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.filter.FilterStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeVertexStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.LambdaFlatMapStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.LambdaMapStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.map.SelectOneStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.map.SelectStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.TraversalFlatMapStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.TraversalMapStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.VertexStep; import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SideEffectStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; 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.TraversalHelper; import org.apache.tinkerpop.gremlin.structure.Direction; import org.apache.tinkerpop.gremlin.structure.Graph; @@ -83,7 +82,10 @@ public final class SparkSingleIterationStrategy extends AbstractTraversalStrateg } } } - if (!doesMessagePass && !SparkSingleIterationStrategy.endsWithInElement(computerTraversal)) { + if (!doesMessagePass && + !SparkSingleIterationStrategy.endsWithInElement(computerTraversal) && + !(computerTraversal.getTraverserRequirements().contains(TraverserRequirement.LABELED_PATH) || // todo: remove this when dynamic detachment is available in 3.3.0 + computerTraversal.getTraverserRequirements().contains(TraverserRequirement.PATH))) { // todo: remove this when dynamic detachment is available in 3.3.0 step.setComputer(step.getComputer() // if no message passing, don't partition the loaded graph .configure(Constants.GREMLIN_SPARK_SKIP_PARTITIONER, true) @@ -95,6 +97,9 @@ public final class SparkSingleIterationStrategy extends AbstractTraversalStrateg private static final boolean endsWithInElement(final Traversal.Admin<?, ?> traversal) { Step<?, ?> current = traversal.getEndStep(); + while (current instanceof Barrier) { // clip off any tail barriers + current = current.getPreviousStep(); + } while (!(current instanceof EmptyStep)) { if ((current instanceof VertexStep && (((VertexStep) current).returnsVertex() || !((VertexStep) current).getDirection().equals(Direction.OUT))) || @@ -107,11 +112,7 @@ public final class SparkSingleIterationStrategy extends AbstractTraversalStrateg if (((TraversalParent) current).getGlobalChildren().stream().filter(SparkSingleIterationStrategy::endsWithInElement).findAny().isPresent()) return true; } - if (!(current instanceof FilterStep || - current instanceof SideEffectStep || - current instanceof SelectStep || - current instanceof SelectOneStep || - current instanceof Barrier)) { + if (!(current instanceof FilterStep || current instanceof SideEffectStep)) { // side-effects and filters do not alter the mapping and thus, deeper analysis is required return false; } current = current.getPreviousStep(); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/989237fd/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategyTest.java ---------------------------------------------------------------------- diff --git a/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategyTest.java b/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategyTest.java index 20596d7..b055eb8 100644 --- a/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategyTest.java +++ b/spark-gremlin/src/test/java/org/apache/tinkerpop/gremlin/spark/process/computer/traversal/strategy/optimization/SparkSingleIterationStrategyTest.java @@ -43,6 +43,7 @@ import java.util.List; import java.util.Map; import java.util.UUID; +import static org.apache.tinkerpop.gremlin.structure.Column.keys; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; @@ -127,12 +128,23 @@ public class SparkSingleIterationStrategyTest extends AbstractSparkTest { test(true, 6L, g.V().inE().id().count()); test(true, 6L, g.V().outE().count()); test(true, 4L, g.V().outE().inV().id().dedup().count()); - test(true, 6L, g.V().as("a").outE().inV().as("b").id().dedup("a", "b").by(T.id).count()); test(true, 4L, g.V().filter(__.in()).count()); test(true, 6L, g.V().sideEffect(__.in()).count()); + test(true, 6L, g.V().map(__.constant("hello")).count()); + test(true, g.V().groupCount()); + test(true, g.V().groupCount("x")); + test(true, g.V().groupCount("x").cap("x")); + test(true, g.V().id().groupCount("x").cap("x")); + test(true, g.V().outE().groupCount()); + test(true, g.V().outE().groupCount().by("weight")); + test(true, g.V().inE().id().groupCount()); + test(true, g.V().inE().values("weight").groupCount()); ///// + test(false, 6L, g.V().as("a").outE().inV().as("b").id().dedup("a", "b").by(T.id).count()); test(false, 6L, g.V().local(__.inE()).count()); test(false, 6L, g.V().outE().outV().count()); // todo: low probability traversal, but none the less could be optimized for + test(false, g.V().out().id().groupCount("x")); // todo: low probability traversal, but none the less could be optimized for + test(false, g.V().inE().values("weight").groupCount("x")); // todo: low probability traversal, but none the less could be optimized for test(false, 6L, g.V().in().count()); test(false, 6L, g.V().flatMap(__.in()).count()); test(false, 4L, g.V().map(__.in()).count()); @@ -150,6 +162,18 @@ public class SparkSingleIterationStrategyTest extends AbstractSparkTest { test(false, g.V().out().valueMap()); test(false, 6L, g.V().as("a").outE().inV().values("name").as("b").dedup("a", "b").count()); test(false, 2L, g.V().outE().inV().groupCount().select(Column.values).unfold().dedup().count()); + test(false, g.V().out().groupCount("x")); + test(false, g.V().out().groupCount("x").cap("x")); + test(false, 6L, g.V().both().groupCount("x").cap("x").select(keys).unfold().count()); + test(false, g.V().outE().inV().groupCount()); + test(false, g.V().outE().inV().groupCount().by("name")); + test(false, g.V().outE().inV().tree()); + test(false, g.V().inE().groupCount()); + test(false, g.V().inE().groupCount().by("weight")); + test(false, g.V().in().values("name").groupCount()); + test(false, g.V().out().groupCount("x")); + test(false, g.V().in().groupCount("x")); + test(false, g.V().both().groupCount("x").cap("x")); } private static <R> void test(boolean singleIteration, final Traversal<?, R> traversal) {
