OmniSciDB  d2f719934e
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
RaExecutionSequence Class Reference

A container for relational algebra descriptors defining the execution order for a relational algebra query. Holds the relational algebra descriptors for executing a relational algebra query. Each descriptor holds both a top-level relational algebra node and a ResultSet ptr holding the results from the execution of the accompany node(s). The sequence can be generated on initialization or lazily with calls to the next() operator. More...

#include <RelAlgExecutionDescriptor.h>

Public Member Functions

 RaExecutionSequence (const RelAlgNode *, const bool build_sequence=true)
 
 RaExecutionSequence (std::unique_ptr< RaExecutionDesc > exec_desc)
 
RaExecutionDescnext ()
 
RaExecutionDescprev ()
 
std::optional< size_t > nextStepId (const bool after_broadcast) const
 
bool executionFinished () const
 
RaExecutionDescgetDescriptor (size_t idx) const
 
RaExecutionDescgetDescriptorByBodyId (unsigned const body_id, size_t const start_idx) const
 
size_t size () const
 
bool empty () const
 
size_t totalDescriptorsCount () const
 

Private Member Functions

size_t stepsToNextBroadcast () const
 

Private Attributes

DAG graph_
 
std::unordered_set< Vertexjoins_
 
std::vector< Vertexordering_
 
size_t current_vertex_ = 0
 
size_t scan_count_ = 0
 
std::vector< std::unique_ptr
< RaExecutionDesc > > 
descs_
 

Detailed Description

A container for relational algebra descriptors defining the execution order for a relational algebra query. Holds the relational algebra descriptors for executing a relational algebra query. Each descriptor holds both a top-level relational algebra node and a ResultSet ptr holding the results from the execution of the accompany node(s). The sequence can be generated on initialization or lazily with calls to the next() operator.

Definition at line 134 of file RelAlgExecutionDescriptor.h.

Constructor & Destructor Documentation

RaExecutionSequence::RaExecutionSequence ( const RelAlgNode sink,
const bool  build_sequence = true 
)

Definition at line 238 of file RelAlgExecutionDescriptor.cpp.

References anonymous_namespace{RelAlgExecutionDescriptor.cpp}::build_dag(), CHECK, anonymous_namespace{RelAlgExecutionDescriptor.cpp}::get_join_vertices(), graph_, joins_, anonymous_namespace{RelAlgExecutionDescriptor.cpp}::merge_sort_with_input(), next(), ordering_, and gpu_enabled::reverse().

239  {
240  CHECK(sink);
241  if (dynamic_cast<const RelScan*>(sink) || dynamic_cast<const RelJoin*>(sink)) {
242  throw std::runtime_error("Query not supported yet");
243  }
244 
245  graph_ = build_dag(sink);
246 
247  boost::topological_sort(graph_, std::back_inserter(ordering_));
248  std::reverse(ordering_.begin(), ordering_.end());
249 
250  ordering_ = merge_sort_with_input(ordering_, graph_);
251  joins_ = get_join_vertices(ordering_, graph_);
252 
253  if (build_sequence) {
254  while (next()) {
255  // noop
256  }
257  }
258 }
std::unordered_set< Vertex > joins_
std::unordered_set< Vertex > get_join_vertices(const std::vector< Vertex > &vertices, const DAG &graph)
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:211
std::vector< Vertex > merge_sort_with_input(const std::vector< Vertex > &vertices, const DAG &graph)
DEVICE void reverse(ARGS &&...args)
Definition: gpu_enabled.h:96

+ Here is the call graph for this function:

RaExecutionSequence::RaExecutionSequence ( std::unique_ptr< RaExecutionDesc exec_desc)

Definition at line 260 of file RelAlgExecutionDescriptor.cpp.

References descs_.

260  {
261  descs_.emplace_back(std::move(exec_desc));
262 }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_

Member Function Documentation

bool RaExecutionSequence::empty ( ) const
inline

Definition at line 169 of file RelAlgExecutionDescriptor.h.

References descs_.

Referenced by RelAlgExecutor::executeRelAlgSeq().

169 { return descs_.empty(); }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_

+ Here is the caller graph for this function:

bool RaExecutionSequence::executionFinished ( ) const

Definition at line 307 of file RelAlgExecutionDescriptor.cpp.

References current_vertex_, nextStepId(), ordering_, and totalDescriptorsCount().

