[
https://issues.apache.org/jira/browse/TINKERPOP3-700?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14557600#comment-14557600
]
Matthias Broecheler commented on TINKERPOP3-700:
------------------------------------------------
But how do you know which of these "branches" to follow? The idea behind the
BudgetAlgorithm is to make smart choices on that. Simply trying all these in
parallel doesn't sound very smart and waste a lot of computational resources.
Also, in complicated matches, the number of potential branches grows
exponentially in the number of conditions such that enumerating them all would
become infeasible.
> WhereStep should "MatchStep" and ConjunctionP should use the BudgetAlgorithm
> ----------------------------------------------------------------------------
>
> Key: TINKERPOP3-700
> URL: https://issues.apache.org/jira/browse/TINKERPOP3-700
> Project: TinkerPop 3
> Issue Type: Improvement
> Components: process
> Reporter: Marko A. Rodriguez
>
> {code}
> g.V.as('a').where(a.knows.b
> a.knows.c
> b.knows.c)
> {code}
> The above can be written as an OrP of the form:
> {code}
> g.V.as('a').or(select(a).knows.b.select(b).knows.c.select(a).knows.where(eq(c)),
>
> select(a).knows.c.select(a).knows.b.select(b).knows.where(eq(c)));
> {code}
> In essence, the where-statements are rewritten in terms of every possible
> permutation. When these permutations are put into an OrP (via
> or(traversals…)), then if any branch returns a result, then the original 'a'
> is emitted (as {{WhereStep}} is a {{FilterStep}}). If {{OrP}} is under the
> BudgetAlgorithm, then {{OrP}} will "thread between" its traversals until a
> value is yielded. *And given that all permutations are the same semantics --
> if one fails, they all fail!*
> What is nice about this, is that arbitrary nesting comes "for free."
> {code}
> g.V.as('a').where(a.knows.b
> a.uncle.b
> and(a.worksFor.c
> b.worksFor.c))
> {code}
> This is rewritten as:
> {code}
> g.V.as('a').or(select(a).knows.b.or(select(a).worksFor.c.select(b).worksFor.where(eq(c)),select(b).worksFor.c.select(a).worksFor.where(eq(c))).select(a).uncle.where(eq(b)),
>
> select(a).uncle.b.select(a).knows.where(eq(b)).or(select(a).worksFor.c.select(b).worksFor.where(eq(c)),select(b).worksFor.c.select(a).worksFor.where(eq(c))))
> {code}
> *IMPORTANT* This is not a "match" in the {{MatchStep}} sense as it doesn't
> return all permutations that bind, it only filters based on a single match.
> What is interesting about this approach:
> 1. The rewrite algorithm seems simple as its just concatenation given
> {{select()}}-projections and {{where(eq)}}-tails.
> 2. The cool thing about the rewrite in all possible permutations is that if
> any one {{FastNoSuchElementException}}, its booted from the {{ConjunctionP}}
> analysis.
> 3. {{ConjunctionP}} has the BudgetAlgorithm and thus can be used for ANY
> step that has conjunctions -- {{HasStep}}, {{IsStep}}, etc.
> 4. It uses the path data structure to maintain the variable bindings.
> {{WhereStep}} has no state! Its all about {{OrP}}.
> 5. Given that the path data is the variable bindings, then this also works
> for OLAP as the traverser contains all the information it needs (no central
> location of analysis!)
> - However, you would only pick one permutation to do as `or()` does not
> exist in OLAP.
> - and with one permutation, {{where().select()}} is then {{MatchStep}}
> which would then work in OLAP!
> - thus, Gremlin OLAP can rewrite {{match()}} to the
> {{where().select()}} form and TADA!
>
> *IMPORTANT* 4 and 5 above are pretty insane consequences. And if any, we
> should at least use this realization to make {{match()}} work in OLAP.
> Next, realize that how {{where()}} should work is that if an {{as()}} is NOT
> in the path data structure, then its a variable bindings for rewrite.
> Moreover, if you don't provide a start {{as()}}, it is assumed to be the
> incoming object (currently how {{where()}} works). For example:
> {code}
> g.V.where(knows.b
> knows.c
> b.knows.c)
> {code}
> This is rewritten as:
> {code}
> g.V.or(x.select(x).knows.b.or(select(b).worksFor.where(eq(a)),select(x).worksFor.where(eq(b))).select(x).uncle.where(eq(b)),
>
> x.select(x).uncle.b.select(x).knows.where(eq(b)).or(select(b).worksFor.where(eq(x)),select(x).worksFor.where(eq(b))))
>
> {code}
> To be sure, the {{as('a').select('a')}} fragments can of course be optimized
> out to just {{as('a')}}.
>
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
