OmniSciDB  1dac507f6e
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
anonymous_namespace{FromTableReordering.cpp} Namespace Reference

Classes

class  SchedulingDependencyTracking
 
struct  TraversalEdge
 

Typedefs

using cost_t = unsigned
 
using node_t = size_t
 

Functions

static std::unordered_map
< SQLTypes, cost_t > std::pair
< cost_t, cost_t
get_join_qual_cost (const Analyzer::Expr *qual, const Executor *executor)
 
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)
 
SchedulingDependencyTracking build_dependency_tracking (const JoinQualsPerNestingLevel &left_deep_join_quals, const std::vector< std::map< node_t, cost_t >> &join_cost_graph)
 
std::vector< node_ttraverse_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)
 

Variables

static std::unordered_map
< SQLTypes, cost_t
GEO_TYPE_COSTS {kPOINT, 60}
 

Typedef Documentation

using anonymous_namespace{FromTableReordering.cpp}::cost_t = typedef unsigned

Definition at line 28 of file FromTableReordering.cpp.

using anonymous_namespace{FromTableReordering.cpp}::node_t = typedef size_t

Definition at line 29 of file FromTableReordering.cpp.

Function Documentation

SchedulingDependencyTracking anonymous_namespace{FromTableReordering.cpp}::build_dependency_tracking ( const JoinQualsPerNestingLevel left_deep_join_quals,
const std::vector< std::map< node_t, cost_t >> &  join_cost_graph 
)

Definition at line 147 of file FromTableReordering.cpp.

References anonymous_namespace{FromTableReordering.cpp}::SchedulingDependencyTracking::addEdge(), CHECK(), LEFT, and run_benchmark_import::type.

Referenced by traverse_join_cost_graph().

149  {
150  SchedulingDependencyTracking dependency_tracking(left_deep_join_quals.size() + 1);
151  // Add directed graph edges for left join dependencies.
152  // See also start_it inside traverse_join_cost_graph(). These
153  // edges prevent start_it from pointing to a table with a
154  // left join dependency on another table.
155  for (size_t level_idx = 0; level_idx < left_deep_join_quals.size(); ++level_idx) {
156  if (left_deep_join_quals[level_idx].type == JoinType::LEFT) {
157  dependency_tracking.addEdge(level_idx, level_idx + 1);
158  }
159  }
160  // Add directed graph edges for geojoin type dependencies.
161  // See also start_it inside traverse_join_cost_graph(). These
162  // edges prevent start_it from pointing to a table with a
163  // geojoin type dependency as defined by GEO_TYPE_COSTS.
164  for (size_t idx1 = 0; idx1 < join_cost_graph.size(); ++idx1) {
165  for (auto& inner_map : join_cost_graph[idx1]) {
166  auto& idx2 = inner_map.first;
167  auto& cost_forward = inner_map.second;
168  auto reverse_it = join_cost_graph[idx2].find(idx1);
169  CHECK(reverse_it != join_cost_graph[idx2].end());
170  auto& cost_backward = reverse_it->second;
171  if (cost_forward > cost_backward) {
172  dependency_tracking.addEdge(idx1, idx2);
173  }
174  }
175  }
176  return dependency_tracking;
177 }
CHECK(cgen_state)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

std::vector<std::map<node_t, cost_t> > anonymous_namespace{FromTableReordering.cpp}::build_join_cost_graph ( const JoinQualsPerNestingLevel left_deep_join_quals,
const std::vector< InputTableInfo > &  table_infos,
const Executor executor 
)

Definition at line 76 of file FromTableReordering.cpp.

References CHECK_EQ, CHECK_GE, get_join_qual_cost(), and ScalarExprVisitor< T >::visit().

Referenced by get_node_input_permutation().

79  {
80  CHECK_EQ(left_deep_join_quals.size() + 1, table_infos.size());
81  std::vector<std::map<node_t, cost_t>> join_cost_graph(table_infos.size());
83  // Build the constraints graph: nodes are nest levels, edges are the existence of
84  // qualifiers between levels.
85  for (const auto& current_level_join_conditions : left_deep_join_quals) {
86  for (const auto& qual : current_level_join_conditions.quals) {
87  std::set<int> qual_nest_levels = visitor.visit(qual.get());
88  if (qual_nest_levels.size() != 2) {
89  continue;
90  }
91  int lhs_nest_level = *qual_nest_levels.begin();
92  CHECK_GE(lhs_nest_level, 0);
93  qual_nest_levels.erase(qual_nest_levels.begin());
94  int rhs_nest_level = *qual_nest_levels.begin();
95  CHECK_GE(rhs_nest_level, 0);
96 
97  // Get the {lhs, rhs} cost for the qual
98  const auto cost_pair = get_join_qual_cost(qual.get(), executor);
99  const auto edge_it = join_cost_graph[lhs_nest_level].find(rhs_nest_level);
100  if (edge_it == join_cost_graph[lhs_nest_level].end() ||
101  edge_it->second > cost_pair.second) {
102  join_cost_graph[lhs_nest_level][rhs_nest_level] = cost_pair.second;
103  join_cost_graph[rhs_nest_level][lhs_nest_level] = cost_pair.first;
104  }
105  }
106  }
107  return join_cost_graph;
108 }
#define CHECK_EQ(x, y)
Definition: Logger.h:198
#define CHECK_GE(x, y)
Definition: Logger.h:203
T visit(const Analyzer::Expr *expr) const
static std::unordered_map< SQLTypes, cost_t > std::pair< cost_t, cost_t > get_join_qual_cost(const Analyzer::Expr *qual, const Executor *executor)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static std::unordered_map<SQLTypes, cost_t> std::pair<cost_t, cost_t> anonymous_namespace{FromTableReordering.cpp}::get_join_qual_cost ( const Analyzer::Expr qual,
const Executor executor 
)

