You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2015/11/03 17:16:45 UTC
incubator-tinkerpop git commit: MatchStep is smart to bias patterns
towards the local star graph to reduce inter-machine communication.
Repository: incubator-tinkerpop
Updated Branches:
refs/heads/TINKERPOP3-768 aadd42212 -> 956d7977f
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-768
Commit: 956d7977f4507db8d51b0468604f3b214e0681b3
Parents: aadd422
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Tue Nov 3 09:16:39 2015 -0700
Committer: Marko A. Rodriguez <ok...@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(