Liya Fan created CALCITE-3827:
---------------------------------
Summary: 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
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 (topological sort).
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
