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

Posted to reviews@impala.apache.org by "Tianyi Wang (Code Review)" <ge...@cloudera.org> on 2017/09/19 01:22:25 UTC

[Impala-ASF-CR] IMPALA-5932: Improve the transitive closure computation performance in value transfer graph

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 <tw...@cloudera.com>

[Impala-ASF-CR] IMPALA-5932: Improve transitive closure computation performance in FE

Posted by "Tianyi Wang (Code Review)" <ge...@cloudera.org>.

Tianyi Wang has posted comments on this change.

Change subject: IMPALA-5932: Improve transitive closure computation performance in FE
......................................................................


Patch Set 2:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8098/2/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:

Line 2703:               valueTransfer_[p[i]][p[k]] |= valueTransfer_[p[i]][p[j]] &&
> The following is sufficient because L2701 already establishes that valueTra
Done


-- 
To view, visit http://gerrit.cloudera.org:8080/8098
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3
Gerrit-PatchSet: 2
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tianyi Wang <tw...@cloudera.com>
Gerrit-Reviewer: Alex Behm <al...@cloudera.com>
Gerrit-Reviewer: Tianyi Wang <tw...@cloudera.com>
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-5932: Improve transitive closure computation performance in FE

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change.

Change subject: IMPALA-5932: Improve transitive closure computation performance in FE
......................................................................


Patch Set 3:

Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/1236/

-- 
To view, visit http://gerrit.cloudera.org:8080/8098
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3
Gerrit-PatchSet: 3
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tianyi Wang <tw...@cloudera.com>
Gerrit-Reviewer: Alex Behm <al...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins
Gerrit-Reviewer: Tianyi Wang <tw...@cloudera.com>
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-5932: Improve transitive closure computation performance in FE

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change.

Change subject: IMPALA-5932: Improve transitive closure computation performance in FE
......................................................................


Patch Set 3: Verified+1

-- 
To view, visit http://gerrit.cloudera.org:8080/8098
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3
Gerrit-PatchSet: 3
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tianyi Wang <tw...@cloudera.com>
Gerrit-Reviewer: Alex Behm <al...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins
Gerrit-Reviewer: Tianyi Wang <tw...@cloudera.com>
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-5932: Improve transitive closure computation performance in FE

Posted by "Alex Behm (Code Review)" <ge...@cloudera.org>.

Alex Behm has posted comments on this change.

Change subject: IMPALA-5932: Improve transitive closure computation performance in FE
......................................................................


Patch Set 3: Code-Review+2

-- 
To view, visit http://gerrit.cloudera.org:8080/8098
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3
Gerrit-PatchSet: 3
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tianyi Wang <tw...@cloudera.com>
Gerrit-Reviewer: Alex Behm <al...@cloudera.com>
Gerrit-Reviewer: Tianyi Wang <tw...@cloudera.com>
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-5932: Improve transitive closure computation performance in FE

Posted by "Tianyi Wang (Code Review)" <ge...@cloudera.org>.

Tianyi Wang has posted comments on this change.

Change subject: IMPALA-5932: Improve transitive closure computation performance in FE
......................................................................


Patch Set 2:

(5 comments)

http://gerrit.cloudera.org:8080/#/c/8098/1//COMMIT_MSG
Commit Message:

Line 7: IMPALA-5932: Improve transitive closure computation performance in FE
> Shrink to fit
Done


Line 9: This patch implements the Floyd-Warshall algorithm for the transitive
> the Floyd-Warshall algorithm
Done


Line 10: closure computation for the value transfer graph, replacing the existing
> closure computation for the value transfer graph
Done


http://gerrit.cloudera.org:8080/#/c/8098/1/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:

Line 2703:               valueTransfer_[p[i]][p[k]] |= valueTransfer_[p[i]][p[j]] &&
> Comment that this optimization works because our graphs are typically spars
Done


http://gerrit.cloudera.org:8080/#/c/8098/2/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:

Line 2698
Removed this comment since the graph here is not a DAG:  
 select * from (select * from tb0) v0 left join (select * from tb0) v1 on v0.c=v1.c left join (select * from tb0) v2 on v1.c=v2.c left join (select * from tb0) v3 on v2.c=v3.c where v0.c=v3.c;


-- 
To view, visit http://gerrit.cloudera.org:8080/8098
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3
Gerrit-PatchSet: 2
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tianyi Wang <tw...@cloudera.com>
Gerrit-Reviewer: Alex Behm <al...@cloudera.com>
Gerrit-Reviewer: Tianyi Wang <tw...@cloudera.com>
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-5932: Improve transitive closure computation performance in FE

Posted by "Tianyi Wang (Code Review)" <ge...@cloudera.org>.

Tianyi Wang has uploaded a new patch set (#3).

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
---
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
1 file changed, 7 insertions(+), 16 deletions(-)


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

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3
Gerrit-PatchSet: 3
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tianyi Wang <tw...@cloudera.com>
Gerrit-Reviewer: Alex Behm <al...@cloudera.com>
Gerrit-Reviewer: Tianyi Wang <tw...@cloudera.com>

[Impala-ASF-CR] IMPALA-5932: Improve transitive closure computation performance in FE

Posted by "Alex Behm (Code Review)" <ge...@cloudera.org>.

Alex Behm has posted comments on this change.

Change subject: IMPALA-5932: Improve transitive closure computation performance in FE
......................................................................


Patch Set 2:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8098/2/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:

Line 2703:               valueTransfer_[p[i]][p[k]] |= valueTransfer_[p[i]][p[j]] &&
The following is sufficient because L2701 already establishes that valueTransfer_[p[i]][p[j]] is true

valueTransfer_[p[i]][p[k]] |= valueTransfer_[p[j]][p[k]];


-- 
To view, visit http://gerrit.cloudera.org:8080/8098
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: Idb00e3c1f904e60ae25567a52b4bf0809a84c6b3
Gerrit-PatchSet: 2
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tianyi Wang <tw...@cloudera.com>
Gerrit-Reviewer: Alex Behm <al...@cloudera.com>
Gerrit-Reviewer: Tianyi Wang <tw...@cloudera.com>
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-5932: Improve transitive closure computation performance in FE

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

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 <al...@cloudera.com>
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 <tw...@cloudera.com>
Gerrit-Reviewer: Alex Behm <al...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins
Gerrit-Reviewer: Tianyi Wang <tw...@cloudera.com>