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
