OmniSciDB  a987f07e93
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
FromTableReordering.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 
17 #include "FromTableReordering.h"
18 #include "Execute.h"
19 #include "ExpressionRewrite.h"
20 #include "RangeTableIndexVisitor.h"
22 
23 #include <numeric>
24 #include <queue>
25 #include <regex>
26 
27 namespace {
28 
29 using cost_t = unsigned;
30 using node_t = size_t;
31 
32 static std::unordered_map<SQLTypes, cost_t> GEO_TYPE_COSTS{{kPOINT, 60},
33  {kARRAY, 60},
34  {kLINESTRING, 70},
35  {kPOLYGON, 80},
36  {kMULTIPOLYGON, 90}};
37 
38 // Returns a lhs/rhs cost for the given qualifier. Must be strictly greater than 0.
39 // todo (yoonmin): compute the cost of inner join edge and outer join edge
40 // Currently, we set 100 for inner join and 200 for loop join
41 // for geometries, we use types of geometries if corresponding qual is not supported
42 // by overlaps hash join framework
43 // otherwise, we take a different approach depending on overlaps join function to maximize
44 // the chance of using the overlaps hash join framework
45 std::tuple<cost_t, cost_t, InnerQualDecision> get_join_qual_cost(
46  const Analyzer::Expr* qual,
47  const Executor* executor) {
48  if (executor) {
49  GeospatialFunctionFinder geo_func_finder;
50  geo_func_finder.visit(qual);
51  int inner_table_id = -1;
52  int outer_table_id = -1;
53  std::tie(inner_table_id, outer_table_id) = geo_func_finder.getTableIdsOfGeoExpr();
54  if (inner_table_id != -1 && outer_table_id != -1) {
55  // try to find a chance to swap tables in the binary join
56  // note that self-join does not need to be swapped
57  CHECK_NE(outer_table_id, inner_table_id);
58  const auto cat = executor->getCatalog();
59  const auto inner_table_metadata = cat->getMetadataForTable(inner_table_id);
60  const auto outer_table_metadata = cat->getMetadataForTable(outer_table_id);
61  const auto& target_geo_func_name = geo_func_finder.getGeoFunctionName();
62  if (inner_table_metadata->fragmenter && outer_table_metadata->fragmenter) {
63  const auto inner_table_cardinality =
64  inner_table_metadata->fragmenter->getNumRows();
65  const auto outer_table_cardinality =
66  outer_table_metadata->fragmenter->getNumRows();
67  auto inner_qual_decision = inner_table_cardinality > outer_table_cardinality
70  // detect the case when table reordering by cardinality incurs unexpected overhead
71  // i.e., SELECT ... FROM R, S where ST_Interesects(S.poly, R.pt) where |R| > |S|
72  // but |R| is not that larger than |S|, i.e., |R| / |S| < 10.0
73  // in this case, it might be a better when keeping the existing ordering
74  // to exploit (overlaps) hash join instead of loop join
75  const auto& geo_args = geo_func_finder.getGeoArgCvs();
76  const auto inner_cv_it =
77  std::find_if(geo_args.begin(),
78  geo_args.end(),
79  [inner_table_id](const Analyzer::ColumnVar* cv) {
80  return cv->get_table_id() == inner_table_id;
81  });
82  CHECK(inner_cv_it != geo_args.end());
83  const auto outer_cv_it =
84  std::find_if(geo_args.begin(),
85  geo_args.end(),
86  [outer_table_id](const Analyzer::ColumnVar* cv) {
87  return cv->get_table_id() == outer_table_id;
88  });
89  CHECK(outer_cv_it != geo_args.end());
90  const auto inner_cv = *inner_cv_it;
91  bool needs_table_reordering = inner_table_cardinality < outer_table_cardinality;
92  const auto outer_inner_card_ratio =
93  outer_table_cardinality / static_cast<double>(inner_table_cardinality);
95  target_geo_func_name) ||
97  target_geo_func_name)) {
98  // the goal of this is to maximize the chance of using overlaps hash join
99  // to achieve this, point column has zero for its rte_idx (so we build a
100  // hash table based on poly column which has rte_idx = 1)
101  // but if it's cardinality is smaller than that of polygon table more than 10x
102  // we try to fall back to loop join to avoid too expensive overlaps join cost
103  if (inner_cv->get_rte_idx() == 0 &&
104  (inner_cv->get_type_info().get_type() == kPOINT)) {
105  // outer is poly, and we can use overlaps hash join
106  if (needs_table_reordering && outer_inner_card_ratio > 10.0 &&
107  inner_table_cardinality < 10000) {
108  // but current pt table is small enough and hash table is larger than
109  // the pt table at least 10 times, then we fall back to loop join
110  // to avoid too expensive hash join
111  // so let's try to set inner table as poly table to invalidate
112  // rte index requirement
113  return {200, 200, InnerQualDecision::RHS};
114  } else {
115  // otherwise, try to keep the existing ordering
116  return {180, 190, InnerQualDecision::IGNORE};
117  }
118  } else {
119  // poly is the inner table, so we need to reorder tables to use overlaps hash
120  // join
121  if (needs_table_reordering) {
122  // outer point table is larger than inner poly table, so let's reorder them
123  // by table cardinality
124  return {200, 200, InnerQualDecision::RHS};
125  } else {
126  // otherwise, try to keep the existing ordering
127  return {180, 190, InnerQualDecision::IGNORE};
128  }
129  }
130  }
131  // rest of overlaps-available and overlaps-unavailable geo functions
132  // can reach here, and they are reordered by table cardinality
133  // specifically, overlaps-available geo join functions are satisfied one of
134  // followings: ST_OVERLAPS_sv and is_poly_mpoly_rewrite_target_func we can use
135  // overlaps hash join for those functions regardless of table ordering see
136  // rewrite_overlaps_conjunction function in ExpressionRewrite.cpp
137  VLOG(2) << "Detect geo join operator, initial_inner_table(table_id: "
138  << inner_table_id << ", cardinality: " << inner_table_cardinality
139  << "), initial_outer_table(table_id: " << outer_table_id
140  << ", cardinality: " << outer_table_cardinality
141  << "), inner_qual_decision: " << inner_qual_decision;
142  return {200, 200, inner_qual_decision};
143  }
144  } else {
145  // let's fall back to the old strategy by ordering tables by types of geometries
146  const auto func_oper = dynamic_cast<const Analyzer::FunctionOper*>(qual);
147  if (func_oper) {
148  std::vector<SQLTypes> geo_types_for_func;
149  for (size_t i = 0; i < func_oper->getArity(); i++) {
150  const auto arg_expr = func_oper->getArg(i);
151  const auto& ti = arg_expr->get_type_info();
152  if (ti.is_geometry() || is_constructed_point(arg_expr)) {
153  geo_types_for_func.push_back(ti.get_type());
154  }
155  }
156  std::regex geo_func_regex("ST_[\\w]*");
157  std::smatch geo_func_match;
158  const auto& func_name = func_oper->getName();
159  if (geo_types_for_func.size() == 2 &&
160  std::regex_match(func_name, geo_func_match, geo_func_regex)) {
161  const auto rhs_cost = GEO_TYPE_COSTS[geo_types_for_func[0]];
162  const auto lhs_cost = GEO_TYPE_COSTS[geo_types_for_func[1]];
163  return {lhs_cost, rhs_cost, InnerQualDecision::IGNORE};
164  }
165  return {200, 200, InnerQualDecision::IGNORE};
166  }
167  }
168  }
169 
170  const auto bin_oper = dynamic_cast<const Analyzer::BinOper*>(qual);
171  if (!bin_oper || !IS_EQUIVALENCE(bin_oper->get_optype())) {
172  return {200, 200, InnerQualDecision::IGNORE};
173  }
174  InnerQualDecision inner_qual_decision = InnerQualDecision::UNKNOWN;
175  if (executor) {
176  try {
177  const auto normalized_bin_oper = HashJoin::normalizeColumnPairs(
178  bin_oper, *executor->getCatalog(), executor->getTemporaryTables());
179  const auto& inner_outer = normalized_bin_oper.first;
180  // normalization success, so we need to figure out which cv becomes an inner
181  auto lhs = bin_oper->get_left_operand();
182  if (auto lhs_tuple = dynamic_cast<const Analyzer::ExpressionTuple*>(
183  bin_oper->get_left_operand())) {
184  lhs = lhs_tuple->getTuple().front().get();
185  }
186  CHECK(lhs);
187  if (lhs == inner_outer.front().first) {
188  inner_qual_decision = InnerQualDecision::LHS;
189  } else if (lhs == inner_outer.front().second) {
190  inner_qual_decision = InnerQualDecision::RHS;
191  }
192  } catch (const HashJoinFail& e) {
193  return {200, 200, e.inner_qual_decision};
194  } catch (...) {
195  return {200, 200, inner_qual_decision};
196  }
197  }
198  return {100, 100, inner_qual_decision};
199 }
200 
201 // Builds a graph with nesting levels as nodes and join condition costs as edges.
202 std::vector<std::map<node_t, cost_t>> build_join_cost_graph(
203  const JoinQualsPerNestingLevel& left_deep_join_quals,
204  const std::vector<InputTableInfo>& table_infos,
205  const Executor* executor,
206  std::vector<std::map<node_t, InnerQualDecision>>& qual_detection_res) {
207  CHECK_EQ(left_deep_join_quals.size() + 1, table_infos.size());
208  std::vector<std::map<node_t, cost_t>> join_cost_graph(table_infos.size());
210  // Build the constraints graph: nodes are nest levels, edges are the existence of
211  // qualifiers between levels.
212  for (const auto& current_level_join_conditions : left_deep_join_quals) {
213  for (const auto& qual : current_level_join_conditions.quals) {
214  std::set<int> qual_nest_levels = visitor.visit(qual.get());
215  if (qual_nest_levels.size() != 2) {
216  continue;
217  }
218  int lhs_nest_level = *qual_nest_levels.begin();
219  CHECK_GE(lhs_nest_level, 0);
220  qual_nest_levels.erase(qual_nest_levels.begin());
221  int rhs_nest_level = *qual_nest_levels.begin();
222  CHECK_GE(rhs_nest_level, 0);
223 
224  // Get the {lhs, rhs} cost for the qual
225  const auto qual_costing = get_join_qual_cost(qual.get(), executor);
226  qual_detection_res[lhs_nest_level][rhs_nest_level] = std::get<2>(qual_costing);
227  qual_detection_res[rhs_nest_level][lhs_nest_level] = std::get<2>(qual_costing);
228  const auto edge_it = join_cost_graph[lhs_nest_level].find(rhs_nest_level);
229  auto rhs_cost = std::get<1>(qual_costing);
230  if (edge_it == join_cost_graph[lhs_nest_level].end() ||
231  edge_it->second > rhs_cost) {
232  auto lhs_cost = std::get<0>(qual_costing);
233  join_cost_graph[lhs_nest_level][rhs_nest_level] = rhs_cost;
234  join_cost_graph[rhs_nest_level][lhs_nest_level] = lhs_cost;
235  }
236  }
237  }
238  return join_cost_graph;
239 }
240 
241 // Tracks dependencies between nodes.
243  public:
244  SchedulingDependencyTracking(const size_t node_count) : inbound_(node_count) {}
245 
246  // Add a from -> to dependency.
247  void addEdge(const node_t from, const node_t to) { inbound_[to].insert(from); }
248 
249  // Removes from's outbound dependencies.
250  void removeNode(const node_t from) {
251  for (auto& inbound_for_node : inbound_) {
252  inbound_for_node.erase(from);
253  }
254  }
255 
256  // Returns the set of all nodes without dependencies.
257  std::unordered_set<node_t> getRoots() const {
258  std::unordered_set<node_t> roots;
259  for (node_t candidate = 0; candidate < inbound_.size(); ++candidate) {
260  if (inbound_[candidate].empty()) {
261  roots.insert(candidate);
262  }
263  }
264  return roots;
265  }
266 
267  private:
268  std::vector<std::unordered_set<node_t>> inbound_;
269 };
270 
271 // The tree edge for traversal of the cost graph.
275 };
276 
277 // Builds dependency tracking based on left joins
279  const JoinQualsPerNestingLevel& left_deep_join_quals,
280  const std::vector<std::map<node_t, cost_t>>& join_cost_graph) {
281  SchedulingDependencyTracking dependency_tracking(left_deep_join_quals.size() + 1);
282  // Add directed graph edges for left join dependencies.
283  // See also start_it inside traverse_join_cost_graph(). These
284  // edges prevent start_it from pointing to a table with a
285  // left join dependency on another table.
286  for (size_t level_idx = 0; level_idx < left_deep_join_quals.size(); ++level_idx) {
287  if (left_deep_join_quals[level_idx].type == JoinType::LEFT) {
288  dependency_tracking.addEdge(level_idx, level_idx + 1);
289  }
290  }
291  return dependency_tracking;
292 }
293 
294 // Do a breadth-first traversal of the cost graph. This avoids scheduling a nest level
295 // before the ones which constraint it are scheduled and it favors equi joins over loop
296 // joins.
297 std::vector<node_t> traverse_join_cost_graph(
298  const std::vector<std::map<node_t, cost_t>>& join_cost_graph,
299  const std::vector<InputTableInfo>& table_infos,
300  const std::function<bool(const node_t lhs_nest_level, const node_t rhs_nest_level)>&
301  compare_node,
302  const std::function<bool(const TraversalEdge&, const TraversalEdge&)>& compare_edge,
303  const JoinQualsPerNestingLevel& left_deep_join_quals,
304  std::vector<std::map<node_t, InnerQualDecision>>& qual_normalization_res) {
305  std::vector<node_t> all_nest_levels(table_infos.size());
306  std::iota(all_nest_levels.begin(), all_nest_levels.end(), 0);
307  std::vector<node_t> input_permutation;
308  std::unordered_set<node_t> visited;
309  auto dependency_tracking =
310  build_dependency_tracking(left_deep_join_quals, join_cost_graph);
311  auto schedulable_node = [&dependency_tracking, &visited](const node_t node) {
312  const auto nodes_ready = dependency_tracking.getRoots();
313  return nodes_ready.find(node) != nodes_ready.end() &&
314  visited.find(node) == visited.end();
315  };
316  while (visited.size() < table_infos.size()) {
317  // Filter out nest levels which are already visited or have pending dependencies.
318  std::vector<node_t> remaining_nest_levels;
319  std::copy_if(all_nest_levels.begin(),
320  all_nest_levels.end(),
321  std::back_inserter(remaining_nest_levels),
322  schedulable_node);
323  CHECK(!remaining_nest_levels.empty());
324  // Start with the table with most tuples.
325  const auto start_it = std::max_element(
326  remaining_nest_levels.begin(), remaining_nest_levels.end(), compare_node);
327  CHECK(start_it != remaining_nest_levels.end());
328  std::priority_queue<TraversalEdge, std::vector<TraversalEdge>, decltype(compare_edge)>
329  worklist(compare_edge);
330  // look at all edges, compare the
331  // cost of our edge vs theirs, and pick the best start edge
332  node_t start = *start_it;
333  // we adaptively switch the inner and outer when we have a chance to exploit
334  // hash join framework for a query with a single binary join
335  TraversalEdge start_edge{start, 0};
336 
337  // when we have a single binary join in the query, we can analyze the qual and apply
338  // more smart table reordering logic that maximizes the chance of exploiting hash join
339  // todo (yoonmin) : generalize this for an arbitrary join pipeline
340  if (remaining_nest_levels.size() == 2 && qual_normalization_res[start].size() == 1) {
341  auto inner_qual_decision = qual_normalization_res[start].begin()->second;
342  auto join_qual = left_deep_join_quals.begin()->quals;
343  using ColvarSet =
344  std::set<const Analyzer::ColumnVar*,
345  bool (*)(const Analyzer::ColumnVar*, const Analyzer::ColumnVar*)>;
346 
347  auto set_new_rte_idx = [](ColvarSet& cv_set, int new_rte) {
348  std::for_each(
349  cv_set.begin(), cv_set.end(), [new_rte](const Analyzer::ColumnVar* cv) {
350  const_cast<Analyzer::ColumnVar*>(cv)->set_rte_idx(new_rte);
351  });
352  };
353 
354  // IGNORE: use the existing table reordering logic
355  // KEEP: return the existing table permutation and related cvs (column variables)
356  // SWAP: change the starting table of the table reordering logic and relevant
357  // columns' rte index
358  enum class Decision { IGNORE, KEEP, SWAP };
359 
360  auto analyze_join_qual = [&start,
361  &remaining_nest_levels,
362  &inner_qual_decision,
363  &table_infos,
364  compare_node](const std::shared_ptr<Analyzer::Expr>& lhs,
365  ColvarSet& lhs_colvar_set,
366  const std::shared_ptr<Analyzer::Expr>& rhs,
367  ColvarSet& rhs_colvar_set) {
368  if (!lhs || !rhs || lhs_colvar_set.empty() || rhs_colvar_set.empty()) {
369  return std::make_pair(Decision::IGNORE, start);
370  }
371 
372  auto alternative_it = std::find_if(
373  remaining_nest_levels.begin(),
374  remaining_nest_levels.end(),
375  [start](const size_t nest_level) { return start != nest_level; });
376  CHECK(alternative_it != remaining_nest_levels.end());
377  auto alternative_rte = *alternative_it;
378 
379  Decision decision = Decision::IGNORE;
380  // inner col's rte should be larger than outer col
381  int inner_rte = -1;
382  int outer_rte = -1;
383  bool is_outer_col_valid = false;
384  auto check_expr_is_valid_col = [&is_outer_col_valid](const Analyzer::Expr* expr) {
385  if (auto expr_tuple = dynamic_cast<const Analyzer::ExpressionTuple*>(expr)) {
386  for (auto& inner_expr : expr_tuple->getTuple()) {
387  auto cv_from_expr =
388  HashJoin::getHashJoinColumn<Analyzer::ColumnVar>(inner_expr.get());
389  if (!cv_from_expr) {
390  is_outer_col_valid = false;
391  return;
392  }
393  }
394  } else {
395  auto cv_from_expr = HashJoin::getHashJoinColumn<Analyzer::ColumnVar>(expr);
396  if (!cv_from_expr) {
397  is_outer_col_valid = false;
398  return;
399  }
400  }
401  is_outer_col_valid = true;
402  };
403  if (inner_qual_decision == InnerQualDecision::LHS) {
404  inner_rte = (*lhs_colvar_set.begin())->get_rte_idx();
405  outer_rte = (*rhs_colvar_set.begin())->get_rte_idx();
406  check_expr_is_valid_col(rhs.get());
407  } else if (inner_qual_decision == InnerQualDecision::RHS) {
408  inner_rte = (*rhs_colvar_set.begin())->get_rte_idx();
409  outer_rte = (*lhs_colvar_set.begin())->get_rte_idx();
410  check_expr_is_valid_col(lhs.get());
411  }
412  if (inner_rte >= 0 && outer_rte >= 0) {
413  const auto inner_cardinality =
414  table_infos[inner_rte].info.getNumTuplesUpperBound();
415  const auto outer_cardinality =
416  table_infos[outer_rte].info.getNumTuplesUpperBound();
417  if (inner_cardinality > g_trivial_loop_join_threshold) {
418  if (inner_rte == static_cast<int>(start)) {
419  // inner is driving the join loop but also has a valid join column
420  // which is available for building a hash table
421  // but ignore swapping when inner's cardinality is larger than that of
422  // outer's / otherwise swap inner and outer (to use the valid inner)
423  decision = is_outer_col_valid && inner_cardinality > outer_cardinality
424  ? Decision::IGNORE
425  : Decision::SWAP;
426  } else {
427  CHECK_EQ(inner_rte, static_cast<int>(alternative_rte));
428  // now, a valid inner column is outer table
429  if (compare_node(inner_rte, start)) {
430  // but outer table is larger than the current inner
431  // so we can exploit the existing table reordering logic
432  decision = Decision::IGNORE;
433  } else {
434  // and outer table is smaller than the current inner
435  // so we do not need to reorder the table starting from the inner
436  decision = Decision::KEEP;
437  }
438  }
439  }
440  }
441 
442  if (decision == Decision::KEEP) {
443  return std::make_pair(decision, start);
444  } else if (decision == Decision::SWAP) {
445  return std::make_pair(decision, alternative_rte);
446  }
447  return std::make_pair(Decision::IGNORE, start);
448  };
449 
450  auto collect_colvars = [](const std::shared_ptr<Analyzer::Expr> expr,
451  ColvarSet& cv_set) {
452  expr->collect_column_var(cv_set, false);
453  };
454 
455  auto adjust_reordering_logic = [&start, &start_edge, &start_it, set_new_rte_idx](
456  Decision decision,
457  int alternative_rte,
458  ColvarSet& lhs_colvar_set,
459  ColvarSet& rhs_colvar_set) {
460  CHECK(decision == Decision::SWAP);
461  start = alternative_rte;
462  set_new_rte_idx(lhs_colvar_set, alternative_rte);
463  set_new_rte_idx(rhs_colvar_set, *start_it);
464  start_edge.join_cost = 0;
465  start_edge.nest_level = start;
466  };
467 
468  auto bin_op = dynamic_cast<Analyzer::BinOper*>(join_qual.begin()->get());
469  if (bin_op) {
470  auto lhs = bin_op->get_own_left_operand();
471  auto rhs = bin_op->get_own_right_operand();
472  if (auto lhs_exp = dynamic_cast<Analyzer::ExpressionTuple*>(lhs.get())) {
473  // retrieve the decision and info for adjusting reordering by referring the
474  // first cv and apply them to the rest of cvs
475  auto rhs_exp = dynamic_cast<Analyzer::ExpressionTuple*>(rhs.get());
476  CHECK(rhs_exp);
477  auto& lhs_exprs = lhs_exp->getTuple();
478  auto& rhs_exprs = rhs_exp->getTuple();
479  CHECK_EQ(lhs_exprs.size(), rhs_exprs.size());
480  for (size_t i = 0; i < lhs_exprs.size(); ++i) {
481  Decision decision{Decision::IGNORE};
482  int alternative_rte_idx = -1;
483  ColvarSet lhs_colvar_set(Analyzer::ColumnVar::colvar_comp);
484  ColvarSet rhs_colvar_set(Analyzer::ColumnVar::colvar_comp);
485  collect_colvars(lhs_exprs.at(i), lhs_colvar_set);
486  collect_colvars(rhs_exprs.at(i), rhs_colvar_set);
487  if (i == 0) {
488  auto investigation_res =
489  analyze_join_qual(lhs, lhs_colvar_set, rhs, rhs_colvar_set);
490  decision = investigation_res.first;
491  if (decision == Decision::KEEP) {
492  return remaining_nest_levels;
493  }
494  alternative_rte_idx = investigation_res.second;
495  }
496  if (decision == Decision::SWAP) {
497  adjust_reordering_logic(
498  decision, alternative_rte_idx, lhs_colvar_set, rhs_colvar_set);
499  }
500  }
501  } else {
502  ColvarSet lhs_colvar_set(Analyzer::ColumnVar::colvar_comp);
503  ColvarSet rhs_colvar_set(Analyzer::ColumnVar::colvar_comp);
504  collect_colvars(lhs, lhs_colvar_set);
505  collect_colvars(rhs, rhs_colvar_set);
506  auto investigation_res =
507  analyze_join_qual(lhs, lhs_colvar_set, rhs, rhs_colvar_set);
508  if (investigation_res.first == Decision::KEEP) {
509  return remaining_nest_levels;
510  } else if (investigation_res.first == Decision::SWAP) {
511  adjust_reordering_logic(investigation_res.first,
512  investigation_res.second,
513  lhs_colvar_set,
514  rhs_colvar_set);
515  }
516  }
517  }
518  }
519 
520  VLOG(2) << "Table reordering starting with nest level " << start;
521  for (const auto& graph_edge : join_cost_graph[*start_it]) {
522  const node_t succ = graph_edge.first;
523  if (!schedulable_node(succ)) {
524  continue;
525  }
526  const TraversalEdge succ_edge{succ, graph_edge.second};
527  for (const auto& successor_edge : join_cost_graph[succ]) {
528  if (successor_edge.first == start) {
529  start_edge.join_cost = successor_edge.second;
530  // lhs cost / num tuples less than rhs cost if compare edge is true, swap nest
531  // levels
532  if (compare_edge(start_edge, succ_edge)) {
533  VLOG(2) << "Table reordering changing start nest level from " << start
534  << " to " << succ;
535  start = succ;
536  start_edge = succ_edge;
537  }
538  }
539  }
540  }
541  VLOG(2) << "Table reordering picked start nest level " << start << " with cost "
542  << start_edge.join_cost;
543  CHECK_EQ(start, start_edge.nest_level);
544  worklist.push(start_edge);
545  const auto it_ok = visited.insert(start);
546  CHECK(it_ok.second);
547  while (!worklist.empty()) {
548  // Extract a node and add it to the permutation.
549  TraversalEdge crt = worklist.top();
550  worklist.pop();
551  VLOG(1) << "Insert input permutation, idx: " << input_permutation.size()
552  << ", nest_level: " << crt.nest_level;
553  input_permutation.push_back(crt.nest_level);
554  dependency_tracking.removeNode(crt.nest_level);
555  // Add successors which are ready and not visited yet to the queue.
556  for (const auto& graph_edge : join_cost_graph[crt.nest_level]) {
557  const node_t succ = graph_edge.first;
558  if (!schedulable_node(succ)) {
559  continue;
560  }
561  worklist.push(TraversalEdge{succ, graph_edge.second});
562  const auto it_ok = visited.insert(succ);
563  CHECK(it_ok.second);
564  }
565  }
566  }
567  return input_permutation;
568 }
569 
570 } // namespace
571 
572 std::vector<node_t> get_node_input_permutation(
573  const JoinQualsPerNestingLevel& left_deep_join_quals,
574  const std::vector<InputTableInfo>& table_infos,
575  const Executor* executor) {
576  std::vector<std::map<node_t, InnerQualDecision>> qual_normalization_res(
577  table_infos.size());
578  const auto join_cost_graph = build_join_cost_graph(
579  left_deep_join_quals, table_infos, executor, qual_normalization_res);
580  // Use the number of tuples in each table to break ties in BFS.
581  const auto compare_node = [&table_infos](const node_t lhs_nest_level,
582  const node_t rhs_nest_level) {
583  return table_infos[lhs_nest_level].info.getNumTuplesUpperBound() <
584  table_infos[rhs_nest_level].info.getNumTuplesUpperBound();
585  };
586  const auto compare_edge = [&compare_node](const TraversalEdge& lhs_edge,
587  const TraversalEdge& rhs_edge) {
588  // Only use the number of tuples as a tie-breaker, if costs are equal.
589  if (lhs_edge.join_cost == rhs_edge.join_cost) {
590  return compare_node(lhs_edge.nest_level, rhs_edge.nest_level);
591  }
592  return lhs_edge.join_cost > rhs_edge.join_cost;
593  };
594  return traverse_join_cost_graph(join_cost_graph,
595  table_infos,
596  compare_node,
597  compare_edge,
598  left_deep_join_quals,
599  qual_normalization_res);
600 }
#define CHECK_EQ(x, y)
Definition: Logger.h:297
std::string cat(Ts &&...args)
static bool colvar_comp(const ColumnVar *l, const ColumnVar *r)
Definition: Analyzer.h:217
#define IS_EQUIVALENCE(X)
Definition: sqldefs.h:69
SchedulingDependencyTracking build_dependency_tracking(const JoinQualsPerNestingLevel &left_deep_join_quals, const std::vector< std::map< node_t, cost_t >> &join_cost_graph)
static std::pair< std::vector< InnerOuter >, std::vector< InnerOuterStringOpInfos > > normalizeColumnPairs(const Analyzer::BinOper *condition, const Catalog_Namespace::Catalog &cat, const TemporaryTables *temporary_tables)
Definition: HashJoin.cpp:996
bool is_constructed_point(const Analyzer::Expr *expr)
Definition: Execute.h:1516
static std::unordered_map< SQLTypes, cost_t > std::tuple< cost_t, cost_t, InnerQualDecision > get_join_qual_cost(const Analyzer::Expr *qual, const Executor *executor)
#define CHECK_GE(x, y)
Definition: Logger.h:302
const std::vector< const Analyzer::ColumnVar * > & getGeoArgCvs() const
std::vector< JoinCondition > JoinQualsPerNestingLevel
T visit(const Analyzer::Expr *expr) const
unsigned g_trivial_loop_join_threshold
Definition: Execute.cpp:89
std::vector< node_t > get_node_input_permutation(const JoinQualsPerNestingLevel &left_deep_join_quals, const std::vector< InputTableInfo > &table_infos, const Executor *executor)
const std::pair< int, int > getTableIdsOfGeoExpr() const
static std::unordered_map< SQLTypes, cost_t > GEO_TYPE_COSTS
#define CHECK_NE(x, y)
Definition: Logger.h:298
std::vector< std::map< node_t, cost_t > > build_join_cost_graph(const JoinQualsPerNestingLevel &left_deep_join_quals, const std::vector< InputTableInfo > &table_infos, const Executor *executor, std::vector< std::map< node_t, InnerQualDecision >> &qual_detection_res)
const std::string & getGeoFunctionName() const
static bool is_poly_point_rewrite_target_func(std::string_view target_func_name)
const SQLTypeInfo & get_type_info() const
Definition: Analyzer.h:83
const Analyzer::Expr * getArg(const size_t i) const
Definition: Analyzer.h:2406
DEVICE void iota(ARGS &&...args)
Definition: gpu_enabled.h:69
#define CHECK(condition)
Definition: Logger.h:289
InnerQualDecision
Definition: HashJoin.h:62
std::vector< node_t > traverse_join_cost_graph(const std::vector< std::map< node_t, cost_t >> &join_cost_graph, const std::vector< InputTableInfo > &table_infos, const std::function< bool(const node_t lhs_nest_level, const node_t rhs_nest_level)> &compare_node, const std::function< bool(const TraversalEdge &, const TraversalEdge &)> &compare_edge, const JoinQualsPerNestingLevel &left_deep_join_quals, std::vector< std::map< node_t, InnerQualDecision >> &qual_normalization_res)
AccessManager::Decision Decision
InnerQualDecision inner_qual_decision
Definition: HashJoin.h:78
const std::shared_ptr< Analyzer::Expr > get_own_left_operand() const
Definition: Analyzer.h:453
#define VLOG(n)
Definition: Logger.h:383
static bool is_point_poly_rewrite_target_func(std::string_view target_func_name)