[
https://issues.apache.org/jira/browse/TINKERPOP-1904?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
stephen mallette closed TINKERPOP-1904.
---------------------------------------
Resolution: Won't Do
We're not so good at big long traversals in general so big {{union()}} with 20+
traversals probably isn't a sweet spot for us. There is a much greater cost to
strategy application when there are tons of child traversals compared to inline
and step re-identification (as you identified) bears some of that cost. I think
that we will close this one in favor of TINKERPOP-1339 which would probably
help in this area. Of course, we've made two attempts (both Kuppitz and myself
separately) at that one and could never get OLAP to work right so.....
> union performance is O(g^2)
> ---------------------------
>
> Key: TINKERPOP-1904
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1904
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
> Affects Versions: 3.2.7, 3.3.1
> Reporter: Robert Dale
> Priority: Minor
>
> Where 'g' is the number of traversals within union(), the space analyzed by
> union() grows O(g^2)
> Comparing addV()s in-lined Vs unioned. That is, g.addV().addV()... Vs.
> union(addV(),addV(),...)
> *count: inline, union*
> *20*: 12ms, 20ms - ~2x slower
> *200*: 30ms, 350ms - ~10x slower
> *2000*: 150ms, 55s - ~366x slower
>
> For 2000 count, .profile() claims only 1.3s of the 55s.
>
> It seems that most of the time is spent in
> TraversalHelper.reIdSteps()
> .. BranchStep.getGlobalChildren() <- called 4 million times (2000x2000 or
> g^2)
>
> Looks like it's iterating all traversals for each traversal. I'm not sure
> what the purpose or the mechanics of this are but I wonder if it can be
> improved.
>
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
