OmniSciDB  8a228a1076
EquiJoinCondition.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2017 MapD Technologies, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
17 
18 #include "Analyzer/Analyzer.h"
21 
22 namespace {
23 
24 // Returns true iff crt and prev are both equi-join conditions on the same pair of tables.
25 bool can_combine_with(const Analyzer::Expr* crt, const Analyzer::Expr* prev) {
26  const auto crt_bin = dynamic_cast<const Analyzer::BinOper*>(crt);
27  const auto prev_bin = dynamic_cast<const Analyzer::BinOper*>(prev);
28  if (!crt_bin || !prev_bin) {
29  return false;
30  }
31  if (!IS_EQUIVALENCE(crt_bin->get_optype()) || crt_bin->get_qualifier() != kONE ||
32  !IS_EQUIVALENCE(prev_bin->get_optype()) || prev_bin->get_qualifier() != kONE ||
33  // We could accept a mix of kEQ and kBW_EQ, but don't bother for now.
34  crt_bin->get_optype() != prev_bin->get_optype()) {
35  return false;
36  }
37  const auto crt_inner = std::dynamic_pointer_cast<Analyzer::ColumnVar>(
38  remove_cast(crt_bin->get_own_right_operand()));
39  const auto prev_inner = std::dynamic_pointer_cast<Analyzer::ColumnVar>(
40  remove_cast(prev_bin->get_own_right_operand()));
42  const auto crt_outer_rte_set = visitor.visit(crt_bin->get_left_operand());
43  const auto prev_outer_rte_set = visitor.visit(prev_bin->get_left_operand());
44  // We shouldn't treat mixed nesting levels columns as a composite key tuple.
45  if (crt_outer_rte_set.size() != 1 || prev_outer_rte_set.size() != 1 ||
46  crt_outer_rte_set != prev_outer_rte_set) {
47  return false;
48  }
49  if (!crt_inner || !prev_inner ||
50  crt_inner->get_table_id() != prev_inner->get_table_id() ||
51  crt_inner->get_rte_idx() != prev_inner->get_rte_idx()) {
52  return false;
53  }
54  return true;
55 }
56 
57 std::list<std::shared_ptr<Analyzer::Expr>> make_composite_equals_impl(
58  const std::vector<std::shared_ptr<Analyzer::Expr>>& crt_coalesced_quals) {
59  std::list<std::shared_ptr<Analyzer::Expr>> join_quals;
60  std::vector<std::shared_ptr<Analyzer::Expr>> lhs_tuple;
61  std::vector<std::shared_ptr<Analyzer::Expr>> rhs_tuple;
62  bool not_null{true};
63  for (const auto& qual : crt_coalesced_quals) {
64  const auto qual_binary = std::dynamic_pointer_cast<Analyzer::BinOper>(qual);
65  CHECK(qual_binary);
66  not_null = not_null && qual_binary->get_type_info().get_notnull();
67  const auto lhs_col = remove_cast(qual_binary->get_own_left_operand());
68  const auto rhs_col = remove_cast(qual_binary->get_own_right_operand());
69  const auto lhs_ti = lhs_col->get_type_info();
70  // Coalesce cols for integers, bool, and dict encoded strings. Forces baseline hash
71  // join.
72  if (IS_NUMBER(lhs_ti.get_type()) ||
73  (IS_STRING(lhs_ti.get_type()) && lhs_ti.get_compression() == kENCODING_DICT) ||
74  (lhs_ti.get_type() == kBOOLEAN)) {
75  lhs_tuple.push_back(lhs_col);
76  rhs_tuple.push_back(rhs_col);
77  } else {
78  join_quals.push_back(qual);
79  }
80  }
81  CHECK(!crt_coalesced_quals.empty());
82  const auto first_qual =
83  std::dynamic_pointer_cast<Analyzer::BinOper>(crt_coalesced_quals.front());
84  CHECK(first_qual);
85  CHECK_EQ(lhs_tuple.size(), rhs_tuple.size());
86  if (lhs_tuple.size() > 0) {
87  join_quals.push_front(std::make_shared<Analyzer::BinOper>(
88  SQLTypeInfo(kBOOLEAN, not_null),
89  false,
90  first_qual->get_optype(),
91  kONE,
92  lhs_tuple.size() > 1 ? std::make_shared<Analyzer::ExpressionTuple>(lhs_tuple)
93  : lhs_tuple.front(),
94  rhs_tuple.size() > 1 ? std::make_shared<Analyzer::ExpressionTuple>(rhs_tuple)
95  : rhs_tuple.front()));
96  }
97  return join_quals;
98 }
99 
100 // Create an equals expression with column tuple operands out of regular equals
101 // expressions.
102 std::list<std::shared_ptr<Analyzer::Expr>> make_composite_equals(
103  const std::vector<std::shared_ptr<Analyzer::Expr>>& crt_coalesced_quals) {
104  if (crt_coalesced_quals.size() == 1) {
105  return {crt_coalesced_quals.front()};
106  }
107  return make_composite_equals_impl(crt_coalesced_quals);
108 }
109 
110 } // namespace
111 
112 std::list<std::shared_ptr<Analyzer::Expr>> combine_equi_join_conditions(
113  const std::list<std::shared_ptr<Analyzer::Expr>>& join_quals) {
114  if (join_quals.empty()) {
115  return {};
116  }
117  std::list<std::shared_ptr<Analyzer::Expr>> coalesced_quals;
118  std::vector<std::shared_ptr<Analyzer::Expr>> crt_coalesced_quals;
119  for (const auto& simple_join_qual : join_quals) {
120  if (crt_coalesced_quals.empty()) {
121  crt_coalesced_quals.push_back(simple_join_qual);
122  continue;
123  }
124  if (crt_coalesced_quals.size() >= g_maximum_conditions_to_coalesce ||
125  !can_combine_with(simple_join_qual.get(), crt_coalesced_quals.back().get())) {
126  coalesced_quals.splice(coalesced_quals.end(),
127  make_composite_equals(crt_coalesced_quals));
128  crt_coalesced_quals.clear();
129  }
130  crt_coalesced_quals.push_back(simple_join_qual);
131  }
132  if (!crt_coalesced_quals.empty()) {
133  coalesced_quals.splice(coalesced_quals.end(),
134  make_composite_equals(crt_coalesced_quals));
135  }
136  return coalesced_quals;
137 }
138 
139 std::list<std::shared_ptr<Analyzer::Expr>> coalesce_singleton_equi_join(
140  const std::shared_ptr<Analyzer::BinOper>& join_qual) {
141  std::vector<std::shared_ptr<Analyzer::Expr>> singleton_qual_list;
142  singleton_qual_list.push_back(join_qual);
143  return make_composite_equals_impl(singleton_qual_list);
144 }
Defines data structures for the semantic analysis phase of query processing.
#define CHECK_EQ(x, y)
Definition: Logger.h:205
std::shared_ptr< Analyzer::Expr > remove_cast(const std::shared_ptr< Analyzer::Expr > &expr)
Definition: Analyzer.cpp:3241
#define IS_EQUIVALENCE(X)
Definition: sqldefs.h:67
std::list< std::shared_ptr< Analyzer::Expr > > coalesce_singleton_equi_join(const std::shared_ptr< Analyzer::BinOper > &join_qual)
std::list< std::shared_ptr< Analyzer::Expr > > make_composite_equals(const std::vector< std::shared_ptr< Analyzer::Expr >> &crt_coalesced_quals)
bool can_combine_with(const Analyzer::Expr *crt, const Analyzer::Expr *prev)
Definition: sqldefs.h:69
T visit(const Analyzer::Expr *expr) const
#define IS_STRING(T)
Definition: sqltypes.h:173
#define CHECK(condition)
Definition: Logger.h:197
const size_t g_maximum_conditions_to_coalesce
#define IS_NUMBER(T)
Definition: sqltypes.h:170
std::list< std::shared_ptr< Analyzer::Expr > > make_composite_equals_impl(const std::vector< std::shared_ptr< Analyzer::Expr >> &crt_coalesced_quals)
std::list< std::shared_ptr< Analyzer::Expr > > combine_equi_join_conditions(const std::list< std::shared_ptr< Analyzer::Expr >> &join_quals)