OmniSciDB  8a228a1076
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 ()
 
ssize_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 106 of file RelAlgExecutionDescriptor.h.

Constructor & Destructor Documentation

◆ RaExecutionSequence() [1/2]

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

Definition at line 193 of file RelAlgExecutionDescriptor.cpp.

References anonymous_namespace{RelAlgExecutionDescriptor.cpp}::build_dag(), CHECK, anonymous_namespace{RelAlgExecutionDescriptor.cpp}::get_join_vertices(), and anonymous_namespace{RelAlgExecutionDescriptor.cpp}::merge_sort_with_input().

194  {
195  CHECK(sink);
196  if (dynamic_cast<const RelScan*>(sink) || dynamic_cast<const RelJoin*>(sink)) {
197  throw std::runtime_error("Query not supported yet");
198  }
199 
200  graph_ = build_dag(sink);
201 
202  boost::topological_sort(graph_, std::back_inserter(ordering_));
203  std::reverse(ordering_.begin(), ordering_.end());
204 
205  ordering_ = merge_sort_with_input(ordering_, graph_);
206  joins_ = get_join_vertices(ordering_, graph_);
207 
208  if (build_sequence) {
209  while (next()) {
210  // noop
211  }
212  }
213 }
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:197
std::vector< Vertex > merge_sort_with_input(const std::vector< Vertex > &vertices, const DAG &graph)
+ Here is the call graph for this function:

◆ RaExecutionSequence() [2/2]

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

Definition at line 215 of file RelAlgExecutionDescriptor.cpp.

215  {
216  descs_.emplace_back(std::move(exec_desc));
217 }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_

Member Function Documentation

◆ empty()

bool RaExecutionSequence::empty ( ) const
inline

Definition at line 132 of file RelAlgExecutionDescriptor.h.

Referenced by RelAlgExecutor::executeRelAlgSeq().

132 { return descs_.empty(); }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
+ Here is the caller graph for this function:

◆ executionFinished()

bool RaExecutionSequence::executionFinished ( ) const

Definition at line 249 of file RelAlgExecutionDescriptor.cpp.

249  {
250  if (current_vertex_ == ordering_.size()) {
251  // All descriptors visited, execution finished
252  return true;
253  } else {
254  const auto next_step_id = nextStepId(true);
255  if (next_step_id < 0 ||
256  (static_cast<size_t>(next_step_id) == totalDescriptorsCount())) {
257  // One step remains (the current vertex), or all remaining steps can be executed
258  // without another broadcast (i.e. on the aggregator)
259  return true;
260  }
261  }
262  return false;
263 }
ssize_t nextStepId(const bool after_broadcast) const
std::vector< Vertex > ordering_

◆ getDescriptor()

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

Definition at line 126 of file RelAlgExecutionDescriptor.h.

References CHECK_LT.

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

126  {
127  CHECK_LT(idx, descs_.size());
128  return descs_[idx].get();
129  }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
#define CHECK_LT(x, y)
Definition: Logger.h:207
+ Here is the caller graph for this function:

◆ next()

RaExecutionDesc * RaExecutionSequence::next ( )

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

Definition at line 219 of file RelAlgExecutionDescriptor.cpp.

References CHECK.

219  {
220  while (current_vertex_ < ordering_.size()) {
221  auto vert = ordering_[current_vertex_++];
222  if (joins_.count(vert)) {
223  continue;
224  }
225  auto& node = graph_[vert];
226  CHECK(node);
227  if (dynamic_cast<const RelScan*>(node)) {
228  scan_count_++;
229  continue;
230  }
231  descs_.emplace_back(std::make_unique<RaExecutionDesc>(node));
232  return descs_.back().get();
233  }
234  return nullptr;
235 }
std::unordered_set< Vertex > joins_
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:197

◆ nextStepId()

ssize_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 -1 if no execution descriptors remain in the graph.

Definition at line 237 of file RelAlgExecutionDescriptor.cpp.

237  {
238  if (after_broadcast) {
239  if (current_vertex_ == ordering_.size()) {
240  return -1;
241  }
242  const auto steps_to_next_broadcast = static_cast<ssize_t>(stepsToNextBroadcast());
243  return static_cast<ssize_t>(descs_.size()) + steps_to_next_broadcast;
244  } else {
245  return current_vertex_ == ordering_.size() ? -1 : descs_.size();
246  }
247 }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
std::vector< Vertex > ordering_

