IMPALA-7090: Limit the size of expr created by EqualityDisjunctsToInRule Currently EqualityDisjunctsToInRule introduced in IMPALA-5280 might create an expr with unlimited number of children and fails a query, which should be avoided. The easy solution is to not apply the rewrite when the number of children is large.
Change-Id: Ie40c3210271a9e3c7f1b2b869a8c2ec8bacaa72a Reviewed-on: http://gerrit.cloudera.org:8080/10528 Reviewed-by: Tianyi Wang <[email protected]> Tested-by: Impala Public Jenkins <[email protected]> Project: http://git-wip-us.apache.org/repos/asf/impala/repo Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/aba8fdf8 Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/aba8fdf8 Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/aba8fdf8 Branch: refs/heads/master Commit: aba8fdf8b2e1831986b82cec6f79fc71586e6b01 Parents: 84b55c6 Author: Tianyi Wang <[email protected]> Authored: Fri May 25 18:04:17 2018 -0700 Committer: Impala Public Jenkins <[email protected]> Committed: Wed May 30 09:28:29 2018 +0000 ---------------------------------------------------------------------- .../rewrite/EqualityDisjunctsToInRule.java | 32 ++++++----- .../impala/analysis/ExprRewriterTest.java | 58 +++++++++++++++++++- 2 files changed, 75 insertions(+), 15 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/impala/blob/aba8fdf8/fe/src/main/java/org/apache/impala/rewrite/EqualityDisjunctsToInRule.java ---------------------------------------------------------------------- diff --git a/fe/src/main/java/org/apache/impala/rewrite/EqualityDisjunctsToInRule.java b/fe/src/main/java/org/apache/impala/rewrite/EqualityDisjunctsToInRule.java index d1a2ca7..deebefa 100644 --- a/fe/src/main/java/org/apache/impala/rewrite/EqualityDisjunctsToInRule.java +++ b/fe/src/main/java/org/apache/impala/rewrite/EqualityDisjunctsToInRule.java @@ -53,10 +53,10 @@ public class EqualityDisjunctsToInRule implements ExprRewriteRule { } /** - * Takes the children of an OR predicate and attempts to combine them into a single IN predicate. - * The transformation is applied if one of the children is an IN predicate and the other child - * is a compatible IN predicate or equality predicate. Returns the transformed expr or null - * if no transformation was possible. + * Takes the children of an OR predicate and attempts to combine them into a single IN + * predicate. The transformation is applied if one of the children is an IN predicate + * and the other child is a compatible IN predicate or equality predicate. Returns the + * transformed expr or null if no transformation was possible. */ private Expr rewriteInAndOtherExpr(Expr child0, Expr child1) { InPredicate inPred = null; @@ -64,27 +64,31 @@ public class EqualityDisjunctsToInRule implements ExprRewriteRule { if (child0 instanceof InPredicate) { inPred = (InPredicate) child0; otherPred = child1; - } - else if (child1 instanceof InPredicate) { + } else if (child1 instanceof InPredicate) { inPred = (InPredicate) child1; otherPred = child0; } - if (inPred == null || inPred.isNotIn() || inPred.contains(Subquery.class)) return null; - if (!inPred.getChild(0).equals(otherPred.getChild(0))) return null; + if (inPred == null || inPred.isNotIn() || inPred.contains(Subquery.class) || + !inPred.getChild(0).equals(otherPred.getChild(0))) { + return null; + } // other predicate can be OR predicate or IN predicate List<Expr> newInList = Lists.newArrayList( inPred.getChildren().subList(1, inPred.getChildren().size())); if (Expr.IS_EXPR_EQ_LITERAL_PREDICATE.apply(otherPred)) { + if (newInList.size() + 1 == Expr.EXPR_CHILDREN_LIMIT) return null; newInList.add(otherPred.getChild(1)); - } else - if (otherPred instanceof InPredicate && !((InPredicate) otherPred).isNotIn() - && !otherPred.contains(Subquery.class)) { - newInList.addAll( - otherPred.getChildren().subList(1, otherPred.getChildren().size())); - } else { + } else if (otherPred instanceof InPredicate && !((InPredicate) otherPred).isNotIn() + && !otherPred.contains(Subquery.class)) { + if (newInList.size() + otherPred.getChildren().size() > Expr.EXPR_CHILDREN_LIMIT) { return null; } + newInList.addAll( + otherPred.getChildren().subList(1, otherPred.getChildren().size())); + } else { + return null; + } return new InPredicate(inPred.getChild(0), newInList, false); } http://git-wip-us.apache.org/repos/asf/impala/blob/aba8fdf8/fe/src/test/java/org/apache/impala/analysis/ExprRewriterTest.java ---------------------------------------------------------------------- diff --git a/fe/src/test/java/org/apache/impala/analysis/ExprRewriterTest.java b/fe/src/test/java/org/apache/impala/analysis/ExprRewriterTest.java index bebc6ba..de58d31 100644 --- a/fe/src/test/java/org/apache/impala/analysis/ExprRewriterTest.java +++ b/fe/src/test/java/org/apache/impala/analysis/ExprRewriterTest.java @@ -21,6 +21,7 @@ import org.apache.impala.analysis.AnalysisContext.AnalysisResult; import org.apache.impala.common.AnalysisException; import org.apache.impala.common.ImpalaException; import org.apache.impala.common.RuntimeEnv; +import org.apache.impala.rewrite.EqualityDisjunctsToInRule; import org.apache.impala.rewrite.ExprRewriteRule; import org.apache.impala.rewrite.ExprRewriter; import org.junit.Assert; @@ -30,7 +31,7 @@ import com.google.common.base.Preconditions; /** * Tests that the ExprRewriter framework covers all clauses as well as nested statements. - * Does not test specific rewrite rules. + * It also tests some specific rewrite rules. */ public class ExprRewriterTest extends AnalyzerTest { @@ -167,4 +168,59 @@ public class ExprRewriterTest extends AnalyzerTest { RewritesOk("delete functional_kudu.testtbl where exists (" + stmt_ + ")", 24, 12); } } + + /** + * construct an in-list: string_col in [offset ... offset + length) + */ + private void CreateInList(int offset, int length, StringBuilder stmtSb) { + stmtSb.append("string_col in("); + for (int j = 0; j < length - 1; ++j) { + stmtSb.append("'c").append(offset + j).append("',"); + } + stmtSb.append("'c").append(offset + length - 1).append("')"); + } + + private void CheckNumChangesByEqualityDisjunctsToInRule( + String stmt, int expectedNumChanges) throws ImpalaException { + StatementBase parsedStmt = (StatementBase) ParsesOk(stmt); + AnalyzesOkNoRewrite(parsedStmt); + ExprRewriter rewriter = new ExprRewriter(EqualityDisjunctsToInRule.INSTANCE); + parsedStmt.rewriteExprs(rewriter); + Assert.assertEquals(expectedNumChanges, rewriter.getNumChanges()); + } + + @Test + public void TestEqualityDisjunctsToInRuleSizeLimit() throws ImpalaException { + String stmtPrefix = "select count(*) from functional.alltypes where ( "; + // Test that EqualityDisjunctsToInRule doesn't create an expr with a number of + // children exceeding the limit. + { + // Create a disjunct with 2 in-lists of length Expr.EXPR_CHILDREN_LIMIT - 1. + StringBuilder stmtSb = new StringBuilder(stmtPrefix); + for (int i = 0; i < 2; ++i) { + int offset = (Expr.EXPR_CHILDREN_LIMIT - 1) * i; + CreateInList(offset, Expr.EXPR_CHILDREN_LIMIT - 1, stmtSb); + if (i != 1) stmtSb.append(" or "); + } + stmtSb.append(")"); + CheckNumChangesByEqualityDisjunctsToInRule(stmtSb.toString(), 0); + } + { + // Create a disjunct with an in-list of length Expr.EXPR_CHILDREN_LIMIT - 1 and a + // EQ predicate. + StringBuilder stmtSb = new StringBuilder(stmtPrefix); + CreateInList(0, Expr.EXPR_CHILDREN_LIMIT - 1, stmtSb); + stmtSb.append("or string_col='").append(Expr.EXPR_CHILDREN_LIMIT - 1).append("')"); + CheckNumChangesByEqualityDisjunctsToInRule(stmtSb.toString(), 0); + } + { + // Create a disjunct with an in-list of length Expr.EXPR_CHILDREN_LIMIT - 2 and 2 + // EQ predicates. + StringBuilder stmtSb = new StringBuilder(stmtPrefix); + CreateInList(0, Expr.EXPR_CHILDREN_LIMIT - 2, stmtSb); + stmtSb.append("or string_col='").append(Expr.EXPR_CHILDREN_LIMIT - 2) + .append("' or string_col='").append(Expr.EXPR_CHILDREN_LIMIT - 1).append("')"); + CheckNumChangesByEqualityDisjunctsToInRule(stmtSb.toString(), 1); + } + } }
