This is an automated email from the ASF dual-hosted git repository. dkuppitz pushed a commit to branch TINKERPOP-1882 in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit 28733e689d81c4b0bbbac090715a22aab768a1af Author: Daniel Kuppitz <[email protected]> AuthorDate: Sat Jan 12 19:50:28 2019 -0700 TINKERPOP-1882 Implemented `EarlyLimitStrategy`. --- CHANGELOG.asciidoc | 1 + .../tinkerpop/gremlin/jsr223/CoreImports.java | 2 + .../process/traversal/TraversalStrategies.java | 2 + .../strategy/optimization/EarlyLimitStrategy.java | 136 +++++++++++++++++++++ .../strategy/optimization/LazyBarrierStrategy.java | 3 +- .../structure/io/graphson/GraphSONModule.java | 5 + .../gremlin/structure/io/gryo/GryoVersion.java | 7 +- .../optimization/EarlyLimitStrategyTest.java | 101 +++++++++++++++ .../jython/gremlin_python/process/strategies.py | 3 + .../tinkergraph/structure/TinkerGraphPlayTest.java | 97 +++------------ 10 files changed, 271 insertions(+), 86 deletions(-) diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc index 1b0f79b..152dbdf 100644 --- a/CHANGELOG.asciidoc +++ b/CHANGELOG.asciidoc @@ -26,6 +26,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima * Masked sensitive configuration options in the logs of `KryoShimServiceLoader`. * Fixed a concurrency issue in `TraverserSet` * Fixed a bug in `InlineFilterStrategy` that mixed up and's and or's when folding merging conditions together. +* Implemented `EarlyLimitStrategy` which is supposed to significantly reduce backend operations for queries the use `range()`. [[release-3-3-5]] === TinkerPop 3.3.5 (Release Date: January 2, 2019) diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java index 712cf01..576d0de 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/jsr223/CoreImports.java @@ -76,6 +76,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.Subgra import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.MatchAlgorithmStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.EarlyLimitStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.FilterRankingStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IdentityRemovalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy; @@ -232,6 +233,7 @@ public final class CoreImports { CLASS_IMPORTS.add(IdentityRemovalStrategy.class); CLASS_IMPORTS.add(IncidentToAdjacentStrategy.class); CLASS_IMPORTS.add(MatchPredicateStrategy.class); + CLASS_IMPORTS.add(EarlyLimitStrategy.class); CLASS_IMPORTS.add(OrderLimitStrategy.class); CLASS_IMPORTS.add(PathProcessorStrategy.class); CLASS_IMPORTS.add(CountStrategy.class); diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java index 5e93345..e802304 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java @@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.Connec import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.CountStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.EarlyLimitStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.FilterRankingStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.InlineFilterStrategy; @@ -213,6 +214,7 @@ public interface TraversalStrategies extends Serializable, Cloneable { final TraversalStrategies graphStrategies = new DefaultTraversalStrategies(); graphStrategies.addStrategies( ConnectiveStrategy.instance(), + EarlyLimitStrategy.instance(), InlineFilterStrategy.instance(), IncidentToAdjacentStrategy.instance(), AdjacentToIncidentStrategy.instance(), diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategy.java new file mode 100644 index 0000000..acef8f9 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategy.java @@ -0,0 +1,136 @@ +/* + * 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.optimization; + +import javafx.geometry.Side; +import org.apache.tinkerpop.gremlin.process.traversal.Step; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.step.Barrier; +import org.apache.tinkerpop.gremlin.process.traversal.step.SideEffectCapable; +import org.apache.tinkerpop.gremlin.process.traversal.step.branch.BranchStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.branch.RepeatStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.filter.FilterStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.filter.NoneStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.filter.RangeGlobalStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TailGlobalStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.FlatMapStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.IdStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.LabelStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.OrderGlobalStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.PathStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.SackStep; +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.TreeStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.ProfileSideEffectStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SideEffectCapStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep; +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.HashSet; +import java.util.List; +import java.util.Set; + +/** + * @author Daniel Kuppitz (http://gremlin.guru) + */ +public final class EarlyLimitStrategy + extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> + implements TraversalStrategy.OptimizationStrategy { + + private static final EarlyLimitStrategy INSTANCE = new EarlyLimitStrategy(); + + private EarlyLimitStrategy() { + } + + @Override + public void apply(final Traversal.Admin<?, ?> traversal) { + + final List<Step> steps = traversal.getSteps(); + Step insertAfter = null; + boolean merge = false; + //noinspection ForLoopReplaceableByForEach + for (int i = 0, j = steps.size(); i < j; i++) { + final Step step = steps.get(i); + if (step instanceof RangeGlobalStep) { + if (insertAfter != null) { + TraversalHelper.copyLabels(step, step.getPreviousStep(), true); + insertAfter = moveRangeStep((RangeGlobalStep) step, insertAfter, traversal, merge); + if (insertAfter instanceof NoneStep) { + // any step besides a SideEffectCapStep after a NoneStep would be pointless + final int noneStepIndex = TraversalHelper.stepIndex(insertAfter, traversal); + for (i = j - 2; i > noneStepIndex; i--) { + if (!(steps.get(i) instanceof SideEffectCapStep) && !(steps.get(i) instanceof ProfileSideEffectStep)) { + traversal.removeStep(i); + } + } + break; + } + j = steps.size(); + } + } else if ( + step instanceof Barrier || step instanceof BranchStep || step instanceof FlatMapStep || + step instanceof FilterStep || step instanceof RepeatStep) { + insertAfter = step; + merge = true; + } else if (step instanceof SideEffectCapable) { + merge = false; + } + } + } + + @SuppressWarnings("unchecked") + private Step moveRangeStep(final RangeGlobalStep step, final Step insertAfter, final Traversal.Admin<?, ?> traversal, + final boolean merge) { + final Step rangeStep; + boolean remove = true; + if (insertAfter instanceof RangeGlobalStep) { + final RangeGlobalStep other = (RangeGlobalStep) insertAfter; + final long low = other.getLowRange() + step.getLowRange(); + if (other.getHighRange() == -1L) { + rangeStep = new RangeGlobalStep(traversal, low, other.getLowRange() + step.getHighRange()); + } else if (step.getHighRange() == -1L) { + final long high = other.getHighRange() - other.getLowRange() - step.getLowRange() + low; + if (low < high) { + rangeStep = new RangeGlobalStep(traversal, low, high); + } else { + rangeStep = new NoneStep<>(traversal); + } + } else { + final long high = other.getLowRange() + step.getHighRange(); + rangeStep = new RangeGlobalStep(traversal, low, Math.min(high, other.getHighRange())); + } + remove = merge; + TraversalHelper.replaceStep(merge ? insertAfter : step, rangeStep, traversal); + } else { + rangeStep = step.clone(); + TraversalHelper.insertAfterStep(rangeStep, insertAfter, traversal); + } + if (remove) traversal.removeStep(step); + return rangeStep; + } + + public static EarlyLimitStrategy instance() { + return INSTANCE; + } +} diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategy.java index 927d6c9..1313d3e 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategy.java @@ -54,7 +54,8 @@ public final class LazyBarrierStrategy extends AbstractTraversalStrategy<Travers AdjacentToIncidentStrategy.class, FilterRankingStrategy.class, InlineFilterStrategy.class, - MatchPredicateStrategy.class)); + MatchPredicateStrategy.class, + EarlyLimitStrategy.class)); private static final int BIG_START_SIZE = 5; protected static final int MAX_BARRIER_SIZE = 2500; diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java index 876d6d2..1078a6b 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/graphson/GraphSONModule.java @@ -41,6 +41,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.Partit import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SubgraphStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.MatchAlgorithmStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.EarlyLimitStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.FilterRankingStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IdentityRemovalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy; @@ -181,6 +182,7 @@ abstract class GraphSONModule extends TinkerPopJacksonModule { LambdaRestrictionStrategy.class, ReadOnlyStrategy.class, StandardVerificationStrategy.class, + EarlyLimitStrategy.class, // GraphFilterStrategy.class, VertexProgramStrategy.class @@ -297,6 +299,7 @@ abstract class GraphSONModule extends TinkerPopJacksonModule { LambdaRestrictionStrategy.class, ReadOnlyStrategy.class, StandardVerificationStrategy.class, + EarlyLimitStrategy.class, // GraphFilterStrategy.class, VertexProgramStrategy.class @@ -396,6 +399,7 @@ abstract class GraphSONModule extends TinkerPopJacksonModule { LambdaRestrictionStrategy.class, ReadOnlyStrategy.class, StandardVerificationStrategy.class, + EarlyLimitStrategy.class, // GraphFilterStrategy.class, VertexProgramStrategy.class @@ -504,6 +508,7 @@ abstract class GraphSONModule extends TinkerPopJacksonModule { LambdaRestrictionStrategy.class, ReadOnlyStrategy.class, StandardVerificationStrategy.class, + EarlyLimitStrategy.class, // GraphFilterStrategy.class, VertexProgramStrategy.class diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java index 459c04f..d88a8c0 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java @@ -51,6 +51,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.Partit import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SubgraphStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.MatchAlgorithmStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.EarlyLimitStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.FilterRankingStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IdentityRemovalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy; @@ -235,7 +236,7 @@ public enum GryoVersion { add(GryoTypeReg.of(Collections.singleton(null).getClass(), 54)); add(GryoTypeReg.of(Collections.singletonList(null).getClass(), 24)); add(GryoTypeReg.of(Collections.singletonMap(null, null).getClass(), 23)); - add(GryoTypeReg.of(Types.COLLECTIONS_SYNCHRONIZED_MAP, 185, new UtilSerializers.SynchronizedMapSerializer())); // ***LAST ID*** + add(GryoTypeReg.of(Types.COLLECTIONS_SYNCHRONIZED_MAP, 185, new UtilSerializers.SynchronizedMapSerializer())); add(GryoTypeReg.of(Contains.class, 49)); add(GryoTypeReg.of(Currency.class, 40)); add(GryoTypeReg.of(Date.class, 38)); @@ -335,6 +336,7 @@ public enum GryoVersion { add(GryoTypeReg.of(GraphFilterStrategy.class, 157)); add(GryoTypeReg.of(LambdaRestrictionStrategy.class, 158)); add(GryoTypeReg.of(ReadOnlyStrategy.class, 159)); + add(GryoTypeReg.of(EarlyLimitStrategy.class, 186)); // ***LAST ID*** add(GryoTypeReg.of(MatchStep.CountMatchAlgorithm.class, 160)); add(GryoTypeReg.of(MatchStep.GreedyMatchAlgorithm.class, 164)); @@ -412,7 +414,7 @@ public enum GryoVersion { add(GryoTypeReg.of(Collections.singleton(null).getClass(), 54)); add(GryoTypeReg.of(Collections.singletonList(null).getClass(), 24)); add(GryoTypeReg.of(Collections.singletonMap(null, null).getClass(), 23)); - add(GryoTypeReg.of(Types.COLLECTIONS_SYNCHRONIZED_MAP, 185, new UtilSerializers.SynchronizedMapSerializer())); // ***LAST ID*** + add(GryoTypeReg.of(Types.COLLECTIONS_SYNCHRONIZED_MAP, 185, new UtilSerializers.SynchronizedMapSerializer())); add(GryoTypeReg.of(Contains.class, 49)); add(GryoTypeReg.of(Currency.class, 40)); add(GryoTypeReg.of(Date.class, 38)); @@ -553,6 +555,7 @@ public enum GryoVersion { add(GryoTypeReg.of(GraphFilterStrategy.class, 157)); add(GryoTypeReg.of(LambdaRestrictionStrategy.class, 158)); add(GryoTypeReg.of(ReadOnlyStrategy.class, 159)); + add(GryoTypeReg.of(EarlyLimitStrategy.class, 186)); // ***LAST ID*** add(GryoTypeReg.of(MatchStep.CountMatchAlgorithm.class, 160)); add(GryoTypeReg.of(MatchStep.GreedyMatchAlgorithm.class, 167)); // skip 171, 172 to sync with tp33 diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategyTest.java new file mode 100644 index 0000000..8be6386 --- /dev/null +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategyTest.java @@ -0,0 +1,101 @@ +/* + * 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.optimization; + +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.GraphTraversal; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; +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; + +/** + * @author Daniel Kuppitz (http://gremlin.guru) + */ +@RunWith(Parameterized.class) +public class EarlyLimitStrategyTest { + + @Parameterized.Parameter() + public Traversal original; + + @Parameterized.Parameter(value = 1) + public Traversal optimized; + + @Parameterized.Parameter(value = 2) + public Collection<TraversalStrategy> otherStrategies; + + @Test + public void doTest() { + final TraversalStrategies strategies = new DefaultTraversalStrategies(); + strategies.addStrategies(EarlyLimitStrategy.instance()); + for (final TraversalStrategy strategy : this.otherStrategies) { + strategies.addStrategies(strategy); + if (strategy instanceof ProfileStrategy) { + final TraversalStrategies os = new DefaultTraversalStrategies(); + os.addStrategies(ProfileStrategy.instance()); + this.optimized.asAdmin().setStrategies(os); + this.optimized.asAdmin().applyStrategies(); + } + } + this.original.asAdmin().setStrategies(strategies); + this.original.asAdmin().applyStrategies(); + assertEquals(this.optimized, this.original); + } + + @Parameterized.Parameters(name = "{0}") + public static Iterable<Object> generateTestParameters() { + return Arrays.asList(new Object[][]{ + {__.out().valueMap().limit(1), __.out().limit(1).valueMap(), Collections.emptyList()}, + {__.V().out().valueMap().limit(1), __.V().out().limit(1).valueMap(), Collections.singleton(LazyBarrierStrategy.instance())}, + {__.out().out().limit(1).in().in(), __.out().out().limit(1).in().barrier(LazyBarrierStrategy.MAX_BARRIER_SIZE).in(), Collections.singleton(LazyBarrierStrategy.instance())}, + {__.out().has("name","marko").limit(1).in().in(), __.out().has("name","marko").limit(1).in().in(), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).limit(1), __.out().limit(1).map(__.identity()).map(__.identity()), Collections.singleton(LazyBarrierStrategy.instance())}, + {__.out().map(__.identity()).map(__.identity()).limit(1).as("a"), __.out().limit(1).map(__.identity()).map(__.identity()).as("a"), Collections.singleton(LazyBarrierStrategy.instance())}, + {__.out().map(__.identity()).map(__.identity()).limit(2).out().map(__.identity()).map(__.identity()).limit(1), __.out().limit(2).map(__.identity()).map(__.identity()).out().limit(1).map(__.identity()).map(__.identity()), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).limit(2).map(__.identity()).map(__.identity()).limit(1), __.out().limit(1).map(__.identity()).map(__.identity()).map(__.identity()).map(__.identity()), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(5, 20).map(__.identity()).map(__.identity()).range(5, 10), __.out().range(10, 15).map(__.identity()).map(__.identity()).map(__.identity()).map(__.identity()), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(50, 100).map(__.identity()).map(__.identity()).range(10, 50), __.out().range(60, 100).map(__.identity()).map(__.identity()).map(__.identity()).map(__.identity()), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(50, 100).map(__.identity()).map(__.identity()).range(10, 60), __.out().range(60, 100).map(__.identity()).map(__.identity()).map(__.identity()).map(__.identity()), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(50, -1).map(__.identity()).map(__.identity()).range(10, 60), __.out().range(60, 110).map(__.identity()).map(__.identity()).map(__.identity()).map(__.identity()), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(50, 100).map(__.identity()).map(__.identity()).range(10, -1), __.out().range(60, 100).map(__.identity()).map(__.identity()).map(__.identity()).map(__.identity()), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(50, 100).as("a").map(__.identity()).map(__.identity()).range(10, -1).as("b"), __.out().range(60, 100).map(__.identity()).map(__.identity()).as("a").map(__.identity()).map(__.identity()).as("b"), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(50, 100).map(__.identity()).map(__.identity()).range(50, -1), __.out().none(), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(50, 100).map(__.identity()).map(__.identity()).range(60, -1), __.out().none(), Collections.emptyList()}, + {__.out().map(__.identity()).map(__.identity()).range(50, 100).as("a").map(__.identity()).map(__.identity()).range(60, -1).as("b"), __.out().none(), Collections.emptyList()}, + {__.out().range(50, 100).store("a").range(50, -1), __.out().range(50, 100).store("a").none(), Collections.emptyList()}, + {__.out().range(50, 100).store("a").range(50, -1).cap("a"), ((GraphTraversal) __.out().range(50, 100).store("a").none()).cap("a"), Collections.emptyList()}, + {__.out().range(50, 100).map(__.identity()).range(50, -1).profile(), __.out().none().profile(), Collections.singleton(ProfileStrategy.instance())}, + {__.out().store("a").limit(10), __.out().limit(10).store("a"), Collections.emptyList()}, + {__.out().aggregate("a").limit(10), __.out().aggregate("a").limit(10), Collections.emptyList()}, + {__.V().branch(__.label()).option("person", __.out("knows").valueMap().limit(1)).option("software", __.out("created").valueMap().limit(2).fold()), + __.V().branch(__.label()).option("person", __.out("knows").limit(1).valueMap()).option("software", __.out("created").limit(2).valueMap().fold()), Collections.emptyList()} + }); + } +} diff --git a/gremlin-python/src/main/jython/gremlin_python/process/strategies.py b/gremlin-python/src/main/jython/gremlin_python/process/strategies.py index f5ba9fb..6bb9ab9 100644 --- a/gremlin-python/src/main/jython/gremlin_python/process/strategies.py +++ b/gremlin-python/src/main/jython/gremlin_python/process/strategies.py @@ -168,6 +168,9 @@ class GraphFilterStrategy(TraversalStrategy): def __init__(self): TraversalStrategy.__init__(self) +class EarlyLimitStrategy(TraversalStrategy): + def __init__(self): + TraversalStrategy.__init__(self) ########################### # VERIFICATION STRATEGIES # diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java index e0018fc..c278e89 100644 --- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java +++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java @@ -19,6 +19,7 @@ package org.apache.tinkerpop.gremlin.tinkergraph.structure; import org.apache.tinkerpop.gremlin.process.computer.Computer; +import org.apache.tinkerpop.gremlin.process.traversal.Order; import org.apache.tinkerpop.gremlin.process.traversal.P; import org.apache.tinkerpop.gremlin.process.traversal.Pop; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; @@ -26,6 +27,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.EarlyLimitStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PathRetractionStrategy; import org.apache.tinkerpop.gremlin.structure.*; import org.apache.tinkerpop.gremlin.structure.io.graphml.GraphMLIo; @@ -122,90 +124,19 @@ public class TinkerGraphPlayTest { @Ignore public void testPlayDK() throws Exception { - final Map<String, String> aliases = new HashMap<>(); - aliases.put("marko","okram"); - final GraphTraversalSource g = TinkerFactory.createModern().traversal(); - /*g.withSideEffect("a", aliases).V().hasLabel("person"). - values("name").as("n"). - optional(select("a").select(select("n"))). - forEachRemaining(System.out::println);*/ - - // shortest path lengths (by summed weight) - g.withSack(0.0).V().has("person", "name", "marko"). - repeat(__.bothE(). - sack(sum). - by("weight"). - otherV(). - group("m"). - by(). - by(sack().min()).as("x"). - // where(P.eq("m")).by(sack()).by(select(select("x"))). // could be that easy, but "x" is unknown here - filter(project("s","x"). - by(sack()). - by(select("m").select(select("x"))). - where("s", P.eq("x"))). - group("p"). - by(). - by(project("path","length"). - by(path().by("name").by("weight")). - by(sack())) - ). - cap("p").unfold(). - group(). - by(select(Column.keys).values("name")). - by(Column.values).next().entrySet(). - forEach(System.out::println); - - System.out.println("---"); - - // longest path lengths (by summed weight) - g.withSack(0.0).V().has("person", "name", "marko"). - repeat(__.bothE().simplePath(). - sack(sum). - by("weight"). - otherV(). - group("m"). - by(). - by(sack().max()).as("x"). - filter(project("s","x"). - by(sack()). - by(select("m").select(select("x"))). - where("s", P.eq("x"))). - group("p"). - by(). - by(project("path","length"). - by(path().by("name").by("weight")). - by(sack())) - ). - cap("p").unfold(). - group(). - by(select(Column.keys).values("name")). - by(Column.values).next().entrySet(). - forEach(System.out::println); - - System.out.println("---"); + Graph graph = TinkerGraph.open(); + graph.io(GraphMLIo.build()).readGraph("../data/grateful-dead.xml"); - // all shortest paths (by summed weight) - g.withSack(0.0).V().as("a"). - repeat(__.bothE(). - sack(sum). - by("weight"). - otherV().as("b"). - group("m"). - by(select("a","b").by("name")). - by(sack().min()). - filter(project("s","x"). - by(sack()). - by(select("m").select(select("a", "b").by("name"))). - where("s", P.eq("x"))). - group("p"). - by(select("a","b").by("name")). - by(map(union(path().by("name").by("weight"), sack()).fold())) - ). - cap("p").unfold(). - order(). - by(select(Column.keys).select("a")). - by(select(Column.keys).select("b")). + GraphTraversalSource g = graph.traversal();//.withoutStrategies(EarlyLimitStrategy.class); + g.V().has("name", "Bob_Dylan").in("sungBy").as("a"). + repeat(out().order().by(Order.shuffle).simplePath().from("a")). + until(out("writtenBy").has("name", "Johnny_Cash")).limit(1).as("b"). + repeat(out().order().by(Order.shuffle).as("c").simplePath().from("b").to("c")). + until(out("sungBy").has("name", "Grateful_Dead")).limit(1). + path().from("a").unfold(). + <List<String>>project("song", "artists"). + by("name"). + by(__.coalesce(out("sungBy", "writtenBy").dedup().values("name"), constant("Unknown")).fold()). forEachRemaining(System.out::println); }
