[impala] 02/04: IMPALA-9358: Query slowdown with inline views and hundreds of columns

[ta...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

tarmstrong pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git

commit d971b19dee289d8fe54eebf484cb14ee6d56f60e
Author: Kurt Deschler <kd...@cloudera.com>
AuthorDate: Tue Feb 4 19:12:22 2020 -0500

    IMPALA-9358: Query slowdown with inline views and hundreds of columns
    
    IMPALA-8386 introduced an expensive precondition check using the function
    ExprSubstitutionMap.checkComposedFrom(). This check has significant
    performance impact on statements that contain inline views with hundreds
    of columns. Most of the cost is in the get() calls used to find
    expressions in the local substitution map.
    
    The fix is to add a getWithHint() call that uses the current loop index as a
    starting point to search for expressions. This leverages the fact that
    expressions have identical positions in both substitution maps in most
    common cases.
    
    A more generic approach would be to accelerate expression equality search
    using hash functions but that would be a much riskier fix and Impala
    currently lacks the infrasturucture to so.
    
    Testing:
    Performance testing with a query with 1000 expressions of the
    following form:
      with a as (select c1 c1, c1 c2, c1 c3, ... from t)
      select c1, c2, c3, ... from a;
    
    repro query went from 12 sec to 1 sec.
    There was no noticeable time spent in the precondition now.
    
    Change-Id: I77423d9c10e1edbb505cb210b5c072281b5d7cfc
    Reviewed-on: http://gerrit.cloudera.org:8080/15157
    Reviewed-by: Impala Public Jenkins <im...@cloudera.com>
    Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
 .../apache/impala/analysis/ExprSubstitutionMap.java    | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/fe/src/main/java/org/apache/impala/analysis/ExprSubstitutionMap.java b/fe/src/main/java/org/apache/impala/analysis/ExprSubstitutionMap.java
index baf7b61..087ed6c 100644
--- a/fe/src/main/java/org/apache/impala/analysis/ExprSubstitutionMap.java
+++ b/fe/src/main/java/org/apache/impala/analysis/ExprSubstitutionMap.java
@@ -71,6 +71,20 @@ public final class ExprSubstitutionMap {
   }
 
   /**
+   * Same as get() but start at index 'hint'
+   */
+  public Expr getWithHint(Expr lhsExpr, int hint) {
+    for (int i = hint; i < lhs_.size(); ++i) {
+      if (lhsExpr.equals(lhs_.get(i))) return rhs_.get(i);
+    }
+    if (lhs_.size() < hint) hint = lhs_.size();
+    for (int i = 0; i < hint; ++i) {
+      if (lhsExpr.equals(lhs_.get(i))) return rhs_.get(i);
+    }
+    return null;
+  }
+
+  /**
    * Returns true if the smap contains a mapping for lhsExpr.
    */
   public boolean containsMappingFor(Expr lhsExpr) {
@@ -186,8 +200,8 @@ public final class ExprSubstitutionMap {
       for (int j = i + 1; j < other.lhs_.size(); ++j) {
         Expr a = other.lhs_.get(i);
         Expr b = other.lhs_.get(j);
-        Expr finalA = get(a);
-        Expr finalB = get(b);
+        Expr finalA = getWithHint(a, i);
+        Expr finalB = getWithHint(b, j);
         if (finalA == null || finalB == null) {
           if (LOG.isTraceEnabled()) {
             if (finalA == null) {