307  {
308  if (current_vertex_ == ordering_.size()) {
309  // All descriptors visited, execution finished
310  return true;
311  } else {
312  const auto next_step_id = nextStepId(true);
313  if (!next_step_id || (*next_step_id == totalDescriptorsCount())) {
314  // One step remains (the current vertex), or all remaining steps can be executed
315  // without another broadcast (i.e. on the aggregator)
316  return true;
317  }
318  }
319  return false;
320 }
std::vector< Vertex > ordering_
std::optional< size_t > nextStepId(const bool after_broadcast) const

+ Here is the call graph for this function:

RaExecutionDesc* RaExecutionSequence::getDescriptor ( size_t  idx) const
inline

Definition at line 160 of file RelAlgExecutionDescriptor.h.

References CHECK_LT, and descs_.

Referenced by RelAlgExecutor::executeRelAlgQuerySingleStep(), RelAlgExecutor::executeRelAlgSeq(), RelAlgExecutor::executeRelAlgStep(), and RelAlgExecutor::executeRelAlgSubSeq().

160  {
161  CHECK_LT(idx, descs_.size());
162  return descs_[idx].get();
163  }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
#define CHECK_LT(x, y)
Definition: Logger.h:221

+ Here is the caller graph for this function:

RaExecutionDesc * RaExecutionSequence::getDescriptorByBodyId ( unsigned const  body_id,
size_t const  start_idx 
) const

Definition at line 332 of file RelAlgExecutionDescriptor.cpp.

References CHECK_LT, and descs_.

Referenced by RelAlgExecutor::executeRelAlgStep().

334  {
335  CHECK_LT(start_idx, descs_.size());
336  auto const from_end = descs_.size() - (start_idx + 1);
337  MatchBody const match_body{body_id};
338  auto const itr = std::find_if(descs_.rbegin() + from_end, descs_.rend(), match_body);
339  return itr == descs_.rend() ? nullptr : itr->get();
340 }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
#define CHECK_LT(x, y)
Definition: Logger.h:221

+ Here is the caller graph for this function:

RaExecutionDesc * RaExecutionSequence::next ( )

Return the next execution descriptor in the sequence. If no more execution descriptors exist, returns nullptr.

Definition at line 264 of file RelAlgExecutionDescriptor.cpp.

References CHECK, current_vertex_, descs_, graph_, joins_, ordering_, and scan_count_.

Referenced by RaExecutionSequence().

264  {
265  while (current_vertex_ < ordering_.size()) {
266  auto vert = ordering_[current_vertex_++];
267  if (joins_.count(vert)) {
268  continue;
269  }
270  auto& node = graph_[vert];
271  CHECK(node);
272  if (dynamic_cast<const RelScan*>(node)) {
273  scan_count_++;
274  continue;
275  }
276  descs_.emplace_back(std::make_unique<RaExecutionDesc>(node));
277  return descs_.back().get();
278  }
279  return nullptr;
280 }
std::unordered_set< Vertex > joins_
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:211

+ Here is the caller graph for this function:

std::optional< size_t > RaExecutionSequence::nextStepId ( const bool  after_broadcast) const

Returns the index of the next execution descriptor in the graph. If after_broadcast is true, returns the index of the first execution descriptor after the next global broadcast. Returns std::nullopt if no execution descriptors remain in the graph.

Definition at line 294 of file RelAlgExecutionDescriptor.cpp.

References current_vertex_, descs_, ordering_, and stepsToNextBroadcast().

Referenced by executionFinished().

294  {
295  if (after_broadcast) {
296  if (current_vertex_ == ordering_.size()) {
297  return std::nullopt;
298  }
299  return descs_.size() + stepsToNextBroadcast();
300  } else if (current_vertex_ == ordering_.size()) {
301  return std::nullopt;
302  } else {
303  return descs_.size();
304  }
305 }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
std::vector< Vertex > ordering_

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

RaExecutionDesc * RaExecutionSequence::prev ( )

Return the previous execution descriptor in the sequence. If the sequence is made up of 0 or 1 descriptors, returns nullptr.

Definition at line 282 of file RelAlgExecutionDescriptor.cpp.

References CHECK_GE, and descs_.

282  {
283  if (descs_.empty()) {
284  return nullptr;
285  }
286  if (descs_.size() == 1) {
287  return nullptr;
288  }
289  CHECK_GE(descs_.size(), size_t(2));
290  auto itr = descs_.rbegin();
291  return (++itr)->get();
292 }
#define CHECK_GE(x, y)
Definition: Logger.h:224
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
size_t RaExecutionSequence::size ( ) const
inline

Definition at line 168 of file RelAlgExecutionDescriptor.h.

References descs_.

Referenced by RelAlgExecutor::executeRelAlgQueryWithFilterPushDown(), and RelAlgExecutor::executeRelAlgSeq().

168 { return descs_.size(); }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_

