impala-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Tianyi Wang (Code Review)" <ger...@cloudera.org>
Subject [Impala-ASF-CR] IMPALA-5932: Improve the transitive closure computation performance in value transfer graph
Date Tue, 19 Sep 2017 01:22:25 GMT
Tianyi Wang has uploaded a new change for review.

  http://gerrit.cloudera.org:8080/8098

Change subject: IMPALA-5932: Improve the transitive closure computation performance in value
transfer graph
......................................................................

IMPALA-5932: Improve the transitive closure computation performance in value transfer graph

This patch implements Floyd-Warshall algorithm for the transitive
closure computation in 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
---
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
1 file changed, 7 insertions(+), 13 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/98/8098/1
-- 
To view, visit http://gerrit.cloudera.org:8080/8098
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newchange
Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3
Gerrit-PatchSet: 1
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tianyi Wang <twang@cloudera.com>

Mime
View raw message