OmniSciDB  cde582ebc3
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
EquiJoinCondition.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2022 HEAVY.AI, 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  */
16 
18 
19 #include "Analyzer/Analyzer.h"
22 
23 namespace {
24 
25 // Returns true iff crt and prev are both equi-join conditions on the same pair of tables.
26 bool can_combine_with(const Analyzer::Expr* crt, const Analyzer::Expr* prev) {
27  const auto crt_bin = dynamic_cast<const Analyzer::BinOper*>(crt);
28  const auto prev_bin = dynamic_cast<const Analyzer::BinOper*>(prev);
29  if (!crt_bin || !prev_bin) {
30  return false;
31  }
32  if (!IS_EQUIVALENCE(crt_bin->get_optype()) || crt_bin->get_qualifier() != kONE ||
33  !IS_EQUIVALENCE(prev_bin->get_optype()) || prev_bin->get_qualifier() != kONE ||
34  // We could accept a mix of kEQ and kBW_EQ, but don't bother for now.
35  crt_bin->get_optype() != prev_bin->get_optype()) {
36  return false;
37  }
38 
39  auto get_rhs_col_var = [](const auto bin_oper) {
40  auto inner_col_var = std::dynamic_pointer_cast<Analyzer::ColumnVar>(
41  remove_cast(bin_oper->get_own_right_operand()));
42  if (!inner_col_var) {
43  const auto string_oper = std::dynamic_pointer_cast<Analyzer::StringOper>(
44  remove_cast(bin_oper->get_own_right_operand()));
45  if (string_oper && string_oper->getArity() >= 1UL) {
46  inner_col_var =
47  std::dynamic_pointer_cast<Analyzer::ColumnVar>(string_oper->getOwnArg(0));
48  }
49  }
50  return inner_col_var;
51  };
52 
53  const std::shared_ptr<Analyzer::ColumnVar> crt_inner_col_var = get_rhs_col_var(crt_bin);
54  const std::shared_ptr<Analyzer::ColumnVar> prev_inner_col_var =
55  get_rhs_col_var(prev_bin);
56  if (!crt_inner_col_var || !prev_inner_col_var) {
57  return false;
58  }
60  const auto crt_outer_rte_set = visitor.visit(crt_bin->get_left_operand());
61  const auto prev_outer_rte_set = visitor.visit(prev_bin->get_left_operand());
62  // We shouldn't treat mixed nesting levels columns as a composite key tuple.
63  if (crt_outer_rte_set.size() != 1 || prev_outer_rte_set.size() != 1 ||
64  crt_outer_rte_set != prev_outer_rte_set) {
65  return false;
66  }
67  if (crt_inner_col_var->get_table_id() != prev_inner_col_var->get_table_id() ||
68  crt_inner_col_var->get_rte_idx() != prev_inner_col_var->get_rte_idx()) {
69  return false;
70  }
71  return true;
72 }
73 
74 std::list<std::shared_ptr<Analyzer::Expr>> make_composite_equals_impl(
75  const std::vector<std::shared_ptr<Analyzer::Expr>>& crt_coalesced_quals) {
76  std::list<std::shared_ptr<Analyzer::Expr>> join_quals;
77  std::vector<std::shared_ptr<Analyzer::Expr>> lhs_tuple;
78  std::vector<std::shared_ptr<Analyzer::Expr>> rhs_tuple;
79  bool not_null{true};
80  for (const auto& qual : crt_coalesced_quals) {
81  const auto qual_binary = std::dynamic_pointer_cast<Analyzer::BinOper>(qual);
82  CHECK(qual_binary);
83  not_null = not_null && qual_binary->get_type_info().get_notnull();
84  const auto lhs_col = remove_cast(qual_binary->get_own_left_operand());
85  const auto rhs_col = remove_cast(qual_binary->get_own_right_operand());
86  const auto lhs_ti = lhs_col->get_type_info();
87  // Coalesce cols for integers, bool, and dict encoded strings. Forces baseline hash
88  // join.
89  if (IS_NUMBER(lhs_ti.get_type()) ||
90  (IS_STRING(lhs_ti.get_type()) && lhs_ti.get_compression() == kENCODING_DICT) ||
91  (lhs_ti.get_type() == kBOOLEAN)) {
92  lhs_tuple.push_back(lhs_col);
93  rhs_tuple.push_back(rhs_col);
94  } else {
95  join_quals.push_back(qual);
96  }
97  }
98  CHECK(!crt_coalesced_quals.empty());
99  const auto first_qual =
100  std::dynamic_pointer_cast<Analyzer::BinOper>(crt_coalesced_quals.front());
101  CHECK(first_qual);
102  CHECK_EQ(lhs_tuple.size(), rhs_tuple.size());
103  if (lhs_tuple.size() > 0) {
104  join_quals.push_front(std::make_shared<Analyzer::BinOper>(
105  SQLTypeInfo(kBOOLEAN, not_null),
106  false,
107  first_qual->get_optype(),
108  kONE,
109  lhs_tuple.size() > 1 ? std::make_shared<Analyzer::ExpressionTuple>(lhs_tuple)
110  : lhs_tuple.front(),
111  rhs_tuple.size() > 1 ? std::make_shared<Analyzer::ExpressionTuple>(rhs_tuple)
112  : rhs_tuple.front()));
113  }
114  return join_quals;
115 }
116 
117 // Create an equals expression with column tuple operands out of regular equals
118 // expressions.
119 std::list<std::shared_ptr<Analyzer::Expr>> make_composite_equals(
120  const std::vector<std::shared_ptr<Analyzer::Expr>>& crt_coalesced_quals) {
121  if (crt_coalesced_quals.size() == 1) {
122  return {crt_coalesced_quals.front()};
123  }
124  return make_composite_equals_impl(crt_coalesced_quals);
125 }
126 
127 } // namespace
128 
129 std::list<std::shared_ptr<Analyzer::Expr>> combine_equi_join_conditions(
130  const std::list<std::shared_ptr<Analyzer::Expr>>& join_quals) {
131  if (join_quals.empty()) {
132  return {};
133  }
134  std::list<std::shared_ptr<Analyzer::Expr>> coalesced_quals;
135  std::vector<std::shared_ptr<Analyzer::Expr>> crt_coalesced_quals;
136  for (const auto& simple_join_qual : join_quals) {
137  if (crt_coalesced_quals.empty()) {
138  crt_coalesced_quals.push_back(simple_join_qual);
139  continue;
140  }
141  if (crt_coalesced_quals.size() >= g_maximum_conditions_to_coalesce ||
142  !can_combine_with(simple_join_qual.get(), crt_coalesced_quals.back().get())) {
143  coalesced_quals.splice(coalesced_quals.end(),
144  make_composite_equals(crt_coalesced_quals));
145  crt_coalesced_quals.clear();
146  }
147  crt_coalesced_quals.push_back(simple_join_qual);
148  }
149  if (!crt_coalesced_quals.empty()) {
150  coalesced_quals.splice(coalesced_quals.end(),
151  make_composite_equals(crt_coalesced_quals));
152  }
153  return coalesced_quals;
154 }
155 
156 std::list<std::shared_ptr<Analyzer::Expr>> coalesce_singleton_equi_join(
157  const std::shared_ptr<Analyzer::BinOper>& join_qual) {
158  std::vector<std::shared_ptr<Analyzer::Expr>> singleton_qual_list;
159  singleton_qual_list.push_back(join_qual);
160  return make_composite_equals_impl(singleton_qual_list);
161 }
Defines data structures for the semantic analysis phase of query processing.
#define CHECK_EQ(x, y)
Definition: Logger.h:230
std::shared_ptr< Analyzer::Expr > remove_cast(const std::shared_ptr< Analyzer::Expr > &expr)
Definition: Analyzer.cpp:4196
#define IS_EQUIVALENCE(X)
Definition: sqldefs.h:68
std::list< std::shared_ptr< Analyzer::Expr > > coalesce_singleton_equi_join(const std::shared_ptr< Analyzer::BinOper > &join_qual)
T visit(const Analyzer::Expr *expr) const
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:70
Expression class for string functions The &quot;arg&quot; constructor parameter must be an expression that reso...
Definition: Analyzer.h:1463
#define IS_STRING(T)
Definition: sqltypes.h:250
#define CHECK(condition)
Definition: Logger.h:222
const size_t g_maximum_conditions_to_coalesce
#define IS_NUMBER(T)
Definition: sqltypes.h:247
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)