tajo-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hyun...@apache.org
Subject git commit: TAJO-229: Implement JoinGraph to represent a graph of relation joins. (hyunsik)
Date Fri, 04 Oct 2013 12:20:31 GMT
Updated Branches:
  refs/heads/master b9baf526f -> 8b872bc17


TAJO-229: Implement JoinGraph to represent a graph of relation joins. (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/8b872bc1
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tajo/tree/8b872bc1
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tajo/diff/8b872bc1

Branch: refs/heads/master
Commit: 8b872bc17f9c7dfffdfd44d4c5717e37113ec804
Parents: b9baf52
Author: Hyunsik Choi <hyunsik@apache.org>
Authored: Fri Oct 4 21:20:06 2013 +0900
Committer: Hyunsik Choi <hyunsik@apache.org>
Committed: Fri Oct 4 21:20:06 2013 +0900

----------------------------------------------------------------------
 CHANGES.txt                                     |  3 +
 .../org/apache/tajo/catalog/TestDDLBuilder.java | 48 ----------
 .../org/apache/tajo/annotation/NotNull.java     | 25 +++++
 .../org/apache/tajo/annotation/Nullable.java    |  5 +-
 .../tajo/engine/planner/LogicalOptimizer.java   | 14 +--
 .../apache/tajo/engine/planner/LogicalPlan.java |  2 +-
 .../tajo/engine/planner/LogicalPlanner.java     |  4 +-
 .../tajo/engine/planner/global/MasterPlan.java  | 10 +-
 .../engine/planner/graph/DirectedGraph.java     | 33 +++----
 .../apache/tajo/engine/planner/graph/Graph.java | 45 +++++++++
 .../planner/graph/SimpleDirectedGraph.java      | 51 +++++++----
 .../planner/graph/SimpleUndirectedGraph.java    | 92 +++++++++++++++++++
 .../engine/planner/graph/UndirectedGraph.java   | 30 ++++++
 .../tajo/engine/planner/logical/BinaryNode.java |  3 -
 .../tajo/engine/planner/logical/JoinNode.java   |  6 +-
 .../engine/planner/logical/join/JoinEdge.java   | 57 ++++++++++++
 .../engine/planner/logical/join/JoinGraph.java  | 62 +++++++++++++
 .../engine/planner/logical/join/JoinTree.java   | 95 -------------------
 .../tajo/master/TajoMasterClientService.java    |  1 -
 .../master/querymaster/QueryMasterTask.java     |  1 -
 .../org/apache/tajo/client/TestDDLBuilder.java  | 49 ++++++++++
 .../planner/TestGenericDirectedGraph.java       | 73 ---------------
 .../tajo/engine/planner/TestLogicalPlan.java    |  4 +-
 .../engine/planner/TestSimpleDirectedGraph.java | 79 ++++++++++++++++
 .../planner/TestSimpleUndirectedGraph.java      | 96 ++++++++++++++++++++
 .../tajo/storage/AbstractStorageManager.java    |  2 -
 26 files changed, 614 insertions(+), 276 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index 3632870..2f16735 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -43,6 +43,9 @@ Release 0.2.0 - unreleased
 
   IMPROVEMENTS
 
+    TAJO-229: Implement JoinGraph to represent a graph of relation joins.
+    (hyunsik)
+
     TAJO-223: Maximize disk read bandwidth utilization of StorageManagerV2 by
     moving Tuple creation role to next(). (Keuntae Park via hyunsik)
 

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-catalog/tajo-catalog-common/src/test/java/org/apache/tajo/catalog/TestDDLBuilder.java
----------------------------------------------------------------------
diff --git a/tajo-catalog/tajo-catalog-common/src/test/java/org/apache/tajo/catalog/TestDDLBuilder.java b/tajo-catalog/tajo-catalog-common/src/test/java/org/apache/tajo/catalog/TestDDLBuilder.java
deleted file mode 100644
index 876abb4..0000000
--- a/tajo-catalog/tajo-catalog-common/src/test/java/org/apache/tajo/catalog/TestDDLBuilder.java
+++ /dev/null
@@ -1,48 +0,0 @@
-/**
- * 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.catalog;
-
-import org.apache.hadoop.fs.Path;
-import org.apache.hadoop.io.compress.GzipCodec;
-import org.apache.tajo.catalog.proto.CatalogProtos;
-import org.apache.tajo.common.TajoDataTypes;
-import org.apache.tajo.util.FileUtil;
-import org.junit.Test;
-
-import java.io.File;
-
-import static org.junit.Assert.assertEquals;
-
-
-public class TestDDLBuilder {
-  @Test
-  public void testBuildDDL() throws Exception {
-    Schema schema = new Schema();
-    schema.addColumn("name", TajoDataTypes.Type.BLOB);
-    schema.addColumn("addr", TajoDataTypes.Type.TEXT);
-    TableMeta meta = CatalogUtil.newTableMeta(schema, CatalogProtos.StoreType.CSV);
-    meta.putOption("csv.delimiter", "|");
-    meta.putOption(TableMeta.COMPRESSION_CODEC, GzipCodec.class.getName());
-
-
-    TableDesc desc = new TableDescImpl("table1", meta, new Path("/table1"));
-
-    assertEquals(FileUtil.readTextFile(new File("src/test/results/testBuildDDL.result")), DDLBuilder.buildDDL(desc));
-  }
-}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-common/src/main/java/org/apache/tajo/annotation/NotNull.java
----------------------------------------------------------------------
diff --git a/tajo-common/src/main/java/org/apache/tajo/annotation/NotNull.java b/tajo-common/src/main/java/org/apache/tajo/annotation/NotNull.java
new file mode 100644
index 0000000..880f768
--- /dev/null
+++ b/tajo-common/src/main/java/org/apache/tajo/annotation/NotNull.java
@@ -0,0 +1,25 @@
+/**
+ * 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.annotation;
+
+@java.lang.annotation.Documented
+@java.lang.annotation.Retention(java.lang.annotation.RetentionPolicy.RUNTIME)
+@java.lang.annotation.Target({java.lang.annotation.ElementType.PARAMETER, java.lang.annotation.ElementType.FIELD})
+public @interface NotNull {
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-common/src/main/java/org/apache/tajo/annotation/Nullable.java
----------------------------------------------------------------------
diff --git a/tajo-common/src/main/java/org/apache/tajo/annotation/Nullable.java b/tajo-common/src/main/java/org/apache/tajo/annotation/Nullable.java
index d6a757d..0c5ef98 100644
--- a/tajo-common/src/main/java/org/apache/tajo/annotation/Nullable.java
+++ b/tajo-common/src/main/java/org/apache/tajo/annotation/Nullable.java
@@ -18,8 +18,11 @@
 
 package org.apache.tajo.annotation;
 
+import java.lang.annotation.ElementType;
+
 @java.lang.annotation.Documented
 @java.lang.annotation.Retention(java.lang.annotation.RetentionPolicy.RUNTIME)
-@java.lang.annotation.Target({java.lang.annotation.ElementType.PARAMETER, java.lang.annotation.ElementType.FIELD})
+@java.lang.annotation.Target({java.lang.annotation.ElementType.PARAMETER, java.lang.annotation.ElementType.FIELD,
+    ElementType.METHOD})
 public @interface Nullable {
 }

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/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 dcd4fca..06cd6b9 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
@@ -27,18 +27,20 @@ import org.apache.tajo.engine.planner.rewrite.ProjectionPushDownRule;
  * This class optimizes a logical plan.
  */
 public class LogicalOptimizer {
-  private BasicQueryRewriteEngine rewriteEngine;
+  private BasicQueryRewriteEngine rulesBeforeJoinOpt;
+  private BasicQueryRewriteEngine rulesAfterToJoinOpt;
 
   public LogicalOptimizer() {
-    rewriteEngine = new BasicQueryRewriteEngine();
+    rulesBeforeJoinOpt = new BasicQueryRewriteEngine();
+    rulesBeforeJoinOpt.addRewriteRule(new FilterPushDownRule());
 
-    rewriteEngine.addRewriteRule(new FilterPushDownRule());
-    rewriteEngine.addRewriteRule(new ProjectionPushDownRule());
+    rulesAfterToJoinOpt = new BasicQueryRewriteEngine();
+    rulesAfterToJoinOpt.addRewriteRule(new ProjectionPushDownRule());
   }
 
   public LogicalNode optimize(LogicalPlan plan) throws PlanningException {
-    rewriteEngine.rewrite(plan);
-
+    rulesBeforeJoinOpt.rewrite(plan);
+    rulesAfterToJoinOpt.rewrite(plan);
     return plan.getRootBlock().getRoot();
   }
 }
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/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 ebe8de5..adb8d66 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
@@ -112,7 +112,7 @@ public class LogicalPlan {
   }
 
   public void connectBlocks(QueryBlock srcBlock, QueryBlock targetBlock, BlockType type) {
-    queryBlockGraph.connect(srcBlock.getName(), targetBlock.getName(), new BlockEdge(srcBlock, targetBlock, type));
+    queryBlockGraph.addEdge(srcBlock.getName(), targetBlock.getName(), new BlockEdge(srcBlock, targetBlock, type));
   }
 
   public QueryBlock getParentBlock(QueryBlock block) {

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/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 49f7e53..8906349 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
@@ -29,8 +29,6 @@ import org.apache.hadoop.fs.Path;
 import org.apache.tajo.algebra.*;
 import org.apache.tajo.algebra.CreateTable.ColumnDefinition;
 import org.apache.tajo.catalog.*;
-import org.apache.tajo.engine.function.AggFunction;
-import org.apache.tajo.engine.function.GeneralFunction;
 import org.apache.tajo.catalog.proto.CatalogProtos;
 import org.apache.tajo.common.TajoDataTypes;
 import org.apache.tajo.common.TajoDataTypes.DataType;
@@ -38,6 +36,8 @@ import org.apache.tajo.datum.Datum;
 import org.apache.tajo.datum.DatumFactory;
 import org.apache.tajo.datum.NullDatum;
 import org.apache.tajo.engine.eval.*;
+import org.apache.tajo.engine.function.AggFunction;
+import org.apache.tajo.engine.function.GeneralFunction;
 import org.apache.tajo.engine.planner.LogicalPlan.QueryBlock;
 import org.apache.tajo.engine.planner.logical.*;
 import org.apache.tajo.engine.query.exception.InvalidQueryException;

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/global/MasterPlan.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/global/MasterPlan.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/global/MasterPlan.java
index 6d30d00..35b62c9 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/global/MasterPlan.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/global/MasterPlan.java
@@ -107,7 +107,7 @@ public class MasterPlan {
   }
 
   public void addConnect(DataChannel dataChannel) {
-    execBlockGraph.connect(dataChannel.getSrcId(), dataChannel.getTargetId(), dataChannel);
+    execBlockGraph.addEdge(dataChannel.getSrcId(), dataChannel.getTargetId(), dataChannel);
   }
 
   public void addConnect(ExecutionBlock src, ExecutionBlock target, PartitionType type) {
@@ -123,15 +123,15 @@ public class MasterPlan {
   }
 
   public boolean isConnected(ExecutionBlockId src, ExecutionBlockId target) {
-    return execBlockGraph.isConnected(src, target);
+    return execBlockGraph.hasEdge(src, target);
   }
 
   public boolean isReverseConnected(ExecutionBlock target, ExecutionBlock src) {
-    return execBlockGraph.isReversedConnected(target.getId(), src.getId());
+    return execBlockGraph.hasReversedEdge(target.getId(), src.getId());
   }
 
   public boolean isReverseConnected(ExecutionBlockId target, ExecutionBlockId src) {
-    return execBlockGraph.isReversedConnected(target, src);
+    return execBlockGraph.hasReversedEdge(target, src);
   }
 
   public DataChannel getChannel(ExecutionBlock src, ExecutionBlock target) {
@@ -167,7 +167,7 @@ public class MasterPlan {
   }
 
   public void disconnect(ExecutionBlockId src, ExecutionBlockId target) {
-    execBlockGraph.disconnect(src, target);
+    execBlockGraph.removeEdge(src, target);
   }
 
   public ExecutionBlock getParent(ExecutionBlock executionBlock) {

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraph.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraph.java
index df428bb..b6ff71b 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraph.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/DirectedGraph.java
@@ -18,6 +18,8 @@
 
 package org.apache.tajo.engine.planner.graph;
 
+import org.apache.tajo.annotation.Nullable;
+
 import java.util.List;
 
 /**
@@ -26,37 +28,30 @@ import java.util.List;
  * @param <V> The vertex class type
  * @param <E> The edge class type
  */
-public interface DirectedGraph<V, E> {
-
-  int size();
-
-  void connect(V tail, V head, E edge);
-
-  void disconnect(V tail, V head);
+public interface DirectedGraph<V, E> extends Graph<V, E> {
 
-  boolean isConnected(V tail, V head);
-
-  boolean isReversedConnected(V head, V tail);
-
-  E getEdge(V tail, V head);
+  boolean hasReversedEdge(V head, V tail);
 
   E getReverseEdge(V head, V tail);
 
-  int getChildCount(V v);
-
   List<E> getIncomingEdges(V head);
 
   List<E> getOutgoingEdges(V tail);
 
-  List<V> getChilds(V v);
+  /////////////////////////////////
+  // belows are tree features
+  /////////////////////////////////
+  boolean isRoot(V v);
 
-  V getChild(V block, int idx);
+  boolean isLeaf(V v);
 
-  V getParent(V v);
+  @Nullable V getParent(V v);
 
-  boolean isRoot(V v);
+  int getChildCount(V v);
 
-  boolean isLeaf(V v);
+  @Nullable V getChild(V block, int idx);
+
+  List<V> getChilds(V v);
 
   /**
    * It visits all vertices in a post-order traverse way.

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/Graph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/Graph.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/Graph.java
new file mode 100644
index 0000000..d380b94
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/Graph.java
@@ -0,0 +1,45 @@
+/**
+ * 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 org.apache.tajo.annotation.Nullable;
+
+import java.util.Collection;
+
+/**
+ * This is the topmost graph interface. It only provides essential graph features.
+ * @param <V> Vertex class
+ * @param <E> Edge Class
+ */
+
+public interface Graph<V, E> {
+  int getVertexSize();
+
+  int getEdgeNum();
+
+  void addEdge(V tail, V head, E edge);
+
+  void removeEdge(V tail, V head);
+
+  boolean hasEdge(V tail, V head);
+
+  @Nullable E getEdge(V tail, V head);
+
+  Collection<E> getEdgesAll();
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleDirectedGraph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleDirectedGraph.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleDirectedGraph.java
index 3bc360f..12f33cb 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleDirectedGraph.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleDirectedGraph.java
@@ -19,12 +19,11 @@
 package org.apache.tajo.engine.planner.graph;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
+import org.apache.tajo.annotation.Nullable;
 import org.apache.tajo.util.TUtil;
 
-import java.util.ArrayList;
-import java.util.List;
-import java.util.Map;
-import java.util.Stack;
+import java.util.*;
 
 /**
  * This represents a simple directed graph. It does not support multiple edges between both vertices.
@@ -34,23 +33,33 @@ import java.util.Stack;
  */
 public class SimpleDirectedGraph<V, E> implements DirectedGraph<V,E> {
   /** map: child -> parent */
-  private Map<V, Map<V, E>> directedEdges = TUtil.newLinkedHashMap();
+  protected Map<V, Map<V, E>> directedEdges = TUtil.newLinkedHashMap();
   /** map: parent -> child */
-  private Map<V, Map<V, E>> reversedEdges = TUtil.newLinkedHashMap();
+  protected Map<V, Map<V, E>> reversedEdges = TUtil.newLinkedHashMap();
 
   @Override
-  public int size() {
+  public int getVertexSize() {
     return directedEdges.size();
   }
 
   @Override
-  public void connect(V tail, V head, E edge) {
+  public int getEdgeNum() {
+    int edgeNum = 0;
+    for (Map<V, E> map : directedEdges.values()) {
+      edgeNum += map.values().size();
+    }
+
+    return edgeNum;
+  }
+
+  @Override
+  public void addEdge(V tail, V head, E edge) {
     TUtil.putToNestedMap(directedEdges, tail, head, edge);
     TUtil.putToNestedMap(reversedEdges, head, tail, edge);
   }
 
   @Override
-  public void disconnect(V tail, V head) {
+  public void removeEdge(V tail, V head) {
     if (directedEdges.containsKey(tail)) {
       directedEdges.get(tail).remove(head);
       if (directedEdges.get(tail).isEmpty()) {
@@ -67,18 +76,18 @@ public class SimpleDirectedGraph<V, E> implements DirectedGraph<V,E> {
   }
 
   @Override
-  public boolean isConnected(V tail, V head) {
+  public boolean hasEdge(V tail, V head) {
     return directedEdges.containsKey(tail) && directedEdges.get(tail).containsKey(head);
   }
 
   @Override
-  public boolean isReversedConnected(V head, V tail) {
+  public boolean hasReversedEdge(V head, V tail) {
     return reversedEdges.containsKey(head) && reversedEdges.get(head).containsKey(tail);
   }
 
   @Override
-  public E getEdge(V tail, V head) {
-    if (isConnected(tail, head)) {
+  public @Nullable E getEdge(V tail, V head) {
+    if (hasEdge(tail, head)) {
       return directedEdges.get(tail).get(head);
     } else {
       return null;
@@ -86,8 +95,9 @@ public class SimpleDirectedGraph<V, E> implements DirectedGraph<V,E> {
   }
 
   @Override
-  public E getReverseEdge(V head, V tail) {
-    if (isReversedConnected(head, tail)) {
+  public @Nullable
+  E getReverseEdge(V head, V tail) {
+    if (hasReversedEdge(head, tail)) {
       return reversedEdges.get(head).get(tail);
     } else {
       return null;
@@ -95,6 +105,15 @@ public class SimpleDirectedGraph<V, E> implements DirectedGraph<V,E> {
   }
 
   @Override
+  public Collection<E> getEdgesAll() {
+    List<E> edges = Lists.newArrayList();
+    for (Map<V, E> map : directedEdges.values()) {
+      edges.addAll(map.values());
+    }
+    return edges;
+  }
+
+  @Override
   public int getChildCount(V v) {
     if (reversedEdges.containsKey(v)) {
       return reversedEdges.get(v).size();
@@ -138,7 +157,7 @@ public class SimpleDirectedGraph<V, E> implements DirectedGraph<V,E> {
   }
 
   @Override
-  public V getParent(V v) {
+  public @Nullable V getParent(V v) {
     if (directedEdges.containsKey(v)) {
       return directedEdges.get(v).keySet().iterator().next();
     } else {

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleUndirectedGraph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleUndirectedGraph.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleUndirectedGraph.java
new file mode 100644
index 0000000..38a025d
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/SimpleUndirectedGraph.java
@@ -0,0 +1,92 @@
+/**
+ * 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 com.google.common.collect.Lists;
+import org.apache.tajo.annotation.Nullable;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * This implementation is based on a directed graph implementation. Each edge is connected in bidirection
+ * between two vertices.
+ *
+ * @param <V> Vertex Class
+ * @param <E> Edge Class
+ */
+public class SimpleUndirectedGraph<V, E> extends SimpleDirectedGraph<V, E> implements UndirectedGraph<V, E> {
+
+  @Override
+  public @Nullable E getEdge(V tail, V head) {
+    E edge = super.getEdge(tail, head);
+    if (edge != null) {
+      return edge;
+    }
+    edge = super.getEdge(head, tail);
+    if (edge != null) {
+      return edge;
+    }
+    return null;
+  }
+
+  @Override
+  public Collection<E> getEdges(V v) {
+    List<E> edges = Lists.newArrayList();
+    List<E> outgoingEdges = getOutgoingEdges(v);
+    if (outgoingEdges != null) {
+      edges.addAll(outgoingEdges);
+    }
+    List<E> incomingEdges = getIncomingEdges(v);
+    if (incomingEdges != null) {
+      edges.addAll(incomingEdges);
+    }
+    return edges;
+  }
+
+  @Override
+  public int getDegree(V v) {
+    return getEdges(v).size();
+  }
+
+  @Override
+  public Collection<E> getEdgesAll() {
+    List<E> edges = Lists.newArrayList();
+    for (Map<V, E> map : directedEdges.values()) {
+      edges.addAll(map.values());
+    }
+    return edges;
+  }
+
+  @Override
+  public V getParent(V v) {
+    throw new UnsupportedOperationException("Cannot support getParent(V v) in UndirectedGraph");
+  }
+
+  @Override
+  public boolean isRoot(V v) {
+    throw new UnsupportedOperationException("Cannot support isRoot(V v) in UndirectedGraph");
+  }
+
+  @Override
+  public boolean isLeaf(V v) {
+    throw new UnsupportedOperationException("Cannot support isLeaf(V v) in UndirectedGraph");
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/UndirectedGraph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/UndirectedGraph.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/UndirectedGraph.java
new file mode 100644
index 0000000..7f74cd1
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/graph/UndirectedGraph.java
@@ -0,0 +1,30 @@
+/**
+ * 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 org.apache.tajo.annotation.NotNull;
+
+import java.util.Collection;
+
+public interface UndirectedGraph<V, E> extends Graph<V, E> {
+  Collection<E> getEdges(@NotNull V v);
+
+  int getDegree(@NotNull V v);
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/BinaryNode.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/BinaryNode.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/BinaryNode.java
index 37b0fdf..fad06a3 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/BinaryNode.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/BinaryNode.java
@@ -16,9 +16,6 @@
  * limitations under the License.
  */
 
-/**
- * 
- */
 package org.apache.tajo.engine.planner.logical;
 
 import com.google.gson.annotations.Expose;

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/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 58214ac..5d81379 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,9 +32,13 @@ public class JoinNode extends BinaryNode implements Projectable, Cloneable {
   @Expose private EvalNode joinQual;
   @Expose private Target[] targets;
 
-  public JoinNode(int pid, JoinType joinType, LogicalNode left) {
+  public JoinNode(int pid, JoinType joinType) {
     super(pid, NodeType.JOIN);
     this.joinType = joinType;
+  }
+
+  public JoinNode(int pid, JoinType joinType, LogicalNode left) {
+    this(pid, joinType);
     setLeftChild(left);
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/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
new file mode 100644
index 0000000..d1cdab7
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinEdge.java
@@ -0,0 +1,57 @@
+/**
+ * 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.tajo.algebra.JoinType;
+import org.apache.tajo.engine.eval.EvalNode;
+
+import java.util.Collections;
+import java.util.Set;
+
+public class JoinEdge {
+  private JoinType joinType;
+  private String leftRelation;
+  private String rightRelation;
+  private Set<EvalNode> joinQual;
+
+  public JoinEdge(JoinType joinType, String leftRelation, String rightRelation, EvalNode ... condition) {
+    this.joinType = joinType;
+    Collections.addAll(joinQual, condition);
+  }
+
+  public JoinType getJoinType() {
+    return joinType;
+  }
+
+  public String getLeftRelation() {
+    return leftRelation;
+  }
+
+  public String getRightRelation() {
+    return rightRelation;
+  }
+
+  public void addJoinQual(EvalNode joinQual) {
+    this.joinQual.add(joinQual);
+  }
+
+  public EvalNode [] getJoinQual() {
+    return joinQual.toArray(new EvalNode[joinQual.size()]);
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/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
new file mode 100644
index 0000000..e07140b
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinGraph.java
@@ -0,0 +1,62 @@
+/**
+ * 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.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.planner.PlannerUtil;
+import org.apache.tajo.engine.planner.graph.SimpleUndirectedGraph;
+
+import java.util.Collection;
+import java.util.List;
+
+public class JoinGraph extends SimpleUndirectedGraph<String, JoinEdge> {
+  public Collection<JoinEdge> getJoinsFrom(String relation) {
+    return getEdges(relation);
+  }
+
+  public void addJoin(EvalNode condition) {
+    List<Column> left = EvalTreeUtil.findAllColumnRefs(condition.getLeftExpr());
+    List<Column> right = EvalTreeUtil.findAllColumnRefs(condition.getRightExpr());
+
+    String leftRelName = left.get(0).getQualifier();
+    String rightRelName = right.get(0).getQualifier();
+
+    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);
+      }
+    }
+    return joinGraph;
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinTree.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinTree.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinTree.java
deleted file mode 100644
index 2ec055a..0000000
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinTree.java
+++ /dev/null
@@ -1,95 +0,0 @@
-/**
- * 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.collect.Lists;
-import com.google.common.collect.Maps;
-import org.apache.tajo.catalog.Column;
-import org.apache.tajo.engine.eval.EvalNode;
-import org.apache.tajo.engine.eval.EvalTreeUtil;
-
-import java.util.Collection;
-import java.util.Collections;
-import java.util.List;
-import java.util.Map;
-
-public class JoinTree {
-  private Map<String,List<Edge>> map
-      = Maps.newHashMap();
-
-  public void addJoin(EvalNode node) {
-    List<Column> left = EvalTreeUtil.findAllColumnRefs(node.getLeftExpr());
-    List<Column> right = EvalTreeUtil.findAllColumnRefs(node.getRightExpr());
-
-    String ltbName = left.get(0).getQualifier();
-    String rtbName = right.get(0).getQualifier();
-
-    Edge l2r = new Edge(ltbName, rtbName, node);
-    Edge r2l = new Edge(rtbName, ltbName, node);
-    List<Edge> edges;
-    if (map.containsKey(ltbName)) {
-      edges = map.get(ltbName);
-    } else {
-      edges = Lists.newArrayList();
-    }
-    edges.add(l2r);
-    map.put(ltbName, edges);
-
-    if (map.containsKey(rtbName)) {
-      edges = map.get(rtbName);
-    } else {
-      edges = Lists.newArrayList();
-    }
-    edges.add(r2l);
-    map.put(rtbName, edges);
-  }
-
-  public int degree(String tableName) {
-    return this.map.get(tableName).size();
-  }
-
-  public Collection<String> getTables() {
-    return Collections.unmodifiableCollection(this.map.keySet());
-  }
-
-  public Collection<Edge> getEdges(String tableName) {
-    return Collections.unmodifiableCollection(this.map.get(tableName));
-  }
-
-  public Collection<Edge> getAllEdges() {
-    List<Edge> edges = Lists.newArrayList();
-    for (List<Edge> edgeList : map.values()) {
-      edges.addAll(edgeList);
-    }
-    return Collections.unmodifiableCollection(edges);
-  }
-
-  public int getTableNum() {
-    return this.map.size();
-  }
-
-  public int getJoinNum() {
-    int sum = 0;
-    for (List<Edge> edgeList : map.values()) {
-      sum += edgeList.size();
-    }
-
-    return sum / 2;
-  }
-}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/TajoMasterClientService.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/TajoMasterClientService.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/TajoMasterClientService.java
index 70c8ae5..b6efd1d 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/TajoMasterClientService.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/TajoMasterClientService.java
@@ -23,7 +23,6 @@ import com.google.protobuf.ServiceException;
 import org.apache.commons.lang.exception.ExceptionUtils;
 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
-import org.apache.hadoop.fs.FileStatus;
 import org.apache.hadoop.fs.FileSystem;
 import org.apache.hadoop.fs.Path;
 import org.apache.hadoop.yarn.service.AbstractService;

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/QueryMasterTask.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/QueryMasterTask.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/QueryMasterTask.java
index b93fc11..adc50df 100644
--- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/QueryMasterTask.java
+++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/QueryMasterTask.java
@@ -41,7 +41,6 @@ import org.apache.tajo.engine.planner.global.MasterPlan;
 import org.apache.tajo.engine.planner.logical.LogicalNode;
 import org.apache.tajo.engine.planner.logical.NodeType;
 import org.apache.tajo.engine.planner.logical.ScanNode;
-import org.apache.tajo.master.QueryContext;
 import org.apache.tajo.master.GlobalEngine;
 import org.apache.tajo.master.QueryContext;
 import org.apache.tajo.master.TajoAsyncDispatcher;

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/client/TestDDLBuilder.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/client/TestDDLBuilder.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/client/TestDDLBuilder.java
new file mode 100644
index 0000000..d4e31b2
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/client/TestDDLBuilder.java
@@ -0,0 +1,49 @@
+/**
+ * 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.client;
+
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.io.compress.GzipCodec;
+import org.apache.tajo.catalog.*;
+import org.apache.tajo.catalog.proto.CatalogProtos;
+import org.apache.tajo.common.TajoDataTypes;
+import org.apache.tajo.util.FileUtil;
+import org.junit.Test;
+
+import java.io.File;
+
+import static org.junit.Assert.assertEquals;
+
+
+public class TestDDLBuilder {
+  @Test
+  public void testBuildDDL() throws Exception {
+    Schema schema = new Schema();
+    schema.addColumn("name", TajoDataTypes.Type.BLOB);
+    schema.addColumn("addr", TajoDataTypes.Type.TEXT);
+    TableMeta meta = CatalogUtil.newTableMeta(schema, CatalogProtos.StoreType.CSV);
+    meta.putOption("csv.delimiter", "|");
+    meta.putOption(TableMeta.COMPRESSION_CODEC, GzipCodec.class.getName());
+
+
+    TableDesc desc = new TableDescImpl("table1", meta, new Path("/table1"));
+
+    assertEquals(FileUtil.readTextFile(new File("src/test/results/testBuildDDL.result")), DDLBuilder.buildDDL(desc));
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestGenericDirectedGraph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestGenericDirectedGraph.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestGenericDirectedGraph.java
deleted file mode 100644
index f4d4a8d..0000000
--- a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestGenericDirectedGraph.java
+++ /dev/null
@@ -1,73 +0,0 @@
-/**
- * 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.engine.planner.graph.DirectedGraphVisitor;
-import org.apache.tajo.engine.planner.graph.SimpleDirectedGraph;
-import org.junit.Test;
-
-import java.util.Stack;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertTrue;
-
-public class TestGenericDirectedGraph {
-
-  @Test
-  public final void test() {
-    SimpleDirectedGraph<String, Integer> graph = new SimpleDirectedGraph<String, Integer>();
-
-    //     root
-    //     /  \
-    // (1)/    \ (2)
-    //   /      \
-    // child1  child2
-    //           / \
-    //       (3)/   \(4)
-    //         /     \
-    //    child3   child4
-    //
-    String root = "root";
-    String child1 = "child1";
-    String child2 = "child2";
-    String child3 = "child3";
-    String child4 = "child4";
-
-    graph.connect(child1, root, 1);
-    graph.connect(child2, root, 2);
-    graph.connect(child3, child2, 3);
-    graph.connect(child4, child2, 4);
-
-    assertTrue(graph.isRoot(root));
-    assertFalse(graph.isLeaf(root));
-
-    assertEquals(2, graph.getChildCount(root));
-    assertEquals(2, graph.getChildCount(child2));
-
-    graph.accept(root, new Visitor());
-  }
-
-  private class Visitor implements DirectedGraphVisitor<String> {
-    @Override
-    public void visit(Stack<String> stack, String s) {
-      System.out.println("===> " + s);
-    }
-  }
-}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestLogicalPlan.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestLogicalPlan.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestLogicalPlan.java
index 11775c1..9b8307d 100644
--- a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestLogicalPlan.java
+++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestLogicalPlan.java
@@ -89,9 +89,9 @@ public class TestLogicalPlan {
     LogicalPlan.QueryBlock new1 = plan.newAndGetBlock("@new1");
     LogicalPlan.QueryBlock new2 = plan.newAndGetBlock("@new2");
 
-    plan.getQueryBlockGraph().connect(new1.getName(), root.getName(),
+    plan.getQueryBlockGraph().addEdge(new1.getName(), root.getName(),
         new LogicalPlan.BlockEdge(new1, root, BlockType.TableSubQuery));
-    plan.getQueryBlockGraph().connect(new2.getName(), root.getName(),
+    plan.getQueryBlockGraph().addEdge(new2.getName(), root.getName(),
         new LogicalPlan.BlockEdge(new2, root, BlockType.TableSubQuery));
 
     SimpleDirectedGraph<String, LogicalPlan.BlockEdge> graph = plan.getQueryBlockGraph();

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestSimpleDirectedGraph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestSimpleDirectedGraph.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestSimpleDirectedGraph.java
new file mode 100644
index 0000000..607a6ae
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestSimpleDirectedGraph.java
@@ -0,0 +1,79 @@
+/**
+ * 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.engine.planner.graph.DirectedGraphVisitor;
+import org.apache.tajo.engine.planner.graph.SimpleDirectedGraph;
+import org.junit.Test;
+
+import java.util.Stack;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+public class TestSimpleDirectedGraph {
+
+  @Test
+  public final void test() {
+    SimpleDirectedGraph<String, Integer> graph = new SimpleDirectedGraph<String, Integer>();
+
+    //     root
+    //     /  \
+    // (1)/    \ (2)
+    //   /      \
+    // child1  child2
+    //           / \
+    //       (3)/   \(4)
+    //         /     \
+    //    child3   child4
+    //
+    String root = "root";
+    String child1 = "child1";
+    String child2 = "child2";
+    String child3 = "child3";
+    String child4 = "child4";
+
+    graph.addEdge(child1, root, 1);
+    graph.addEdge(child2, root, 2);
+    graph.addEdge(child3, child2, 3);
+    graph.addEdge(child4, child2, 4);
+
+    assertEquals(4, graph.getEdgeNum());
+    assertEquals(4, graph.getEdgesAll().size());
+
+    // tree features
+    assertTrue(graph.isRoot(root));
+    assertFalse(graph.isLeaf(root));
+
+    assertEquals(2, graph.getChildCount(root));
+    assertEquals(2, graph.getChildCount(child2));
+
+    // visitor
+    graph.accept(root, new Visitor());
+  }
+
+  private class Visitor implements DirectedGraphVisitor<String> {
+
+    @Override
+    public void visit(Stack<String> stack, String s) {
+      System.out.println("===> " + s);
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestSimpleUndirectedGraph.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestSimpleUndirectedGraph.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestSimpleUndirectedGraph.java
new file mode 100644
index 0000000..1cd2389
--- /dev/null
+++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/planner/TestSimpleUndirectedGraph.java
@@ -0,0 +1,96 @@
+/**
+ * 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 com.google.common.collect.Sets;
+import org.apache.tajo.engine.planner.graph.SimpleUndirectedGraph;
+import org.apache.tajo.engine.planner.graph.UndirectedGraph;
+import org.junit.Test;
+
+import java.util.Set;
+
+import static org.junit.Assert.*;
+
+public class TestSimpleUndirectedGraph {
+
+  @Test
+  public final void test() {
+    UndirectedGraph<String, Integer> graph = new SimpleUndirectedGraph<String, Integer>();
+
+    //     root
+    //     /  \
+    // (1)/    \ (2)
+    //   /      \
+    // child1  child2
+    //           / \
+    //       (3)/   \(4)
+    //         /     \
+    //    child3   child4
+    //
+    String root = "root";
+    String child1 = "child1";
+    String child2 = "child2";
+    String child3 = "child3";
+    String child4 = "child4";
+
+    graph.addEdge(child1, root, 1);
+    graph.addEdge(child2, root, 2);
+    graph.addEdge(child3, child2, 3);
+    graph.addEdge(child4, child2, 4);
+
+    // for connected edges
+    assertNotNull(graph.getEdge(child1, root));
+    assertNotNull(graph.getEdge(root, child1));
+
+    assertNotNull(graph.getEdge(root, child2));
+    assertNotNull(graph.getEdge(child2, root));
+
+    assertNotNull(graph.getEdge(child2, child3));
+    assertNotNull(graph.getEdge(child3, child2));
+
+    assertNotNull(graph.getEdge(child2, child4));
+    assertNotNull(graph.getEdge(child4, child2));
+
+    // for not-connected edges
+    assertNull(graph.getEdge(root, child4));
+    assertNull(graph.getEdge(child4, root));
+
+    assertNull(graph.getEdge(root, child3));
+    assertNull(graph.getEdge(child3, root));
+
+    assertNull(graph.getEdge(child1, child2));
+    assertNull(graph.getEdge(child2, child1));
+
+    assertNull(graph.getEdge(child3, child4));
+    assertNull(graph.getEdge(child4, child3));
+
+    // number
+    assertEquals(4, graph.getEdgeNum());
+    assertEquals(4, graph.getEdgesAll().size());
+
+    assertEquals(2, graph.getDegree(root));
+    assertEquals(1, graph.getDegree(child1));
+    assertEquals(3, graph.getDegree(child2));
+    assertEquals(1, graph.getDegree(child3));
+    assertEquals(1, graph.getDegree(child4));
+
+    Set<Integer> edges = Sets.newHashSet(2, 3, 4);
+    assertEquals(edges, Sets.newHashSet(graph.getEdges(child2)));
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/8b872bc1/tajo-core/tajo-core-storage/src/main/java/org/apache/tajo/storage/AbstractStorageManager.java
----------------------------------------------------------------------
diff --git a/tajo-core/tajo-core-storage/src/main/java/org/apache/tajo/storage/AbstractStorageManager.java b/tajo-core/tajo-core-storage/src/main/java/org/apache/tajo/storage/AbstractStorageManager.java
index 40d0410..f8cf94d 100644
--- a/tajo-core/tajo-core-storage/src/main/java/org/apache/tajo/storage/AbstractStorageManager.java
+++ b/tajo-core/tajo-core-storage/src/main/java/org/apache/tajo/storage/AbstractStorageManager.java
@@ -26,13 +26,11 @@ import org.apache.hadoop.conf.Configuration;
 import org.apache.hadoop.fs.*;
 import org.apache.hadoop.hdfs.DFSConfigKeys;
 import org.apache.hadoop.hdfs.DistributedFileSystem;
-import org.apache.tajo.TajoConstants;
 import org.apache.tajo.catalog.Schema;
 import org.apache.tajo.catalog.TableMeta;
 import org.apache.tajo.catalog.TableMetaImpl;
 import org.apache.tajo.catalog.proto.CatalogProtos;
 import org.apache.tajo.conf.TajoConf;
-import org.apache.tajo.storage.v2.StorageManagerV2;
 import org.apache.tajo.util.Bytes;
 import org.apache.tajo.util.FileUtil;
 


Mime
View raw message