Impala Public Jenkins has submitted this change and it was merged. Change subject: IMPALA-5932: Improve transitive closure computation performance in FE ......................................................................
IMPALA-5932: Improve transitive closure computation performance in FE This patch implements the Floyd-Warshall algorithm for the transitive closure computation for the value transfer graph, replacing the existing N^4 brute force algorithm. The performance improvement depends on the size and structure of the value transfer graph. On a random graph with 800 slots and 2800 edges it is 43X faster itself. And the "Equivalence classes computed" event in the runtime profile becomes 21X faster. This computation is covered by the existing tests, which verifies the equivalency of the new and the old value transfer graphs. Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3 Reviewed-on: http://gerrit.cloudera.org:8080/8098 Reviewed-by: Alex Behm <[email protected]> Tested-by: Impala Public Jenkins --- M fe/src/main/java/org/apache/impala/analysis/Analyzer.java 1 file changed, 7 insertions(+), 16 deletions(-) Approvals: Impala Public Jenkins: Verified Alex Behm: Looks good to me, approved -- To view, visit http://gerrit.cloudera.org:8080/8098 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-MessageType: merged Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3 Gerrit-PatchSet: 4 Gerrit-Project: Impala-ASF Gerrit-Branch: master Gerrit-Owner: Tianyi Wang <[email protected]> Gerrit-Reviewer: Alex Behm <[email protected]> Gerrit-Reviewer: Impala Public Jenkins Gerrit-Reviewer: Tianyi Wang <[email protected]>
