Uploaded image for project: 'TinkerPop'
  1. TinkerPop
  2. TINKERPOP-1470

InlineFilterStrategy should try and P.or() has() children in OrSteps.

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 3.2.2
    • Fix Version/s: 3.2.3
    • Component/s: process
    • Labels:
      None

      Description

      The following patterns:

      g.V().or(has("age",gt(20)), has("age",lt(32)))
      g.V().and(or(has("age",gt(20)), has("age",lt(32))),has("age",neq(23))
      

      should be re-written by InlineFilterStrategy as:

      g.V().has("age",gt(20).or(lt(32)))
      g.V().has("age",gt(20).or(lt(32)).and(neq(23)))
      

      This would then make it easier for provider strategies to fold the predicate into graph/vertex-centric push down predicates accordingly.

      Note that InlineFilterStep already has the code to flatten AndSteps. Thus, during its recursion, it would do the following rewrites to get to the final form.

      g.V().and(or(has("age",gt(20)), has("age",lt(32))),has("age",neq(23))
      g.V().or(has("age",gt(20)), has("age",lt(32))).has("age",neq(23))
      g.V().has("age",gt(20).or(lt(32))).has("age",neq(23))
      g.V().has("age",gt(20).or(lt(32)).and(neq(23)))
      

        Issue Links

          Activity

          Hide
          githubbot ASF GitHub Bot added a comment -

          GitHub user okram opened a pull request:

          https://github.com/apache/tinkerpop/pull/445

          TINKERPOP-1470: InlineFilterStrategy should try and P.or() has() children in OrSteps.

          https://issues.apache.org/jira/browse/TINKERPOP-1470

          Added `InlineFilterStrategy` support for:

          ```
          OrStep[HasStep(x,p1),HasStep(y,p2)]
          ```

          to be rewritten as:

          ```
          HasStep(x,p1.or(p2)))
          ```

          While doing this, I found a bug in `ConnectiveP` around nesting predicates that should be inlined. I added upgrade notes about `ConnectiveP` as well as about hidden step labels (forgot to add this from a previous ticket).

          Also, I added this ticket as future work: https://issues.apache.org/jira/browse/TINKERPOP-1482

          VOTE +1

          You can merge this pull request into a Git repository by running:

          $ git pull https://github.com/apache/tinkerpop TINKERPOP-1470

          Alternatively you can review and apply these changes as the patch at:

          https://github.com/apache/tinkerpop/pull/445.patch

          To close this pull request, make a commit to your master/trunk branch
          with (at least) the following in the commit message:

          This closes #445


          commit 6da9151ef19c998688b78309e69fddb274ddf9d6
          Author: Marko A. Rodriguez <okrammarko@gmail.com>
          Date: 2016-09-29T16:39:20Z

          Added support for or(has,has) to be has(x.or) in InlineFilterStrategy. While doing this, I found a bug in ConnectiveP steps where nested equivalents were not being inlined. That bug has been fixed. Added test cases to PTest to demonstrate proper inlining and nesting of ConnectivePs. I left two TODOs. One regarding match()-pulls that are labeled (interfering with FilterRankStrategy) and one regarding, has.has being turned into has(x.and). The reason why the latter isn't done now as it may greatly mess up providers who just rely on eq() for index lookups and are not smart enough to look into and()/or() predicates.


          Show
          githubbot ASF GitHub Bot added a comment - GitHub user okram opened a pull request: https://github.com/apache/tinkerpop/pull/445 TINKERPOP-1470 : InlineFilterStrategy should try and P.or() has() children in OrSteps. https://issues.apache.org/jira/browse/TINKERPOP-1470 Added `InlineFilterStrategy` support for: ``` OrStep [HasStep(x,p1),HasStep(y,p2)] ``` to be rewritten as: ``` HasStep(x,p1.or(p2))) ``` While doing this, I found a bug in `ConnectiveP` around nesting predicates that should be inlined. I added upgrade notes about `ConnectiveP` as well as about hidden step labels (forgot to add this from a previous ticket). Also, I added this ticket as future work: https://issues.apache.org/jira/browse/TINKERPOP-1482 VOTE +1 You can merge this pull request into a Git repository by running: $ git pull https://github.com/apache/tinkerpop TINKERPOP-1470 Alternatively you can review and apply these changes as the patch at: https://github.com/apache/tinkerpop/pull/445.patch To close this pull request, make a commit to your master/trunk branch with (at least) the following in the commit message: This closes #445 commit 6da9151ef19c998688b78309e69fddb274ddf9d6 Author: Marko A. Rodriguez <okrammarko@gmail.com> Date: 2016-09-29T16:39:20Z Added support for or(has ,has ) to be has(x.or ) in InlineFilterStrategy. While doing this, I found a bug in ConnectiveP steps where nested equivalents were not being inlined. That bug has been fixed. Added test cases to PTest to demonstrate proper inlining and nesting of ConnectivePs. I left two TODOs. One regarding match()-pulls that are labeled (interfering with FilterRankStrategy) and one regarding, has .has being turned into has(x.and ). The reason why the latter isn't done now as it may greatly mess up providers who just rely on eq() for index lookups and are not smart enough to look into and()/or() predicates.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user okram commented on the issue:

          https://github.com/apache/tinkerpop/pull/445

          I added some other things to this ticket. In particular:

          1. `FilterRankStrategy` is now smart about propagating labels "right" to increase the liklihood of good sorts.
          2. Fixed a bug in `TraversalHelper.copyLabels()`.
          3. `InlineFilterStrategy` now compresses `HasStep`-chains.

          Show
          githubbot ASF GitHub Bot added a comment - Github user okram commented on the issue: https://github.com/apache/tinkerpop/pull/445 I added some other things to this ticket. In particular: 1. `FilterRankStrategy` is now smart about propagating labels "right" to increase the liklihood of good sorts. 2. Fixed a bug in `TraversalHelper.copyLabels()`. 3. `InlineFilterStrategy` now compresses `HasStep`-chains.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user okram commented on the issue:

          https://github.com/apache/tinkerpop/pull/445

          Ran integration tests overnight.

          ```
          [INFO] ------------------------------------------------------------------------
          [INFO] BUILD SUCCESS
          [INFO] ------------------------------------------------------------------------
          [INFO] Total time: 05:12 h
          [INFO] Finished at: 2016-09-29T21:09:28-06:00
          [INFO] Final Memory: 121M/1519M
          [INFO] ------------------------------------------------------------------------
          ```

          Show
          githubbot ASF GitHub Bot added a comment - Github user okram commented on the issue: https://github.com/apache/tinkerpop/pull/445 Ran integration tests overnight. ``` [INFO] ------------------------------------------------------------------------ [INFO] BUILD SUCCESS [INFO] ------------------------------------------------------------------------ [INFO] Total time: 05:12 h [INFO] Finished at: 2016-09-29T21:09:28-06:00 [INFO] Final Memory: 121M/1519M [INFO] ------------------------------------------------------------------------ ```
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user twilmes commented on the issue:

          https://github.com/apache/tinkerpop/pull/445

          I like how you pulled the chunks of processing out into separate methods in `InlineFilterStrategy`. Cleans things up nicely.

          VOTE: +1

          Show
          githubbot ASF GitHub Bot added a comment - Github user twilmes commented on the issue: https://github.com/apache/tinkerpop/pull/445 I like how you pulled the chunks of processing out into separate methods in `InlineFilterStrategy`. Cleans things up nicely. VOTE: +1
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user okram commented on the issue:

          https://github.com/apache/tinkerpop/pull/445

          Could you review this @dkuppitz? Check out `FilterRankStrategy(Test)` and tell me what you think.

          Show
          githubbot ASF GitHub Bot added a comment - Github user okram commented on the issue: https://github.com/apache/tinkerpop/pull/445 Could you review this @dkuppitz? Check out `FilterRankStrategy(Test)` and tell me what you think.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user dkuppitz commented on a diff in the pull request:

          https://github.com/apache/tinkerpop/pull/445#discussion_r81550568

          — Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java —
          @@ -72,97 +75,163 @@ public void apply(final Traversal.Admin<?, ?> traversal) {
          boolean changed = true; // recursively walk child traversals trying to inline them into the current traversal line.
          while (changed) {
          changed = false;

          • // filter(x.y) --> x.y
          • for (final TraversalFilterStep<?> step : TraversalHelper.getStepsOfClass(TraversalFilterStep.class, traversal)) {
          • final Traversal.Admin<?, ?> childTraversal = step.getLocalChildren().get(0);
          • if (TraversalHelper.hasAllStepsOfClass(childTraversal, FilterStep.class) &&
          • !TraversalHelper.hasStepOfClass(childTraversal,
          • DropStep.class,
          • RangeGlobalStep.class,
          • DedupGlobalStep.class,
          • LambdaHolder.class)) {
            + for (final FilterStep<?> step : TraversalHelper.getStepsOfAssignableClass(FilterStep.class, traversal)) {
              • End diff –

          Complex traversal could waste a few CPU cycles in this method. Here's an optimized version:

          ```
          @Override
          public void apply(final Traversal.Admin<?, ?> traversal) {
          boolean changed = true; // recursively walk child traversals trying to inline them into the current traversal line.
          while (changed) {
          changed = false;
          final Iterator<FilterStep> filterStepIterator = TraversalHelper.getStepsOfAssignableClass(FilterStep.class, traversal).iterator();
          while (!changed && filterStepIterator.hasNext())

          { final FilterStep<?> step = filterStepIterator.next(); changed = step instanceof HasStep && InlineFilterStrategy.processHasStep((HasStep) step, traversal) || step instanceof TraversalFilterStep && InlineFilterStrategy.processTraversalFilterStep((TraversalFilterStep) step, traversal) || step instanceof OrStep && InlineFilterStrategy.processOrStep((OrStep) step, traversal) || step instanceof AndStep && InlineFilterStrategy.processAndStep((AndStep) step, traversal); }

          if (!changed && traversal.getParent() instanceof EmptyStep) {
          final Iterator<MatchStep> matchStepIterator = TraversalHelper.getStepsOfClass(MatchStep.class, traversal).iterator();
          while (!changed && matchStepIterator.hasNext())

          { if (InlineFilterStrategy.processMatchStep(matchStepIterator.next(), traversal)) changed = true; }

          }
          }
          }
          ```

          Show
          githubbot ASF GitHub Bot added a comment - Github user dkuppitz commented on a diff in the pull request: https://github.com/apache/tinkerpop/pull/445#discussion_r81550568 — Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java — @@ -72,97 +75,163 @@ public void apply(final Traversal.Admin<?, ?> traversal) { boolean changed = true; // recursively walk child traversals trying to inline them into the current traversal line. while (changed) { changed = false; // filter(x.y) --> x.y for (final TraversalFilterStep<?> step : TraversalHelper.getStepsOfClass(TraversalFilterStep.class, traversal)) { final Traversal.Admin<?, ?> childTraversal = step.getLocalChildren().get(0); if (TraversalHelper.hasAllStepsOfClass(childTraversal, FilterStep.class) && !TraversalHelper.hasStepOfClass(childTraversal, DropStep.class, RangeGlobalStep.class, DedupGlobalStep.class, LambdaHolder.class)) { + for (final FilterStep<?> step : TraversalHelper.getStepsOfAssignableClass(FilterStep.class, traversal)) { End diff – Complex traversal could waste a few CPU cycles in this method. Here's an optimized version: ``` @Override public void apply(final Traversal.Admin<?, ?> traversal) { boolean changed = true; // recursively walk child traversals trying to inline them into the current traversal line. while (changed) { changed = false; final Iterator<FilterStep> filterStepIterator = TraversalHelper.getStepsOfAssignableClass(FilterStep.class, traversal).iterator(); while (!changed && filterStepIterator.hasNext()) { final FilterStep<?> step = filterStepIterator.next(); changed = step instanceof HasStep && InlineFilterStrategy.processHasStep((HasStep) step, traversal) || step instanceof TraversalFilterStep && InlineFilterStrategy.processTraversalFilterStep((TraversalFilterStep) step, traversal) || step instanceof OrStep && InlineFilterStrategy.processOrStep((OrStep) step, traversal) || step instanceof AndStep && InlineFilterStrategy.processAndStep((AndStep) step, traversal); } if (!changed && traversal.getParent() instanceof EmptyStep) { final Iterator<MatchStep> matchStepIterator = TraversalHelper.getStepsOfClass(MatchStep.class, traversal).iterator(); while (!changed && matchStepIterator.hasNext()) { if (InlineFilterStrategy.processMatchStep(matchStepIterator.next(), traversal)) changed = true; } } } } ```
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user dkuppitz commented on the issue:

          https://github.com/apache/tinkerpop/pull/445

          LGTM.

          VOTE: +1

          Show
          githubbot ASF GitHub Bot added a comment - Github user dkuppitz commented on the issue: https://github.com/apache/tinkerpop/pull/445 LGTM. VOTE: +1
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user okram commented on the issue:

          https://github.com/apache/tinkerpop/pull/445

          merged.

          Show
          githubbot ASF GitHub Bot added a comment - Github user okram commented on the issue: https://github.com/apache/tinkerpop/pull/445 merged.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user okram closed the pull request at:

          https://github.com/apache/tinkerpop/pull/445

          Show
          githubbot ASF GitHub Bot added a comment - Github user okram closed the pull request at: https://github.com/apache/tinkerpop/pull/445

            People

            • Assignee:
              okram Marko A. Rodriguez
              Reporter:
              okram Marko A. Rodriguez
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development