Hi everyone,
@Josh -- thanks for the review. Appreciate it. Also, if you would like to
collaborate on adding BudgetMatchAlgorithm, that would be sweet. Here is the
current MatchAlgorithm interface. Note that for OLAP, the MatchAlgorithm's
state is not global to the graph, but local to the subgraph partition (i.e. the
worker).
https://github.com/apache/incubator-tinkerpop/blob/master/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java#L402-L422
(basically recordStart and recordEnd are called before and after a traverser
is pushed into a pattern).
@Matthias -- yea. if someone has a schema and knows the best way to execute the
patterns for their data, then they can easily write their own MatchAlgorithm
and use it. This gets back to the work Pieter Martin is wanting to do around
using schema data to optimize traversals. We need to make a
MatchAlgorithmStrategy that allows the user to define which strategy to use for
the GraphTraversalSource -- right now, its just hardcoded to use
CountMatchAlgorithm.
@Stephen/everyone -- So in master/, I deleted Josh's MatchStep and replaced it
with XMatchStep which is now called MatchStep :).
https://github.com/apache/incubator-tinkerpop/blob/master/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
All the test cases pass for both OLTP and OLAP except for these two peculiar
situations:
https://github.com/apache/incubator-tinkerpop/blob/master/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java#L190
- Do we treat "predicate patterns" as filters only? The
problem, this would require predicate patterns to NOT leave the StarGraph in
OLAP. Decisions point. I will work with Kuppitz to see what he thinks is best.
There is another related decision to be had around OR semantics --- to make it
work in both OLAP and OLTP the semantics of OR are sorta crazy --- basically,
"try all paths independently." Those that continue, continue…… eek?! This is
the same problem of "predicate patterns." Without having a global blackboard,
there is no way to know if a particular OR branch (or predicate pattern)
failed….the traverser simply dies and the OR is never the wiser.
https://github.com/apache/incubator-tinkerpop/blob/master/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java#L308
- The where()-clause when outside of match() is unable to get
path metadata (i.e. name.equals("Garcia"). The solution is to fold where() into
match() but I haven't updated MatchWhereStrategy yet… will do.
Besides those two, all tests just passed and more that can now be solved (e.g.
the one's that expected an illegal argument exception for being "cyclic.").
I have some "play queries" in TinkerGraphTest that use AND/OR nesting and I
will add those to MatchTest now.
Thanks everyone,
Marko.
http://markorodriguez.com
On Jun 18, 2015, at 7:20 AM, Marko Rodriguez <[email protected]> wrote:
> Hi Stephen,
>
> There are 3 failing tests. 2 of them are because MatchStep expects a
> IllegalArgumentException to be thrown because MatchStep can't solve the
> pattern -- XMatch can. The other one is because of different number of
> results --- again, debatable on what to actually return as both XMatch and
> Match return the "right" results, just if the duplicates should be allowed or
> not.
>
> Marko.
>
> http://markorodriguez.com
>
> On Jun 18, 2015, at 4:44 AM, Stephen Mallette <[email protected]> wrote:
>
>> 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
>>>>>
>>>>>
>>>>
>>>
>
