using memoization in MatchEndStep so referenced labels don't need to be computed over and over again. Simplified PathUtil -- removed two methods that are now inlined.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/b900de27 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/b900de27 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/b900de27 Branch: refs/heads/master Commit: b900de27546d7a10263a34808301726cb3f48fca Parents: 632a67d Author: Marko A. Rodriguez <[email protected]> Authored: Mon Jul 11 12:11:41 2016 -0600 Committer: Marko A. Rodriguez <[email protected]> Committed: Mon Jul 11 12:11:41 2016 -0600 ---------------------------------------------------------------------- .../process/traversal/step/PathProcessor.java | 13 +--- .../process/traversal/step/map/MatchStep.java | 66 ++++++++++---------- .../optimization/PathRetractionStrategy.java | 4 +- .../process/traversal/util/PathUtil.java | 27 +------- .../neo4j/process/NativeNeo4jCypherCheck.java | 4 +- 5 files changed, 40 insertions(+), 74 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java index 8ad5181..0c8ed47 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java @@ -65,18 +65,7 @@ public interface PathProcessor { public Set<String> getKeepLabels(); public static <S> Traverser.Admin<S> processTraverserPathLabels(final Traverser.Admin<S> traverser, final Set<String> labels) { - if (null != labels) - traverser.keepLabels(labels); + if (null != labels) traverser.keepLabels(labels); return traverser; } - - static void keepLabels(final Traverser traverser, final Set<String> labels) { - if(labels == null) { - return; - } else { - traverser.asAdmin().keepLabels(labels); - } - } - - } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/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 998b7d3..e1f6d8f 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 @@ -351,16 +351,15 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } final Traverser.Admin traverser; - if (this.standardAlgorithmBarrier.isEmpty()) { + if (this.standardAlgorithmBarrier.isEmpty()) { // pull from previous step 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(); - } + } else + traverser = this.standardAlgorithmBarrier.remove(); // pull from internal lazy barrier /// if (!this.isDuplicate(traverser)) { if (hasMatched(this.connective, traverser)) @@ -424,18 +423,8 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> final Set<String> tags = traverser.getTags(); final List<Traversal.Admin<?, ?>> remainingTraversals = new ArrayList<>(); for (final Traversal.Admin<?, ?> matchTraversal : matchTraversals) { - if (!tags.contains(matchTraversal.getStartStep().getId())) { + if (!tags.contains(matchTraversal.getStartStep().getId())) remainingTraversals.add(matchTraversal); - } /*else { - // include the current traversal that the traverser is executing in the list of - // remaining traversals - for (final Step<?, ?> s : matchTraversal.getSteps()) { - if (s.getId().equals(traverser.getStepId())) { - remainingTraversals.add(matchTraversal); - break; - } - } - } */ } return remainingTraversals; } @@ -461,7 +450,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> ////////////////////////////// - public static class MatchStartStep extends AbstractStep<Object, Object> implements Scoping { + public static final class MatchStartStep extends AbstractStep<Object, Object> implements Scoping { private final String selectKey; private Set<String> scopeKeys = null; @@ -510,9 +499,12 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } - public static class MatchEndStep extends EndStep<Object> { + public static final class MatchEndStep extends EndStep<Object> { private final String matchKey; + // memoization of referenced labels Map<startStepId, referencedLabels> + private final Map<String, Set<String>> referencedLabelsMap = new HashMap<>(); + private MatchStep<?, ?> parent = null; public MatchEndStep(final Traversal.Admin traversal, final String matchKey) { super(traversal); @@ -520,42 +512,48 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } - private void retractUnnecessaryLabels(final Traverser.Admin<Object> traverser) { - 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)) { - keepers.addAll(PathUtil.getReferencedLabels(traversal)); + private <S> Traverser.Admin<S> retractUnnecessaryLabels(final Traverser.Admin<S> traverser) { + if (null == this.parent.getKeepLabels()) + return traverser; + + final Set<String> keepers = new HashSet<>(this.parent.getKeepLabels()); + for (final Traversal.Admin<?, ?> traversal : this.parent.getRemainingTraversals(traverser)) { + Set<String> referencedLabels = this.referencedLabelsMap.get(traversal.getStartStep().getId()); + if (null == referencedLabels) { + referencedLabels = new HashSet<>(); + for (final Step<?, ?> step : traversal.getSteps()) { + referencedLabels.addAll(PathUtil.getReferencedLabels(step)); + } + this.referencedLabelsMap.put(traversal.getStartStep().getId(), referencedLabels); } - keepers.addAll(parent.getKeepLabels()); - PathProcessor.processTraverserPathLabels(traverser, keepers); + keepers.addAll(referencedLabels); } + return PathProcessor.processTraverserPathLabels(traverser, keepers); } @Override protected Traverser.Admin<Object> processNextStart() throws NoSuchElementException { - + if (null == this.parent) + this.parent = ((MatchStep) this.getTraversal().getParent().asStep()); while (true) { final Traverser.Admin traverser = this.starts.next(); // no end label if (null == this.matchKey) { if (this.traverserStepIdAndLabelsSetByChild) - traverser.setStepId(((MatchStep<?, ?>) this.getTraversal().getParent()).getId()); - ((MatchStep<?, ?>) this.getTraversal().getParent()).getMatchAlgorithm().recordEnd(traverser, this.getTraversal()); - retractUnnecessaryLabels(traverser); - return traverser; + traverser.setStepId(this.parent.getId()); + this.parent.getMatchAlgorithm().recordEnd(traverser, this.getTraversal()); + return this.retractUnnecessaryLabels(traverser); } // TODO: sideEffect check? // path check final Path path = traverser.path(); if (!path.hasLabel(this.matchKey) || traverser.get().equals(path.get(Pop.last, this.matchKey))) { if (this.traverserStepIdAndLabelsSetByChild) - traverser.setStepId(((MatchStep<?, ?>) this.getTraversal().getParent()).getId()); + traverser.setStepId(this.parent.getId()); traverser.addLabels(Collections.singleton(this.matchKey)); - ((MatchStep<?, ?>) this.getTraversal().getParent()).getMatchAlgorithm().recordEnd(traverser, this.getTraversal()); - retractUnnecessaryLabels(traverser); - return traverser; + this.parent.getMatchAlgorithm().recordEnd(traverser, this.getTraversal()); + return this.retractUnnecessaryLabels(traverser); } } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java index 2ff22ba..a85b752 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java @@ -120,7 +120,9 @@ public final class PathRetractionStrategy extends AbstractTraversalStrategy<Trav 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))); + Set<String> parentKeepLabels = new HashSet<>(PathUtil.getReferencedLabels(parent)); + parentKeepLabels.addAll(PathUtil.getReferencedLabelsAfterStep(parent)); + parentKeeperPairs.add(new Pair<>(parent, parentKeepLabels)); parent = parent.getTraversal().getParent().asStep(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/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 64e418f..ab97836 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 @@ -26,7 +26,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters; -import java.util.Collections; import java.util.HashSet; import java.util.Set; @@ -40,34 +39,12 @@ public class PathUtil { } public static Set<String> getReferencedLabelsAfterStep(Step<?, ?> step) { - if (step.getNextStep().equals(EmptyStep.instance())) { - return Collections.emptySet(); - } final Set<String> labels = new HashSet<>(); - while (!(step = step.getNextStep()).equals(EmptyStep.instance())) { + while (!(step instanceof EmptyStep)) { labels.addAll(PathUtil.getReferencedLabels(step)); - } - return labels; - } - - public static Set<String> getReferencedLabels(final Traversal.Admin<?, ?> traversal) { - final Set<String> referencedLabels = new HashSet<>(); - for (final Step<?, ?> step : traversal.getSteps()) { - referencedLabels.addAll(getReferencedLabels(step)); - } - return referencedLabels; - } - - public static Set<String> whichLabelsReferencedFromHereForward(Step<?, ?> step) { - final Set<String> found = new HashSet<>(); - while (!step.equals(EmptyStep.instance())) { - final Set<String> referencedLabels = getReferencedLabels(step); - for (final String refLabel : referencedLabels) { - found.add(refLabel); - } step = step.getNextStep(); } - return found; + return labels; } public static Set<String> getReferencedLabels(final Step step) { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java ---------------------------------------------------------------------- diff --git a/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java b/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java index 390c749..a758eea 100644 --- a/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java +++ b/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java @@ -199,8 +199,8 @@ public class NativeNeo4jCypherCheck extends AbstractNeo4jGremlinTest { () -> n.cypher("MATCH (a)<-[:writtenBy]-(b), (b)-[:followedBy]->(c), (c)-[:writtenBy]->(d) WHERE a <> d AND a.name = 'Garcia' AND 'artist' IN labels(a) RETURN a.name, d.name"), /// () -> g.V().match( - as("a").out("followed").as("b"), - as("b").out("followed").as("c")).select("a").by("name"), + as("a").out("followedBy").as("b"), + as("b").out("followedBy").as("c")).select("a").by("name"), () -> n.cypher("MATCH ((a)-[:followedBy]->(b), (b)-[:followedBy]->(c) RETURN a.name") /// /*() -> g.V().match(
