Hi,
I just realized that the examples provided in the gist don't show AND/OR
nesting. Here is an example for those that are interested over the TinkerPop
toy graph:
g.V().xmatch("a",
where("a", P.neq("c")),
as("a").out("created").as("b"),
or(
as("a").out("knows").has("name", "vadas"),
as("a").in("knows").and().as("a").has(T.label,"person")
),
as("b").in("created").as("c"),
as("b").in("created").count().is(P.gt(1)))
.select().by("name")
There result being:
{a=marko, b=lop, c=josh}
{a=marko, b=lop, c=peter}
{a=josh, b=lop, c=marko}
{a=josh, b=lop, c=peter}
There are a couple of interesting things to note. First, look how
where("a",P.neq("c")) is the first pattern, but is not executed first as it is
unsolvable without "c" being bound. I'm just showing that patterns can be in
any arbitrary order though its best to give them in an order that is legal and
efficient as it will take CountMatchAlgorithm a few clock-cylces to work out
which patterns are doing the largest set reductions.
Second, note that both the prefix-notation OR and the infix-notation AND are
legal and compile as expected (bolded above). Realize that without nesting,
XMatchStep assumes a single nest of AND -- that is, the fist level is always
AND.
[TinkerGraphStep([],vertex)@[a], XMatchStep(AND,[[XMatchStartStep,
WhereStep(global,a,neq(v[6])), XMatchEndStep], [XMatchStartStep(a),
VertexStep(OUT,[created],vertex), XMatchEndStep(b)],
[XMatchStep(OR,[[XMatchStartStep(a), VertexStep(OUT,[knows],vertex),
HasStep([name.eq(vadas)]), XMatchEndStep],
[XMatchStep(AND,[[XMatchStartStep(a), VertexStep(IN,[knows],vertex),
XMatchEndStep], [XMatchStartStep(a), HasStep([~label.eq(person)]),
XMatchEndStep]]), XMatchEndStep]]), XMatchEndStep], [XMatchStartStep(b),
VertexStep(IN,[created],vertex), XMatchEndStep(c)], [XMatchStartStep(b),
TraversalFlatMapStep([VertexStep(IN,[created],edge), RangeGlobalStep(0,2),
CountGlobalStep, IsStep(gt(1))]), XMatchEndStep]]),
SelectStep(local,[value(name)])]
** I bolded Daniel's strategy work on count() optimization :)
Finally, I didn't show this in the last email, but this also works in OLAP:
GraphTraversalSource g = TinkerFactory.createModern().traversal(computer());
g.V().xmatch("a",
where("a", P.neq("c")),
as("a").out("created").as("b"),
or(
as("a").out("knows").has("name", "vadas"),
as("a").in("knows").and().as("a").has(T.label,"person")
),
as("b").in("created").as("c"),
as("b").in("created").count().is(P.gt(1)))
.select().by("name")
{a=v[1], b=v[3], c=v[4]}
{a=v[1], b=v[3], c=v[6]}
{a=v[4], b=v[3], c=v[1]}
{a=v[4], b=v[3], c=v[6]}
Realize we can't do "by("name")" as that requires reference to the vertex to
get its properties and in OLAP, we don't have that…… There are a few solutions
to getting data from path elements but it hasn't shook itself out yet.
Enjoy,
Marko.
http://markorodriguez.com
On Jun 17, 2015, at 4: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
>
