OmniSciDB  5ade3759e0
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  */
16 #include "EquiJoinCondition.h"
17 #include "Analyzer/Analyzer.h"
18 #include "HashJoinRuntime.h"
19 #include "RangeTableIndexVisitor.h"
20 
21 namespace {
22 
23 // Returns true iff crt and prev are both equi-join conditions on the same pair of tables.
24 bool can_combine_with(const Analyzer::Expr* crt, const Analyzer::Expr* prev) {
25  const auto crt_bin = dynamic_cast<const Analyzer::BinOper*>(crt);
26  const auto prev_bin = dynamic_cast<const Analyzer::BinOper*>(prev);
27  if (!crt_bin || !prev_bin) {
28  return false;
29  }
30  if (!IS_EQUIVALENCE(crt_bin->get_optype()) || crt_bin->get_qualifier() != kONE ||
31  !IS_EQUIVALENCE(prev_bin->get_optype()) || prev_bin->get_qualifier() != kONE ||
32  // We could accept a mix of kEQ and kBW_EQ, but don't bother for now.
33  crt_bin->get_optype() != prev_bin->get_optype()) {
34  return false;
35  }
36  const auto crt_inner = std::dynamic_pointer_cast<Analyzer::ColumnVar>(
37  remove_cast(crt_bin->get_own_right_operand()));
38  const auto prev_inner = std::dynamic_pointer_cast<Analyzer::ColumnVar>(
39  remove_cast(prev_bin->get_own_right_operand()));
41  const auto crt_outer_rte_set = visitor.visit(crt_bin->get_left_operand());
42  const auto prev_outer_rte_set = visitor.visit(prev_bin->get_left_operand());
43  // We shouldn't treat mixed nesting levels columns as a composite key tuple.
44  if (crt_outer_rte_set.size() != 1 || prev_outer_rte_set.size() != 1 ||
45  crt_outer_rte_set != prev_outer_rte_set) {
46  return false;
47  }
48  if (!crt_inner || !prev_inner ||
49  crt_inner->get_table_id() != prev_inner->get_table_id() ||
50  crt_inner->get_rte_idx() != prev_inner->get_rte_idx()) {
51  return false;
52  }
53  return true;
54 }
55 
56 std::list<std::shared_ptr<Analyzer::Expr>> make_composite_equals_impl(
57  const std::vector<std::shared_ptr<Analyzer::Expr>>& crt_coalesced_quals) {
58  std::list<std::shared_ptr<Analyzer::Expr>> join_quals;
59  std::vector<std::shared_ptr<Analyzer::Expr>> lhs_tuple;
60  std::vector<std::shared_ptr<Analyzer::Expr>> rhs_tuple;
61  bool not_null{true};
62  for (const auto& qual : crt_coalesced_quals) {
63  const auto qual_binary = std::dynamic_pointer_cast<Analyzer::BinOper>(qual);
64  CHECK(qual_binary);
65  not_null = not_null && qual_binary->get_type_info().get_notnull();
66  const auto lhs_col = remove_cast(qual_binary->get_own_left_operand());
67  const auto rhs_col = remove_cast(qual_binary->get_own_right_operand());
68  const auto lhs_ti = lhs_col->get_type_info();
69  // Coalesce cols for integers, bool, and dict encoded strings. Forces baseline hash
70  // join.
71  if (IS_NUMBER(lhs_ti.get_type()) ||
72  (IS_STRING(lhs_ti.get_type()) && lhs_ti.get_compression() == kENCODING_DICT) ||
73  (lhs_ti.get_type() == kBOOLEAN)) {
74  lhs_tuple.push_back(lhs_col);
75  rhs_tuple.push_back(rhs_col);
76  } else {
77  join_quals.push_back(qual);
78  }
79  }
80  CHECK(!crt_coalesced_quals.empty());
81  const auto first_qual =
82  std::dynamic_pointer_cast<Analyzer::BinOper>(crt_coalesced_quals.front());
83  CHECK(first_qual);
84  CHECK_EQ(lhs_tuple.size(), rhs_tuple.size());
85  if (lhs_tuple.size() > 0) {
86  join_quals.push_front(std::make_shared<Analyzer::BinOper>(
87  SQLTypeInfo(kBOOLEAN, not_null),
88  false,
89  first_qual->get_optype(),
90  kONE,
91  lhs_tuple.size() > 1 ? std::make_shared<Analyzer::ExpressionTuple>(lhs_tuple)
92  : lhs_tuple.front(),
93  rhs_tuple.size() > 1 ? std::make_shared<Analyzer::ExpressionTuple>(rhs_tuple)
94  : rhs_tuple.front()));
95  }
96  return join_quals;
97 }
98 
99 // Create an equals expression with column tuple operands out of regular equals
100 // expressions.
101 std::list<std::shared_ptr<Analyzer::Expr>> make_composite_equals(
102  const std::vector<std::shared_ptr<Analyzer::Expr>>& crt_coalesced_quals) {
103  if (crt_coalesced_quals.size() == 1) {
104  return {crt_coalesced_quals.front()};
105  }
106  return make_composite_equals_impl(crt_coalesced_quals);
107 }
108 
109 } // namespace
110 
111 std::list<std::shared_ptr<Analyzer::Expr>> combine_equi_join_conditions(
112  const std::list<std::shared_ptr<Analyzer::Expr>>& join_quals) {
113  if (join_quals.empty()) {
114  return {};
115  }
116  std::list<std::shared_ptr<Analyzer::Expr>> coalesced_quals;
117  std::vector<std::shared_ptr<Analyzer::Expr>> crt_coalesced_quals;
118  for (const auto& simple_join_qual : join_quals) {
119  if (crt_coalesced_quals.empty()) {
120  crt_coalesced_quals.push_back(simple_join_qual);
121  continue;
122  }
123  if (crt_coalesced_quals.size() >= g_maximum_conditions_to_coalesce ||
124  !can_combine_with(simple_join_qual.get(), crt_coalesced_quals.back().get())) {
125  coalesced_quals.splice(coalesced_quals.end(),
126  make_composite_equals(crt_coalesced_quals));
127  crt_coalesced_quals.clear();
128  }
129  crt_coalesced_quals.push_back(simple_join_qual);
130  }
131  if (!crt_coalesced_quals.empty()) {
132  coalesced_quals.splice(coalesced_quals.end(),
133  make_composite_equals(crt_coalesced_quals));
134  }
135  return coalesced_quals;
136 }
137 
138 std::list<std::shared_ptr<Analyzer::Expr>> coalesce_singleton_equi_join(
139  const std::shared_ptr<Analyzer::BinOper>& join_qual) {
140  std::vector<std::shared_ptr<Analyzer::Expr>> singleton_qual_list;
141  singleton_qual_list.push_back(join_qual);
142  return make_composite_equals_impl(singleton_qual_list);
143 }
Defines data structures for the semantic analysis phase of query processing.
#define CHECK_EQ(x, y)
Definition: Logger.h:195
std::shared_ptr< Analyzer::Expr > remove_cast(const std::shared_ptr< Analyzer::Expr > &expr)
Definition: Analyzer.cpp:2993
#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)
SQLTypeInfoCore< ArrayContextTypeSizer, ExecutorTypePackaging, DateTimeFacilities > SQLTypeInfo
Definition: sqltypes.h:823
Definition: sqldefs.h:69
T visit(const Analyzer::Expr *expr) const
#define IS_STRING(T)
Definition: sqltypes.h:163
#define CHECK(condition)
Definition: Logger.h:187
const size_t g_maximum_conditions_to_coalesce
#define IS_NUMBER(T)
Definition: sqltypes.h:160
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)