[
https://issues.apache.org/jira/browse/CALCITE-3827?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17070642#comment-17070642
]
Liya Fan commented on CALCITE-3827:
-----------------------------------
[~julianhyde] Thanks again for your attention.
We set the break-even point to 0.5, for the sake of easy computation. According
to our experiments, however, the optimal break-even point should be greater
than 0.5, as the new algorithm (based on the indexed tables) generally
outperforms the old algorithm (traversing all edges).
It should be noted that the optimal break-even point should depend on a number
of factors, like the quality & efficiency of hashCode & equals method
implementations. So it is a scenario-dependent variable.
That being said, the general principle still holds: when removing a minority of
vertices, the new algorithm performs better; and when removing the majority of
vertices, the old algorithm outperforms.
> Reduce the time complexity of finding in-edges of a vertex in the graph
> -----------------------------------------------------------------------
>
> Key: CALCITE-3827
> URL: https://issues.apache.org/jira/browse/CALCITE-3827
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Reporter: Liya Fan
> Priority: Major
> Labels: pull-request-available
> Time Spent: 2h 40m
> Remaining Estimate: 0h
>
> In the current graph implementation, it takes O(1) time to find the out-edges
> of a vertex, but O(e) time (where e is the total number of edges in the
> graph) to find the in-edges of a vertex.
> In some scenarios (e.g. clearing cache in hep planner), this may have severe
> performance penalty. To solve this problem, we add a inward edge table, in
> addition to the existing outward edge table, to the graph. This helps to
> reduce the time complexity for finding in-edges to O(1).
> Please note that, there is extra performance overhead for maintaining the in
> edge table, when adding/deleting vertices to the graph. However, the added
> overhead only takes O(1) time.
> Finally, it should be noted that, some existing operations can benefit from
> this improvement (e.g. topological sort).
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
