OmniSciDB  29e35f4d58
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_reduction) 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 stepsToNextReduction () 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 183 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().

184  {
185  CHECK(sink);
186  if (dynamic_cast<const RelScan*>(sink) || dynamic_cast<const RelJoin*>(sink)) {
187  throw std::runtime_error("Query not supported yet");
188  }
189 
190  graph_ = build_dag(sink);
191 
192  boost::topological_sort(graph_, std::back_inserter(ordering_));
193  std::reverse(ordering_.begin(), ordering_.end());
194 
195  ordering_ = merge_sort_with_input(ordering_, graph_);
196  joins_ = get_join_vertices(ordering_, graph_);
197 
198  if (build_sequence) {
199  while (next()) {
200  // noop
201  }
202  }
203 }
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:193
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 205 of file RelAlgExecutionDescriptor.cpp.

205  {
206  descs_.emplace_back(std::move(exec_desc));
207 }
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 239 of file RelAlgExecutionDescriptor.cpp.

239  {
240  if (current_vertex_ == ordering_.size()) {
241  // All descriptors visited, execution finished
242  return true;
243  } else {
244  const auto next_step_id = nextStepId(true);
245  if (next_step_id < 0 ||
246  (static_cast<size_t>(next_step_id) == totalDescriptorsCount())) {
247  // One step remains (the current vertex), or all remaining steps can be executed
248  // without another reduction
249  return true;
250  }
251  }
252  return false;
253 }
ssize_t nextStepId(const bool after_reduction) 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:203
+ 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 209 of file RelAlgExecutionDescriptor.cpp.

References CHECK.

209  {
210  while (current_vertex_ < ordering_.size()) {
211  auto vert = ordering_[current_vertex_++];
212  if (joins_.count(vert)) {
213  continue;
214  }
215  auto& node = graph_[vert];
216  CHECK(node);
217  if (dynamic_cast<const RelScan*>(node)) {
218  scan_count_++;
219  continue;
220  }
221  descs_.emplace_back(std::make_unique<RaExecutionDesc>(node));
222  return descs_.back().get();
223  }
224  return nullptr;
225 }
std::unordered_set< Vertex > joins_
std::vector< std::unique_ptr< RaExecutionDesc > > descs_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:193

◆ nextStepId()

ssize_t RaExecutionSequence::nextStepId ( const bool  after_reduction) const

Returns the index of the next execution descriptor in the graph. If after_reduction is true, returns the index of the first execution descriptor after the next global reduction. Returns -1 if no execution descriptors remain in the graph.

Definition at line 227 of file RelAlgExecutionDescriptor.cpp.

227  {
228  if (after_reduction) {
229  if (current_vertex_ == ordering_.size()) {
230  return -1;
231  }
232  const auto steps_to_next_reduction = static_cast<ssize_t>(stepsToNextReduction());
233  return static_cast<ssize_t>(descs_.size()) + steps_to_next_reduction;
234  } else {
235  return current_vertex_ == ordering_.size() ? -1 : descs_.size();
236  }
237 }
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:

◆ stepsToNextReduction()

size_t RaExecutionSequence::stepsToNextReduction ( ) const
private

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

Definition at line 273 of file RelAlgExecutionDescriptor.cpp.

References CHECK, and CHECK_EQ.

273  {
274  size_t steps_to_next_reduction = 0;
275  auto crt_vertex = current_vertex_;
276  while (crt_vertex < ordering_.size()) {
277  auto vert = ordering_[crt_vertex++];
278  auto node = graph_[vert];
279  CHECK(node);
280  if (joins_.count(vert)) {
281  auto join_node = dynamic_cast<const RelLeftDeepInnerJoin*>(node);
282  CHECK(join_node);
283  if (crt_vertex < ordering_.size() - 1) {
284  // Force the parent node of the RelLeftDeepInnerJoin to run on the aggregator.
285  // Note that crt_vertex has already been incremented once above for the join node
286  // -- increment it again to account for the parent node of the join
287  ++steps_to_next_reduction;
288  ++crt_vertex;
289  continue;
290  } else {
291  CHECK_EQ(crt_vertex, ordering_.size() - 1);
292  // If the join node parent is the last node in the tree, run all remaining steps
293  // on the aggregator
294  return ++steps_to_next_reduction;
295  }
296  }
297  if (auto sort = dynamic_cast<const RelSort*>(node)) {
298  CHECK_EQ(sort->inputCount(), size_t(1));
299  node = sort->getInput(0);
300  }
301  if (dynamic_cast<const RelScan*>(node)) {
302  return steps_to_next_reduction;
303  }
304  if (dynamic_cast<const RelModify*>(node)) {
305  // Modify runs on the leaf automatically, run the same node as a noop on the
306  // aggregator
307  ++steps_to_next_reduction;
308  continue;
309  }
310  for (size_t input_idx = 0; input_idx < node->inputCount(); input_idx++) {
311  if (dynamic_cast<const RelScan*>(node->getInput(input_idx))) {
312  return steps_to_next_reduction;
313  }
314  }
315  ++steps_to_next_reduction;
316  }
317  return steps_to_next_reduction;
318 }
#define CHECK_EQ(x, y)
Definition: Logger.h:201
std::unordered_set< Vertex > joins_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:193

◆ totalDescriptorsCount()

size_t RaExecutionSequence::totalDescriptorsCount ( ) const

Definition at line 255 of file RelAlgExecutionDescriptor.cpp.

References CHECK.

255  {
256  size_t num_descriptors = 0;
257  size_t crt_vertex = 0;
258  while (crt_vertex < ordering_.size()) {
259  auto vert = ordering_[crt_vertex++];
260  if (joins_.count(vert)) {
261  continue;
262  }
263  auto& node = graph_[vert];
264  CHECK(node);
265  if (dynamic_cast<const RelScan*>(node)) {
266  continue;
267  }
268  ++num_descriptors;
269  }
270  return num_descriptors;
271 }
std::unordered_set< Vertex > joins_
std::vector< Vertex > ordering_
#define CHECK(condition)
Definition: Logger.h:193

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: