http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/parser/preprocessed/SqlParser_gen.hpp ---------------------------------------------------------------------- diff --git a/parser/preprocessed/SqlParser_gen.hpp b/parser/preprocessed/SqlParser_gen.hpp index e35664f..b884861 100644 --- a/parser/preprocessed/SqlParser_gen.hpp +++ b/parser/preprocessed/SqlParser_gen.hpp @@ -1,8 +1,8 @@ -/* A Bison parser, made by GNU Bison 3.0.2. */ +/* A Bison parser, made by GNU Bison 3.0.4. */ /* Bison interface for Yacc-like parsers in C - Copyright (C) 1984, 1989-1990, 2000-2013 Free Software Foundation, Inc. + Copyright (C) 1984, 1989-1990, 2000-2015 Free Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -164,10 +164,10 @@ extern int quickstep_yydebug; /* Value type. */ #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED -typedef union YYSTYPE YYSTYPE; + union YYSTYPE { -#line 117 "../SqlParser.ypp" /* yacc.c:1909 */ +#line 118 "../SqlParser.ypp" /* yacc.c:1915 */ quickstep::ParseString *string_value_; @@ -203,6 +203,8 @@ union YYSTYPE quickstep::PtrList<quickstep::ParseTableReference> *table_reference_list_; quickstep::ParseTableReferenceSignature *table_reference_signature_; + quickstep::ParseJoinedTableReference::JoinType join_type_; + quickstep::ParseDataType *data_type_; quickstep::ParseAttributeDefinition *attribute_definition_; quickstep::ParseColumnConstraint *column_constraint_; @@ -257,8 +259,10 @@ union YYSTYPE quickstep::PtrVector<quickstep::ParseSubqueryTableReference> *with_list_; quickstep::ParseSubqueryTableReference *with_list_element_; -#line 261 "SqlParser_gen.hpp" /* yacc.c:1909 */ +#line 263 "SqlParser_gen.hpp" /* yacc.c:1915 */ }; + +typedef union YYSTYPE YYSTYPE; # define YYSTYPE_IS_TRIVIAL 1 # define YYSTYPE_IS_DECLARED 1 #endif
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/parser/tests/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/parser/tests/CMakeLists.txt b/parser/tests/CMakeLists.txt index e9229e0..cea0f45 100644 --- a/parser/tests/CMakeLists.txt +++ b/parser/tests/CMakeLists.txt @@ -58,6 +58,10 @@ add_test(quickstep_parser_tests_ParserTest_insert quickstep_parser_tests_ParserTest "${CMAKE_CURRENT_SOURCE_DIR}/Insert.test" "${CMAKE_CURRENT_BINARY_DIR}/Insert.test") +add_test(quickstep_parser_tests_ParserTest_join + quickstep_parser_tests_ParserTest + "${CMAKE_CURRENT_SOURCE_DIR}/Join.test" + "${CMAKE_CURRENT_BINARY_DIR}/Join.test") add_test(quickstep_parser_tests_ParserTest_select quickstep_parser_tests_ParserTest "${CMAKE_CURRENT_SOURCE_DIR}/Select.test" http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/parser/tests/Join.test ---------------------------------------------------------------------- diff --git a/parser/tests/Join.test b/parser/tests/Join.test new file mode 100644 index 0000000..8a252a4 --- /dev/null +++ b/parser/tests/Join.test @@ -0,0 +1,160 @@ +# Copyright 2016, Quickstep Research Group, Computer Sciences Department, +# University of WisconsinâMadison. +# +# Licensed 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. + +SELECT * +FROM a JOIN b ON a.w = b.w + JOIN c ON a.x = c.x + JOIN d ON a.y = d.y; +-- +SelectStatement ++-select_query=Select + +-select_clause=SelectStar + +-from_clause= + +-JoinedTable[join_type=InnerJoin] + +-left_table=JoinedTable[join_type=InnerJoin] + | +-left_table=JoinedTable[join_type=InnerJoin] + | | +-left_table=TableReference[table=a] + | | +-right_table=TableReference[table=b] + | | +-join_predicate=Equal + | | +-left_operand=AttributeReference[attribute_name=w,relation_name=a] + | | +-right_operand=AttributeReference[attribute_name=w,relation_name=b] + | +-right_table=TableReference[table=c] + | +-join_predicate=Equal + | +-left_operand=AttributeReference[attribute_name=x,relation_name=a] + | +-right_operand=AttributeReference[attribute_name=x,relation_name=c] + +-right_table=TableReference[table=d] + +-join_predicate=Equal + +-left_operand=AttributeReference[attribute_name=y,relation_name=a] + +-right_operand=AttributeReference[attribute_name=y,relation_name=d] +== + +SELECT * +FROM a AS a1 JOIN b AS b1 ON a1.w = b1.w + JOIN c AS c1 ON a1.x = c1.x + JOIN d AS d1 ON a1.y = d1.y; +WHERE a1.x > b1.x + AND a1.y > c1.y + AND a1.z > d1.z; +-- +SelectStatement ++-select_query=Select + +-select_clause=SelectStar + +-from_clause= + +-JoinedTable[join_type=InnerJoin] + +-left_table=JoinedTable[join_type=InnerJoin] + | +-left_table=JoinedTable[join_type=InnerJoin] + | | +-left_table=TableReference[table=a] + | | | +-table_signature=TableSignature[table_alias=a1] + | | +-right_table=TableReference[table=b] + | | | +-table_signature=TableSignature[table_alias=b1] + | | +-join_predicate=Equal + | | +-left_operand=AttributeReference[attribute_name=w,relation_name=a1] + | | +-right_operand=AttributeReference[attribute_name=w,relation_name=b1] + | +-right_table=TableReference[table=c] + | | +-table_signature=TableSignature[table_alias=c1] + | +-join_predicate=Equal + | +-left_operand=AttributeReference[attribute_name=x,relation_name=a1] + | +-right_operand=AttributeReference[attribute_name=x,relation_name=c1] + +-right_table=TableReference[table=d] + | +-table_signature=TableSignature[table_alias=d1] + +-join_predicate=Equal + +-left_operand=AttributeReference[attribute_name=y,relation_name=a1] + +-right_operand=AttributeReference[attribute_name=y,relation_name=d1] +== + +SELECT * +FROM a LEFT OUTER JOIN b ON a.w = b.w + RIGHT OUTER JOIN c ON a.x = c.x + FULL OUTER JOIN d ON a.y = d.y; +-- +SelectStatement ++-select_query=Select + +-select_clause=SelectStar + +-from_clause= + +-JoinedTable[join_type=FullOuterJoin] + +-left_table=JoinedTable[join_type=RightOuterJoin] + | +-left_table=JoinedTable[join_type=LeftOuterJoin] + | | +-left_table=TableReference[table=a] + | | +-right_table=TableReference[table=b] + | | +-join_predicate=Equal + | | +-left_operand=AttributeReference[attribute_name=w,relation_name=a] + | | +-right_operand=AttributeReference[attribute_name=w,relation_name=b] + | +-right_table=TableReference[table=c] + | +-join_predicate=Equal + | +-left_operand=AttributeReference[attribute_name=x,relation_name=a] + | +-right_operand=AttributeReference[attribute_name=x,relation_name=c] + +-right_table=TableReference[table=d] + +-join_predicate=Equal + +-left_operand=AttributeReference[attribute_name=y,relation_name=a] + +-right_operand=AttributeReference[attribute_name=y,relation_name=d] +== + +SELECT * +FROM a INNER JOIN b ON (a.w = b.w OR a.x > b.y); +-- +SelectStatement ++-select_query=Select + +-select_clause=SelectStar + +-from_clause= + +-JoinedTable[join_type=InnerJoin] + +-left_table=TableReference[table=a] + +-right_table=TableReference[table=b] + +-join_predicate=Or + +-Equal + | +-left_operand=AttributeReference[attribute_name=w,relation_name=a] + | +-right_operand=AttributeReference[attribute_name=w,relation_name=b] + +-Greater + +-left_operand=AttributeReference[attribute_name=x,relation_name=a] + +-right_operand=AttributeReference[attribute_name=y,relation_name=b] +== + +SELECT * +FROM b LEFT JOIN c ON b.x = c.x JOIN d ON c.y = d.y; +-- +SelectStatement ++-select_query=Select + +-select_clause=SelectStar + +-from_clause= + +-JoinedTable[join_type=InnerJoin] + +-left_table=JoinedTable[join_type=LeftOuterJoin] + | +-left_table=TableReference[table=b] + | +-right_table=TableReference[table=c] + | +-join_predicate=Equal + | +-left_operand=AttributeReference[attribute_name=x,relation_name=b] + | +-right_operand=AttributeReference[attribute_name=x,relation_name=c] + +-right_table=TableReference[table=d] + +-join_predicate=Equal + +-left_operand=AttributeReference[attribute_name=y,relation_name=c] + +-right_operand=AttributeReference[attribute_name=y,relation_name=d] +== + +SELECT * +FROM b LEFT JOIN (c JOIN d ON c.y = d.y) ON b.x = c.x; +-- +SelectStatement ++-select_query=Select + +-select_clause=SelectStar + +-from_clause= + +-JoinedTable[join_type=LeftOuterJoin] + +-left_table=TableReference[table=b] + +-right_table=JoinedTable[join_type=InnerJoin] + | +-left_table=TableReference[table=c] + | +-right_table=TableReference[table=d] + | +-join_predicate=Equal + | +-left_operand=AttributeReference[attribute_name=y,relation_name=c] + | +-right_operand=AttributeReference[attribute_name=y,relation_name=d] + +-join_predicate=Equal + +-left_operand=AttributeReference[attribute_name=x,relation_name=b] + +-right_operand=AttributeReference[attribute_name=x,relation_name=c] http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/parser/tests/TPCH.test ---------------------------------------------------------------------- diff --git a/parser/tests/TPCH.test b/parser/tests/TPCH.test index dfcd6aa..2d12df5 100644 --- a/parser/tests/TPCH.test +++ b/parser/tests/TPCH.test @@ -1089,9 +1089,46 @@ ORDER BY custdist desc, c_count DESC -- -ERROR: OUTER JOIN is not supported yet (10 : 16) - customer LEFT OUTER JOIN orders ON - ^ +SelectStatement ++-select_query=Select + +-select_clause=SelectList + | +-SelectListItem + | | +-AttributeReference[attribute_name=c_count] + | +-SelectListItem[alias=custdist] + | +-FunctionCall[name=COUNT,is_star=true] + +-group_by=GroupBy + | +-AttributeReference[attribute_name=c_count] + +-order_by=OrderBy + | +-OrderByItem[is_asc=false,nulls_first=true] + | | +-AttributeReference[attribute_name=custdist] + | +-OrderByItem[is_asc=false,nulls_first=true] + | +-AttributeReference[attribute_name=c_count] + +-from_clause= + +-SubqueryTable + +-table_signature=TableSignature[table_alias=c_orders, + | columns=(c_custkey, c_count)] + +-SubqueryExpression + +-Select + +-select_clause=SelectList + | +-SelectListItem + | | +-AttributeReference[attribute_name=c_custkey] + | +-SelectListItem + | +-FunctionCall[name=COUNT] + | +-AttributeReference[attribute_name=o_orderkey] + +-group_by=GroupBy + | +-AttributeReference[attribute_name=c_custkey] + +-from_clause= + +-JoinedTable[join_type=LeftOuterJoin] + +-left_table=TableReference[table=customer] + +-right_table=TableReference[table=orders] + +-join_predicate=And + +-Equal + | +-left_operand=AttributeReference[attribute_name=c_custkey] + | +-right_operand=AttributeReference[attribute_name=o_custkey] + +-NotLike + +-left_operand=AttributeReference[attribute_name=o_comment] + +-right_operand=Literal + +-StringLiteral[value=%special%requests%] == # Query 14 http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/resolver/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/query_optimizer/resolver/CMakeLists.txt b/query_optimizer/resolver/CMakeLists.txt index f8ffa72..854ace1 100644 --- a/query_optimizer/resolver/CMakeLists.txt +++ b/query_optimizer/resolver/CMakeLists.txt @@ -46,6 +46,7 @@ target_link_libraries(quickstep_queryoptimizer_resolver_Resolver quickstep_parser_ParseGeneratorTableReference quickstep_parser_ParseGroupBy quickstep_parser_ParseHaving + quickstep_parser_ParseJoinedTableReference quickstep_parser_ParseLimit quickstep_parser_ParseLiteralValue quickstep_parser_ParseOrderBy http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/resolver/NameResolver.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/resolver/NameResolver.cpp b/query_optimizer/resolver/NameResolver.cpp index 35745f3..9833f56 100644 --- a/query_optimizer/resolver/NameResolver.cpp +++ b/query_optimizer/resolver/NameResolver.cpp @@ -121,6 +121,23 @@ E::AttributeReferencePtr NameResolver::lookup( return attribute; } +void NameResolver::merge(NameResolver *other) { + // Check whether there is any conflict name with the input name resolver. + for (const auto &scoped_rel_info : other->rel_name_to_rel_info_map_) { + const std::string &rel_name = scoped_rel_info.first; + if (rel_name_to_rel_info_map_.find(rel_name) != rel_name_to_rel_info_map_.end()) { + THROW_SQL_ERROR_AT(&scoped_rel_info.second->parse_relation_name) + << "Relation alias " << rel_name << " appears more than once"; + } + } + + for (std::unique_ptr<RelationInfo> &scoped_relation : other->relations_) { + relations_.emplace_back(scoped_relation.release()); + } + rel_name_to_rel_info_map_.insert(other->rel_name_to_rel_info_map_.begin(), + other->rel_name_to_rel_info_map_.end()); +} + std::vector<E::AttributeReferencePtr> NameResolver::getVisibleAttributeReferences() const { std::vector<E::AttributeReferencePtr> referenced_attributes; for (const std::unique_ptr<RelationInfo> &rel : relations_) { http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/resolver/NameResolver.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/resolver/NameResolver.hpp b/query_optimizer/resolver/NameResolver.hpp index 6aed904..ea3f1e4 100644 --- a/query_optimizer/resolver/NameResolver.hpp +++ b/query_optimizer/resolver/NameResolver.hpp @@ -86,6 +86,15 @@ class NameResolver { const ParseString *parse_rel_node) const; /** + * @brief Combines the name scopes in the current name resolver and in \p other. + * The ownership of <relations_> in \p other will be transferred to the + * current name resolver. + * + * @param other The name resolver to be merged into this resolver. + */ + void merge(NameResolver *other); + + /** * @return All AttributeReferences in the current name scope. */ std::vector<expressions::AttributeReferencePtr> getVisibleAttributeReferences() const; http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/resolver/Resolver.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/resolver/Resolver.cpp b/query_optimizer/resolver/Resolver.cpp index 8323c33..242a1f0 100644 --- a/query_optimizer/resolver/Resolver.cpp +++ b/query_optimizer/resolver/Resolver.cpp @@ -42,6 +42,7 @@ #include "parser/ParseGeneratorTableReference.hpp" #include "parser/ParseGroupBy.hpp" #include "parser/ParseHaving.hpp" +#include "parser/ParseJoinedTableReference.hpp" #include "parser/ParseLimit.hpp" #include "parser/ParseLiteralValue.hpp" #include "parser/ParseOrderBy.hpp" @@ -1467,6 +1468,16 @@ L::LogicalPtr Resolver::resolveTableReference(const ParseTableReference &table_r name_resolver->addRelation(reference_alias, logical_plan); break; } + case ParseTableReference::kJoinedTableReference: { + NameResolver joined_table_name_resolver; + + logical_plan = resolveJoinedTableReference( + static_cast<const ParseJoinedTableReference&>(table_reference), + &joined_table_name_resolver); + + name_resolver->merge(&joined_table_name_resolver); + break; + } default: LOG(FATAL) << "Unhandeled table reference " << table_reference.toString(); } @@ -1592,6 +1603,29 @@ L::LogicalPtr Resolver::resolveGeneratorTableReference( } +L::LogicalPtr Resolver::resolveJoinedTableReference( + const ParseJoinedTableReference &joined_table_reference, + NameResolver *name_resolver) { + const L::LogicalPtr left_table = + resolveTableReference(*joined_table_reference.left_table(), name_resolver); + const L::LogicalPtr right_table = + resolveTableReference(*joined_table_reference.right_table(), name_resolver); + + ExpressionResolutionInfo resolution_info(*name_resolver, + "join clause" /* clause_name */, + nullptr /* select_list_info */); + const E::PredicatePtr on_predicate = + resolvePredicate(*joined_table_reference.join_predicate(), &resolution_info); + + if (joined_table_reference.join_type() == ParseJoinedTableReference::JoinType::kInnerJoin) { + return L::Filter::Create( + L::MultiwayCartesianJoin::Create({ left_table, right_table }), + on_predicate); + } + + THROW_SQL_ERROR_AT(&joined_table_reference) << "Outer joins are not supported yet"; +} + void Resolver::resolveSelectClause( const ParseSelectionClause &parse_selection, const std::string &select_name, http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/resolver/Resolver.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/resolver/Resolver.hpp b/query_optimizer/resolver/Resolver.hpp index 31afe18..a84c61c 100644 --- a/query_optimizer/resolver/Resolver.hpp +++ b/query_optimizer/resolver/Resolver.hpp @@ -41,6 +41,7 @@ class Comparison; class ParseExpression; class ParseFunctionCall; class ParseGeneratorTableReference; +class ParseJoinedTableReference; class ParseOrderBy; class ParsePredicate; class ParseSearchedCaseExpression; @@ -333,6 +334,19 @@ class Resolver { const ParseString *reference_alias); /** + * @brief Resolves a joined table resulting from a join between two table + * references. + * + * @param joined_table_reference The parse joined table reference to be resolved. + * @param name_resolver The name resolver to be updated with the left and the + * right tables. + * @return A logical plan for the joined table reference. + */ + logical::LogicalPtr resolveJoinedTableReference( + const ParseJoinedTableReference &joined_table_reference, + NameResolver *name_resolver); + + /** * @brief Renames the output columns from \p logical_plan based on the table signature * by wrapping it with a Project. * http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/OptimizerTextTestRunner.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/OptimizerTextTestRunner.hpp b/query_optimizer/tests/OptimizerTextTestRunner.hpp index ee1967a..7904ac3 100644 --- a/query_optimizer/tests/OptimizerTextTestRunner.hpp +++ b/query_optimizer/tests/OptimizerTextTestRunner.hpp @@ -51,6 +51,7 @@ class OptimizerTextTestRunner : public TextBasedTestRunner { */ OptimizerTextTestRunner() { test_database_loader_.createTestRelation(true /* allow_vchar */); + test_database_loader_.createJoinRelations(); } void runTestCase(const std::string &input, http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/TestDatabaseLoader.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/TestDatabaseLoader.cpp b/query_optimizer/tests/TestDatabaseLoader.cpp index 05907b3..2de69b6 100644 --- a/query_optimizer/tests/TestDatabaseLoader.cpp +++ b/query_optimizer/tests/TestDatabaseLoader.cpp @@ -18,6 +18,7 @@ #include "query_optimizer/tests/TestDatabaseLoader.hpp" #include <cmath> +#include <cstddef> #include <cstdint> #include <memory> #include <string> @@ -84,6 +85,35 @@ CatalogRelation *TestDatabaseLoader::createTestRelation(bool allow_vchar) { return test_relation_; } +void TestDatabaseLoader::createJoinRelations() { + std::vector<std::string> rel_names = { "a", "b", "c", "d" }; + std::vector<std::vector<std::pair<std::string, TypeID>>> rel_columns = { + { { "w", kInt }, { "x", kInt }, { "y", kInt }, { "z", kInt } }, + { { "w", kInt }, { "x", kInt } }, + { { "x", kInt }, { "y", kInt } }, + { { "y", kInt }, { "z", kInt } } + }; + + for (std::size_t rel_idx = 0; rel_idx < rel_names.size(); ++rel_idx) { + std::unique_ptr<CatalogRelation> relation( + new CatalogRelation(&catalog_database_, + rel_names[rel_idx], + -1 /* id */, + true /* temporary */)); + + const std::vector<std::pair<std::string, TypeID>> &columns = rel_columns[rel_idx]; + int attr_id = -1; + for (std::size_t col_idx = 0; col_idx < columns.size(); ++col_idx) { + relation->addAttribute(new CatalogAttribute( + relation.get(), + columns[col_idx].first, + TypeFactory::GetType(columns[col_idx].second), + ++attr_id)); + } + catalog_database_.addRelation(relation.release()); + } +} + void TestDatabaseLoader::loadTestRelation() { CHECK(test_relation_ != nullptr); CHECK(!test_relation_->hasAttributeWithName("vchar_col")); http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/TestDatabaseLoader.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/TestDatabaseLoader.hpp b/query_optimizer/tests/TestDatabaseLoader.hpp index 27ef650..80dbfd2 100644 --- a/query_optimizer/tests/TestDatabaseLoader.hpp +++ b/query_optimizer/tests/TestDatabaseLoader.hpp @@ -111,6 +111,14 @@ class TestDatabaseLoader { CatalogRelation* createTestRelation(bool allow_vchar); /** + * @brief Creates four relations a(w INT, x INT, y INT, z INT), b(w INT, x INT), + * c(x INT, y INT) and d(y INT, z INT) for testing JOINs. The created + * relations are stored inside \p catalog_database_. + * @warning This can only be called once. + */ + void createJoinRelations(); + + /** * @brief Loads data into the test relation. The test relation has 25 tuples. * Each tuple is * ((-1)^x*x, x^2, sqrt(x), (-1)^x*x*sqrt(x), http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/execution_generator/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/execution_generator/CMakeLists.txt b/query_optimizer/tests/execution_generator/CMakeLists.txt index d70ea4c..149721c 100644 --- a/query_optimizer/tests/execution_generator/CMakeLists.txt +++ b/query_optimizer/tests/execution_generator/CMakeLists.txt @@ -43,6 +43,11 @@ add_test(quickstep_queryoptimizer_tests_executiongenerator_insert "${CMAKE_CURRENT_SOURCE_DIR}/Insert.test" "${CMAKE_CURRENT_BINARY_DIR}/Insert.test" "${CMAKE_CURRENT_BINARY_DIR}/Insert/") +add_test(quickstep_queryoptimizer_tests_executiongenerator_join + "../quickstep_queryoptimizer_tests_ExecutionGeneratorTest" + "${CMAKE_CURRENT_SOURCE_DIR}/Join.test" + "${CMAKE_CURRENT_BINARY_DIR}/Join.test" + "${CMAKE_CURRENT_BINARY_DIR}/Join/") add_test(quickstep_queryoptimizer_tests_executiongenerator_select "../quickstep_queryoptimizer_tests_ExecutionGeneratorTest" "${CMAKE_CURRENT_SOURCE_DIR}/Select.test" @@ -72,6 +77,7 @@ file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/Distinct) file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/Drop) file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/Index) file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/Insert) +file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/Join) file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/Select) file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/StringPatternMatching) file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/TableGenerator) http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/execution_generator/Join.test ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/execution_generator/Join.test b/query_optimizer/tests/execution_generator/Join.test new file mode 100644 index 0000000..6d6d2e1 --- /dev/null +++ b/query_optimizer/tests/execution_generator/Join.test @@ -0,0 +1,132 @@ +# Copyright 2016, Quickstep Research Group, Computer Sciences Department, +# University of WisconsinâMadison. +# +# Licensed 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. + +# Prepare testing relations +CREATE TABLE a(w INT, x LONG, y DOUBLE, z VARCHAR(16)); +CREATE TABLE b(w INT, x LONG); +CREATE TABLE c(x LONG, y DOUBLE); +CREATE TABLE d(y DOUBLE, z VARCHAR(16)); + +INSERT INTO a VALUES(0, 0, 0, 'C0'); +INSERT INTO a VALUES(1, 10, 100, 'C1'); +INSERT INTO a VALUES(2, 20, 200, 'C2'); +INSERT INTO a VALUES(3, 30, 300, 'C3'); +INSERT INTO a VALUES(4, 40, 400, 'C4'); +INSERT INTO a VALUES(5, 50, 500, 'C5'); +INSERT INTO a VALUES(6, 60, 600, 'C6'); +INSERT INTO a VALUES(7, 70, 700, 'C7'); +INSERT INTO a VALUES(8, 80, 800, 'C8'); +INSERT INTO a VALUES(9, 90, 900, 'C9'); +INSERT INTO a VALUES(10, 100, 1000, 'C10'); +INSERT INTO a VALUES(11, 110, 1100, 'C11'); +INSERT INTO a VALUES(12, 120, 1200, 'C12'); +INSERT INTO a VALUES(13, 130, 1300, 'C13'); +INSERT INTO a VALUES(14, 140, 1400, 'C14'); +INSERT INTO a VALUES(15, 150, 1500, 'C15'); +INSERT INTO a VALUES(16, 160, 1600, 'C16'); +INSERT INTO a VALUES(17, 170, 1700, 'C17'); +INSERT INTO a VALUES(18, 180, 1800, 'C18'); +INSERT INTO a VALUES(19, 190, 1900, 'C19'); + +INSERT INTO b +SELECT w, x + (w/2)%2 +FROM a +WHERE w % 2 = 0; + +INSERT INTO c +SELECT x, y + (x/3)%3-1 +FROM a +WHERE x % 3 = 0; + +INSERT INTO d +SELECT y, z +FROM a; +-- +== + + +# Join queries +SELECT a.w, b.x, c.y, d.z +FROM a JOIN b ON a.w = b.w + JOIN c ON a.x = c.x + JOIN d ON a.y = d.y; +-- ++-----------+--------------------+------------------------+----------------+ +|w |x |y |z | ++-----------+--------------------+------------------------+----------------+ +| 0| 0| -1| C0| +| 6| 61| 601| C6| +| 12| 120| 1200| C12| +| 18| 181| 1799| C18| ++-----------+--------------------+------------------------+----------------+ +== + +SELECT a.w, b.x, c.y +FROM a JOIN b ON (a.w = b.w OR a.x > b.x) + JOIN c ON (a.x = c.x AND a.y > c.y) + JOIN d ON (a.y = d.y OR a.z > d.z) +GROUP BY a.w, b.x, c.y +ORDER BY a.w, b.x, c.y; +-- ++-----------+--------------------+------------------------+ +|w |x |y | ++-----------+--------------------+------------------------+ +| 0| 0| -1| +| 9| 0| 899| +| 9| 21| 899| +| 9| 40| 899| +| 9| 61| 899| +| 9| 80| 899| +| 18| 0| 1799| +| 18| 21| 1799| +| 18| 40| 1799| +| 18| 61| 1799| +| 18| 80| 1799| +| 18| 101| 1799| +| 18| 120| 1799| +| 18| 141| 1799| +| 18| 160| 1799| +| 18| 181| 1799| ++-----------+--------------------+------------------------+ +== + +SELECT a1.w, b1.x, c1.y, d1.z +FROM a AS a1 JOIN b AS b1 ON a1.w = b1.w + JOIN c AS c1 ON a1.x = c1.x + JOIN d AS d1 ON a1.y = d1.y +WHERE a1.x = b1.x + AND a1.y = c1.y + AND a1.z = d1.z; +-- ++-----------+--------------------+------------------------+----------------+ +|w |x |y |z | ++-----------+--------------------+------------------------+----------------+ +| 12| 120| 1200| C12| ++-----------+--------------------+------------------------+----------------+ +== + +SELECT a1.w, b1.x, c1.y, d1.z +FROM a AS a1 JOIN b AS b1 ON a1.x <> b1.x + JOIN c AS c1 ON a1.y <> c1.y + JOIN d AS d1 ON a1.z = d1.z +WHERE a1.w = b1.w + AND a1.x = c1.x; +-- ++-----------+--------------------+------------------------+----------------+ +|w |x |y |z | ++-----------+--------------------+------------------------+----------------+ +| 6| 61| 601| C6| +| 18| 181| 1799| C18| ++-----------+--------------------+------------------------+----------------+ http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/logical_generator/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/logical_generator/CMakeLists.txt b/query_optimizer/tests/logical_generator/CMakeLists.txt index 08aba11..4edddfa 100644 --- a/query_optimizer/tests/logical_generator/CMakeLists.txt +++ b/query_optimizer/tests/logical_generator/CMakeLists.txt @@ -17,12 +17,14 @@ add_test(quickstep_queryoptimizer_tests_logicalgenerator_create "../quickstep_queryoptimizer_tests_OptimizerTextTest" "${CMAKE_CURRENT_SOURCE_DIR}/Create.test" "${CMAKE_CURRENT_BINARY_DIR}/Create.test") - - add_test(quickstep_queryoptimizer_tests_logicalgenerator_index - "../quickstep_queryoptimizer_tests_OptimizerTextTest" - "${CMAKE_CURRENT_SOURCE_DIR}/Index.test" - "${CMAKE_CURRENT_BINARY_DIR}/Index.test") - +add_test(quickstep_queryoptimizer_tests_logicalgenerator_index + "../quickstep_queryoptimizer_tests_OptimizerTextTest" + "${CMAKE_CURRENT_SOURCE_DIR}/Index.test" + "${CMAKE_CURRENT_BINARY_DIR}/Index.test") +add_test(quickstep_queryoptimizer_tests_logicalgenerator_join + "../quickstep_queryoptimizer_tests_OptimizerTextTest" + "${CMAKE_CURRENT_SOURCE_DIR}/Join.test" + "${CMAKE_CURRENT_BINARY_DIR}/Join.test") add_test(quickstep_queryoptimizer_tests_logicalgenerator_select "../quickstep_queryoptimizer_tests_OptimizerTextTest" "${CMAKE_CURRENT_SOURCE_DIR}/Select.test" http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/logical_generator/Join.test ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/logical_generator/Join.test b/query_optimizer/tests/logical_generator/Join.test new file mode 100644 index 0000000..d48df4c --- /dev/null +++ b/query_optimizer/tests/logical_generator/Join.test @@ -0,0 +1,217 @@ +# Copyright 2016, Quickstep Research Group, Computer Sciences Department, +# University of WisconsinâMadison. +# +# Licensed 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. + +[default optimized_logical_plan] + +SELECT a.z +FROM a JOIN b ON a.w = b.w + JOIN c ON a.x = c.x + JOIN d ON a.y = d.y; +-- +TopLevelPlan ++-plan=Project +| +-input=HashJoin +| | +-left=HashJoin +| | | +-left=HashJoin +| | | | +-left=TableReference[relation_name=a] +| | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | | | +-right=TableReference[relation_name=b] +| | | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | | +-left_join_attributes= +| | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | +-right_join_attributes= +| | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | +-right=TableReference[relation_name=c] +| | | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | | +-left_join_attributes= +| | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | +-right_join_attributes= +| | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | +-right=TableReference[relation_name=d] +| | | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| | +-left_join_attributes= +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | +-right_join_attributes= +| | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| +-project_list= +| +-AttributeReference[id=3,name=z,relation=a,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a,type=Int] +== + +SELECT a.z +FROM a JOIN b ON (a.w = b.w OR a.x > b.x) + JOIN c ON (a.x = c.x AND a.y > c.y) + JOIN d ON (a.y = d.y OR a.z > d.z); +-- +TopLevelPlan ++-plan=Project +| +-input=NestedLoopsJoin +| | +-left=Filter +| | | +-input=HashJoin +| | | | +-left=NestedLoopsJoin +| | | | | +-left=TableReference[relation_name=a] +| | | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | | | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | | | | +-right=TableReference[relation_name=b] +| | | | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | | | +-join_predicate=Or +| | | | | +-Equal +| | | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | | +-Greater +| | | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | | +-right=TableReference[relation_name=c] +| | | | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | | | +-left_join_attributes= +| | | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | +-right_join_attributes= +| | | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | +-filter_predicate=Greater +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | +-right=TableReference[relation_name=d] +| | | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| | +-join_predicate=Or +| | +-Equal +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | +-Greater +| | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| +-project_list= +| +-AttributeReference[id=3,name=z,relation=a,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a,type=Int] +== + +SELECT a1.z +FROM a AS a1 JOIN b AS b1 ON a1.w = b1.w + JOIN c AS c1 ON a1.x = c1.x + JOIN d AS d1 ON a1.y = d1.y +WHERE a1.x = b1.x + AND a1.y = c1.y + AND a1.z = d1.z; +-- +TopLevelPlan ++-plan=Project +| +-input=HashJoin +| | +-left=HashJoin +| | | +-left=HashJoin +| | | | +-left=TableReference[relation_name=a,relation_alias=a1] +| | | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | | +-right=TableReference[relation_name=b,relation_alias=b1] +| | | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | | | +-left_join_attributes= +| | | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | +-right_join_attributes= +| | | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | +-right=TableReference[relation_name=c,relation_alias=c1] +| | | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | | | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| | | +-left_join_attributes= +| | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | +-right_join_attributes= +| | | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | +-right=TableReference[relation_name=d,relation_alias=d1] +| | | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| | | +-AttributeReference[id=9,name=z,relation=d1,type=Int] +| | +-left_join_attributes= +| | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | +-right_join_attributes= +| | +-AttributeReference[id=9,name=z,relation=d1,type=Int] +| | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| +-project_list= +| +-AttributeReference[id=3,name=z,relation=a1,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a1,type=Int] +== + +SELECT a1.z +FROM a AS a1 JOIN b AS b1 ON a1.w <> b1.w + JOIN c AS c1 ON a1.x <> c1.x + JOIN d AS d1 ON a1.y <> d1.y +WHERE a1.x = b1.x + AND a1.y = c1.y + AND a1.z = d1.z; +-- +TopLevelPlan ++-plan=Project +| +-input=Filter +| | +-input=HashJoin +| | | +-left=Filter +| | | | +-input=HashJoin +| | | | | +-left=Filter +| | | | | | +-input=HashJoin +| | | | | | | +-left=TableReference[relation_name=a,relation_alias=a1] +| | | | | | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | | | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | | | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | | | | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | | | | | +-right=TableReference[relation_name=b,relation_alias=b1] +| | | | | | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | | | | | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | | | | | | +-left_join_attributes= +| | | | | | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | | | | +-right_join_attributes= +| | | | | | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | | | | | +-filter_predicate=NotEqual +| | | | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | | | +-right=TableReference[relation_name=c,relation_alias=c1] +| | | | | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | | | | | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| | | | | +-left_join_attributes= +| | | | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | | +-right_join_attributes= +| | | | | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| | | | +-filter_predicate=NotEqual +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | | +-right=TableReference[relation_name=d,relation_alias=d1] +| | | | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| | | | +-AttributeReference[id=9,name=z,relation=d1,type=Int] +| | | +-left_join_attributes= +| | | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | +-right_join_attributes= +| | | +-AttributeReference[id=9,name=z,relation=d1,type=Int] +| | +-filter_predicate=NotEqual +| | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| +-project_list= +| +-AttributeReference[id=3,name=z,relation=a1,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a1,type=Int] http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/physical_generator/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/physical_generator/CMakeLists.txt b/query_optimizer/tests/physical_generator/CMakeLists.txt index c01b133..abc6d9b 100644 --- a/query_optimizer/tests/physical_generator/CMakeLists.txt +++ b/query_optimizer/tests/physical_generator/CMakeLists.txt @@ -37,6 +37,10 @@ add_test(quickstep_queryoptimizer_tests_physicalgenerator_insert "../quickstep_queryoptimizer_tests_OptimizerTextTest" "${CMAKE_CURRENT_SOURCE_DIR}/Insert.test" "${CMAKE_CURRENT_BINARY_DIR}/Insert.test") +add_test(quickstep_queryoptimizer_tests_physicalgenerator_join + "../quickstep_queryoptimizer_tests_OptimizerTextTest" + "${CMAKE_CURRENT_SOURCE_DIR}/Join.test" + "${CMAKE_CURRENT_BINARY_DIR}/Join.test") add_test(quickstep_queryoptimizer_tests_physicalgenerator_select "../quickstep_queryoptimizer_tests_OptimizerTextTest" "${CMAKE_CURRENT_SOURCE_DIR}/Select.test" http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/physical_generator/Join.test ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/physical_generator/Join.test b/query_optimizer/tests/physical_generator/Join.test new file mode 100644 index 0000000..c1f49b0 --- /dev/null +++ b/query_optimizer/tests/physical_generator/Join.test @@ -0,0 +1,237 @@ +# Copyright 2016, Quickstep Research Group, Computer Sciences Department, +# University of WisconsinâMadison. +# +# Licensed 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. + +[default physical_plan] + +SELECT a.z +FROM a JOIN b ON a.w = b.w + JOIN c ON a.x = c.x + JOIN d ON a.y = d.y; +-- +TopLevelPlan ++-plan=HashJoin +| +-left=HashJoin +| | +-left=HashJoin +| | | +-left=TableReference[relation=a] +| | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | | +-right=TableReference[relation=b] +| | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | +-project_expressions= +| | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | | +-left_join_attributes= +| | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | +-right_join_attributes= +| | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | +-right=TableReference[relation=c] +| | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | +-project_expressions= +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | +-left_join_attributes= +| | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | +-right_join_attributes= +| | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| +-right=TableReference[relation=d] +| | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| +-project_expressions= +| | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| +-left_join_attributes= +| | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| +-right_join_attributes= +| +-AttributeReference[id=8,name=y,relation=d,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a,type=Int] +== + +SELECT a.z +FROM a JOIN b ON (a.w = b.w OR a.x > b.x) + JOIN c ON (a.x = c.x AND a.y > c.y) + JOIN d ON (a.y = d.y OR a.z > d.z); +-- +TopLevelPlan ++-plan=NestedLoopsJoin +| +-left=HashJoin +| | +-left=NestedLoopsJoin +| | | +-left=TableReference[relation=a] +| | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | | +-right=TableReference[relation=b] +| | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | +-join_predicate=Or +| | | | +-Equal +| | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | +-Greater +| | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | +-project_expressions= +| | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | +-right=TableReference[relation=c] +| | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | +-residual_predicate=Greater +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | +-project_expressions= +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | +-left_join_attributes= +| | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | +-right_join_attributes= +| | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| +-right=TableReference[relation=d] +| | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| +-join_predicate=Or +| | +-Equal +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | +-Greater +| | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| +-project_expressions= +| +-AttributeReference[id=3,name=z,relation=a,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a,type=Int] +== + +SELECT a1.z +FROM a AS a1 JOIN b AS b1 ON a1.w = b1.w + JOIN c AS c1 ON a1.x = c1.x + JOIN d AS d1 ON a1.y = d1.y +WHERE a1.x = b1.x + AND a1.y = c1.y + AND a1.z = d1.z; +-- +TopLevelPlan ++-plan=HashJoin +| +-left=HashJoin +| | +-left=HashJoin +| | | +-left=TableReference[relation=a,alias=a1] +| | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | +-right=TableReference[relation=b,alias=b1] +| | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | | +-project_expressions= +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | +-left_join_attributes= +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | +-right_join_attributes= +| | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | +-right=TableReference[relation=c,alias=c1] +| | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| | +-project_expressions= +| | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | +-left_join_attributes= +| | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | +-right_join_attributes= +| | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| +-right=TableReference[relation=d,alias=d1] +| | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| | +-AttributeReference[id=9,name=z,relation=d1,type=Int] +| +-project_expressions= +| | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| +-left_join_attributes= +| | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| +-right_join_attributes= +| +-AttributeReference[id=9,name=z,relation=d1,type=Int] +| +-AttributeReference[id=8,name=y,relation=d1,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a1,type=Int] +== + +SELECT a1.z +FROM a AS a1 JOIN b AS b1 ON a1.w <> b1.w + JOIN c AS c1 ON a1.x <> c1.x + JOIN d AS d1 ON a1.y <> d1.y +WHERE a1.x = b1.x + AND a1.y = c1.y + AND a1.z = d1.z; +-- +TopLevelPlan ++-plan=HashJoin +| +-left=HashJoin +| | +-left=HashJoin +| | | +-left=TableReference[relation=a,alias=a1] +| | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | +-right=TableReference[relation=b,alias=b1] +| | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | | +-residual_predicate=NotEqual +| | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | +-project_expressions= +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | +-left_join_attributes= +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | +-right_join_attributes= +| | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | +-right=TableReference[relation=c,alias=c1] +| | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| | +-residual_predicate=NotEqual +| | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | +-project_expressions= +| | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | +-left_join_attributes= +| | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | +-right_join_attributes= +| | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| +-right=TableReference[relation=d,alias=d1] +| | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| | +-AttributeReference[id=9,name=z,relation=d1,type=Int] +| +-residual_predicate=NotEqual +| | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| +-project_expressions= +| | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| +-left_join_attributes= +| | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| +-right_join_attributes= +| +-AttributeReference[id=9,name=z,relation=d1,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a1,type=Int] http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/resolver/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/resolver/CMakeLists.txt b/query_optimizer/tests/resolver/CMakeLists.txt index bc9725c..4d5a504 100644 --- a/query_optimizer/tests/resolver/CMakeLists.txt +++ b/query_optimizer/tests/resolver/CMakeLists.txt @@ -41,6 +41,10 @@ add_test(quickstep_queryoptimizer_tests_resolver_insert "../quickstep_queryoptimizer_tests_OptimizerTextTest" "${CMAKE_CURRENT_SOURCE_DIR}/Insert.test" "${CMAKE_CURRENT_BINARY_DIR}/Insert.test") +add_test(quickstep_queryoptimizer_tests_resolver_join + "../quickstep_queryoptimizer_tests_OptimizerTextTest" + "${CMAKE_CURRENT_SOURCE_DIR}/Join.test" + "${CMAKE_CURRENT_BINARY_DIR}/Join.test") add_test(quickstep_queryoptimizer_tests_resolver_select "../quickstep_queryoptimizer_tests_OptimizerTextTest" "${CMAKE_CURRENT_SOURCE_DIR}/Select.test" http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e87cabf4/query_optimizer/tests/resolver/Join.test ---------------------------------------------------------------------- diff --git a/query_optimizer/tests/resolver/Join.test b/query_optimizer/tests/resolver/Join.test new file mode 100644 index 0000000..f501f97 --- /dev/null +++ b/query_optimizer/tests/resolver/Join.test @@ -0,0 +1,172 @@ +# Copyright 2016, Quickstep Research Group, Computer Sciences Department, +# University of WisconsinâMadison. +# +# Licensed 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. + +[default initial_logical_plan] + +SELECT a.z +FROM a JOIN b ON a.w = b.w + JOIN c ON a.x = c.x + JOIN d ON a.y = d.y; +-- +TopLevelPlan ++-plan=Project +| +-input=Filter +| | +-input=MultiwayCartesianJoin +| | | +-Filter +| | | | +-input=MultiwayCartesianJoin +| | | | | +-Filter +| | | | | | +-input=MultiwayCartesianJoin +| | | | | | | +-TableReference[relation_name=a] +| | | | | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | | | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | | | | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | | | | | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | | | | | | +-TableReference[relation_name=b] +| | | | | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | | | | +-filter_predicate=Equal +| | | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | | +-TableReference[relation_name=c] +| | | | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | | | +-filter_predicate=Equal +| | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | +-TableReference[relation_name=d] +| | | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| | +-filter_predicate=Equal +| | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| +-project_list= +| +-AttributeReference[id=3,name=z,relation=a,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a,type=Int] +== + +SELECT a.z +FROM a JOIN b ON (a.w = b.w OR a.x > b.x) + JOIN c ON (a.x = c.x OR a.y > c.y) + JOIN d ON (a.y = d.y OR a.z > d.z); +-- +TopLevelPlan ++-plan=Project +| +-input=Filter +| | +-input=MultiwayCartesianJoin +| | | +-Filter +| | | | +-input=MultiwayCartesianJoin +| | | | | +-Filter +| | | | | | +-input=MultiwayCartesianJoin +| | | | | | | +-TableReference[relation_name=a] +| | | | | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | | | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | | | | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | | | | | | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | | | | | | +-TableReference[relation_name=b] +| | | | | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | | | | +-filter_predicate=Or +| | | | | | +-Equal +| | | | | | | +-AttributeReference[id=0,name=w,relation=a,type=Int] +| | | | | | | +-AttributeReference[id=4,name=w,relation=b,type=Int] +| | | | | | +-Greater +| | | | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | | | +-AttributeReference[id=5,name=x,relation=b,type=Int] +| | | | | +-TableReference[relation_name=c] +| | | | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | | | +-filter_predicate=Or +| | | | +-Equal +| | | | | +-AttributeReference[id=1,name=x,relation=a,type=Int] +| | | | | +-AttributeReference[id=6,name=x,relation=c,type=Int] +| | | | +-Greater +| | | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | | +-AttributeReference[id=7,name=y,relation=c,type=Int] +| | | +-TableReference[relation_name=d] +| | | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| | +-filter_predicate=Or +| | +-Equal +| | | +-AttributeReference[id=2,name=y,relation=a,type=Int] +| | | +-AttributeReference[id=8,name=y,relation=d,type=Int] +| | +-Greater +| | +-AttributeReference[id=3,name=z,relation=a,type=Int] +| | +-AttributeReference[id=9,name=z,relation=d,type=Int] +| +-project_list= +| +-AttributeReference[id=3,name=z,relation=a,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a,type=Int] +== + +SELECT a1.z +FROM a AS a1 JOIN b AS b1 ON a1.w = b1.w + JOIN c AS c1 ON a1.x = c1.x + JOIN d AS d1 ON a1.y = d1.y; +WHERE a1.x = b1.x + AND a1.y = c1.y + AND a1.z = d1.z; +-- +TopLevelPlan ++-plan=Project +| +-input=Filter +| | +-input=MultiwayCartesianJoin +| | | +-Filter +| | | | +-input=MultiwayCartesianJoin +| | | | | +-Filter +| | | | | | +-input=MultiwayCartesianJoin +| | | | | | | +-TableReference[relation_name=a,relation_alias=a1] +| | | | | | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | | | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | | | | | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | | | | | | | +-AttributeReference[id=3,name=z,relation=a1,type=Int] +| | | | | | | +-TableReference[relation_name=b,relation_alias=b1] +| | | | | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | | | | | +-AttributeReference[id=5,name=x,relation=b1,type=Int] +| | | | | | +-filter_predicate=Equal +| | | | | | +-AttributeReference[id=0,name=w,relation=a1,type=Int] +| | | | | | +-AttributeReference[id=4,name=w,relation=b1,type=Int] +| | | | | +-TableReference[relation_name=c,relation_alias=c1] +| | | | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | | | | +-AttributeReference[id=7,name=y,relation=c1,type=Int] +| | | | +-filter_predicate=Equal +| | | | +-AttributeReference[id=1,name=x,relation=a1,type=Int] +| | | | +-AttributeReference[id=6,name=x,relation=c1,type=Int] +| | | +-TableReference[relation_name=d,relation_alias=d1] +| | | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| | | +-AttributeReference[id=9,name=z,relation=d1,type=Int] +| | +-filter_predicate=Equal +| | +-AttributeReference[id=2,name=y,relation=a1,type=Int] +| | +-AttributeReference[id=8,name=y,relation=d1,type=Int] +| +-project_list= +| +-AttributeReference[id=3,name=z,relation=a1,type=Int] ++-output_attributes= + +-AttributeReference[id=3,name=z,relation=a1,type=Int] +== + +SELECT * +FROM b LEFT JOIN c ON b.x = c.x JOIN d ON c.y = d.y; +-- +ERROR: Outer joins are not supported yet (2 : 13) +FROM b LEFT JOIN c ON b.x = c.x JOIN d ON ... + ^ +== + +SELECT * +FROM b LEFT JOIN (c JOIN d ON c.y = d.y) ON b.x = c.x; +-- +ERROR: Outer joins are not supported yet (2 : 13) +FROM b LEFT JOIN (c JOIN d ON c.y = d.y) O... + ^
