added a lazy barrier to OLTP MatchStep (added a TODO note that in the future we may want to make MatchStep a LocalBarrierStep). Tweaked up the OLTP PrunePathStrategy optimization to only do lazy barriers if the parent is NOT a MatchStep (as the MatchStep is a lazy barrier now). Lightened up the IdentityRemoveStrategy sensitivty as recommended by @tdwilmes ... Epic stuff.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/983538d7 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/983538d7 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/983538d7 Branch: refs/heads/TINKERPOP-1278 Commit: 983538d75d55150d5290492cf386eb46ad95db55 Parents: 43c6108 Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Sun Jul 10 12:48:06 2016 -0600 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Sun Jul 10 12:48:06 2016 -0600 ---------------------------------------------------------------------- .../process/traversal/step/map/MatchStep.java | 22 +++++++----- .../optimization/PrunePathStrategy.java | 14 ++++---- .../process/traversal/util/PathUtil.java | 14 +++++--- .../IdentityRemovalStrategyTest.java | 2 +- .../optimization/PrunePathStrategyTest.java | 13 ++++---- .../structure/TinkerGraphPlayTest.java | 35 ++++++++------------ 6 files changed, 52 insertions(+), 48 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/983538d7/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java index 6983bd1..813b85c 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java @@ -38,7 +38,9 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.ComputerAwareSte import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.ReducingBarrierStep; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConnectiveStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PrunePathStrategy; import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet; import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal; import org.apache.tinkerpop.gremlin.process.traversal.util.PathUtil; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; @@ -313,28 +315,33 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> return false; } + private final TraverserSet standardAlgorithmBarrier = new TraverserSet(); + @Override protected Iterator<Traverser.Admin<Map<String, E>>> standardAlgorithm() throws NoSuchElementException { while (true) { - Traverser.Admin traverser = null; + if (this.first) { this.first = false; this.initializeMatchAlgorithm(TraversalEngine.Type.STANDARD); - } else { + } else if (this.standardAlgorithmBarrier.isEmpty()) { for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) { - if (matchTraversal.hasNext()) { - traverser = matchTraversal.getEndStep().next(); - break; + while (matchTraversal.hasNext() && + this.standardAlgorithmBarrier.size() < PrunePathStrategy.MAX_BARRIER_SIZE) { // TODO: perhaps make MatchStep a LocalBarrierStep ?? + this.standardAlgorithmBarrier.add(matchTraversal.getEndStep().next()); } } } - if (null == traverser) { + final Traverser.Admin traverser; + if (this.standardAlgorithmBarrier.isEmpty()) { traverser = this.starts.next(); if (!traverser.getTags().contains(this.getId())) { traverser.getTags().add(this.getId()); // so the traverser never returns to this branch ever again if (!this.hasPathLabel(traverser.path(), this.matchStartLabels)) traverser.addLabels(Collections.singleton(this.computedStartLabel)); // if the traverser doesn't have a legal start, then provide it the pre-computed one } + } else { + traverser = this.standardAlgorithmBarrier.remove(); } /// if (!this.isDuplicate(traverser)) { @@ -499,7 +506,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> MatchStep parent = ((MatchStep) this.getTraversal().getParent().asStep()); if (null != parent.getKeepLabels()) { final Set<String> keepers = new HashSet<>(); - for (final Traversal.Admin<?, ?> traversal : (List<Traversal.Admin<?, ?>>)parent.getRemainingTraversals(traverser)) { + for (final Traversal.Admin<?, ?> traversal : (List<Traversal.Admin<?, ?>>) parent.getRemainingTraversals(traverser)) { keepers.addAll(PathUtil.getReferencedLabels(traversal)); } keepers.addAll(parent.getKeepLabels()); @@ -511,7 +518,6 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> protected Traverser.Admin<Object> processNextStart() throws NoSuchElementException { - while (true) { final Traverser.Admin traverser = this.starts.next(); // no end label http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/983538d7/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 efd2949..b8a5b39 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 @@ -38,17 +38,16 @@ import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashSet; -import java.util.LinkedHashMap; import java.util.List; -import java.util.Map; import java.util.Set; /** * @author Ted Wilmes (http://twilmes.org) + * @author Marko A. Rodriguez (http://markorodriguez.com) */ public final class PrunePathStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy { - public static Integer MAX_BARRIER_SIZE = 1000; + public static Integer MAX_BARRIER_SIZE = 2500; private static final PrunePathStrategy INSTANCE = new PrunePathStrategy(); // these strategies do strong rewrites involving path labeling and thus, should run prior to PrunePathStrategy @@ -74,7 +73,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal final boolean hasPathStep = TraversalHelper.anyStepRecursively(step -> step.getRequirements().contains(TraverserRequirement.PATH), traversal); if (hasPathStep) { for (final Step<?, ?> step : traversal.getSteps()) { - if(step instanceof PathProcessor) { + if (step instanceof PathProcessor) { ((PathProcessor) step).setKeepLabels(null); } } @@ -104,7 +103,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal } else ((PathProcessor) currentStep).setKeepLabels(new HashSet<>(keepLabels)); - if (currentStep.getTraversal().getParent().asStep() instanceof MatchStep) { + if (currentStep.getTraversal().getParent() instanceof MatchStep) { pathProcessor.setKeepLabels(((MatchStep) currentStep.getTraversal().getParent().asStep()).getMatchStartLabels()); pathProcessor.getKeepLabels().addAll(((MatchStep) currentStep.getTraversal().getParent().asStep()).getMatchEndLabels()); } @@ -112,7 +111,8 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal // 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)) + !(currentStep.getNextStep() instanceof NoOpBarrierStep) && + !(currentStep.getTraversal().getParent() instanceof MatchStep)) TraversalHelper.insertAfterStep(new NoOpBarrierStep<>(traversal, MAX_BARRIER_SIZE), currentStep, traversal); } } @@ -123,7 +123,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal Step<?, ?> parent = traversal.getParent().asStep(); final List<Pair<Step, Set<String>>> parentKeeperPairs = new ArrayList<>(); while (!parent.equals(EmptyStep.instance())) { - parentKeeperPairs.add(new Pair<>(parent, PathUtil.whichLabelsReferencedFromHereForward(parent, foundLabels))); + parentKeeperPairs.add(new Pair<>(parent, PathUtil.whichLabelsReferencedFromHereForward(parent))); parent = parent.getTraversal().getParent().asStep(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/983538d7/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 87ecc9e..64e418f 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 @@ -35,12 +35,16 @@ import java.util.Set; */ public class PathUtil { + private PathUtil() { + // static public methods only + } + public static Set<String> getReferencedLabelsAfterStep(Step<?, ?> step) { - if(step.getNextStep().equals(EmptyStep.instance())) { + if (step.getNextStep().equals(EmptyStep.instance())) { return Collections.emptySet(); } final Set<String> labels = new HashSet<>(); - while(!(step = step.getNextStep()).equals(EmptyStep.instance())) { + while (!(step = step.getNextStep()).equals(EmptyStep.instance())) { labels.addAll(PathUtil.getReferencedLabels(step)); } return labels; @@ -54,11 +58,11 @@ public class PathUtil { return referencedLabels; } - public static Set<String> whichLabelsReferencedFromHereForward(Step<?, ?> step, final Set<String> labels) { + public static Set<String> whichLabelsReferencedFromHereForward(Step<?, ?> step) { final Set<String> found = new HashSet<>(); - while(!step.equals(EmptyStep.instance())) { + while (!step.equals(EmptyStep.instance())) { final Set<String> referencedLabels = getReferencedLabels(step); - for(final String refLabel : referencedLabels) { + for (final String refLabel : referencedLabels) { found.add(refLabel); } step = step.getNextStep(); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/983538d7/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java index 065dc53..b14798e 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java @@ -95,7 +95,7 @@ public class IdentityRemovalStrategyTest { return new Iterator<GraphTraversal>() { - final int minIdentities = 3; + final int minIdentities = 5; final int maxIdentities = 10; final Integer[] starts = IntStream.range(0, 1000).boxed().toArray(Integer[]::new); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/983538d7/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 97c6f50..44cc333 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 @@ -51,6 +51,7 @@ import static org.junit.Assert.assertEquals; /** * @author Ted Wilmes (http://twilmes.org) + * @author Marko A. Rodriguez (http://markorodriguez.com) */ @RunWith(Parameterized.class) public class PrunePathStrategyTest { @@ -166,16 +167,16 @@ public class PrunePathStrategyTest { {__.V().select("a").map(select("c").map(select("b"))).select("c"), "[[b, c], [[b, c], [[c]]], []]", null}, {__.V().select("a").map(select("b").repeat(select("c"))).select("a"), - "[[a, b, c], [[a, c], [[a, c]]], []]", null}, + "[[a, b, c], [[a, c], [[a, c]]], []]", null}, {__.V().select("c").map(select("c").map(select("c"))).select("c"), "[[c], [[c], [[c]]], []]", null}, {__.V().select("c").map(select("c").map(select("c"))).select("b"), "[[b, c], [[b, c], [[b]]], []]", null}, - {__.V().select("a").map(select("c").map(select("b"))).select("c"), + {__.V().select("a").map(select("c").map(select("b"))).select("c"), "[[b, c], [[b, c], [[c]]], []]", null}, - {__.V().select("a").map(select("b").repeat(select("c"))).select("a"), - "[[a, b, c], [[a, c], [[a, c]]], []]", null}, - {__.V().out("created").project("a","b").by("name").by(__.in("created").count()).order().by(select("b")).select("a"), "[[[a]], []]", null}, + {__.V().select("a").map(select("b").repeat(select("c"))).select("a"), + "[[a, b, c], [[a, c], [[a, c]]], []]", null}, + {__.V().out("created").project("a", "b").by("name").by(__.in("created").count()).order().by(select("b")).select("a"), "[[[a]], []]", null}, {__.order().by("weight", Order.decr).store("w").by("weight").filter(values("weight").as("cw"). - select("w").by(limit(Scope.local, 1)).as("mw").where("cw", eq("mw"))).project("from","to","weight").by(__.outV()).by(__.inV()).by("weight"), + select("w").by(limit(Scope.local, 1)).as("mw").where("cw", eq("mw"))).project("from", "to", "weight").by(__.outV()).by(__.inV()).by("weight"), "[[[cw, mw], []]]", null} }); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/983538d7/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 e6a6c85..5bf3c48 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 @@ -31,7 +31,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; @@ -39,15 +38,11 @@ import org.slf4j.Logger; import org.slf4j.LoggerFactory; import java.util.Arrays; -import java.util.Comparator; import java.util.List; import java.util.function.Supplier; -import static org.apache.tinkerpop.gremlin.process.traversal.P.eq; -import static org.apache.tinkerpop.gremlin.process.traversal.P.gte; import static org.apache.tinkerpop.gremlin.process.traversal.P.lt; import static org.apache.tinkerpop.gremlin.process.traversal.P.neq; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.and; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.as; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.both; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.choose; @@ -60,7 +55,6 @@ import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.outE; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.select; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.union; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.valueMap; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.where; /** * @author Stephen Mallette (http://stephen.genoprime.com) @@ -71,23 +65,22 @@ public class TinkerGraphPlayTest { @Test @Ignore public void testPlay8() throws Exception { - Graph graph = TinkerFactory.createModern(); - GraphTraversalSource g = graph.traversal().withComputer();//GraphTraversalSource.computer()); - //System.out.println(g.V().outE("knows").identity().inV().count().is(P.eq(5)).explain()); - //System.out.println(g.V().hasLabel("person").fold().order(Scope.local).by("age").toList()); - //System.out.println(g.V().repeat(out()).times(2).profile("m").explain()); - final Traversal<?, ?> traversal = g.V().hasLabel("person").<Number>project("a", "b").by(__.outE().count()).by("age"); - System.out.println(traversal.explain()); - //System.out.println(g.V().hasLabel("person").pageRank().by("rank").by(bothE()).values("rank").profile("m").explain()); - //System.out.println(traversal.asAdmin().clone().toString()); - // final Traversal<?,?> clone = traversal.asAdmin().clone(); - // clone.asAdmin().applyStrategies(); - // System.out.println(clone); - System.out.println(traversal.asAdmin().toList()); - //System.out.println(traversal.asAdmin().getSideEffects().get("m") + " "); - //System.out.println(g.V().pageRank().order().by(PageRankVertexProgram.PAGE_RANK).valueMap().toList()); + Graph graph = TinkerGraph.open(); + graph.io(GraphMLIo.build()).readGraph("../data/grateful-dead.xml"); + //Graph graph = TinkerFactory.createModern(); + + GraphTraversalSource g = graph.traversal().withStrategies(PrunePathStrategy.instance()); + GraphTraversalSource h = graph.traversal().withoutStrategies(PrunePathStrategy.class); + + for (final GraphTraversalSource source : Arrays.asList(h, g)) { + System.out.println(source.V().match( + __.as("a").out().as("b"), + __.as("b").out().as("c"), + __.as("c").out().as("d")).select("d").count().profile().next()); + } } + @Test @Ignore public void benchmarkGroup() throws Exception {
