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/04 14:20:31 UTC
git commit: TAJO-229: Implement JoinGraph to represent a graph of
relation joins. (hyunsik)
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 <hy...@apache.org>
Authored: Fri Oct 4 21:20:06 2013 +0900
Committer: Hyunsik Choi <hy...@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;