You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@impala.apache.org by "Quanlong Huang (Code Review)" <ge...@cloudera.org> on 2019/04/17 03:11:36 UTC
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Quanlong Huang has uploaded this change for review. ( http://gerrit.cloudera.org:8080/13051
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
IMPALA-7957: Fix slot equivalences may be enforced multiple times
Predicates can be divided into three types according to the way they are
generated:
1) origin predicates that come from the query
2) auxiliary equal predicates generated for equivalence between a
label(alias) and its real expression
3) inferred predicates that inferred from the slot equivalences graph
The slot equivalences graph (valueTransferGraph in Analyzer) is
generated by the first two kinds of predicates. Analyzer will create
equivalence predicates for a PlanNode based on the unassigned predicates
and the valueTransferGraph. However, the current implementation can't
avoid creating inferred predicates that are duplicated with previously
created inferred predicates if they have been assigned before.
Duplicated inferred predicates are either redundant or wrong. Say, if we
create predicate p1: s1 = s2 for the current PlanNode and p1 duplicates
with a previously inferred predicate p0: s1 = s2 (same as s2 = s1), we
can prove that p1 is redundant or wrong:
1) p0 must have been assigned. Otherwise, p0 will be in the unassigned
conjuncts list and p1 won't be created.
2) p0 must have been assigned to an offspring node of the current
PlanNode since we create the PlanNodes in a depth first manner.
3) The origin predicates that infer to p0 have been assigned to an
offspring node too.
Then, rows that should be rejected have been filtered out either by p0
or the origin predicates that infer to p0. What's worse, assigning p1 on
top of the origin predicates may wrongly reject rows. Hence, p1 is
either redundant or wrong.
In this patch, we check the existence of previously inferred equivalence
predicates before creating a predicate. Also add some useful TRACE level
logs.
Tests:
* Add tests for UNIONs in inline-view.test
* Run all tests locally in CORE exploration strategy
Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
---
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
M fe/src/main/java/org/apache/impala/analysis/BinaryPredicate.java
M fe/src/main/java/org/apache/impala/analysis/SlotRef.java
M fe/src/main/java/org/apache/impala/planner/SingleNodePlanner.java
M testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
5 files changed, 292 insertions(+), 9 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/51/13051/2
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 2
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 3:
Oh! Thanks for the missing case!
I'll refactor the patch later to handle this problem. Just be busy on some other stuff these days...
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Sat, 27 Apr 2019 02:10:46 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Tim Armstrong (Code Review)" <ge...@cloudera.org>.
Tim Armstrong has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 3:
(4 comments)
I'm afraid I found a case that this doesn't handle, i.e. the solution is incomplete. I think the issue with the current approach is that it tracks the exact set of predicates that were placed, but createEquivConjuncts() can enumerate predicates derived from any pair of slots in the equivalence class.
I think this is on the right track, but I think maybe we need to take the set of predicates that were already assigned for pairs of slots within the tuple, then union the sets in partialEquivSlots() based on those predicates.
SELECT t.id, t2.id
FROM functional.alltypestiny t
LEFT JOIN
(SELECT id, int_col, smallint_col
FROM functional.alltypestiny
WHERE int_col = id and smallint_col = id and tinyint_col = id) t2
ON (t.id = t2.id)
UNION ALL
VALUES (NULL, NULL)
http://gerrit.cloudera.org:8080/#/c/13051/3//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/13051/3//COMMIT_MSG@43
PS3, Line 43: * Run all tests locally in CORE exploration strategy
Can you also add the repro query to an end-to-end inline-view test, just to confirm that it produces the expected results.
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java@220
PS3, Line 220: infereed
inferred
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java@221
PS3, Line 221: public final Map<Pair<SlotId, SlotId>, ExprId> inferredConjunctsBySlots =
Can you document the invariant that both orders of every pair must be added, i.e.
inferredConjunctsBySlots[(a, b)] = c <=> inferredConjunctsBySlots[(b, a)] = c?
Or actually, maybe it's better to normalise the pairs, e.g. so that the lower SlotId is always the first one in the pair.
http://gerrit.cloudera.org:8080/#/c/13051/3/testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
File testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test:
http://gerrit.cloudera.org:8080/#/c/13051/3/testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test@1833
PS3, Line 1833: ====
Some more test cases:
# Add the same predicate *outside* the left join, it should still be enforced.
SELECT t.id
FROM functional.alltypestiny t
LEFT JOIN
(SELECT id, int_col
FROM functional.alltypestiny
WHERE int_col = id) t2
ON (t.id = t2.id) where t2.id = t2.int_col
UNION ALL
VALUES (NULL);
# Same thing except with a predicate on a different column (i.e. adding it to the equivalence class)
SELECT t.id, t2.id
FROM functional.alltypestiny t
LEFT JOIN
(SELECT id, int_col, smallint_col
FROM functional.alltypestiny
WHERE int_col = id) t2
ON (t.id = t2.id) where t2.int_col = t2.smallint_col
UNION ALL
VALUES (NULL, NULL)
# Multiple predicates that must not be placed above the join
SELECT t.id, t2.id
FROM functional.alltypestiny t
LEFT JOIN
(SELECT id, int_col, smallint_col
FROM functional.alltypestiny
WHERE int_col = id and smallint_col = id) t2
ON (t.id = t2.id)
UNION ALL
VALUES (NULL, NULL);
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Fri, 26 Apr 2019 16:49:29 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 3:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/2871/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Wed, 24 Apr 2019 01:56:54 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Tim Armstrong (Code Review)" <ge...@cloudera.org>.
Tim Armstrong has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 5: Code-Review+2
Sorry for the slow turnaround. Greatly appreciate your work on this - thank you for fixing such a tricky bug.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Mon, 03 Jun 2019 18:38:05 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Tim Armstrong (Code Review)" <ge...@cloudera.org>.
Tim Armstrong has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 5:
I need to carve out some time to understand the new patchset. I think the approach makes sense but it needs a bit of thought.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Thu, 23 May 2019 22:13:13 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 5:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/3192/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Mon, 13 May 2019 06:52:46 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 5: Verified+1
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Tue, 04 Jun 2019 00:20:00 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 2:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/2810/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 2
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Wed, 17 Apr 2019 03:52:25 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Tim Armstrong (Code Review)" <ge...@cloudera.org>.
Tim Armstrong has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 3:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java@1840
PS3, Line 1840: // Loop over all pairs of equivalent slots and merge their disjoint slots sets,
I did a proof-of-concept fix that solved the bug I found by checking if there was any pair of values in slotIds that had an entry in inferredConjunctsBySlots and then skipping over the equivalence class. This seems to solve the issue. There might be a more elegant way to factor it.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Mon, 29 Apr 2019 15:49:22 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 2:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/13051/2/testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
File testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test:
http://gerrit.cloudera.org:8080/#/c/13051/2/testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test@1760
PS2, Line 1760: ====
> Can you add some tests with ORDER BY LIMIT and GROUP BY in the first branch
Sure
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 2
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Fri, 19 Apr 2019 14:48:24 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 5:
Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/4391/ DRY_RUN=true
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Mon, 03 Jun 2019 18:47:12 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Tim Armstrong (Code Review)" <ge...@cloudera.org>.
Tim Armstrong has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 2:
(1 comment)
I'm struggling to wrap my head around this but in the meantime have a couple of ideas for ests.
http://gerrit.cloudera.org:8080/#/c/13051/2/testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
File testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test:
http://gerrit.cloudera.org:8080/#/c/13051/2/testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test@1760
PS2, Line 1760: ====
Can you add some tests with ORDER BY LIMIT and GROUP BY in the first branch of the union? Just to confirm that there isn't a variant of the bug since there's some different logic with those code paths.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 2
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Thu, 18 Apr 2019 00:15:06 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 4:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/13051/4/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:
http://gerrit.cloudera.org:8080/#/c/13051/4/fe/src/main/java/org/apache/impala/analysis/Analyzer.java@1822
PS4, Line 1822: LOG.trace("Previously assigned predicates: " + Expr.debugString(inferredConjuncts));
line too long (92 > 90)
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 4
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Mon, 13 May 2019 05:56:01 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Tim Armstrong, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/13051
to look at the new patch set (#3).
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
IMPALA-7957: Fix slot equivalences may be enforced multiple times
Predicates can be divided into three types according to the way they are
generated:
1) origin predicates that come from the query
2) auxiliary equal predicates generated for equivalence between a
label(alias) and its real expression
3) inferred predicates that inferred from the slot equivalences graph
The slot equivalences graph (valueTransferGraph in Analyzer) is
generated by the first two kinds of predicates. Analyzer will create
equivalence predicates for a PlanNode based on the unassigned predicates
and the valueTransferGraph. However, the current implementation can't
avoid creating inferred predicates that are duplicated with previously
created inferred predicates if they have been assigned before.
Duplicated inferred predicates are either redundant or wrong. Say, if we
create predicate p1: s1 = s2 for the current PlanNode and p1 duplicates
with a previously inferred predicate p0: s1 = s2 (same as s2 = s1), we
can prove that p1 is redundant or wrong:
1) p0 must have been assigned. Otherwise, p0 will be in the unassigned
conjuncts list and p1 won't be created.
2) p0 must have been assigned to an offspring node of the current
PlanNode since we create the PlanNodes in a depth first manner.
3) The origin predicates that infer to p0 have been assigned to an
offspring node too.
Then, rows that should be rejected have been filtered out either by p0
or the origin predicates that infer to p0. What's worse, assigning p1 on
top of the origin predicates may wrongly reject rows. Hence, p1 is
either redundant or wrong.
In this patch, we check the existence of previously inferred equivalence
predicates before creating a predicate. Also add some useful TRACE level
logs.
Tests:
* Add tests for UNIONs in inline-view.test
* Run all tests locally in CORE exploration strategy
Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
---
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
M fe/src/main/java/org/apache/impala/analysis/BinaryPredicate.java
M fe/src/main/java/org/apache/impala/analysis/SlotRef.java
M fe/src/main/java/org/apache/impala/planner/SingleNodePlanner.java
M testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
5 files changed, 365 insertions(+), 9 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/51/13051/3
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Tim Armstrong, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/13051
to look at the new patch set (#4).
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
IMPALA-7957: Fix slot equivalences may be enforced multiple times
Predicates can be divided into three types according to the way they are
generated:
1) origin predicates that come from the query
2) auxiliary equal predicates generated for equivalence between a
label(alias) and its real expression
3) inferred predicates that inferred from the slot equivalences graph
The slot equivalences graph (valueTransferGraph in Analyzer) is
generated by the first two kinds of predicates. Analyzer will create
equivalence predicates for a PlanNode based on the unassigned predicates
and the valueTransferGraph. However, the current implementation can't
avoid creating inferred predicates that are duplicated with previously
created inferred predicates if they have been assigned before.
Duplicated inferred predicates are either redundant or wrong. Say, if we
create predicate p1: s1 = s2 for the current PlanNode and p1 duplicates
with a previously inferred predicate p0: s1 = s2 (same as s2 = s1), we
can prove that p1 is redundant or wrong:
1) p0 must have been assigned. Otherwise, p0 will be in the unassigned
conjuncts list and p1 won't be created.
2) p0 must have been assigned to an offspring node of the current
PlanNode since we create the PlanNodes in a depth first manner.
3) The origin predicates that infer to p0 have been assigned to an
offspring node too.
Then, rows that should be rejected have been filtered out either by p0
or the origin predicates that infer to p0. What's worse, assigning p1 on
top of the origin predicates may wrongly reject rows. Hence, p1 is
either redundant or wrong.
In inferring predicates based on slot equivalence (createEquivConjuncts)
we should update partialEquivSlots based on the previously assigned
equivalence predicates. So slot equivalence won't be enforced multiple
times.
This patch also adds some useful TRACE level logs.
Tests:
* Add tests for UNIONs in inline-view.test
* Run all tests locally in CORE exploration strategy
Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
---
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
M fe/src/main/java/org/apache/impala/analysis/BinaryPredicate.java
M fe/src/main/java/org/apache/impala/analysis/SlotDescriptor.java
M fe/src/main/java/org/apache/impala/analysis/SlotRef.java
M fe/src/main/java/org/apache/impala/planner/SingleNodePlanner.java
M testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
6 files changed, 482 insertions(+), 13 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/51/13051/4
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 4
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Tim Armstrong (Code Review)" <ge...@cloudera.org>.
Tim Armstrong has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
IMPALA-7957: Fix slot equivalences may be enforced multiple times
Predicates can be divided into three types according to the way they are
generated:
1) origin predicates that come from the query
2) auxiliary equal predicates generated for equivalence between a
label(alias) and its real expression
3) inferred predicates that inferred from the slot equivalences graph
The slot equivalences graph (valueTransferGraph in Analyzer) is
generated by the first two kinds of predicates. Analyzer will create
equivalence predicates for a PlanNode based on the unassigned predicates
and the valueTransferGraph. However, the current implementation can't
avoid creating inferred predicates that are duplicated with previously
created inferred predicates if they have been assigned before.
Duplicated inferred predicates are either redundant or wrong. Say, if we
create predicate p1: s1 = s2 for the current PlanNode and p1 duplicates
with a previously inferred predicate p0: s1 = s2 (same as s2 = s1), we
can prove that p1 is redundant or wrong:
1) p0 must have been assigned. Otherwise, p0 will be in the unassigned
conjuncts list and p1 won't be created.
2) p0 must have been assigned to an offspring node of the current
PlanNode since we create the PlanNodes in a depth first manner.
3) The origin predicates that infer to p0 have been assigned to an
offspring node too.
Then, rows that should be rejected have been filtered out either by p0
or the origin predicates that infer to p0. What's worse, assigning p1 on
top of the origin predicates may wrongly reject rows. Hence, p1 is
either redundant or wrong.
In inferring predicates based on slot equivalence (createEquivConjuncts)
we should update partialEquivSlots based on the previously assigned
equivalence predicates. So slot equivalence won't be enforced multiple
times.
This patch also adds some useful TRACE level logs.
Tests:
* Add tests for UNIONs in inline-view.test
* Run all tests locally in CORE exploration strategy
Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Reviewed-on: http://gerrit.cloudera.org:8080/13051
Reviewed-by: Tim Armstrong <ta...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
M fe/src/main/java/org/apache/impala/analysis/BinaryPredicate.java
M fe/src/main/java/org/apache/impala/analysis/SlotDescriptor.java
M fe/src/main/java/org/apache/impala/analysis/SlotRef.java
M fe/src/main/java/org/apache/impala/planner/SingleNodePlanner.java
M testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
6 files changed, 482 insertions(+), 13 deletions(-)
Approvals:
Tim Armstrong: Looks good to me, approved
Impala Public Jenkins: Verified
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 4:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/3191/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 4
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Mon, 13 May 2019 06:48:34 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Tim Armstrong, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/13051
to look at the new patch set (#5).
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
IMPALA-7957: Fix slot equivalences may be enforced multiple times
Predicates can be divided into three types according to the way they are
generated:
1) origin predicates that come from the query
2) auxiliary equal predicates generated for equivalence between a
label(alias) and its real expression
3) inferred predicates that inferred from the slot equivalences graph
The slot equivalences graph (valueTransferGraph in Analyzer) is
generated by the first two kinds of predicates. Analyzer will create
equivalence predicates for a PlanNode based on the unassigned predicates
and the valueTransferGraph. However, the current implementation can't
avoid creating inferred predicates that are duplicated with previously
created inferred predicates if they have been assigned before.
Duplicated inferred predicates are either redundant or wrong. Say, if we
create predicate p1: s1 = s2 for the current PlanNode and p1 duplicates
with a previously inferred predicate p0: s1 = s2 (same as s2 = s1), we
can prove that p1 is redundant or wrong:
1) p0 must have been assigned. Otherwise, p0 will be in the unassigned
conjuncts list and p1 won't be created.
2) p0 must have been assigned to an offspring node of the current
PlanNode since we create the PlanNodes in a depth first manner.
3) The origin predicates that infer to p0 have been assigned to an
offspring node too.
Then, rows that should be rejected have been filtered out either by p0
or the origin predicates that infer to p0. What's worse, assigning p1 on
top of the origin predicates may wrongly reject rows. Hence, p1 is
either redundant or wrong.
In inferring predicates based on slot equivalence (createEquivConjuncts)
we should update partialEquivSlots based on the previously assigned
equivalence predicates. So slot equivalence won't be enforced multiple
times.
This patch also adds some useful TRACE level logs.
Tests:
* Add tests for UNIONs in inline-view.test
* Run all tests locally in CORE exploration strategy
Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
---
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
M fe/src/main/java/org/apache/impala/analysis/BinaryPredicate.java
M fe/src/main/java/org/apache/impala/analysis/SlotDescriptor.java
M fe/src/main/java/org/apache/impala/analysis/SlotRef.java
M fe/src/main/java/org/apache/impala/planner/SingleNodePlanner.java
M testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
6 files changed, 482 insertions(+), 13 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/51/13051/5
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Tim Armstrong (Code Review)" <ge...@cloudera.org>.
Tim Armstrong has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 3:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java@221
PS3, Line 221: public final Map<Pair<SlotId, SlotId>, ExprId> inferredConjunctsBySlots =
> Can you document the invariant that both orders of every pair must be added
Maybe this isn't relevant any more if we change the approach
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Fri, 26 Apr 2019 16:50:07 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 3:
(1 comment)
> Patch Set 3:
>
> (1 comment)
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java
File fe/src/main/java/org/apache/impala/analysis/Analyzer.java:
http://gerrit.cloudera.org:8080/#/c/13051/3/fe/src/main/java/org/apache/impala/analysis/Analyzer.java@1840
PS3, Line 1840: // Loop over all pairs of equivalent slots and merge their disjoint slots sets,
> I did a proof-of-concept fix that solved the bug I found by checking if the
Yes, that would fix the extra bug. I think a more elegant way is to union the slots in current tuple based on previous inferred conjuncts when we init the partialEquivSlots. Unfortunately, it doesn't work. I'm still confused about this and going to look deeper.
Besides, my proof may need deeper review since I found several other places could infer predicates too, e.g. getHashLookupJoinConjuncts, createJoinNode.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Tue, 30 Apr 2019 13:55:37 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 2:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/13051/2/fe/src/main/java/org/apache/impala/planner/SingleNodePlanner.java
File fe/src/main/java/org/apache/impala/planner/SingleNodePlanner.java:
http://gerrit.cloudera.org:8080/#/c/13051/2/fe/src/main/java/org/apache/impala/planner/SingleNodePlanner.java@1131
PS2, Line 1131: we
: // need to make sure that equivalences are not enforced multiple times
Actually, I got the idea from this comment and found that it should be enforced in other places too. Hope my provement is correct.
http://gerrit.cloudera.org:8080/#/c/13051/2/testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test
File testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test:
http://gerrit.cloudera.org:8080/#/c/13051/2/testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test@1760
PS2, Line 1760: ====
> Sure
Done
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 2
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Wed, 24 Apr 2019 01:10:49 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7957: Fix slot equivalences may be enforced multiple times
Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/13051 )
Change subject: IMPALA-7957: Fix slot equivalences may be enforced multiple times
......................................................................
Patch Set 5:
Updated the patch. Instead of tracking the registered inferred predicates, we should track all the assigned EQ binary predicates grouped by TupleId. When inferring predicates, we should respect those predicates by union the PartialEquvSlots based on them.
--
To view, visit http://gerrit.cloudera.org:8080/13051
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ida2d5d8149b217e18ebae61e136848162503653e
Gerrit-Change-Number: 13051
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Comment-Date: Tue, 14 May 2019 09:53:24 +0000
Gerrit-HasComments: No