You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tajo.apache.org by hy...@apache.org on 2013/10/11 12:27:40 UTC
[2/2] git commit: TAJO-99: Design the interface of join enumeration
algorithm. (hyunsik)
TAJO-99: Design the interface of join enumeration algorithm. (hyunsik)
Project: http://git-wip-us.apache.org/repos/asf/incubator-tajo/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tajo/commit/517355dc
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tajo/tree/517355dc
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tajo/diff/517355dc
Branch: refs/heads/master
Commit: 517355dc50fec4244bc5a9d5f7fc246cfc6f31a9
Parents: 85b8394
Author: Hyunsik Choi <hy...@apache.org>
Authored: Fri Oct 11 19:27:02 2013 +0900
Committer: Hyunsik Choi <hy...@apache.org>
Committed: Fri Oct 11 19:27:02 2013 +0900
----------------------------------------------------------------------
CHANGES.txt | 2 +
.../java/org/apache/tajo/conf/TajoConf.java | 3 +-
.../main/java/org/apache/tajo/util/TUtil.java | 16 +
.../engine/planner/BasicLogicalPlanVisitor.java | 142 +++++----
.../planner/ExplainLogicalPlanVisitor.java | 88 +++---
.../tajo/engine/planner/LogicalOptimizer.java | 182 +++++++++++-
.../apache/tajo/engine/planner/LogicalPlan.java | 74 ++++-
.../tajo/engine/planner/LogicalPlanVisitor.java | 30 +-
.../tajo/engine/planner/LogicalPlanner.java | 9 +-
.../engine/planner/PhysicalPlannerImpl.java | 11 +-
.../apache/tajo/engine/planner/PlannerUtil.java | 43 +++
.../planner/graph/DirectedGraphCursor.java | 65 +++++
.../tajo/engine/planner/logical/JoinNode.java | 6 +-
.../planner/logical/join/FoundJoinOrder.java | 60 ++++
.../join/GreedyHeuristicJoinOrderAlgorithm.java | 289 +++++++++++++++++++
.../engine/planner/logical/join/JoinEdge.java | 26 +-
.../engine/planner/logical/join/JoinGraph.java | 44 +--
.../logical/join/JoinOrderAlgorithm.java | 34 +++
.../planner/rewrite/FilterPushDownRule.java | 54 ++--
.../planner/rewrite/ProjectionPushDownRule.java | 59 ++--
.../org/apache/tajo/master/GlobalPlanner.java | 102 +++----
.../engine/planner/TestLogicalOptimizer.java | 32 +-
.../apache/tajo/master/TestGlobalPlanner.java | 21 +-
23 files changed, 1096 insertions(+), 296 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index e191aed..55a0087 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -4,6 +4,8 @@ Release 0.2.0 - unreleased
NEW FEATURES
+ TAJO-99: Design the interface of join enumeration algorithm. (hyunsik)
+
TAJO-179: Support MySQL CatalogStore. (jinho)
TAJO-147: Implement trim(text), ltrim(text), and rtrim(text) function.
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-common/src/main/java/org/apache/tajo/conf/TajoConf.java
----------------------------------------------------------------------
diff --git a/tajo-common/src/main/java/org/apache/tajo/conf/TajoConf.java b/tajo-common/src/main/java/org/apache/tajo/conf/TajoConf.java
index f429a26..8c2585e 100644
--- a/tajo-common/src/main/java/org/apache/tajo/conf/TajoConf.java
+++ b/tajo-common/src/main/java/org/apache/tajo/conf/TajoConf.java
@@ -110,8 +110,9 @@ public class TajoConf extends YarnConfiguration {
EXTENAL_SORT_BUFFER_NUM("tajo.sort.external.buffer", 1000000),
BROADCAST_JOIN_THRESHOLD("tajo.join.broadcast.threshold", (long)5 * 1048576),
INMEMORY_HASH_TABLE_DEFAULT_SIZE("tajo.join.inmemory.table.num", (long)1000000),
- INMEMORY_HASH_JOIN_THRESHOLD("tajo.join.memhash, threshold", (long)256 * 1048576),
+ INMEMORY_INNER_HASH_JOIN_THRESHOLD("tajo.join.inner.memhash.threshold", (long)256 * 1048576),
INMEMORY_HASH_AGGREGATION_THRESHOLD("tajo.aggregation.hash.threshold", (long)256 * 1048576),
+ INMEMORY_OUTER_HASH_AGGREGATION_THRESHOLD("tajo.join.outer.memhash.threshold", (long)256 * 1048576),
//////////////////////////////////////////
// Distributed Query Execution Parameters
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-common/src/main/java/org/apache/tajo/util/TUtil.java
----------------------------------------------------------------------
diff --git a/tajo-common/src/main/java/org/apache/tajo/util/TUtil.java b/tajo-common/src/main/java/org/apache/tajo/util/TUtil.java
index 76e9608..5b5a406 100644
--- a/tajo-common/src/main/java/org/apache/tajo/util/TUtil.java
+++ b/tajo-common/src/main/java/org/apache/tajo/util/TUtil.java
@@ -166,6 +166,22 @@ public class TUtil {
}
}
+ public static String collectionToString(Collection objects) {
+ boolean first = false;
+ StringBuilder sb = new StringBuilder();
+ for(Object object : objects) {
+ if (first) {
+ first = false;
+ } else {
+ sb.append(", ");
+ }
+
+ sb.append(object.toString());
+ }
+
+ return sb.toString();
+ }
+
public static String arrayToString(Object [] objects) {
boolean first = false;
StringBuilder sb = new StringBuilder();
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/BasicLogicalPlanVisitor.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/BasicLogicalPlanVisitor.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/BasicLogicalPlanVisitor.java
index 0a564d9..768aeb0 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/BasicLogicalPlanVisitor.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/BasicLogicalPlanVisitor.java
@@ -22,199 +22,213 @@ import org.apache.tajo.engine.planner.logical.*;
import java.util.Stack;
-public class BasicLogicalPlanVisitor<T> implements LogicalPlanVisitor<T> {
+public class BasicLogicalPlanVisitor<CONTEXT, RESULT> implements LogicalPlanVisitor<CONTEXT, RESULT> {
/**
* The prehook is called before each node is visited.
*/
@SuppressWarnings("unused")
- public void preHook(LogicalPlan plan, LogicalNode node, Stack<LogicalNode> stack, T data) throws PlanningException {
+ public void preHook(LogicalPlan plan, LogicalNode node, Stack<LogicalNode> stack, CONTEXT data) throws PlanningException {
}
/**
* The posthook is called after each node is visited.
*/
@SuppressWarnings("unused")
- public void postHook(LogicalPlan plan, LogicalNode node, Stack<LogicalNode> stack, T data)
+ public void postHook(LogicalPlan plan, LogicalNode node, Stack<LogicalNode> stack, CONTEXT data)
throws PlanningException {
}
+ public CONTEXT visit(CONTEXT context, LogicalPlan plan, LogicalPlan.QueryBlock block) throws PlanningException {
+ RESULT result = visitChild(context, plan, block.getRoot(), new Stack<LogicalNode>());
+ return context;
+ }
+
+ public CONTEXT visit(CONTEXT context, LogicalPlan plan, LogicalNode node) throws PlanningException {
+ RESULT result = visitChild(context, plan, node, new Stack<LogicalNode>());
+ return context;
+ }
+
/**
* visitChild visits each logicalNode recursively.
*/
- public LogicalNode visitChild(LogicalPlan plan, LogicalNode node, Stack<LogicalNode> stack, T data)
+ public RESULT visitChild(CONTEXT context, LogicalPlan plan, LogicalNode node, Stack<LogicalNode> stack)
throws PlanningException {
- LogicalNode current;
+ RESULT current;
switch (node.getType()) {
case ROOT:
- current = visitRoot(plan, (LogicalRootNode) node, stack, data);
+ current = visitRoot(context, plan, (LogicalRootNode) node, stack);
break;
case PROJECTION:
- current = visitProjection(plan, (ProjectionNode) node, stack, data);
+ current = visitProjection(context, plan, (ProjectionNode) node, stack);
break;
case LIMIT:
- current = visitLimit(plan, (LimitNode) node, stack, data);
+ current = visitLimit(context, plan, (LimitNode) node, stack);
break;
case SORT:
- current = visitSort(plan, (SortNode) node, stack, data);
+ current = visitSort(context, plan, (SortNode) node, stack);
break;
case GROUP_BY:
- current = visitGroupBy(plan, (GroupbyNode) node, stack, data);
+ current = visitGroupBy(context, plan, (GroupbyNode) node, stack);
break;
case SELECTION:
- current = visitFilter(plan, (SelectionNode) node, stack, data);
+ current = visitFilter(context, plan, (SelectionNode) node, stack);
break;
case JOIN:
- current = visitJoin(plan, (JoinNode) node, stack, data);
+ current = visitJoin(context, plan, (JoinNode) node, stack);
break;
case UNION:
- current = visitUnion(plan, (UnionNode) node, stack, data);
+ current = visitUnion(context, plan, (UnionNode) node, stack);
break;
case EXCEPT:
- current = visitExcept(plan, (ExceptNode) node, stack, data);
+ current = visitExcept(context, plan, (ExceptNode) node, stack);
break;
case INTERSECT:
- current = visitIntersect(plan, (IntersectNode) node, stack, data);
+ current = visitIntersect(context, plan, (IntersectNode) node, stack);
break;
case TABLE_SUBQUERY:
- current = visitTableSubQuery(plan, (TableSubQueryNode) node, stack, data);
+ current = visitTableSubQuery(context, plan, (TableSubQueryNode) node, stack);
break;
case SCAN:
- current = visitScan(plan, (ScanNode) node, stack, data);
+ current = visitScan(context, plan, (ScanNode) node, stack);
break;
case STORE:
- current = visitStoreTable(plan, (StoreTableNode) node, stack, data);
+ current = visitStoreTable(context, plan, (StoreTableNode) node, stack);
+ break;
+ case INSERT:
+ current = visitInsert(context, plan, (InsertNode) node, stack);
break;
default:
- current = node; // nothing to do for others
+ throw new PlanningException("Unknown logical node type: " + node.getType());
}
return current;
}
@Override
- public LogicalNode visitRoot(LogicalPlan plan, LogicalRootNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitRoot(CONTEXT context, LogicalPlan plan, LogicalRootNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitProjection(LogicalPlan plan, ProjectionNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitProjection(CONTEXT context, LogicalPlan plan, ProjectionNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitLimit(LogicalPlan plan, LimitNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitLimit(CONTEXT context, LogicalPlan plan, LimitNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitSort(LogicalPlan plan, SortNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitSort(CONTEXT context, LogicalPlan plan, SortNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitGroupBy(LogicalPlan plan, GroupbyNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitGroupBy(CONTEXT context, LogicalPlan plan, GroupbyNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitFilter(LogicalPlan plan, SelectionNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitFilter(CONTEXT context, LogicalPlan plan, SelectionNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitJoin(LogicalPlan plan, JoinNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitJoin(CONTEXT context, LogicalPlan plan, JoinNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getLeftChild(), stack, context);
- visitChild(plan, node.getRightChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getLeftChild(), stack);
+ visitChild(context, plan, node.getRightChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitUnion(LogicalPlan plan, UnionNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitUnion(CONTEXT context, LogicalPlan plan, UnionNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getLeftChild(), stack, context);
- visitChild(plan, node.getRightChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getLeftChild(), stack);
+ visitChild(context, plan, node.getRightChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitExcept(LogicalPlan plan, ExceptNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitExcept(CONTEXT context, LogicalPlan plan, ExceptNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getLeftChild(), stack, context);
- visitChild(plan, node.getRightChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getLeftChild(), stack);
+ visitChild(context, plan, node.getRightChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitIntersect(LogicalPlan plan, IntersectNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitIntersect(CONTEXT context, LogicalPlan plan, IntersectNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getLeftChild(), stack, context);
- visitChild(plan, node.getRightChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getLeftChild(), stack);
+ visitChild(context, plan, node.getRightChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitTableSubQuery(LogicalPlan plan, TableSubQueryNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitTableSubQuery(CONTEXT context, LogicalPlan plan, TableSubQueryNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getSubQuery(), stack, context);
+ RESULT result = visitChild(context, plan, node.getSubQuery(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitScan(LogicalPlan plan, ScanNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitScan(CONTEXT context, LogicalPlan plan, ScanNode node, Stack<LogicalNode> stack)
throws PlanningException {
- return node;
+ return null;
}
@Override
- public LogicalNode visitStoreTable(LogicalPlan plan, StoreTableNode node, Stack<LogicalNode> stack, T context)
+ public RESULT visitStoreTable(CONTEXT context, LogicalPlan plan, StoreTableNode node, Stack<LogicalNode> stack)
throws PlanningException {
stack.push(node);
- visitChild(plan, node.getChild(), stack, context);
+ RESULT result = visitChild(context, plan, node.getChild(), stack);
stack.pop();
- return node;
+ return result;
}
@Override
- public LogicalNode visitInsert(LogicalPlan plan, InsertNode node, Stack<LogicalNode> stack, T context) throws PlanningException {
+ public RESULT visitInsert(CONTEXT context, LogicalPlan plan, InsertNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
stack.push(node);
- visitChild(plan, node.getSubQuery(), stack, context);
+ RESULT result = visitChild(context, plan, node.getSubQuery(), stack);
stack.pop();
- return node;
+ return result;
}
}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExplainLogicalPlanVisitor.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExplainLogicalPlanVisitor.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExplainLogicalPlanVisitor.java
index ce07d77..cd42b34 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExplainLogicalPlanVisitor.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/ExplainLogicalPlanVisitor.java
@@ -25,7 +25,7 @@ import java.util.Stack;
/**
* It returns a list of node plan strings.
*/
-public class ExplainLogicalPlanVisitor extends BasicLogicalPlanVisitor<ExplainLogicalPlanVisitor.Context> {
+public class ExplainLogicalPlanVisitor extends BasicLogicalPlanVisitor<ExplainLogicalPlanVisitor.Context, LogicalNode> {
public static class Context {
public int maxDepth = -1;
@@ -67,56 +67,56 @@ public class ExplainLogicalPlanVisitor extends BasicLogicalPlanVisitor<ExplainLo
public Context getBlockPlanStrings(LogicalPlan plan, String block) throws PlanningException {
Stack<LogicalNode> stack = new Stack<LogicalNode>();
Context explainContext = new Context();
- visitChild(plan, plan.getBlock(block).getRoot(), stack, explainContext);
+ visitChild(explainContext, plan, plan.getBlock(block).getRoot(), stack);
return explainContext;
}
@Override
- public LogicalNode visitRoot(LogicalPlan plan, LogicalRootNode node, Stack<LogicalNode> stack, Context context)
+ public LogicalNode visitRoot(Context context, LogicalPlan plan, LogicalRootNode node, Stack<LogicalNode> stack)
throws PlanningException {
- return visitChild(plan, node.getChild(), stack, context);
+ return visitChild(context, plan, node.getChild(), stack);
}
@Override
- public LogicalNode visitProjection(LogicalPlan plan, ProjectionNode node, Stack<LogicalNode> stack,
- Context context) throws PlanningException {
- return visitUnaryNode(plan, node, stack, context);
+ public LogicalNode visitProjection(Context context, LogicalPlan plan, ProjectionNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ return visitUnaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitLimit(LogicalPlan plan, LimitNode node, Stack<LogicalNode> stack, Context context)
+ public LogicalNode visitLimit(Context context, LogicalPlan plan, LimitNode node, Stack<LogicalNode> stack)
throws PlanningException {
- return visitUnaryNode(plan, node, stack, context);
+ return visitUnaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitSort(LogicalPlan plan, SortNode node, Stack<LogicalNode> stack,
- Context context) throws PlanningException {
- return visitUnaryNode(plan, node, stack, context);
+ public LogicalNode visitSort(Context context, LogicalPlan plan, SortNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ return visitUnaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitGroupBy(LogicalPlan plan, GroupbyNode node, Stack<LogicalNode> stack,
- Context context) throws PlanningException {
- return visitUnaryNode(plan, node, stack, context);
+ public LogicalNode visitGroupBy(Context context, LogicalPlan plan, GroupbyNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ return visitUnaryNode(context, plan, node, stack);
}
- private LogicalNode visitUnaryNode(LogicalPlan plan, UnaryNode node, Stack<LogicalNode> stack, Context context)
+ private LogicalNode visitUnaryNode(Context context, LogicalPlan plan, UnaryNode node, Stack<LogicalNode> stack)
throws PlanningException {
context.depth++;
stack.push(node);
- visitChild(plan, node.getChild(), stack, context);
+ visitChild(context, plan, node.getChild(), stack);
context.depth--;
context.add(context.depth, node.getPlanString());
return node;
}
- private LogicalNode visitBinaryNode(LogicalPlan plan, BinaryNode node, Stack<LogicalNode> stack, Context context)
+ private LogicalNode visitBinaryNode(Context context, LogicalPlan plan, BinaryNode node, Stack<LogicalNode> stack)
throws PlanningException {
context.depth++;
stack.push(node);
- visitChild(plan, node.getLeftChild(), stack, context);
- visitChild(plan, node.getRightChild(), stack, context);
+ visitChild(context, plan, node.getLeftChild(), stack);
+ visitChild(context, plan, node.getRightChild(), stack);
stack.pop();
context.depth--;
context.add(context.depth, node.getPlanString());
@@ -124,41 +124,41 @@ public class ExplainLogicalPlanVisitor extends BasicLogicalPlanVisitor<ExplainLo
}
@Override
- public LogicalNode visitFilter(LogicalPlan plan, SelectionNode node, Stack<LogicalNode> stack,
- Context context) throws PlanningException {
- return visitUnaryNode(plan, node, stack, context);
+ public LogicalNode visitFilter(Context context, LogicalPlan plan, SelectionNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ return visitUnaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitJoin(LogicalPlan plan, JoinNode node, Stack<LogicalNode> stack, Context context)
- throws PlanningException {
- return visitBinaryNode(plan, node, stack, context);
+ public LogicalNode visitJoin(Context context, LogicalPlan plan, JoinNode node, Stack<LogicalNode> stack) throws
+ PlanningException {
+ return visitBinaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitUnion(LogicalPlan plan, UnionNode node, Stack<LogicalNode> stack,
- Context context) throws PlanningException {
- return visitBinaryNode(plan, node, stack, context);
+ public LogicalNode visitUnion(Context context, LogicalPlan plan, UnionNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ return visitBinaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitExcept(LogicalPlan plan, ExceptNode node, Stack<LogicalNode> stack,
- Context context) throws PlanningException {
- return visitBinaryNode(plan, node, stack, context);
+ public LogicalNode visitExcept(Context context, LogicalPlan plan, ExceptNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ return visitBinaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitIntersect(LogicalPlan plan, IntersectNode node, Stack<LogicalNode> stack,
- Context context) throws PlanningException {
- return visitBinaryNode(plan, node, stack, context);
+ public LogicalNode visitIntersect(Context context, LogicalPlan plan, IntersectNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ return visitBinaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitTableSubQuery(LogicalPlan plan, TableSubQueryNode node, Stack<LogicalNode> stack,
- Context context) throws PlanningException {
+ public LogicalNode visitTableSubQuery(Context context, LogicalPlan plan, TableSubQueryNode node,
+ Stack<LogicalNode> stack) throws PlanningException {
context.depth++;
stack.push(node);
- super.visitTableSubQuery(plan, node, stack, context);
+ super.visitTableSubQuery(context, plan, node, stack);
stack.pop();
context.depth--;
context.add(context.depth, node.getPlanString());
@@ -167,22 +167,24 @@ public class ExplainLogicalPlanVisitor extends BasicLogicalPlanVisitor<ExplainLo
}
@Override
- public LogicalNode visitScan(LogicalPlan plan, ScanNode node, Stack<LogicalNode> stack, Context context)
+ public LogicalNode visitScan(Context context, LogicalPlan plan, ScanNode node, Stack<LogicalNode> stack)
throws PlanningException {
context.add(context.depth, node.getPlanString());
return node;
}
@Override
- public LogicalNode visitStoreTable(LogicalPlan plan, StoreTableNode node, Stack<LogicalNode> stack, Context context) throws PlanningException {
- return visitUnaryNode(plan, node, stack, context);
+ public LogicalNode visitStoreTable(Context context, LogicalPlan plan, StoreTableNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ return visitUnaryNode(context, plan, node, stack);
}
@Override
- public LogicalNode visitInsert(LogicalPlan plan, InsertNode node, Stack<LogicalNode> stack, Context context) throws PlanningException {
+ public LogicalNode visitInsert(Context context, LogicalPlan plan, InsertNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
context.depth++;
stack.push(node);
- visitChild(plan, node.getSubQuery(), stack, context);
+ visitChild(context, plan, node.getSubQuery(), stack);
stack.pop();
context.depth--;
context.add(context.depth, node.getPlanString());
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/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 06cd6b9..943ca6f 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
@@ -18,17 +18,36 @@
package org.apache.tajo.engine.planner;
-import org.apache.tajo.engine.planner.logical.LogicalNode;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+import org.apache.hadoop.classification.InterfaceStability;
+import org.apache.tajo.engine.eval.EvalNode;
+import org.apache.tajo.engine.eval.EvalTreeUtil;
+import org.apache.tajo.engine.planner.graph.DirectedGraphCursor;
+import org.apache.tajo.engine.planner.logical.*;
+import org.apache.tajo.engine.planner.logical.join.FoundJoinOrder;
+import org.apache.tajo.engine.planner.logical.join.GreedyHeuristicJoinOrderAlgorithm;
+import org.apache.tajo.engine.planner.logical.join.JoinGraph;
+import org.apache.tajo.engine.planner.logical.join.JoinOrderAlgorithm;
import org.apache.tajo.engine.planner.rewrite.BasicQueryRewriteEngine;
import org.apache.tajo.engine.planner.rewrite.FilterPushDownRule;
import org.apache.tajo.engine.planner.rewrite.ProjectionPushDownRule;
+import java.util.Collection;
+import java.util.Set;
+import java.util.Stack;
+
+import static org.apache.tajo.engine.planner.LogicalPlan.BlockEdge;
+import static org.apache.tajo.engine.planner.logical.join.GreedyHeuristicJoinOrderAlgorithm.getCost;
+
/**
* This class optimizes a logical plan.
*/
+@InterfaceStability.Evolving
public class LogicalOptimizer {
private BasicQueryRewriteEngine rulesBeforeJoinOpt;
private BasicQueryRewriteEngine rulesAfterToJoinOpt;
+ private JoinOrderAlgorithm joinOrderAlgorithm = new GreedyHeuristicJoinOrderAlgorithm();
public LogicalOptimizer() {
rulesBeforeJoinOpt = new BasicQueryRewriteEngine();
@@ -40,7 +59,168 @@ public class LogicalOptimizer {
public LogicalNode optimize(LogicalPlan plan) throws PlanningException {
rulesBeforeJoinOpt.rewrite(plan);
+
+ DirectedGraphCursor<String, BlockEdge> blockCursor =
+ new DirectedGraphCursor<String, BlockEdge>(plan.getQueryBlockGraph(), plan.getRootBlock().getName());
+
+ while(blockCursor.hasNext()) {
+ optimizeJoinOrder(plan, blockCursor.nextBlock());
+ }
+
rulesAfterToJoinOpt.rewrite(plan);
return plan.getRootBlock().getRoot();
}
+
+ private void optimizeJoinOrder(LogicalPlan plan, String blockName) throws PlanningException {
+ LogicalPlan.QueryBlock block = plan.getBlock(blockName);
+
+ if (block.hasJoinNode()) {
+ String originalOrder = JoinOrderStringBuilder.buildJoinOrderString(plan, block);
+ double nonOptimizedJoinCost = JoinCostComputer.computeCost(plan, block);
+
+ // finding relations and filter expressions
+ JoinGraphContext joinGraphContext = JoinGraphBuilder.buildJoinGraph(plan, block);
+
+ // finding join order and restore remain filter order
+ FoundJoinOrder order = joinOrderAlgorithm.findBestOrder(plan, block,
+ joinGraphContext.joinGraph, joinGraphContext.quals, joinGraphContext.relationsWithoutQual);
+ block.setJoinNode(order.getOrderedJoin());
+
+ String optimizedOrder = JoinOrderStringBuilder.buildJoinOrderString(plan, block);
+
+ block.addHistory("Non-optimized join order: " + originalOrder + " (cost: " + nonOptimizedJoinCost + ")");
+ block.addHistory("Optimized join order : " + optimizedOrder + " (cost: " + order.getCost() + ")");
+ }
+ }
+
+ private static class JoinGraphContext {
+ JoinGraph joinGraph = new JoinGraph();
+ Set<EvalNode> quals = Sets.newHashSet();
+ Set<String> relationsWithoutQual = Sets.newHashSet();
+ }
+
+ private static class JoinGraphBuilder extends BasicLogicalPlanVisitor<JoinGraphContext, LogicalNode> {
+ private final static JoinGraphBuilder instance;
+
+ static {
+ instance = new JoinGraphBuilder();
+ }
+
+ public static JoinGraphContext buildJoinGraph(LogicalPlan plan, LogicalPlan.QueryBlock block)
+ throws PlanningException {
+ JoinGraphContext joinGraphContext = new JoinGraphContext();
+ instance.visit(joinGraphContext, plan, block);
+ return joinGraphContext;
+ }
+
+ public LogicalNode visitFilter(JoinGraphContext context, LogicalPlan plan, SelectionNode node,
+ Stack<LogicalNode> stack) throws PlanningException {
+ super.visitFilter(context, plan, node, stack);
+ context.quals.addAll(Lists.newArrayList(EvalTreeUtil.getConjNormalForm(node.getQual())));
+ return node;
+ }
+
+ @Override
+ public LogicalNode visitJoin(JoinGraphContext joinGraphContext, LogicalPlan plan, JoinNode joinNode,
+ Stack<LogicalNode> stack)
+ throws PlanningException {
+ super.visitJoin(joinGraphContext, plan, joinNode, stack);
+ if (joinNode.hasJoinQual()) {
+ Collection<EvalNode> nonJoinQual =
+ joinGraphContext.joinGraph.addJoin(joinNode.getJoinType(), joinNode.getJoinQual());
+ joinGraphContext.quals.addAll(nonJoinQual);
+ } else {
+ LogicalNode leftChild = joinNode.getLeftChild();
+ if (leftChild instanceof RelationNode) {
+ RelationNode rel = (RelationNode) leftChild;
+ joinGraphContext.relationsWithoutQual.add(rel.getCanonicalName());
+ }
+ }
+ return joinNode;
+ }
+ }
+
+ public static class JoinOrderStringBuilder extends BasicLogicalPlanVisitor<StringBuilder, LogicalNode> {
+ private static final JoinOrderStringBuilder instance;
+ static {
+ instance = new JoinOrderStringBuilder();
+ }
+
+ public static JoinOrderStringBuilder getInstance() {
+ return instance;
+ }
+
+ public static String buildJoinOrderString(LogicalPlan plan, LogicalPlan.QueryBlock block) throws PlanningException {
+ StringBuilder originalOrder = new StringBuilder();
+ instance.visit(originalOrder, plan, block);
+ return originalOrder.toString();
+ }
+
+ @Override
+ public LogicalNode visitJoin(StringBuilder sb, LogicalPlan plan, JoinNode joinNode,
+ Stack<LogicalNode> stack)
+ throws PlanningException {
+ stack.push(joinNode);
+ sb.append("(");
+ visitChild(sb, plan, joinNode.getLeftChild(), stack);
+ sb.append(",");
+ visitChild(sb, plan, joinNode.getRightChild(), stack);
+ sb.append(")");
+ stack.pop();
+ return joinNode;
+ }
+
+ @Override
+ public LogicalNode visitTableSubQuery(StringBuilder sb, LogicalPlan plan, TableSubQueryNode node,
+ Stack<LogicalNode> stack) {
+ sb.append(node.getTableName());
+ return node;
+ }
+
+ public LogicalNode visitScan(StringBuilder sb, LogicalPlan plan, ScanNode node, Stack<LogicalNode> stack) {
+ sb.append(node.getTableName());
+ return node;
+ }
+ }
+
+ private static class CostContext {
+ double accumulatedCost = 0;
+ }
+
+ public static class JoinCostComputer extends BasicLogicalPlanVisitor<CostContext, LogicalNode> {
+ private static final JoinCostComputer instance;
+
+ static {
+ instance = new JoinCostComputer();
+ }
+
+ public static double computeCost(LogicalPlan plan, LogicalPlan.QueryBlock block) throws PlanningException {
+ CostContext costContext = new CostContext();
+ instance.visit(costContext, plan, block);
+ return costContext.accumulatedCost;
+ }
+
+ @Override
+ public LogicalNode visitJoin(CostContext joinGraphContext, LogicalPlan plan, JoinNode joinNode,
+ Stack<LogicalNode> stack)
+ throws PlanningException {
+ super.visitJoin(joinGraphContext, plan, joinNode, stack);
+
+ double filterFactor = 1;
+ if (joinNode.hasJoinQual()) {
+ EvalNode [] quals = EvalTreeUtil.getConjNormalForm(joinNode.getJoinQual());
+ filterFactor = Math.pow(GreedyHeuristicJoinOrderAlgorithm.DEFAULT_SELECTION_FACTOR, quals.length);
+ }
+
+ if (joinNode.getLeftChild() instanceof RelationNode) {
+ joinGraphContext.accumulatedCost = getCost(joinNode.getLeftChild()) * getCost(joinNode.getRightChild())
+ * filterFactor;
+ } else {
+ joinGraphContext.accumulatedCost = joinGraphContext.accumulatedCost +
+ (joinGraphContext.accumulatedCost * getCost(joinNode.getRightChild()) * filterFactor);
+ }
+
+ return joinNode;
+ }
+ }
}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/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 fb628d9..395a9e2 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
@@ -18,13 +18,14 @@
package org.apache.tajo.engine.planner;
-import com.google.common.collect.Maps;
+import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
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.planner.graph.DirectedGraphCursor;
import org.apache.tajo.engine.planner.graph.SimpleDirectedGraph;
import org.apache.tajo.engine.planner.logical.*;
import org.apache.tajo.util.TUtil;
@@ -53,6 +54,9 @@ public class LogicalPlan {
private Map<Integer, QueryBlock> queryBlockByPID = new HashMap<Integer, QueryBlock>();
private SimpleDirectedGraph<String, BlockEdge> queryBlockGraph = new SimpleDirectedGraph<String, BlockEdge>();
+ /** planning and optimization log */
+ private List<String> planingHistory = Lists.newArrayList();
+
public LogicalPlan(LogicalPlanner planner) {
this.planner = planner;
}
@@ -252,12 +256,24 @@ public class LogicalPlan {
public String getQueryGraphAsString() {
StringBuilder sb = new StringBuilder();
- sb.append("-----------------------------\n");
+ sb.append("\n-----------------------------\n");
sb.append("Query Block Graph\n");
sb.append("-----------------------------\n");
sb.append(queryBlockGraph.toStringGraph(getRootBlock().getName()));
sb.append("-----------------------------\n");
-
+ sb.append("Optimization Log:\n");
+ DirectedGraphCursor<String, BlockEdge> cursor =
+ new DirectedGraphCursor<String, BlockEdge>(queryBlockGraph, getRootBlock().getName());
+ while(cursor.hasNext()) {
+ QueryBlock block = getBlock(cursor.nextBlock());
+ if (block.getPlaningHistory().size() > 0) {
+ sb.append("\n[").append(block.getName()).append("]\n");
+ for (String log : block.getPlaningHistory()) {
+ sb.append("> ").append(log).append("\n");
+ }
+ }
+ }
+ sb.append("-----------------------------\n");
sb.append("\n");
sb.append(getLogicalPlanAsString());
@@ -282,6 +298,14 @@ public class LogicalPlan {
return explains.toString();
}
+ public void addHistory(String string) {
+ planingHistory.add(string);
+ }
+
+ public List<String> getHistory() {
+ return planingHistory;
+ }
+
@Override
public String toString() {
return getQueryGraphAsString();
@@ -338,6 +362,7 @@ public class LogicalPlan {
private boolean hasGrouping;
private Projectable projectionNode;
private GroupbyNode groupingNode;
+ private JoinNode joinNode;
private SelectionNode selectionNode;
private StoreTableNode storeTableNode;
private InsertNode insertNode;
@@ -345,6 +370,9 @@ public class LogicalPlan {
TargetListManager targetListManager;
+ /** It contains a planning log for this block */
+ private List<String> planingHistory = Lists.newArrayList();
+
public QueryBlock(String blockName) {
this.blockName = blockName;
}
@@ -370,8 +398,8 @@ public class LogicalPlan {
queryBlockByPID.put(blockRoot.getPID(), this);
}
- public <T extends LogicalNode> T getRoot() {
- return (T) rootNode;
+ public <NODE extends LogicalNode> NODE getRoot() {
+ return (NODE) rootNode;
}
public NodeType getRootType() {
@@ -406,7 +434,7 @@ public class LogicalPlan {
return this.relations.size() > 0;
}
- public void setLatestNode(LogicalNode node) {
+ public void updateLatestNode(LogicalNode node) {
this.latestNode = node;
}
@@ -487,6 +515,25 @@ public class LogicalPlan {
return this.groupingNode;
}
+ public boolean hasJoinNode() {
+ return joinNode != null;
+ }
+
+ /**
+ * @return the topmost JoinNode instance
+ */
+ 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;
}
@@ -523,12 +570,21 @@ public class LogicalPlan {
this.insertNode = insertNode;
}
+ public List<String> getPlaningHistory() {
+ return planingHistory;
+ }
+
+ public void addHistory(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()) {
@@ -546,6 +602,10 @@ public class LogicalPlan {
setGroupbyNode((GroupbyNode) node);
break;
+ case JOIN:
+ setJoinNode((JoinNode) node);
+ break;
+
case SELECTION:
setSelectionNode((SelectionNode) node);
break;
@@ -560,8 +620,6 @@ public class LogicalPlan {
break;
}
- setLatestNode(node);
-
// if this node is the topmost
if (path.size() == 0) {
setRoot(node);
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/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 d0a1cf6..e05b09b 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
@@ -22,33 +22,33 @@ import org.apache.tajo.engine.planner.logical.*;
import java.util.Stack;
-public interface LogicalPlanVisitor <CONTEXT> {
- LogicalNode visitRoot(LogicalPlan plan, LogicalRootNode node, Stack<LogicalNode> stack, CONTEXT context)
+public interface LogicalPlanVisitor <CONTEXT, RESULT> {
+ RESULT visitRoot(CONTEXT context, LogicalPlan plan, LogicalRootNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitProjection(LogicalPlan plan, ProjectionNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitProjection(CONTEXT context, LogicalPlan plan, ProjectionNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitLimit(LogicalPlan plan, LimitNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitLimit(CONTEXT context, LogicalPlan plan, LimitNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitSort(LogicalPlan plan, SortNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitSort(CONTEXT context, LogicalPlan plan, SortNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitGroupBy(LogicalPlan plan, GroupbyNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitGroupBy(CONTEXT context, LogicalPlan plan, GroupbyNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitFilter(LogicalPlan plan, SelectionNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitFilter(CONTEXT context, LogicalPlan plan, SelectionNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitJoin(LogicalPlan plan, JoinNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitJoin(CONTEXT context, LogicalPlan plan, JoinNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitUnion(LogicalPlan plan, UnionNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitUnion(CONTEXT context, LogicalPlan plan, UnionNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitExcept(LogicalPlan plan, ExceptNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitExcept(CONTEXT context, LogicalPlan plan, ExceptNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitIntersect(LogicalPlan plan, IntersectNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitIntersect(CONTEXT context, LogicalPlan plan, IntersectNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitTableSubQuery(LogicalPlan plan, TableSubQueryNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitTableSubQuery(CONTEXT context, LogicalPlan plan, TableSubQueryNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitScan(LogicalPlan plan, ScanNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitScan(CONTEXT context, LogicalPlan plan, ScanNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitStoreTable(LogicalPlan plan, StoreTableNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitStoreTable(CONTEXT context, LogicalPlan plan, StoreTableNode node, Stack<LogicalNode> stack)
throws PlanningException;
- LogicalNode visitInsert(LogicalPlan plan, InsertNode node, Stack<LogicalNode> stack, CONTEXT context)
+ RESULT visitInsert(CONTEXT context, LogicalPlan plan, InsertNode node, Stack<LogicalNode> stack)
throws PlanningException;
}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanner.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanner.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanner.java
index d083ac1..38f045f 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanner.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/LogicalPlanner.java
@@ -23,6 +23,7 @@ import com.google.common.collect.Lists;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.fs.ContentSummary;
import org.apache.hadoop.fs.FileStatus;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
@@ -183,10 +184,14 @@ public class LogicalPlanner extends BaseAlgebraVisitor<LogicalPlanner.PlanContex
FileSystem fs = desc.getPath().getFileSystem(new Configuration());
FileStatus status = fs.getFileStatus(desc.getPath());
if (desc.getMeta().getStat() != null && (status.isDirectory() || status.isFile())) {
- desc.getMeta().getStat().setNumBytes(fs.getContentSummary(desc.getPath()).getLength());
+ ContentSummary summary = fs.getContentSummary(desc.getPath());
+ if (summary != null) {
+ long volume = summary.getLength();
+ desc.getMeta().getStat().setNumBytes(volume);
+ }
}
} catch (Throwable t) {
- t.printStackTrace();
+ LOG.warn(t);
}
}
}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PhysicalPlannerImpl.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PhysicalPlannerImpl.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PhysicalPlannerImpl.java
index 14514a9..a64eecf 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PhysicalPlannerImpl.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PhysicalPlannerImpl.java
@@ -57,9 +57,6 @@ public class PhysicalPlannerImpl implements PhysicalPlanner {
protected final TajoConf conf;
protected final AbstractStorageManager sm;
- final long threshold = 1048576 * 128; // 64MB
-
-
public PhysicalPlannerImpl(final TajoConf conf, final AbstractStorageManager sm) {
this.conf = conf;
this.sm = sm;
@@ -295,7 +292,7 @@ public class PhysicalPlannerImpl implements PhysicalPlanner {
long leftSize = estimateSizeRecursive(context, leftLineage);
long rightSize = estimateSizeRecursive(context, rightLineage);
- final long threshold = conf.getLongVar(TajoConf.ConfVars.INMEMORY_HASH_JOIN_THRESHOLD);
+ final long threshold = conf.getLongVar(TajoConf.ConfVars.INMEMORY_INNER_HASH_JOIN_THRESHOLD);
boolean hashJoin = false;
if (leftSize < threshold || rightSize < threshold) {
@@ -366,7 +363,7 @@ public class PhysicalPlannerImpl implements PhysicalPlanner {
String [] rightLineage = PlannerUtil.getLineage(plan.getRightChild());
long rightTableVolume = estimateSizeRecursive(context, rightLineage);
- if (rightTableVolume < threshold) {
+ if (rightTableVolume < conf.getLongVar(TajoConf.ConfVars.INMEMORY_OUTER_HASH_AGGREGATION_THRESHOLD)) {
// we can implement left outer join using hash join, using the right operand as the build relation
LOG.info("Left Outer Join (" + plan.getPID() +") chooses [Hash Join].");
return new HashLeftOuterJoinExec(context, plan, leftExec, rightExec);
@@ -383,8 +380,8 @@ public class PhysicalPlannerImpl implements PhysicalPlanner {
//if the left operand is small enough => implement it as a left outer hash join with exchanged operators (note:
// blocking, but merge join is blocking as well)
String [] outerLineage4 = PlannerUtil.getLineage(plan.getLeftChild());
- long outerSize4 = estimateSizeRecursive(context, outerLineage4);
- if (outerSize4 < threshold){
+ long outerSize = estimateSizeRecursive(context, outerLineage4);
+ if (outerSize < conf.getLongVar(TajoConf.ConfVars.INMEMORY_OUTER_HASH_AGGREGATION_THRESHOLD)){
LOG.info("Right Outer Join (" + plan.getPID() +") chooses [Hash Join].");
return new HashLeftOuterJoinExec(context, plan, rightExec, leftExec);
} else {
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PlannerUtil.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PlannerUtil.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PlannerUtil.java
index 7bef3b9..e224328 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PlannerUtil.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/PlannerUtil.java
@@ -95,6 +95,49 @@ public class PlannerUtil {
}
return child;
}
+
+ public static void replaceNode(LogicalPlan plan, LogicalNode startNode, LogicalNode oldNode, LogicalNode newNode) {
+ LogicalNodeReplaceVisitor replacer = new LogicalNodeReplaceVisitor(oldNode, newNode);
+ try {
+ replacer.visit(null, plan, startNode);
+ } catch (PlanningException e) {
+ e.printStackTrace();
+ }
+ }
+
+ public static class LogicalNodeReplaceVisitor extends BasicLogicalPlanVisitor<Object, LogicalNode> {
+ private LogicalNode target;
+ private LogicalNode tobeReplaced;
+
+ public LogicalNodeReplaceVisitor(LogicalNode target, LogicalNode tobeReplaced) {
+ this.target = target;
+ this.tobeReplaced = tobeReplaced;
+ }
+
+ @Override
+ public LogicalNode visitChild(Object context, LogicalPlan plan, LogicalNode node, Stack<LogicalNode> stack)
+ throws PlanningException {
+ super.visitChild(context, plan, node, stack);
+
+ if (node.equals(target)) {
+ LogicalNode parent = stack.peek();
+
+ if (parent instanceof BinaryNode) {
+ BinaryNode binaryParent = (BinaryNode) parent;
+ if (binaryParent.getLeftChild().equals(target)) {
+ binaryParent.setLeftChild(tobeReplaced);
+ }
+ if (binaryParent.getRightChild().equals(target)) {
+ binaryParent.setRightChild(tobeReplaced);
+ }
+ } else if (parent instanceof UnaryNode) {
+ UnaryNode unaryParent = (UnaryNode) parent;
+ unaryParent.setChild(tobeReplaced);
+ }
+ }
+ return node;
+ }
+ }
public static void replaceNode(LogicalNode plan, LogicalNode newNode, NodeType type) {
LogicalNode parent = findTopParentNode(plan, type);
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraphCursor.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraphCursor.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraphCursor.java
new file mode 100644
index 0000000..7db9b83
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraphCursor.java
@@ -0,0 +1,65 @@
+/**
+ * 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.graph;
+
+import java.util.ArrayList;
+
+public class DirectedGraphCursor<V,E> {
+ private DirectedGraph<V,E> graph;
+ private ArrayList<V> orderedVertices = new ArrayList<V>();
+ private int cursor = 0;
+
+ public DirectedGraphCursor(DirectedGraph<V, E> graph, V startVertex) {
+ this.graph = graph;
+ buildOrder(startVertex);
+ }
+
+ public int size() {
+ return orderedVertices.size();
+ }
+
+ private void buildOrder(V current) {
+ if (!graph.isLeaf(current)) {
+ for (V child : graph.getChilds(current)) {
+ buildOrder(child);
+ }
+ }
+ orderedVertices.add(current);
+ }
+
+ public boolean hasNext() {
+ return cursor < orderedVertices.size();
+ }
+
+ public V nextBlock() {
+ return orderedVertices.get(cursor++);
+ }
+
+ public V peek() {
+ return orderedVertices.get(cursor);
+ }
+
+ public V peek(int skip) {
+ return orderedVertices.get(cursor + skip);
+ }
+
+ public void reset() {
+ cursor = 0;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/JoinNode.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/JoinNode.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/JoinNode.java
index 5d81379..520415b 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/JoinNode.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/JoinNode.java
@@ -32,8 +32,12 @@ public class JoinNode extends BinaryNode implements Projectable, Cloneable {
@Expose private EvalNode joinQual;
@Expose private Target[] targets;
- public JoinNode(int pid, JoinType joinType) {
+ public JoinNode(int pid) {
super(pid, NodeType.JOIN);
+ }
+
+ public JoinNode(int pid, JoinType joinType) {
+ this(pid);
this.joinType = joinType;
}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/FoundJoinOrder.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/FoundJoinOrder.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/FoundJoinOrder.java
new file mode 100644
index 0000000..a50d44f
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/FoundJoinOrder.java
@@ -0,0 +1,60 @@
+/**
+ * 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.logical.join;
+
+import org.apache.hadoop.classification.InterfaceStability;
+import org.apache.tajo.engine.eval.EvalNode;
+import org.apache.tajo.engine.planner.logical.JoinNode;
+
+/**
+ * It contains the result of join enumeration.
+ */
+@InterfaceStability.Evolving
+public class FoundJoinOrder {
+ private JoinNode joinNode;
+ private EvalNode[] quals;
+ private double cost;
+
+ public FoundJoinOrder(JoinNode joinNode, EvalNode[] quals, double cost) {
+ this.joinNode = joinNode;
+ this.quals = quals;
+ this.cost = cost;
+ }
+
+ /**
+ * @return a ordered join operators
+ */
+ public JoinNode getOrderedJoin() {
+ return this.joinNode;
+ }
+
+ public double getCost() {
+ return cost;
+ }
+
+ /**
+ * The search conditions contained in where clause are pushed down into join operators.
+ * This method returns the remain search conditions except for pushed down condition.
+ *
+ * @return the remain search conditions
+ */
+ public EvalNode [] getRemainConditions() {
+ return this.quals;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/GreedyHeuristicJoinOrderAlgorithm.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/GreedyHeuristicJoinOrderAlgorithm.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/GreedyHeuristicJoinOrderAlgorithm.java
new file mode 100644
index 0000000..05d7e19
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/GreedyHeuristicJoinOrderAlgorithm.java
@@ -0,0 +1,289 @@
+/**
+ * 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.logical.join;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Maps;
+import org.apache.tajo.algebra.JoinType;
+import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.engine.eval.EvalNode;
+import org.apache.tajo.engine.eval.EvalTreeUtil;
+import org.apache.tajo.engine.planner.LogicalPlan;
+import org.apache.tajo.engine.planner.logical.JoinNode;
+import org.apache.tajo.engine.planner.logical.LogicalNode;
+import org.apache.tajo.engine.planner.logical.RelationNode;
+import org.apache.tajo.engine.planner.logical.ScanNode;
+import org.apache.tajo.engine.utils.SchemaUtil;
+import org.apache.tajo.util.TUtil;
+
+import java.util.*;
+
+/**
+ * This is a greedy heuristic algorithm to find a left-deep join tree. This algorithm finds
+ * the best join order with join conditions and pushes down join conditions to
+ * all join operators.
+ */
+public class GreedyHeuristicJoinOrderAlgorithm implements JoinOrderAlgorithm {
+ public static double DEFAULT_SELECTION_FACTOR = 0.1;
+
+ @Override
+ public FoundJoinOrder findBestOrder(LogicalPlan plan, LogicalPlan.QueryBlock block, JoinGraph joinGraph,
+ Set<EvalNode> qualSet, Set<String> relationsWithoutQual) {
+
+ // Build a map (a relation name -> a relation object)
+ // initialize a relation set
+ HashMap<String, RelationNode> relationMap = Maps.newHashMap();
+ // Remain relation set to be joined
+ Set<String> remainRelNames = new HashSet<String>();
+ for (RelationNode relation : block.getRelations()) {
+ RelationNode rel = relation;
+ relationMap.put(rel.getCanonicalName(), rel);
+ remainRelNames.add(rel.getCanonicalName());
+ }
+ // A set of already-joined relations
+ Set<String> alreadyJoinedRelNames = new HashSet<String>();
+
+ // Get candidates from all relations to be joined
+ List<RelationNode> candidates = getSmallerRelations(relationMap, remainRelNames);
+
+ LogicalNode lastOne = candidates.get(0); // Get the first candidate relation (i.e., smallest)
+ remainRelNames.remove(((RelationNode)lastOne).getCanonicalName()); // Remove the first candidate relation
+
+ // Add the first candidate to the set of joined relations
+ alreadyJoinedRelNames.add(((RelationNode)lastOne).getCanonicalName());
+
+ List<CandidateJoinNode> orderedJoins;
+ CandidateJoinNode chosen = null;
+ while(true) {
+ // Get a set of relations that can be joined to the composite relation.
+ Set<CandidateJoin> joinCandidates = new HashSet<CandidateJoin>();
+ for (String currentRel : alreadyJoinedRelNames) {
+ // find all relations that can be joined to this relation
+ Collection<JoinEdge> edges = joinGraph.getJoinsWith(currentRel);
+
+ if (edges.size() > 0) { // if there are available join quals
+ for (JoinEdge edge : edges) {
+ if (alreadyJoinedRelNames.contains(edge.getLeftRelation())
+ && currentRel.contains(edge.getRightRelation())) { // if two relations are already joined
+ continue;
+ }
+
+ if (!alreadyJoinedRelNames.contains(edge.getLeftRelation())) {
+ joinCandidates.add(new CandidateJoin(edge.getLeftRelation(), edge)) ;
+ }
+ if (!alreadyJoinedRelNames.contains(edge.getRightRelation())) {
+ joinCandidates.add(new CandidateJoin(edge.getRightRelation(), edge));
+ }
+ }
+ } else {
+ for (RelationNode rel : block.getRelations()) {
+ // Add all relations except for itself to join candidates
+ if (!currentRel.equals(rel.getCanonicalName())) {
+ joinCandidates.add(new CandidateJoin(rel.getCanonicalName(),
+ new JoinEdge(JoinType.CROSS, currentRel, rel.getCanonicalName())));
+ }
+ }
+ }
+ }
+
+ // Get a ranked candidates from the set of relations that can be joined
+ orderedJoins = getBestJoinRelations(relationMap, lastOne, joinCandidates);
+
+ // Get a candidate relation such that the candidate incurs the smallest intermediate and is
+ // not join to any relation yet.
+
+ for (int i = 0; i < orderedJoins.size(); i++) {
+ chosen = orderedJoins.get(i);
+ if (remainRelNames.contains(chosen.getRelation().getCanonicalName())) {
+ break;
+ }
+ }
+
+ // Set the candidate to a inner relation and remove from the relation set.
+ JoinNode lastJoinNode = new JoinNode(plan.newPID(), chosen.getJoinType());
+ lastJoinNode.setLeftChild(lastOne); // Set the first candidate to a left relation of the first join
+ lastJoinNode.setRightChild(chosen.getRelation());
+
+ Schema merged = SchemaUtil.merge(lastJoinNode.getLeftChild().getOutSchema(),
+ lastJoinNode.getRightChild().getOutSchema());
+ lastJoinNode.setInSchema(merged);
+ lastJoinNode.setOutSchema(merged);
+
+ if (chosen.hasJoinQual()) {
+ lastJoinNode.setJoinQual(EvalTreeUtil.transformCNF2Singleton(chosen.getJoinQual()));
+ for (EvalNode joinCondition : chosen.getJoinQual()) {
+ qualSet.remove(joinCondition);
+ }
+ }
+ lastJoinNode.setCost(getCost(chosen));
+ alreadyJoinedRelNames.add(chosen.getRelation().getCanonicalName());
+ remainRelNames.remove(chosen.getRelation().getCanonicalName());
+ lastOne = lastJoinNode;
+
+ // If the relation set is empty, stop this loop.
+ if (remainRelNames.isEmpty()) {
+ Preconditions.checkState(qualSet.isEmpty(), "Not all join conditions are pushed down to joins.");
+ break;
+ }
+ }
+
+ return new FoundJoinOrder((JoinNode) lastOne, qualSet.toArray(new EvalNode[qualSet.size()]), getCost(chosen));
+ }
+
+ private class CandidateJoin {
+ final JoinEdge edge;
+ final String relationName;
+
+ public CandidateJoin(String rightRelation, JoinEdge edge) {
+ this.relationName = rightRelation;
+ this.edge = edge;
+ }
+
+ public String getRelationName() {
+ return relationName;
+ }
+
+ public JoinEdge getEdge() {
+ return edge;
+ }
+
+ public String toString() {
+ return edge.toString();
+ }
+ }
+
+ private class CandidateJoinNode {
+ final LogicalNode relOrJoin;
+ final RelationNode rel;
+ final JoinEdge joinEdge;
+
+ public CandidateJoinNode(LogicalNode relOrJoin, RelationNode relation, JoinEdge joinEdge) {
+ this.relOrJoin = relOrJoin;
+ this.rel = relation;
+ this.joinEdge = joinEdge;
+ }
+
+ public LogicalNode getRelationOrJoin() {
+ return relOrJoin;
+ }
+
+ public RelationNode getRelation() {
+ return rel;
+ }
+
+ public JoinType getJoinType() {
+ return joinEdge.getJoinType();
+ }
+
+ public boolean hasJoinQual() {
+ return joinEdge.hasJoinQual() && joinEdge.getJoinQual().length > 0;
+ }
+
+ public EvalNode [] getJoinQual() {
+ return joinEdge.getJoinQual();
+ }
+
+ public String toString() {
+ StringBuilder sb = new StringBuilder(rel.getCanonicalName());
+ if (hasJoinQual()) {
+ sb.append("with ").append(TUtil.arrayToString(joinEdge.getJoinQual()));
+ }
+ return sb.toString();
+ }
+ }
+
+ private List<RelationNode> getSmallerRelations(Map<String, RelationNode> map, Set<String> relationSet) {
+ List<RelationNode> relations = new ArrayList<RelationNode>();
+ for (String name : relationSet) {
+ relations.add(map.get(name));
+ }
+ Collections.sort(relations, new RelationOpComparator());
+ return relations;
+ }
+
+ private List<CandidateJoinNode> getBestJoinRelations(Map<String, RelationNode> map,
+ LogicalNode lastJoin,
+ Set<CandidateJoin> candidateJoins) {
+ List<CandidateJoinNode> relations = new ArrayList<CandidateJoinNode>();
+ for (CandidateJoin candidate : candidateJoins) {
+ relations.add(new CandidateJoinNode(lastJoin, map.get(candidate.getRelationName()), candidate.getEdge()));
+ }
+ Collections.sort(relations, new CandidateJoinOpComparator());
+ return relations;
+ }
+
+ public static double getCost(LogicalNode node) {
+ if (node instanceof ScanNode) {
+ ScanNode scanNode = (ScanNode) node;
+ if (scanNode.getTableDesc().getMeta().getStat() != null) {
+ return ((ScanNode)node).getTableDesc().getMeta().getStat().getNumBytes();
+ } else {
+ return Long.MAX_VALUE;
+ }
+ } else {
+ return node.getCost();
+ }
+ }
+
+ /** it assumes that left-deep join tree. */
+ public static double getCost(LogicalNode left, LogicalNode right, EvalNode [] quals) {
+ double filterFactor = 1;
+ if (quals != null) {
+ filterFactor = Math.pow(DEFAULT_SELECTION_FACTOR, quals.length);
+ }
+
+ if (left instanceof RelationNode) {
+ return getCost(left) * getCost(right) * filterFactor;
+ } else {
+ return getCost(left)
+ + (getCost(left) * getCost(right) * filterFactor);
+ }
+ }
+
+ private double getCost(CandidateJoinNode join) {
+ return getCost(join.getRelationOrJoin(), join.getRelation(), join.getJoinQual());
+ }
+
+ class RelationOpComparator implements Comparator<RelationNode> {
+ @Override
+ public int compare(RelationNode o1, RelationNode o2) {
+ if (getCost(o1) < getCost(o2)) {
+ return -1;
+ } else if (getCost(o1) > getCost(o2)) {
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+ }
+
+ class CandidateJoinOpComparator implements Comparator<CandidateJoinNode> {
+ @Override
+ public int compare(CandidateJoinNode o1, CandidateJoinNode o2) {
+ double cmp = getCost(o1) - getCost(o2);
+ if (cmp < 0) {
+ return -1;
+ } else if (getCost(o1.getRelation()) > getCost(o2.getRelation())) {
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinEdge.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinEdge.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinEdge.java
index d1cdab7..844bbf2 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinEdge.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinEdge.java
@@ -18,20 +18,28 @@
package org.apache.tajo.engine.planner.logical.join;
+import com.google.common.collect.Sets;
import org.apache.tajo.algebra.JoinType;
import org.apache.tajo.engine.eval.EvalNode;
+import org.apache.tajo.util.TUtil;
import java.util.Collections;
import java.util.Set;
public class JoinEdge {
- private JoinType joinType;
- private String leftRelation;
- private String rightRelation;
- private Set<EvalNode> joinQual;
+ private final JoinType joinType;
+ private final String leftRelation;
+ private final String rightRelation;
+ private final Set<EvalNode> joinQual = Sets.newHashSet();
- public JoinEdge(JoinType joinType, String leftRelation, String rightRelation, EvalNode ... condition) {
+ public JoinEdge(JoinType joinType, String leftRelation, String rightRelation) {
this.joinType = joinType;
+ this.leftRelation = leftRelation;
+ this.rightRelation = rightRelation;
+ }
+
+ public JoinEdge(JoinType joinType, String leftRelation, String rightRelation, EvalNode ... condition) {
+ this(joinType, leftRelation, rightRelation);
Collections.addAll(joinQual, condition);
}
@@ -47,6 +55,10 @@ public class JoinEdge {
return rightRelation;
}
+ public boolean hasJoinQual() {
+ return joinQual != null;
+ }
+
public void addJoinQual(EvalNode joinQual) {
this.joinQual.add(joinQual);
}
@@ -54,4 +66,8 @@ public class JoinEdge {
public EvalNode [] getJoinQual() {
return joinQual.toArray(new EvalNode[joinQual.size()]);
}
+
+ public String toString() {
+ return leftRelation + " " + joinType + " " + rightRelation + " ON " + TUtil.collectionToString(joinQual);
+ }
}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinGraph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinGraph.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinGraph.java
index e07140b..2e600ba 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinGraph.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinGraph.java
@@ -18,6 +18,7 @@
package org.apache.tajo.engine.planner.logical.join;
+import com.google.common.collect.Sets;
import org.apache.tajo.algebra.JoinType;
import org.apache.tajo.catalog.Column;
import org.apache.tajo.engine.eval.EvalNode;
@@ -27,36 +28,37 @@ import org.apache.tajo.engine.planner.graph.SimpleUndirectedGraph;
import java.util.Collection;
import java.util.List;
+import java.util.Set;
public class JoinGraph extends SimpleUndirectedGraph<String, JoinEdge> {
- public Collection<JoinEdge> getJoinsFrom(String relation) {
+ public Collection<JoinEdge> getJoinsWith(String relation) {
return getEdges(relation);
}
- public void addJoin(EvalNode condition) {
- List<Column> left = EvalTreeUtil.findAllColumnRefs(condition.getLeftExpr());
- List<Column> right = EvalTreeUtil.findAllColumnRefs(condition.getRightExpr());
+ public Collection<EvalNode> addJoin(JoinType joinType, EvalNode joinQual) {
+ Set<EvalNode> cnf = Sets.newHashSet(EvalTreeUtil.getConjNormalForm(joinQual));
+ Set<EvalNode> nonJoinQuals = Sets.newHashSet();
+ for (EvalNode singleQual : cnf) {
+ if (PlannerUtil.isJoinQual(singleQual)) {
+ List<Column> left = EvalTreeUtil.findAllColumnRefs(singleQual.getLeftExpr());
+ List<Column> right = EvalTreeUtil.findAllColumnRefs(singleQual.getRightExpr());
- String leftRelName = left.get(0).getQualifier();
- String rightRelName = right.get(0).getQualifier();
+ String leftRelName = left.get(0).getQualifier();
+ String rightRelName = right.get(0).getQualifier();
- JoinEdge edge = getEdge(leftRelName, rightRelName);
+ JoinEdge edge = getEdge(leftRelName, rightRelName);
- if (edge != null) {
- edge.addJoinQual(condition);
- } else {
- edge = new JoinEdge(JoinType.INNER, leftRelName, rightRelName, condition);
- addEdge(leftRelName, rightRelName, edge);
- }
- }
-
- public static JoinGraph createJoinGraph(EvalNode [] cnf) {
- JoinGraph joinGraph = new JoinGraph();
- for (EvalNode expr : cnf) {
- if (PlannerUtil.isJoinQual(expr)) {
- joinGraph.addJoin(expr);
+ if (edge != null) {
+ edge.addJoinQual(singleQual);
+ } else {
+ edge = new JoinEdge(joinType, leftRelName, rightRelName, singleQual);
+ addEdge(leftRelName, rightRelName, edge);
+ }
+ } else {
+ nonJoinQuals.add(singleQual);
}
}
- return joinGraph;
+ cnf.retainAll(nonJoinQuals);
+ return cnf;
}
}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java
new file mode 100644
index 0000000..b34c1ac
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java
@@ -0,0 +1,34 @@
+/**
+ * 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.logical.join;
+
+import org.apache.hadoop.classification.InterfaceStability;
+import org.apache.tajo.engine.eval.EvalNode;
+import org.apache.tajo.engine.planner.LogicalPlan;
+
+import java.util.Set;
+
+/**
+ * An interface for join order algorithms
+ */
+@InterfaceStability.Evolving
+public interface JoinOrderAlgorithm {
+ FoundJoinOrder findBestOrder(LogicalPlan plan, LogicalPlan.QueryBlock block, JoinGraph joinGraph,
+ Set<EvalNode> joinQuals, Set<String> relationsWithoutQual);
+}
http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/517355dc/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java
index 22bcd06..ae0e25b 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java
@@ -19,9 +19,13 @@
package org.apache.tajo.engine.planner.rewrite;
import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
import org.apache.tajo.algebra.JoinType;
+import org.apache.tajo.catalog.Column;
import org.apache.tajo.engine.eval.EvalNode;
import org.apache.tajo.engine.eval.EvalTreeUtil;
+import org.apache.tajo.engine.eval.EvalType;
+import org.apache.tajo.engine.eval.FieldEval;
import org.apache.tajo.engine.planner.BasicLogicalPlanVisitor;
import org.apache.tajo.engine.planner.LogicalPlan;
import org.apache.tajo.engine.planner.PlannerUtil;
@@ -29,17 +33,9 @@ import org.apache.tajo.engine.planner.PlanningException;
import org.apache.tajo.engine.planner.logical.*;
import org.apache.tajo.engine.query.exception.InvalidQueryException;
-import org.apache.tajo.engine.eval.EvalType;
-import org.apache.tajo.engine.eval.FieldEval;
-import org.apache.tajo.catalog.Column;
-import com.google.common.collect.Sets;
-import java.util.Set;
-import java.util.Iterator;
-
-import java.util.List;
-import java.util.Stack;
+import java.util.*;
-public class FilterPushDownRule extends BasicLogicalPlanVisitor<List<EvalNode>> implements RewriteRule {
+public class FilterPushDownRule extends BasicLogicalPlanVisitor<Set<EvalNode>, LogicalNode> implements RewriteRule {
private static final String NAME = "FilterPushDown";
@Override
@@ -50,7 +46,7 @@ public class FilterPushDownRule extends BasicLogicalPlanVisitor<List<EvalNode>>
@Override
public boolean isEligible(LogicalPlan plan) {
for (LogicalPlan.QueryBlock block : plan.getQueryBlocks()) {
- if (PlannerUtil.findTopNode(block.getRoot(), NodeType.SELECTION) != null) {
+ if (block.hasSelectionNode() || block.hasJoinNode()) {
return true;
}
}
@@ -60,21 +56,19 @@ public class FilterPushDownRule extends BasicLogicalPlanVisitor<List<EvalNode>>
@Override
public LogicalPlan rewrite(LogicalPlan plan) throws PlanningException {
for (LogicalPlan.QueryBlock block : plan.getQueryBlocks()) {
- if (block.hasSelectionNode()) {
- SelectionNode filterNode = block.getSelectionNode();
- Stack<LogicalNode> stack = new Stack<LogicalNode>();
- EvalNode [] cnf = EvalTreeUtil.getConjNormalForm(filterNode.getQual());
- visitChild(plan, block.getRoot(), stack, Lists.newArrayList(cnf));
- }
+ this.visit(new HashSet<EvalNode>(), plan, block.getRoot());
}
return plan;
}
- public LogicalNode visitFilter(LogicalPlan plan, SelectionNode selNode, Stack<LogicalNode> stack, List<EvalNode> cnf)
+ @Override
+ public LogicalNode visitFilter(Set<EvalNode> cnf, LogicalPlan plan, SelectionNode selNode, Stack<LogicalNode> stack)
throws PlanningException {
+ cnf.addAll(Sets.newHashSet(EvalTreeUtil.getConjNormalForm(selNode.getQual())));
+
stack.push(selNode);
- visitChild(plan, selNode.getChild(), stack, cnf);
+ visitChild(cnf, plan, selNode.getChild(), stack);
stack.pop();
// remove the selection operator if there is no search condition
@@ -96,7 +90,8 @@ public class FilterPushDownRule extends BasicLogicalPlanVisitor<List<EvalNode>>
return joinType == JoinType.LEFT_OUTER || joinType == JoinType.RIGHT_OUTER || joinType==JoinType.FULL_OUTER;
}
- public LogicalNode visitJoin(LogicalPlan plan, JoinNode joinNode, Stack<LogicalNode> stack, List<EvalNode> cnf)
+ @Override
+ public LogicalNode visitJoin(Set<EvalNode> cnf, LogicalPlan plan, JoinNode joinNode, Stack<LogicalNode> stack)
throws PlanningException {
LogicalNode left = joinNode.getRightChild();
LogicalNode right = joinNode.getLeftChild();
@@ -198,8 +193,12 @@ public class FilterPushDownRule extends BasicLogicalPlanVisitor<List<EvalNode>>
}
}
- visitChild(plan, left, stack, cnf);
- visitChild(plan, right, stack, cnf);
+ if (joinNode.hasJoinQual()) {
+ cnf.addAll(Sets.newHashSet(EvalTreeUtil.getConjNormalForm(joinNode.getJoinQual())));
+ }
+
+ visitChild(cnf, plan, left, stack);
+ visitChild(cnf, plan, right, stack);
List<EvalNode> matched = Lists.newArrayList();
for (EvalNode eval : cnf) {
@@ -219,12 +218,8 @@ public class FilterPushDownRule extends BasicLogicalPlanVisitor<List<EvalNode>>
}
if (qual != null) {
- if (joinNode.hasJoinQual()) {
- EvalNode conjQual = EvalTreeUtil.transformCNF2Singleton(joinNode.getJoinQual(), qual);
- joinNode.setJoinQual(conjQual);
- } else {
- joinNode.setJoinQual(qual);
- }
+ joinNode.setJoinQual(qual);
+
if (joinNode.getJoinType() == JoinType.CROSS) {
joinNode.setJoinType(JoinType.INNER);
}
@@ -234,7 +229,8 @@ public class FilterPushDownRule extends BasicLogicalPlanVisitor<List<EvalNode>>
return joinNode;
}
- public LogicalNode visitScan(LogicalPlan plan, ScanNode scanNode, Stack<LogicalNode> stack, List<EvalNode> cnf)
+ @Override
+ public LogicalNode visitScan(Set<EvalNode> cnf, LogicalPlan plan, ScanNode scanNode, Stack<LogicalNode> stack)
throws PlanningException {
List<EvalNode> matched = Lists.newArrayList();