[
https://issues.apache.org/jira/browse/CALCITE-3827?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17047227#comment-17047227
]
Liya Fan commented on CALCITE-3827:
-----------------------------------
> Im cautious about paying the extra cost.
Thanks for your attention. The extra cost should be marginal, given that the
node class is well-implemented. Here, a well-implemented class should at least
satisfy the following properties:
1. the hashCode & equals methods are light-weight
2. the returned values of the hashCode method has a small chance of colliding
IMO, some classes in our code base do not satisfy the above conditions, and we
need to improve them in the future.
> Could cache clearing be done more efficiently?
IMO, it is difficult to do so without significantly changing the current logic.
In addition, there are always scenarios when we need to traverse the graph
bottom-up, and we should support such scenarios with good performance.
> 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
> 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)
