You are viewing a plain text version of this content. The canonical link for it is here.

Posted to issues@impala.apache.org by "Tianyi Wang (JIRA)" <ji...@apache.org> on 2017/09/13 22:22:00 UTC

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

Tianyi Wang created IMPALA-5932:
-----------------------------------

             Summary: Improve the performance of transitive closure computation in value transfer graph
                 Key: IMPALA-5932
                 URL: https://issues.apache.org/jira/browse/IMPALA-5932
             Project: IMPALA
          Issue Type: Improvement
          Components: Frontend
    Affects Versions: Impala 2.11.0
            Reporter: Tianyi Wang
            Assignee: Tianyi Wang
            Priority: Minor


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 sparse DAG, Topological sort + using adjacency list instead of matrix can give VE complexity where E is the number of edges. 



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)