Details

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

Labels:None

Epic Color:ghxlabel8
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/incubatorimpala/blob/39e8cf313f41acc1a70be4c12b67173bd156f029/fe/src/main/java/org/apache/impala/analysis/Analyzer.java#L2691). It could be improved straightforwardly to V^3 with a standard FloyedWarshall algorithm implementation. Also, given that our graph is a DAG, Topological sort and bitmap tricks might be practically faster.
Activity
 All
 Comments
 Work Log
 History
 Activity
 Transitions
Let's keep it simple and use Floyd Warshall for now. We should only consider further optimization of that part if we can show it's a significant bottleneck.
I think we can do a simple optimization to the basic FW because our graph is typically sparse. We can reduce the number of times the innermost loop is invoked (we can discuss details on the CR).