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/TINKERPOP-1458 Commit: ff1c3844a487cf4db437edfdf7f2251c38da50ab Parents: 9ef8a9a Author: Marko A. Rodriguez <[email protected]> Authored: Thu Sep 29 14:42:51 2016 -0600 Committer: Marko A. Rodriguez <[email protected]> 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); + } }
