tajo-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hyun...@apache.org
Subject [07/12] TAJO-501: Rewrite the projection part of logical planning.
Date Fri, 17 Jan 2014 09:23:37 GMT
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExprFinder.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExprFinder.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExprFinder.java
new file mode 100644
index 0000000..c97a30a
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExprFinder.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.engine.planner;
+
+import org.apache.tajo.algebra.*;
+
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+
+class ExprFinder extends SimpleAlgebraVisitor<ExprFinder.Context, Object> {
+
+  static class Context {
+    Set<Expr> set = new HashSet<Expr>();
+    OpType targetType;
+
+    Context(OpType type) {
+      this.targetType = type;
+    }
+  }
+
+  public static <T extends Expr> Set<T> finds(Expr expr, OpType type) {
+    Context context = new Context(type);
+    ExprFinder finder = new ExprFinder();
+    Stack<Expr> stack = new Stack<Expr>();
+    stack.push(expr);
+    try {
+      finder.visit(context, new Stack<Expr>(), expr);
+    } catch (PlanningException e) {
+      throw new RuntimeException(e);
+    }
+    stack.pop();
+    return (Set<T>) context.set;
+  }
+
+  public Object visit(Context ctx, Stack<Expr> stack, Expr expr) throws PlanningException {
+    if (expr instanceof UnaryOperator) {
+      preHook(ctx, stack, expr);
+      visitUnaryOperator(ctx, stack, (UnaryOperator) expr);
+      postHook(ctx, stack, expr, null);
+    } else if (expr instanceof BinaryOperator) {
+      preHook(ctx, stack, expr);
+      visitBinaryOperator(ctx, stack, (BinaryOperator) expr);
+      postHook(ctx, stack, expr, null);
+    } else {
+      super.visit(ctx, stack, expr);
+    }
+
+    if (ctx.targetType == expr.getType()) {
+      ctx.set.add(expr);
+    }
+
+    return null;
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExprNormalizer.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExprNormalizer.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExprNormalizer.java
new file mode 100644
index 0000000..ca509c4
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExprNormalizer.java
@@ -0,0 +1,259 @@
+/**
+ * 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.engine.planner;
+
+import org.apache.tajo.algebra.*;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Stack;
+
+/**
+ * ExprNormalizer performs two kinds of works:
+ *
+ * <h3>1. Duplication Removal.</h3>
+ *
+ * For example, assume a simple query as follows:
+ * <pre>
+ *   select price * rate as total_price, ..., order by price * rate
+ * </pre>
+ *
+ * The expression <code>price * rate</code> is duplicated in both select list and order by clause.
+ * Against those cases, ExprNormalizer removes duplicated expressions and replaces one with one reference.
+ * In the case, ExprNormalizer replaces price * rate with total_price reference.
+ *
+ * <h3>2. Dissection of Expression</h3>
+ *
+ * A expression can be a complex expressions, including a mixed of scalar and aggregation expressions.
+ * For example, assume an aggregation query as follows:
+ * <pre>
+ *   select sum(price * rate) * (1 - avg(discount_rate))), ...
+ * </pre>
+ *
+ * In this case, ExprNormalizer dissects the expression 'sum(price * rate) * (1 - avg(discount_rate)))'
+ * into the following expressions:
+ * <ul>
+ *   <li>$1 = price * rage</li>
+ *   <li>$2 = sum($1)</li>
+ *   <li>$3 = avg(discount_rate)</li>
+ *   <li>$4 = $3 * (1 - $3)</li>
+ * </ul>
+ *
+ * It mainly two advantages. Firstly, it makes complex expression evaluations easier across multiple physical executors.
+ * Second, it gives move opportunities to remove duplicated expressions.
+ *
+ * <h3>3. Name Normalization</h3>
+ *
+ * Users can use qualified column names, unqualified column names or aliased column references.
+ *
+ * Consider the following example:
+ *
+ * <pre>
+ *   select rate_a as total_rate, rate_a * 100, table1.rate_a, ... WHERE total_rate * 100
+ * </pre>
+ *
+ * <code>total_rate</code>, <code>rate_a</code>, and <code>table1.rate_a</code> are all the same references. But,
+ * they have different forms. Due to their different forms, duplication removal can be hard.
+ *
+ * In order to solve this problem, ExprNormalizer normalizes all column references as qualified names while it keeps
+ * its points..
+ */
+class ExprNormalizer extends SimpleAlgebraVisitor<ExprNormalizer.ExprNormalizedResult, Object> {
+
+  public static class ExprNormalizedResult {
+    private final LogicalPlan plan;
+    private final LogicalPlan.QueryBlock block;
+
+    Expr baseExpr; // outmost expressions, which can includes one or more references of the results of aggregation
+                   // function.
+    List<NamedExpr> aggExprs = new ArrayList<NamedExpr>(); // aggregation functions
+    List<NamedExpr> scalarExprs = new ArrayList<NamedExpr>(); // scalar expressions which can be referred
+
+    private ExprNormalizedResult(LogicalPlanner.PlanContext context) {
+      this.plan = context.plan;
+      this.block = context.queryBlock;
+    }
+
+    @Override
+    public String toString() {
+      return baseExpr.toString() + ", agg=" + aggExprs.size() + ", scalar=" + scalarExprs.size();
+    }
+  }
+
+  public ExprNormalizedResult normalize(LogicalPlanner.PlanContext context, Expr expr) throws PlanningException {
+    ExprNormalizedResult exprNormalizedResult = new ExprNormalizedResult(context);
+    Stack<Expr> stack = new Stack<Expr>();
+    stack.push(expr);
+    visit(exprNormalizedResult, new Stack<Expr>(), expr);
+    exprNormalizedResult.baseExpr = stack.pop();
+    return exprNormalizedResult;
+  }
+
+  private boolean isAggregationFunction(Expr expr) {
+    return expr.getType() == OpType.GeneralSetFunction || expr.getType() == OpType.CountRowsFunction;
+  }
+
+  @Override
+  public Object visitCaseWhen(ExprNormalizedResult ctx, Stack<Expr> stack, CaseWhenPredicate expr)
+      throws PlanningException {
+    stack.push(expr);
+    for (CaseWhenPredicate.WhenExpr when : expr.getWhens()) {
+      visit(ctx, stack, when.getCondition());
+      visit(ctx, stack, when.getResult());
+
+      if (isAggregationFunction(when.getCondition())) {
+        String referenceName = ctx.block.namedExprsMgr.addExpr(when.getCondition());
+        ctx.aggExprs.add(new NamedExpr(when.getCondition(), referenceName));
+        when.setCondition(new ColumnReferenceExpr(referenceName));
+      }
+
+      if (isAggregationFunction(when.getResult())) {
+        String referenceName = ctx.block.namedExprsMgr.addExpr(when.getResult());
+        ctx.aggExprs.add(new NamedExpr(when.getResult(), referenceName));
+        when.setResult(new ColumnReferenceExpr(referenceName));
+      }
+    }
+
+    if (expr.hasElseResult()) {
+      visit(ctx, stack, expr.getElseResult());
+      if (isAggregationFunction(expr.getElseResult())) {
+        String referenceName = ctx.block.namedExprsMgr.addExpr(expr.getElseResult());
+        ctx.aggExprs.add(new NamedExpr(expr.getElseResult(), referenceName));
+        expr.setElseResult(new ColumnReferenceExpr(referenceName));
+      }
+    }
+    stack.pop();
+    return expr;
+  }
+
+  @Override
+  public Expr visitUnaryOperator(ExprNormalizedResult ctx, Stack<Expr> stack, UnaryOperator expr) throws PlanningException {
+    super.visitUnaryOperator(ctx, stack, expr);
+    if (isAggregationFunction(expr.getChild())) {
+      // Get an anonymous column name and replace the aggregation function by the column name
+      String refName = ctx.block.namedExprsMgr.addExpr(expr.getChild());
+      ctx.aggExprs.add(new NamedExpr(expr.getChild(), refName));
+      expr.setChild(new ColumnReferenceExpr(refName));
+    }
+
+    return expr;
+  }
+
+  @Override
+  public Expr visitBinaryOperator(ExprNormalizedResult ctx, Stack<Expr> stack, BinaryOperator expr) throws PlanningException {
+    super.visitBinaryOperator(ctx, stack, expr);
+
+    ////////////////////////
+    // For Left Term
+    ////////////////////////
+
+    if (isAggregationFunction(expr.getLeft())) {
+      String leftRefName = ctx.block.namedExprsMgr.addExpr(expr.getLeft());
+      ctx.aggExprs.add(new NamedExpr(expr.getLeft(), leftRefName));
+      expr.setLeft(new ColumnReferenceExpr(leftRefName));
+    }
+
+
+    ////////////////////////
+    // For Right Term
+    ////////////////////////
+    if (isAggregationFunction(expr.getRight())) {
+      String rightRefName = ctx.block.namedExprsMgr.addExpr(expr.getRight());
+      ctx.aggExprs.add(new NamedExpr(expr.getRight(), rightRefName));
+      expr.setRight(new ColumnReferenceExpr(rightRefName));
+    }
+
+    return expr;
+  }
+
+  ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+  // Function Section
+  ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+  @Override
+  public Expr visitFunction(ExprNormalizedResult ctx, Stack<Expr> stack, FunctionExpr expr) throws PlanningException {
+    stack.push(expr);
+
+    Expr param;
+    for (int i = 0; i < expr.getParams().length; i++) {
+      param = expr.getParams()[i];
+      visit(ctx, stack, param);
+
+      if (isAggregationFunction(param)) {
+        String referenceName = ctx.plan.newGeneratedFieldName(param);
+        ctx.aggExprs.add(new NamedExpr(param, referenceName));
+        expr.getParams()[i] = new ColumnReferenceExpr(referenceName);
+      }
+    }
+
+    stack.pop();
+
+    return expr;
+  }
+
+  @Override
+  public Expr visitGeneralSetFunction(ExprNormalizedResult ctx, Stack<Expr> stack, GeneralSetFunctionExpr expr)
+      throws PlanningException {
+    stack.push(expr);
+
+    Expr param;
+    for (int i = 0; i < expr.getParams().length; i++) {
+      param = expr.getParams()[i];
+      visit(ctx, stack, param);
+
+      String referenceName = ctx.block.namedExprsMgr.addExpr(param);
+      ctx.scalarExprs.add(new NamedExpr(param, referenceName));
+      expr.getParams()[i] = new ColumnReferenceExpr(referenceName);
+    }
+    stack.pop();
+    return expr;
+  }
+
+  ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+  // Literal Section
+  ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+  @Override
+  public Expr visitCastExpr(ExprNormalizedResult ctx, Stack<Expr> stack, CastExpr expr) throws PlanningException {
+    super.visitCastExpr(ctx, stack, expr);
+    if (expr.getChild().getType() == OpType.GeneralSetFunction
+        || expr.getChild().getType() == OpType.CountRowsFunction) {
+      String referenceName = ctx.block.namedExprsMgr.addExpr(expr.getChild());
+      ctx.aggExprs.add(new NamedExpr(expr.getChild(), referenceName));
+      expr.setChild(new ColumnReferenceExpr(referenceName));
+    }
+    return expr;
+  }
+
+  @Override
+  public Expr visitColumnReference(ExprNormalizedResult ctx, Stack<Expr> stack, ColumnReferenceExpr expr)
+      throws PlanningException {
+    // normalize column references.
+    if (!expr.hasQualifier()) {
+      if (ctx.block.namedExprsMgr.contains(expr.getCanonicalName())) {
+        NamedExpr namedExpr = ctx.block.namedExprsMgr.getNamedExpr(expr.getCanonicalName());
+        return new ColumnReferenceExpr(namedExpr.getAlias());
+      } else {
+        String normalized = ctx.plan.getNormalizedColumnName(ctx.block, expr);
+        expr.setName(normalized);
+      }
+    }
+    return expr;
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/GroupElement.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/GroupElement.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/GroupElement.java
index 3c8ee5c..3fb05c2 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/GroupElement.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/GroupElement.java
@@ -22,29 +22,28 @@ import com.google.gson.Gson;
 import com.google.gson.GsonBuilder;
 import com.google.gson.annotations.Expose;
 import org.apache.tajo.algebra.Aggregation;
-import org.apache.tajo.catalog.Column;
+import org.apache.tajo.engine.eval.EvalNode;
 
 public class GroupElement implements Cloneable {
-  @Expose
-  private Aggregation.GroupType type;
-  @Expose private Column[] columns;
+  @Expose private Aggregation.GroupType type;
+  @Expose private EvalNode [] groupingSets;
 
   @SuppressWarnings("unused")
   public GroupElement() {
     // for gson
   }
 
-  public GroupElement(Aggregation.GroupType type, Column[] columns) {
+  public GroupElement(Aggregation.GroupType type, EvalNode [] groupingSets) {
     this.type = type;
-    this.columns = columns;
+    this.groupingSets = groupingSets;
   }
 
   public Aggregation.GroupType getType() {
     return this.type;
   }
 
-  public Column [] getColumns() {
-    return this.columns;
+  public EvalNode [] getGroupingSets() {
+    return this.groupingSets;
   }
 
   public String toString() {
@@ -56,9 +55,9 @@ public class GroupElement implements Cloneable {
   public Object clone() throws CloneNotSupportedException {
     GroupElement groups = (GroupElement) super.clone();
     groups.type = type;
-    groups.columns = new Column[columns.length];
-    for (int i = 0; i < columns.length; i++) {
-      groups.columns[i++] = (Column) columns[i].clone();
+    groups.groupingSets = new EvalNode [groupingSets.length];
+    for (int i = 0; i < groupingSets.length; i++) {
+      groups.groupingSets[i++] = (EvalNode) groupingSets[i].clone();
     }
     return groups;
   }

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/InsertNode.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/InsertNode.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/InsertNode.java
index 4a3e479..ecba05a 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/InsertNode.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/InsertNode.java
@@ -38,18 +38,19 @@ public class InsertNode extends LogicalNode implements Cloneable {
   @Expose private Options options;
   @Expose private LogicalNode subQuery;
 
-
-  public InsertNode(int pid, TableDesc desc, LogicalNode subQuery) {
+  public InsertNode(int pid) {
     super(pid, NodeType.INSERT);
+  }
+
+  public void setTargetTableDesc(TableDesc desc) {
     this.targetTableDesc = desc;
-    this.subQuery = subQuery;
-    this.setInSchema(subQuery.getOutSchema());
-    this.setOutSchema(subQuery.getOutSchema());
   }
 
-  public InsertNode(int pid, Path location, LogicalNode subQuery) {
-    super(pid, NodeType.INSERT);
-    this.path = location;
+  public void setTargetLocation(Path path) {
+    this.path = path;
+  }
+
+  public void setSubQuery(LogicalNode subQuery) {
     this.subQuery = subQuery;
     this.setInSchema(subQuery.getOutSchema());
     this.setOutSchema(subQuery.getOutSchema());

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalOptimizer.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalOptimizer.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalOptimizer.java
index acbace0..b462a30 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalOptimizer.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalOptimizer.java
@@ -36,6 +36,7 @@ import org.apache.tajo.engine.planner.rewrite.FilterPushDownRule;
 import org.apache.tajo.engine.planner.rewrite.PartitionedTableRewriter;
 import org.apache.tajo.engine.planner.rewrite.ProjectionPushDownRule;
 
+import java.util.LinkedHashSet;
 import java.util.Set;
 import java.util.Stack;
 
@@ -77,7 +78,7 @@ public class LogicalOptimizer {
   private void optimizeJoinOrder(LogicalPlan plan, String blockName) throws PlanningException {
     LogicalPlan.QueryBlock block = plan.getBlock(blockName);
 
-    if (block.hasJoinNode()) {
+    if (block.hasNode(NodeType.JOIN)) {
       String originalOrder = JoinOrderStringBuilder.buildJoinOrderString(plan, block);
       double nonOptimizedJoinCost = JoinCostComputer.computeCost(plan, block);
 
@@ -87,12 +88,39 @@ public class LogicalOptimizer {
       // finding join order and restore remain filter order
       FoundJoinOrder order = joinOrderAlgorithm.findBestOrder(plan, block,
           joinGraphContext.joinGraph, joinGraphContext.relationsForProduct);
-      block.setJoinNode(order.getOrderedJoin());
+      JoinNode newJoinNode = order.getOrderedJoin();
 
+      JoinNode old = block.getNode(NodeType.JOIN);
+      JoinTargetCollector collector = new JoinTargetCollector();
+      Set<Target> targets = new LinkedHashSet<Target>();
+      collector.visitJoin(targets, plan, block, old, new Stack<LogicalNode>());
+
+      if (targets.size() == 0) {
+        newJoinNode.setTargets(PlannerUtil.schemaToTargets(old.getOutSchema()));
+      } else {
+        newJoinNode.setTargets(targets.toArray(new Target[targets.size()]));
+      }
+
+      PlannerUtil.replaceNode(plan, block.getRoot(), old, newJoinNode);
       String optimizedOrder = JoinOrderStringBuilder.buildJoinOrderString(plan, block);
+      block.addPlanHistory("Non-optimized join order: " + originalOrder + " (cost: " + nonOptimizedJoinCost + ")");
+      block.addPlanHistory("Optimized join order    : " + optimizedOrder + " (cost: " + order.getCost() + ")");
+    }
+  }
 
-      block.addHistory("Non-optimized join order: " + originalOrder + " (cost: " + nonOptimizedJoinCost + ")");
-      block.addHistory("Optimized join order    : " + optimizedOrder + " (cost: " + order.getCost() + ")");
+  private static class JoinTargetCollector extends BasicLogicalPlanVisitor<Set<Target>, LogicalNode> {
+    @Override
+    public LogicalNode visitJoin(Set<Target> ctx, LogicalPlan plan, LogicalPlan.QueryBlock block, JoinNode node,
+                                 Stack<LogicalNode> stack)
+        throws PlanningException {
+      super.visitJoin(ctx, plan, block, node, stack);
+
+      if (node.hasTargets()) {
+        for (Target target : node.getTargets()) {
+          ctx.add(target);
+        }
+      }
+      return node;
     }
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlan.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlan.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlan.java
index 584fd6e..2519a95 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlan.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlan.java
@@ -19,12 +19,13 @@
 package org.apache.tajo.engine.planner;
 
 import com.google.common.collect.Lists;
-import com.google.common.collect.Sets;
+import org.apache.commons.lang.ObjectUtils;
 import org.apache.tajo.algebra.*;
 import org.apache.tajo.annotation.NotThreadSafe;
 import org.apache.tajo.catalog.Column;
 import org.apache.tajo.catalog.Schema;
-import org.apache.tajo.engine.eval.*;
+import org.apache.tajo.engine.eval.EvalNode;
+import org.apache.tajo.engine.eval.EvalTreeUtil;
 import org.apache.tajo.engine.exception.NoSuchColumnException;
 import org.apache.tajo.engine.exception.VerifyException;
 import org.apache.tajo.engine.planner.graph.DirectedGraphCursor;
@@ -39,13 +40,12 @@ import java.util.*;
  */
 @NotThreadSafe
 public class LogicalPlan {
-  private final LogicalPlanner planner;
-
   /** the prefix character for virtual tables */
-  public static final char VIRTUAL_TABLE_PREFIX='@';
+  public static final char VIRTUAL_TABLE_PREFIX='#';
+  public static final char NONAMED_COLUMN_PREFIX='?';
   /** it indicates the root block */
   public static final String ROOT_BLOCK = VIRTUAL_TABLE_PREFIX + "ROOT";
-  public static final String NONAME_BLOCK_PREFIX = VIRTUAL_TABLE_PREFIX + "NONAME_";
+  public static final String NONAME_BLOCK_PREFIX = VIRTUAL_TABLE_PREFIX + "QB_";
   private int nextPid = 0;
   private Integer noNameBlockId = 0;
   private Integer noNameColumnId = 0;
@@ -54,10 +54,12 @@ public class LogicalPlan {
   private Map<String, QueryBlock> queryBlocks = new LinkedHashMap<String, QueryBlock>();
   private Map<Integer, LogicalNode> nodeMap = new HashMap<Integer, LogicalNode>();
   private Map<Integer, QueryBlock> queryBlockByPID = new HashMap<Integer, QueryBlock>();
+  private Map<String, String> exprToBlockNameMap = TUtil.newHashMap();
   private SimpleDirectedGraph<String, BlockEdge> queryBlockGraph = new SimpleDirectedGraph<String, BlockEdge>();
 
   /** planning and optimization log */
   private List<String> planingHistory = Lists.newArrayList();
+  LogicalPlanner planner;
 
   public LogicalPlan(LogicalPlanner planner) {
     this.planner = planner;
@@ -79,23 +81,39 @@ public class LogicalPlan {
     return nextPid++;
   }
 
-  public QueryBlock newNoNameBlock() {
+  public QueryBlock newQueryBlock() {
     return newAndGetBlock(NONAME_BLOCK_PREFIX + (noNameBlockId++));
   }
 
-  public String newNonameColumnName(String prefix) {
-    String suffix = noNameColumnId == 0 ? "" : String.valueOf(noNameColumnId);
-    noNameColumnId++;
-    return "?" + prefix + suffix;
+  private String generateFieldName(String prefix) {
+    int sequence = noNameColumnId++;
+    return NONAMED_COLUMN_PREFIX + prefix.toLowerCase() + (sequence > 0 ? "_" + sequence : "");
   }
 
-  /**
-   * Check if a query block exists
-   * @param blockName the query block name to be checked
-   * @return true if exists. Otherwise, false
-   */
-  public boolean existBlock(String blockName) {
-    return queryBlocks.containsKey(blockName);
+  public String newGeneratedFieldName(EvalNode evalNode) {
+    String prefix = evalNode.getName();
+    return generateFieldName(prefix);
+  }
+
+  public String newGeneratedFieldName(Expr expr) {
+    String prefix;
+
+    switch (expr.getType()) {
+    case CountRowsFunction:
+      prefix = "count";
+      break;
+    case GeneralSetFunction:
+      GeneralSetFunctionExpr setFunction = (GeneralSetFunctionExpr) expr;
+      prefix = setFunction.getSignature();
+      break;
+    case Function:
+      FunctionExpr function = (FunctionExpr) expr;
+      prefix = function.getSignature();
+      break;
+    default:
+      prefix = expr.getType().name();
+    }
+    return generateFieldName(prefix);
   }
 
   public QueryBlock getRootBlock() {
@@ -137,6 +155,18 @@ public class LogicalPlan {
     return childBlocks;
   }
 
+  public void mapExprToBlock(Expr expr, String blockName) {
+    exprToBlockNameMap.put(ObjectUtils.identityToString(expr), blockName);
+  }
+
+  public QueryBlock getBlockByExpr(Expr expr) {
+    return getBlock(exprToBlockNameMap.get(ObjectUtils.identityToString(expr)));
+  }
+
+  public String getBlockNameByExpr(Expr expr) {
+    return exprToBlockNameMap.get(ObjectUtils.identityToString(expr));
+  }
+
   public Collection<QueryBlock> getQueryBlocks() {
     return queryBlocks.values();
   }
@@ -145,13 +175,18 @@ public class LogicalPlan {
     return queryBlockGraph;
   }
 
+  public String getNormalizedColumnName(QueryBlock block, ColumnReferenceExpr columnRef)
+      throws PlanningException {
+    Column found = resolveColumn(block, columnRef);
+    return found.getQualifiedName();
+  }
+
   /**
    * It resolves a column.
    */
-  public Column resolveColumn(QueryBlock block, LogicalNode currentNode, ColumnReferenceExpr columnRef)
-      throws PlanningException {
+  public Column resolveColumn(QueryBlock block, ColumnReferenceExpr columnRef) throws PlanningException {
 
-    if (columnRef.hasQualifier()) { // if a column referenec is qualified
+    if (columnRef.hasQualifier()) { // if a column reference is qualified
 
       RelationNode relationOp = block.getRelation(columnRef.getQualifier());
 
@@ -159,44 +194,73 @@ public class LogicalPlan {
       if (relationOp == null) {
         // TODO - nested query can only refer outer query block? or not?
         for (QueryBlock eachBlock : queryBlocks.values()) {
-          if (eachBlock.containRelation(columnRef.getQualifier())) {
+          if (eachBlock.existsRelation(columnRef.getQualifier())) {
             relationOp = eachBlock.getRelation(columnRef.getQualifier());
           }
         }
       }
 
+      // If we cannot find any relation against a qualified column name
       if (relationOp == null) {
         throw new NoSuchColumnException(columnRef.getCanonicalName());
       }
 
       Schema schema = relationOp.getTableSchema();
-
       Column column = schema.getColumnByFQN(columnRef.getCanonicalName());
       if (column == null) {
-        throw new VerifyException("ERROR: no such a column '"+ columnRef.getCanonicalName() + "'");
+        throw new NoSuchColumnException(columnRef.getCanonicalName());
       }
 
-      return column;
+      // If code reach here, a column is found.
+      // But, it may be aliased from bottom logical node.
+      // If the column is aliased, the found name may not be used in upper node.
+
+      // Here, we try to check if column reference is already aliased.
+      // If so, it replaces the name with aliased name.
+      LogicalNode currentNode = block.getCurrentNode();
+
+      // The condition (currentNode.getInSchema().contains(column)) means
+      // the column can be used at the current node. So, we don't need to find aliase name.
+      if (currentNode != null && !currentNode.getInSchema().contains(column)) {
+        List<Column> candidates = TUtil.newList();
+        if (block.namedExprsMgr.isAliased(column.getQualifiedName())) {
+          String alias = block.namedExprsMgr.getAlias(columnRef.getCanonicalName());
+          Column found = resolveColumn(block, new ColumnReferenceExpr(alias));
+          if (found != null) {
+            candidates.add(found);
+          }
+        }
+        if (!candidates.isEmpty()) {
+          return ensureUniqueColumn(candidates);
+        }
+      }
 
+      return column;
     } else { // if a column reference is not qualified
 
-      // if current logical node is available
-      if (currentNode != null && currentNode.getOutSchema() != null) {
-        Column found = currentNode.getOutSchema().getColumnByName(columnRef.getName());
+      // Trying to find the column within the current block
+
+      if (block.getLatestNode() != null) {
+        Column found = block.getLatestNode().getOutSchema().getColumnByName(columnRef.getName());
         if (found != null) {
           return found;
         }
       }
 
-      if (block.getLatestNode() != null) {
-        Column found = block.getLatestNode().getOutSchema().getColumnByName(columnRef.getName());
+      List<Column> candidates = TUtil.newList();
+      // Trying to find columns from aliased references.
+      if (block.namedExprsMgr.isAliased(columnRef.getCanonicalName())) {
+        String originalName = block.namedExprsMgr.getAlias(columnRef.getCanonicalName());
+        Column found = resolveColumn(block, new ColumnReferenceExpr(originalName));
         if (found != null) {
-          return found;
+          candidates.add(found);
         }
       }
+      if (!candidates.isEmpty()) {
+        return ensureUniqueColumn(candidates);
+      }
 
       // Trying to find columns from other relations in the current block
-      List<Column> candidates = TUtil.newList();
       for (RelationNode rel : block.getRelations()) {
         Column found = rel.getOutSchema().getColumnByName(columnRef.getName());
         if (found != null) {
@@ -238,16 +302,6 @@ public class LogicalPlan {
     }
   }
 
-  /**
-   * replace the found column if the column is renamed to an alias name
-   */
-  public Column getColumnOrAliasedColumn(QueryBlock block, Column column) throws PlanningException {
-    if (block.targetListManager.isResolve(column)) {
-      column = block.targetListManager.getResolvedColumn(column);
-    }
-    return column;
-  }
-
   private static Column ensureUniqueColumn(List<Column> candidates)
       throws VerifyException {
     if (candidates.size() == 1) {
@@ -282,9 +336,9 @@ public class LogicalPlan {
         new DirectedGraphCursor<String, BlockEdge>(queryBlockGraph, getRootBlock().getName());
     while(cursor.hasNext()) {
       QueryBlock block = getBlock(cursor.nextBlock());
-      if (block.getPlaningHistory().size() > 0) {
+      if (block.getPlanHistory().size() > 0) {
         sb.append("\n[").append(block.getName()).append("]\n");
-        for (String log : block.getPlaningHistory()) {
+        for (String log : block.getPlanHistory()) {
           sb.append("> ").append(log).append("\n");
         }
       }
@@ -308,7 +362,7 @@ public class LogicalPlan {
             ExplainLogicalPlanVisitor.printDepthString(explainContext.getMaxDepth(), explainContext.explains.pop()));
       }
     } catch (PlanningException e) {
-      e.printStackTrace();
+      throw new RuntimeException(e);
     }
 
     return explains.toString();
@@ -366,41 +420,43 @@ public class LogicalPlan {
   }
 
   public class QueryBlock {
-    private String blockName;
+    private final String blockName;
     private LogicalNode rootNode;
     private NodeType rootType;
-    private Map<String, RelationNode> relations = new HashMap<String, RelationNode>();
-    private Map<OpType, List<Expr>> algebraicExprs = TUtil.newHashMap();
 
-    // changing states
+    // transient states
+    private final Map<String, RelationNode> nameToRelationMap = TUtil.newHashMap();
+    private final Map<OpType, List<Expr>> operatorToExprMap = TUtil.newHashMap();
+    /**
+     * It's a map between nodetype and node. node types can be duplicated. So, latest node type is only kept.
+     */
+    private final Map<NodeType, LogicalNode> nodeTypeToNodeMap = TUtil.newHashMap();
+    private final Map<String, LogicalNode> exprToNodeMap = TUtil.newHashMap();
+    final NamedExprsManager namedExprsMgr;
+
+    private LogicalNode currentNode;
     private LogicalNode latestNode;
-    private boolean resolvedGrouping = true;
-    private boolean hasGrouping;
-    private Projectable projectionNode;
-    private GroupbyNode groupingNode;
-    private JoinNode joinNode;
-    private SelectionNode selectionNode;
-    private StoreTableNode storeTableNode;
-    private InsertNode insertNode;
+    private final Set<JoinType> includedJoinTypes = TUtil.newHashSet();
+    /**
+     * Set true value if this query block has either implicit or explicit aggregation.
+     */
+    private boolean aggregationRequired = true;
     private Schema schema;
 
-    TargetListManager targetListManager;
-
     /** It contains a planning log for this block */
-    private List<String> planingHistory = Lists.newArrayList();
+    private final List<String> planingHistory = Lists.newArrayList();
+    /** It is for debugging or unit tests */
+    private Target [] unresolvedTargets;
 
     public QueryBlock(String blockName) {
       this.blockName = blockName;
+      this.namedExprsMgr = new NamedExprsManager(LogicalPlan.this);
     }
 
     public String getName() {
       return blockName;
     }
 
-    public boolean hasRoot() {
-      return rootNode != null;
-    }
-
     public void refresh() {
       setRoot(rootNode);
     }
@@ -411,7 +467,6 @@ public class LogicalPlan {
         LogicalRootNode rootNode = (LogicalRootNode) blockRoot;
         rootType = rootNode.getChild().getType();
       }
-      queryBlockByPID.put(blockRoot.getPID(), this);
     }
 
     public <NODE extends LogicalNode> NODE getRoot() {
@@ -422,20 +477,32 @@ public class LogicalPlan {
       return rootType;
     }
 
-    public boolean containRelation(String name) {
-      return relations.containsKey(PlannerUtil.normalizeTableName(name));
+    public Target [] getUnresolvedTargets() {
+      return unresolvedTargets;
     }
 
-    public void addRelation(RelationNode relation) {
-      relations.put(PlannerUtil.normalizeTableName(relation.getCanonicalName()), relation);
+    public void setUnresolvedTargets(Target [] unresolvedTargets) {
+      this.unresolvedTargets = unresolvedTargets;
+    }
+
+    public boolean existsRelation(String name) {
+      return nameToRelationMap.containsKey(PlannerUtil.normalizeTableName(name));
     }
 
     public RelationNode getRelation(String name) {
-      return relations.get(PlannerUtil.normalizeTableName(name));
+      return nameToRelationMap.get(PlannerUtil.normalizeTableName(name));
+    }
+
+    public void addRelation(RelationNode relation) {
+      nameToRelationMap.put(PlannerUtil.normalizeTableName(relation.getCanonicalName()), relation);
     }
 
     public Collection<RelationNode> getRelations() {
-      return this.relations.values();
+      return this.nameToRelationMap.values();
+    }
+
+    public boolean hasTableExpression() {
+      return this.nameToRelationMap.size() > 0;
     }
 
     public void setSchema(Schema schema) {
@@ -446,8 +513,22 @@ public class LogicalPlan {
       return schema;
     }
 
-    public boolean hasTableExpression() {
-      return this.relations.size() > 0;
+    public NamedExprsManager getNamedExprsManager() {
+      return namedExprsMgr;
+    }
+
+    public void updateCurrentNode(Expr expr) throws PlanningException {
+
+      if (expr.getType() != OpType.RelationList) { // skip relation list because it is a virtual expr.
+        this.currentNode = exprToNodeMap.get(ObjectUtils.identityToString(expr));
+        if (currentNode == null) {
+          throw new PlanningException("Unregistered Algebra Expression: " + expr.getType());
+        }
+      }
+    }
+
+    public <T extends LogicalNode> T getCurrentNode() {
+      return (T) this.currentNode;
     }
 
     public void updateLatestNode(LogicalNode node) {
@@ -459,384 +540,94 @@ public class LogicalPlan {
     }
 
     public void setAlgebraicExpr(Expr expr) {
-      TUtil.putToNestedList(algebraicExprs, expr.getType(), expr);
+      TUtil.putToNestedList(operatorToExprMap, expr.getType(), expr);
     }
 
     public boolean hasAlgebraicExpr(OpType opType) {
-      return algebraicExprs.containsKey(opType);
+      return operatorToExprMap.containsKey(opType);
     }
 
     public <T extends Expr> List<T> getAlgebraicExpr(OpType opType) {
-      return (List<T>) algebraicExprs.get(opType);
+      return (List<T>) operatorToExprMap.get(opType);
     }
 
     public <T extends Expr> T getSingletonExpr(OpType opType) {
       if (hasAlgebraicExpr(opType)) {
-        return (T) algebraicExprs.get(opType).get(0);
+        return (T) operatorToExprMap.get(opType).get(0);
       } else {
         return null;
       }
     }
 
-    public boolean hasProjection() {
-      return hasAlgebraicExpr(OpType.Projection);
-    }
-
-    public Projection getProjection() {
-      return getSingletonExpr(OpType.Projection);
-    }
-
-    public boolean hasHaving() {
-      return hasAlgebraicExpr(OpType.Having);
-    }
-
-    public Having getHaving() {
-      return getSingletonExpr(OpType.Having);
-    }
-
-    public void setProjectionNode(Projectable node) {
-      this.projectionNode = node;
-    }
-
-    public Projectable getProjectionNode() {
-      return this.projectionNode;
+    public boolean hasNode(NodeType nodeType) {
+      return nodeTypeToNodeMap.containsKey(nodeType);
     }
 
-    public boolean isGroupingResolved() {
-      return this.resolvedGrouping;
-    }
-
-    public void resolveGroupingRequired() {
-      this.resolvedGrouping = true;
-    }
-
-    public void setHasGrouping() {
-      hasGrouping = true;
-      resolvedGrouping = false;
-    }
+    public void registerNode(LogicalNode node) {
+      // id -> node
+      nodeMap.put(node.getPID(), node);
 
-    public boolean hasGrouping() {
-      return hasGrouping || hasGroupbyNode();
-    }
+      // So, this is only for filter, groupby, sort, limit, projection, which exists once at a query block.
+      nodeTypeToNodeMap.put(node.getType(), node);
 
-    public boolean hasGroupbyNode() {
-      return this.groupingNode != null;
+      queryBlockByPID.put(node.getPID(), this);
     }
 
-    public void setGroupbyNode(GroupbyNode groupingNode) {
-      this.groupingNode = groupingNode;
+    public <T extends LogicalNode> T getNode(NodeType nodeType) {
+      return (T) nodeTypeToNodeMap.get(nodeType);
     }
 
-    public GroupbyNode getGroupbyNode() {
-      return this.groupingNode;
+    // expr -> node
+    public void registerExprWithNode(Expr expr, LogicalNode node) {
+      exprToNodeMap.put(ObjectUtils.identityToString(expr), node);
     }
 
-    public boolean hasJoinNode() {
-      return joinNode != null;
+    public <T extends LogicalNode> T getNodeFromExpr(Expr expr) {
+      return (T) exprToNodeMap.get(ObjectUtils.identityToString(expr));
     }
 
     /**
-     * @return the topmost JoinNode instance
+     * This flag can be changed as a plan is generated.
+     *
+     * True value means that this query should have aggregation phase. If aggregation plan is added to this block,
+     * it becomes false because it doesn't need aggregation phase anymore. It is usually used to add aggregation
+     * phase from SELECT statement without group-by clause.
+     *
+     * @return True if aggregation is needed but this query hasn't had aggregation phase.
      */
-    public JoinNode getJoinNode() {
-      return joinNode;
-    }
-
-    public void setJoinNode(JoinNode node) {
-      if (joinNode == null || latestNode == node) {
-        this.joinNode = node;
-      } else {
-        PlannerUtil.replaceNode(LogicalPlan.this, latestNode, this.joinNode, node);
-      }
-    }
-
-    public boolean hasSelectionNode() {
-      return this.selectionNode != null;
-    }
-
-    public void setSelectionNode(SelectionNode selectionNode) {
-      this.selectionNode = selectionNode;
+    public boolean isAggregationRequired() {
+      return this.aggregationRequired;
     }
 
-    public SelectionNode getSelectionNode() {
-      return selectionNode;
-    }
-
-    public boolean hasStoreTableNode() {
-      return this.storeTableNode != null;
-    }
-
-    public void setStoreTableNode(StoreTableNode storeTableNode) {
-      this.storeTableNode = storeTableNode;
-    }
-
-    public StoreTableNode getStoreTableNode() {
-      return this.storeTableNode;
+    /**
+     * Unset aggregation required flag. It has to be called after an aggregation phase is added to this block.
+     */
+    public void unsetAggregationRequire() {
+      this.aggregationRequired = true;
     }
 
-    public boolean hasInsertNode() {
-      return this.insertNode != null;
+    public void setAggregationRequire() {
+      aggregationRequired = false;
     }
 
-    public InsertNode getInsertNode() {
-      return this.insertNode;
+    public boolean containsJoinType(JoinType joinType) {
+      return includedJoinTypes.contains(joinType);
     }
 
-    public void setInsertNode(InsertNode insertNode) {
-      this.insertNode = insertNode;
+    public void addJoinType(JoinType joinType) {
+      includedJoinTypes.add(joinType);
     }
 
-    public List<String> getPlaningHistory() {
+    public List<String> getPlanHistory() {
       return planingHistory;
     }
 
-    public void addHistory(String history) {
+    public void addPlanHistory(String history) {
       this.planingHistory.add(history);
     }
 
-    public boolean postVisit(LogicalNode node, Stack<OpType> path) {
-      if (nodeMap.containsKey(node.getPID())) {
-        return false;
-      }
-
-      nodeMap.put(node.getPID(), node);
-      updateLatestNode(node);
-
-      // if an added operator is a relation, add it to relation set.
-      switch (node.getType()) {
-        case STORE:
-          setStoreTableNode((StoreTableNode) node);
-          break;
-
-        case SCAN:
-          ScanNode relationOp = (ScanNode) node;
-          addRelation(relationOp);
-          break;
-
-        case GROUP_BY:
-          resolveGroupingRequired();
-          setGroupbyNode((GroupbyNode) node);
-          break;
-
-        case JOIN:
-          setJoinNode((JoinNode) node);
-          break;
-
-        case SELECTION:
-          setSelectionNode((SelectionNode) node);
-          break;
-
-        case INSERT:
-          setInsertNode((InsertNode) node);
-          break;
-
-        case TABLE_SUBQUERY:
-          TableSubQueryNode tableSubQueryNode = (TableSubQueryNode) node;
-          addRelation(tableSubQueryNode);
-          break;
-      }
-
-      // if this node is the topmost
-      if (path.size() == 0) {
-        setRoot(node);
-      }
-
-      return true;
-    }
-
     public String toString() {
       return blockName;
     }
-
-    ///////////////////////////////////////////////////////////////////////////
-    //                 Target List Management Methods
-    ///////////////////////////////////////////////////////////////////////////
-    //
-    // A target list means a list of expressions after SELECT keyword in SQL.
-    //
-    // SELECT rel1.col1, sum(rel1.col2), res1.col3 + res2.col2, ... FROM ...
-    //        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-    //                        TARGET LIST
-    //
-    ///////////////////////////////////////////////////////////////////////////
-
-    public void initTargetList(Target[] original) {
-      targetListManager = new TargetListManager(LogicalPlan.this, original);
-    }
-
-    public boolean isTargetResolved(int targetId) {
-      return targetListManager.isResolved(targetId);
-    }
-
-    public void resolveAllTargetList() {
-      targetListManager.resolveAll();
-    }
-
-    public void resolveTarget(int idx) {
-      targetListManager.resolve(idx);
-    }
-
-    public boolean isAlreadyTargetCreated(int idx) {
-      return getTarget(idx) != null;
-    }
-
-    public Target getTarget(int idx) {
-      return targetListManager.getTarget(idx);
-    }
-
-    public int getTargetListNum() {
-      return targetListManager.size();
-    }
-
-    public void fillTarget(int idx) throws PlanningException {
-      Target target = planner.createTarget(LogicalPlan.this, this, getProjection().getTargets()[idx]);
-      // below code reaches only when target is created.
-      targetListManager.fill(idx, target);
-    }
-
-    public boolean checkIfTargetCanBeEvaluated(int targetId, LogicalNode node) {
-      return isAlreadyTargetCreated(targetId)
-          && PlannerUtil.canBeEvaluated(targetListManager.getTarget(targetId).getEvalTree(), node);
-    }
-
-    public TargetListManager getTargetListManager() {
-      return targetListManager;
-    }
-
-    public Target [] getCurrentTargets() {
-      return targetListManager.getTargets();
-    }
-
-    public Schema updateSchema() {
-      return targetListManager.getUpdatedSchema();
-    }
-
-    public void fillTargets() throws PlanningException {
-      for (int i = 0; i < getTargetListNum(); i++) {
-        if (!isAlreadyTargetCreated(i)) {
-          try {
-            fillTarget(i);
-          } catch (VerifyException e) {
-          }
-        }
-      }
-    }
-
-    public void checkAndResolveTargets(LogicalNode node) throws PlanningException {
-      // If all columns are projected and do not include any expression
-      if (getProjection().isAllProjected() && node instanceof RelationNode) {
-        initTargetList(PlannerUtil.schemaToTargets(node.getOutSchema()));
-        resolveAllTargetList();
-
-      } else {
-        // fill a target if an annotated target can be created.
-        // Some targets which are based on multiple relations can be created only in a join node.
-        fillTargets();
-
-        // add target to list if a target can be evaluated at this node
-        List<Integer> newEvaluatedTargetIds = new ArrayList<Integer>();
-        for (int i = 0; i < getTargetListNum(); i++) {
-          if (getTarget(i) != null && !isTargetResolved(i)) {
-            EvalNode expr = getTarget(i).getEvalTree();
-
-            if (checkIfTargetCanBeEvaluated(i, node)) {
-
-              if (node instanceof RelationNode) { // for scan node
-                if (expr.getType() == EvalType.FIELD) {
-                  resolveTarget(i);
-                  if (getTarget(i).hasAlias()) {
-                    newEvaluatedTargetIds.add(i);
-                  }
-                } else if (EvalTreeUtil.findDistinctAggFunction(expr).size() == 0) {
-                  // if this expression does no contain any aggregation function
-                  resolveTarget(i);
-                  newEvaluatedTargetIds.add(i);
-                }
-
-              } else if (node instanceof GroupbyNode) { // for grouping
-                if (EvalTreeUtil.findDistinctAggFunction(expr).size() > 0) {
-                  resolveTarget(i);
-                  newEvaluatedTargetIds.add(i);
-                }
-
-              } else if (node instanceof JoinNode) { // for join
-                if (EvalTreeUtil.findDistinctAggFunction(expr).size() == 0) {
-                  // if this expression does no contain any aggregation function,
-                  resolveTarget(i);
-                  newEvaluatedTargetIds.add(i);
-                }
-              }
-            }
-          }
-        }
-
-        if (node instanceof ScanNode || node instanceof JoinNode) {
-
-          Schema baseSchema = null;
-          if (node instanceof ScanNode) {
-            baseSchema = ((ScanNode)node).getTableSchema();
-          } else if (node instanceof JoinNode) {
-            baseSchema = node.getInSchema(); // composite schema
-          }
-
-          if (newEvaluatedTargetIds.size() > 0) {
-            // fill addedTargets with output columns and new expression columns (e.g., aliased column or expressions)
-            Target[] addedTargets = new Target[baseSchema.getColumnNum() + newEvaluatedTargetIds.size()];
-            PlannerUtil.schemaToTargets(baseSchema, addedTargets);
-            int baseIdx = baseSchema.getColumnNum();
-            for (int i = 0; i < newEvaluatedTargetIds.size(); i++) {
-              addedTargets[baseIdx + i] = getTarget(newEvaluatedTargetIds.get(i));
-            }
-
-            // set targets to ScanNode because it needs to evaluate expressions
-            ((Projectable)node).setTargets(addedTargets);
-            // the output schema of ScanNode has to have the combination of the original output and newly-added targets.
-            node.setOutSchema(LogicalPlanner.getProjectedSchema(LogicalPlan.this, addedTargets));
-          } else {
-            // if newEvaluatedTargetIds == 0, the original input schema will be used as the output schema.
-            node.setOutSchema(node.getInSchema());
-          }
-        } else if (node instanceof GroupbyNode) {
-          // Set the current targets to the GroupByNode because the GroupByNode is the last projection operator.
-          GroupbyNode groupbyNode = (GroupbyNode) node;
-          groupbyNode.setTargets(targetListManager.getUpdatedTarget(Sets.newHashSet(newEvaluatedTargetIds)));
-          //groupbyNode.setTargets(getCurrentTargets());
-          boolean distinct = false;
-          for (Target target : groupbyNode.getTargets()) {
-            for (AggregationFunctionCallEval aggrFunc : EvalTreeUtil.findDistinctAggFunction(target.getEvalTree())) {
-              if (aggrFunc.isDistinct()) {
-                distinct = true;
-                break;
-              }
-            }
-          }
-          groupbyNode.setDistinct(distinct);
-          node.setOutSchema(updateSchema());
-
-          // if a having condition is given,
-          if (hasHaving()) {
-            EvalNode havingCondition = planner.createEvalTree(LogicalPlan.this, this, getHaving().getQual());
-            List<AggregationFunctionCallEval> aggrFunctions = EvalTreeUtil.findDistinctAggFunction(havingCondition);
-
-            if (aggrFunctions.size() == 0) {
-              groupbyNode.setHavingCondition(havingCondition);
-            } else {
-              Target [] addedTargets = new Target[aggrFunctions.size()];
-              for (int i = 0; i < aggrFunctions.size(); i++) {
-                Target aggrFunctionTarget = new Target(aggrFunctions.get(i),
-                    newNonameColumnName(aggrFunctions.get(i).getName()));
-                addedTargets[i] = aggrFunctionTarget;
-                EvalTreeUtil.replace(havingCondition, aggrFunctions.get(i),
-                    new FieldEval(aggrFunctionTarget.getColumnSchema()));
-              }
-              Target [] updatedTargets = TUtil.concat(groupbyNode.getTargets(), addedTargets);
-              groupbyNode.setTargets(updatedTargets);
-              groupbyNode.setHavingCondition(havingCondition);
-              groupbyNode.setHavingSchema(PlannerUtil.targetToSchema(groupbyNode.getTargets()));
-            }
-          }
-        }
-      }
-    }
   }
 }
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanPreprocessor.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanPreprocessor.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanPreprocessor.java
new file mode 100644
index 0000000..3ab328c
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanPreprocessor.java
@@ -0,0 +1,301 @@
+/**
+ * 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.engine.planner;
+
+import org.apache.tajo.algebra.*;
+import org.apache.tajo.catalog.CatalogService;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.catalog.TableDesc;
+import org.apache.tajo.engine.eval.EvalNode;
+import org.apache.tajo.engine.eval.EvalType;
+import org.apache.tajo.engine.eval.FieldEval;
+import org.apache.tajo.engine.planner.logical.*;
+import org.apache.tajo.engine.utils.SchemaUtil;
+
+import java.util.Stack;
+
+/**
+ * It finds all relations for each block and builds base schema information.
+ */
+class LogicalPlanPreprocessor extends BaseAlgebraVisitor<LogicalPlanPreprocessor.PreprocessContext, LogicalNode> {
+  private ExprAnnotator annotator;
+
+  static class PreprocessContext {
+    LogicalPlan plan;
+    LogicalPlan.QueryBlock currentBlock;
+
+    public PreprocessContext(LogicalPlan plan, LogicalPlan.QueryBlock currentBlock) {
+      this.plan = plan;
+      this.currentBlock = currentBlock;
+    }
+
+    public PreprocessContext(PreprocessContext context, LogicalPlan.QueryBlock currentBlock) {
+      this.plan = context.plan;
+      this.currentBlock = currentBlock;
+    }
+  }
+
+  /** Catalog service */
+  private CatalogService catalog;
+
+  LogicalPlanPreprocessor(CatalogService catalog, ExprAnnotator annotator) {
+    this.catalog = catalog;
+    this.annotator = annotator;
+  }
+
+  @Override
+  public void preHook(PreprocessContext ctx, Stack<Expr> stack, Expr expr) throws PlanningException {
+    ctx.currentBlock.setAlgebraicExpr(expr);
+    ctx.plan.mapExprToBlock(expr, ctx.currentBlock.getName());
+  }
+
+  @Override
+  public LogicalNode postHook(PreprocessContext ctx, Stack<Expr> stack, Expr expr, LogicalNode result) throws PlanningException {
+    // If non-from statement, result can be null. It avoids that case.
+    if (result != null) {
+      // setNode method registers each node to corresponding block and plan.
+      ctx.currentBlock.registerNode(result);
+      // It makes a map between an expr and a logical node.
+      ctx.currentBlock.registerExprWithNode(expr, result);
+    }
+    return result;
+  }
+
+  @Override
+  public LogicalNode visitProjection(PreprocessContext ctx, Stack<Expr> stack, Projection expr) throws PlanningException {
+    // If Non-from statement, it immediately returns.
+    if (!expr.hasChild()) {
+      return new EvalExprNode(ctx.plan.newPID());
+    }
+
+    stack.push(expr); // <--- push
+    LogicalNode child = visit(ctx, stack, expr.getChild());
+
+    Target [] targets;
+    if (expr.isAllProjected()) {
+      targets = PlannerUtil.schemaToTargets(child.getOutSchema());
+    } else {
+      targets = new Target[expr.getNamedExprs().length];
+
+      for (int i = 0; i < expr.getNamedExprs().length; i++) {
+        NamedExpr namedExpr = expr.getNamedExprs()[i];
+        EvalNode evalNode = annotator.createEvalNode(ctx.plan, ctx.currentBlock, namedExpr.getExpr());
+
+        if (namedExpr.hasAlias()) {
+          targets[i] = new Target(evalNode, namedExpr.getAlias());
+        } else if (evalNode.getType() == EvalType.FIELD) {
+          targets[i] = new Target((FieldEval) evalNode);
+        } else {
+          targets[i] = new Target(evalNode, "?name_" + i);
+        }
+      }
+    }
+    stack.pop(); // <--- Pop
+
+    ProjectionNode projectionNode = new ProjectionNode(ctx.plan.newPID());
+    projectionNode.setInSchema(child.getOutSchema());
+    projectionNode.setOutSchema(PlannerUtil.targetToSchema(targets));
+    return projectionNode;
+  }
+
+  @Override
+  public LogicalNode visitLimit(PreprocessContext ctx, Stack<Expr> stack, Limit expr) throws PlanningException {
+    stack.push(expr);
+    LogicalNode child = visit(ctx, stack, expr.getChild());
+    stack.pop();
+
+    LimitNode limitNode = new LimitNode(ctx.plan.newPID());
+    limitNode.setInSchema(child.getOutSchema());
+    limitNode.setOutSchema(child.getOutSchema());
+    return limitNode;
+  }
+
+  @Override
+  public LogicalNode visitSort(PreprocessContext ctx, Stack<Expr> stack, Sort expr) throws PlanningException {
+    stack.push(expr);
+    LogicalNode child = visit(ctx, stack, expr.getChild());
+    stack.pop();
+
+    SortNode sortNode = new SortNode(ctx.plan.newPID());
+    sortNode.setInSchema(child.getOutSchema());
+    sortNode.setOutSchema(child.getOutSchema());
+    return sortNode;
+  }
+
+  @Override
+  public LogicalNode visitHaving(PreprocessContext ctx, Stack<Expr> stack, Having expr) throws PlanningException {
+    stack.push(expr);
+    LogicalNode child = visit(ctx, stack, expr.getChild());
+    stack.pop();
+
+    HavingNode havingNode = new HavingNode(ctx.plan.newPID());
+    havingNode.setInSchema(child.getOutSchema());
+    havingNode.setOutSchema(child.getOutSchema());
+    return havingNode;
+  }
+
+  @Override
+  public LogicalNode visitGroupBy(PreprocessContext ctx, Stack<Expr> stack, Aggregation expr) throws PlanningException {
+    stack.push(expr); // <--- push
+    LogicalNode child = visit(ctx, stack, expr.getChild());
+
+    Projection projection = ctx.currentBlock.getSingletonExpr(OpType.Projection);
+    int finalTargetNum = projection.getNamedExprs().length;
+    Target [] targets = new Target[finalTargetNum];
+
+    for (int i = 0; i < finalTargetNum; i++) {
+      NamedExpr namedExpr = projection.getNamedExprs()[i];
+      EvalNode evalNode = annotator.createEvalNode(ctx.plan, ctx.currentBlock, namedExpr.getExpr());
+
+      if (namedExpr.hasAlias()) {
+        targets[i] = new Target(evalNode, namedExpr.getAlias());
+      } else {
+        targets[i] = new Target(evalNode, "?name_" + i);
+      }
+    }
+    stack.pop();
+
+    GroupbyNode groupByNode = new GroupbyNode(ctx.plan.newPID());
+    groupByNode.setInSchema(child.getOutSchema());
+    groupByNode.setOutSchema(PlannerUtil.targetToSchema(targets));
+    return groupByNode;
+  }
+
+  @Override
+  public LogicalNode visitUnion(PreprocessContext ctx, Stack<Expr> stack, SetOperation expr) throws PlanningException {
+    LogicalPlan.QueryBlock leftBlock = ctx.plan.newQueryBlock();
+    PreprocessContext leftContext = new PreprocessContext(ctx, leftBlock);
+    LogicalNode leftChild = visit(leftContext, new Stack<Expr>(), expr.getLeft());
+    ctx.currentBlock.registerExprWithNode(expr.getLeft(), leftChild);
+
+    LogicalPlan.QueryBlock rightBlock = ctx.plan.newQueryBlock();
+    PreprocessContext rightContext = new PreprocessContext(ctx, rightBlock);
+    LogicalNode rightChild = visit(rightContext, new Stack<Expr>(), expr.getRight());
+    ctx.currentBlock.registerExprWithNode(expr.getRight(), rightChild);
+
+    UnionNode unionNode = new UnionNode(ctx.plan.newPID());
+    unionNode.setLeftChild(leftChild);
+    unionNode.setRightChild(rightChild);
+    unionNode.setInSchema(leftChild.getOutSchema());
+    unionNode.setOutSchema(leftChild.getOutSchema());
+
+    return unionNode;
+  }
+
+  public LogicalNode visitFilter(PreprocessContext ctx, Stack<Expr> stack, Selection expr) throws PlanningException {
+    stack.push(expr);
+    LogicalNode child = visit(ctx, stack, expr.getChild());
+    stack.pop();
+
+    SelectionNode selectionNode = new SelectionNode(ctx.plan.newPID());
+    selectionNode.setInSchema(child.getOutSchema());
+    selectionNode.setOutSchema(child.getOutSchema());
+    return selectionNode;
+  }
+
+  @Override
+  public LogicalNode visitJoin(PreprocessContext ctx, Stack<Expr> stack, Join expr) throws PlanningException {
+    stack.push(expr);
+    LogicalNode left = visit(ctx, stack, expr.getLeft());
+    LogicalNode right = visit(ctx, stack, expr.getRight());
+    stack.pop();
+    JoinNode joinNode = new JoinNode(ctx.plan.newPID());
+    joinNode.setJoinType(expr.getJoinType());
+    Schema merged = SchemaUtil.merge(left.getOutSchema(), right.getOutSchema());
+    joinNode.setInSchema(merged);
+    joinNode.setOutSchema(merged);
+
+    ctx.currentBlock.addJoinType(expr.getJoinType());
+    return joinNode;
+  }
+
+  @Override
+  public LogicalNode visitRelation(PreprocessContext ctx, Stack<Expr> stack, Relation expr)
+      throws PlanningException {
+
+    Relation relation = expr;
+    TableDesc desc = catalog.getTableDesc(relation.getName());
+
+    ScanNode scanNode;
+    if (relation.hasAlias()) {
+      scanNode = new ScanNode(ctx.plan.newPID(), desc, relation.getAlias());
+    } else {
+      scanNode = new ScanNode(ctx.plan.newPID(), desc);
+    }
+    ctx.currentBlock.addRelation(scanNode);
+
+    return scanNode;
+  }
+
+  @Override
+  public LogicalNode visitTableSubQuery(PreprocessContext ctx, Stack<Expr> stack, TablePrimarySubQuery expr)
+      throws PlanningException {
+
+    PreprocessContext newContext;
+    // Note: TableSubQuery always has a table name.
+    // SELECT .... FROM (SELECT ...) TB_NAME <-
+    newContext = new PreprocessContext(ctx, ctx.plan.newAndGetBlock(expr.getName()));
+    LogicalNode child = super.visitTableSubQuery(newContext, stack, expr);
+
+    // a table subquery should be dealt as a relation.
+    TableSubQueryNode node = new TableSubQueryNode(ctx.plan.newPID(), expr.getName(), child);
+    ctx.currentBlock.addRelation(node);
+    return node;
+  }
+
+  ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+  // Data Definition Language Section
+  ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+  @Override
+  public LogicalNode visitCreateTable(PreprocessContext ctx, Stack<Expr> stack, CreateTable expr)
+      throws PlanningException {
+
+    CreateTableNode createTableNode = new CreateTableNode(ctx.plan.newPID());
+
+    if (expr.hasSubQuery()) {
+      stack.push(expr);
+      visit(ctx, stack, expr.getSubQuery());
+      stack.pop();
+    }
+
+    return createTableNode;
+  }
+
+  @Override
+  public LogicalNode visitDropTable(PreprocessContext ctx, Stack<Expr> stack, DropTable expr)
+      throws PlanningException {
+    DropTableNode dropTable = new DropTableNode(ctx.plan.newPID());
+    return dropTable;
+  }
+
+  ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+  // Insert or Update Section
+  ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+  public LogicalNode visitInsert(PreprocessContext ctx, Stack<Expr> stack, Insert expr) throws PlanningException {
+    PreprocessContext newContext = new PreprocessContext(ctx, ctx.plan.newQueryBlock());
+    LogicalNode child = super.visitInsert(newContext, stack, expr);
+
+    InsertNode insertNode = new InsertNode(ctx.plan.newPID());
+    insertNode.setInSchema(child.getOutSchema());
+    insertNode.setOutSchema(child.getOutSchema());
+    return insertNode;
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVerifier.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVerifier.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVerifier.java
index e48b655..41e42d0 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVerifier.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVerifier.java
@@ -71,9 +71,6 @@ public class LogicalPlanVerifier extends BasicLogicalPlanVisitor<VerificationSta
       }
     }
 
-    if (node.hasHavingCondition()) {
-      ExprsVerifier.verify(state, node.getHavingCondition());
-    }
     return node;
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8e1f989a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVisitor.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVisitor.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVisitor.java
index 697a8c6..bf41996 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVisitor.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanVisitor.java
@@ -35,6 +35,9 @@ public interface LogicalPlanVisitor<CONTEXT, RESULT> {
   RESULT visitSort(CONTEXT context, LogicalPlan plan, LogicalPlan.QueryBlock block, SortNode node,
                    Stack<LogicalNode> stack) throws PlanningException;
 
+  RESULT visitHaving(CONTEXT context, LogicalPlan plan, LogicalPlan.QueryBlock block, HavingNode node,
+                      Stack<LogicalNode> stack) throws PlanningException;
+
   RESULT visitGroupBy(CONTEXT context, LogicalPlan plan, LogicalPlan.QueryBlock block, GroupbyNode node,
                       Stack<LogicalNode> stack) throws PlanningException;
 


Mime
View raw message