Return-Path: X-Original-To: apmail-tajo-commits-archive@minotaur.apache.org Delivered-To: apmail-tajo-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id A3EAD17DBB for ; Sat, 25 Oct 2014 18:17:51 +0000 (UTC) Received: (qmail 91908 invoked by uid 500); 25 Oct 2014 18:17:51 -0000 Delivered-To: apmail-tajo-commits-archive@tajo.apache.org Received: (qmail 91805 invoked by uid 500); 25 Oct 2014 18:17:51 -0000 Mailing-List: contact commits-help@tajo.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@tajo.apache.org Delivered-To: mailing list commits@tajo.apache.org Received: (qmail 91703 invoked by uid 99); 25 Oct 2014 18:17:51 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 25 Oct 2014 18:17:51 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id F1DE78949F7; Sat, 25 Oct 2014 18:17:50 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: hyunsik@apache.org To: commits@tajo.apache.org Date: Sat, 25 Oct 2014 18:17:57 -0000 Message-Id: <55ca23bd5f4d4a2d80ed9fa5e9f52c13@git.apache.org> In-Reply-To: References: X-Mailer: ASF-Git Admin Mailer Subject: [08/28] 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 { + + @Override + public EvalNode visitBinaryEval(Object context, Stack 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 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 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()); + } + + /** + * @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 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 list = new ArrayList(); + toConjunctiveNormalFormArrayRecursive(expr, list); + return list.toArray(new EvalNode[list.size()]); + } + + private static void toConjunctiveNormalFormArrayRecursive(EvalNode node, List 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 list = new ArrayList(); + for (EvalNode expr : exprs) { + toDisjunctiveNormalFormArrayRecursive(expr, list); + } + return list.toArray(new EvalNode[list.size()]); + } + + private static void toDisjunctiveNormalFormArrayRecursive(EvalNode node, List 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 implements EvalNodeVisitor2 { + + @Override + public RESULT visitChild(CONTEXT context, EvalNode evalNode, Stack 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 stack) { + stack.push(unaryEval); + RESULT result = visitChild(context, unaryEval.getChild(), stack); + stack.pop(); + return result; + } + + private RESULT visitDefaultBinaryEval(CONTEXT context, BinaryEval binaryEval, Stack 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 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 stack) { + return null; + } + + @Override + public RESULT visitRowConstant(CONTEXT context, RowConstantEval evalNode, Stack stack) { + return null; + } + + @Override + public RESULT visitField(CONTEXT context, Stack stack, FieldEval evalNode) { + return null; + } + + @Override + public RESULT visitPlus(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitMinus(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitMultiply(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitDivide(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitModular(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitAnd(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitOr(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitNot(CONTEXT context, NotEval evalNode, Stack stack) { + return visitDefaultUnaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitEqual(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitNotEqual(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitLessThan(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitLessThanOrEqual(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitGreaterThan(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitGreaterThanOrEqual(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitIsNull(CONTEXT context, IsNullEval evalNode, Stack stack) { + return visitDefaultUnaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitBetween(CONTEXT context, BetweenPredicateEval evalNode, Stack 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 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 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 stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitLike(CONTEXT context, LikePredicateEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitSimilarTo(CONTEXT context, SimilarToPredicateEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitRegex(CONTEXT context, RegexPredicateEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitConcatenate(CONTEXT context, BinaryEval evalNode, Stack stack) { + return visitDefaultBinaryEval(context, evalNode, stack); + } + + @Override + public RESULT visitFuncCall(CONTEXT context, GeneralFunctionEval evalNode, Stack stack) { + return visitDefaultFunctionEval(context, evalNode, stack); + } + + @Override + public RESULT visitAggrFuncCall(CONTEXT context, AggregationFunctionCallEval evalNode, Stack stack) { + return visitDefaultFunctionEval(context, evalNode, stack); + } + + @Override + public RESULT visitWindowFunc(CONTEXT context, WindowFunctionEval evalNode, Stack stack) { + return visitDefaultFunctionEval(context, evalNode, stack); + } + + @Override + public RESULT visitSigned(CONTEXT context, SignedEval signedEval, Stack stack) { + return visitDefaultUnaryEval(context, signedEval, stack); + } + + @Override + public RESULT visitCast(CONTEXT context, CastEval castEval, Stack 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 getLeftExpr() { + return (T) this.leftExpr; + } + + public void setRightExpr(EvalNode expr) { + this.rightExpr = expr; + } + + public 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 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 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(); + 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, 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 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 { + RESULT visitChild(CONTEXT context, EvalNode evalNode, Stack stack); + + // Column and Value reference expressions + RESULT visitConst(CONTEXT context, ConstEval evalNode, Stack stack); + RESULT visitRowConstant(CONTEXT context, RowConstantEval evalNode, Stack stack); + RESULT visitField(CONTEXT context, Stack stack, FieldEval evalNode); + + // Arithmetic expression + RESULT visitPlus(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitMinus(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitMultiply(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitDivide(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitModular(CONTEXT context, BinaryEval evalNode, Stack stack); + + // Logical Predicates + RESULT visitAnd(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitOr(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitNot(CONTEXT context, NotEval evalNode, Stack stack); + + // Comparison Predicates + RESULT visitEqual(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitNotEqual(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitLessThan(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitLessThanOrEqual(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitGreaterThan(CONTEXT context, BinaryEval evalNode, Stack stack); + RESULT visitGreaterThanOrEqual(CONTEXT context, BinaryEval evalNode, Stack stack); + + // Other Predicates + RESULT visitIsNull(CONTEXT context, IsNullEval evalNode, Stack stack); + RESULT visitBetween(CONTEXT context, BetweenPredicateEval evalNode, Stack stack); + RESULT visitCaseWhen(CONTEXT context, CaseWhenEval evalNode, Stack stack); + RESULT visitIfThen(CONTEXT context, CaseWhenEval.IfThenEval evalNode, Stack stack); + RESULT visitInPredicate(CONTEXT context, InEval evalNode, Stack stack); + + // String operator and Pattern matching predicates + RESULT visitLike(CONTEXT context, LikePredicateEval evalNode, Stack stack); + RESULT visitSimilarTo(CONTEXT context, SimilarToPredicateEval evalNode, Stack stack); + RESULT visitRegex(CONTEXT context, RegexPredicateEval evalNode, Stack stack); + RESULT visitConcatenate(CONTEXT context, BinaryEval evalNode, Stack stack); + + // Functions + RESULT visitFuncCall(CONTEXT context, GeneralFunctionEval evalNode, Stack stack); + RESULT visitAggrFuncCall(CONTEXT context, AggregationFunctionCallEval evalNode, Stack stack); + RESULT visitWindowFunc(CONTEXT context, WindowFunctionEval evalNode, Stack stack); + + RESULT visitSigned(CONTEXT context, SignedEval signedEval, Stack stack); + + RESULT visitCast(CONTEXT context, CastEval signedEval, Stack 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()); + return context.countOfReplaces; + } + + private static class ReplaceContext { + int countOfReplaces = 0; + } + + public static class EvalReplaceVisitor extends BasicEvalNodeVisitor { + 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 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 findUniqueColumns(EvalNode node) { + UniqueColumnFinder finder = new UniqueColumnFinder(); + node.postOrder(finder); + return finder.getColumnRefs(); + } + + public static List 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 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 getContainExpr(EvalNode expr, Column target) { + Set 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 getExprCounters(EvalNode expr) { + VariableCounter counter = new VariableCounter(); + expr.postOrder(counter); + return counter.getCounter(); + } + + private static void getContainExpr(EvalNode expr, Column target, Set 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 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. + *
    + *
  1. An expression is an equal comparison expression.
    2. + *
  2. Both terms in an expression are column references.
    3. + *
  3. Both column references point come from different tables
    4. + *
+ * + * 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. + *
    + *
  1. An expression is an equal comparison expression.
    2. + *
  2. Both terms in an expression are column references.
    3. + *
  3. Both column references point come from different tables
    4. + *
+ * + * 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 leftColumns = EvalTreeUtil.findUniqueColumns(binaryEval.getLeftExpr()); + Set 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 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 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 colList = new ArrayList(); + private FieldEval field = null; + + @Override + public void visit(EvalNode node) { + if (node.getType() == EvalType.FIELD) { + field = (FieldEval) node; + colList.add(field.getColumnRef()); + } + } + + public List getColumnRefs() { + return this.colList; + } + } + + public static class UniqueColumnFinder implements EvalNodeVisitor { + private LinkedHashSet 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 getColumnRefs() { + return this.columnSet; + } + } + + public static class VariableCounter implements EvalNodeVisitor { + private final Map 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 getCounter() { + return counter; + } + } + + public static Set findDistinctAggFunction(EvalNode expr) { + AllAggFunctionFinder finder = new AllAggFunctionFinder(); + expr.postOrder(finder); + return finder.getAggregationFunction(); + } + + public static class AllAggFunctionFinder implements EvalNodeVisitor { + private Set 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 getAggregationFunction() { + return this.aggFucntions; + } + } + + public static Collection findEvalsByType(EvalNode evalNode, EvalType type) { + EvalFinder finder = new EvalFinder(type); + finder.visitChild(null, evalNode, new Stack()); + return (Collection) finder.evalNodes; + } + + public static Collection findOuterJoinSensitiveEvals(EvalNode evalNode) { + OuterJoinSensitiveEvalFinder finder = new OuterJoinSensitiveEvalFinder(); + finder.visitChild(null, evalNode, new Stack()); + return (Collection) finder.evalNodes; + } + + public static class EvalFinder extends BasicEvalNodeVisitor { + private EvalType targetType; + List evalNodes = TUtil.newList(); + + public EvalFinder(EvalType targetType) { + this.targetType = targetType; + } + + @Override + public Object visitChild(Object context, EvalNode evalNode, Stack stack) { + super.visitChild(context, evalNode, stack); + + if (evalNode.type == targetType) { + evalNodes.add(evalNode); + } + + return evalNode; + } + } + + public static class OuterJoinSensitiveEvalFinder extends BasicEvalNodeVisitor { + private List evalNodes = TUtil.newList(); + + @Override + public Object visitChild(Object context, EvalNode evalNode, Stack 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