◆ size()

size_t RaExecutionSequence::size ( ) const
inline

Definition at line 131 of file RelAlgExecutionDescriptor.h.

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

131 { return descs_.size(); }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
+ Here is the caller graph for this function:

◆ stepsToNextBroadcast()

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

References CHECK, and CHECK_EQ.

283  {
284  size_t steps_to_next_broadcast = 0;
285  auto crt_vertex = current_vertex_;
286  while (crt_vertex < ordering_.size()) {
287  auto vert = ordering_[crt_vertex++];
288  auto node = graph_[vert];
289  CHECK(node);
290  if (joins_.count(vert)) {
291  auto join_node = dynamic_cast<const RelLeftDeepInnerJoin*>(node);
292  CHECK(join_node);
293  if (crt_vertex < ordering_.size() - 1) {
294  // Force the parent node of the RelLeftDeepInnerJoin to run on the aggregator.
295  // Note that crt_vertex has already been incremented once above for the join node
296  // -- increment it again to account for the parent node of the join
297  ++steps_to_next_broadcast;
298  ++crt_vertex;
299  continue;
300  } else {
301  CHECK_EQ(crt_vertex, ordering_.size() - 1);
302  // If the join node parent is the last node in the tree, run all remaining steps
303  // on the aggregator
304  return ++steps_to_next_broadcast;
305  }
306  }
307  if (auto sort = dynamic_cast<const RelSort*>(node)) {
308  CHECK_EQ(sort->inputCount(), size_t(1));
309  node = sort->getInput(0);
310  }
311  if (dynamic_cast<const RelScan*>(node)) {
312  return steps_to_next_broadcast;
313  }
314  if (dynamic_cast<const RelModify*>(node)) {
315  // Modify runs on the leaf automatically, run the same node as a noop on the
316  // aggregator
317  ++steps_to_next_broadcast;
318  continue;
319  }
320  if (auto project = dynamic_cast<const RelProject*>(node)) {
321  if (project->hasWindowFunctionExpr()) {
322  ++steps_to_next_broadcast;
323  continue;
324  }
325  }
326  for (size_t input_idx = 0; input_idx < node->inputCount(); input_idx++) {
327  if (dynamic_cast<const RelScan*>(node->getInput(input_idx))) {
328  return steps_to_next_broadcast;
329  }
330  }
331  ++steps_to_next_broadcast;
332  }
333  return steps_to_next_broadcast;
334 }
#define CHECK_EQ(x, y)
Definition: Logger.h:205
std::unordered_set< Vertex > joins_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:197

◆ totalDescriptorsCount()

size_t RaExecutionSequence::totalDescriptorsCount ( ) const

Definition at line 265 of file RelAlgExecutionDescriptor.cpp.

References CHECK.

265  {
266  size_t num_descriptors = 0;
267  size_t crt_vertex = 0;
268  while (crt_vertex < ordering_.size()) {
269  auto vert = ordering_[crt_vertex++];
270  if (joins_.count(vert)) {
271  continue;
272  }
273  auto& node = graph_[vert];
274  CHECK(node);
275  if (dynamic_cast<const RelScan*>(node)) {
276  continue;
277  }
278  ++num_descriptors;
279  }
280  return num_descriptors;
281 }
std::unordered_set< Vertex > joins_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:197

Member Data Documentation

◆ current_vertex_

size_t RaExecutionSequence::current_vertex_ = 0
private

Definition at line 141 of file RelAlgExecutionDescriptor.h.

◆ descs_

std::vector<std::unique_ptr<RaExecutionDesc> > RaExecutionSequence::descs_
private

Definition at line 157 of file RelAlgExecutionDescriptor.h.

◆ graph_

DAG RaExecutionSequence::graph_
private

Definition at line 137 of file RelAlgExecutionDescriptor.h.

◆ joins_

std::unordered_set<Vertex> RaExecutionSequence::joins_
private

Definition at line 139 of file RelAlgExecutionDescriptor.h.

◆ ordering_

std::vector<Vertex> RaExecutionSequence::ordering_
private

Definition at line 140 of file RelAlgExecutionDescriptor.h.

◆ scan_count_

size_t RaExecutionSequence::scan_count_ = 0
private

Definition at line 142 of file RelAlgExecutionDescriptor.h.


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