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