tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ok...@apache.org
Subject [3/9] tinkerpop git commit: FilterRankStategy is now smart about pushing labels 'right'. Why is this good -- it ensures that filter-chains are as concatenated as possible without changing path semantics. This is about increasing the number of potential h
Date Mon, 03 Oct 2016 14:27:02 GMT
FilterRankStategy is now smart about pushing labels 'right'. Why is this good -- it ensures
that filter-chains are as concatenated as possible without changing path semantics. This is
about increasing the number of potential has()-steps that providers can grab for index lookups.
Also, InlineFilterStep is is able to compress has().has() chains into a single has() and propagate
labels accordingly. Added various test cases to validate behavior. The only thing left is
HasContainer being able to compress AndP predicates and we will have a really tight compression
on filters.


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

Branch: refs/heads/master
Commit: ff1c3844a487cf4db437edfdf7f2251c38da50ab
Parents: 9ef8a9a
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Thu Sep 29 14:42:51 2016 -0600
Committer: Marko A. Rodriguez <okrammarko@gmail.com>
Committed: Mon Oct 3 08:24:17 2016 -0600

----------------------------------------------------------------------
 CHANGELOG.asciidoc                              |  1 +
 .../optimization/FilterRankingStrategy.java     | 16 ++++++--
 .../optimization/InlineFilterStrategy.java      | 18 ++++++++-
 .../process/traversal/util/TraversalHelper.java | 11 ++++--
 .../decoration/SubgraphStrategyTest.java        | 28 +++++++-------
 .../optimization/FilterRankingStrategyTest.java |  3 ++
 .../optimization/InlineFilterStrategyTest.java  | 39 +++++++++++++-------
 7 files changed, 79 insertions(+), 37 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/ff1c3844/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index d204b44..638a80c 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.3 (Release Date: NOT OFFICIALLY RELEASED YET)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
+* `FilterRankStrategy` now propagates labels "right" across non-`TraversalParent` filters.
 * Fixed a bug in `ConnectiveP` where nested equivalent connectives should be inlined.
 * Fixed a bug in `IncidentToAdjacentStrategy` where `TreeStep` traversals were allowed.
 * Fixed a end-step label bug in `MatchPredicateStrategy`.

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/ff1c3844/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
index 2a0a025..dead668 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java
@@ -43,7 +43,6 @@ import org.apache.tinkerpop.gremlin.structure.Graph;
 import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
 
 import java.util.Collections;