+ Here is the caller graph for this function:

size_t RaExecutionSequence::stepsToNextBroadcast ( ) const
private

Starting from the current vertex, iterate the graph counting the number of execution descriptors remaining before the next required broadcast step. The current vertex is counted as the first step before a broadcast is required; i.e. a return value of 0 indicates no additional steps in the graph can be executed without a global broadcast, and a return value of 2 indicates the current vertex and both subsequent vertices can be executed before a global broacast is needed.

Definition at line 360 of file RelAlgExecutionDescriptor.cpp.

References CHECK, CHECK_EQ, current_vertex_, graph_, i, joins_, ordering_, and gpu_enabled::sort().

Referenced by nextStepId().

360  {
361  size_t steps_to_next_broadcast = 0;
362  auto crt_vertex = current_vertex_;
363  while (crt_vertex < ordering_.size()) {
364  auto vert = ordering_[crt_vertex++];
365  auto node = graph_[vert];
366  CHECK(node);
367  if (joins_.count(vert)) {
368  auto join_node = dynamic_cast<const RelLeftDeepInnerJoin*>(node);
369  CHECK(join_node);
370  for (size_t i = 0; i < join_node->inputCount(); i++) {
371  const auto input = join_node->getInput(i);
372  if (dynamic_cast<const RelScan*>(input)) {
373  return steps_to_next_broadcast;
374  }
375  }
376  if (crt_vertex < ordering_.size() - 1) {
377  // Force the parent node of the RelLeftDeepInnerJoin to run on the aggregator.
378  // Note that crt_vertex has already been incremented once above for the join node
379  // -- increment it again to account for the parent node of the join
380  ++steps_to_next_broadcast;
381  ++crt_vertex;
382  continue;
383  } else {
384  CHECK_EQ(crt_vertex, ordering_.size() - 1);
385  // If the join node parent is the last node in the tree, run all remaining steps
386  // on the aggregator
387  return ++steps_to_next_broadcast;
388  }
389  }
390  if (auto sort = dynamic_cast<const RelSort*>(node)) {
391  CHECK_EQ(sort->inputCount(), size_t(1));
392  node = sort->getInput(0);
393  }
394  if (dynamic_cast<const RelScan*>(node)) {
395  return steps_to_next_broadcast;
396  }
397  if (dynamic_cast<const RelModify*>(node)) {
398  // Modify runs on the leaf automatically, run the same node as a noop on the
399  // aggregator
400  ++steps_to_next_broadcast;
401  continue;
402  }
403  if (auto project = dynamic_cast<const RelProject*>(node)) {
404  if (project->hasWindowFunctionExpr()) {
405  ++steps_to_next_broadcast;
406  continue;
407  }
408  }
409  for (size_t input_idx = 0; input_idx < node->inputCount(); input_idx++) {
410  if (dynamic_cast<const RelScan*>(node->getInput(input_idx))) {
411  return steps_to_next_broadcast;
412  }
413  }
414  ++steps_to_next_broadcast;
415  }
416  return steps_to_next_broadcast;
417 }
#define CHECK_EQ(x, y)
Definition: Logger.h:219
DEVICE void sort(ARGS &&...args)
Definition: gpu_enabled.h:105
std::unordered_set< Vertex > joins_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:211

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

size_t RaExecutionSequence::totalDescriptorsCount ( ) const

Definition at line 342 of file RelAlgExecutionDescriptor.cpp.

References CHECK, graph_, joins_, and ordering_.

Referenced by executionFinished().

342  {
343  size_t num_descriptors = 0;
344  size_t crt_vertex = 0;
345  while (crt_vertex < ordering_.size()) {
346  auto vert = ordering_[crt_vertex++];
347  if (joins_.count(vert)) {
348  continue;
349  }
350  auto& node = graph_[vert];
351  CHECK(node);
352  if (dynamic_cast<const RelScan*>(node)) {
353  continue;
354  }
355  ++num_descriptors;
356  }
357  return num_descriptors;
358 }
std::unordered_set< Vertex > joins_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:211

+ Here is the caller graph for this function:

Member Data Documentation

size_t RaExecutionSequence::current_vertex_ = 0
private
std::vector<std::unique_ptr<RaExecutionDesc> > RaExecutionSequence::descs_
private
DAG RaExecutionSequence::graph_
private
std::unordered_set<Vertex> RaExecutionSequence::joins_
private
std::vector<Vertex> RaExecutionSequence::ordering_
private
size_t RaExecutionSequence::scan_count_ = 0
private

Definition at line 179 of file RelAlgExecutionDescriptor.h.

Referenced by next().


The documentation for this class was generated from the following files: