Merge branch 'tp32'
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/f57c6dc1 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/f57c6dc1 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/f57c6dc1 Branch: refs/heads/master Commit: f57c6dc1040274f8dcedc02cfa7268fb49b860cf Parents: 68ff561 e5a1bb5 Author: Daniel Kuppitz <daniel_kupp...@hotmail.com> Authored: Tue Sep 26 10:22:43 2017 -0700 Committer: Daniel Kuppitz <daniel_kupp...@hotmail.com> Committed: Tue Sep 26 10:22:43 2017 -0700 ---------------------------------------------------------------------- CHANGELOG.asciidoc | 1 + .../traversal/strategy/optimization/CountStrategy.java | 10 +++++++++- .../strategy/optimization/CountStrategyTest.java | 3 +++ 3 files changed, 13 insertions(+), 1 deletion(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f57c6dc1/CHANGELOG.asciidoc ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f57c6dc1/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java ---------------------------------------------------------------------- diff --cc gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java index a6fa06d,0000000..b2f1ecb mode 100644,000000..100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java @@@ -1,189 -1,0 +1,197 @@@ +/* + * 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.Compare; +import org.apache.tinkerpop.gremlin.process.traversal.Contains; +import org.apache.tinkerpop.gremlin.process.traversal.P; +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.dsl.graph.__; +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.*; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.CountGlobalStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep; ++import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.IdentityStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SideEffectStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.util.ConnectiveP; +import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; + +import java.util.Collection; +import java.util.Collections; +import java.util.EnumSet; +import java.util.HashMap; +import java.util.Map; +import java.util.Objects; +import java.util.Set; +import java.util.function.BiPredicate; + +/** + * This strategy optimizes any occurrence of {@link CountGlobalStep} followed by an {@link IsStep}. The idea is to limit + * the number of incoming elements in a way that it's enough for the {@link IsStep} to decide whether it evaluates + * {@code true} or {@code false}. If the traversal already contains a user supplied limit, the strategy won't + * modify it. + * + * @author Daniel Kuppitz (http://gremlin.guru) + * @example <pre> + * __.outE().count().is(0) // is replaced by __.not(outE()) + * __.outE().count().is(lt(3)) // is replaced by __.outE().limit(3).count().is(lt(3)) + * __.outE().count().is(gt(3)) // is replaced by __.outE().limit(4).count().is(gt(3)) + * </pre> + */ +public final class CountStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy { + + private static final Map<BiPredicate, Long> RANGE_PREDICATES = new HashMap<BiPredicate, Long>() {{ + put(Contains.within, 1L); + put(Contains.without, 0L); + }}; + private static final Set<Compare> INCREASED_OFFSET_SCALAR_PREDICATES = + EnumSet.of(Compare.eq, Compare.neq, Compare.lte, Compare.gt); + + private static final CountStrategy INSTANCE = new CountStrategy(); + + private CountStrategy() { + } + + public static CountStrategy instance() { + return INSTANCE; + } + + @Override + public void apply(final Traversal.Admin<?, ?> traversal) { + final TraversalParent parent = traversal.getParent(); + int size = traversal.getSteps().size(); + Step prev = null; + for (int i = 0; i < size; i++) { + final Step curr = traversal.getSteps().get(i); + if (i < size - 1 && doStrategy(curr)) { + final IsStep isStep = (IsStep) traversal.getSteps().get(i + 1); + final P isStepPredicate = isStep.getPredicate(); + Long highRange = null; + boolean useNotStep = false, dismissCountIs = false; + for (P p : isStepPredicate instanceof ConnectiveP ? ((ConnectiveP<?>) isStepPredicate).getPredicates() : Collections.singletonList(isStepPredicate)) { + final Object value = p.getValue(); + final BiPredicate predicate = p.getBiPredicate(); + if (value instanceof Number) { + final long highRangeOffset = INCREASED_OFFSET_SCALAR_PREDICATES.contains(predicate) ? 1L : 0L; - final Long highRangeCandidate = ((Number) value).longValue() + highRangeOffset; ++ final Long highRangeCandidate = (long) Math.ceil(((Number) value).doubleValue()) + highRangeOffset; + final boolean update = highRange == null || highRangeCandidate > highRange; + if (update) { + if (parent instanceof EmptyStep) { + useNotStep = false; + } else { + if (parent instanceof RepeatStep) { + final RepeatStep repeatStep = (RepeatStep) parent; + dismissCountIs = useNotStep = Objects.equals(traversal, repeatStep.getUntilTraversal()) + || Objects.equals(traversal, repeatStep.getEmitTraversal()); + } else { + dismissCountIs = useNotStep = parent instanceof FilterStep || parent instanceof SideEffectStep; + } + } + highRange = highRangeCandidate; + useNotStep &= curr.getLabels().isEmpty() && isStep.getLabels().isEmpty() + && isStep.getNextStep() instanceof EmptyStep + && ((highRange <= 1L && predicate.equals(Compare.lt)) + || (highRange == 1L && (predicate.equals(Compare.eq) || predicate.equals(Compare.lte)))); + dismissCountIs &= curr.getLabels().isEmpty() && isStep.getLabels().isEmpty() + && isStep.getNextStep() instanceof EmptyStep + && (highRange == 1L && (predicate.equals(Compare.gt) || predicate.equals(Compare.gte))); + } + } else { + final Long highRangeOffset = RANGE_PREDICATES.get(predicate); + if (value instanceof Collection && highRangeOffset != null) { + final Object high = Collections.max((Collection) value); + if (high instanceof Number) { + final Long highRangeCandidate = ((Number) high).longValue() + highRangeOffset; + final boolean update = highRange == null || highRangeCandidate > highRange; + if (update) highRange = highRangeCandidate; + } + } + } + } + if (highRange != null) { + if (useNotStep || dismissCountIs) { + traversal.asAdmin().removeStep(isStep); // IsStep + traversal.asAdmin().removeStep(curr); // CountStep + size -= 2; + if (!dismissCountIs) { + final TraversalParent p; + if ((p = traversal.getParent()) instanceof FilterStep && !(p instanceof ConnectiveStep)) { + final Step<?, ?> filterStep = parent.asStep(); + final Traversal.Admin parentTraversal = filterStep.getTraversal(); + final Step notStep = new NotStep<>(parentTraversal, + traversal.getSteps().isEmpty() ? __.identity() : traversal); + filterStep.getLabels().forEach(notStep::addLabel); + TraversalHelper.replaceStep(filterStep, notStep, parentTraversal); + } else { + final Traversal.Admin inner; + if (prev != null) { + inner = __.start().asAdmin(); + for (; ; ) { + final Step pp = prev.getPreviousStep(); + inner.addStep(0, prev); + if (pp instanceof EmptyStep || pp instanceof GraphStep || + !(prev instanceof FilterStep || prev instanceof SideEffectStep)) break; + traversal.removeStep(prev); + prev = pp; + size--; + } + } else { + inner = __.identity().asAdmin(); + } + if (prev != null) + TraversalHelper.replaceStep(prev, new NotStep<>(traversal, inner), traversal); + else + traversal.asAdmin().addStep(new NotStep<>(traversal, inner)); + } ++ } else if (size == 0) { ++ final Step parentStep = traversal.getParent().asStep(); ++ if (!(parentStep instanceof EmptyStep)) { ++ final Traversal.Admin parentTraversal = parentStep.getTraversal(); ++ //parentTraversal.removeStep(parentStep); // this leads to IndexOutOfBoundsExceptions ++ TraversalHelper.replaceStep(parentStep, new IdentityStep<>(parentTraversal), parentTraversal); ++ } + } + } else { + TraversalHelper.insertBeforeStep(new RangeGlobalStep<>(traversal, 0L, highRange), curr, traversal); + } + i++; + } + } + prev = curr; + } + } + + private boolean doStrategy(final Step step) { + if (!(step instanceof CountGlobalStep) || + !(step.getNextStep() instanceof IsStep) || + step.getPreviousStep() instanceof RangeGlobalStep) // if a RangeStep was provided, assume that the user knows what he's doing + return false; + + final Step parent = step.getTraversal().getParent().asStep(); + return (parent instanceof FilterStep || parent.getLabels().isEmpty()) && // if the parent is labeled, then the count matters + !(parent.getNextStep() instanceof MatchStep.MatchEndStep && // if this is in a pattern match, then don't do it. + ((MatchStep.MatchEndStep) parent.getNextStep()).getMatchKey().isPresent()); + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f57c6dc1/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java ---------------------------------------------------------------------- diff --cc gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java index ee4ce38,0000000..0271274 mode 100644,000000..100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java @@@ -1,117 -1,0 +1,120 @@@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; + +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.Parameterized; + +import java.util.Arrays; + +import static org.apache.tinkerpop.gremlin.process.traversal.P.gt; +import static org.apache.tinkerpop.gremlin.process.traversal.P.gte; +import static org.apache.tinkerpop.gremlin.process.traversal.P.inside; +import static org.apache.tinkerpop.gremlin.process.traversal.P.lt; +import static org.apache.tinkerpop.gremlin.process.traversal.P.lte; +import static org.apache.tinkerpop.gremlin.process.traversal.P.neq; +import static org.apache.tinkerpop.gremlin.process.traversal.P.outside; +import static org.apache.tinkerpop.gremlin.process.traversal.P.within; +import static org.apache.tinkerpop.gremlin.process.traversal.P.without; +import static org.junit.Assert.assertEquals; + +/** + * @author Daniel Kuppitz (http://gremlin.guru) + * @author Stephen Mallette (http://stephen.genoprime.com) + */ +@RunWith(Parameterized.class) +public class CountStrategyTest { + + @Parameterized.Parameter(value = 0) + public Traversal original; + + @Parameterized.Parameter(value = 1) + public Traversal optimized; + + @Parameterized.Parameters(name = "{0}") + public static Iterable<Object[]> generateTestParameters() { + + return Arrays.asList(new Traversal[][]{ + {__.count().is(0), __.limit(1).count().is(0)}, + {__.count().is(1), __.limit(2).count().is(1)}, + {__.out().count().is(0), __.out().limit(1).count().is(0)}, + {__.outE().count().is(lt(1)), __.outE().limit(1).count().is(lt(1))}, + {__.both().count().is(lte(0)), __.both().limit(1).count().is(lte(0))}, + {__.map(__.out().count().is(0)), __.map(__.out().limit(1).count().is(0))}, + {__.map(__.outE().count().is(lt(1))), __.map(__.outE().limit(1).count().is(lt(1)))}, + {__.map(__.both().count().is(lte(0))), __.map(__.both().limit(1).count().is(lte(0)))}, + {__.filter(__.out().count().is(0)), __.not(__.out())}, + {__.filter(__.outE().count().is(lt(1))), __.not(__.outE())}, + {__.filter(__.both().count().is(lte(0))), __.not(__.both())}, + {__.store("x").count().is(0).as("a"), __.store("x").limit(1).count().is(0).as("a")}, + {__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)}, + {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))}, + {__.out().count().is(lte(3)), __.out().limit(4).count().is(lte(3))}, + {__.out().count().is(lt(3)), __.out().limit(3).count().is(lt(3))}, + {__.out().count().is(gt(2)), __.out().limit(3).count().is(gt(2))}, + {__.out().count().is(gte(2)), __.out().limit(2).count().is(gte(2))}, + {__.out().count().is(inside(2, 4)), __.out().limit(4).count().is(inside(2, 4))}, + {__.out().count().is(outside(2, 4)), __.out().limit(5).count().is(outside(2, 4))}, + {__.out().count().is(within(2, 6, 4)), __.out().limit(7).count().is(within(2, 6, 4))}, + {__.out().count().is(without(2, 6, 4)), __.out().limit(6).count().is(without(2, 6, 4))}, + {__.map(__.count().is(0)), __.map(__.limit(1).count().is(0))}, + {__.flatMap(__.count().is(0)), __.flatMap(__.limit(1).count().is(0))}, + {__.flatMap(__.count().is(0)).as("a"), __.flatMap(__.count().is(0)).as("a")}, + {__.filter(__.count().is(0)).as("a"), __.not(__.identity()).as("a")}, + {__.filter(__.count().is(0)), __.not(__.identity())}, + {__.sideEffect(__.count().is(0)), __.sideEffect(__.not(__.identity()))}, + {__.branch(__.count().is(0)), __.branch(__.limit(1).count().is(0))}, + {__.count().is(0).store("x"), __.limit(1).count().is(0).store("x")}, + {__.repeat(__.out()).until(__.outE().count().is(0)), __.repeat(__.out()).until(__.not(__.outE()))}, + {__.repeat(__.out()).emit(__.outE().count().is(0)), __.repeat(__.out()).emit(__.not(__.outE()))}, + {__.where(__.outE().hasLabel("created").count().is(0)), __.not(__.outE().hasLabel("created"))}, + {__.where(__.out().outE().hasLabel("created").count().is(0)), __.not(__.out().outE().hasLabel("created"))}, + {__.where(__.out().outE().hasLabel("created").count().is(0).store("x")), __.where(__.out().outE().hasLabel("created").limit(1).count().is(0).store("x"))}, + {__.filter(__.bothE().count().is(gt(0))), __.filter(__.bothE())}, + {__.filter(__.bothE().count().is(gte(1))), __.filter(__.bothE())}, + {__.filter(__.bothE().count().is(gt(1))), __.filter(__.bothE().limit(2).count().is(gt(1)))}, + {__.filter(__.bothE().count().is(gte(2))), __.filter(__.bothE().limit(2).count().is(gte(2)))}, + {__.and(__.out().count().is(0), __.in().count().is(0)), __.and(__.not(__.out()), __.not(__.in()))}, + {__.and(__.out().count().is(0), __.in().count().is(1)), __.and(__.not(__.out()), __.in().limit(2).count().is(1))}, + {__.and(__.out().count().is(1), __.in().count().is(0)), __.and(__.out().limit(2).count().is(1), __.not(__.in()))}, + {__.or(__.out().count().is(0), __.in().count().is(0)), __.or(__.not(__.out()), __.not(__.in()))}, ++ {__.path().filter(__.count().is(gte(0.5))).limit(5), __.path().identity().limit(5)}, // unfortunately we can't just remove the filter step ++ {__.path().filter(__.unfold().count().is(gte(0.5))), __.path().filter(__.unfold())}, ++ {__.path().filter(__.unfold().count().is(gte(1.5))), __.path().filter(__.unfold().limit(2).count().is(gte(1.5)))}, + }); + } + + void applyCountStrategy(final Traversal traversal) { + final TraversalStrategies strategies = new DefaultTraversalStrategies(); + strategies.addStrategies(CountStrategy.instance()); + traversal.asAdmin().setStrategies(strategies); + traversal.asAdmin().applyStrategies(); + } + + @Test + public void doTest() { + applyCountStrategy(original); + assertEquals(optimized, original); + } +}
