I wanted to see what kind of test coverage existed over XMatch so I quickly swapped xmatch for match. I'm not sure if additional work needs to be done, but several tests don't pass under xmatch - perhaps the answer there is trivial when you dig into it. In any case, as it stands with the failing tests, XMatchStep has reasonable coverage, though a few more targeted tests to cover those areas would give me more confidence in a +1 for GA.
On Wed, Jun 17, 2015 at 9:37 PM, Matthias Broecheler <[email protected]> wrote: > +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 > > > > > > > > >
