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."

        Attachments

          Issue Links

            Activity

              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: