[ https://issues.apache.org/jira/browse/CALCITE-4049?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17134589#comment-17134589 ]
Xiening Dai commented on CALCITE-4049: -------------------------------------- After looking it deeper, I feel the shorted path might not needed at all. Right now, the getShortestPath() is used only by ConventionTraitDef.canConvert(). [1] But actually in ConventionTraitDef.convert(), it doesn't use the shortest path for conversion, instead it gets all possible paths and enumerate them one by one. [2] So it looks to me that the shortest path is not used at all. And even though the comment of Graph#getPaths() says it returns shortest path first, but actually it uses a DFS to find the path, and doesn't grantee shortest first today. So I believe the getShortedPath() can be removed. [1] https://github.com/apache/calcite/blob/52a57078ba081b24b9d086ed363c715485d1a519/core/src/main/java/org/apache/calcite/plan/ConventionTraitDef.java#L200 [2] https://github.com/apache/calcite/blob/52a57078ba081b24b9d086ed363c715485d1a519/core/src/main/java/org/apache/calcite/plan/ConventionTraitDef.java#L139 > Reduce the time complexity of getting shortest distances > -------------------------------------------------------- > > Key: CALCITE-4049 > URL: https://issues.apache.org/jira/browse/CALCITE-4049 > Project: Calcite > Issue Type: Improvement > Components: core > Reporter: Liya Fan > Assignee: Liya Fan > Priority: Major > Fix For: 1.24.0 > > Time Spent: 1h 20m > Remaining Estimate: 0h > > Currently, we have {{Graphs#makeImmutable}} to compute the shortest paths > between all pairs of nodes. For many scenarios, however, we do not need the > exact paths between nodes. Instead, we are only interested in the lengths of > the shortest paths. > To get the path length, we need to get the shortest path first, which is > returned as a {{List}}, then we call the {{List#size()}} method. According to > the current implementation, the returned list is of type {{ConsList}}. The > time complexity of {{ConsList#size}} is O(p) (p is the number of vertices on > the path), which is inefficient. > In this issue, we revise the implementation of {{ConsList#size}} so that it > takes O(1) time. In addition, we also give a utiltiy to get the shortest > distances between nodes. -- This message was sent by Atlassian Jira (v8.3.4#803005)