You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tajo.apache.org by ji...@apache.org on 2014/10/26 06:46:07 UTC
[08/33] TAJO-1125: Separate logical plan and optimizer into a maven
module.
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