tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ok...@apache.org
Subject [3/7] incubator-tinkerpop git commit: added OrderLimitStrategy which finds order()...limit(x) patterns. It then tells OrderStep to order-then-limit. This is a potentially massive optimization in OLAP where if you do order().limit(5), the max number of tr
Date Thu, 17 Mar 2016 13:17:56 GMT
added OrderLimitStrategy which finds order()...limit(x) patterns. It then tells OrderStep to
order-then-limit. This is a potentially massive optimization in OLAP where if you do order().limit(5),
the max number of traversers coming to the master traversal, is 5 * numberOfWorkers instead
of the full set of traversers. Added OrderBiOperator which is a Memory reducer which handles
this in OLAP. Added test cases to make this pretty. Added this as a default strategy in the
GlobalCache. Currently OrderLimitStrategy is only for OLAP -- we could make it for OLTP, but
we would have to write our own custom Collections.sort() that has a size limit.


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

Branch: refs/heads/master
Commit: a67567e0ce627a5fa313d4be0a0f5b9f6ad65584
Parents: 3ee1548
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Tue Mar 15 11:57:54 2016 -0600
Committer: Marko A. Rodriguez <okrammarko@gmail.com>
Committed: Tue Mar 15 11:57:54 2016 -0600

----------------------------------------------------------------------
 .../gremlin/process/computer/GraphFilter.java   |  2 +-
 .../traversal/TraversalVertexProgram.java       | 34 ++++++--
 .../process/traversal/TraversalStrategies.java  |  2 +
 .../traversal/step/map/OrderGlobalStep.java     | 57 ++++++++++++-
 .../traversal/step/map/OrderLocalStep.java      |  2 +-
 .../optimization/OrderLimitStrategy.java        | 87 ++++++++++++++++++++
 .../ComputerVerificationStrategy.java           |  2 +-
 .../traversal/traverser/util/TraverserSet.java  |  9 +-
 .../process/traversal/util/TraversalHelper.java | 68 +--------------
 .../gremlin/structure/io/gryo/GryoMapper.java   |  4 +-
 .../process/util/TraversalHelperTest.java       | 14 ++--
 .../traversal/step/map/GroovyOrderTest.groovy   |  5 ++
 .../process/traversal/step/map/OrderTest.java   | 23 ++++++
 13 files changed, 220 insertions(+), 89 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilter.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilter.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilter.java
