Return-Path: X-Original-To: apmail-tajo-commits-archive@minotaur.apache.org Delivered-To: apmail-tajo-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id E010D1041F for ; Thu, 5 Dec 2013 15:04:10 +0000 (UTC) Received: (qmail 24496 invoked by uid 500); 5 Dec 2013 15:04:10 -0000 Delivered-To: apmail-tajo-commits-archive@tajo.apache.org Received: (qmail 24108 invoked by uid 500); 5 Dec 2013 15:04:08 -0000 Mailing-List: contact commits-help@tajo.incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@tajo.incubator.apache.org Delivered-To: mailing list commits@tajo.incubator.apache.org Received: (qmail 22998 invoked by uid 99); 5 Dec 2013 15:04:06 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 05 Dec 2013 15:04:06 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED,RP_MATCHES_RCVD X-Spam-Check-By: apache.org Received: from [140.211.11.3] (HELO mail.apache.org) (140.211.11.3) by apache.org (qpsmtpd/0.29) with SMTP; Thu, 05 Dec 2013 15:04:02 +0000 Received: (qmail 20377 invoked by uid 99); 5 Dec 2013 15:03:39 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 05 Dec 2013 15:03:39 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id 392B181B621; Thu, 5 Dec 2013 15:03:39 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: hyunsik@apache.org To: commits@tajo.incubator.apache.org Date: Thu, 05 Dec 2013 15:03:39 -0000 Message-Id: X-Mailer: ASF-Git Admin Mailer Subject: [1/2] TAJO-316: Improve GreedyHeuristicJoinOrderAlgorithm to deal with non-commutative joins. (hyunsik) X-Virus-Checked: Checked by ClamAV on apache.org Updated Branches: refs/heads/master 45de54bcd -> 39fe4d765 http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java index b34c1ac..eafa671 100644 --- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java +++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/logical/join/JoinOrderAlgorithm.java @@ -19,8 +19,8 @@ package org.apache.tajo.engine.planner.logical.join; import org.apache.hadoop.classification.InterfaceStability; -import org.apache.tajo.engine.eval.EvalNode; import org.apache.tajo.engine.planner.LogicalPlan; +import org.apache.tajo.engine.planner.PlanningException; import java.util.Set; @@ -29,6 +29,18 @@ import java.util.Set; */ @InterfaceStability.Evolving public interface JoinOrderAlgorithm { + + /** + * + * @param plan + * @param block + * @param joinGraph A join graph represents join conditions and their connections among relations. + * Given a graph, each vertex represents a relation, and each edge contains a join condition. + * A join graph does not contain relations that do not have any corresponding join condition. + * @param relationsWithoutQual The names of relations that do not have any corresponding join condition. + * @return + * @throws PlanningException + */ FoundJoinOrder findBestOrder(LogicalPlan plan, LogicalPlan.QueryBlock block, JoinGraph joinGraph, - Set joinQuals, Set relationsWithoutQual); + Set relationsWithoutQual) throws PlanningException; } http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java index 824a0b8..0971444 100644 --- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java +++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/engine/planner/rewrite/FilterPushDownRule.java @@ -108,8 +108,8 @@ public class FilterPushDownRule extends BasicLogicalPlanVisitor, L String leftTableName = ((FieldEval) joinQual.getLeftExpr()).getTableId(); String rightTableName = ((FieldEval) joinQual.getRightExpr()).getTableId(); List nullSuppliers = Lists.newArrayList(); - String [] leftLineage = PlannerUtil.getLineage(joinNode.getLeftChild()); - String [] rightLineage = PlannerUtil.getLineage(joinNode.getRightChild()); + String [] leftLineage = PlannerUtil.getRelationLineage(joinNode.getLeftChild()); + String [] rightLineage = PlannerUtil.getRelationLineage(joinNode.getRightChild()); Set leftTableSet = Sets.newHashSet(leftLineage); Set rightTableSet = Sets.newHashSet(rightLineage); http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/Repartitioner.java ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/Repartitioner.java b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/Repartitioner.java index 82d2be4..ac59408 100644 --- a/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/Repartitioner.java +++ b/tajo-core/tajo-core-backend/src/main/java/org/apache/tajo/master/querymaster/Repartitioner.java @@ -471,7 +471,7 @@ public class Repartitioner { GroupbyNode groupby = PlannerUtil.findTopNode(subQuery.getBlock().getPlan(), NodeType.GROUP_BY); // the number of tasks cannot exceed the number of merged fetch uris. int determinedTaskNum = Math.min(maxNum, finalFetchURI.size()); - if (groupby.getGroupingColumns().length == 0) { + if (groupby != null && groupby.getGroupingColumns().length == 0) { determinedTaskNum = 1; } http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestInsertQuery.java ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestInsertQuery.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestInsertQuery.java index c005551..9882bc6 100644 --- a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestInsertQuery.java +++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestInsertQuery.java @@ -53,7 +53,7 @@ public class TestInsertQuery { @Test public final void testInsertOverwrite() throws Exception { String tableName ="InsertOverwrite"; - ResultSet res = tpch.execute("create table " + tableName +" (col1 int8, col2 int4, col3 float4)"); + ResultSet res = tpch.execute("create table " + tableName +" (col1 int4, col2 int4, col3 float4)"); res.close(); TajoTestingCluster cluster = tpch.getTestingCluster(); CatalogService catalog = cluster.getMaster().getCatalog(); @@ -70,7 +70,7 @@ public class TestInsertQuery { @Test public final void testInsertOverwriteSmallerColumns() throws Exception { String tableName = "insertoverwritesmallercolumns"; - ResultSet res = tpch.execute("create table " + tableName + " (col1 int8, col2 int4, col3 float4)"); + ResultSet res = tpch.execute("create table " + tableName + " (col1 int4, col2 int4, col3 float4)"); res.close(); TajoTestingCluster cluster = tpch.getTestingCluster(); CatalogService catalog = cluster.getMaster().getCatalog(); @@ -87,7 +87,7 @@ public class TestInsertQuery { @Test public final void testInsertOverwriteWithTargetColumns() throws Exception { String tableName = "InsertOverwriteWithTargetColumns"; - ResultSet res = tpch.execute("create table " + tableName + " (col1 int8, col2 int4, col3 float4)"); + ResultSet res = tpch.execute("create table " + tableName + " (col1 int4, col2 int4, col3 float4)"); res.close(); TajoTestingCluster cluster = tpch.getTestingCluster(); CatalogService catalog = cluster.getMaster().getCatalog(); @@ -204,7 +204,7 @@ public class TestInsertQuery { @Test public final void testInsertOverwriteWithCompression() throws Exception { String tableName = "testInsertOverwriteWithCompression"; - ResultSet res = tpch.execute("create table " + tableName + " (col1 int8, col2 int4, col3 float4) USING csv WITH ('csvfile.delimiter'='|','compression.codec'='org.apache.hadoop.io.compress.DeflateCodec')"); + ResultSet res = tpch.execute("create table " + tableName + " (col1 int4, col2 int4, col3 float4) USING csv WITH ('csvfile.delimiter'='|','compression.codec'='org.apache.hadoop.io.compress.DeflateCodec')"); res.close(); TajoTestingCluster cluster = tpch.getTestingCluster(); CatalogService catalog = cluster.getMaster().getCatalog(); http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestJoinQuery.java ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestJoinQuery.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestJoinQuery.java index bf069ec..fbcc9a0 100644 --- a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestJoinQuery.java +++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestJoinQuery.java @@ -19,21 +19,20 @@ package org.apache.tajo.engine.query; import com.google.common.collect.Maps; +import org.apache.tajo.IntegrationTest; +import org.apache.tajo.TpchTestBase; +import org.apache.tajo.util.FileUtil; import org.junit.AfterClass; import org.junit.BeforeClass; import org.junit.Test; import org.junit.experimental.categories.Category; -import org.apache.tajo.IntegrationTest; -import org.apache.tajo.TpchTestBase; -import org.apache.tajo.util.FileUtil; import java.io.File; import java.io.IOException; import java.sql.ResultSet; import java.util.Map; -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertFalse; +import static org.junit.Assert.*; @Category(IntegrationTest.class) public class TestJoinQuery { @@ -129,6 +128,63 @@ public class TestJoinQuery { } @Test + public final void testLeftOuterJoin1() throws Exception { + ResultSet res = tpch.execute( + "select c_custkey, orders.o_orderkey from customer left outer join orders on c_custkey = o_orderkey;"); + try { + Map result = Maps.newHashMap(); + result.put(1, 1); + result.put(2, 2); + result.put(3, 3); + result.put(4, 0); + result.put(5, 0); + while(res.next()) { + assertTrue(result.get(res.getInt(1)) == res.getInt(2)); + } + } finally { + res.close(); + } + } + + @Test + public final void testRightOuterJoin1() throws Exception { + ResultSet res = tpch.execute( + "select c_custkey, orders.o_orderkey from orders right outer join customer on c_custkey = o_orderkey;"); + try { + Map result = Maps.newHashMap(); + result.put(1, 1); + result.put(2, 2); + result.put(3, 3); + result.put(4, 0); + result.put(5, 0); + while(res.next()) { + assertTrue(result.get(res.getInt(1)) == res.getInt(2)); + } + } finally { + res.close(); + } + } + + @Test + public final void testFullOuterJoin1() throws Exception { + ResultSet res = tpch.execute( + "select c_custkey, orders.o_orderkey, from orders full outer join customer on c_custkey = o_orderkey;"); + try { + Map result = Maps.newHashMap(); + result.put(1, 1); + result.put(2, 2); + result.put(3, 3); + result.put(4, 0); + result.put(5, 0); + while(res.next()) { + assertTrue(result.get(res.getInt(1)) == res.getInt(2)); + } + } finally { + res.close(); + } + } + + @Test public void testJoinRefEval() throws Exception { ResultSet res = tpch.execute("select r_regionkey, n_regionkey, (r_regionkey + n_regionkey) as plus from region, nation where r_regionkey = n_regionkey"); try { http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestSelectQuery.java ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestSelectQuery.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestSelectQuery.java index 2547714..369b4c6 100644 --- a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestSelectQuery.java +++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestSelectQuery.java @@ -425,7 +425,7 @@ public class TestSelectQuery { for (;res.next();) { count++; } - assertEquals(6, count); + assertEquals(8, count); } finally { res.close(); } http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestTableSubQuery.java ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestTableSubQuery.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestTableSubQuery.java index db886ba..b24b03d 100644 --- a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestTableSubQuery.java +++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/engine/query/TestTableSubQuery.java @@ -91,4 +91,27 @@ public class TestTableSubQuery { res.close(); } } + + @Test + public final void testJoinSubQuery2() throws Exception { + ResultSet res = tpch.execute( + "SELECT A.n_regionkey, B.r_regionkey, A.n_name, B.r_name " + + "FROM\n" + + "(SELECT * FROM nation WHERE n_name LIKE 'A%') A " + + ", region B WHERE A.n_regionkey=B.r_regionkey"); + + Map expected = new HashMap(); + expected.put("ARGENTINA", "AMERICA"); + expected.put("ALGERIA", "AFRICA"); + try { + assertNotNull(res); + assertTrue(res.next()); + assertTrue(expected.get(res.getString("n_name")).equals(res.getString("r_name"))); + assertTrue(res.next()); + assertTrue(expected.get(res.getString("n_name")).equals(res.getString("r_name"))); + assertFalse(res.next()); + } finally { + res.close(); + } + } } \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java index c3b5aa3..5b6b5a3 100644 --- a/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java +++ b/tajo-core/tajo-core-backend/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java @@ -66,7 +66,9 @@ public class TestExecutionBlockCursor { for (String table : tpch.getTableNames()) { TableMeta m = CatalogUtil.newTableMeta(CatalogProtos.StoreType.CSV); TableDesc d = CatalogUtil.newTableDesc(table, tpch.getSchema(table), m, CommonTestingUtil.getTestDir()); - d.setStats(new TableStats()); + TableStats stats = new TableStats(); + stats.setNumBytes(TPCH.tableVolumes.get(table)); + d.setStats(stats); catalog.addTable(d); } @@ -110,7 +112,7 @@ public class TestExecutionBlockCursor { count++; } - // 4 input relations, 1 broadcast join and 2 symmetric repartition joins and 1 terminal = 8 execution blocks + // 5 input relations, 1 broadcast join and 2 symmetric repartition joins and 1 terminal = 8 execution blocks assertEquals(8, count); } } http://git-wip-us.apache.org/repos/asf/incubator-tajo/blob/39fe4d76/tajo-core/tajo-core-backend/src/test/tpch/customer.tbl ---------------------------------------------------------------------- diff --git a/tajo-core/tajo-core-backend/src/test/tpch/customer.tbl b/tajo-core/tajo-core-backend/src/test/tpch/customer.tbl index 2c2a8e7..4f684c6 100644 --- a/tajo-core/tajo-core-backend/src/test/tpch/customer.tbl +++ b/tajo-core/tajo-core-backend/src/test/tpch/customer.tbl @@ -1,3 +1,5 @@ 1|Customer#000000001|IVhzIApeRb ot,c,E|15|25-989-741-2988|711.56|BUILDING|to the even, regular platelets. regular, ironic epitaphs nag e| 2|Customer#000000002|XSTf4,NCwDVaWNe6tEgvwfmRchLXak|13|23-768-687-3665|121.65|AUTOMOBILE|l accounts. blithely ironic theodolites integrate boldly: caref| 3|Customer#000000003|MG9kdTD2WBHm|1|11-719-748-3364|7498.12|AUTOMOBILE| deposits eat slyly ironic, even instructions. express foxes detect slyly. blithely even accounts abov| +4|Customer#000000004|XxVSJsLAGtn|4|14-128-190-5944|2866.83|MACHINERY| requests. final, regular ideas sleep final accou| +5|Customer#000000005|KvpyuHCplrB84WgAiGV6sYpZq7Tj|3|13-750-942-6364|794.47|HOUSEHOLD|n accounts will have to unwind. foxes cajole accor|