realized that a few traverser species were not super.merge() and thus, not having their tags merged appropriately. this led to weird results in MatchStep when prune strategy was activated. However, this then exposed a massive optimization with PathRetractionStrategy. Some traversers do not have to go down every path. Nutz. As if only some keepLabels are needed, then two traversers down to separate paths can come to the same keepLabel and thus, 'be the same'. Speed ups from 2000ms to 100ms. Will continue to follow this line of reasoning as its a bit scary as bulk counts can be 'difference' (much like MatchStep(OR))...but the result set is always the same.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/8851987b Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/8851987b Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/8851987b Branch: refs/heads/TINKERPOP-1278 Commit: 8851987b8d237008134da6c7503a6aa8a42ab7b1 Parents: 4894b67 Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Tue Jul 12 11:52:39 2016 -0600 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Tue Jul 12 11:52:56 2016 -0600 ---------------------------------------------------------------------- .../process/traversal/step/map/MatchStep.java | 12 +++---- .../traverser/B_LP_O_S_SE_SL_Traverser.java | 34 +++----------------- .../traverser/B_O_S_SE_SL_Traverser.java | 6 ++-- .../traversal/traverser/B_O_Traverser.java | 1 + .../traverser/O_OB_S_SE_SL_Traverser.java | 1 + .../traversal/traverser/O_Traverser.java | 1 - .../structure/TinkerGraphPlayTest.java | 4 +-- 7 files changed, 17 insertions(+), 42 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8851987b/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 6ac1786..a6804de 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 @@ -357,11 +357,10 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> @Override protected Iterator<Traverser.Admin<Map<String, E>>> standardAlgorithm() throws NoSuchElementException { while (true) { - if (this.first) { this.first = false; this.initializeMatchAlgorithm(TraversalEngine.Type.STANDARD); - } else if (this.standardAlgorithmBarrier.isEmpty()) { + } else { // TODO: if(standardAlgorithmBarrier.isEmpty()) -- leads to consistent counts without retracting paths, but orders of magnitude slower. for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) { while (matchTraversal.hasNext() && this.standardAlgorithmBarrier.size() < PathRetractionStrategy.DEFAULT_STANDARD_BARRIER_SIZE) { // TODO: perhaps make MatchStep a LocalBarrierStep ?? @@ -370,7 +369,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } final Traverser.Admin traverser; - if (this.standardAlgorithmBarrier.isEmpty()) { // pull from previous step + 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 @@ -378,7 +377,8 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> 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(); // pull from internal lazy barrier + traverser = this.standardAlgorithmBarrier.remove(); + /// if (!this.isDuplicate(traverser)) { if (hasMatched(this.connective, traverser)) @@ -543,7 +543,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> final Traverser.Admin traverser = this.starts.next(); // no end label if (null == this.matchKey) { - //if (this.traverserStepIdAndLabelsSetByChild) -- traverser equality is based on stepId, lets ensure they are all at the parent + // if (this.traverserStepIdAndLabelsSetByChild) -- traverser equality is based on stepId, lets ensure they are all at the parent traverser.setStepId(this.parent.getId()); this.parent.getMatchAlgorithm().recordEnd(traverser, this.getTraversal()); return this.retractUnnecessaryLabels(traverser); @@ -552,7 +552,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> // 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 equality is based on stepId and thus, lets ensure they are all at the parent + // if (this.traverserStepIdAndLabelsSetByChild) -- traverser equality is based on stepId and thus, lets ensure they are all at the parent traverser.setStepId(this.parent.getId()); traverser.addLabels(this.matchKeyCollection); this.parent.getMatchAlgorithm().recordEnd(traverser, this.getTraversal()); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8851987b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java index ce70c5c..8c66992 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java @@ -108,32 +108,6 @@ public class B_LP_O_S_SE_SL_Traverser<T> extends B_O_S_SE_SL_Traverser<T> { this.path = ImmutablePath.make(); } - - - - /*@Override - public void keepLabels(final Set<String> labels) { - if (!labels.isEmpty()) { - Set<String> retractLabels = new HashSet<>(); - List<Set<String>> existingLabels = this.path.labels(); - for(Set<String> labelSet : existingLabels) { - for(String l : labelSet) { - if(labels.contains(l) == false) { retractLabels.add(l); }; - } - } - this.path = this.path.retract(retractLabels); - } else if (labels.isEmpty()) { - Set<String> retractLabels = new HashSet<>(); - List<Set<String>> existingLabels = this.path.labels(); - for(Set<String> labelSet : existingLabels) { - retractLabels.addAll(labelSet); - } - if(!retractLabels.isEmpty()) { - this.path = this.path.retract(retractLabels); - } - } - }*/ - @Override public int hashCode() { return super.hashCode() + this.path.hashCode(); @@ -142,11 +116,11 @@ public class B_LP_O_S_SE_SL_Traverser<T> extends B_O_S_SE_SL_Traverser<T> { @Override public boolean equals(final Object object) { return (object instanceof B_LP_O_S_SE_SL_Traverser) - && ((B_LP_O_S_SE_SL_Traverser) object).get().equals(this.t) - && ((B_LP_O_S_SE_SL_Traverser) object).getStepId().equals(this.getStepId()) - && ((B_LP_O_S_SE_SL_Traverser) object).loops() == this.loops() + && ((B_LP_O_S_SE_SL_Traverser) object).t.equals(this.t) + && ((B_LP_O_S_SE_SL_Traverser) object).future.equals(this.future) + && ((B_LP_O_S_SE_SL_Traverser) object).loops == this.loops && (null == this.sack || null != this.sideEffects.getSackMerger()) - && ((B_LP_O_S_SE_SL_Traverser) object).path().popEquals(Pop.last, this.path); // this should be Pop.all? + && ((B_LP_O_S_SE_SL_Traverser) object).path.popEquals(Pop.last, this.path); // this should be Pop.all? } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8851987b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_S_SE_SL_Traverser.java index 5dc1313..ab1a783 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_S_SE_SL_Traverser.java @@ -118,9 +118,9 @@ public class B_O_S_SE_SL_Traverser<T> extends B_O_Traverser<T> { @Override public boolean equals(final Object object) { return object instanceof B_O_S_SE_SL_Traverser - && ((B_O_S_SE_SL_Traverser) object).get().equals(this.t) - && ((B_O_S_SE_SL_Traverser) object).getStepId().equals(this.getStepId()) - && ((B_O_S_SE_SL_Traverser) object).loops() == this.loops() + && ((B_O_S_SE_SL_Traverser) object).t.equals(this.t) + && ((B_O_S_SE_SL_Traverser) object).future.equals(this.future) + && ((B_O_S_SE_SL_Traverser) object).loops == this.loops && (null == this.sack || (null != this.sideEffects && null != this.sideEffects.getSackMerger())); // hmmm... serialization in OLAP destroys the transient sideEffects } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8851987b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_Traverser.java index 4c64fb0..4a66ab1 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_O_Traverser.java @@ -48,6 +48,7 @@ public class B_O_Traverser<T> extends O_Traverser<T> { @Override public void merge(final Traverser.Admin<?> other) { + super.merge(other); this.bulk = this.bulk + other.bulk(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8851987b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_OB_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_OB_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_OB_S_SE_SL_Traverser.java index 7196e72..1ed5ad9 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_OB_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_OB_S_SE_SL_Traverser.java @@ -115,6 +115,7 @@ public class O_OB_S_SE_SL_Traverser<T> extends O_Traverser<T> { @Override public void merge(final Traverser.Admin<?> other) { + super.merge(other); if (null != this.sack && null != this.sideEffects.getSackMerger()) this.sack = this.sideEffects.getSackMerger().apply(this.sack, other.sack()); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8851987b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java index 2671a91..e9735b0 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java @@ -63,7 +63,6 @@ public abstract class O_Traverser<T> extends AbstractTraverser<T> { @Override public void merge(final Traverser.Admin<?> other) { - super.merge(other); if (!other.getTags().isEmpty()) { if (this.tags == null) this.tags = new HashSet<>(); this.tags.addAll(other.getTags()); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/8851987b/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 3554b34..abe6195 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 @@ -76,9 +76,9 @@ public class TinkerGraphPlayTest { for (final GraphTraversalSource source : Arrays.asList(d, c, b, a)) { System.out.println(source + "--PathRetractionStrategy[" + source.getStrategies().toList().contains(PathRetractionStrategy.instance()) + "]"); - System.out.println(TimeUtil.clockWithResult(2, () -> source.V().match( + System.out.println(source.V().match( __.as("a").out().as("b"), - __.as("a").both().as("c")).select("a").count().next())); + __.as("a").in().as("c")).select("a").profile().next()); } }
