tajo-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hyun...@apache.org
Subject [08/28] TAJO-1125: Separate logical plan and optimizer into a maven module.
Date Sat, 25 Oct 2014 18:17:57 GMT
http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java
new file mode 100644
index 0000000..84352f0
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java
@@ -0,0 +1,417 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import org.apache.tajo.catalog.Column;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Stack;
+
+public class AlgebraicUtil {
+  
+  /**
+   * Transpose a given comparison expression into the expression 
+   * where the variable corresponding to the target is placed 
+   * on the left-hand side.
+   * 
+   * @param evalNode
+   * @param target
+   * @return Transposed expression
+   */
+  public static EvalNode transpose(EvalNode evalNode, Column target) {
+    BinaryEval commutated;
+
+    if (evalNode instanceof BinaryEval) { // if it is binary
+      BinaryEval binaryEval = (BinaryEval) evalNode;
+      // If the variable is in the right term, inverse the expr.
+      if (!EvalTreeUtil.containColumnRef(binaryEval.getLeftExpr(), target)) {
+        // the commutate method works with a copy of the expr
+        commutated = commutate(binaryEval);
+      } else {
+        try {
+          commutated = (BinaryEval) evalNode.clone();
+        } catch (CloneNotSupportedException e) {
+          throw new AlgebraicException(e);
+        }
+      }
+
+      return _transpose(commutated, target);
+    } else {
+      return evalNode;
+    }
+  }
+  
+  private static EvalNode _transpose(BinaryEval _expr, Column target) {
+     EvalNode expr = eliminateConstantExprs(_expr);
+
+    if (expr instanceof BinaryEval) { // only if expr is a binary operator
+      BinaryEval binaryEval = (BinaryEval) expr;
+      if (isSingleVar(binaryEval.getLeftExpr())) {
+        return expr;
+      }
+
+      EvalNode left = binaryEval.getLeftExpr();
+      EvalNode lTerm = null;
+      EvalNode rTerm = null;
+
+      if (EvalType.isArithmeticOperator(left.getType())) { // we can ensure that left is binary.
+
+        // If the left-left term is a variable, the left-right term is transposed.
+        if (EvalTreeUtil.containColumnRef(((BinaryEval)left).getLeftExpr(), target)) {
+          PartialBinaryExpr tmpTerm = splitRightTerm((BinaryEval) left);
+          tmpTerm.type = inverseOperator(tmpTerm.type);
+          tmpTerm.setLeftExpr(((BinaryEval)expr).getRightExpr());
+          lTerm = ((BinaryEval)left).getLeftExpr();
+          rTerm = new BinaryEval(tmpTerm);
+        } else {
+          // Otherwise, the left-right term is transposed into the left-left term.
+          PartialBinaryExpr tmpTerm = splitLeftTerm((BinaryEval) left);
+          tmpTerm.type = inverseOperator(tmpTerm.type);
+          tmpTerm.setLeftExpr(((BinaryEval)expr).getRightExpr());
+          lTerm = ((BinaryEval)left).getRightExpr();
+          rTerm = new BinaryEval(tmpTerm);
+        }
+      }
+
+      return _transpose(new BinaryEval(expr.getType(), lTerm, rTerm), target);
+    } else {
+      return _expr;
+    }
+  }
+  
+  /**
+   * Inverse a given operator (+, -, *, /)
+   * 
+   * @param type
+   * @return inversed operator type
+   */
+  public static EvalType inverseOperator(EvalType type) {
+    switch (type) {
+    case PLUS:
+      return EvalType.MINUS;
+    case MINUS:
+      return EvalType.PLUS;
+    case MULTIPLY:
+      return EvalType.DIVIDE;
+    case DIVIDE:
+      return EvalType.MULTIPLY;
+    default : throw new AlgebraicException("ERROR: cannot inverse the operator: " 
+      + type);
+    }
+  }
+  
+  /**
+   * Examine if a given expr is a variable.
+   * 
+   * @param node
+   * @return true if a given expr is a variable.
+   */
+  private static boolean isSingleVar(EvalNode node) {
+    if (node.getType() == EvalType.FIELD) {
+      return true;
+    } else {
+      return false;
+    }
+  }
+
+  private static class AlgebraicOptimizer extends SimpleEvalNodeVisitor<Object> {
+
+    @Override
+    public EvalNode visitBinaryEval(Object context, Stack<EvalNode> stack, BinaryEval binaryEval) {
+      stack.push(binaryEval);
+      EvalNode lhs = visit(context, binaryEval.getLeftExpr(), stack);
+      EvalNode rhs = visit(context, binaryEval.getRightExpr(), stack);
+      stack.pop();
+
+      if (!binaryEval.getLeftExpr().equals(lhs)) {
+        binaryEval.setLeftExpr(lhs);
+      }
+      if (!binaryEval.getRightExpr().equals(rhs)) {
+        binaryEval.setRightExpr(rhs);
+      }
+
+      if (lhs.getType() == EvalType.CONST && rhs.getType() == EvalType.CONST) {
+        return new ConstEval(binaryEval.eval(null, null));
+      }
+
+      return binaryEval;
+    }
+
+    @Override
+    public EvalNode visitUnaryEval(Object context, Stack<EvalNode> stack, UnaryEval unaryEval) {
+      stack.push(unaryEval);
+      EvalNode child = visit(context, unaryEval.getChild(), stack);
+      stack.pop();
+
+      if (child.getType() == EvalType.CONST) {
+        return new ConstEval(unaryEval.eval(null, null));
+      }
+
+      return unaryEval;
+    }
+
+    @Override
+    public EvalNode visitFuncCall(Object context, FunctionEval evalNode, Stack<EvalNode> stack) {
+      boolean constantOfAllDescendents = true;
+
+      if ("sleep".equals(evalNode.funcDesc.getFunctionName())) {
+        constantOfAllDescendents = false;
+      } else {
+        if (evalNode.getArgs() != null) {
+          for (EvalNode arg : evalNode.getArgs()) {
+            arg = visit(context, arg, stack);
+            constantOfAllDescendents &= (arg.getType() == EvalType.CONST);
+          }
+        }
+      }
+
+      if (constantOfAllDescendents && evalNode.getType() == EvalType.FUNCTION) {
+        return new ConstEval(evalNode.eval(null, null));
+      } else {
+        return evalNode;
+      }
+    }
+  }
+
+  private final static AlgebraicOptimizer algebraicOptimizer = new AlgebraicOptimizer();
+  
+  /**
+   * Simplify the given expr. That is, all subexprs consisting of only constants
+   * are calculated immediately.
+   * 
+   * @param expr to be simplified
+   * @return the simplified expr
+   */
+  public static EvalNode eliminateConstantExprs(EvalNode expr) {
+    return algebraicOptimizer.visit(null, expr, new Stack<EvalNode>());
+  }
+  
+  /** 
+   * @param expr to be evaluated if the expr includes one variable
+   * @return true if expr has only one field
+   */
+  public static boolean containSingleVar(EvalNode expr) {
+    Map<EvalType, Integer> counter = EvalTreeUtil.getExprCounters(expr);
+    
+    int sum = 0;
+    for (Integer cnt : counter.values()) {      
+      sum += cnt;
+    }
+    
+    if (sum == 1 && counter.get(EvalType.FIELD) == 1) {
+      return true;
+    } else {
+      return false;
+    }
+  }
+  
+  /**
+   * Split the left term and transform it into the right deep expression.
+   * 
+   * @param binary - notice the left term of this expr will be eliminated
+   * after done.
+   * @return the separated expression changed into the right deep expression.  
+   * For example, the expr 'x * y' is transformed into '* x'.  
+   *
+   */
+  public static PartialBinaryExpr splitLeftTerm(BinaryEval binary) {
+    
+    if (!(EvalType.isArithmeticOperator(binary.getType()))) {
+      throw new AlgebraicException("Invalid algebraic operation: " + binary);
+    }
+    
+    if (binary.getLeftExpr() instanceof BinaryEval) {
+      return splitLeftTerm((BinaryEval) binary.getLeftExpr());
+    }
+    
+    PartialBinaryExpr splitted = 
+        new PartialBinaryExpr(binary.getType(), null, binary.getLeftExpr());
+    binary.setLeftExpr(null);
+    return splitted;
+  }
+  
+  /**
+   * Split the left term and transform it into the right deep expression.
+   * 
+   * @param binary - to be splited
+   * @return the separated expression changed into the right deep expression.
+   * For example, the expr 'x * y' is transformed into '* y'. 
+   *
+   * @throws CloneNotSupportedException
+   */
+  public static PartialBinaryExpr splitRightTerm(BinaryEval binary) {
+    
+    if (!(EvalType.isArithmeticOperator(binary.getType()))) {
+      throw new AlgebraicException("Invalid algebraic operation: " + binary);
+    }
+    
+    if (binary.getRightExpr() instanceof BinaryEval) {
+      return splitRightTerm((BinaryEval) binary.getRightExpr());
+    }
+    
+    PartialBinaryExpr splitted = 
+        new PartialBinaryExpr(binary.getType(), null, binary.getRightExpr());
+    binary.setRightExpr(null);
+    return splitted;
+  }
+  
+  /**
+   * Commutate two terms which are added, subtracted and multiplied.
+   * 
+   * @param inputExpr
+   * @return
+   */
+  public static BinaryEval commutate(BinaryEval inputExpr) {
+    BinaryEval rewritten;
+    switch (inputExpr.getType()) {
+    case AND:
+    case OR:
+    case EQUAL:
+    case PLUS:
+    case MINUS:
+    case MULTIPLY: // these types can be commutated w/o any change
+      rewritten = EvalTreeFactory.create(inputExpr.getType(),
+          inputExpr.getRightExpr(), inputExpr.getLeftExpr());
+      break;
+      
+    case GTH:
+      rewritten = EvalTreeFactory.create(EvalType.LTH,
+          inputExpr.getRightExpr(), inputExpr.getLeftExpr());
+      break;
+    case GEQ:
+      rewritten = EvalTreeFactory.create(EvalType.LEQ,
+          inputExpr.getRightExpr(), inputExpr.getLeftExpr());
+      break;
+    case LTH:
+      rewritten = EvalTreeFactory.create(EvalType.GTH,
+          inputExpr.getRightExpr(), inputExpr.getLeftExpr());
+      break;
+    case LEQ:
+      rewritten = EvalTreeFactory.create(EvalType.GEQ,
+          inputExpr.getRightExpr(), inputExpr.getLeftExpr());
+      break;
+      
+    default :
+      throw new AlgebraicException("Cannot commutate the expr: " + inputExpr);
+    }
+    
+    return rewritten;
+  }
+
+  public static boolean isIndexableOperator(EvalNode expr) {
+    return expr.getType() == EvalType.EQUAL ||
+        expr.getType() == EvalType.LEQ ||
+        expr.getType() == EvalType.LTH ||
+        expr.getType() == EvalType.GEQ ||
+        expr.getType() == EvalType.GTH ||
+        expr.getType() == EvalType.BETWEEN ||
+        expr.getType() == EvalType.IN ||
+        (expr.getType() == EvalType.LIKE && !((LikePredicateEval)expr).isLeadingWildCard());
+  }
+
+  /**
+   * Convert a list of conjunctive normal forms into a singleton expression.
+   *
+   * @param cnfExprs
+   * @return The EvalNode object that merges all CNF-formed expressions.
+   */
+  public static EvalNode createSingletonExprFromCNF(EvalNode... cnfExprs) {
+    if (cnfExprs.length == 1) {
+      return cnfExprs[0];
+    }
+
+    return createSingletonExprFromCNFRecursive(cnfExprs, 0);
+  }
+
+  private static EvalNode createSingletonExprFromCNFRecursive(EvalNode[] evalNode, int idx) {
+    if (idx == evalNode.length - 2) {
+      return new BinaryEval(EvalType.AND, evalNode[idx], evalNode[idx + 1]);
+    } else {
+      return new BinaryEval(EvalType.AND, evalNode[idx], createSingletonExprFromCNFRecursive(evalNode, idx + 1));
+    }
+  }
+
+  /**
+   * Transforms a expression to an array of conjunctive normal formed expressions.
+   *
+   * @param expr The expression to be transformed to an array of CNF-formed expressions.
+   * @return An array of CNF-formed expressions
+   */
+  public static EvalNode [] toConjunctiveNormalFormArray(EvalNode expr) {
+    List<EvalNode> list = new ArrayList<EvalNode>();
+    toConjunctiveNormalFormArrayRecursive(expr, list);
+    return list.toArray(new EvalNode[list.size()]);
+  }
+
+  private static void toConjunctiveNormalFormArrayRecursive(EvalNode node, List<EvalNode> found) {
+    if (node.getType() == EvalType.AND) {
+      toConjunctiveNormalFormArrayRecursive(((BinaryEval)node).getLeftExpr(), found);
+      toConjunctiveNormalFormArrayRecursive(((BinaryEval)node).getRightExpr(), found);
+    } else {
+      found.add(node);
+    }
+  }
+
+  /**
+   * Convert a list of conjunctive normal forms into a singleton expression.
+   *
+   * @param cnfExprs
+   * @return The EvalNode object that merges all CNF-formed expressions.
+   */
+  public static EvalNode createSingletonExprFromDNF(EvalNode... cnfExprs) {
+    if (cnfExprs.length == 1) {
+      return cnfExprs[0];
+    }
+
+    return createSingletonExprFromDNFRecursive(cnfExprs, 0);
+  }
+
+  private static EvalNode createSingletonExprFromDNFRecursive(EvalNode[] evalNode, int idx) {
+    if (idx == evalNode.length - 2) {
+      return new BinaryEval(EvalType.OR, evalNode[idx], evalNode[idx + 1]);
+    } else {
+      return new BinaryEval(EvalType.OR, evalNode[idx], createSingletonExprFromDNFRecursive(evalNode, idx + 1));
+    }
+  }
+
+  /**
+   * Transforms a expression to an array of disjunctive normal formed expressions.
+   *
+   * @param exprs The expressions to be transformed to an array of CNF-formed expressions.
+   * @return An array of CNF-formed expressions
+   */
+  public static EvalNode [] toDisjunctiveNormalFormArray(EvalNode...exprs) {
+    List<EvalNode> list = new ArrayList<EvalNode>();
+    for (EvalNode expr : exprs) {
+      toDisjunctiveNormalFormArrayRecursive(expr, list);
+    }
+    return list.toArray(new EvalNode[list.size()]);
+  }
+
+  private static void toDisjunctiveNormalFormArrayRecursive(EvalNode node, List<EvalNode> found) {
+    if (node.getType() == EvalType.OR) {
+      toDisjunctiveNormalFormArrayRecursive(((BinaryEval)node).getLeftExpr(), found);
+      toDisjunctiveNormalFormArrayRecursive(((BinaryEval)node).getRightExpr(), found);
+    } else {
+      found.add(node);
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BasicEvalNodeVisitor.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BasicEvalNodeVisitor.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BasicEvalNodeVisitor.java
new file mode 100644
index 0000000..81b0f8e
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BasicEvalNodeVisitor.java
@@ -0,0 +1,345 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import org.apache.tajo.exception.UnsupportedException;
+
+import java.util.Stack;
+
+public class BasicEvalNodeVisitor<CONTEXT, RESULT> implements EvalNodeVisitor2<CONTEXT, RESULT> {
+
+  @Override
+  public RESULT visitChild(CONTEXT context, EvalNode evalNode, Stack<EvalNode> stack) {
+    RESULT result;
+    switch (evalNode.getType()) {
+      // Column and Value reference expressions
+      case CONST:
+        result = visitConst(context, (ConstEval) evalNode, stack);
+        break;
+      case ROW_CONSTANT:
+        result = visitRowConstant(context, (RowConstantEval) evalNode, stack);
+        break;
+      case FIELD:
+        result = visitField(context, stack, (FieldEval) evalNode);
+        break;
+
+      // Arithmetic expression
+      case PLUS:
+        result = visitPlus(context, (BinaryEval) evalNode, stack);
+        break;
+      case MINUS:
+        result = visitMinus(context, (BinaryEval) evalNode, stack);
+        break;
+      case MULTIPLY:
+        result = visitMultiply(context, (BinaryEval) evalNode, stack);
+        break;
+      case DIVIDE:
+        result = visitDivide(context, (BinaryEval) evalNode, stack);
+        break;
+      case MODULAR:
+        result = visitModular(context, (BinaryEval) evalNode, stack);
+        break;
+
+      // Logical Predicates
+      case AND:
+        result = visitAnd(context, (BinaryEval) evalNode, stack);
+        break;
+      case OR:
+        result = visitOr(context, (BinaryEval) evalNode, stack);
+        break;
+      case NOT:
+        result = visitNot(context, (NotEval) evalNode, stack);
+        break;
+
+      // Comparison Predicates
+      case EQUAL:
+        result = visitEqual(context, (BinaryEval) evalNode, stack);
+        break;
+      case NOT_EQUAL:
+        result = visitNotEqual(context, (BinaryEval) evalNode, stack);
+        break;
+      case LTH:
+        result = visitLessThan(context, (BinaryEval) evalNode, stack);
+        break;
+      case LEQ:
+        result = visitLessThanOrEqual(context, (BinaryEval) evalNode, stack);
+        break;
+      case GTH:
+        result = visitGreaterThan(context, (BinaryEval) evalNode, stack);
+        break;
+      case GEQ:
+        result = visitGreaterThanOrEqual(context, (BinaryEval) evalNode, stack);
+        break;
+
+      // SQL standard predicates
+      case IS_NULL:
+        result = visitIsNull(context, (IsNullEval) evalNode, stack);
+        break;
+      case BETWEEN:
+        result = visitBetween(context, (BetweenPredicateEval) evalNode, stack);
+        break;
+      case CASE:
+        result = visitCaseWhen(context, (CaseWhenEval) evalNode, stack);
+        break;
+      case IF_THEN:
+        result = visitIfThen(context, (CaseWhenEval.IfThenEval) evalNode, stack);
+        break;
+      case IN:
+        result = visitInPredicate(context, (InEval) evalNode, stack);
+        break;
+
+      // String operators and Pattern match predicates
+      case LIKE:
+        result = visitLike(context, (LikePredicateEval) evalNode, stack);
+        break;
+      case SIMILAR_TO:
+        result = visitSimilarTo(context, (SimilarToPredicateEval) evalNode, stack);
+        break;
+      case REGEX:
+        result = visitRegex(context, (RegexPredicateEval) evalNode, stack);
+        break;
+      case CONCATENATE:
+        result = visitConcatenate(context, (BinaryEval) evalNode, stack);
+        break;
+
+      // Functions
+      case FUNCTION:
+        result = visitFuncCall(context, (GeneralFunctionEval) evalNode, stack);
+        break;
+      case AGG_FUNCTION:
+        result = visitAggrFuncCall(context, (AggregationFunctionCallEval) evalNode, stack);
+        break;
+      case WINDOW_FUNCTION:
+        result = visitWindowFunc(context, (WindowFunctionEval) evalNode, stack);
+      break;
+
+      case SIGNED:
+        result = visitSigned(context, (SignedEval) evalNode, stack);
+        break;
+      case CAST:
+        result = visitCast(context, (CastEval) evalNode, stack);
+        break;
+
+      default:
+        throw new UnsupportedException("Unknown EvalType: " + evalNode);
+    }
+
+    return result;
+  }
+
+  private RESULT visitDefaultUnaryEval(CONTEXT context, UnaryEval unaryEval, Stack<EvalNode> stack) {
+    stack.push(unaryEval);
+    RESULT result = visitChild(context, unaryEval.getChild(), stack);
+    stack.pop();
+    return result;
+  }
+
+  private RESULT visitDefaultBinaryEval(CONTEXT context, BinaryEval binaryEval, Stack<EvalNode> stack) {
+    stack.push(binaryEval);
+    RESULT result = visitChild(context, binaryEval.getLeftExpr(), stack);
+    visitChild(context, binaryEval.getRightExpr(), stack);
+    stack.pop();
+    return result;
+  }
+
+  private RESULT visitDefaultFunctionEval(CONTEXT context, FunctionEval functionEval, Stack<EvalNode> stack) {
+    RESULT result = null;
+    stack.push(functionEval);
+    if (functionEval.getArgs() != null) {
+      for (EvalNode arg : functionEval.getArgs()) {
+        result = visitChild(context, arg, stack);
+      }
+    }
+    stack.pop();
+    return result;
+  }
+
+  @Override
+  public RESULT visitConst(CONTEXT context, ConstEval evalNode, Stack<EvalNode> stack) {
+    return null;
+  }
+
+  @Override
+  public RESULT visitRowConstant(CONTEXT context, RowConstantEval evalNode, Stack<EvalNode> stack) {
+    return null;
+  }
+
+  @Override
+  public RESULT visitField(CONTEXT context, Stack<EvalNode> stack, FieldEval evalNode) {
+    return null;
+  }
+
+  @Override
+  public RESULT visitPlus(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitMinus(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitMultiply(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitDivide(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitModular(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitAnd(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitOr(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitNot(CONTEXT context, NotEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultUnaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitEqual(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitNotEqual(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitLessThan(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitLessThanOrEqual(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitGreaterThan(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitGreaterThanOrEqual(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitIsNull(CONTEXT context, IsNullEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultUnaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitBetween(CONTEXT context, BetweenPredicateEval evalNode, Stack<EvalNode> stack) {
+    stack.push(evalNode);
+    RESULT result = visitChild(context, evalNode.getPredicand(), stack);
+    visitChild(context, evalNode.getBegin(), stack);
+    visitChild(context, evalNode.getEnd(), stack);
+    return result;
+  }
+
+  @Override
+  public RESULT visitCaseWhen(CONTEXT context, CaseWhenEval evalNode, Stack<EvalNode> stack) {
+    RESULT result = null;
+    stack.push(evalNode);
+    for (CaseWhenEval.IfThenEval ifThenEval : evalNode.getIfThenEvals()) {
+      result = visitIfThen(context, ifThenEval, stack);
+    }
+    if (evalNode.hasElse()) {
+      result = visitChild(context, evalNode.getElse(), stack);
+    }
+    stack.pop();
+    return result;
+  }
+
+  @Override
+  public RESULT visitIfThen(CONTEXT context, CaseWhenEval.IfThenEval evalNode, Stack<EvalNode> stack) {
+    RESULT result;
+    stack.push(evalNode);
+    result = visitChild(context, evalNode.getCondition(), stack);
+    visitChild(context, evalNode.getResult(), stack);
+    stack.pop();
+    return result;
+  }
+
+  @Override
+  public RESULT visitInPredicate(CONTEXT context, InEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitLike(CONTEXT context, LikePredicateEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitSimilarTo(CONTEXT context, SimilarToPredicateEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitRegex(CONTEXT context, RegexPredicateEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitConcatenate(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultBinaryEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitFuncCall(CONTEXT context, GeneralFunctionEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultFunctionEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitAggrFuncCall(CONTEXT context, AggregationFunctionCallEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultFunctionEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitWindowFunc(CONTEXT context, WindowFunctionEval evalNode, Stack<EvalNode> stack) {
+    return visitDefaultFunctionEval(context, evalNode, stack);
+  }
+
+  @Override
+  public RESULT visitSigned(CONTEXT context, SignedEval signedEval, Stack<EvalNode> stack) {
+    return visitDefaultUnaryEval(context, signedEval, stack);
+  }
+
+  @Override
+  public RESULT visitCast(CONTEXT context, CastEval castEval, Stack<EvalNode> stack) {
+    return visitDefaultUnaryEval(context, castEval, stack);
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BetweenPredicateEval.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BetweenPredicateEval.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BetweenPredicateEval.java
new file mode 100644
index 0000000..84197e8
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BetweenPredicateEval.java
@@ -0,0 +1,268 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import com.google.gson.annotations.Expose;
+import org.apache.tajo.catalog.CatalogUtil;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.common.TajoDataTypes;
+import org.apache.tajo.datum.Datum;
+import org.apache.tajo.datum.DatumFactory;
+import org.apache.tajo.datum.NullDatum;
+import org.apache.tajo.storage.Tuple;
+
+public class BetweenPredicateEval extends EvalNode implements Cloneable {
+  private static final TajoDataTypes.DataType RES_TYPE = CatalogUtil.newSimpleDataType(TajoDataTypes.Type.BOOLEAN);
+  @Expose private boolean not;
+  @Expose private boolean symmetric;
+  @Expose private EvalNode predicand;
+  @Expose private EvalNode begin;
+  @Expose private EvalNode end;
+
+  private Checker checker;
+
+  public BetweenPredicateEval(boolean not, boolean symmetric, EvalNode predicand, EvalNode begin, EvalNode end) {
+    super(EvalType.BETWEEN);
+    this.not = not;
+    this.symmetric = symmetric;
+    this.predicand = predicand;
+    this.begin = begin;
+    this.end = end;
+  }
+
+  public boolean isNot() {
+    return not;
+  }
+
+  public boolean isSymmetric() {
+    return symmetric;
+  }
+
+  public void setPredicand(EvalNode predicand) {
+    this.predicand = predicand;
+  }
+
+  public EvalNode getPredicand() {
+    return predicand;
+  }
+
+  public void setBegin(EvalNode begin) {
+    this.begin = begin;
+  }
+
+  public EvalNode getBegin() {
+    return begin;
+  }
+
+  public void setEnd(EvalNode end) {
+    this.end = end;
+  }
+
+  public EvalNode getEnd() {
+    return end;
+  }
+
+  private static interface Checker {
+    Datum eval(Schema schema, Tuple param);
+  }
+
+  private static class ConstantChecker implements Checker {
+    EvalNode predicand;
+    Datum begin;
+    Datum end;
+    private boolean not;
+
+    private ConstantChecker(boolean not, EvalNode predicand, Datum begin, Datum end) {
+      this.predicand = predicand;
+      this.not = not;
+      if (begin.compareTo(end) > 0) {
+        this.begin = end;
+        this.end = begin;
+      } else {
+        this.begin = begin;
+        this.end = end;
+      }
+    }
+
+    @Override
+    public Datum eval(Schema schema, Tuple param) {
+      Datum predicandValue = predicand.eval(schema, param);
+
+      if (!predicandValue.isNull()) {
+        return DatumFactory.createBool(not ^ (predicandValue.greaterThanEqual(begin).asBool()
+                && predicandValue.lessThanEqual(end).asBool()));
+      } else {
+        return NullDatum.get();
+      }
+    }
+  }
+
+  private static class AsymmetricChecker implements Checker {
+    EvalNode predicand;
+    EvalNode begin;
+    EvalNode end;
+    private boolean not;
+
+    private AsymmetricChecker(boolean not, EvalNode predicand, EvalNode begin, EvalNode end) {
+      this.not = not;
+      this.predicand = predicand;
+      this.begin = begin;
+      this.end = end;
+    }
+
+    @Override
+    public Datum eval(Schema schema, Tuple param) {
+      Datum predicandValue = predicand.eval(schema, param);
+      Datum beginValue = begin.eval(schema, param);
+      Datum endValue = end.eval(schema, param);
+
+      if (!(predicandValue.isNull() || beginValue.isNull() || endValue.isNull())) {
+        return
+            DatumFactory.createBool(not ^ (predicandValue.greaterThanEqual(beginValue).asBool()
+                && predicandValue.lessThanEqual(endValue).asBool()));
+      } else {
+        return NullDatum.get();
+      }
+    }
+  }
+
+  private static class SymmetricChecker implements Checker {
+    boolean not;
+    EvalNode predicand;
+    EvalNode begin;
+    EvalNode end;
+
+    SymmetricChecker(boolean not, EvalNode predicand, EvalNode begin, EvalNode end) {
+      this.not = not;
+      this.predicand = predicand;
+      this.begin = begin;
+      this.end = end;
+    }
+
+    @Override
+    public Datum eval(Schema schema, Tuple param) {
+      Datum predicandValue = predicand.eval(schema, param);
+      Datum beginValue = begin.eval(schema, param);
+      Datum endValue = end.eval(schema, param);
+
+      if (!(predicandValue.isNull()|| beginValue.isNull() || endValue.isNull())) {
+        return DatumFactory.createBool( not ^
+            (predicandValue.greaterThanEqual(beginValue).asBool() && predicandValue.lessThanEqual(endValue).asBool()) ||
+            (predicandValue.lessThanEqual(beginValue).asBool() && predicandValue.greaterThanEqual(endValue).asBool())
+        );
+      } else {
+        return NullDatum.get();
+      }
+    }
+  }
+
+  @Override
+  public TajoDataTypes.DataType getValueType() {
+    return RES_TYPE;
+  }
+
+  @Override
+  public int childNum() {
+    return 3;
+  }
+
+  @Override
+  public EvalNode getChild(int idx) {
+    if (idx == 0) {
+      return predicand;
+    } else if (idx == 1) {
+      return begin;
+    } else if (idx == 2) {
+      return end;
+    } else {
+      throw new ArrayIndexOutOfBoundsException(idx);
+    }
+  }
+
+  @Override
+  public String getName() {
+    return "between";
+  }
+
+  @Override
+  public String toString() {
+    return predicand + " BETWEEN " + (symmetric ? "SYMMETRIC" : "ASYMMETRIC") + " " + begin + " AND " + end;
+  }
+
+  @Override
+  public Datum eval(Schema schema, Tuple tuple) {
+    if (checker == null) {
+      if (begin.getType() == EvalType.CONST && end.getType() == EvalType.CONST) {
+        Datum beginValue = ((ConstEval)begin).getValue();
+        Datum endValue = ((ConstEval)end).getValue();
+
+        if (symmetric || beginValue.compareTo(endValue) <= 0) {
+          checker = new ConstantChecker(not, predicand, beginValue, endValue);
+        } else {
+          checker = new AsymmetricChecker(not, predicand, begin, end);
+        }
+      } else {
+        if (symmetric) {
+          checker = new SymmetricChecker(not, predicand, begin, end);
+        } else {
+          checker = new AsymmetricChecker(not, predicand, begin, end);
+        }
+      }
+    }
+
+    return checker.eval(schema, tuple);
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (obj instanceof BetweenPredicateEval) {
+      BetweenPredicateEval another = (BetweenPredicateEval) obj;
+      return not == another.not && symmetric == another.symmetric && predicand.equals(another.predicand) &&
+          begin.equals(another.begin) && end.equals(another.end);
+    }
+    return false;
+  }
+
+  @Deprecated
+  public void preOrder(EvalNodeVisitor visitor) {
+    visitor.visit(this);
+    predicand.preOrder(visitor);
+    begin.preOrder(visitor);
+    end.preOrder(visitor);
+  }
+
+  @Deprecated
+  public void postOrder(EvalNodeVisitor visitor) {
+    predicand.postOrder(visitor);
+    begin.postOrder(visitor);
+    end.postOrder(visitor);
+    visitor.visit(this);
+  }
+
+  @Override
+  public Object clone() throws CloneNotSupportedException {
+    BetweenPredicateEval newBetween = (BetweenPredicateEval) super.clone();
+    newBetween.not = not;
+    newBetween.symmetric = symmetric;
+    newBetween.predicand = predicand;
+    newBetween.begin = begin;
+    newBetween.end = end;
+    return newBetween;
+  }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BinaryEval.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BinaryEval.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BinaryEval.java
new file mode 100644
index 0000000..faeefcd
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/BinaryEval.java
@@ -0,0 +1,217 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import com.google.common.base.Objects;
+import com.google.gson.annotations.Expose;
+import org.apache.tajo.catalog.CatalogUtil;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.common.TajoDataTypes.DataType;
+import org.apache.tajo.datum.Datum;
+import org.apache.tajo.datum.DatumFactory;
+import org.apache.tajo.datum.NullDatum;
+import org.apache.tajo.DataTypeUtil;
+import org.apache.tajo.exception.InvalidOperationException;
+import org.apache.tajo.storage.Tuple;
+
+import static org.apache.tajo.common.TajoDataTypes.Type;
+
+public class BinaryEval extends EvalNode implements Cloneable {
+  @Expose protected EvalNode leftExpr;
+  @Expose protected EvalNode rightExpr;
+  @Expose protected DataType returnType;
+
+  protected BinaryEval(EvalType type) {
+    super(type);
+  }
+
+  public BinaryEval(EvalType type, EvalNode left, EvalNode right) {
+    super(type);
+    this.leftExpr = left;
+    this.rightExpr = right;
+
+    if(
+        type == EvalType.AND ||
+            type == EvalType.OR ||
+            type == EvalType.EQUAL ||
+            type == EvalType.NOT_EQUAL ||
+            type == EvalType.LTH ||
+            type == EvalType.GTH ||
+            type == EvalType.LEQ ||
+            type == EvalType.GEQ ) {
+      this.returnType = CatalogUtil.newSimpleDataType(Type.BOOLEAN);
+    } else if (
+        type == EvalType.PLUS ||
+            type == EvalType.MINUS ||
+            type == EvalType.MULTIPLY ||
+            type == EvalType.DIVIDE ||
+            type == EvalType.MODULAR ) {
+      this.returnType = DataTypeUtil.determineType(left.getValueType(), right.getValueType());
+
+    } else if (type == EvalType.CONCATENATE) {
+      this.returnType = CatalogUtil.newSimpleDataType(Type.TEXT);
+    }
+  }
+
+  public BinaryEval(PartialBinaryExpr expr) {
+    this(expr.type, expr.leftExpr, expr.rightExpr);
+  }
+
+  public void setLeftExpr(EvalNode expr) {
+    this.leftExpr = expr;
+  }
+
+  public <T extends EvalNode> T getLeftExpr() {
+    return (T) this.leftExpr;
+  }
+
+  public void setRightExpr(EvalNode expr) {
+    this.rightExpr = expr;
+  }
+
+  public <T extends EvalNode> T getRightExpr() {
+    return (T) this.rightExpr;
+  }
+
+  @Override
+  public int childNum() {
+    return 2;
+  }
+
+  @Override
+  public EvalNode getChild(int id) {
+    if (id == 0) {
+      return this.leftExpr;
+    } else if (id == 1) {
+      return this.rightExpr;
+    } else {
+      throw new ArrayIndexOutOfBoundsException("only 0 or 1 is available, but (" + id + ") is not available)");
+    }
+  }
+
+  public void setChild(int id, EvalNode child) {
+    if (id == 0) {
+      this.leftExpr = child;
+    } else if (id == 1) {
+      this.rightExpr = child;
+    } else {
+      throw new ArrayIndexOutOfBoundsException("only 0 or 1 is available, but (" + id + ") is not available)");
+    }
+  }
+
+  @Override
+  public Datum eval(Schema schema, Tuple tuple) {
+    Datum lhs = leftExpr.eval(schema, tuple);
+    Datum rhs = rightExpr.eval(schema, tuple);
+
+    switch(type) {
+    case AND:
+      return lhs.and(rhs);
+    case OR:
+      return lhs.or(rhs);
+
+    case EQUAL:
+      return lhs.equalsTo(rhs);
+    case NOT_EQUAL:
+      return lhs.notEqualsTo(rhs);
+    case LTH:
+      return lhs.lessThan(rhs);
+    case LEQ:
+      return lhs.lessThanEqual(rhs);
+    case GTH:
+      return lhs.greaterThan(rhs);
+    case GEQ:
+      return lhs.greaterThanEqual(rhs);
+
+    case PLUS:
+      return lhs.plus(rhs);
+    case MINUS:
+      return lhs.minus(rhs);
+    case MULTIPLY:
+      return lhs.multiply(rhs);
+    case DIVIDE:
+      return lhs.divide(rhs);
+    case MODULAR:
+      return lhs.modular(rhs);
+
+    case CONCATENATE:
+      if (lhs.type() == Type.NULL_TYPE || rhs.type() == Type.NULL_TYPE) {
+        return NullDatum.get();
+      }
+      return DatumFactory.createText(lhs.asChars() + rhs.asChars());
+    default:
+      throw new InvalidOperationException("Unknown binary operation: " + type);
+    }
+  }
+
+  @Override
+	public String getName() {
+		return type.name();
+	}
+
+	@Override
+	public DataType getValueType() {
+	  return returnType;
+	}
+
+  @Deprecated
+  public void preOrder(EvalNodeVisitor visitor) {
+    visitor.visit(this);
+    leftExpr.preOrder(visitor);
+    rightExpr.preOrder(visitor);
+  }
+
+  @Deprecated
+  public void postOrder(EvalNodeVisitor visitor) {
+    leftExpr.postOrder(visitor);
+    rightExpr.postOrder(visitor);
+    visitor.visit(this);
+  }
+
+	public String toString() {
+		return leftExpr +" " + type.getOperatorName() + " "+ rightExpr;
+	}
+
+  @Override
+  public boolean equals(Object obj) {
+    if (obj instanceof BinaryEval) {
+      BinaryEval other = (BinaryEval) obj;
+
+      boolean b1 = this.type == other.type;
+      boolean b2 = leftExpr.equals(other.leftExpr);
+      boolean b3 = rightExpr.equals(other.rightExpr);
+      return b1 && b2 && b3;
+    }
+    return false;
+  }
+
+  public int hashCode() {
+    return Objects.hashCode(this.type, leftExpr, rightExpr);
+  }
+
+  @Override
+  public Object clone() throws CloneNotSupportedException {
+    BinaryEval node = (BinaryEval) super.clone();
+    node.type = type;
+    node.leftExpr = leftExpr != null ? (EvalNode) leftExpr.clone() : null;
+    node.rightExpr = rightExpr != null ? (EvalNode) rightExpr.clone() : null;
+
+    return node;
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/CaseWhenEval.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/CaseWhenEval.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/CaseWhenEval.java
new file mode 100644
index 0000000..4321d02
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/CaseWhenEval.java
@@ -0,0 +1,284 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import com.google.common.collect.Lists;
+import com.google.gson.annotations.Expose;
+import org.apache.tajo.catalog.CatalogUtil;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.common.TajoDataTypes;
+import org.apache.tajo.common.TajoDataTypes.DataType;
+import org.apache.tajo.common.TajoDataTypes.Type;
+import org.apache.tajo.datum.Datum;
+import org.apache.tajo.datum.NullDatum;
+import org.apache.tajo.json.GsonObject;
+import org.apache.tajo.plan.serder.PlanGsonHelper;
+import org.apache.tajo.storage.Tuple;
+import org.apache.tajo.util.TUtil;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class CaseWhenEval extends EvalNode implements GsonObject {
+  @Expose private List<IfThenEval> whens = Lists.newArrayList();
+  @Expose private EvalNode elseResult;
+
+  public CaseWhenEval() {
+    super(EvalType.CASE);
+  }
+
+  public void addIfCond(IfThenEval ifCond) {
+    whens.add(ifCond);
+  }
+
+  public void addIfCond(EvalNode condition, EvalNode result) {
+    whens.add(new IfThenEval(condition, result));
+  }
+
+  public List<IfThenEval> getIfThenEvals() {
+    return whens;
+  }
+
+  public boolean hasElse() {
+    return this.elseResult != null;
+  }
+
+  public EvalNode getElse() {
+    return elseResult;
+  }
+
+  public void setElseResult(EvalNode elseResult) {
+    this.elseResult = elseResult;
+  }
+
+  @Override
+  public DataType getValueType() {
+    // Find not null type
+    for (IfThenEval eachWhen: whens) {
+      if (eachWhen.getResult().getValueType().getType() != Type.NULL_TYPE) {
+        return eachWhen.getResult().getValueType();
+      }
+    }
+
+    if (elseResult != null) { // without else clause
+      return elseResult.getValueType();
+    }
+
+    return NullDatum.getDataType();
+  }
+
+  @Override
+  public int childNum() {
+    return whens.size() + (elseResult != null ? 1 : 0);
+  }
+
+  @Override
+  public EvalNode getChild(int idx) {
+    if (idx < whens.size()) {
+      return whens.get(idx);
+    } else if (idx == whens.size()) {
+      return elseResult;
+    } else {
+      throw new ArrayIndexOutOfBoundsException(idx);
+    }
+  }
+
+  @Override
+  public String getName() {
+    return "?";
+  }
+
+  public Datum eval(Schema schema, Tuple tuple) {
+    for (int i = 0; i < whens.size(); i++) {
+      if (whens.get(i).checkIfCondition(schema, tuple)) {
+        return whens.get(i).eval(schema, tuple);
+      }
+    }
+
+    if (elseResult != null) { // without else clause
+      return elseResult.eval(schema, tuple);
+    }
+
+    return NullDatum.get();
+  }
+
+  @Override
+  public String toString() {
+    StringBuilder sb = new StringBuilder("CASE ");
+    for (IfThenEval when : whens) {
+     sb.append(when).append(" ");
+    }
+
+    sb.append("ELSE ").append(elseResult).append(" END");
+
+    return sb.toString();
+  }
+
+  @Override
+  public void preOrder(EvalNodeVisitor visitor) {
+    visitor.visit(this);
+    for (IfThenEval when : whens) {
+      when.preOrder(visitor);
+    }
+    if (elseResult != null) { // without else clause
+      elseResult.preOrder(visitor);
+    }
+  }
+
+  @Override
+  public void postOrder(EvalNodeVisitor visitor) {
+    for (IfThenEval when : whens) {
+      when.postOrder(visitor);
+    }
+    if (elseResult != null) { // without else clause
+      elseResult.postOrder(visitor);
+    }
+    visitor.visit(this);
+  }
+
+  @Override
+  public Object clone() throws CloneNotSupportedException {
+    CaseWhenEval caseWhenEval = (CaseWhenEval) super.clone();
+    caseWhenEval.whens = new ArrayList<IfThenEval>();
+    for (IfThenEval ifThenEval : whens) {
+      caseWhenEval.whens.add((IfThenEval) ifThenEval.clone());
+    }
+    caseWhenEval.elseResult = elseResult;
+    return caseWhenEval;
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (obj instanceof CaseWhenEval) {
+      CaseWhenEval other = (CaseWhenEval) obj;
+
+      for (int i = 0; i < other.whens.size(); i++) {
+        if (!whens.get(i).equals(other.whens.get(i))) {
+          return false;
+        }
+      }
+      return TUtil.checkEquals(elseResult, other.elseResult);
+    } else {
+      return false;
+    }
+  }
+
+  public static class IfThenEval extends EvalNode implements GsonObject {
+    @Expose private EvalNode condition;
+    @Expose private EvalNode result;
+
+    public IfThenEval(EvalNode condition, EvalNode result) {
+      super(EvalType.IF_THEN);
+      this.condition = condition;
+      this.result = result;
+    }
+
+    @Override
+    public DataType getValueType() {
+      return CatalogUtil.newSimpleDataType(TajoDataTypes.Type.BOOLEAN);
+    }
+
+    @Override
+    public int childNum() {
+      return 2;
+    }
+
+    @Override
+    public EvalNode getChild(int idx) {
+      if (idx == 0) {
+        return condition;
+      } else if (idx == 1) {
+        return result;
+      } else {
+        throw new ArrayIndexOutOfBoundsException(idx);
+      }
+    }
+
+    @Override
+    public String getName() {
+      return "when?";
+    }
+
+    public boolean checkIfCondition(Schema schema, Tuple tuple) {
+      return condition.eval(schema, tuple).isTrue();
+    }
+
+    public Datum eval(Schema schema, Tuple tuple) {
+      return result.eval(schema, tuple);
+    }
+
+    public void setCondition(EvalNode condition) {
+      this.condition = condition;
+    }
+
+    public EvalNode getCondition() {
+      return this.condition;
+    }
+
+    public void setResult(EvalNode result) {
+      this.result = result;
+    }
+
+    public EvalNode getResult() {
+      return this.result;
+    }
+
+    @Override
+    public boolean equals(Object object) {
+      if (object instanceof IfThenEval) {
+        IfThenEval other = (IfThenEval) object;
+        return condition.equals(other.condition) && result.equals(other.result);
+      } else {
+        return false;
+      }
+    }
+
+    @Override
+    public String toString() {
+      return "WHEN " + condition + " THEN " + result;
+    }
+
+    @Override
+    public String toJson() {
+      return PlanGsonHelper.toJson(IfThenEval.this, IfThenEval.class);
+    }
+
+    @Override
+    public void preOrder(EvalNodeVisitor visitor) {
+      visitor.visit(this);
+      condition.preOrder(visitor);
+      result.preOrder(visitor);
+    }
+
+    @Override
+    public void postOrder(EvalNodeVisitor visitor) {
+      condition.postOrder(visitor);
+      result.postOrder(visitor);
+      visitor.visit(this);
+    }
+
+    @Override
+    public Object clone() throws CloneNotSupportedException {
+      IfThenEval ifThenEval = (IfThenEval) super.clone();
+      ifThenEval.condition = (EvalNode)condition.clone();
+      ifThenEval.result = (EvalNode)result.clone();
+      return ifThenEval;
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/CastEval.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/CastEval.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/CastEval.java
new file mode 100644
index 0000000..d625a11
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/CastEval.java
@@ -0,0 +1,74 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import com.google.gson.annotations.Expose;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.datum.Datum;
+import org.apache.tajo.datum.DatumFactory;
+import org.apache.tajo.storage.Tuple;
+
+import static org.apache.tajo.common.TajoDataTypes.DataType;
+
+public class CastEval extends UnaryEval {
+  @Expose private DataType target;
+
+  public CastEval(EvalNode operand, DataType target) {
+    super(EvalType.CAST, operand);
+    this.target = target;
+  }
+
+  public EvalNode getOperand() {
+    return child;
+  }
+
+  @Override
+  public DataType getValueType() {
+    return target;
+  }
+
+  @Override
+  public String getName() {
+    return target.getType().name();
+  }
+
+  public Datum eval(Schema schema, Tuple tuple) {
+    Datum operandDatum = child.eval(schema, tuple);
+    if (operandDatum.isNull()) {
+      return operandDatum;
+    }
+
+    return DatumFactory.cast(operandDatum, target);
+  }
+
+  public String toString() {
+    return "CAST (" + child + " AS " + target.getType() + ")";
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    boolean valid = obj != null && obj instanceof CastEval;
+    if (valid) {
+      CastEval another = (CastEval) obj;
+      return child.equals(another.child) && target.equals(another.target);
+    } else {
+      return false;
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/ConstEval.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/ConstEval.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/ConstEval.java
new file mode 100644
index 0000000..b9f48a9
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/ConstEval.java
@@ -0,0 +1,109 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import com.google.common.base.Objects;
+import com.google.gson.annotations.Expose;
+import org.apache.tajo.catalog.CatalogUtil;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.common.TajoDataTypes.DataType;
+import org.apache.tajo.datum.Datum;
+import org.apache.tajo.storage.Tuple;
+
+public class ConstEval extends EvalNode implements Comparable<ConstEval>, Cloneable {
+	@Expose Datum datum = null;
+	
+	public ConstEval(Datum datum) {
+		super(EvalType.CONST);
+		this.datum = datum;
+	}
+
+  public Datum getValue() {
+    return this.datum;
+  }
+	
+	public String toString() {
+		return datum.toString();
+	}
+
+  @Override
+  public Datum eval(Schema schema, Tuple tuple) {
+    return datum;
+  }
+
+  @Override
+	public DataType getValueType() {
+    return CatalogUtil.newSimpleDataType(datum.type());
+	}
+
+  @Override
+  public int childNum() {
+    return 0;
+  }
+
+  @Override
+  public EvalNode getChild(int idx) {
+    return null;
+  }
+
+  @Override
+	public String getName() {
+		return this.datum.toString();
+	}
+	
+  @Override
+  public boolean equals(Object obj) {
+    if (obj instanceof ConstEval) {
+      ConstEval other = (ConstEval) obj;
+
+      if (this.type == other.type && this.datum.equals(other.datum)) {
+        return true;
+      }
+    }
+    return false;
+  }
+  
+  @Override
+  public int hashCode() {
+    return Objects.hashCode(type, datum.type(), datum);
+  }
+  
+  @Override
+  public Object clone() throws CloneNotSupportedException {
+    ConstEval eval = (ConstEval) super.clone();
+    eval.datum = datum;
+    
+    return eval;
+  }
+
+  @Override
+  public int compareTo(ConstEval other) {    
+    return datum.compareTo(other.datum);
+  }
+  
+  @Override
+  public void preOrder(EvalNodeVisitor visitor) {
+    visitor.visit(this);
+  }
+  
+  @Override
+  public void postOrder(EvalNodeVisitor visitor) {
+    visitor.visit(this);
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNode.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNode.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNode.java
new file mode 100644
index 0000000..638383a
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNode.java
@@ -0,0 +1,74 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import com.google.gson.annotations.Expose;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.common.TajoDataTypes.DataType;
+import org.apache.tajo.datum.Datum;
+import org.apache.tajo.json.GsonObject;
+import org.apache.tajo.plan.serder.PlanGsonHelper;
+import org.apache.tajo.storage.Tuple;
+
+/**
+ * An annotated expression which includes actual data domains.
+ * It is also used for evaluation.
+ */
+public abstract class EvalNode implements Cloneable, GsonObject {
+	@Expose protected EvalType type;
+
+  public EvalNode() {
+  }
+
+	public EvalNode(EvalType type) {
+		this.type = type;
+	}
+	
+	public EvalType getType() {
+		return this.type;
+	}
+	
+	public abstract DataType getValueType();
+
+  public abstract int childNum();
+
+  public abstract EvalNode getChild(int idx);
+	
+	public abstract String getName();
+
+  @Override
+	public String toJson() {
+    return PlanGsonHelper.toJson(this, EvalNode.class);
+	}
+	
+	public abstract <T extends Datum> T eval(Schema schema, Tuple tuple);
+
+  @Deprecated
+  public abstract  void preOrder(EvalNodeVisitor visitor);
+
+  @Deprecated
+  public abstract void postOrder(EvalNodeVisitor visitor);
+
+  @Override
+  public Object clone() throws CloneNotSupportedException {
+    EvalNode evalNode = (EvalNode) super.clone();
+    evalNode.type = type;
+    return evalNode;
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNodeVisitor.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNodeVisitor.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNodeVisitor.java
new file mode 100644
index 0000000..372786b
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNodeVisitor.java
@@ -0,0 +1,24 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+@Deprecated
+public interface EvalNodeVisitor {
+  public void visit(EvalNode node);
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNodeVisitor2.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNodeVisitor2.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNodeVisitor2.java
new file mode 100644
index 0000000..bae193a
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalNodeVisitor2.java
@@ -0,0 +1,72 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import java.util.Stack;
+
+public interface EvalNodeVisitor2<CONTEXT, RESULT> {
+  RESULT visitChild(CONTEXT context, EvalNode evalNode, Stack<EvalNode> stack);
+
+  // Column and Value reference expressions
+  RESULT visitConst(CONTEXT context, ConstEval evalNode, Stack<EvalNode> stack);
+  RESULT visitRowConstant(CONTEXT context, RowConstantEval evalNode, Stack<EvalNode> stack);
+  RESULT visitField(CONTEXT context, Stack<EvalNode> stack, FieldEval evalNode);
+
+  // Arithmetic expression
+  RESULT visitPlus(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitMinus(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitMultiply(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitDivide(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitModular(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+
+  // Logical Predicates
+  RESULT visitAnd(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitOr(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitNot(CONTEXT context, NotEval evalNode, Stack<EvalNode> stack);
+
+  // Comparison Predicates
+  RESULT visitEqual(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitNotEqual(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitLessThan(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitLessThanOrEqual(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitGreaterThan(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+  RESULT visitGreaterThanOrEqual(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+
+  // Other Predicates
+  RESULT visitIsNull(CONTEXT context, IsNullEval evalNode, Stack<EvalNode> stack);
+  RESULT visitBetween(CONTEXT context, BetweenPredicateEval evalNode, Stack<EvalNode> stack);
+  RESULT visitCaseWhen(CONTEXT context, CaseWhenEval evalNode, Stack<EvalNode> stack);
+  RESULT visitIfThen(CONTEXT context, CaseWhenEval.IfThenEval evalNode, Stack<EvalNode> stack);
+  RESULT visitInPredicate(CONTEXT context, InEval evalNode, Stack<EvalNode> stack);
+
+  // String operator and Pattern matching predicates
+  RESULT visitLike(CONTEXT context, LikePredicateEval evalNode, Stack<EvalNode> stack);
+  RESULT visitSimilarTo(CONTEXT context, SimilarToPredicateEval evalNode, Stack<EvalNode> stack);
+  RESULT visitRegex(CONTEXT context, RegexPredicateEval evalNode, Stack<EvalNode> stack);
+  RESULT visitConcatenate(CONTEXT context, BinaryEval evalNode, Stack<EvalNode> stack);
+
+  // Functions
+  RESULT visitFuncCall(CONTEXT context, GeneralFunctionEval evalNode, Stack<EvalNode> stack);
+  RESULT visitAggrFuncCall(CONTEXT context, AggregationFunctionCallEval evalNode, Stack<EvalNode> stack);
+  RESULT visitWindowFunc(CONTEXT context, WindowFunctionEval evalNode, Stack<EvalNode> stack);
+
+  RESULT visitSigned(CONTEXT context, SignedEval signedEval, Stack<EvalNode> stack);
+
+  RESULT visitCast(CONTEXT context, CastEval signedEval, Stack<EvalNode> stack);
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeFactory.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeFactory.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeFactory.java
new file mode 100644
index 0000000..c708f4c
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeFactory.java
@@ -0,0 +1,32 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import org.apache.tajo.datum.Datum;
+
+public class EvalTreeFactory {
+	public static ConstEval newConst(Datum datum) {
+		return new ConstEval(datum);
+	}
+	
+	public static BinaryEval create(EvalType type, EvalNode e1,
+	    EvalNode e2) {
+		return new BinaryEval(type, e1, e2);
+	}
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/b143f991/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java
new file mode 100644
index 0000000..1f3f2ab
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java
@@ -0,0 +1,520 @@
+/**
+ * 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.tajo.plan.expr;
+
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+import org.apache.tajo.algebra.ColumnReferenceExpr;
+import org.apache.tajo.algebra.NamedExpr;
+import org.apache.tajo.algebra.OpType;
+import org.apache.tajo.annotation.Nullable;
+import org.apache.tajo.catalog.CatalogUtil;
+import org.apache.tajo.catalog.Column;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.common.TajoDataTypes.DataType;
+import org.apache.tajo.datum.Datum;
+import org.apache.tajo.exception.InternalException;
+import org.apache.tajo.plan.util.ExprFinder;
+import org.apache.tajo.plan.LogicalPlan;
+import org.apache.tajo.plan.Target;
+import org.apache.tajo.util.TUtil;
+
+import java.util.*;
+
+public class EvalTreeUtil {
+
+  public static void changeColumnRef(EvalNode node, String oldName, String newName) {
+    node.postOrder(new ChangeColumnRefVisitor(oldName, newName));
+  }
+
+  public static int replace(EvalNode expr, EvalNode targetExpr, EvalNode tobeReplaced) {
+    EvalReplaceVisitor replacer = new EvalReplaceVisitor(targetExpr, tobeReplaced);
+    ReplaceContext context = new ReplaceContext();
+    replacer.visitChild(context, expr, new Stack<EvalNode>());
+    return context.countOfReplaces;
+  }
+
+  private static class ReplaceContext {
+    int countOfReplaces = 0;
+  }
+
+  public static class EvalReplaceVisitor extends BasicEvalNodeVisitor<ReplaceContext, EvalNode> {
+    private EvalNode target;
+    private EvalNode tobeReplaced;
+
+    public EvalReplaceVisitor(EvalNode target, EvalNode tobeReplaced) {
+      this.target = target;
+      this.tobeReplaced = tobeReplaced;
+    }
+
+    @Override
+    public EvalNode visitChild(ReplaceContext context, EvalNode evalNode, Stack<EvalNode> stack) {
+      super.visitChild(context, evalNode, stack);
+
+      if (evalNode.equals(target)) {
+        context.countOfReplaces++;
+
+        EvalNode parent = stack.peek();
+
+        if (parent instanceof BetweenPredicateEval) {
+          BetweenPredicateEval between = (BetweenPredicateEval) parent;
+          if (between.getPredicand().equals(evalNode)) {
+            between.setPredicand(tobeReplaced);
+          }
+          if (between.getBegin().equals(evalNode)) {
+            between.setBegin(tobeReplaced);
+          }
+          if (between.getEnd().equals(evalNode)) {
+            between.setEnd(tobeReplaced);
+          }
+
+        } else if (parent instanceof CaseWhenEval) {
+          CaseWhenEval caseWhen = (CaseWhenEval) parent;
+
+          // Here, we need to only consider only 'Else'
+          // because IfElseEval is handled in the below condition.
+          if (caseWhen.hasElse() && caseWhen.getElse().equals(evalNode)) {
+            caseWhen.setElseResult(tobeReplaced);
+          }
+        } else if (parent instanceof CaseWhenEval.IfThenEval) {
+          CaseWhenEval.IfThenEval ifThen = (CaseWhenEval.IfThenEval) parent;
+          if (ifThen.getCondition().equals(evalNode)) {
+            ifThen.setCondition(tobeReplaced);
+          }
+          if (ifThen.getResult().equals(evalNode)) {
+            ifThen.setResult(tobeReplaced);
+          }
+       } else if (parent instanceof FunctionEval) {
+          FunctionEval functionEval = (FunctionEval) parent;
+          EvalNode [] arguments = functionEval.getArgs();
+          for (int i = 0; i < arguments.length; i++) {
+            if (arguments[i].equals(evalNode)) {
+              arguments[i] = tobeReplaced;
+            }
+          }
+          functionEval.setArgs(arguments);
+
+        } else if (parent instanceof UnaryEval) {
+          if (((UnaryEval)parent).getChild().equals(evalNode)) {
+            ((UnaryEval)parent).setChild(tobeReplaced);
+          }
+        } else if (parent instanceof BinaryEval) {
+          BinaryEval binary = (BinaryEval) parent;
+          if (binary.getLeftExpr() != null && binary.getLeftExpr().equals(evalNode)) {
+            binary.setLeftExpr(tobeReplaced);
+          }
+          if (binary.getRightExpr() != null && binary.getRightExpr().equals(evalNode)) {
+            binary.setRightExpr(tobeReplaced);
+          }
+        }
+      }
+
+      return evalNode;
+    }
+  }
+
+  /**
+   * It finds unique columns from a EvalNode.
+   */
+  public static LinkedHashSet<Column> findUniqueColumns(EvalNode node) {
+    UniqueColumnFinder finder = new UniqueColumnFinder();
+    node.postOrder(finder);
+    return finder.getColumnRefs();
+  }
+  
+  public static List<Column> findAllColumnRefs(EvalNode node) {
+    AllColumnRefFinder finder = new AllColumnRefFinder();
+    node.postOrder(finder);
+    return finder.getColumnRefs();
+  }
+  
+  public static Schema getSchemaByTargets(Schema inputSchema, Target[] targets)
+      throws InternalException {
+    Schema schema = new Schema();
+    for (Target target : targets) {
+      schema.addColumn(
+          target.hasAlias() ? target.getAlias() : target.getEvalTree().getName(),
+          getDomainByExpr(inputSchema, target.getEvalTree()));
+    }
+    
+    return schema;
+  }
+
+  public static String columnsToStr(Collection<Column> columns) {
+    StringBuilder sb = new StringBuilder();
+    String prefix = "";
+    for (Column column: columns) {
+      sb.append(prefix).append(column.getQualifiedName());
+      prefix = ",";
+    }
+
+    return sb.toString();
+  }
+  
+  public static DataType getDomainByExpr(Schema inputSchema, EvalNode expr)
+      throws InternalException {
+    switch (expr.getType()) {
+    case AND:      
+    case OR:
+    case EQUAL:
+    case NOT_EQUAL:
+    case LTH:
+    case LEQ:
+    case GTH:
+    case GEQ:
+    case PLUS:
+    case MINUS:
+    case MULTIPLY:
+    case DIVIDE:
+    case CONST:
+    case FUNCTION:
+        return expr.getValueType();
+
+    case FIELD:
+      FieldEval fieldEval = (FieldEval) expr;
+      return inputSchema.getColumn(fieldEval.getName()).getDataType();
+
+      
+    default:
+      throw new InternalException("Unknown expr type: " 
+          + expr.getType().toString());
+    }
+  }
+
+  /**
+   * Return all exprs to refer columns corresponding to the target.
+   *
+   * @param expr
+   * @param target to be found
+   * @return a list of exprs
+   */
+  public static Collection<EvalNode> getContainExpr(EvalNode expr, Column target) {
+    Set<EvalNode> exprSet = Sets.newHashSet();
+    getContainExpr(expr, target, exprSet);
+    return exprSet;
+  }
+  
+  /**
+   * Return the counter to count the number of expression types individually.
+   *  
+   * @param expr
+   * @return
+   */
+  public static Map<EvalType, Integer> getExprCounters(EvalNode expr) {
+    VariableCounter counter = new VariableCounter();
+    expr.postOrder(counter);
+    return counter.getCounter();
+  }
+  
+  private static void getContainExpr(EvalNode expr, Column target, Set<EvalNode> exprSet) {
+    switch (expr.getType()) {
+    case EQUAL:
+    case LTH:
+    case LEQ:
+    case GTH:
+    case GEQ:
+    case NOT_EQUAL:
+      if (containColumnRef(expr, target)) {          
+        exprSet.add(expr);
+      }
+    }    
+  }
+  
+  /**
+   * Examine if the expr contains the column reference corresponding 
+   * to the target column
+   */
+  public static boolean containColumnRef(EvalNode expr, Column target) {
+    Set<Column> exprSet = findUniqueColumns(expr);
+    return exprSet.contains(target);
+  }
+
+  /**
+   * If a given expression is join condition, it returns TRUE. Otherwise, it returns FALSE.
+   *
+   * If three conditions are satisfied, we can recognize the expression as a equi join condition.
+   * <ol>
+   *   <li>An expression is an equal comparison expression.</li>
+   *   <li>Both terms in an expression are column references.</li>
+   *   <li>Both column references point come from different tables</li>
+   * </ol>
+   *
+   * For theta join condition, we will use "an expression is a predicate including column references which come
+   * from different two tables" instead of the first rule.
+   *
+   * @param expr EvalNode to be evaluated
+   * @param includeThetaJoin If true, it will return equi as well as non-equi join conditions.
+   *                         Otherwise, it only returns equi-join conditions.
+   * @return True if it is join condition.
+   */
+  public static boolean isJoinQual(EvalNode expr, boolean includeThetaJoin) {
+    return isJoinQual(null, expr, includeThetaJoin);
+  }
+
+  /**
+   * If a given expression is join condition, it returns TRUE. Otherwise, it returns FALSE.
+   *
+   * If three conditions are satisfied, we can recognize the expression as a equi join condition.
+   * <ol>
+   *   <li>An expression is an equal comparison expression.</li>
+   *   <li>Both terms in an expression are column references.</li>
+   *   <li>Both column references point come from different tables</li>
+   * </ol>
+   *
+   * For theta join condition, we will use "an expression is a predicate including column references which come
+   * from different two tables" instead of the first rule.
+   *
+   * @param block if block is not null, it tracks the lineage of aliased name derived from complex expressions.
+   * @param expr EvalNode to be evaluated
+   * @param includeThetaJoin If true, it will return equi as well as non-equi join conditions.
+   *                         Otherwise, it only returns equi-join conditions.
+   * @return True if it is join condition.
+   */
+  public static boolean isJoinQual(@Nullable LogicalPlan.QueryBlock block, EvalNode expr, boolean includeThetaJoin) {
+
+    if (expr instanceof BinaryEval) {
+      boolean joinComparator;
+      if (includeThetaJoin) {
+        joinComparator = EvalType.isComparisonOperator(expr.getType());
+      } else {
+        joinComparator = expr.getType() == EvalType.EQUAL;
+      }
+
+      BinaryEval binaryEval = (BinaryEval) expr;
+      boolean isBothTermFields = isSingleColumn(binaryEval.getLeftExpr()) && isSingleColumn(binaryEval.getRightExpr());
+
+      Set<Column> leftColumns = EvalTreeUtil.findUniqueColumns(binaryEval.getLeftExpr());
+      Set<Column> rightColumns = EvalTreeUtil.findUniqueColumns(binaryEval.getRightExpr());
+
+      boolean ensureColumnsOfDifferentTables = false;
+
+      if (leftColumns.size() == 1 && rightColumns.size() == 1) { // ensure there is only one column of each table
+        Column leftColumn = leftColumns.iterator().next();
+        Column rightColumn = rightColumns.iterator().next();
+
+        String leftQualifier = CatalogUtil.extractQualifier(leftColumn.getQualifiedName());
+        String rightQualifier = CatalogUtil.extractQualifier(rightColumn.getQualifiedName());
+
+        // if block is given, it will track an original expression of each term in order to decide whether
+        // this expression is a join condition, or not.
+        if (block != null) {
+          boolean leftQualified = CatalogUtil.isFQColumnName(leftColumn.getQualifiedName());
+          boolean rightQualified = CatalogUtil.isFQColumnName(rightColumn.getQualifiedName());
+
+          if (!leftQualified) { // if left one is aliased name
+
+            // getting original expression of left term
+            NamedExpr rawExpr = block.getNamedExprsManager().getNamedExpr(leftColumn.getQualifiedName());
+            Set<ColumnReferenceExpr> foundColumns = ExprFinder.finds(rawExpr.getExpr(), OpType.Column);
+
+            // ensure there is only one column of an original expression
+            if (foundColumns.size() == 1) {
+              leftQualifier = CatalogUtil.extractQualifier(foundColumns.iterator().next().getCanonicalName());
+            }
+          }
+          if (!rightQualified) { // if right one is aliased name
+
+            // getting original expression of right term
+            NamedExpr rawExpr = block.getNamedExprsManager().getNamedExpr(rightColumn.getQualifiedName());
+            Set<ColumnReferenceExpr> foundColumns = ExprFinder.finds(rawExpr.getExpr(), OpType.Column);
+
+            // ensure there is only one column of an original expression
+            if (foundColumns.size() == 1) {
+              rightQualifier = CatalogUtil.extractQualifier(foundColumns.iterator().next().getCanonicalName());
+            }
+          }
+        }
+
+        // if columns of both term is different to each other, it will be true.
+        ensureColumnsOfDifferentTables = !leftQualifier.equals(rightQualifier);
+      }
+
+      return joinComparator && isBothTermFields && ensureColumnsOfDifferentTables;
+    } else {
+      return false;
+    }
+  }
+
+  static boolean isSingleColumn(EvalNode evalNode) {
+    return EvalTreeUtil.findUniqueColumns(evalNode).size() == 1;
+  }
+  
+  public static class ChangeColumnRefVisitor implements EvalNodeVisitor {    
+    private final String findColumn;
+    private final String toBeChanged;
+    
+    public ChangeColumnRefVisitor(String oldName, String newName) {
+      this.findColumn = oldName;
+      this.toBeChanged = newName;
+    }
+    
+    @Override
+    public void visit(EvalNode node) {
+      if (node.type == EvalType.FIELD) {
+        FieldEval field = (FieldEval) node;
+        if (field.getColumnName().equals(findColumn)
+            || field.getName().equals(findColumn)) {
+          field.replaceColumnRef(toBeChanged);
+        }
+      }
+    }    
+  }
+  
+  public static class AllColumnRefFinder implements EvalNodeVisitor {
+    private List<Column> colList = new ArrayList<Column>();
+    private FieldEval field = null;
+    
+    @Override
+    public void visit(EvalNode node) {
+      if (node.getType() == EvalType.FIELD) {
+        field = (FieldEval) node;
+        colList.add(field.getColumnRef());
+      } 
+    }
+    
+    public List<Column> getColumnRefs() {
+      return this.colList;
+    }
+  }
+  
+  public static class UniqueColumnFinder implements EvalNodeVisitor {
+    private LinkedHashSet<Column> columnSet = Sets.newLinkedHashSet();
+    private FieldEval field = null;
+    
+    @Override
+    public void visit(EvalNode node) {
+      if (node.getType() == EvalType.FIELD) {
+        field = (FieldEval) node;
+        columnSet.add(field.getColumnRef());
+      }
+    }
+    
+    public LinkedHashSet<Column> getColumnRefs() {
+      return this.columnSet;
+    }
+  }
+  
+  public static class VariableCounter implements EvalNodeVisitor {
+    private final Map<EvalType, Integer> counter;
+    
+    public VariableCounter() {
+      counter = Maps.newHashMap();
+      counter.put(EvalType.FUNCTION, 0);
+      counter.put(EvalType.FIELD, 0);
+    }
+    
+    @Override
+    public void visit(EvalNode node) {
+      if (counter.containsKey(node.getType())) {
+        int val = counter.get(node.getType());
+        val++;
+        counter.put(node.getType(), val);
+      }
+    }
+    
+    public Map<EvalType, Integer> getCounter() {
+      return counter;
+    }
+  }
+
+  public static Set<AggregationFunctionCallEval> findDistinctAggFunction(EvalNode expr) {
+    AllAggFunctionFinder finder = new AllAggFunctionFinder();
+    expr.postOrder(finder);
+    return finder.getAggregationFunction();
+  }
+
+  public static class AllAggFunctionFinder implements EvalNodeVisitor {
+    private Set<AggregationFunctionCallEval> aggFucntions = Sets.newHashSet();
+    private AggregationFunctionCallEval field = null;
+
+    @Override
+    public void visit(EvalNode node) {
+      if (node.getType() == EvalType.AGG_FUNCTION) {
+        field = (AggregationFunctionCallEval) node;
+        aggFucntions.add(field);
+      }
+    }
+
+    public Set<AggregationFunctionCallEval> getAggregationFunction() {
+      return this.aggFucntions;
+    }
+  }
+
+  public static <T extends EvalNode> Collection<T> findEvalsByType(EvalNode evalNode, EvalType type) {
+    EvalFinder finder = new EvalFinder(type);
+    finder.visitChild(null, evalNode, new Stack<EvalNode>());
+    return (Collection<T>) finder.evalNodes;
+  }
+
+  public static <T extends EvalNode> Collection<T> findOuterJoinSensitiveEvals(EvalNode evalNode) {
+    OuterJoinSensitiveEvalFinder finder = new OuterJoinSensitiveEvalFinder();
+    finder.visitChild(null, evalNode, new Stack<EvalNode>());
+    return (Collection<T>) finder.evalNodes;
+  }
+
+  public static class EvalFinder extends BasicEvalNodeVisitor<Object, Object> {
+    private EvalType targetType;
+    List<EvalNode> evalNodes = TUtil.newList();
+
+    public EvalFinder(EvalType targetType) {
+      this.targetType = targetType;
+    }
+
+    @Override
+    public Object visitChild(Object context, EvalNode evalNode, Stack<EvalNode> stack) {
+      super.visitChild(context, evalNode, stack);
+
+      if (evalNode.type == targetType) {
+        evalNodes.add(evalNode);
+      }
+
+      return evalNode;
+    }
+  }
+
+  public static class OuterJoinSensitiveEvalFinder extends BasicEvalNodeVisitor<Object, Object> {
+    private List<EvalNode> evalNodes = TUtil.newList();
+
+    @Override
+    public Object visitChild(Object context, EvalNode evalNode, Stack<EvalNode> stack) {
+      super.visitChild(context, evalNode, stack);
+
+      if (evalNode.type == EvalType.CASE) {
+        evalNodes.add(evalNode);
+      } else if (evalNode.type == EvalType.FUNCTION) {
+        FunctionEval functionEval = (FunctionEval)evalNode;
+        if ("coalesce".equals(functionEval.getName())) {
+          evalNodes.add(evalNode);
+        }
+      } else if (evalNode.type == EvalType.IS_NULL) {
+        evalNodes.add(evalNode);
+      }
+
+      return evalNode;
+    }
+  }
+
+  public static boolean checkIfCanBeConstant(EvalNode evalNode) {
+    return findUniqueColumns(evalNode).size() == 0 && findDistinctAggFunction(evalNode).size() == 0;
+  }
+
+  public static Datum evaluateImmediately(EvalNode evalNode) {
+    return evalNode.eval(null, null);
+  }
+}
\ No newline at end of file


Mime
View raw message