tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From spmalle...@apache.org
Subject [1/6] incubator-tinkerpop git commit: MatchStep is smart to bias patterns towards the local star graph to reduce inter-machine communication.
Date Wed, 04 Nov 2015 18:13:31 GMT
Repository: incubator-tinkerpop
Updated Branches:
  refs/heads/TINKERPOP3-913 180a6cb22 -> 986bc7017


MatchStep is smart to bias patterns towards the local star graph to reduce inter-machine communication.


Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/956d7977
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/956d7977
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/956d7977

Branch: refs/heads/TINKERPOP3-913
Commit: 956d7977f4507db8d51b0468604f3b214e0681b3
Parents: aadd422
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Tue Nov 3 09:16:39 2015 -0700
Committer: Marko A. Rodriguez <okrammarko@gmail.com>
Committed: Tue Nov 3 09:16:39 2015 -0700

----------------------------------------------------------------------
 .../process/traversal/step/map/MatchStep.java   | 48 ++++++++----
 .../traversal/step/map/MatchStepTest.java       | 82 +++++++++++++++++++-
 2 files changed, 115 insertions(+), 15 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/956d7977/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 724ab8a..1ed202f 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
@@ -22,6 +22,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Path;
 import org.apache.tinkerpop.gremlin.process.traversal.Pop;
 import org.apache.tinkerpop.gremlin.process.traversal.Step;
 import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalEngine;
 import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
 import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
@@ -64,8 +65,9 @@ import java.util.stream.Stream;
  */
 public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
implements TraversalParent, Scoping {
 
-    public static enum TraversalType {WHERE_PREDICATE, WHERE_TRAVERSAL, MATCH_TRAVERSAL}
+    public enum TraversalType {WHERE_PREDICATE, WHERE_TRAVERSAL, MATCH_TRAVERSAL}
 
+    private TraversalEngine.Type traversalEngineType;
     private List<Traversal.Admin<Object, Object>> matchTraversals = new ArrayList<>();
     private boolean first = true;
     private Set<String> matchStartLabels = new HashSet<>();
@@ -153,6 +155,12 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
         }
     }
 
+    @Override
+    public void onEngine(final TraversalEngine engine) {
+        super.onEngine(engine);
+        this.traversalEngineType = engine.getType();
+    }
+
     public ConnectiveStep.Connective getConnective() {
         return this.connective;
     }
@@ -216,7 +224,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
             clone.matchTraversals.add(clone.integrateChild(traversal.clone()));
         }
         if (this.dedups != null) clone.dedups = new HashSet<>();
-        clone.initializeMatchAlgorithm();
+        clone.initializeMatchAlgorithm(this.traversalEngineType);
         return clone;
     }
 
@@ -281,13 +289,13 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
         return bindings;
     }
 
