Mailing-List: contact issues-help@drill.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@drill.apache.org
Date: Tue, 20 Oct 2015 18:28:27 +0000 (UTC)
From: "ASF GitHub Bot (JIRA)" <jira@apache.org>
To: issues@drill.apache.org
Message-ID: <JIRA.12903145.1444254122000.9961.1445365707761@Atlassian.JIRA>
In-Reply-To: <JIRA.12903145.1444254122000@Atlassian.JIRA>
References: <JIRA.12903145.1444254122000@Atlassian.JIRA>
 <JIRA.12903145.1444254122461@arcas>
Subject: [jira] [Commented] (DRILL-3912) Common subexpression elimination in
 code generation
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ https://issues.apache.org/jira/browse/DRILL-3912?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14965520#comment-14965520 ] 

ASF GitHub Bot commented on DRILL-3912:
---------------------------------------

Github user jinfengni commented on a diff in the pull request:

    https://github.com/apache/drill/pull/189#discussion_r42534375
  
    --- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/EqualityVisitor.java ---
    @@ -0,0 +1,322 @@
    +/**
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + * <p/>
    + * http://www.apache.org/licenses/LICENSE-2.0
    + * <p/>
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +package org.apache.drill.exec.expr;
    +
    +import com.google.common.collect.Lists;
    +import org.apache.drill.common.expression.BooleanOperator;
    +import org.apache.drill.common.expression.CastExpression;
    +import org.apache.drill.common.expression.ConvertExpression;
    +import org.apache.drill.common.expression.FunctionCall;
    +import org.apache.drill.common.expression.FunctionHolderExpression;
    +import org.apache.drill.common.expression.IfExpression;
    +import org.apache.drill.common.expression.LogicalExpression;
    +import org.apache.drill.common.expression.NullExpression;
    +import org.apache.drill.common.expression.SchemaPath;
    +import org.apache.drill.common.expression.TypedNullConstant;
    +import org.apache.drill.common.expression.ValueExpressions.BooleanExpression;
    +import org.apache.drill.common.expression.ValueExpressions.DateExpression;
    +import org.apache.drill.common.expression.ValueExpressions.Decimal18Expression;
    +import org.apache.drill.common.expression.ValueExpressions.Decimal28Expression;
    +import org.apache.drill.common.expression.ValueExpressions.Decimal38Expression;
    +import org.apache.drill.common.expression.ValueExpressions.Decimal9Expression;
    +import org.apache.drill.common.expression.ValueExpressions.DoubleExpression;
    +import org.apache.drill.common.expression.ValueExpressions.FloatExpression;
    +import org.apache.drill.common.expression.ValueExpressions.IntExpression;
    +import org.apache.drill.common.expression.ValueExpressions.IntervalDayExpression;
    +import org.apache.drill.common.expression.ValueExpressions.IntervalYearExpression;
    +import org.apache.drill.common.expression.ValueExpressions.LongExpression;
    +import org.apache.drill.common.expression.ValueExpressions.QuotedString;
    +import org.apache.drill.common.expression.ValueExpressions.TimeExpression;
    +import org.apache.drill.common.expression.ValueExpressions.TimeStampExpression;
    +import org.apache.drill.common.expression.visitors.AbstractExprVisitor;
    +
    +import java.util.List;
    +
    +public class EqualityVisitor extends AbstractExprVisitor<Boolean,LogicalExpression,RuntimeException> {
    +  @Override
    +  public Boolean visitFunctionCall(FunctionCall call, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof FunctionCall)) {
    +      return false;
    +    }
    +    if (!checkType(call, value)) {
    +      return false;
    +    }
    +    if (!call.getName().equals(((FunctionCall) value).getName())) {
    +      return false;
    +    }
    +    return checkChildren(call, value);
    +  }
    +
    +  @Override
    +  public Boolean visitFunctionHolderExpression(FunctionHolderExpression holder, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof FunctionHolderExpression)) {
    +      return false;
    +    }
    +    if (!checkType(holder, value)) {
    +      return false;
    +    }
    +    if (!holder.getName().equals(((FunctionHolderExpression) value).getName())) {
    +      return false;
    +    }
    +    return checkChildren(holder, value);
    +  }
    +
    +  @Override
    +  public Boolean visitIfExpression(IfExpression ifExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof IfExpression)) {
    +      return false;
    +    }
    +    return checkChildren(ifExpr, value);
    +  }
    +
    +  @Override
    +  public Boolean visitBooleanOperator(BooleanOperator call, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof BooleanOperator)) {
    +      return false;
    +    }
    +    if (!call.getName().equals(((BooleanOperator) value).getName())) {
    +      return false;
    +    }
    +    return checkChildren(call, value);
    +  }
    +
    +  @Override
    +  public Boolean visitSchemaPath(SchemaPath path, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof SchemaPath)) {
    +      return false;
    +    }
    +    return path.equals(value);
    +  }
    +
    +  @Override
    +  public Boolean visitIntConstant(IntExpression intExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof IntExpression)) {
    +      return false;
    +    }
    +    return intExpr.getInt() == ((IntExpression) value).getInt();
    +  }
    +
    +  @Override
    +  public Boolean visitFloatConstant(FloatExpression fExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof FloatExpression)) {
    +      return false;
    +    }
    +    return fExpr.getFloat() == ((FloatExpression) value).getFloat();
    +  }
    +
    +  @Override
    +  public Boolean visitLongConstant(LongExpression intExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof LongExpression)) {
    +      return false;
    +    }
    +    return intExpr.getLong() == ((LongExpression) value).getLong();
    +  }
    +
    +  @Override
    +  public Boolean visitDateConstant(DateExpression intExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof DateExpression)) {
    +      return false;
    +    }
    +    return intExpr.getDate() == ((DateExpression) value).getDate();
    +  }
    +
    +  @Override
    +  public Boolean visitTimeConstant(TimeExpression intExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof TimeExpression)) {
    +      return false;
    +    }
    +    return intExpr.getTime() == ((TimeExpression) value).getTime();
    +  }
    +
    +  @Override
    +  public Boolean visitTimeStampConstant(TimeStampExpression intExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof TimeStampExpression)) {
    +      return false;
    +    }
    +    return intExpr.getTimeStamp() == ((TimeStampExpression) value).getTimeStamp();
    +  }
    +
    +  @Override
    +  public Boolean visitIntervalYearConstant(IntervalYearExpression intExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof IntervalYearExpression)) {
    +      return false;
    +    }
    +    return intExpr.getIntervalYear() == ((IntervalYearExpression) value).getIntervalYear();
    +  }
    +
    +  @Override
    +  public Boolean visitIntervalDayConstant(IntervalDayExpression intExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof IntervalDayExpression)) {
    +      return false;
    +    }
    +    return intExpr.getIntervalDay() == ((IntervalDayExpression) value).getIntervalDay();
    +  }
    +
    +  @Override
    +  public Boolean visitDecimal9Constant(Decimal9Expression decExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof Decimal9Expression)) {
    +      return false;
    +    }
    +    if (decExpr.getIntFromDecimal() != ((Decimal9Expression) value).getIntFromDecimal()) {
    +      return false;
    +    }
    +    if (decExpr.getScale() != ((Decimal9Expression) value).getScale()) {
    +      return false;
    +    }
    +    if (decExpr.getPrecision() != ((Decimal9Expression) value).getPrecision()) {
    +      return false;
    +    }
    +    return true;
    +  }
    +
    +  @Override
    +  public Boolean visitDecimal18Constant(Decimal18Expression decExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof Decimal18Expression)) {
    +      return false;
    +    }
    +    if (decExpr.getLongFromDecimal() != ((Decimal18Expression) value).getLongFromDecimal()) {
    +      return false;
    +    }
    +    if (decExpr.getScale() != ((Decimal18Expression) value).getScale()) {
    +      return false;
    +    }
    +    if (decExpr.getPrecision() != ((Decimal18Expression) value).getPrecision()) {
    +      return false;
    +    }
    +    return true;
    +  }
    +
    +  @Override
    +  public Boolean visitDecimal28Constant(Decimal28Expression decExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof Decimal28Expression)) {
    +      return false;
    +    }
    +    if (decExpr.getBigDecimal() != ((Decimal28Expression) value).getBigDecimal()) {
    +      return false;
    +    }
    +    return true;
    +  }
    +
    +  @Override
    +  public Boolean visitDecimal38Constant(Decimal38Expression decExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof Decimal38Expression)) {
    +      return false;
    +    }
    +    if (decExpr.getBigDecimal() != ((Decimal38Expression) value).getBigDecimal()) {
    +      return false;
    +    }
    +    if (!decExpr.getMajorType().equals(((Decimal38Expression) value).getMajorType())) {
    +      return false;
    +    }
    +    return false;
    +  }
    +
    +  @Override
    +  public Boolean visitDoubleConstant(DoubleExpression dExpr, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof DoubleExpression)) {
    +      return false;
    +    }
    +    return dExpr.getDouble() == ((DoubleExpression) value).getDouble();
    +  }
    +
    +  @Override
    +  public Boolean visitBooleanConstant(BooleanExpression e, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof BooleanExpression)) {
    +      return false;
    +    }
    +    return e.getBoolean() == ((BooleanExpression) value).getBoolean();
    +  }
    +
    +  @Override
    +  public Boolean visitQuotedStringConstant(QuotedString e, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof QuotedString)) {
    +      return false;
    +    }
    +    return e.getString().equals(((QuotedString) value).getString());
    +  }
    +
    +  @Override
    +  public Boolean visitNullExpression(NullExpression e, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof NullExpression)) {
    +      return false;
    +    }
    +    return e.getMajorType().equals(value.getMajorType());
    +  }
    +
    +  @Override
    +  public Boolean visitCastExpression(CastExpression e, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof CastExpression)) {
    +      return false;
    +    }
    +    if (!e.getMajorType().equals(value.getMajorType())) {
    +      return false;
    +    }
    +    return checkChildren(e, value);
    +  }
    +
    +  @Override
    +  public Boolean visitConvertExpression(ConvertExpression e, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof ConvertExpression)) {
    +      return false;
    +    }
    +    if (!e.getConvertFunction().equals(((ConvertExpression) value).getConvertFunction())) {
    +      return false;
    +    }
    +    return checkChildren(e, value);
    +  }
    +
    +  @Override
    +  public Boolean visitNullConstant(TypedNullConstant e, LogicalExpression value) throws RuntimeException {
    +    if (!(value instanceof TypedNullConstant)) {
    +      return false;
    +    }
    +    return e.getMajorType().equals(e.getMajorType());
    +  }
    +
    +  @Override
    +  public Boolean visitUnknown(LogicalExpression e, LogicalExpression value) throws RuntimeException {
    +    if (e instanceof ValueVectorReadExpression && value instanceof ValueVectorReadExpression) {
    +      return visitValueVectorReadExpression((ValueVectorReadExpression) e, (ValueVectorReadExpression) value);
    +    }
    +    return false;
    +  }
    +
    +  private Boolean visitValueVectorReadExpression(ValueVectorReadExpression e, ValueVectorReadExpression value) {
    +    return e.getTypedFieldId().equals(value.getTypedFieldId());
    --- End diff --
    
    Please post the revised patch when it's ready.
    
    In the meantime, I feel it's probably not the best practice that EqualityVisitor relies on the cleaning of cache whenever MappingSet is changed.   For one thing, people would expect EqualityVisitor return true if and only if two expressions are identical by semantics; it should not return true for two semantically different expressions, and only make it work by assuming the cache is cleaned.
    
    Also, if people use Equality for ExpressionHolder later on for other use case, and did not know such trick, then it's likely some bug would be encountered. 
     

> Common subexpression elimination in code generation
> ---------------------------------------------------
>
>                 Key: DRILL-3912
>                 URL: https://issues.apache.org/jira/browse/DRILL-3912
>             Project: Apache Drill
>          Issue Type: Bug
>            Reporter: Steven Phillips
>            Assignee: Jinfeng Ni
>
> Drill currently will evaluate the full expression tree, even if there are redundant subtrees. Many of these redundant evaluations can be eliminated by reusing the results from previously evaluated expression trees.
> For example,
> {code}
> select a + 1, (a + 1)* (a - 1) from t
> {code}
> Will compute the entire (a + 1) expression twice. With CSE, it will only be evaluated once.
> The benefit will be reducing the work done when evaluating expressions, as well as reducing the amount of code that is generated, which could also lead to better JIT optimization.


--
This message was sent by Atlassian JIRA
(v6.3.4#6332)