OmniSciDB  ba1bac9284
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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
 
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 236 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().

237  {
238  CHECK(sink);
239  if (dynamic_cast<const RelScan*>(sink) || dynamic_cast<const RelJoin*>(sink)) {
240  throw std::runtime_error("Query not supported yet");
241  }
242 
243  graph_ = build_dag(sink);
244 
245  boost::topological_sort(graph_, std::back_inserter(ordering_));
246  std::reverse(ordering_.begin(), ordering_.end());
247 
248  ordering_ = merge_sort_with_input(ordering_, graph_);
249  joins_ = get_join_vertices(ordering_, graph_);
250 
251  if (build_sequence) {
252  while (next()) {
253  // noop
254  }
255  }
256 }
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:206
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 258 of file RelAlgExecutionDescriptor.cpp.

References descs_.

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

Member Function Documentation

bool RaExecutionSequence::empty ( ) const
inline

Definition at line 166 of file RelAlgExecutionDescriptor.h.

References descs_.

Referenced by RelAlgExecutor::executeRelAlgSeq().

166 { 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 305 of file RelAlgExecutionDescriptor.cpp.

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

305  {
306  if (current_vertex_ == ordering_.size()) {
307  // All descriptors visited, execution finished
308  return true;
309  } else {
310  const auto next_step_id = nextStepId(true);
311  if (!next_step_id || (*next_step_id == totalDescriptorsCount())) {
312  // One step remains (the current vertex), or all remaining steps can be executed
313  // without another broadcast (i.e. on the aggregator)
314  return true;
315  }
316  }
317  return false;
318 }
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:216

+ 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 262 of file RelAlgExecutionDescriptor.cpp.

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

Referenced by RaExecutionSequence().

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

+ 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 292 of file RelAlgExecutionDescriptor.cpp.

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

Referenced by executionFinished().

292  {
293  if (after_broadcast) {
294  if (current_vertex_ == ordering_.size()) {
295  return std::nullopt;
296  }
297  return descs_.size() + stepsToNextBroadcast();
298  } else if (current_vertex_ == ordering_.size()) {
299  return std::nullopt;
300  } else {
301  return descs_.size();
302  }
303 }
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 280 of file RelAlgExecutionDescriptor.cpp.

References CHECK_GE, and descs_.

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

Definition at line 165 of file RelAlgExecutionDescriptor.h.

References descs_.

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

165 { 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 338 of file RelAlgExecutionDescriptor.cpp.

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

Referenced by nextStepId().

338  {
339  size_t steps_to_next_broadcast = 0;
340  auto crt_vertex = current_vertex_;
341  while (crt_vertex < ordering_.size()) {
342  auto vert = ordering_[crt_vertex++];
343  auto node = graph_[vert];
344  CHECK(node);
345  if (joins_.count(vert)) {
346  auto join_node = dynamic_cast<const RelLeftDeepInnerJoin*>(node);
347  CHECK(join_node);
348  for (size_t i = 0; i < join_node->inputCount(); i++) {
349  const auto input = join_node->getInput(i);
350  if (dynamic_cast<const RelScan*>(input)) {
351  return steps_to_next_broadcast;
352  }
353  }
354  if (crt_vertex < ordering_.size() - 1) {
355  // Force the parent node of the RelLeftDeepInnerJoin to run on the aggregator.
356  // Note that crt_vertex has already been incremented once above for the join node
357  // -- increment it again to account for the parent node of the join
358  ++steps_to_next_broadcast;
359  ++crt_vertex;
360  continue;
361  } else {
362  CHECK_EQ(crt_vertex, ordering_.size() - 1);
363  // If the join node parent is the last node in the tree, run all remaining steps
364  // on the aggregator
365  return ++steps_to_next_broadcast;
366  }
367  }
368  if (auto sort = dynamic_cast<const RelSort*>(node)) {
369  CHECK_EQ(sort->inputCount(), size_t(1));
370  node = sort->getInput(0);
371  }
372  if (dynamic_cast<const RelScan*>(node)) {
373  return steps_to_next_broadcast;
374  }
375  if (dynamic_cast<const RelModify*>(node)) {
376  // Modify runs on the leaf automatically, run the same node as a noop on the
377  // aggregator
378  ++steps_to_next_broadcast;
379  continue;
380  }
381  if (auto project = dynamic_cast<const RelProject*>(node)) {
382  if (project->hasWindowFunctionExpr()) {
383  ++steps_to_next_broadcast;
384  continue;
385  }
386  }
387  for (size_t input_idx = 0; input_idx < node->inputCount(); input_idx++) {
388  if (dynamic_cast<const RelScan*>(node->getInput(input_idx))) {
389  return steps_to_next_broadcast;
390  }
391  }
392  ++steps_to_next_broadcast;
393  }
394  return steps_to_next_broadcast;
395 }
#define CHECK_EQ(x, y)
Definition: Logger.h:214
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:206

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

size_t RaExecutionSequence::totalDescriptorsCount ( ) const

Definition at line 320 of file RelAlgExecutionDescriptor.cpp.

References CHECK, graph_, joins_, and ordering_.

Referenced by executionFinished().

320  {
321  size_t num_descriptors = 0;
322  size_t crt_vertex = 0;
323  while (crt_vertex < ordering_.size()) {
324  auto vert = ordering_[crt_vertex++];
325  if (joins_.count(vert)) {
326  continue;
327  }
328  auto& node = graph_[vert];
329  CHECK(node);
330  if (dynamic_cast<const RelScan*>(node)) {
331  continue;
332  }
333  ++num_descriptors;
334  }
335  return num_descriptors;
336 }
std::unordered_set< Vertex > joins_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:206

+ 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 176 of file RelAlgExecutionDescriptor.h.

Referenced by next().


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