index 0fb700a..c8ce53b 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilter.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilter.java
@@ -68,7 +68,7 @@ public final class GraphFilter implements Cloneable, Serializable {
     //private boolean allowAllRemainingEdges = false;
 
     public void setVertexFilter(final Traversal<Vertex, Vertex> vertexFilter) {
-        if (!TraversalHelper.isLocalVertex(vertexFilter.asAdmin()))
+        if (!TraversalHelper.isLocalProperties(vertexFilter.asAdmin()))
             throw GraphComputer.Exceptions.vertexFilterAccessesIncidentEdges(vertexFilter);
         this.vertexFilter = vertexFilter.asAdmin().clone();
     }

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
index 92edf58..da51f72 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/TraversalVertexProgram.java
@@ -43,7 +43,17 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.Barrier;
 import org.apache.tinkerpop.gremlin.process.traversal.step.LocalBarrier;
 import org.apache.tinkerpop.gremlin.process.traversal.step.MapReducer;
 import org.apache.tinkerpop.gremlin.process.traversal.step.MemoryComputing;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.HasStep;
+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.GraphStep;
+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.map.PropertyKeyStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertyMapStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertyValueStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.SackStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.ReducingBarrierStep;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.VertexProgramStrategy;
@@ -299,9 +309,7 @@ public final class TraversalVertexProgram implements VertexProgram<TraverserSet<
             if (traverser.isHalted()) {
                 traverser.asAdmin().detach();
                 haltedTraversers.add(traverser);
-            } else if (traverser.get() instanceof Attachable &&
-                    !(traverser.get() instanceof Path) &&
-                    !TraversalHelper.isLocalElement(this.traversalMatrix.getStepById(traverser.getStepId())))
{  // this is so that patterns like order().name work as expected.
+            } else if (this.isRemoteTraverser(traverser)) {  // this is so that patterns
like order().name work as expected.
                 traverser.asAdmin().detach();
                 remoteActiveTraversers.add(traverser);
             } else {
@@ -312,8 +320,8 @@ public final class TraversalVertexProgram implements VertexProgram<TraverserSet<
                             result.asAdmin().detach();
                             haltedTraversers.add(result.asAdmin());
                         } else {
-                            if (result.get() instanceof Attachable) {
-                                traverser.asAdmin().detach();
+                            if (this.isRemoteTraverser(result.asAdmin())) {
+                                result.asAdmin().detach();
                                 remoteActiveTraversers.add(result.asAdmin());
                             } else
                                 localActiveTraversers.add(result.asAdmin());
@@ -330,7 +338,7 @@ public final class TraversalVertexProgram implements VertexProgram<TraverserSet<
                     traverser.asAdmin().detach();
                     haltedTraversers.add(traverser.asAdmin());
                 } else {
-                    if (traverser.get() instanceof Attachable) {
+                    if (this.isRemoteTraverser(traverser.asAdmin())) {
                         traverser.asAdmin().detach();
                         remoteActiveTraversers.add(traverser.asAdmin());
                     } else
@@ -341,6 +349,20 @@ public final class TraversalVertexProgram implements VertexProgram<TraverserSet<
         assert toProcessTraversers.isEmpty();
     }
 
+    private boolean isRemoteTraverser(final Traverser.Admin traverser) {
+        return traverser.get() instanceof Attachable &&
+                !(traverser.get() instanceof Path) &&
+                !isLocalElement(this.traversalMatrix.getStepById(traverser.getStepId()));
+    }
+
+    // TODO: once this is complete (fully known), move to TraversalHelper
+    private static boolean isLocalElement(final Step<?, ?> step) {
+        return step instanceof PropertiesStep || step instanceof PropertyMapStep ||
+                step instanceof IdStep || step instanceof LabelStep || step instanceof SackStep
||
+                step instanceof PropertyKeyStep || step instanceof PropertyValueStep ||
+                step instanceof TailGlobalStep || step instanceof RangeGlobalStep || step
instanceof HasStep;
+    }
+
     @Override
     public Set<VertexComputeKey> getVertexComputeKeys() {
         return VERTEX_COMPUTE_KEYS;

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
----------------------------------------------------------------------
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 274b7a6..7526602 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
@@ -25,6 +25,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.Filt
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IdentityRemovalStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.MatchPredicateStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.OrderLimitStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.RangeByIsCountStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.StandardVerificationStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserGeneratorFactory;
@@ -202,6 +203,7 @@ public interface TraversalStrategies extends Serializable, Cloneable {
                     IdentityRemovalStrategy.instance(),
                     MatchPredicateStrategy.instance(),
                     RangeByIsCountStrategy.instance(),
+                    OrderLimitStrategy.instance(),
                     StandardVerificationStrategy.instance());
             //LambdaRestrictionStrategy.instance(),
             //LazyBarrierStrategy.instance(),

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
index a6bed1f..19a7ea5 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
@@ -18,8 +18,10 @@
  */
 package org.apache.tinkerpop.gremlin.process.traversal.step.map;
 
+import org.apache.tinkerpop.gremlin.process.computer.MemoryComputeKey;
 import org.apache.tinkerpop.gremlin.process.traversal.Order;
 import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
 import org.apache.tinkerpop.gremlin.process.traversal.lambda.IdentityTraversal;
 import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating;
 import org.apache.tinkerpop.gremlin.process.traversal.step.ComparatorHolder;
@@ -31,11 +33,14 @@ import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
 import org.apache.tinkerpop.gremlin.util.function.ChainedComparator;
 import org.javatuples.Pair;
 
+import java.io.Serializable;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
+import java.util.function.BinaryOperator;
 import java.util.stream.Collectors;
 
 /**
@@ -44,7 +49,8 @@ import java.util.stream.Collectors;
 public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBarrierStep<S>
implements ComparatorHolder<S, C>, TraversalParent, ByModulating {
 
     private List<Pair<Traversal.Admin<S, C>, Comparator<C>>> comparators
= new ArrayList<>();
-    private ChainedComparator chainedComparator = null;
+    private ChainedComparator<S, C> chainedComparator = null;
+    private long limit = Long.MAX_VALUE;
 
     public OrderGlobalStep(final Traversal.Admin traversal) {
         super(traversal);
@@ -57,7 +63,11 @@ public final class OrderGlobalStep<S, C extends Comparable> extends
CollectingBa
         if (this.chainedComparator.isShuffle())
             traverserSet.shuffle();
         else
-            traverserSet.sort(this.chainedComparator);
+            traverserSet.sort((Comparator) this.chainedComparator);
+    }
+
+    public void setLimit(final long limit) {
+        this.limit = limit;
     }
 
     @Override
@@ -121,4 +131,47 @@ public final class OrderGlobalStep<S, C extends Comparable> extends
CollectingBa
         this.comparators.stream().map(Pair::getValue0).forEach(TraversalParent.super::integrateChild);
     }
 
+    @Override
+    public MemoryComputeKey<TraverserSet<S>> getMemoryComputeKey() {
+        if (null == this.chainedComparator)
+            this.chainedComparator = new ChainedComparator(true, this.comparators);
+        return MemoryComputeKey.of(this.getId(), new OrderBiOperator(this.chainedComparator,
this.limit), false, true);
+    }
+
+    ////////////////
+
+    public static final class OrderBiOperator implements BinaryOperator<TraverserSet>,
Serializable {
+
+        private ChainedComparator chainedComparator;
+        private long limit;
+
+        private OrderBiOperator() {
+            // for serializers that need a no-arg constructor
+        }
+
+        public OrderBiOperator(final ChainedComparator chainedComparator, final long limit)
{
+            this.chainedComparator = chainedComparator;
+            this.limit = limit;
+        }
+
+        @Override
+        public TraverserSet apply(final TraverserSet setA, final TraverserSet setB) {
+            setA.addAll(setB);
+            if (this.chainedComparator.isShuffle())
+                setA.shuffle();
+            else
+                setA.sort(this.chainedComparator);
+            if (Long.MAX_VALUE != this.limit && setA.bulkSize() > this.limit)
{
+                long counter = 0l;
+                final Iterator<Traverser.Admin> traversers = setA.iterator();
+                while (traversers.hasNext()) {
+                    final Traverser.Admin traverser = traversers.next();
+                    if (counter > this.limit)
+                        traversers.remove();
+                    counter = counter + traverser.bulk();
+                }
+            }
+            return setA;
+        }
+    }
 }

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
index 7d4c2cf..a1c24e7 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
@@ -46,7 +46,7 @@ import java.util.stream.Collectors;
 public final class OrderLocalStep<S, C extends Comparable> extends MapStep<S, S>
implements ComparatorHolder<S, C>, ByModulating, TraversalParent {
 
     private List<Pair<Traversal.Admin<S, C>, Comparator<C>>> comparators
= new ArrayList<>();
-    private ChainedComparator chainedComparator = null;
+    private ChainedComparator<S, C> chainedComparator = null;
 
     public OrderLocalStep(final Traversal.Admin traversal) {
         super(traversal);

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/OrderLimitStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/OrderLimitStrategy.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/OrderLimitStrategy.java
new file mode 100644
index 0000000..98d7ebd
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/OrderLimitStrategy.java
@@ -0,0 +1,87 @@
+/*
+ * 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.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.filter.RangeGlobalStep;
+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.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 Marko A. Rodriguez (http://markorodriguez.com)
+ */
+public final class OrderLimitStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy>
implements TraversalStrategy.OptimizationStrategy {
+
+    private static final OrderLimitStrategy INSTANCE = new OrderLimitStrategy();
+
+    private static Set<Class<? extends Step>> LEGAL_STEPS = new HashSet<>(
+            Arrays.asList(LabelStep.class,
+                    IdStep.class,
+                    PathStep.class,
+                    SelectStep.class,
+                    SelectOneStep.class,
+                    SackStep.class,
+                    TreeStep.class));
+
+    private OrderLimitStrategy() {
+    }
+
+    @Override
+    public void apply(final Traversal.Admin<?, ?> traversal) {
+        if (!TraversalHelper.onGraphComputer(traversal))
+            return;
+
+        final List<OrderGlobalStep> orders = TraversalHelper.getStepsOfClass(OrderGlobalStep.class,
traversal);
+        for (final OrderGlobalStep order : orders) {
+            RangeGlobalStep range = null;
+            Step<?, ?> currentStep = order.getNextStep();
+            while (true) {
+                if (currentStep instanceof RangeGlobalStep) {
+                    range = (RangeGlobalStep) currentStep;
+                    break;
+                } else if (!LEGAL_STEPS.contains(currentStep.getClass()))
+                    break;
+                else
+                    currentStep = currentStep.getNextStep();
+            }
+            if (null != range)
+                order.setLimit(range.getHighRange());
+        }
+    }
+
+    public static OrderLimitStrategy instance() {
+        return INSTANCE;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
index 27ad118..8a2b9a9 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
@@ -101,7 +101,7 @@ public final class ComputerVerificationStrategy extends AbstractTraversalStrateg
 
             // collecting barriers and dedup global use can only operate on the element and
its properties (no incidences)
             if ((step instanceof CollectingBarrierStep || step instanceof DedupGlobalStep)
&& step instanceof TraversalParent) {
-                if (((TraversalParent) step).getLocalChildren().stream().filter(t -> !TraversalHelper.isLocalVertex(t)).findAny().isPresent())
+                if (((TraversalParent) step).getLocalChildren().stream().filter(t -> !TraversalHelper.isLocalProperties(t)).findAny().isPresent())
                     throw new VerificationException("A barrier-steps can not process the
incident edges of a vertex: " + step, traversal);
             }
 

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
index 757bc32..d6461ce 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/TraverserSet.java
@@ -20,6 +20,7 @@ package org.apache.tinkerpop.gremlin.process.traversal.traverser.util;
 
 import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
 import org.apache.tinkerpop.gremlin.process.traversal.util.FastNoSuchElementException;
+import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
 
 import java.io.Serializable;
 import java.util.AbstractSet;
@@ -136,18 +137,20 @@ public class TraverserSet<S> extends AbstractSet<Traverser.Admin<S>>
implements
 
     @Override
     public String toString() {
-        return this.map.keySet().toString();
+        return this.map.values().toString();
     }
 
     public void sort(final Comparator<Traverser<S>> comparator) {
-        final List<Traverser.Admin<S>> list = new ArrayList<>(this.map.values());
+        final List<Traverser.Admin<S>> list = new ArrayList<>(this.map.size());
+        IteratorUtils.removeOnNext(this.map.values().iterator()).forEachRemaining(list::add);
         Collections.sort(list, comparator);
         this.map.clear();
         list.forEach(traverser -> this.map.put(traverser, traverser));
     }
 
     public void shuffle() {
-        final List<Traverser.Admin<S>> list = new ArrayList<>(this.map.values());
+        final List<Traverser.Admin<S>> list = new ArrayList<>(this.map.size());
+        IteratorUtils.removeOnNext(this.map.values().iterator()).forEachRemaining(list::add);
         Collections.shuffle(list);
         this.map.clear();
         list.forEach(traverser -> this.map.put(traverser, traverser));

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/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 50340fa..ee20147 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
@@ -21,36 +21,22 @@ package org.apache.tinkerpop.gremlin.process.traversal.util;
 import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.TraversalVertexProgramStep;
 import org.apache.tinkerpop.gremlin.process.traversal.Step;
 import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
-import org.apache.tinkerpop.gremlin.process.traversal.lambda.ElementValueTraversal;
-import org.apache.tinkerpop.gremlin.process.traversal.lambda.TokenTraversal;
 import org.apache.tinkerpop.gremlin.process.traversal.step.HasContainerHolder;
-import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
 import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
 import org.apache.tinkerpop.gremlin.process.traversal.step.branch.RepeatStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.ConnectiveStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.filter.FilterStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.NotStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TailGlobalStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WherePredicateStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereTraversalStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeVertexStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStep;
-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.MatchStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertiesStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertyKeyStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertyMapStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertyValueStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.SelectOneStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.VertexStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.StartStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.BulkSet;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
-import org.apache.tinkerpop.gremlin.structure.Property;
 import org.apache.tinkerpop.gremlin.structure.T;
-import org.apache.tinkerpop.gremlin.structure.Vertex;
 import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
 
 import java.util.ArrayList;
@@ -72,57 +58,7 @@ public final class TraversalHelper {
     private TraversalHelper() {
     }
 
-    public static boolean isBeyondElementId(final Traversal.Admin<?, ?> traversal)
{
-        if (traversal instanceof TokenTraversal && !((TokenTraversal) traversal).getToken().equals(T.id))
-            return true;
-        else if (traversal instanceof ElementValueTraversal)
-            return true;
-        else
-            return traversal.getSteps().stream()
-                    .filter(step -> step instanceof VertexStep ||
-                            step instanceof LambdaHolder || // if we don't know, then yes.
-                            step instanceof LabelStep ||
-                            step instanceof EdgeVertexStep ||
-                            step instanceof PropertiesStep ||
-                            step instanceof PropertyMapStep ||
-                            (step instanceof TraversalParent &&
-                                    (((TraversalParent) step).getLocalChildren().stream().filter(TraversalHelper::isBeyondElementId).findAny().isPresent()
||
-                                            ((TraversalParent) step).getGlobalChildren().stream().filter(TraversalHelper::isBeyondElementId).findAny().isPresent())))
-                    .findAny().isPresent();
-    }
-
-    public static Class getLastElementClass(final Traversal.Admin<?, ?> traversal)
{
-        Step<?, ?> currentStep = traversal.getEndStep();
-        while (!(currentStep instanceof EmptyStep)) {
-            if (currentStep instanceof VertexStep)
-                return ((VertexStep) currentStep).getReturnClass();
-            else if (currentStep instanceof GraphStep)
-                return ((GraphStep) currentStep).getReturnClass();
-            else if (currentStep instanceof EdgeVertexStep)
-                return Vertex.class;
-            else if (currentStep instanceof PropertiesStep)
-                return ((PropertiesStep) currentStep).getReturnType().forProperties() ? Property.class
: Object.class;
-            else if (currentStep instanceof SelectOneStep) {
-                final String key = ((SelectOneStep<?, ?>) currentStep).getScopeKeys().iterator().next();
-                while (!(currentStep instanceof EmptyStep)) {
-                    if (currentStep.getLabels().contains(key))
-                        break;
-                    currentStep = currentStep.getPreviousStep();
-                }
-            } else
-                currentStep = currentStep.getPreviousStep();
-        }
-        return Object.class;
-    }
-
-    public static boolean isLocalElement(final Step<?, ?> step) {
-        return step instanceof PropertiesStep || step instanceof PropertyMapStep ||
-                step instanceof IdStep || step instanceof LabelStep ||
-                step instanceof PropertyKeyStep || step instanceof PropertyValueStep ||
-                step instanceof TailGlobalStep || step instanceof FilterStep;
-    }
-
-    public static boolean isLocalVertex(final Traversal.Admin<?, ?> traversal) {
+    public static boolean isLocalProperties(final Traversal.Admin<?, ?> traversal)
{
         for (final Step step : traversal.getSteps()) {
             if (step instanceof RepeatStep &&
                     ((RepeatStep<?>) step).getGlobalChildren().stream()
@@ -137,7 +73,7 @@ public final class TraversalHelper {
                 return false;
             } else if (step instanceof TraversalParent) {
                 if (((TraversalParent) step).getLocalChildren().stream()
-                        .filter(t -> !isLocalVertex(t.asAdmin()))
+                        .filter(t -> !isLocalProperties(t.asAdmin()))
                         .findAny().isPresent()) return false;
             }
         }

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoMapper.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoMapper.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoMapper.java
index acd66cf..091d1f3 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoMapper.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoMapper.java
@@ -29,6 +29,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.map.GroupCountStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.GroupStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.GroupStepV3d0;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.MeanGlobalStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.OrderGlobalStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.TreeStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.BulkSet;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.Tree;
@@ -300,7 +301,7 @@ public final class GryoMapper implements Mapper<Kryo> {
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(HashSet.class,
null, 62));
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(BulkSet.class,
null, 64));
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(MutableMetrics.class,
null, 69));
-            add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(ImmutableMetrics.class,
null, 115)); // ***LAST ID***
+            add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(ImmutableMetrics.class,
null, 115));
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(StandardTraversalMetrics.class,
null, 70));
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(MapMemory.class,
null, 73));
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(MapReduce.NullObject.class,
null, 74));
@@ -332,6 +333,7 @@ public final class GryoMapper implements Mapper<Kryo> {
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(TreeStep.TreeBiOperator.class,
null, 112));
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(GroupStepV3d0.GroupBiOperatorV3d0.class,
null, 113));
             add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(RangeGlobalStep.RangeBiOperator.class,
null, 114));
+            add(Triplet.<Class, Function<Kryo, Serializer>, Integer>with(OrderGlobalStep.OrderBiOperator.class,
null, 116)); // ***LAST ID***
         }};
 
         private final List<IoRegistry> registries = new ArrayList<>();

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/util/TraversalHelperTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/util/TraversalHelperTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/util/TraversalHelperTest.java
index 3e6196f..626cd0b 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/util/TraversalHelperTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/util/TraversalHelperTest.java
@@ -21,7 +21,6 @@ package org.apache.tinkerpop.gremlin.process.util;
 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.step.TraversalParent;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.FilterStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.HasStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.filter.LambdaFilterStep;
@@ -48,13 +47,12 @@ import static org.junit.Assert.assertTrue;
 public class TraversalHelperTest {
 
     @Test
-    public void shouldIdentifyScopeOfAccess() {
-        assertFalse(TraversalHelper.isBeyondElementId(__.identity().asAdmin()));
-        assertFalse(TraversalHelper.isBeyondElementId(__.id().asAdmin()));
-        assertTrue(TraversalHelper.isBeyondElementId(__.label().asAdmin()));
-        assertTrue(TraversalHelper.isBeyondElementId(__.values("name").asAdmin()));
-        assertTrue(TraversalHelper.isBeyondElementId(__.outE("knows").asAdmin()));
-        // assertTrue(TraversalHelper.isBeyondElementId(((TraversalParent) __.order().asAdmin().getStartStep()).getLocalChildren().get(0)));
+    public void shouldIdentityLocalProperties() {
+        assertTrue(TraversalHelper.isLocalProperties(__.identity().asAdmin()));
+        assertTrue(TraversalHelper.isLocalProperties(__.id().asAdmin()));
+        assertTrue(TraversalHelper.isLocalProperties(__.label().asAdmin()));
+        assertTrue(TraversalHelper.isLocalProperties(__.values("name").asAdmin()));
+        assertFalse(TraversalHelper.isLocalProperties(__.outE("knows").asAdmin()));
     }
 
     @Test

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyOrderTest.groovy
----------------------------------------------------------------------
diff --git a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyOrderTest.groovy
b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyOrderTest.groovy
index 8d1df8f..04bbd9f 100644
--- a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyOrderTest.groovy
+++ b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyOrderTest.groovy
@@ -121,5 +121,10 @@ public abstract class GroovyOrderTest {
         public Traversal<Vertex, Vertex> get_g_V_hasXsong_name_OHBOYX_outXfollowedByX_outXfollowedByX_order_byXperformancesX_byXsongType_incrX()
{
             new ScriptTraversal<>(g, "gremlin-groovy", "g.V.has('song', 'name', 'OH
BOY').out('followedBy').out('followedBy').order.by('performances').by('songType',decr)")
         }
+
+        @Override
+        public Traversal<Vertex, String> get_g_V_both_hasLabelXpersonX_order_byXage_decrX_limitX5X_name()
{
+            new ScriptTraversal<>(g, "gremlin-groovy", "g.V.both.hasLabel('person').order.by('age',decr).limit(5).name")
+        }
     }
 }

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/a67567e0/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderTest.java
b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderTest.java
index 7637123..cf08b44 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderTest.java
@@ -87,6 +87,8 @@ public abstract class OrderTest extends AbstractGremlinProcessTest {
 
     public abstract Traversal<Vertex, Vertex> get_g_V_hasXsong_name_OHBOYX_outXfollowedByX_outXfollowedByX_order_byXperformancesX_byXsongType_incrX();
 
+    public abstract Traversal<Vertex, String> get_g_V_both_hasLabelXpersonX_order_byXage_decrX_limitX5X_name();
+
     @Test
     @LoadGraphWith(MODERN)
     public void g_V_name_order() {
@@ -359,6 +361,7 @@ public abstract class OrderTest extends AbstractGremlinProcessTest {
     @LoadGraphWith(GRATEFUL)
     public void g_V_hasXsong_name_OHBOYX_outXfollowedByX_outXfollowedByX_order_byXperformancesX_byXsongType_incrX()
{
         final Traversal<Vertex, Vertex> traversal = get_g_V_hasXsong_name_OHBOYX_outXfollowedByX_outXfollowedByX_order_byXperformancesX_byXsongType_incrX();
+        printTraversalForm(traversal);
         int counter = 0;
         String lastSongType = "a";
         int lastPerformances = Integer.MIN_VALUE;
@@ -376,6 +379,21 @@ public abstract class OrderTest extends AbstractGremlinProcessTest {
         assertEquals(144, counter);
     }
 
+    @Test
+    @LoadGraphWith(MODERN)
+    public void g_V_both_hasLabelXpersonX_order_byXage_decrX_limitX5X_name() {
+        final Traversal<Vertex, String> traversal = get_g_V_both_hasLabelXpersonX_order_byXage_decrX_limitX5X_name();
+        printTraversalForm(traversal);
+        final List<String> results = traversal.toList();
+        assertEquals(5, results.size());
+        assertFalse(traversal.hasNext());
+        assertEquals("peter", results.get(0));
+        assertEquals("josh", results.get(1));
+        assertEquals("josh", results.get(2));
+        assertEquals("josh", results.get(3));
+        assertEquals("marko", results.get(4));
+    }
+
     public static class Traversals extends OrderTest {
 
         @Override
@@ -471,5 +489,10 @@ public abstract class OrderTest extends AbstractGremlinProcessTest {
         public Traversal<Vertex, Vertex> get_g_V_hasXsong_name_OHBOYX_outXfollowedByX_outXfollowedByX_order_byXperformancesX_byXsongType_incrX()
{
             return g.V().has("song", "name", "OH BOY").out("followedBy").out("followedBy").order().by("performances").by("songType",
Order.decr);
         }
+
+        @Override
+        public Traversal<Vertex, String> get_g_V_both_hasLabelXpersonX_order_byXage_decrX_limitX5X_name()
{
+            return g.V().both().hasLabel("person").order().by("age", Order.decr).limit(5).values("name");
+        }
     }
 }



Mime
View raw message