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

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


    • 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:


      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:


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




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


              • Created: