tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ok...@apache.org
Subject [1/3] tinkerpop git commit: Added where(a.out.b) => select(a).where(out.b) AND where(a.out) => select(a).filter(out) to PathProcessorStrategy (an OLAP strategy). This opens up more traversals that would otherwise break the star-graph local child constrai
Date Mon, 07 Nov 2016 16:38:47 GMT
Repository: tinkerpop
Updated Branches:
  refs/heads/tp32 11f711d5f -> 0c8d856f0


Added where(a.out.b) => select(a).where(out.b) AND where(a.out) => select(a).filter(out)
to PathProcessorStrategy (an OLAP strategy). This opens up more traversals that would otherwise
break the star-graph local child constraint in OLAP.


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

Branch: refs/heads/tp32
Commit: a69efffef138b036581fdb8c5bcd22c8075aa846
Parents: ab48b3f
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Wed Nov 2 04:50:57 2016 -0600
Committer: Marko A. Rodriguez <okrammarko@gmail.com>
Committed: Wed Nov 2 04:50:57 2016 -0600

----------------------------------------------------------------------
 CHANGELOG.asciidoc                              |  1 +
 .../optimization/InlineFilterStrategy.java      |  5 +-
 .../optimization/MatchPredicateStrategy.java    |  2 +-
 .../optimization/PathProcessorStrategy.java     | 31 ++++++---
 .../optimization/PathProcessorStrategyTest.java | 70 +++++++++++---------
 5 files changed, 66 insertions(+), 43 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a69efffe/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index cf8c007..578972c 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -26,6 +26,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
 TinkerPop 3.2.4 (Release Date: NOT OFFICIALLY RELEASED YET)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
+* `PathProcessorStrategy` can inline certain `where(traversal)`-steps in order to increase
the likelihood of star-local children.
 * `SparkGraphComputer` no longer starts a worker iteration if the worker's partition is empty.
 * Added `ProjectStep.getProjectKeys()` for strategies that rely on such information.
 * Added `VertexFeatures.supportsDuplicateMultiProperties()` for graphs that only support
unique values in multi-properties.

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a69efffe/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
index 60d024e..2fa207d 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
@@ -73,11 +73,12 @@ public final class InlineFilterStrategy extends AbstractTraversalStrategy<Traver
 
     private static final InlineFilterStrategy INSTANCE = new InlineFilterStrategy();
     private static final Set<Class<? extends OptimizationStrategy>> POSTS = new
HashSet<>(Arrays.asList(
-            MatchPredicateStrategy.class,
             FilterRankingStrategy.class,
             GraphFilterStrategy.class,
             AdjacentToIncidentStrategy.class));
-    private static final Set<Class<? extends OptimizationStrategy>> PRIORS =
Collections.singleton(IdentityRemovalStrategy.class);
+    private static final Set<Class<? extends OptimizationStrategy>> PRIORS =
new HashSet<>(Arrays.asList(
+            IdentityRemovalStrategy.class,
+            MatchPredicateStrategy.class));
 
     private InlineFilterStrategy() {
     }

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a69efffe/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java
index f2928d8..c91c392 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java
@@ -54,7 +54,7 @@ import java.util.Set;
 public final class MatchPredicateStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy>
