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/09/29 20:42:57 UTC
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 has()-s
Repository: tinkerpop
Updated Branches:
refs/heads/TINKERPOP-1470 c9f8de87c -> ef459d97f
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/ef459d97
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/ef459d97
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/ef459d97
Branch: refs/heads/TINKERPOP-1470
Commit: ef459d97fe821295e0dd177d18cfc4841174be71
Parents: c9f8de8
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Thu Sep 29 14:42:51 2016 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Thu Sep 29 14:42:51 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/ef459d97/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 19381c3..6a99abd 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/ef459d97/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/ef459d97/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/ef459d97/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/ef459d97/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/ef459d97/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/ef459d97/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);
+ }
}