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/20 21:33:01 UTC
[jira] [Resolved] (IMPALA-5932) Improve the performance of
transitive closure computation in value transfer graph
[ https://issues.apache.org/jira/browse/IMPALA-5932?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tianyi Wang resolved IMPALA-5932.
---------------------------------
Resolution: Fixed
Fix Version/s: Impala 2.11.0
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 <al...@cloudera.com>
Tested-by: Impala Public Jenkins
> 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
> Fix For: Impala 2.11.0
>
>
> 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.
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)