OmniSciDB  1dac507f6e
 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 ()
 
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::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(), graph_, joins_, anonymous_namespace{RelAlgExecutionDescriptor.cpp}::merge_sort_with_input(), next(), and ordering_.

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_
CHECK(cgen_state)
std::unordered_set< Vertex > get_join_vertices(const std::vector< Vertex > &vertices, const DAG &graph)
std::vector< Vertex > ordering_
std::vector< Vertex > merge_sort_with_input(const std::vector< Vertex > &vertices, const DAG &graph)

+ Here is the call graph for this function:

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

Definition at line 205 of file RelAlgExecutionDescriptor.cpp.

References descs_.

205  {
206  descs_.emplace_back(std::move(exec_desc));
207 }
std::vector< std::unique_ptr< RaExecutionDesc > > descs_

Member Function Documentation

bool RaExecutionSequence::empty ( ) const
inline

Definition at line 132 of file RelAlgExecutionDescriptor.h.

References descs_.

Referenced by RelAlgExecutor::executeRelAlgSeq().

132 { 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 239 of file RelAlgExecutionDescriptor.cpp.

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

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_

+ Here is the call graph for this function:

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

Definition at line 126 of file RelAlgExecutionDescriptor.h.

References CHECK_LT, and descs_.

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:200

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

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

Referenced by RaExecutionSequence().

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_
CHECK(cgen_state)
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:

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.

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

Referenced by executionFinished().

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_

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

size_t RaExecutionSequence::size ( ) const
inline

Definition at line 131 of file RelAlgExecutionDescriptor.h.

References descs_.

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:

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(), CHECK_EQ, current_vertex_, graph_, joins_, and ordering_.

Referenced by nextStepId().

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  return ++steps_to_next_reduction;
284  }
285  if (auto sort = dynamic_cast<const RelSort*>(node)) {
286  CHECK_EQ(sort->inputCount(), size_t(1));
287  node = sort->getInput(0);
288  }
289  if (dynamic_cast<const RelScan*>(node)) {
290  return steps_to_next_reduction;
291  }
292  if (dynamic_cast<const RelModify*>(node)) {
293  // Modify runs on the leaf automatically, run the same node as a noop on the
294  // aggregator
295  ++steps_to_next_reduction;
296  continue;
297  }
298  for (size_t input_idx = 0; input_idx < node->inputCount(); input_idx++) {
299  if (dynamic_cast<const RelScan*>(node->getInput(input_idx))) {
300  return steps_to_next_reduction;
301  }
302  }
303  ++steps_to_next_reduction;
304  }
305  return steps_to_next_reduction;
306 }
#define CHECK_EQ(x, y)
Definition: Logger.h:198
std::unordered_set< Vertex > joins_
CHECK(cgen_state)
std::vector< Vertex > ordering_

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

size_t RaExecutionSequence::totalDescriptorsCount ( ) const

Definition at line 255 of file RelAlgExecutionDescriptor.cpp.

References CHECK(), graph_, joins_, and ordering_.

Referenced by executionFinished().

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_
CHECK(cgen_state)
std::vector< Vertex > ordering_

+ Here is the call graph for this function:

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

Referenced by next().


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