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

[Proposal] Local Nested Traversals Beyond the Star Graph in OLAP

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Won't Fix
    • Affects Version/s: 3.0.2-incubating
    • Fix Version/s: None
    • Component/s: process
    • Labels:
      None

      Description

      Here is a half-baked solution to the "local star graph"-problem in Gremlin OLAP.

      A Traverser not only maintains a pointer to its current object, but also to its "local traversal spawn object." For instance:

      g.V.where(out('knows').has('name','bob')).name
      

      The Traverser going into the where() step will, lets say, be at v[1]. Thus:

      Traverser.get() == v[1]
      Traverser.spawn() == v[1]
      Traverser.stepId() == "out('knows')"-stepId
      

      At the next step, the Traverser[v[1]] hits up the out("knows") step. This will trigger a message pass. Lets say v[1]-knows->v[2].

      Traverser.get() == v[2]
      Traverser.spawn() == v[1]
      Traverser.stepId() == "has('name','bob')"-stepId
      

      At this point, the Traverser[v[2]] is shoved into has("name","bob") and lets say that v[2] is "bob." What is the next step? There is none because its at the end of the local traversal. So, TraverserExecutor looks up step.getTraversal().getTraversalParent() and executes the local where()-step with a behavior of "v[1] went into , and v[2] came out." Thus, a "simulated local traversal" is "v[1] --> v[2]" and where()-step simply says "ah, v[2], then let me emit v[1]". This yields a Traverser of:

      Traverser.get() == v[1]
      Traverser.spawn() == null
      Traverser.stepId() == values('name')-stepId
      

      The Traverser is sent back to v[1] to solve the values('name')-step function.

      This notion of a "simulated local traversal" is that the where()-step local traversal can be "wrapped" on the fly by TraverserExecutor such that:

      out('knows').has('name','bob') --> directMap(v[1],v[2])
      

      So this is doable for a single local traversal. What about parallel local traversals like and(a,b,c). In this situation, a, b, and c must all come back before and() is complete. I think it might work something like this:

      Traverser.get() == v[1]
      Traverser.spawn() == v[1]
      Traverser.sessionId() == uuid:123-456-789(3)
      

      In this way, before the spawn is "released" by and(), three uuid:123-456-789 session ids must be returned with Traverser.get() != null. If that happens, the and() released v[1] to the next step.

      Note that in this model all the state is in the Traverser. There is no step state required. Given that Traversers are stored at the local vertex during iterations, looking up a Traverser by sessionId can be just as easy as looking it up by Traverser.get(). In this way, a placeholder Traverser exists at the and()-ing vertex waiting for its sessionId to complete.

      .......................... a little sketchy and involved. But I think with some more mulling we can come up with a simple "ah, that is just a that which makes this just that and I can delete the entire codebase because there never was a problem to begin with. I can die yielding no intent. Finally."

        Activity

        Hide
        okram Marko A. Rodriguez added a comment -

        I tried to implement this a while back. I got it working for a few steps, but it was so crazy and a near rewrite of those steps I had it working for that I got discouraged... I think TINKERPOP3-940 might be the way forward on this front. Either way, closing this ticket as I don't its ideas corrupting a future realization.

        Show
        okram Marko A. Rodriguez added a comment - I tried to implement this a while back. I got it working for a few steps, but it was so crazy and a near rewrite of those steps I had it working for that I got discouraged... I think TINKERPOP3-940 might be the way forward on this front. Either way, closing this ticket as I don't its ideas corrupting a future realization.

          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