TINKERPOP-1656 WIP - basic proof of concept for bulk mutations
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/bb583e3a Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/bb583e3a Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/bb583e3a Branch: refs/heads/TINKERPOP-1656 Commit: bb583e3a47aa4ab94ecfe04190073feed4e13a20 Parents: 2591302 Author: Stephen Mallette <sp...@genoprime.com> Authored: Wed Mar 22 07:01:57 2017 -0400 Committer: Stephen Mallette <sp...@genoprime.com> Committed: Thu Apr 19 12:51:43 2018 -0400 ---------------------------------------------------------------------- gremlin-benchmark/pom.xml | 2 +- .../gremlin/process/GraphMutateBenchmark.java | 18 ++- .../traversal/dsl/graph/GraphTraversal.java | 64 ++++++++-- .../traversal/step/MutatingContainerHolder.java | 53 +++++++++ .../traversal/step/map/MutatingStep.java | 102 ++++++++++++++++ .../traversal/step/util/MutatingContainer.java | 109 +++++++++++++++++ .../strategy/optimization/MutatingStrategy.java | 66 ++++++++++ .../process/traversal/util/TraversalHelper.java | 37 +++++- .../tinkergraph/structure/TinkerGraph.java | 119 ++++++++++++++++++- 9 files changed, 554 insertions(+), 16 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/gremlin-benchmark/pom.xml ---------------------------------------------------------------------- diff --git a/gremlin-benchmark/pom.xml b/gremlin-benchmark/pom.xml index 571bc0d..3b8b995 100644 --- a/gremlin-benchmark/pom.xml +++ b/gremlin-benchmark/pom.xml @@ -86,7 +86,7 @@ limitations under the License. <testSourceDirectory>${project.build.sourceDirectory}</testSourceDirectory> <testClassesDirectory>${project.build.outputDirectory}</testClassesDirectory> <includes> - <include>**/*Benchmark*.java</include> + <include>**/*MutateBenchmark*.java</include> </includes> <excludes> <exclude>**/*$*.class</exclude> http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/GraphMutateBenchmark.java ---------------------------------------------------------------------- diff --git a/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/GraphMutateBenchmark.java b/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/GraphMutateBenchmark.java index 733e32b..27a9315 100644 --- a/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/GraphMutateBenchmark.java +++ b/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/GraphMutateBenchmark.java @@ -51,6 +51,20 @@ public class GraphMutateBenchmark extends AbstractGraphMutateBenchmark { @Override public void prepare() { super.prepare(); +// +// withoutStrategies(ConnectiveStrategy.class, +// InlineFilterStrategy.class, +// IncidentToAdjacentStrategy.class, +// AdjacentToIncidentStrategy.class, +// FilterRankingStrategy.class, +// MatchPredicateStrategy.class, +// RepeatUnrollStrategy.class, +// RangeByIsCountStrategy.class, +// PathRetractionStrategy.class, +// LazyBarrierStrategy.class, +// ProfileStrategy.class, +// StandardVerificationStrategy.class) + a = g.addV().next(); b = g.addV().next(); c = g.addV().next(); @@ -173,8 +187,8 @@ public class GraphMutateBenchmark extends AbstractGraphMutateBenchmark { } } - final Edge e = (Edge) t.next(); - return e; + final Edge x = (Edge) t.next(); + return x; } @Benchmark http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java index 222fdab..4ebe1ba 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java @@ -37,7 +37,9 @@ import org.apache.tinkerpop.gremlin.process.traversal.lambda.PredicateTraverser; import org.apache.tinkerpop.gremlin.process.traversal.lambda.TrueTraversal; import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating; import org.apache.tinkerpop.gremlin.process.traversal.step.FromToModulating; +import org.apache.tinkerpop.gremlin.process.traversal.step.FromToModulating; import org.apache.tinkerpop.gremlin.process.traversal.step.Mutating; +import org.apache.tinkerpop.gremlin.process.traversal.step.MutatingContainerHolder; import org.apache.tinkerpop.gremlin.process.traversal.step.TimesModulating; import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalOptionParent; import org.apache.tinkerpop.gremlin.process.traversal.step.branch.BranchStep; @@ -91,6 +93,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.map.MeanGlobalStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.MeanLocalStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.MinGlobalStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.MinLocalStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MutatingStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.NoOpBarrierStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.OrderGlobalStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.OrderLocalStep; @@ -130,6 +133,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SubgraphSt import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.TraversalSideEffectStep; import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.TreeSideEffectStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.HasContainer; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.MutatingContainer; import org.apache.tinkerpop.gremlin.process.traversal.step.util.Tree; import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; @@ -985,7 +989,14 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { */ public default GraphTraversal<S, Vertex> addV(final String vertexLabel) { this.asAdmin().getBytecode().addStep(Symbols.addV, vertexLabel); - return this.asAdmin().addStep(new AddVertexStep<>(this.asAdmin(), vertexLabel)); + + final Step endStep = this.asAdmin().getEndStep(); + final MutatingContainerHolder holder = (endStep instanceof MutatingContainerHolder) ? + (MutatingContainerHolder) endStep : new MutatingStep<>(this.asAdmin()); + + final MutatingContainer container = new MutatingContainer(MutatingContainer.Operation.ADD_V, holder, T.label, vertexLabel); + holder.addMutatingContainer(container); + return endStep == holder ? (GraphTraversal) this : this.asAdmin().addStep((Step) holder); } /** @@ -997,7 +1008,14 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { */ public default GraphTraversal<S, Vertex> addV() { this.asAdmin().getBytecode().addStep(Symbols.addV); - return this.asAdmin().addStep(new AddVertexStep<>(this.asAdmin(), null)); + + final Step endStep = this.asAdmin().getEndStep(); + final MutatingContainerHolder holder = (endStep instanceof MutatingContainerHolder) ? + (MutatingContainerHolder) endStep : new MutatingStep<>(this.asAdmin()); + + final MutatingContainer container = new MutatingContainer(MutatingContainer.Operation.ADD_V, holder); + holder.addMutatingContainer(container); + return endStep == holder ? (GraphTraversal) this : this.asAdmin().addStep((Step) holder); } /** @@ -1023,7 +1041,17 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { */ public default GraphTraversal<S, Edge> addE(final String edgeLabel) { this.asAdmin().getBytecode().addStep(Symbols.addE, edgeLabel); - return this.asAdmin().addStep(new AddEdgeStep<>(this.asAdmin(), edgeLabel)); + + final Step endStep = this.asAdmin().getEndStep(); + final MutatingContainerHolder holder = (endStep instanceof MutatingContainerHolder) ? + (MutatingContainerHolder) endStep : new MutatingStep<>(this.asAdmin()); + + final MutatingContainer container = new MutatingContainer(MutatingContainer.Operation.ADD_E, holder); + container.setEdgeLabel(edgeLabel); + holder.addMutatingContainer(container); + return endStep == holder ? (GraphTraversal) this : this.asAdmin().addStep((Step) holder); + + //return this.asAdmin().addStep(new AddEdgeStep<>(this.asAdmin(), edgeLabel)); } /** @@ -1036,7 +1064,13 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { */ public default GraphTraversal<S, E> to(final String toStepLabel) { this.asAdmin().getBytecode().addStep(Symbols.to, toStepLabel); - ((FromToModulating) this.asAdmin().getEndStep()).addTo(toStepLabel); + + final Step endStep = this.asAdmin().getEndStep(); + if (endStep instanceof MutatingContainerHolder) { + ((MutatingContainerHolder) endStep).getLastMutatingContainer().setInVLabel(toStepLabel); + } else { + ((FromToModulating) this.asAdmin().getEndStep()).addTo(toStepLabel); + } return this; } @@ -1050,7 +1084,13 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { */ public default GraphTraversal<S, E> from(final String fromStepLabel) { this.asAdmin().getBytecode().addStep(Symbols.from, fromStepLabel); - ((FromToModulating) this.asAdmin().getEndStep()).addFrom(fromStepLabel); + + final Step endStep = this.asAdmin().getEndStep(); + if (endStep instanceof MutatingContainerHolder) { + ((MutatingContainerHolder) endStep).getLastMutatingContainer().setOutVLabel(fromStepLabel); + } else { + ((FromToModulating) this.asAdmin().getEndStep()).addFrom(fromStepLabel); + } return this; } @@ -1065,6 +1105,11 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { */ public default GraphTraversal<S, E> to(final Traversal<E, Vertex> toVertex) { this.asAdmin().getBytecode().addStep(Symbols.to, toVertex); + + + // TODO: trigger explode here if this happens? + + ((FromToModulating) this.asAdmin().getEndStep()).addTo(toVertex.asAdmin()); return this; } @@ -1080,6 +1125,11 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { */ public default GraphTraversal<S, E> from(final Traversal<E, Vertex> fromVertex) { this.asAdmin().getBytecode().addStep(Symbols.from, fromVertex); + + + // TODO: trigger explode here if this happens? + + ((FromToModulating) this.asAdmin().getEndStep()).addFrom(fromVertex.asAdmin()); return this; } @@ -2058,7 +2108,7 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { // if it can be detected that this call to property() is related to an addV/E() then we can attempt to fold // the properties into that step to gain an optimization for those graphs that support such capabilities. final Step endStep = this.asAdmin().getEndStep(); - if ((endStep instanceof AddVertexStep || endStep instanceof AddEdgeStep || endStep instanceof AddVertexStartStep) && + if ((endStep instanceof MutatingStep || endStep instanceof AddVertexStep || endStep instanceof AddEdgeStep || endStep instanceof AddVertexStartStep) && keyValues.length == 0 && null == cardinality) { ((Mutating) endStep).addPropertyMutations(key, value); } else { @@ -2419,7 +2469,7 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { ///////////////////// UTILITY STEPS ///////////////////// /** - * A step modulator that provides a lable to the step that can be accessed later in the traversal by other steps. + * A step modulator that provides a label to the step that can be accessed later in the traversal by other steps. * * @param stepLabel the name of the step * @param stepLabels additional names for the label http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/MutatingContainerHolder.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/MutatingContainerHolder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/MutatingContainerHolder.java new file mode 100644 index 0000000..5f69e58 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/MutatingContainerHolder.java @@ -0,0 +1,53 @@ +/* + * 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.util.MutatingContainer; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.CallbackRegistry; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.Event; +import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.Vertex; + +import java.util.List; + +/** + * @author Stephen Mallette (http://stephen.genoprime.com) + */ +public interface MutatingContainerHolder { + + public List<MutatingContainer> getMutatingContainers(); + + public default MutatingContainer getLastMutatingContainer() { + final List<MutatingContainer> containers = getMutatingContainers(); + return containers.get(containers.size() - 1); + } + + public void addMutatingContainer(final MutatingContainer mutatingContainer); + + public default void removeMutatingContainer(final MutatingContainer mutatingContainer) { + throw new UnsupportedOperationException("The holder does not support container removal: " + this.getClass().getCanonicalName()); + } + + public CallbackRegistry<Event> getMutatingCallbackRegistry(); + + public Vertex getLabelledVertex(final String label); + + public Graph getGraph(); +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MutatingStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MutatingStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MutatingStep.java new file mode 100644 index 0000000..d130b7a --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MutatingStep.java @@ -0,0 +1,102 @@ +/* + * 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.map; + +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.Traverser; +import org.apache.tinkerpop.gremlin.process.traversal.step.Mutating; +import org.apache.tinkerpop.gremlin.process.traversal.step.MutatingContainerHolder; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.MutatingContainer; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.CallbackRegistry; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.Event; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.ListCallbackRegistry; +import org.apache.tinkerpop.gremlin.structure.Element; +import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.Vertex; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * @author Stephen Mallette (http://stephen.genoprime.com) + */ +public final class MutatingStep<S> extends MapStep<S, Element> implements MutatingContainerHolder, Mutating { + + private Map<String,Vertex> labelledVertices = new HashMap<>(); + private List<MutatingContainer> mutatingContainers = new ArrayList<>(); + private CallbackRegistry<Event> callbackRegistry; + + public MutatingStep(final Traversal.Admin traversal, final MutatingContainer... mutatingContainers) { + super(traversal); + Collections.addAll(this.mutatingContainers, mutatingContainers); + } + + @Override + protected Element map(final Traverser.Admin<S> traverser) { + Element e = null; + for (final MutatingContainer container : mutatingContainers) { + final Element element = container.get(); + if (element instanceof Vertex) { + // TODO: how to handle multiple labelled stuffs g.addV().as('a').addV().as('a') + for (String label : container.getStepLabels()) { + labelledVertices.put(label, (Vertex) element); + } + } + + e = element; + } + + return e; + } + + @Override + public void addPropertyMutations(final Object... keyValues) { + final MutatingContainer container = mutatingContainers.get(mutatingContainers.size() - 1); + container.addPropertyMutations(keyValues); + } + + @Override + public Graph getGraph() { + return (Graph) this.traversal.getGraph().get(); + } + + @Override + public List<MutatingContainer> getMutatingContainers() { + return this.mutatingContainers; + } + + @Override + public void addMutatingContainer(final MutatingContainer mutatingContainer) { + this.mutatingContainers.add(mutatingContainer); + } + + @Override + public CallbackRegistry<Event> getMutatingCallbackRegistry() { + if (null == callbackRegistry) callbackRegistry = new ListCallbackRegistry<>(); + return callbackRegistry; + } + + @Override + public Vertex getLabelledVertex(final String label) { + return labelledVertices.get(label); + } +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutatingContainer.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutatingContainer.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutatingContainer.java new file mode 100644 index 0000000..c7c6821 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutatingContainer.java @@ -0,0 +1,109 @@ +/* + * 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.util; + +import org.apache.tinkerpop.gremlin.process.traversal.step.Mutating; +import org.apache.tinkerpop.gremlin.process.traversal.step.MutatingContainerHolder; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.CallbackRegistry; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.event.Event; +import org.apache.tinkerpop.gremlin.structure.Element; +import org.apache.tinkerpop.gremlin.structure.Vertex; + +import java.io.Serializable; +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; +import java.util.Set; +import java.util.function.Function; +import java.util.function.Supplier; + +/** + * @author Stephen Mallette (http://stephen.genoprime.com) + */ +public class MutatingContainer implements Supplier<Element>, Mutating, Serializable, Cloneable { + public enum Operation implements Function<MutatingContainer, Element> { + ADD_V { + @Override + public Element apply(final MutatingContainer container) { + return (container.holder.getGraph()).addVertex(container.keyValues.toArray()); + } + }, + ADD_E { + @Override + public Element apply(final MutatingContainer container) { + final Vertex outV = container.holder.getLabelledVertex(container.outVLabel); + final Vertex inV = container.holder.getLabelledVertex(container.inVLabel); + return outV.addEdge(container.edgeLabel, inV, container.keyValues.toArray()); + } + } + } + + private final Operation op; + private final MutatingContainerHolder holder; + private String outVLabel; + private String inVLabel; + private String edgeLabel; + private List<Object> keyValues; + private Set<String> labels = Collections.emptySet(); + + public MutatingContainer(final Operation op, final MutatingContainerHolder holder, final Object... keyValues) { + this.op = op; + this.holder = holder; + if (keyValues != null && keyValues.length > 0) this.keyValues = new ArrayList<>(); + Collections.addAll(this.keyValues, keyValues); + } + + @Override + public void addPropertyMutations(final Object... keyValues) { + if (null == this.keyValues) this.keyValues = new ArrayList<>(); + Collections.addAll(this.keyValues, keyValues); + } + + public void setOutVLabel(final String label) { + this.outVLabel = label; + } + + public void setInVLabel(final String label) { + this.inVLabel = label; + } + + public void addStepLabels(final Set<String> labels) { + this.labels = labels; + } + + public void setEdgeLabel(final String label) { + this.edgeLabel = label; + } + + public Set<String> getStepLabels() { + return Collections.unmodifiableSet(labels); + } + + @Override + public CallbackRegistry<Event> getMutatingCallbackRegistry() { + // hmmmmmmmmmmmmm + return null; + } + + @Override + public Element get() { + return op.apply(this); + } + +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MutatingStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MutatingStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MutatingStrategy.java new file mode 100644 index 0000000..552b8be --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MutatingStrategy.java @@ -0,0 +1,66 @@ +/* + * 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.map.AddVertexStartStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.AddVertexStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MapStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MutatingStep; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; + +import java.util.List; + +/** + * @author Stephen Mallette (http://stephen.genoprime.com) + */ +public final class MutatingStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy { + + private static final MutatingStrategy INSTANCE = new MutatingStrategy(); + + private MutatingStrategy() {} + + @Override + public void apply(final Traversal.Admin<?, ?> traversal) { + final MutatingStep mutatingStep = new MutatingStep(traversal); + + Step start = null; + Step end = null; + final List<Step> steps = traversal.getSteps(); + for (int ix = 0; ix < steps.size(); ix++) { + final Step currentStep = steps.get(ix); + if (currentStep instanceof AddVertexStep) { + //mutatingStep.addMutatingStep(null, (MapStep) currentStep); + if (null == start) start = currentStep; + } + + end = currentStep; + } + + TraversalHelper.removeBetween(start, end); + traversal.addStep(mutatingStep); + } + + public static MutatingStrategy instance() { + return INSTANCE; + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/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 eda836a..608e4e9 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 @@ -27,6 +27,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.lambda.ElementValueTravers import org.apache.tinkerpop.gremlin.process.traversal.lambda.TokenTraversal; import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating; import org.apache.tinkerpop.gremlin.process.traversal.step.HasContainerHolder; +import org.apache.tinkerpop.gremlin.process.traversal.step.MutatingContainerHolder; 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; @@ -38,6 +39,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereTraversal import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeVertexStep; 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.MutatingStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertiesStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertyMapStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.VertexStep; @@ -46,6 +48,8 @@ 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.process.traversal.step.util.HasContainer; import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.MutatingContainer; +import org.apache.tinkerpop.gremlin.structure.Element; import org.apache.tinkerpop.gremlin.structure.T; import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils; @@ -200,13 +204,25 @@ public final class TraversalHelper { } } + /** + * Removes steps in a traversal starting at the {@code startStep} and ending inclusively with the {@code endStep}. + */ + public static <S, E> void removeBetween(final Step<S, ?> startStep, final Step<?, E> endStep) { + removeToTraversal(startStep, endStep, null); + } + + /** + * Removes steps in a traversal starting at the {@code startStep} and ending inclusively with the {@code endStep}, + * storing them in the provided {@code newTraversal}. If the {@code newTraversal} is {@code null} then the steps + * are simply discarded. + */ public static <S, E> void removeToTraversal(final Step<S, ?> startStep, final Step<?, E> endStep, final Traversal.Admin<S, E> newTraversal) { final Traversal.Admin<?, ?> originalTraversal = startStep.getTraversal(); Step<?, ?> currentStep = startStep; while (currentStep != endStep && !(currentStep instanceof EmptyStep)) { final Step<?, ?> temp = currentStep.getNextStep(); originalTraversal.removeStep(currentStep); - newTraversal.addStep(currentStep); + if (newTraversal != null) newTraversal.addStep(currentStep); currentStep = temp; } } @@ -700,7 +716,8 @@ public final class TraversalHelper { } /** - * Used to left-fold a {@link HasContainer} to a {@link HasContainerHolder} if it exists. Else, append a {@link HasStep}. + * Used to left-fold a {@link HasContainer} to a {@link HasContainerHolder} if it exists. Else, append a + * {@link HasStep}. * * @param traversal the traversal to fold or append. * @param hasContainer the container to add left or append. @@ -714,4 +731,20 @@ public final class TraversalHelper { } else return (T) traversal.addStep(new HasStep<>(traversal, hasContainer)); } + + /** + * Used to left-fold a {@link MutatingContainer} to a {@link MutatingContainerHolder} if it exists. Else, append + * a {@link MutatingStep}. + * + * @param traversal the traversal to fold or append. + * @param mutatingContainer the container to add left or append. + * @return the has container folded or appended traversal + */ + public static Traversal.Admin addMutatingContainer(final Traversal.Admin traversal, final MutatingContainer mutatingContainer) { + if (traversal.getEndStep() instanceof MutatingContainerHolder) { + ((MutatingContainerHolder) traversal.getEndStep()).addMutatingContainer(mutatingContainer); + return traversal; + } else + return traversal.addStep(new MutatingStep<>(traversal, mutatingContainer)); + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/bb583e3a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java ---------------------------------------------------------------------- diff --git a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java index 5563665..5e722f3 100644 --- a/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java +++ b/tinkergraph-gremlin/src/main/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.java @@ -22,6 +22,8 @@ import org.apache.commons.configuration.BaseConfiguration; import org.apache.commons.configuration.Configuration; import org.apache.tinkerpop.gremlin.process.computer.GraphComputer; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; import org.apache.tinkerpop.gremlin.structure.Edge; import org.apache.tinkerpop.gremlin.structure.Element; import org.apache.tinkerpop.gremlin.structure.Graph; @@ -50,7 +52,6 @@ import java.util.Set; import java.util.UUID; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.atomic.AtomicLong; -import java.util.stream.Stream; /** * An in-memory (with optional persistence on calls to {@link #close()}), reference implementation of the property @@ -601,7 +602,11 @@ public final class TinkerGraph implements Graph { LONG { @Override public Long getNextId(final TinkerGraph graph) { - return Stream.generate(() -> (graph.currentId.incrementAndGet())).filter(id -> !graph.vertices.containsKey(id) && !graph.edges.containsKey(id)).findAny().get(); + long id; + do { + id = graph.currentId.getAndIncrement(); + } while (graph.vertices.containsKey(id) || graph.edges.containsKey(id)); + return id; } @Override @@ -631,7 +636,11 @@ public final class TinkerGraph implements Graph { INTEGER { @Override public Integer getNextId(final TinkerGraph graph) { - return Stream.generate(() -> (graph.currentId.incrementAndGet())).map(Long::intValue).filter(id -> !graph.vertices.containsKey(id) && !graph.edges.containsKey(id)).findAny().get(); + long id; + do { + id = graph.currentId.getAndIncrement(); + } while (graph.vertices.containsKey(id) || graph.edges.containsKey(id)); + return (int) id; } @Override @@ -691,7 +700,11 @@ public final class TinkerGraph implements Graph { ANY { @Override public Long getNextId(final TinkerGraph graph) { - return Stream.generate(() -> (graph.currentId.incrementAndGet())).filter(id -> !graph.vertices.containsKey(id) && !graph.edges.containsKey(id)).findAny().get(); + long id; + do { + id = graph.currentId.getAndIncrement(); + } while (graph.vertices.containsKey(id) || graph.edges.containsKey(id)); + return id; } @Override @@ -705,4 +718,102 @@ public final class TinkerGraph implements Graph { } } } + + public static void main(String[] args) { + GraphTraversalSource g = TinkerGraph.open().traversal(); + for (int iz = 0; iz < 5000; iz++) { + GraphTraversal<Vertex, ?> t = g.addV("person"); + for (int iy = 0; iy < 32; iy++) { + if (iy % 2 == 0) + t = t.property("x" + String.valueOf(iy), iy * iz); + else + t = t.property("x" + String.valueOf(iy), String.valueOf(iy + iz)); + } + + for (int ix = 0; ix < 100; ix++) { + t = t.addV("person"); + for (int iy = 0; iy < 32; iy++) { + if (iy % 2 == 0) + t = t.property("x" + String.valueOf(iy), iy * iz); + else + t = t.property("x" + String.valueOf(iy), String.valueOf(iy + iz)); + } + } + + t.iterate(); + + } + } + +// public static void main(String[] args) { +// GraphTraversalSource g = TinkerGraph.open().traversal(). +// withoutStrategies( +// org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConnectiveStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.InlineFilterStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.FilterRankingStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.MatchPredicateStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.RepeatUnrollStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.RangeByIsCountStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PathRetractionStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.LazyBarrierStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy.class, +// org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.StandardVerificationStrategy.class). +// withStrategies(org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.MutatingStrategy.instance()); +// for (int iz = 0; iz < 1000000; iz++) { +// GraphTraversal<Vertex, ?> t = g.addV("person"); +// for (int iy = 0; iy < 32; iy++) { +// if (iy % 2 == 0) +// t = t.property("x" + String.valueOf(iy), iy * iz); +// else +// t = t.property("x" + String.valueOf(iy), String.valueOf(iy + iz)); +// } +// +// t.iterate(); +// +// } +// } + + +// public static void main(String[] args) { +// final java.util.Random rand = new java.util.Random(584545454L); +// +// for (int iz = 0; iz < 10; iz++) { +// GraphTraversalSource g = TinkerGraph.open().traversal(); +// GraphTraversal<Vertex, ?> t = null; +// for (int ix = 0; ix < 100; ix++) { +// if (null == t) +// t = g.addV("person"); +// else +// t = t.addV("person"); +// +// for (int iy = 0; iy < 32; iy++) { +// if (iy % 2 == 0) +// t = t.property("x" + String.valueOf(iy), iy * ix); +// else +// t = t.property("x" + String.valueOf(iy), String.valueOf(iy + ix)); +// } +// +// t = t.as("person" + ix); +// +// if (ix > 0) { +// int edgeCount = ix == 99 ? 6 : 3; +// for (int ie = 0; ie < edgeCount; ie++) { +// t = t.addE("knows").from("person" + ix).to("person" + rand.nextInt(ix)); +// +// for (int iy = 0; iy < 8; iy++) { +// if (iy % 2 == 0) +// t = t.property("x" + String.valueOf(iy), iy * ie); +// else +// t = t.property("x" + String.valueOf(iy), String.valueOf(iy + ie)); +// } +// } +// } +// } +// +// t.iterate(); +// +// } +// } }