[IMPALA-5932] Improve the performance of transitive closure computation in value transfer graph

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: Impala 2.11.0
• Fix Version/s: Impala 2.11.0
• Component/s: Frontend
• Epic Color: ghx-label-8
• Assignee: Tianyi Wang
• Reporter: Tianyi Wang
• Created: 13/Sep/17 22:21
• Updated: 20/Sep/17 21:32
• Resolved: 20/Sep/17 21:32

Description

Currently org.apache.impala.analysis.Analyzer.ValueTransferGraph computes transitive closure using a V^4 algorithm, where V is the number of vertexes. (https://github.com/apache/incubator-impala/blob/39e8cf313f41acc1a70be4c12b67173bd156f029/fe/src/main/java/org/apache/impala/analysis/Analyzer.java#L2691). It could be improved straightforwardly to V^3 with a standard Floyed-Warshall algorithm implementation. Also, given that our graph is a DAG, Topological sort and bitmap tricks might be practically faster.