You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by sp...@apache.org on 2020/05/07 14:54:28 UTC
[tinkerpop] 12/14: TINKERPOP-1682 Account for value traversal in
group() with by() optimization
This is an automated email from the ASF dual-hosted git repository.
spmallette pushed a commit to branch TINKERPOP-1682
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit 1f33554ffb118247f4ee6a9803c6d6957eaf4faa
Author: Stephen Mallette <sp...@genoprime.com>
AuthorDate: Wed May 6 14:15:49 2020 -0400
TINKERPOP-1682 Account for value traversal in group() with by() optimization
Extracted common group() step methods to a Grouping interface. Reverted changes to test semantics that were put in place after rebase and modified ByModulatorOptimizationstrategy to support the original semantics.
---
docs/src/upgrade/release-3.5.x.asciidoc | 8 ++
.../gremlin/process/traversal/step/Grouping.java | 100 +++++++++++++++++++++
.../process/traversal/step/TraversalParent.java | 3 +-
.../process/traversal/step/map/GroupStep.java | 78 ++++------------
.../step/sideEffect/GroupSideEffectStep.java | 29 ++++--
.../ByModulatorOptimizationStrategy.java | 75 +++++++++++-----
.../ByModulatorOptimizationStrategyTest.java | 71 +++++++++++++--
gremlin-test/features/map/Select.feature | 4 +-
.../process/traversal/step/map/SelectTest.java | 11 +--
9 files changed, 267 insertions(+), 112 deletions(-)
diff --git a/docs/src/upgrade/release-3.5.x.asciidoc b/docs/src/upgrade/release-3.5.x.asciidoc
index 8621bb1..e513d4e 100644
--- a/docs/src/upgrade/release-3.5.x.asciidoc
+++ b/docs/src/upgrade/release-3.5.x.asciidoc
@@ -201,6 +201,14 @@ formerly held the cache for these side-effects, no longer have any effect and ca
See: link:https://issues.apache.org/jira/browse/TINKERPOP-2269[TINKERPOP-2269]
+==== ByModulatorOptimizationStrategy
+
+The new `ByModulatorOptimizationStrategy` attempts to re-write `by()` modulator traversals to use their more optimized
+forms which can provide a major performance improvement. As a simple an example, a traversal like `by(id())` would
+be replaced by `by(id)`, thus replacing a step-based traversal with a token-based traversal.
+
+Note that this
+
==== Python 2.x Support
The gremlinpython module no longer supports Python 2.x. Users must use Python 3 going forward. For the most part, from
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/Grouping.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/Grouping.java
new file mode 100644
index 0000000..1e15758
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/Grouping.java
@@ -0,0 +1,100 @@
+/*
+ * 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.step;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.ColumnTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.FunctionTraverser;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.IdentityTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.TokenTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.ValueTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.GroupStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.LambdaMapStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.GroupSideEffectStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep;
+
+import java.util.List;
+import java.util.Map;
+
+/**
+ * An interface for common functionality of {@link GroupStep} and {@link GroupSideEffectStep}.
+ */
+public interface Grouping<S, K, V> {
+
+ /**
+ * Determines if the provided traversal is equal to the key traversal that the {@code Grouping} has.
+ */
+ public Traversal.Admin<S, K> getKeyTraversal();
+
+ /**
+ * Determines if the provided traversal is equal to the value traversal that the {@code Grouping} has.
+ */
+ public Traversal.Admin<S, V> getValueTraversal();
+
+ /**
+ * Determines the first (non-local) barrier step in the provided traversal. This method is used by {@link GroupStep}
+ * and {@link GroupSideEffectStep} to ultimately determine the reducing bi-operator.
+ *
+ * @param traversal The traversal to inspect.
+ * @return The first non-local barrier step or {@code null} if no such step was found.
+ */
+ public default Barrier determineBarrierStep(final Traversal.Admin<S, V> traversal) {
+ final List<Step> steps = traversal.getSteps();
+ for (int ix = 0; ix < steps.size(); ix++) {
+ final Step step = steps.get(ix);
+ if (step instanceof Barrier && !(step instanceof LocalBarrier)) {
+ final Barrier b = (Barrier) step;
+
+ // when profile() is enabled the step needs to be wrapped up with the barrier so that the timer on
+ // the ProfileStep is properly triggered
+ if (ix < steps.size() - 1 && steps.get(ix + 1) instanceof ProfileStep)
+ return new ProfilingAware.ProfiledBarrier(b, (ProfileStep) steps.get(ix + 1));
+ else
+ return b;
+ }
+ }
+ return null;
+ }
+
+ public default Traversal.Admin<S, V> convertValueTraversal(final Traversal.Admin<S, V> valueTraversal) {
+ if (valueTraversal instanceof ValueTraversal ||
+ valueTraversal instanceof TokenTraversal ||
+ valueTraversal instanceof IdentityTraversal ||
+ valueTraversal instanceof ColumnTraversal ||
+ valueTraversal.getStartStep() instanceof LambdaMapStep && ((LambdaMapStep) valueTraversal.getStartStep()).getMapFunction() instanceof FunctionTraverser) {
+ return (Traversal.Admin<S, V>) __.map(valueTraversal).fold();
+ } else
+ return valueTraversal;
+ }
+
+ public default Map<K, V> doFinalReduction(final Map<K, Object> map, final Traversal.Admin<S, V> valueTraversal) {
+ final Barrier barrierStep = determineBarrierStep(valueTraversal);
+ if (barrierStep != null) {
+ for (final K key : map.keySet()) {
+ valueTraversal.reset();
+ barrierStep.addBarrier(map.get(key));
+ if (valueTraversal.hasNext())
+ map.put(key, valueTraversal.next());
+ }
+ }
+ return (Map<K, V>) map;
+ }
+}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/TraversalParent.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/TraversalParent.java
index 95a2be1..695d297 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/TraversalParent.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/TraversalParent.java
@@ -20,7 +20,6 @@ package org.apache.tinkerpop.gremlin.process.traversal.step;
import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
-import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
import java.util.Collections;
@@ -57,7 +56,7 @@ public interface TraversalParent extends AutoCloseable {
throw new IllegalStateException("This traversal parent does not support the removal of global traversals: " + this.getClass().getCanonicalName());
}
- public default void replaceLocalChild(final Traversal.Admin<?, ?> oldTrversal, final Traversal.Admin<?, ?> newTrversal) {
+ public default void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
throw new IllegalStateException("This traversal parent does not support the replacement of local traversals: " + this.getClass().getCanonicalName());
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupStep.java
index d538195..2213b2e 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupStep.java
@@ -20,21 +20,14 @@
package org.apache.tinkerpop.gremlin.process.traversal.step.map;
import org.apache.tinkerpop.gremlin.process.traversal.Operator;
-import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
-import org.apache.tinkerpop.gremlin.process.traversal.lambda.ColumnTraversal;
-import org.apache.tinkerpop.gremlin.process.traversal.lambda.ValueTraversal;
-import org.apache.tinkerpop.gremlin.process.traversal.lambda.FunctionTraverser;
-import org.apache.tinkerpop.gremlin.process.traversal.lambda.IdentityTraversal;
-import org.apache.tinkerpop.gremlin.process.traversal.lambda.TokenTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.step.Grouping;
import org.apache.tinkerpop.gremlin.process.traversal.step.ProfilingAware;
import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating;
-import org.apache.tinkerpop.gremlin.process.traversal.step.LocalBarrier;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.Barrier;
-import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.GroupSideEffectStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.ReducingBarrierStep;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
@@ -53,7 +46,8 @@ import java.util.function.BinaryOperator;
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
-public final class GroupStep<S, K, V> extends ReducingBarrierStep<S, Map<K, V>> implements ByModulating, TraversalParent, ProfilingAware {
+public final class GroupStep<S, K, V> extends ReducingBarrierStep<S, Map<K, V>>
+ implements ByModulating, TraversalParent, ProfilingAware, Grouping<S, K, V> {
private char state = 'k';
private Traversal.Admin<S, K> keyTraversal;
@@ -70,31 +64,6 @@ public final class GroupStep<S, K, V> extends ReducingBarrierStep<S, Map<K, V>>
}
/**
- * Determines the first (non-local) barrier step in the provided traversal. This method is used by {@link GroupStep}
- * and {@link GroupSideEffectStep} to ultimately determine the reducing bi-operator.
- *
- * @param traversal The traversal to inspect.
- * @return The first non-local barrier step or {@code null} if no such step was found.
- */
- public static <S, V> Barrier determineBarrierStep(final Traversal.Admin<S, V> traversal) {
- final List<Step> steps = traversal.getSteps();
- for (int ix = 0; ix < steps.size(); ix++) {
- final Step step = steps.get(ix);
- if (step instanceof Barrier && !(step instanceof LocalBarrier)) {
- final Barrier b = (Barrier) step;
-
- // when profile() is enabled the step needs to be wrapped up with the barrier so that the timer on
- // the ProfileStep is properly triggered
- if (ix < steps.size() - 1 && steps.get(ix + 1) instanceof ProfileStep)
- return new ProfilingAware.ProfiledBarrier(b, (ProfileStep) steps.get(ix + 1));
- else
- return b;
- }
- }
- return null;
- }
-
- /**
* Reset the {@link Barrier} on the step to be wrapped in a {@link ProfiledBarrier} which can properly start/stop
* the timer on the associated {@link ProfileStep}.
*/
@@ -103,7 +72,17 @@ public final class GroupStep<S, K, V> extends ReducingBarrierStep<S, Map<K, V>>
resetBarrierForProfiling = barrierStep != null;
}
- private void setValueTraversal(final Traversal.Admin<?, ?> kvTraversal) {
+ @Override
+ public Traversal.Admin<S, K> getKeyTraversal() {
+ return this.keyTraversal;
+ }
+
+ @Override
+ public Traversal.Admin<S, V> getValueTraversal() {
+ return this.valueTraversal;
+ }
+
+ private void setValueTraversal(final Traversal.Admin kvTraversal) {
this.valueTraversal = this.integrateChild(convertValueTraversal(kvTraversal));
this.barrierStep = determineBarrierStep(this.valueTraversal);
this.setReducingBiOperator(new GroupBiOperator<>(null == this.barrierStep ? Operator.assign : this.barrierStep.getMemoryComputeKey().getReducer()));
@@ -199,7 +178,7 @@ public final class GroupStep<S, K, V> extends ReducingBarrierStep<S, Map<K, V>>
@Override
public Map<K, V> generateFinalResult(final Map<K, V> object) {
- return GroupStep.doFinalReduction((Map<K, Object>) object, this.valueTraversal);
+ return doFinalReduction((Map<K, Object>) object, this.valueTraversal);
}
///////////////////////
@@ -230,31 +209,4 @@ public final class GroupStep<S, K, V> extends ReducingBarrierStep<S, Map<K, V>>
return mapA;
}
}
-
-
- ///////////////////////
-
- public static <S, E> Traversal.Admin<S, E> convertValueTraversal(final Traversal.Admin<S, E> valueTraversal) {
- if (valueTraversal instanceof ValueTraversal ||
- valueTraversal instanceof TokenTraversal ||
- valueTraversal instanceof IdentityTraversal ||
- valueTraversal instanceof ColumnTraversal ||
- valueTraversal.getStartStep() instanceof LambdaMapStep && ((LambdaMapStep) valueTraversal.getStartStep()).getMapFunction() instanceof FunctionTraverser) {
- return (Traversal.Admin<S, E>) __.map(valueTraversal).fold();
- } else
- return valueTraversal;
- }
-
- public static <K, V> Map<K, V> doFinalReduction(final Map<K, Object> map, final Traversal.Admin<?, V> valueTraversal) {
- final Barrier barrierStep = determineBarrierStep(valueTraversal);
- if (barrierStep != null) {
- for (final K key : map.keySet()) {
- valueTraversal.reset();
- barrierStep.addBarrier(map.get(key));
- if (valueTraversal.hasNext())
- map.put(key, valueTraversal.next());
- }
- }
- return (Map<K, V>) map;
- }
}
\ No newline at end of file
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupSideEffectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupSideEffectStep.java
index c9526f8..9467467 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupSideEffectStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupSideEffectStep.java
@@ -24,13 +24,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
import org.apache.tinkerpop.gremlin.process.traversal.step.Barrier;
import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating;
+import org.apache.tinkerpop.gremlin.process.traversal.step.Grouping;
import org.apache.tinkerpop.gremlin.process.traversal.step.ProfilingAware;
import org.apache.tinkerpop.gremlin.process.traversal.step.SideEffectCapable;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.GroupStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
-import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
import org.apache.tinkerpop.gremlin.util.function.HashMapSupplier;
@@ -44,7 +44,8 @@ import java.util.Set;
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
-public final class GroupSideEffectStep<S, K, V> extends SideEffectStep<S> implements SideEffectCapable<Map<K, ?>, Map<K, V>>, TraversalParent, ByModulating, ProfilingAware {
+public final class GroupSideEffectStep<S, K, V> extends SideEffectStep<S>
+ implements SideEffectCapable<Map<K, ?>, Map<K, V>>, TraversalParent, ByModulating, ProfilingAware, Grouping<S, K, V> {
private char state = 'k';
private Traversal.Admin<S, K> keyTraversal;
@@ -58,7 +59,7 @@ public final class GroupSideEffectStep<S, K, V> extends SideEffectStep<S> implem
super(traversal);
this.sideEffectKey = sideEffectKey;
this.valueTraversal = this.integrateChild(__.fold().asAdmin());
- this.barrierStep = GroupStep.determineBarrierStep(this.valueTraversal);
+ this.barrierStep = determineBarrierStep(this.valueTraversal);
this.getTraversal().getSideEffects().registerIfAbsent(this.sideEffectKey, HashMapSupplier.instance(),
new GroupStep.GroupBiOperator<>(null == this.barrierStep ?
Operator.assign :
@@ -74,9 +75,19 @@ public final class GroupSideEffectStep<S, K, V> extends SideEffectStep<S> implem
resetBarrierForProfiling = barrierStep != null;
}
- private void setValueTraversal(final Traversal.Admin<?, ?> valueTraversal) {
- this.valueTraversal = this.integrateChild(GroupStep.convertValueTraversal(valueTraversal));
- this.barrierStep = GroupStep.determineBarrierStep(this.valueTraversal);
+ @Override
+ public Traversal.Admin<S, K> getKeyTraversal() {
+ return this.keyTraversal;
+ }
+
+ @Override
+ public Traversal.Admin<S, V> getValueTraversal() {
+ return this.valueTraversal;
+ }
+
+ private void setValueTraversal(final Traversal.Admin valueTraversal) {
+ this.valueTraversal = this.integrateChild(convertValueTraversal(valueTraversal));
+ this.barrierStep = determineBarrierStep(this.valueTraversal);
this.getTraversal().getSideEffects().register(this.sideEffectKey, null,
new GroupStep.GroupBiOperator<>(null == this.barrierStep ?
Operator.assign :
@@ -113,7 +124,7 @@ public final class GroupSideEffectStep<S, K, V> extends SideEffectStep<S> implem
// reset the barrierStep as there are now ProfileStep instances present and the timers won't start right
// without specific configuration through wrapping both the Barrier and ProfileStep in ProfiledBarrier
if (resetBarrierForProfiling) {
- barrierStep = GroupStep.determineBarrierStep(valueTraversal);
+ barrierStep = determineBarrierStep(valueTraversal);
// the barrier only needs to be reset once
resetBarrierForProfiling = false;
@@ -158,7 +169,7 @@ public final class GroupSideEffectStep<S, K, V> extends SideEffectStep<S> implem
if (null != this.keyTraversal)
clone.keyTraversal = this.keyTraversal.clone();
clone.valueTraversal = this.valueTraversal.clone();
- clone.barrierStep = GroupStep.determineBarrierStep(clone.valueTraversal);
+ clone.barrierStep = determineBarrierStep(clone.valueTraversal);
return clone;
}
@@ -179,6 +190,6 @@ public final class GroupSideEffectStep<S, K, V> extends SideEffectStep<S> implem
@Override
public Map<K, V> generateFinalResult(final Map<K, ?> object) {
- return GroupStep.doFinalReduction((Map<K, Object>) object, this.valueTraversal);
+ return doFinalReduction((Map<K, Object>) object, this.valueTraversal);
}
}
\ No newline at end of file
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategy.java
index 4a5cef1..579dcf4 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategy.java
@@ -25,15 +25,20 @@ import org.apache.tinkerpop.gremlin.process.traversal.lambda.IdentityTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.lambda.TokenTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.lambda.ValueTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating;
+import org.apache.tinkerpop.gremlin.process.traversal.step.Grouping;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.FoldStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.GroupStep;
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.PropertiesStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.GroupSideEffectStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.IdentityStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
import org.apache.tinkerpop.gremlin.structure.PropertyType;
import org.apache.tinkerpop.gremlin.structure.T;
+import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
@@ -45,17 +50,24 @@ import java.util.Set;
* <p/>
*
* @author Daniel Kuppitz (http://gremlin.guru)
+ * @author Stephen Mallette (http://stephen.genoprime.com)
* @example <pre>
- * __.path().by(id()) // is replaced by __.path().by(id)
- * __.dedup().by(label()) // is replaced by __.dedup().by(label)
- * __.order().by(values("name")) // is replaced by __.order().by("name")
+ * __.path().by(id()) // is replaced by __.path().by(id)
+ * __.dedup().by(label()) // is replaced by __.dedup().by(label)
+ * __.order().by(values("name")) // is replaced by __.order().by("name")
+ * __.group().by().by(values("name").fold()) // is replaced by __.group().by("name")
* </pre>
*/
public final class ByModulatorOptimizationStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy>
implements TraversalStrategy.OptimizationStrategy {
private static final ByModulatorOptimizationStrategy INSTANCE = new ByModulatorOptimizationStrategy();
- private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Collections.singletonList(IdentityRemovalStrategy.class));
+
+ // when PathProcessorStrategy is present for withComputer() you need to ensure it always executes first because
+ // it does some manipulation to select().by(t) in some cases to turn it to select().map(t) in which case this
+ // strategy has nothing to do. if it were to occur first then that optimization wouldn't work as expected.
+ private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Arrays.asList(
+ PathProcessorStrategy.class, IdentityRemovalStrategy.class));
private ByModulatorOptimizationStrategy() {
}
@@ -69,24 +81,28 @@ public final class ByModulatorOptimizationStrategy extends AbstractTraversalStra
final List<Step> steps = traversal.asAdmin().getSteps();
if (steps.size() == 1) {
final Step singleStep = steps.get(0);
- if (singleStep instanceof PropertiesStep) {
- final PropertiesStep ps = (PropertiesStep) singleStep;
- if (ps.getReturnType().equals(PropertyType.VALUE) && ps.getPropertyKeys().length == 1) {
- step.replaceLocalChild(traversal, new ValueTraversal<>(ps.getPropertyKeys()[0]));
- }
- } else if (singleStep instanceof IdStep) {
- step.replaceLocalChild(traversal, new TokenTraversal<>(T.id));
- } else if (singleStep instanceof LabelStep) {
- step.replaceLocalChild(traversal, new TokenTraversal<>(T.label));
+ optimizeForStep(step, traversal, singleStep);
+ }
+ }
+
+ private void optimizeForStep(final TraversalParent step, final Traversal.Admin<?, ?> traversal, final Step singleStep) {
+ if (singleStep instanceof PropertiesStep) {
+ final PropertiesStep ps = (PropertiesStep) singleStep;
+ if (ps.getReturnType().equals(PropertyType.VALUE) && ps.getPropertyKeys().length == 1) {
+ step.replaceLocalChild(traversal, new ValueTraversal<>(ps.getPropertyKeys()[0]));
+ }
+ } else if (singleStep instanceof IdStep) {
+ step.replaceLocalChild(traversal, new TokenTraversal<>(T.id));
+ } else if (singleStep instanceof LabelStep) {
+ step.replaceLocalChild(traversal, new TokenTraversal<>(T.label));
/* todo: this fails for `Property`s (e.g. outE().property().as("a").select("a").by(key/value))
- } else if (singleStep instanceof PropertyKeyStep) {
- step.setModulateByTraversal(n, new TokenTraversal<>(T.key));
- } else if (singleStep instanceof PropertyValueStep) {
- step.setModulateByTraversal(n, new TokenTraversal<>(T.value));
+ } else if (singleStep instanceof PropertyKeyStep) {
+ step.setModulateByTraversal(n, new TokenTraversal<>(T.key));
+ } else if (singleStep instanceof PropertyValueStep) {
+ step.setModulateByTraversal(n, new TokenTraversal<>(T.value));
*/
- } else if (singleStep instanceof IdentityStep) {
- step.replaceLocalChild(traversal, new IdentityTraversal<>());
- }
+ } else if (singleStep instanceof IdentityStep) {
+ step.replaceLocalChild(traversal, new IdentityTraversal<>());
}
}
@@ -95,8 +111,23 @@ public final class ByModulatorOptimizationStrategy extends AbstractTraversalStra
final Step step = traversal.getParent().asStep();
if (step instanceof ByModulating && step instanceof TraversalParent) {
final TraversalParent byModulatingStep = (TraversalParent) step;
- for (final Traversal.Admin<?, ?> byModulatingTraversal : byModulatingStep.getLocalChildren()) {
- optimizeByModulatingTraversal(byModulatingStep, byModulatingTraversal);
+ if (step instanceof Grouping) {
+ final Grouping grouping = (Grouping) step;
+ optimizeByModulatingTraversal(byModulatingStep, grouping.getKeyTraversal());
+
+ // the value by() needs different handling because by(Traversal) only equals by(String) or by(T)
+ // if the traversal does a fold().
+ final Traversal.Admin<?, ?> currentValueTraversal = grouping.getValueTraversal();
+ final List<Step> stepsInCurrentValueTraversal = currentValueTraversal.getSteps();
+ if (stepsInCurrentValueTraversal.size() == 1 && stepsInCurrentValueTraversal.get(0) instanceof IdentityStep)
+ optimizeForStep(byModulatingStep, currentValueTraversal, stepsInCurrentValueTraversal.get(0));
+ else if (stepsInCurrentValueTraversal.size() == 2 && stepsInCurrentValueTraversal.get(1) instanceof FoldStep)
+ optimizeForStep(byModulatingStep, currentValueTraversal, stepsInCurrentValueTraversal.get(0));
+
+ } else {
+ for (final Traversal.Admin<?, ?> byModulatingTraversal : byModulatingStep.getLocalChildren()) {
+ optimizeByModulatingTraversal(byModulatingStep, byModulatingTraversal);
+ }
}
}
}
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategyTest.java
index d681447..23c4576 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategyTest.java
@@ -34,6 +34,7 @@ import java.util.ArrayList;
import java.util.List;
import static org.apache.tinkerpop.gremlin.process.traversal.Operator.assign;
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.values;
import static org.junit.Assert.assertEquals;
/**
@@ -51,7 +52,7 @@ public class ByModulatorOptimizationStrategyTest {
@Parameterized.Parameters(name = "{0}")
public static Iterable<Object[]> generateTestParameters() {
- final List<Object[]> result = new ArrayList<>();
+ final List<Object[]> originalAndOptimized = new ArrayList<>();
final GraphTraversal[] baseTraversals = new GraphTraversal[]{
__.aggregate("x"),
__.dedup(),
@@ -77,15 +78,15 @@ public class ByModulatorOptimizationStrategyTest {
};
for (final Traversal traversal : baseTraversals) {
- result.add(new Traversal[]{
- ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.values("name")),
+ originalAndOptimized.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(values("name")),
((GraphTraversal) traversal.asAdmin().clone()).by("name"),
});
- result.add(new Traversal[]{
+ originalAndOptimized.add(new Traversal[]{
((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.id()),
((GraphTraversal) traversal.asAdmin().clone()).by(T.id),
});
- result.add(new Traversal[]{
+ originalAndOptimized.add(new Traversal[]{
((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.label()),
((GraphTraversal) traversal.asAdmin().clone()).by(T.label),
});
@@ -97,15 +98,15 @@ public class ByModulatorOptimizationStrategyTest {
((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.value()),
((GraphTraversal) traversal.asAdmin().clone()).by(T.value),
});*/
- result.add(new Traversal[]{
+ originalAndOptimized.add(new Traversal[]{
((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.identity()),
((GraphTraversal) traversal.asAdmin().clone()).by(),
});
}
- result.add(new Traversal[]{
+ originalAndOptimized.add(new Traversal[]{
__.project("a", "b", "c", "d", "e")
- .by(__.values("name"))
+ .by(values("name"))
.by(__.id())
.by(__.label())
.by(__.identity())
@@ -118,7 +119,59 @@ public class ByModulatorOptimizationStrategyTest {
.by(__.outE().count())
});
- return result;
+ final GraphTraversal[] baseGroupTraversals = new GraphTraversal[]{
+ __.group().by("age"),
+ __.group("x").by("age"),
+ };
+
+ for (final Traversal traversal : baseGroupTraversals) {
+ originalAndOptimized.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(values("name").fold()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by("name"),
+ });
+ originalAndOptimized.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.id().fold()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(T.id),
+ });
+ originalAndOptimized.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.label().fold()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(T.label),
+ });
+ /*result.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.key().fold()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(T.key),
+ });
+ result.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.value().fold()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(T.value),
+ });*/
+ originalAndOptimized.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.identity()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(),
+ });
+ }
+
+ originalAndOptimized.add(new Traversal[]{
+ __.group().by(values("age")).by(values("name")),
+ __.group().by("age").by(values("name"))
+ });
+
+ originalAndOptimized.add(new Traversal[]{
+ __.group("x").by(values("age")).by(values("name")),
+ __.group("x").by("age").by(values("name"))
+ });
+
+ originalAndOptimized.add(new Traversal[]{
+ __.group().by(values("age")).by(values("name").fold()),
+ __.group().by("age").by("name")
+ });
+
+ originalAndOptimized.add(new Traversal[]{
+ __.group("x").by(values("age")).by(values("name").fold()),
+ __.group("x").by("age").by("name")
+ });
+
+ return originalAndOptimized;
}
private void applyByModulatorOptimizationStrategy(final Traversal traversal) {
diff --git a/gremlin-test/features/map/Select.feature b/gremlin-test/features/map/Select.feature
index bdd2233..0d4913a 100644
--- a/gremlin-test/features/map/Select.feature
+++ b/gremlin-test/features/map/Select.feature
@@ -205,14 +205,14 @@ Feature: Step - select()
| v[ripple] |
| v[peter] |
- Scenario: g_VX1X_groupXaX_byXconstantXaXX_byXvaluesXnameXunfoldX_selectXaX_selectXaX
+ Scenario: g_VX1X_groupXaX_byXconstantXaXX_byXnameX_selectXaX_selectXaX
Given the modern graph
And using the parameter v1Id defined as "v[marko].id"
And the traversal of
"""
g.V(v1Id).group("a").
by(__.constant("a")).
- by(__.values("name").unfold()).
+ by(__.values("name")).
barrier().
select("a").select("a")
"""
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectTest.java
index a1db3ca..0f5afbd 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectTest.java
@@ -38,6 +38,7 @@ import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
+import java.util.stream.Stream;
import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.CREW;
import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN;
@@ -82,7 +83,7 @@ public abstract class SelectTest extends AbstractGremlinProcessTest {
public abstract Traversal<Vertex, Vertex> get_g_V_chooseXoutE_count_isX0X__asXaX__asXbXX_chooseXselectXaX__selectXaX__selectXbXX();
- public abstract Traversal<Vertex, String> get_g_VX1X_groupXaX_byXconstantXaXX_byXvaluesXnameXunfoldX_selectXaX_selectXaX(final Object v1Id);
+ public abstract Traversal<Vertex, String> get_g_VX1X_groupXaX_byXconstantXaXX_byXnameX_selectXaX_selectXaX(final Object v1Id);
public abstract Traversal<Vertex, Long> get_g_V_asXaX_groupXmX_by_byXbothE_countX_barrier_selectXmX_selectXselectXaXX();
@@ -376,8 +377,8 @@ public abstract class SelectTest extends AbstractGremlinProcessTest {
@Test
@LoadGraphWith(MODERN)
- public void g_VX1X_groupXaX_byXconstantXaXX_byXvaluesXnameXunfoldX_selectXaX_selectXaX() {
- final Traversal<Vertex, String> traversal = get_g_VX1X_groupXaX_byXconstantXaXX_byXvaluesXnameXunfoldX_selectXaX_selectXaX(convertToVertexId("marko"));
+ public void g_VX1X_groupXaX_byXconstantXaXX_byXnameX_selectXaX_selectXaX() {
+ final Traversal<Vertex, String> traversal = get_g_VX1X_groupXaX_byXconstantXaXX_byXnameX_selectXaX_selectXaX(convertToVertexId("marko"));
printTraversalForm(traversal);
assertTrue(traversal.hasNext());
assertEquals("marko", traversal.next());
@@ -888,8 +889,8 @@ public abstract class SelectTest extends AbstractGremlinProcessTest {
}
@Override
- public Traversal<Vertex, String> get_g_VX1X_groupXaX_byXconstantXaXX_byXvaluesXnameXunfoldX_selectXaX_selectXaX(final Object v1Id) {
- return g.V(v1Id).group("a").by(__.constant("a")).by(__.values("name").unfold())
+ public Traversal<Vertex, String> get_g_VX1X_groupXaX_byXconstantXaXX_byXnameX_selectXaX_selectXaX(final Object v1Id) {
+ return g.V(v1Id).group("a").by(__.constant("a")).by(__.values("name"))
.barrier() // TODO: this barrier() should not be necessary
.select("a").select("a");
}