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 2016/02/17 18:04:30 UTC
incubator-tinkerpop git commit: VertexProgramStrategy is now smart
about GraphStep.PageRank. It will just propagate the GraphStep forward to
reduce the number of OLAP jobs required. Added VertexProgramStrategyTest
which verifies the compilation of a OLAP
Repository: incubator-tinkerpop
Updated Branches:
refs/heads/TINKERPOP-1154 11238b630 -> 2d5cd1c0d
VertexProgramStrategy is now smart about GraphStep.PageRank. It will just propagate the GraphStep forward to reduce the number of OLAP jobs required. Added VertexProgramStrategyTest which verifies the compilation of a OLAP traversal.
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/2d5cd1c0
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/2d5cd1c0
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/2d5cd1c0
Branch: refs/heads/TINKERPOP-1154
Commit: 2d5cd1c0d8ec3f687f237cdf9be4b0b74a73af56
Parents: 11238b6
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Wed Feb 17 10:04:22 2016 -0700
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Wed Feb 17 10:04:22 2016 -0700
----------------------------------------------------------------------
.../decoration/VertexProgramStrategy.java | 22 ++++-
.../decoration/VertexProgramStrategyTest.java | 85 ++++++++++++++++++++
2 files changed, 105 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2d5cd1c0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategy.java
index 354e5a5..775a225 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategy.java
@@ -22,13 +22,13 @@ package org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration;
import org.apache.tinkerpop.gremlin.process.computer.GraphComputer;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.VertexComputing;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ComputerResultStep;
-import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.PageRankVertexProgramStep;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.TraversalVertexProgramStep;
import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.ComputerVerificationStrategy;
@@ -70,8 +70,19 @@ public final class VertexProgramStrategy extends AbstractTraversalStrategy<Trave
return;
}
+ // push GraphStep forward in the chain to reduce the number of TraversalVertexProgram compilations
Step<?, ?> currentStep = traversal.getStartStep();
while (!(currentStep instanceof EmptyStep)) {
+ if (currentStep instanceof GraphStep && currentStep.getNextStep() instanceof VertexComputing) {
+ int index = TraversalHelper.stepIndex(currentStep.getNextStep(), traversal);
+ traversal.removeStep(currentStep);
+ traversal.addStep(index, currentStep);
+ }
+ currentStep = currentStep.getNextStep();
+ }
+ // wrap all non-VertexComputing steps into a TraversalVertexProgramStep
+ currentStep = traversal.getStartStep();
+ while (!(currentStep instanceof EmptyStep)) {
Traversal.Admin<?, ?> computerTraversal = new DefaultTraversal<>();
Step<?, ?> firstLegalOLAPStep = getFirstLegalOLAPStep(currentStep);
Step<?, ?> lastLegalOLAPStep = getLastLegalOLAPStep(currentStep);
@@ -88,6 +99,7 @@ public final class VertexProgramStrategy extends AbstractTraversalStrategy<Trave
currentStep = currentStep.getNextStep();
}
}
+ // if the last vertex computing step is a TraversalVertexProgramStep convert to OLTP with ComputerResultStep
TraversalHelper.getLastStepOfAssignableClass(VertexComputing.class, traversal).ifPresent(step -> {
if (step instanceof TraversalVertexProgramStep) {
final ComputerResultStep computerResultStep = new ComputerResultStep<>(traversal, true);
@@ -96,12 +108,16 @@ public final class VertexProgramStrategy extends AbstractTraversalStrategy<Trave
TraversalHelper.insertAfterStep(computerResultStep, (Step) step, traversal);
}
});
- if (traversal.getEndStep() instanceof PageRankVertexProgramStep) { // TODO: VertexComputing but not TraversalVertexProgramStep
+ // if there is a dangling vertex computing step, add an identity traversal (solve this in the future with a specialized MapReduce)
+ if (traversal.getEndStep() instanceof VertexComputing && !(traversal.getEndStep() instanceof TraversalVertexProgramStep)) {
final TraversalVertexProgramStep traversalVertexProgramStep = new TraversalVertexProgramStep(traversal, __.identity().asAdmin());
traversal.addStep(traversalVertexProgramStep);
traversal.addStep(new ComputerResultStep<>(traversal, true));
}
+ // all vertex computing steps needs the graph computer function
traversal.getSteps().stream().filter(step -> step instanceof VertexComputing).forEach(step -> ((VertexComputing) step).setGraphComputerFunction(this.graphComputerFunction));
+
+ //System.out.println(traversal + "!!!!!!!!!!!");
}
private static Step<?, ?> getFirstLegalOLAPStep(Step<?, ?> currentStep) {
@@ -114,6 +130,8 @@ public final class VertexProgramStrategy extends AbstractTraversalStrategy<Trave
}
private static Step<?, ?> getLastLegalOLAPStep(Step<?, ?> currentStep) {
+ if (currentStep instanceof VertexComputing)
+ currentStep = currentStep.getNextStep();
while (!(currentStep instanceof EmptyStep)) {
if (ComputerVerificationStrategy.isStepInstanceOfEndStep(currentStep))
return currentStep;
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2d5cd1c0/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategyTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategyTest.java
new file mode 100644
index 0000000..19bfef6
--- /dev/null
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/VertexProgramStrategyTest.java
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration;
+
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ComputerResultStep;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.TraversalVertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.ComputerVerificationStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
+import org.apache.tinkerpop.gremlin.process.traversal.util.EmptyTraversal;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author Marko A. Rodriguez (http://markorodriguez.com)
+ */
+@RunWith(Parameterized.class)
+public class VertexProgramStrategyTest {
+
+ @Parameterized.Parameter(value = 0)
+ public Traversal original;
+
+ @Parameterized.Parameter(value = 1)
+ public Traversal optimized;
+
+
+ @Test
+ public void doTest() {
+ final TraversalStrategies strategies = new DefaultTraversalStrategies();
+ strategies.addStrategies(new VertexProgramStrategy(Graph::compute), ComputerVerificationStrategy.instance());
+ original.asAdmin().setStrategies(strategies);
+ original.asAdmin().applyStrategies();
+ assertEquals(optimized, original);
+ }
+
+ @Parameterized.Parameters(name = "{0}")
+ public static Iterable<Object[]> generateTestParameters() {
+
+ final ComputerResultStep computerResultStep = new ComputerResultStep(EmptyTraversal.instance(), true);
+
+ return Arrays.asList(new Traversal[][]{
+ {__.V().out().count(), start().addStep(traversal(__.V().out().count())).addStep(computerResultStep)},
+ {__.V().pageRank().out().count(), start().pageRank().asAdmin().addStep(traversal(__.V().out().count())).addStep(computerResultStep)},
+ {__.V().out().pageRank(), start().addStep(traversal(__.V().out())).pageRank().asAdmin().addStep(traversal(__.identity())).addStep(computerResultStep)},
+ {__.V().out().pageRank().count(), start().addStep(traversal(__.V().out())).pageRank().asAdmin().addStep(traversal(__.count())).addStep(computerResultStep)},
+ {__.V().pageRank().order().limit(1), start().pageRank().asAdmin().addStep(traversal(__.V().order())).addStep(computerResultStep).limit(1)}
+ });
+ }
+
+ private static GraphTraversal.Admin<?, ?> start() {
+ return new DefaultGraphTraversal<>().asAdmin();
+ }
+
+ private static Step<?, ?> traversal(final Traversal<?, ?> traversal) {
+ return new TraversalVertexProgramStep(EmptyTraversal.instance(), traversal.asAdmin());
+ }
+}