Uploaded image for project: 'IMPALA'
  1. IMPALA
  2. IMPALA-5932

Improve the performance of transitive closure computation in value transfer graph

    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:
      ghx-label-8

      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.

        Attachments

          Activity

            People

            • Assignee:
              tianyiwang Tianyi Wang
              Reporter:
              tianyiwang Tianyi Wang
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: