+1 - I like the consolidation around the different traversal concepts and the resulting simplification where execution is more orthogonal from optimization.
On Wed, Jun 17, 2015 at 5:03 PM Joshua Shinavier <[email protected]> wrote: > No objection. The code is simpler, and it seems like a good course > correction w.r.t. traversal optimization. Might be possible to drop in > something close to the current MatchStep (*) as an alternative if desired. > > Best, > > Josh > > *) basically, keep track of the inputs and outputs of each component > traversal of the match, build a plan which minimizes the likely cost of > running the next element through the plan, keep updating the plan > > > On Wed, Jun 17, 2015 at 6:05 PM, Marko Rodriguez <[email protected]> > wrote: > > > Hello, > > > > For the last week or so I've been working on XMatchStep w/ Kuppitz. What > > spurned this was my burning desire to get and/or/not settled by GA and > > where()/match() are the culprits that leverage it the most. In fact, > along > > with XMatchStep, WhereStep has gotten a massive revamping for the better. > > Anywho, first off, XMatchStep: > > > > ..simple, elegant -- easy, breezy, cover girl: > > > > > > > https://github.com/apache/incubator-tinkerpop/blob/ebb0fd69821857ecefecf9222983c2bd0e189650/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java > > > > It is now at a point where it is passing all the MatchTest tests (save > > one -- whose expected results are up to debate) and is comparable in > > performance to the original MatchStep developed by Josh Shinavier (cc:d) > > which leverages Matthias Bröcheler's budget match algorithm. > > > > There are a few things about XMatchStep that make it "better" than the > > current/original MatchStep: > > > > 1. Works for both OLAP and OLTP. > > 2. Supports nested AND/OR'ing. > > 3. Supports pluggable "match algorithms." (i.e. pattern execution > > plan) > > 4. Maintains no runtime state (fully functional). > > 5. Uses the more recent advances in TinkerPop's Step framework. > > e.g. Scoping, ComputerAwareStep, ConjunctionStep, etc. > > 6. Supports a broader range of legal patterns. > > 7. Supports local barrier patterns (i.e. count(), min(), max(), > > etc.). > > 8. Supports sideEffects (i.e. as('a').within("x")) > > 9. Supports pulling out HasContainers for GraphStep index > lookups. > > 10. Supports not'ing patterns [coming soon]. > > > > Below are the runtimes for some pattern matches over the Grateful Dead > > graph. The xmatch()-times specified are using CountMatchAlgorithm which > is > > basically "dynamically sort the match pattern execution plan according to > > each pattern's set reduction abilities." > > > > MatchStep vs. XMatchStep: > > https://gist.github.com/okram/d49e1abf48fdc18f77f9 > > > > CountMatchAlgorithm: > > > https://github.com/apache/incubator-tinkerpop/blob/ebb0fd69821857ecefecf9222983c2bd0e189650/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java#L451 > > > > As it stands, it seems that the simple CountMatchAlgorithm is sufficient > > to perform better than MatchStep's budget match implementation. However, > as > > we do more queries and learn more tricks we can always add more match > > algorithms. Easy breezy -- yes, cover girl. > > > > In sum total, I would like to replace MatchStep with XMatchStep for GA. > If > > anyone has any thoughts/arguments on the matter, please state them. > > > > Thank you, > > Marko. > > > > http://markorodriguez.com > > > > >