-    private void initializeMatchAlgorithm() {
+    private void initializeMatchAlgorithm(final TraversalEngine.Type traversalEngineType)
{
         try {
             this.matchAlgorithm = this.matchAlgorithmClass.getConstructor().newInstance();
         } catch (final NoSuchMethodException | IllegalAccessException | InvocationTargetException
| InstantiationException e) {
             throw new IllegalStateException(e.getMessage(), e);
         }
-        this.matchAlgorithm.initialize(this.matchTraversals);
+        this.matchAlgorithm.initialize(traversalEngineType, this.matchTraversals);
     }
 
     @Override
@@ -296,7 +304,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
             Traverser.Admin traverser = null;
             if (this.first) {
                 this.first = false;
-                this.initializeMatchAlgorithm();
+                this.initializeMatchAlgorithm(this.traversalEngineType);
             } else {
                 for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals)
{
                     if (matchTraversal.hasNext()) {
@@ -420,7 +428,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
                 if (null != this.selectKey)
                     this.scopeKeys.add(this.selectKey);
                 if (this.getNextStep() instanceof WhereTraversalStep || this.getNextStep()
instanceof WherePredicateStep)
-                   this.scopeKeys.addAll(((Scoping) this.getNextStep()).getScopeKeys());
+                    this.scopeKeys.addAll(((Scoping) this.getNextStep()).getScopeKeys());
                 this.scopeKeys = Collections.unmodifiableSet(this.scopeKeys);
             }
             return this.scopeKeys;
@@ -555,7 +563,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
         public static Function<List<Traversal.Admin<Object, Object>>, IllegalStateException>
UNMATCHABLE_PATTERN = traversals -> new IllegalStateException("The provided match pattern
is unsolvable: " + traversals);
 
 
-        public void initialize(final List<Traversal.Admin<Object, Object>> traversals);
+        public void initialize(final TraversalEngine.Type traversalEngineType, final List<Traversal.Admin<Object,
Object>> traversals);
 
         public default void recordStart(final Traverser.Admin<Object> traverser, final
Traversal.Admin<Object, Object> traversal) {
 
@@ -571,7 +579,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
         private List<Traversal.Admin<Object, Object>> traversals;
 
         @Override
-        public void initialize(final List<Traversal.Admin<Object, Object>> traversals)
{
+        public void initialize(final TraversalEngine.Type traversalEngineType, final List<Traversal.Admin<Object,
Object>> traversals) {
             this.traversals = traversals;
         }
 
@@ -589,14 +597,26 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
 
         protected List<Bundle> bundles;
         protected int counter = 0;
+        protected boolean onComputer;
 
-        @Override
-        public void initialize(final List<Traversal.Admin<Object, Object>> traversals)
{
+        public void initialize(final TraversalEngine.Type traversalEngineType, final List<Traversal.Admin<Object,
Object>> traversals) {
+            this.onComputer = traversalEngineType.equals(TraversalEngine.Type.COMPUTER);
             this.bundles = traversals.stream().map(Bundle::new).collect(Collectors.toList());
         }
 
         @Override
         public Traversal.Admin<Object, Object> apply(final Traverser.Admin<Object>
traverser) {
+            // optimization to favor processing StarGraph local objects first to limit message
passing (GraphComputer only)
+            // TODO: generalize this for future MatchAlgorithms (given that 3.2.0 will focus
on RealTimeStrategy, it will probably go there)
+            if (this.onComputer) {
+                final List<Set<String>> labels = traverser.path().labels();
+                final Set<String> lastLabels = labels.get(labels.size() - 1);
+                Collections.sort(this.bundles,
+                        Comparator.<Bundle>comparingLong(b -> Helper.getStartLabels(b.traversal).stream().filter(startLabel
-> !lastLabels.contains(startLabel)).count()).
+                                thenComparingInt(b -> b.traversalType.ordinal()).
+                                thenComparingDouble(b -> b.multiplicity));
+            }
+
             Bundle startLabelsBundle = null;
             for (final Bundle bundle : this.bundles) {
                 if (!Helper.hasExecutedTraversal(traverser, bundle.traversal) &&
Helper.hasStartLabels(traverser, bundle.traversal)) {
@@ -618,9 +638,11 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
         @Override
         public void recordEnd(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object,
Object> traversal) {
             this.getBundle(traversal).incrementEndCount();
-            if (this.counter < 200 || this.counter % 250 == 0) // aggressively sort for
the first 200 results -- after that, sort every 250
-                Collections.sort(this.bundles, Comparator.<Bundle>comparingInt(b ->
b.traversalType.ordinal()).thenComparingDouble(b -> b.multiplicity));
-            this.counter++;
+            if (!this.onComputer) {  // if on computer, sort on a per traverser-basis with
bias towards local star graph
+                if (this.counter < 200 || this.counter % 250 == 0) // aggressively sort
for the first 200 results -- after that, sort every 250
+                    Collections.sort(this.bundles, Comparator.<Bundle>comparingInt(b
-> b.traversalType.ordinal()).thenComparingDouble(b -> b.multiplicity));
+                this.counter++;
+            }
         }
 
         protected Bundle getBundle(final Traversal.Admin<Object, Object> traversal)
{

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/956d7977/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
index 9c7cef1..529e717 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
@@ -20,19 +20,25 @@ package org.apache.tinkerpop.gremlin.process.traversal.step.map;
 
 import org.apache.tinkerpop.gremlin.process.traversal.P;
 import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalEngine;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
 import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
 import org.apache.tinkerpop.gremlin.process.traversal.step.StepTest;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.CoinStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.ConnectiveStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WherePredicateStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereTraversalStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_LP_O_P_S_SE_SL_TraverserGenerator;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.EmptyTraverser;
 import org.apache.tinkerpop.gremlin.structure.T;
 import org.junit.Test;
 
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.HashSet;
 import java.util.List;
+import java.util.function.Consumer;
 
 import static org.apache.tinkerpop.gremlin.process.traversal.P.eq;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.*;
@@ -186,7 +192,7 @@ public class MatchStepTest extends StepTest {
         // MAKE SURE THE SORT ORDER CHANGES AS MORE RESULTS ARE RETURNED BY ONE OR THE OTHER
TRAVERSAL
         Traversal.Admin<?, ?> traversal = __.match(as("a").out().as("b"), as("c").in().as("d")).asAdmin();
         MatchStep.CountMatchAlgorithm countMatchAlgorithm = new MatchStep.CountMatchAlgorithm();
-        countMatchAlgorithm.initialize(((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren());
+        countMatchAlgorithm.initialize(TraversalEngine.Type.STANDARD, ((MatchStep<?, ?>)
traversal.getStartStep()).getGlobalChildren());
         Traversal.Admin<Object, Object> firstPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(0);
         Traversal.Admin<Object, Object> secondPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(1);
         //
@@ -232,7 +238,7 @@ public class MatchStepTest extends StepTest {
         ///////  MAKE SURE WHERE PREDICATE TRAVERSALS ARE ALWAYS FIRST AS THEY ARE SIMPLY
.hasNext() CHECKS
         traversal = __.match(as("a").out().as("b"), as("c").in().as("d"), where("a", P.eq("b"))).asAdmin();
         countMatchAlgorithm = new MatchStep.CountMatchAlgorithm();
-        countMatchAlgorithm.initialize(((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren());
+        countMatchAlgorithm.initialize(TraversalEngine.Type.STANDARD, ((MatchStep<?, ?>)
traversal.getStartStep()).getGlobalChildren());
         assertEquals(3, countMatchAlgorithm.bundles.size());
         firstPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(0);
         secondPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(1);
@@ -307,6 +313,78 @@ public class MatchStepTest extends StepTest {
     }
 
     @Test
+    public void testComputerAwareCountMatchAlgorithm() {
+        // MAKE SURE THE SORT ORDER CHANGES AS MORE RESULTS ARE RETURNED BY ONE OR THE OTHER
TRAVERSAL
+        final Consumer doNothing = s -> {
+        };
+        Traversal.Admin<?, ?> traversal = __.match(
+                as("a").sideEffect(doNothing).as("b"),    // 1
+                as("b").sideEffect(doNothing).as("c"),    // 2
+                as("a").sideEffect(doNothing).as("d"),    // 5
+                as("c").sideEffect(doNothing).as("e"),    // 4
+                as("c").sideEffect(doNothing).as("f"))    // 3
+                .asAdmin();
+        traversal.applyStrategies(); // necessary to enure step ids are unique
+        MatchStep.CountMatchAlgorithm countMatchAlgorithm = new MatchStep.CountMatchAlgorithm();
+        countMatchAlgorithm.initialize(TraversalEngine.Type.COMPUTER, ((MatchStep<?, ?>)
traversal.getStartStep()).getGlobalChildren());
+        Traversal.Admin<Object, Object> firstPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(0);
+        Traversal.Admin<Object, Object> secondPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(1);
+        Traversal.Admin<Object, Object> thirdPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(2);
+        Traversal.Admin<Object, Object> forthPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(3);
+        Traversal.Admin<Object, Object> fifthPattern = ((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren().get(4);
+        countMatchAlgorithm.bundles.stream().forEach(bundle -> assertEquals(0.0d, bundle.multiplicity,
0.0d));
+        assertEquals(MatchStep.TraversalType.MATCH_TRAVERSAL, countMatchAlgorithm.getBundle(firstPattern).traversalType);
+        assertEquals(MatchStep.TraversalType.MATCH_TRAVERSAL, countMatchAlgorithm.getBundle(secondPattern).traversalType);
+        assertEquals(MatchStep.TraversalType.MATCH_TRAVERSAL, countMatchAlgorithm.getBundle(thirdPattern).traversalType);
+        assertEquals(MatchStep.TraversalType.MATCH_TRAVERSAL, countMatchAlgorithm.getBundle(forthPattern).traversalType);
+        assertEquals(MatchStep.TraversalType.MATCH_TRAVERSAL, countMatchAlgorithm.getBundle(fifthPattern).traversalType);
+        assertEquals(firstPattern, countMatchAlgorithm.bundles.get(0).traversal);
+        assertEquals(secondPattern, countMatchAlgorithm.bundles.get(1).traversal);
+        assertEquals(thirdPattern, countMatchAlgorithm.bundles.get(2).traversal);
+        assertEquals(forthPattern, countMatchAlgorithm.bundles.get(3).traversal);
+        assertEquals(fifthPattern, countMatchAlgorithm.bundles.get(4).traversal);
+        // MAKE THE SECOND PATTERN EXPENSIVE
+        countMatchAlgorithm.recordStart(EmptyTraverser.instance(), secondPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), secondPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), secondPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), secondPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), secondPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), secondPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), secondPattern);
+        // MAKE THE THIRD PATTERN MORE EXPENSIVE THAN FORTH
+        countMatchAlgorithm.recordStart(EmptyTraverser.instance(), thirdPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), thirdPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), thirdPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), thirdPattern);
+        // MAKE THE FORTH PATTERN EXPENSIVE
+        countMatchAlgorithm.recordStart(EmptyTraverser.instance(), forthPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), forthPattern);
+        countMatchAlgorithm.recordEnd(EmptyTraverser.instance(), forthPattern);
+        //
+        Traverser.Admin traverser = B_LP_O_P_S_SE_SL_TraverserGenerator.instance().generate(1,
EmptyStep.instance(), 1l);
+        traverser.addLabels(Collections.singleton("a"));
+        assertEquals(firstPattern, countMatchAlgorithm.apply(traverser));
+        traverser = traverser.split(1, EmptyStep.instance());
+        traverser.addLabels(new HashSet<>(Arrays.asList("b", firstPattern.getStartStep().getId())));
+        //
+        assertEquals(secondPattern, countMatchAlgorithm.apply(traverser));
+        traverser = traverser.split(1, EmptyStep.instance());
+        traverser.addLabels(new HashSet<>(Arrays.asList("c", secondPattern.getStartStep().getId())));
+        //
+        assertEquals(fifthPattern, countMatchAlgorithm.apply(traverser));
+        traverser = traverser.split(1, EmptyStep.instance());
+        traverser.addLabels(new HashSet<>(Arrays.asList("f", fifthPattern.getStartStep().getId())));
+        //
+        assertEquals(forthPattern, countMatchAlgorithm.apply(traverser));
+        traverser = traverser.split(1, EmptyStep.instance());
+        traverser.addLabels(new HashSet<>(Arrays.asList("e", forthPattern.getStartStep().getId())));
+        //
+        assertEquals(thirdPattern, countMatchAlgorithm.apply(traverser));
+        traverser = traverser.split(1, EmptyStep.instance());
+        traverser.addLabels(new HashSet<>(Arrays.asList("d", thirdPattern.getStartStep().getId())));
+    }
+
+    @Test
     public void shouldCalculateStartLabelCorrectly() {
         Traversal.Admin<?, ?> traversal = match(
                 where(and(


Mime
View raw message