[jira] [Resolved] (CALCITE-3827) Reduce the time complexity of finding in-edges of a vertex in the graph

["Julian Hyde (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/CALCITE-3827?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Julian Hyde resolved CALCITE-3827.
----------------------------------
    Resolution: Fixed

Fixed in [0e00d6553|https://github.com/apache/calcite/commit/0e00d6553]; thanks for the PR, [~fan_li_ya]!

> 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
>            Assignee: Julian Hyde
>            Priority: Major
>              Labels: pull-request-available
>             Fix For: 1.23.0
>
>          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)