-import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
@@ -89,9 +88,18 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
 
     @Override
     public void apply(final Traversal.Admin<?, ?> traversal) {
-        boolean modified;
-        do {
+        boolean modified = true;
+        while(modified) {
             modified = false;
+            for (final Step<?, ?> step : traversal.getSteps()) {
+                if (!step.getLabels().isEmpty()) {
+                    final Step<?, ?> nextStep = step.getNextStep();
+                    if (nextStep instanceof FilterStep && !(nextStep instanceof TraversalParent))
{
+                        TraversalHelper.copyLabels(step, nextStep, true);
+                        modified = true;
+                    }
+                }
+            }
             final List<Step> steps = traversal.getSteps();
             int prevRank = 0;
             for (int i = steps.size() - 1; i >= 0; i--) {
@@ -105,7 +113,7 @@ public final class FilterRankingStrategy extends AbstractTraversalStrategy<Trave
                 }
                 prevRank = rank;
             }
-        } while (modified);
+        }
     }
 
     @Override

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/ff1c3844/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 a3ed9a1..820143a 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
@@ -76,7 +76,10 @@ public final class InlineFilterStrategy extends AbstractTraversalStrategy<Traver
         while (changed) {
             changed = false;
             for (final FilterStep<?> step : TraversalHelper.getStepsOfAssignableClass(FilterStep.class,
traversal)) {
-                if (step instanceof TraversalFilterStep && InlineFilterStrategy.processTraversalFilterStep((TraversalFilterStep)
step, traversal))
+                if (step instanceof HasStep && InlineFilterStrategy.processHasStep((HasStep)
step, traversal))
+                    // has(a,b).has(c) --> has(a,b,c)
+                    changed = true;
+                else if (step instanceof TraversalFilterStep && InlineFilterStrategy.processTraversalFilterStep((TraversalFilterStep)
step, traversal))
                     // filter(x.y) --> x.y
                     changed = true;
                 else if (step instanceof OrStep && InlineFilterStrategy.processOrStep((OrStep)
step, traversal))
@@ -99,6 +102,19 @@ public final class InlineFilterStrategy extends AbstractTraversalStrategy<Traver
     ////////////////////////////
     ///////////////////////////
 
+    private static final boolean processHasStep(final HasStep<?> step, final Traversal.Admin<?,
?> traversal) {
+        if (step.getPreviousStep() instanceof HasStep) {
+            final HasStep<?> previousStep = (HasStep<?>) step.getPreviousStep();
+            for (final HasContainer hasContainer : step.getHasContainers()) {
+                previousStep.addHasContainer(hasContainer);
+            }
+            TraversalHelper.copyLabels(step, previousStep, false);
+            traversal.removeStep(step);
+            return true;
+        }
+        return false;
+    }
+
     private static final boolean processTraversalFilterStep(final TraversalFilterStep<?>
step, final Traversal.Admin<?, ?> traversal) {
         final Traversal.Admin<?, ?> childTraversal = step.getLocalChildren().get(0);
         if (TraversalHelper.hasAllStepsOfClass(childTraversal, FilterStep.class) &&

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/ff1c3844/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java
index 2192666..be1406d 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java
@@ -50,6 +50,7 @@ import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Optional;
 import java.util.Set;
@@ -572,10 +573,12 @@ public final class TraversalHelper {
     }
 
     public static void copyLabels(final Step<?, ?> fromStep, final Step<?, ?>
toStep, final boolean moveLabels) {
-        for (final String label : fromStep.getLabels()) {
-            toStep.addLabel(label);
-            if (moveLabels)
-                fromStep.removeLabel(label);
+        if (!fromStep.getLabels().isEmpty()) {
+            for (final String label : moveLabels ? new LinkedHashSet<>(fromStep.getLabels())
: fromStep.getLabels()) {
+                toStep.addLabel(label);
+                if (moveLabels)
+                    fromStep.removeLabel(label);
+            }
         }
     }
 

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/ff1c3844/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java
index 7082838..901d3a5 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java
@@ -69,28 +69,26 @@ public class SubgraphStrategyTest {
         @Parameterized.Parameter(value = 1)
         public Traversal optimized;
 
-
-        void applySubgraphStrategyTest(final Traversal traversal) {
-            final TraversalStrategies strategies = new DefaultTraversalStrategies();
-            strategies.addStrategies(SubgraphStrategy.build().
+        @Test
+        public void doTest() {
+            final TraversalStrategies originalStrategies = new DefaultTraversalStrategies();
+            originalStrategies.addStrategies(SubgraphStrategy.build().
                     vertices(__.and(has("name", "marko"), has("age", 29))).
                     edges(hasLabel("knows")).
                     vertexProperties(__.<VertexProperty, Long>values().count().and(is(P.lt(10)),
is(0))).create());
-            strategies.addStrategies(InlineFilterStrategy.instance());
-            strategies.addStrategies(StandardVerificationStrategy.instance());
-            traversal.asAdmin().setStrategies(strategies);
-            traversal.asAdmin().applyStrategies();
-        }
-
-        @Test
-        public void doTest() {
-            applySubgraphStrategyTest(original);
-            assertEquals(optimized, original);
+            originalStrategies.addStrategies(InlineFilterStrategy.instance());
+            originalStrategies.addStrategies(StandardVerificationStrategy.instance());
+            this.original.asAdmin().setStrategies(originalStrategies);
+            this.original.asAdmin().applyStrategies();
+            final TraversalStrategies optimizedStrategies = new DefaultTraversalStrategies();
+            optimizedStrategies.addStrategies(InlineFilterStrategy.instance());
+            this.optimized.asAdmin().setStrategies(optimizedStrategies);
+            this.optimized.asAdmin().applyStrategies();
+            assertEquals(this.optimized, this.original);
         }
 
         @Parameterized.Parameters(name = "{0}")
         public static Iterable<Object[]> generateTestParameters() {
-
             return Arrays.asList(new Traversal[][]{
                     {__.outE(), __.outE().hasLabel("knows").and(
                             inV().has("name", "marko").has("age", 29),

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/ff1c3844/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
index dc0d17a..52379fd 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java
@@ -32,6 +32,7 @@ import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 
+import static org.apache.tinkerpop.gremlin.process.traversal.P.eq;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.filter;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.has;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.in;
@@ -79,6 +80,8 @@ public class FilterRankingStrategyTest {
 
         return Arrays.asList(new Object[][]{
                 {__.dedup().order(), __.dedup().order(), Collections.emptyList()},
+                {__.has("name", "marko").has("age", 32).dedup().has("name", "bob").as("a"),
__.has("name", "marko").has("age", 32).dedup().has("name", "bob").as("a"), Collections.emptyList()},
+                {__.has("name", "marko").dedup().as("a").has("age", 32).has("name", "bob").as("b"),
__.has("name", "marko").has("age", 32).dedup().has("name", "bob").as("a","b"), Collections.emptyList()},
                 {__.order().dedup(), __.dedup().order(), Collections.emptyList()},
                 {__.order().as("a").dedup(), __.order().as("a").dedup(), Collections.emptyList()},
                 {__.identity().order().dedup(), __.dedup().order(), Collections.singletonList(IdentityRemovalStrategy.instance())},

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/ff1c3844/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java
index 9530c82..abf1f00 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java
@@ -22,6 +22,10 @@ package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization;
 import org.apache.tinkerpop.gremlin.process.traversal.P;
 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.GraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.HasStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.HasContainer;
 import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -40,7 +44,6 @@ import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.drop;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.filter;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.has;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.limit;
-import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.map;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.match;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.or;
 import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.out;
@@ -74,11 +77,13 @@ public class InlineFilterStrategyTest {
     public static Iterable<Object[]> generateTestParameters() {
 
         return Arrays.asList(new Traversal[][]{
+                {has("age", 10).as("a").has("name", "marko").as("b").coin(0.5).as("c"), addHas(__.start(),
"age", eq(10), "name", eq("marko")).as("a","b").coin(0.5).as("c")},
+                //
                 {filter(out("knows")), filter(out("knows"))},
-                {filter(has("age", P.gt(10))).as("a"), has("age", P.gt(10)).as("a")},
-                {filter(has("age", P.gt(10)).as("b")).as("a"), has("age", P.gt(10)).as("b",
"a")},
-                {filter(has("age", P.gt(10)).as("a")), has("age", P.gt(10)).as("a")},
-                {filter(and(has("age", P.gt(10)).as("a"), has("name", "marko"))), has("age",
P.gt(10)).as("a").has("name", "marko")},
+                {filter(has("age", gt(10))).as("a"), has("age", gt(10)).as("a")},
+                {filter(has("age", gt(10)).as("b")).as("a"), has("age", gt(10)).as("b", "a")},
+                {filter(has("age", gt(10)).as("a")), has("age", gt(10)).as("a")},
+                {filter(and(has("age", gt(10)).as("a"), has("name", "marko"))), addHas(__.start(),
"age", gt(10), "name", eq("marko")).as("a")},
                 //
                 {or(has("name", "marko"), has("age", 32)), or(has("name", "marko"), has("age",
32))},
                 {or(has("name", "marko"), has("name", "bob")), has("name", eq("marko").or(eq("bob")))},
@@ -88,17 +93,17 @@ public class InlineFilterStrategyTest {
                 {or(has("name", "marko"), filter(or(filter(has("name", "bob")), has("name",
"stephen")))), has("name", eq("marko").or(eq("bob").or(eq("stephen"))))},
                 {or(has("name", "marko").as("a"), filter(or(filter(has("name", "bob")).as("b"),
has("name", "stephen").as("c")))), has("name", eq("marko").or(eq("bob").or(eq("stephen")))).as("a",
"b", "c")},
                 //
-                {and(has("age", P.gt(10)), filter(has("age", 22))), has("age", P.gt(10)).has("age",
22)},
-                {and(has("age", P.gt(10)).as("a"), filter(has("age", 22).as("b")).as("c")).as("d"),
has("age", P.gt(10)).as("a").has("age", 22).as("b", "c", "d")},
-                {and(has("age", P.gt(10)).as("a"), and(filter(has("age", 22).as("b")).as("c"),
has("name", "marko").as("d"))), has("age", P.gt(10)).as("a").has("age", 22).as("b", "c").has("name",
"marko").as("d")},
-                {and(has("age", P.gt(10)).as("a"), and(has("name","stephen").as("b"), has("name",
"marko").as("c")).as("d")).as("e"), has("age", P.gt(10)).as("a").has("name","stephen").as("b").has("name","marko").as("c","d","e")},
-                {and(has("age", P.gt(10)), and(out("knows"), has("name", "marko"))), has("age",
P.gt(10)).and(out("knows"), has("name", "marko"))},
-                {and(has("age", P.gt(20)), or(has("age", lt(10)), has("age", gt(100)))),
has("age", gt(20)).has("age", lt(10).or(gt(100)))},
-                {and(has("age", P.gt(20)).as("a"), or(has("age", lt(10)), has("age", gt(100)).as("b"))),
has("age", gt(20)).as("a").has("age", lt(10).or(gt(100))).as("b")},
+                {and(has("age", gt(10)), filter(has("age", 22))), addHas(__.start(), "age",
gt(10), "age", eq(22))},
+                {and(has("age", gt(10)).as("a"), filter(has("age", 22).as("b")).as("c")).as("d"),
addHas(__.start(), "age", gt(10), "age", eq(22)).as("a", "b", "c", "d")},
+                {and(has("age", gt(10)).as("a"), and(filter(has("age", 22).as("b")).as("c"),
has("name", "marko").as("d"))), addHas(__.start(), "age", gt(10), "age", eq(22), "name", eq("marko")).as("a",
"b", "c", "d")},
+                {and(has("age", gt(10)).as("a"), and(has("name", "stephen").as("b"), has("name",
"marko").as("c")).as("d")).as("e"), addHas(__.start(), "age", gt(10), "name", eq("stephen"),
"name", eq("marko")).as("a", "b", "c", "d", "e")},
+                {and(has("age", gt(10)), and(out("knows"), has("name", "marko"))), has("age",
gt(10)).and(out("knows"), has("name", "marko"))},
+                {and(has("age", gt(20)), or(has("age", lt(10)), has("age", gt(100)))), addHas(__.start(),
"age", gt(20), "age", lt(10).or(gt(100)))},
+                {and(has("age", gt(20)).as("a"), or(has("age", lt(10)), has("age", gt(100)).as("b"))),
addHas(__.start(), "age", gt(20), "age", lt(10).or(gt(100))).as("a", "b")},
                 //
                 {V().match(as("a").has("age", 10), as("a").filter(has("name")).as("b")),
V().as("a").has("age", 10).match(as("a").has("name").as("b"))},
                 {match(as("a").has("age", 10), as("a").filter(has("name")).as("b")), match(as("a").has("age",
10), as("a").has("name").as("b"))},
-                {map(match(as("a").has("age", 10), as("a").filter(has("name")).as("b"))),
map(match(as("a").has("age", 10), as("a").has("name").as("b")))},
+                {__.map(match(as("a").has("age", 10), as("a").filter(has("name")).as("b"))),
__.map(match(as("a").has("age", 10), as("a").has("name").as("b")))},
                 {V().match(as("a").has("age", 10)), V().as("a").has("age", 10)},
                 {V().match(as("a").has("age", 10).as("b"), as("a").filter(has("name")).as("b")),
V().as("a").has("age", 10).as("b").match(as("a").has("name").as("b"))},
                 //
@@ -108,4 +113,12 @@ public class InlineFilterStrategyTest {
                 {filter(tail(10).as("a")), filter(tail(10).as("a"))},
         });
     }
+
+    private static GraphTraversal.Admin<?, ?> addHas(final GraphTraversal<?, ?>
traversal, final Object... hasKeyValues) {
+        final HasStep<?> hasStep = new HasStep<>((Traversal.Admin) traversal);
+        for (int i = 0; i < hasKeyValues.length; i = i + 2) {
+            hasStep.addHasContainer(new HasContainer((String) hasKeyValues[i], (P) hasKeyValues[i
+ 1]));
+        }
+        return traversal.asAdmin().addStep(hasStep);
+    }
 }


Mime
View raw message