Definition at line 37 of file FromTableReordering.cpp.

References GEO_TYPE_COSTS, Analyzer::Expr::get_type_info(), Analyzer::FunctionOper::getArg(), IS_EQUIVALENCE, and normalize_column_pairs().

Referenced by build_join_cost_graph().

38  {
39  const auto func_oper = dynamic_cast<const Analyzer::FunctionOper*>(qual);
40  if (func_oper) {
41  std::vector<SQLTypes> geo_types_for_func;
42  for (size_t i = 0; i < func_oper->getArity(); i++) {
43  const auto arg_expr = func_oper->getArg(i);
44  const auto& ti = arg_expr->get_type_info();
45  if (ti.is_geometry()) {
46  geo_types_for_func.push_back(ti.get_type());
47  }
48  }
49  std::regex geo_func_regex("ST_[\\w]*");
50  std::smatch geo_func_match;
51  const auto& func_name = func_oper->getName();
52  if (geo_types_for_func.size() == 2 &&
53  std::regex_match(func_name, geo_func_match, geo_func_regex)) {
54  const auto rhs_cost = GEO_TYPE_COSTS[geo_types_for_func[0]];
55  const auto lhs_cost = GEO_TYPE_COSTS[geo_types_for_func[1]];
56  return {lhs_cost, rhs_cost};
57  }
58  return {200, 200};
59  }
60  const auto bin_oper = dynamic_cast<const Analyzer::BinOper*>(qual);
61  if (!bin_oper || !IS_EQUIVALENCE(bin_oper->get_optype())) {
62  return {200, 200};
63  }
64  if (executor) {
65  try {
67  bin_oper, *executor->getCatalog(), executor->getTemporaryTables());
68  } catch (...) {
69  return {200, 200};
70  }
71  }
72  return {100, 100};
73 }
std::vector< InnerOuter > normalize_column_pairs(const Analyzer::BinOper *condition, const Catalog_Namespace::Catalog &cat, const TemporaryTables *temporary_tables)
#define IS_EQUIVALENCE(X)
Definition: sqldefs.h:67
static std::unordered_map< SQLTypes, cost_t > GEO_TYPE_COSTS
const SQLTypeInfo & get_type_info() const
Definition: Analyzer.h:78
const Analyzer::Expr * getArg(const size_t i) const
Definition: Analyzer.h:1311

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

std::vector<node_t> anonymous_namespace{FromTableReordering.cpp}::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 
)

Definition at line 182 of file FromTableReordering.cpp.

References build_dependency_tracking(), CHECK(), and anonymous_namespace{FromTableReordering.cpp}::TraversalEdge::nest_level.

Referenced by get_node_input_permutation().

188  {
189  std::vector<node_t> all_nest_levels(table_infos.size());
190  std::iota(all_nest_levels.begin(), all_nest_levels.end(), 0);
191  std::vector<node_t> input_permutation;
192  std::unordered_set<node_t> visited;
193  auto dependency_tracking =
194  build_dependency_tracking(left_deep_join_quals, join_cost_graph);
195  auto schedulable_node = [&dependency_tracking, &visited](const node_t node) {
196  const auto nodes_ready = dependency_tracking.getRoots();
197  return nodes_ready.find(node) != nodes_ready.end() &&
198  visited.find(node) == visited.end();
199  };
200  while (visited.size() < table_infos.size()) {
201  // Filter out nest levels which are already visited or have pending dependencies.
202  std::vector<node_t> remaining_nest_levels;
203  std::copy_if(all_nest_levels.begin(),
204  all_nest_levels.end(),
205  std::back_inserter(remaining_nest_levels),
206  schedulable_node);
207  CHECK(!remaining_nest_levels.empty());
208  // Start with the table with most tuples.
209  const auto start_it = std::max_element(
210  remaining_nest_levels.begin(), remaining_nest_levels.end(), compare_node);
211  CHECK(start_it != remaining_nest_levels.end());
212  std::priority_queue<TraversalEdge, std::vector<TraversalEdge>, decltype(compare_edge)>
213  worklist(compare_edge);
214  worklist.push(TraversalEdge{*start_it, 0});
215  const auto it_ok = visited.insert(*start_it);
216  CHECK(it_ok.second);
217  while (!worklist.empty()) {
218  // Extract a node and add it to the permutation.
219  TraversalEdge crt = worklist.top();
220  worklist.pop();
221  input_permutation.push_back(crt.nest_level);
222  dependency_tracking.removeNode(crt.nest_level);
223  // Add successors which are ready and not visited yet to the queue.
224  for (const auto& graph_edge : join_cost_graph[crt.nest_level]) {
225  const node_t succ = graph_edge.first;
226  if (!schedulable_node(succ)) {
227  continue;
228  }
229  worklist.push(TraversalEdge{succ, graph_edge.second});
230  const auto it_ok = visited.insert(succ);
231  CHECK(it_ok.second);
232  }
233  }
234  }
235  return input_permutation;
236 }
SchedulingDependencyTracking build_dependency_tracking(const JoinQualsPerNestingLevel &left_deep_join_quals, const std::vector< std::map< node_t, cost_t >> &join_cost_graph)
CHECK(cgen_state)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Variable Documentation

std::unordered_map<SQLTypes, cost_t> anonymous_namespace{FromTableReordering.cpp}::GEO_TYPE_COSTS {kPOINT, 60}
static

Definition at line 31 of file FromTableReordering.cpp.

Referenced by get_join_qual_cost().