tinkerpop-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (TINKERPOP-1254) Support dropping traverser path information when it is no longer needed.
Date Sun, 10 Jul 2016 18:34:10 GMT

    [ https://issues.apache.org/jira/browse/TINKERPOP-1254?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15369891#comment-15369891
] 

ASF GitHub Bot commented on TINKERPOP-1254:
-------------------------------------------

Github user okram commented on the issue:

    https://github.com/apache/tinkerpop/pull/358
  
    Check this out on OLTP now....INSANE.
    
    ```
    Traversal Metrics
    Step                                                               Count  Traversers 
     Time (ms)    % Dur
    =============================================================================================================
    TinkerGraphStep(vertex,[])                                           808         808 
         1.273     0.02
    MatchStep(AND,[[MatchStartStep(a), ProfileStep,...              14465066      114964 
      5945.246    97.59
      MatchStartStep(a)                                                  808         808 
        74.614
      VertexStep(OUT,vertex)                                            8049        8049 
        77.965
      MatchEndStep(b)                                                   8049        8049 
        97.455
      MatchStartStep(b)                                                 8049        7957 
        69.525
      VertexStep(OUT,vertex)                                          327370      327370 
       180.215
      MatchEndStep(c)                                                 327370      327370 
       792.902
      MatchStartStep(c)                                               327370       56814 
        98.793
      VertexStep(OUT,vertex)                                        14465066     1728961 
       703.308
      MatchEndStep(d)                                               14465066     1728961 
      2470.109
    NoOpBarrierStep(2500)                                           14465066         452 
       144.282     2.37
    SelectOneStep(d)                                                14465066         452 
         1.067     0.02
    CountGlobalStep                                                        1           1 
         0.223     0.00
                                                >TOTAL                     -          
-        6092.093        -
    
    Traversal Metrics
    Step                                                               Count  Traversers 
     Time (ms)    % Dur
    =============================================================================================================
    TinkerGraphStep(vertex,[])                                           808         808 
        22.107     0.03
    MatchStep(AND,[[MatchStartStep(a), ProfileStep,...              14465066    14448765 
     69090.223    87.45
      MatchStartStep(a)                                                  808         808 
      4040.859
      VertexStep(OUT,vertex)                                            8049        8049 
      3886.808
      MatchEndStep(b)                                                   8049        8049 
      3655.827
      MatchStartStep(b)                                                 8049        7957 
      3062.039
      VertexStep(OUT,vertex)                                          327370      327370 
      3942.711
      MatchEndStep(c)                                                 327370      327370 
      3789.122
      MatchStartStep(c)                                               327370      326983 
       437.946
      VertexStep(OUT,vertex)                                        14465066    14465066 
      5516.906
      MatchEndStep(d)                                               14465066    14465066 
      6793.385
    SelectOneStep(d)                                                14465066    14448765 
      7155.383     9.06
    CountGlobalStep                                                        1           1 
      2734.799     3.46
                                                >TOTAL                     -          
-       79002.514        -
    ```


> Support dropping traverser path information when it is no longer needed.
> ------------------------------------------------------------------------
>
>                 Key: TINKERPOP-1254
>                 URL: https://issues.apache.org/jira/browse/TINKERPOP-1254
>             Project: TinkerPop
>          Issue Type: Improvement
>          Components: process
>    Affects Versions: 3.1.1-incubating
>            Reporter: Marko A. Rodriguez
>            Assignee: Ted Wilmes
>
> The most expensive traversals (especially in OLAP) are those that can not be "bulked."
There are various reasons why two traversers at the same object can not be bulked, but the
primary reason is {{PATH}} or {{LABELED_PATH}}. That is, when the history of the traverser
is required, the probability of two traversers having the same history is low.
> A key to making traversals more efficient is to do as a much as possible to remove historic
information from a traverser so it can get bulked. How does one do this? 
> {code}
> g.V.as('a').out().as('b').out().where(neq('a').and().neq('b')).both().name
> {code}
> The {{LABELED_PATH}} of "a" and "b" are required up to the {{where()}} and at which point,
at {{both()}}, they are no longer required. It would be smart to support:
> {code}
> traverser.dropLabels(Set<String>)
> traverser.dropPath()
> {code}
> We would then, via a {{TraversalOptimizationStrategy}} insert a step between {{where()}}
and {{both()}} called {{PathPruneStep}} which would be a {{SideEffectStep}}. The strategy
would know which labels were no longer needed (via forward lookahead) and then do:
> {code}
> public class PathPruneStep {
>   final Set<String> dropLabels = ...
>   final boolean dropPath = ...
>   public void sideEffect(final Traverser<S> traverser) {
>     final Traverser<S> start = this.starts.next();
>     if(this.dropPath) start.dropPath();
>     else start.dropLabels(labels); 
>   }
> }
> {code}
> Again, the more we can prune historic path data no longer needed, the higher the probability
of bulking. Think about this in terms of {{match()}}.
> {code}
> g.V().match(
>   a.out.b,
>   b.out.c,
>   c.neq.a,
>   c.out.b,
> ).select("a")
> {code}
> All we need is "a" at the end. Thus, once a pattern has been passed and no future patterns
require that label, drop it! 
> This idea is related to TINKERPOP-331, but I don't think we should deal with manipulating
the species. Thus, I think 331 is too "low level."



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message