implements TraversalStrategy.OptimizationStrategy {
 
     private static final MatchPredicateStrategy INSTANCE = new MatchPredicateStrategy();
-    private static final Set<Class<? extends OptimizationStrategy>> PRIORS =
new HashSet<>(Arrays.asList(IdentityRemovalStrategy.class, InlineFilterStrategy.class));
+    private static final Set<Class<? extends OptimizationStrategy>> PRIORS =
Collections.singleton(IdentityRemovalStrategy.class);
     private static final Set<Class<? extends OptimizationStrategy>> POSTS = Collections.singleton(FilterRankingStrategy.class);
 
     private MatchPredicateStrategy() {

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a69efffe/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java
index 0b40743..c9d49a9 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java
@@ -25,34 +25,47 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
 import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TraversalFilterStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereTraversalStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.SelectOneStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.SelectStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.TraversalMapStep;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
 
-import java.util.Arrays;
 import java.util.Collections;
-import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
 /**
+ * PathProcessStrategy is an OLAP strategy that does its best to turn non-local children
in {@code where()} and {@code select()}
+ * into local children by inlining components of the non-local child. In this way, PathProcessStrategy
helps to ensure
+ * that more traversals meet the local child constraint imposed on OLAP traversals.
+ *
  * @author Marko A. Rodriguez (http://markorodriguez.com)
+ * @example <pre>
+ * __.select(a).by(x)               // is replaced by select(a).map(x)
+ * __.select(a,b).by(x).by(y)       // is replaced by select(a).by(x).as(a).select(b).by(y).as(b).select(a,b)
+ * __.where(as(a).out().as(b))      // is replaced by select(a).where(out().as(b))
+ * __.where(as(a).out())            // is replaced by select(a).filter(out())
+ * </pre>
  */
 public final class PathProcessorStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy>
implements TraversalStrategy.OptimizationStrategy {
 
     private static final PathProcessorStrategy INSTANCE = new PathProcessorStrategy();
 
-    private static final Set<Class<? extends OptimizationStrategy>> PRIORS =
Collections.singleton(MatchPredicateStrategy.class);
-
     private PathProcessorStrategy() {
     }
 
     @Override
     public Set<Class<? extends OptimizationStrategy>> applyPrior() {
-        return PRIORS;
+        return Collections.singleton(MatchPredicateStrategy.class);
+    }
+
+    @Override
+    public Set<Class<? extends OptimizationStrategy>> applyPost() {
+        return Collections.singleton(InlineFilterStrategy.class);
     }
 
     @Override
@@ -60,9 +73,8 @@ public final class PathProcessorStrategy extends AbstractTraversalStrategy<Trave
         if (!TraversalHelper.onGraphComputer(traversal) || !TraversalHelper.isGlobalChild(traversal))
             return;
 
-        // process where(as("a").out()...)
-        // todo: need to be able to drop path labels for this to work
-        /*final List<WhereTraversalStep> whereTraversalSteps = TraversalHelper.getStepsOfClass(WhereTraversalStep.class,
traversal);
+        // process where(as("a").out()...) => select("a").where(out()...)
+        final List<WhereTraversalStep> whereTraversalSteps = TraversalHelper.getStepsOfClass(WhereTraversalStep.class,
traversal);
         for (final WhereTraversalStep<?> whereTraversalStep : whereTraversalSteps)
{
             final Traversal.Admin<?, ?> localChild = whereTraversalStep.getLocalChildren().get(0);
             if ((localChild.getStartStep() instanceof WhereTraversalStep.WhereStartStep)
&&
@@ -82,13 +94,14 @@ public final class PathProcessorStrategy extends AbstractTraversalStrategy<Trave
                 final SelectOneStep<?, ?> selectOneStep = new SelectOneStep<>(traversal,
Pop.last, whereStartStep.getScopeKeys().iterator().next());
                 traversal.addStep(index, selectOneStep);
                 whereStartStep.removeScopeKey();
+                // process where(as("a").out()) => select("a").filter(out())
                 if (!(localChild.getEndStep() instanceof WhereTraversalStep.WhereEndStep))
{
                     localChild.removeStep(localChild.getStartStep());
                     traversal.addStep(index + 1, new TraversalFilterStep<>(traversal,
localChild));
                     traversal.removeStep(whereTraversalStep);
                 }
             }
-        }*/
+        }
 
         // process select("a","b").by(...).by(...)
         final List<SelectStep> selectSteps = TraversalHelper.getStepsOfClass(SelectStep.class,
traversal);

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a69efffe/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java
index 84f4dcd..562d5d6 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java
@@ -24,16 +24,20 @@ import org.apache.tinkerpop.gremlin.process.traversal.P;
 import org.apache.tinkerpop.gremlin.process.traversal.Pop;
 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.lambda.ElementValueTraversal;
 import org.apache.tinkerpop.gremlin.process.traversal.lambda.IdentityTraversal;
 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 java.util.Collection;
+import java.util.Collections;
 
 import static org.junit.Assert.assertEquals;
 
@@ -49,49 +53,53 @@ public class PathProcessorStrategyTest {
     @Parameterized.Parameter(value = 1)
     public Traversal optimized;
 
+    @Parameterized.Parameter(value = 2)
+    public Collection<TraversalStrategy> otherStrategies;
 
-    void applyPathProcessorStrategy(final Traversal traversal) {
+    @Test
+    public void doTest() {
+        this.original.asAdmin().setParent(new TraversalVertexProgramStep(EmptyTraversal.instance(),
EmptyTraversal.instance())); // trick it
         final TraversalStrategies strategies = new DefaultTraversalStrategies();
         strategies.addStrategies(PathProcessorStrategy.instance());
-        traversal.asAdmin().setStrategies(strategies);
-        traversal.asAdmin().applyStrategies();
+        for (final TraversalStrategy strategy : this.otherStrategies) {
+            strategies.addStrategies(strategy);
+        }
+        this.original.asAdmin().setStrategies(strategies);
+        this.original.asAdmin().applyStrategies();
+        assertEquals(this.optimized, this.original);
     }
 
-    @Test
-    public void doTest() {
-        original.asAdmin().setParent(new TraversalVertexProgramStep(EmptyTraversal.instance(),
EmptyTraversal.instance())); // trick it
-        applyPathProcessorStrategy(original);
-        assertEquals(optimized, original);
-    }
 
     @Parameterized.Parameters(name = "{0}")
     public static Iterable<Object[]> generateTestParameters() {
 
-        return Arrays.asList(new Traversal[][]{
+        return Arrays.asList(new Object[][]{
                 // select("a")
-                {__.select("a"), __.select("a")},
-                {__.select("a").by(), __.select("a").by()},
-                {__.select("a").by(__.outE().count()), __.select("a").map(__.outE().count())},
-                {__.select("a").by("name"), __.select("a").map(new ElementValueTraversal<>("name"))},
-                {__.select("a").out(), __.select("a").out()},
-                {__.select(Pop.all, "a").by(__.values("name")), __.select(Pop.all, "a").by(__.values("name"))},
-                {__.select(Pop.last, "a").by(__.values("name")), __.select(Pop.last, "a").map(__.values("name"))},
-                {__.select(Pop.first, "a").by(__.values("name")), __.select(Pop.first, "a").map(__.values("name"))},
+                {__.select("a"), __.select("a"), Collections.emptyList()},
+                {__.select("a").by(), __.select("a").by(), Collections.emptyList()},
+                {__.select("a").by(__.outE().count()), __.select("a").map(__.outE().count()),
Collections.emptyList()},
+                {__.select("a").by("name"), __.select("a").map(new ElementValueTraversal<>("name")),
Collections.emptyList()},
+                {__.select("a").out(), __.select("a").out(), Collections.emptyList()},
+                {__.select(Pop.all, "a").by(__.values("name")), __.select(Pop.all, "a").by(__.values("name")),
TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+                {__.select(Pop.last, "a").by(__.values("name")), __.select(Pop.last, "a").map(__.values("name")),TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+                {__.select(Pop.first, "a").by(__.values("name")), __.select(Pop.first, "a").map(__.values("name")),
TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
                 // select("a","b")
-                {__.select("a", "b"), __.select("a", "b")},
-                {__.select("a", "b").by(), __.select("a", "b").by()},
-                {__.select("a", "b", "c").by(), __.select("a", "b", "c").by()},
-                {__.select("a", "b").by().by("age"), __.select("b").map(new ElementValueTraversal<>("age")).as("b").select("a").map(new
IdentityTraversal<>()).as("a").select(Pop.last, "a", "b")},
-                {__.select("a", "b").by("name").by("age"), __.select("b").map(new ElementValueTraversal<>("age")).as("b").select("a").map(new
ElementValueTraversal<>("name")).as("a").select(Pop.last, "a", "b")},
-                {__.select("a", "b", "c").by("name").by(__.outE().count()), __.select("c").map(new
ElementValueTraversal<>("name")).as("c").select("b").map(__.outE().count()).as("b").select("a").map(new
ElementValueTraversal<>("name")).as("a").select(Pop.last, "a", "b", "c")},
-                {__.select(Pop.first, "a", "b").by("name").by("age"), __.select(Pop.first,
"b").map(new ElementValueTraversal<>("age")).as("b").select(Pop.first, "a").map(new
ElementValueTraversal<>("name")).as("a").select(Pop.last, "a", "b")},
-                {__.select(Pop.last, "a", "b").by("name").by("age"), __.select(Pop.last,
"b").map(new ElementValueTraversal<>("age")).as("b").select(Pop.last, "a").map(new ElementValueTraversal<>("name")).as("a").select(Pop.last,
"a", "b")},
-                {__.select(Pop.all, "a", "b").by("name").by("age"), __.select(Pop.all, "a",
"b").by("name").by("age")},
+                {__.select("a", "b"), __.select("a", "b"), Collections.emptyList()},
+                {__.select("a", "b").by(), __.select("a", "b").by(), Collections.emptyList()},
+                {__.select("a", "b", "c").by(), __.select("a", "b", "c").by(), Collections.emptyList()},
+                {__.select("a", "b").by().by("age"), __.select("b").map(new ElementValueTraversal<>("age")).as("b").select("a").map(new
IdentityTraversal<>()).as("a").select(Pop.last, "a", "b"), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+                {__.select("a", "b").by("name").by("age"), __.select("b").map(new ElementValueTraversal<>("age")).as("b").select("a").map(new
ElementValueTraversal<>("name")).as("a").select(Pop.last, "a", "b"), Collections.emptyList()},
+                {__.select("a", "b", "c").by("name").by(__.outE().count()), __.select("c").map(new
ElementValueTraversal<>("name")).as("c").select("b").map(__.outE().count()).as("b").select("a").map(new
ElementValueTraversal<>("name")).as("a").select(Pop.last, "a", "b", "c"), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+                {__.select(Pop.first, "a", "b").by("name").by("age"), __.select(Pop.first,
"b").map(new ElementValueTraversal<>("age")).as("b").select(Pop.first, "a").map(new
ElementValueTraversal<>("name")).as("a").select(Pop.last, "a", "b"), Collections.emptyList()},
+                {__.select(Pop.last, "a", "b").by("name").by("age"), __.select(Pop.last,
"b").map(new ElementValueTraversal<>("age")).as("b").select(Pop.last, "a").map(new ElementValueTraversal<>("name")).as("a").select(Pop.last,
"a", "b"), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+                {__.select(Pop.all, "a", "b").by("name").by("age"), __.select(Pop.all, "a",
"b").by("name").by("age"), Collections.emptyList()},
                 // where(as("a")...)
-                {__.where(__.out("knows")), __.where(__.out("knows"))},
-                //{__.where(__.as("a").out("knows")), __.select(Pop.last, "a").where(__.out("knows"))},
-                //{__.where(__.as("a").out("knows").as("b")), __.select(Pop.last, "a").where(__.out("knows").as("b"))},
   // todo: need to be able to drop path labels for this to work
-                {__.where("a", P.eq("b")), __.where("a", P.eq("b"))}
+                {__.where(__.out("knows")), __.where(__.outE("knows")), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+                {__.where(__.as("a").out("knows")), __.select(Pop.last, "a").filter(__.out("knows")),
Collections.emptyList()},
+                {__.where(__.as("a").has("age",P.gt(10))), __.select(Pop.last, "a").has("age",P.gt(10)),
TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+                {__.select("b").where(__.as("a").has("age",P.gt(10))), __.select("b").select(Pop.last,
"a").has("age",P.gt(10)), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+                {__.where(__.as("a").out("knows").as("b")), __.select(Pop.last, "a").where(__.out("knows").as("b")),
Collections.emptyList()},
+                {__.where("a", P.eq("b")), __.where("a", P.eq("b")), Collections.emptyList()}
         });
     }
 }


Mime
View raw message