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

Semantics of BarrierSteps in TraversalParent global traversals is wrong.

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 3.1.1-incubating
    • Fix Version/s: 3.2.0-incubating
    • Component/s: process
    • Labels:

      Description

      Suppose the following traversal:

      g.V.union(outE().count(), inE().count())
      

      Given that count() is a ReducingBarrierStep and thus, continues to pull until there are no more results, you would expect the result set to be:

      [6,6]
      

      However, its actually this:

      [3,0]
      [0,1]
      [0,3]
      [2,1]
      [0,1]
      [1,0]
      

      That is, for each traverser into union(), the count() is calculated.

      In OLAP, the result is [6,6] as expected.

      What should we do?

        Issue Links

          Activity

          Hide
          okram Marko A. Rodriguez added a comment -

          The problem is here:

          https://github.com/apache/incubator-tinkerpop/blob/master/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/BranchStep.java#L89-L90

          What should be happening is that we wrap the this.starts in a "splitting iterator" which will then automatically push traversers into other branches when one branch continues to next().

          Show
          okram Marko A. Rodriguez added a comment - The problem is here: https://github.com/apache/incubator-tinkerpop/blob/master/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/BranchStep.java#L89-L90 What should be happening is that we wrap the this.starts in a "splitting iterator" which will then automatically push traversers into other branches when one branch continues to next() .
          Hide
          githubbot ASF GitHub Bot added a comment -

          GitHub user okram opened a pull request:

          https://github.com/apache/incubator-tinkerpop/pull/247

          TINKERPOP-1188: Semantics of BarrierSteps in TraversalParent global traversals is wrong.

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

          BranchSteps have a bug in them. Gremlin OLAP was correctly implementing the semantics, but Gremlin OLTP was not. Branch step options are global traversals and were acting like local traversals in OLTP. The fix to this bug is "breaking" in that users would relied on this behavior will have to change their traversals. However, its only for those traversals that have barriers in their branches. For instance:

              g.V.union(out,in) // okay
              g.V.union(out.count(), in.count()) // breaking
              

          If the user wants the same results for the second traversal above, they need to do:

              g.V.local(union(out.count(), in.count()))
              

          *CHANGELOG*

          ```

          • Fixed a semantic bug in `BranchStep` where barriers reacted locally. (breaking)
            ```

          *UPDATE DOCS*

          ```
          BranchStep Bug Fix
          ^^^^^^^^^^^^^^^^^^^

          For traversals that have barriers (e.g. `count()`, `max()`, `groupCount()`, etc.) in a `branch()-step` (e.g. `union()` or `choose()`) , the traversal needs to be updated. For instance, if a traversal is of the form `g.V().union(out().count(),both().count())`, the behavior is now different. There was a bug that has been fixed, but it changes the traversal result if the user was relying on the buggy behavior. In order to effect the same behavior, the traversal should be rewritten as `g.V().local(union(out().count(),both().count()))`. Note that if a branch does not have a barrier, then no changes are required. For instance, `g.V().union(out(),both())` does not need to be updated.
          ```

          `mvn clean install` passed. VOTE +1.

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

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

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

          https://github.com/apache/incubator-tinkerpop/pull/247.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 #247


          commit 14b54efb32000467b6949c12dd9422068297ac21
          Author: Marko A. Rodriguez <okrammarko@gmail.com>
          Date: 2016-03-01T19:59:01Z

          Fixed a bug in BranchStep (and its inheriting children – union(), choose(), etc.). Branch options are global traversals and should never reset() on each insert. Moreover, they should fully pull from the source and not – like a local traversal – process one traverser at a time. If users were doing union(sum,count), to get the same result they will need to do local(union(sum,count)). Thus, its a breaking change – but was a bug. This also allowed us to remove one more ComputerVerificationStrategy filter. At this point, OLAP is just like OLTP except for 'local star graph' stuff. Added a new test case to UnionTest that demonstrates the local(union()) vs union() behavior.

          commit 4b162f06475822a1d45390b566bb7e18ed76d90a
          Author: Marko A. Rodriguez <okrammarko@gmail.com>
          Date: 2016-03-01T20:01:42Z

          removed a restraint from ComputerVerificationStrategy. Forgot to update test.


          Show
          githubbot ASF GitHub Bot added a comment - GitHub user okram opened a pull request: https://github.com/apache/incubator-tinkerpop/pull/247 TINKERPOP-1188 : Semantics of BarrierSteps in TraversalParent global traversals is wrong. https://issues.apache.org/jira/browse/TINKERPOP-1188 BranchSteps have a bug in them. Gremlin OLAP was correctly implementing the semantics, but Gremlin OLTP was not. Branch step options are global traversals and were acting like local traversals in OLTP. The fix to this bug is "breaking" in that users would relied on this behavior will have to change their traversals. However, its only for those traversals that have barriers in their branches. For instance: g.V.union(out,in) // okay g.V.union(out.count(), in.count()) // breaking If the user wants the same results for the second traversal above, they need to do: g.V.local(union(out.count(), in.count())) * CHANGELOG * ``` Fixed a semantic bug in `BranchStep` where barriers reacted locally. ( breaking ) ``` * UPDATE DOCS * ``` BranchStep Bug Fix ^^^^^^^^^^^^^^^^^^^ For traversals that have barriers (e.g. `count()`, `max()`, `groupCount()`, etc.) in a `branch()-step` (e.g. `union()` or `choose()`) , the traversal needs to be updated. For instance, if a traversal is of the form `g.V().union(out().count(),both().count())`, the behavior is now different. There was a bug that has been fixed, but it changes the traversal result if the user was relying on the buggy behavior. In order to effect the same behavior, the traversal should be rewritten as `g.V().local(union(out().count(),both().count()))`. Note that if a branch does not have a barrier, then no changes are required. For instance, `g.V().union(out(),both())` does not need to be updated. ``` `mvn clean install` passed. VOTE +1. You can merge this pull request into a Git repository by running: $ git pull https://github.com/apache/incubator-tinkerpop TINKERPOP-1188 Alternatively you can review and apply these changes as the patch at: https://github.com/apache/incubator-tinkerpop/pull/247.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 #247 commit 14b54efb32000467b6949c12dd9422068297ac21 Author: Marko A. Rodriguez <okrammarko@gmail.com> Date: 2016-03-01T19:59:01Z Fixed a bug in BranchStep (and its inheriting children – union(), choose(), etc.). Branch options are global traversals and should never reset() on each insert. Moreover, they should fully pull from the source and not – like a local traversal – process one traverser at a time. If users were doing union(sum,count), to get the same result they will need to do local(union(sum,count)). Thus, its a breaking change – but was a bug. This also allowed us to remove one more ComputerVerificationStrategy filter. At this point, OLAP is just like OLTP except for 'local star graph' stuff. Added a new test case to UnionTest that demonstrates the local(union()) vs union() behavior. commit 4b162f06475822a1d45390b566bb7e18ed76d90a Author: Marko A. Rodriguez <okrammarko@gmail.com> Date: 2016-03-01T20:01:42Z removed a restraint from ComputerVerificationStrategy. Forgot to update test.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user dkuppitz commented on the pull request:

          https://github.com/apache/incubator-tinkerpop/pull/247#issuecomment-190899295

          Makes totally sense. And since it is for 3.2.0, it's okay for it to be a breaking change.

          VOTE: +1

          Show
          githubbot ASF GitHub Bot added a comment - Github user dkuppitz commented on the pull request: https://github.com/apache/incubator-tinkerpop/pull/247#issuecomment-190899295 Makes totally sense. And since it is for 3.2.0, it's okay for it to be a breaking change. VOTE: +1
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user okram commented on the pull request:

          https://github.com/apache/incubator-tinkerpop/pull/247#issuecomment-191034435

          ```
          [INFO] ------------------------------------------------------------------------
          [INFO] Reactor Summary:
          [INFO]
          [INFO] Apache TinkerPop .................................. SUCCESS [4.983s]
          [INFO] Apache TinkerPop :: Gremlin Shaded ................ SUCCESS [2.293s]
          [INFO] Apache TinkerPop :: Gremlin Core .................. SUCCESS [38.106s]
          [INFO] Apache TinkerPop :: Gremlin Test .................. SUCCESS [11.655s]
          [INFO] Apache TinkerPop :: Gremlin Groovy ................ SUCCESS [41.471s]
          [INFO] Apache TinkerPop :: Gremlin Groovy Test ........... SUCCESS [6.856s]
          [INFO] Apache TinkerPop :: TinkerGraph Gremlin ........... SUCCESS [3:16.436s]
          [INFO] Apache TinkerPop :: Hadoop Gremlin ................ SUCCESS [5:11.348s]
          [INFO] Apache TinkerPop :: Spark Gremlin ................. SUCCESS [6:45.838s]
          [INFO] Apache TinkerPop :: Giraph Gremlin ................ SUCCESS [2:22:24.255s]
          [INFO] Apache TinkerPop :: Neo4j Gremlin ................. SUCCESS [17:42.662s]
          [INFO] Apache TinkerPop :: Gremlin Driver ................ SUCCESS [9.118s]
          [INFO] Apache TinkerPop :: Gremlin Server ................ SUCCESS [11:23.499s]
          [INFO] Apache TinkerPop :: Gremlin Console ............... SUCCESS [1:08.180s]
          [INFO] Apache TinkerPop :: Gremlin Archetype ............. SUCCESS [0.070s]
          [INFO] Apache TinkerPop :: Archetype - TinkerGraph ....... SUCCESS [6.263s]
          [INFO] Apache TinkerPop :: Archetype - Server ............ SUCCESS [10.247s]
          [INFO] ------------------------------------------------------------------------
          [INFO] BUILD SUCCESS
          [INFO] ------------------------------------------------------------------------
          [INFO] Total time: 3:10:03.833s
          [INFO] Finished at: Tue Mar 01 20:14:06 MST 2016
          [INFO] Final Memory: 99M/821M
          [INFO] ------------------------------------------------------------------------
          ```

          Show
          githubbot ASF GitHub Bot added a comment - Github user okram commented on the pull request: https://github.com/apache/incubator-tinkerpop/pull/247#issuecomment-191034435 ``` [INFO] ------------------------------------------------------------------------ [INFO] Reactor Summary: [INFO] [INFO] Apache TinkerPop .................................. SUCCESS [4.983s] [INFO] Apache TinkerPop :: Gremlin Shaded ................ SUCCESS [2.293s] [INFO] Apache TinkerPop :: Gremlin Core .................. SUCCESS [38.106s] [INFO] Apache TinkerPop :: Gremlin Test .................. SUCCESS [11.655s] [INFO] Apache TinkerPop :: Gremlin Groovy ................ SUCCESS [41.471s] [INFO] Apache TinkerPop :: Gremlin Groovy Test ........... SUCCESS [6.856s] [INFO] Apache TinkerPop :: TinkerGraph Gremlin ........... SUCCESS [3:16.436s] [INFO] Apache TinkerPop :: Hadoop Gremlin ................ SUCCESS [5:11.348s] [INFO] Apache TinkerPop :: Spark Gremlin ................. SUCCESS [6:45.838s] [INFO] Apache TinkerPop :: Giraph Gremlin ................ SUCCESS [2:22:24.255s] [INFO] Apache TinkerPop :: Neo4j Gremlin ................. SUCCESS [17:42.662s] [INFO] Apache TinkerPop :: Gremlin Driver ................ SUCCESS [9.118s] [INFO] Apache TinkerPop :: Gremlin Server ................ SUCCESS [11:23.499s] [INFO] Apache TinkerPop :: Gremlin Console ............... SUCCESS [1:08.180s] [INFO] Apache TinkerPop :: Gremlin Archetype ............. SUCCESS [0.070s] [INFO] Apache TinkerPop :: Archetype - TinkerGraph ....... SUCCESS [6.263s] [INFO] Apache TinkerPop :: Archetype - Server ............ SUCCESS [10.247s] [INFO] ------------------------------------------------------------------------ [INFO] BUILD SUCCESS [INFO] ------------------------------------------------------------------------ [INFO] Total time: 3:10:03.833s [INFO] Finished at: Tue Mar 01 20:14:06 MST 2016 [INFO] Final Memory: 99M/821M [INFO] ------------------------------------------------------------------------ ```
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user spmallette commented on the pull request:

          https://github.com/apache/incubator-tinkerpop/pull/247#issuecomment-191230940

          VOTE +1

          Show
          githubbot ASF GitHub Bot added a comment - Github user spmallette commented on the pull request: https://github.com/apache/incubator-tinkerpop/pull/247#issuecomment-191230940 VOTE +1
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user asfgit closed the pull request at:

          https://github.com/apache/incubator-tinkerpop/pull/247

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

            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