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)
RaExecutionDesc *	next ()
ssize_t	nextStepId (const bool after_reduction) const
bool	executionFinished () const
RaExecutionDesc *	getDescriptor (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< Vertex >	joins_
std::vector< Vertex >	ordering_
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_.

                                                                    {
  CHECK(sink);
  if (dynamic_cast<const RelScan*>(sink) || dynamic_cast<const RelJoin*>(sink)) {
    throw std::runtime_error("Query not supported yet");
  }

  graph_ = build_dag(sink);

  boost::topological_sort(graph_, std::back_inserter(ordering_));
  std::reverse(ordering_.begin(), ordering_.end());

  ordering_ = merge_sort_with_input(ordering_, graph_);
  joins_ = get_join_vertices(ordering_, graph_);

  if (build_sequence) {
    while (next()) {
      // noop
    }
  }
}

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_.

                                                                                 {
  descs_.emplace_back(std::move(exec_desc));
}

Member Function Documentation

bool RaExecutionSequence::empty ( ) const

inline

Definition at line 132 of file RelAlgExecutionDescriptor.h.

References descs_.

Referenced by RelAlgExecutor::executeRelAlgSeq().

{ return descs_.empty(); }

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().

                                                  {
  if (current_vertex_ == ordering_.size()) {
    // All descriptors visited, execution finished
    return true;
  } else {
    const auto next_step_id = nextStepId(true);
    if (next_step_id < 0 ||
        (static_cast<size_t>(next_step_id) == totalDescriptorsCount())) {
      // One step remains (the current vertex), or all remaining steps can be executed
      // without another reduction
      return true;
    }
  }
  return false;
}

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().

                                                   {
    CHECK_LT(idx, descs_.size());
    return descs_[idx].get();
  }

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().

                                           {
  while (current_vertex_ < ordering_.size()) {
    auto vert = ordering_[current_vertex_++];
    if (joins_.count(vert)) {
      continue;
    }
    auto& node = graph_[vert];
    CHECK(node);
    if (dynamic_cast<const RelScan*>(node)) {
      scan_count_++;
      continue;
    }
    descs_.emplace_back(std::make_unique<RaExecutionDesc>(node));
    return descs_.back().get();
  }
  return nullptr;
}

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().

                                                                        {
  if (after_reduction) {
    if (current_vertex_ == ordering_.size()) {
      return -1;
    }
    const auto steps_to_next_reduction = static_cast<ssize_t>(stepsToNextReduction());
    return static_cast<ssize_t>(descs_.size()) + steps_to_next_reduction;
  } else {
    return current_vertex_ == ordering_.size() ? -1 : descs_.size();
  }
}

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().

{ return descs_.size(); }

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().

                                                       {
  size_t steps_to_next_reduction = 0;
  auto crt_vertex = current_vertex_;
  while (crt_vertex < ordering_.size()) {
    auto vert = ordering_[crt_vertex++];
    auto node = graph_[vert];
    CHECK(node);
    if (joins_.count(vert)) {
      auto join_node = dynamic_cast<const RelLeftDeepInnerJoin*>(node);
      CHECK(join_node);
      if (crt_vertex < ordering_.size() - 1) {
        // Force the parent node of the RelLeftDeepInnerJoin to run on the aggregator.
        // Note that crt_vertex has already been incremented once above for the join node
        // -- increment it again to account for the parent node of the join
        ++steps_to_next_reduction;
        ++crt_vertex;
        continue;
      } else {
        CHECK_EQ(crt_vertex, ordering_.size() - 1);
        // If the join node parent is the last node in the tree, run all remaining steps
        // on the aggregator
        return ++steps_to_next_reduction;
      }
    }
    if (auto sort = dynamic_cast<const RelSort*>(node)) {
      CHECK_EQ(sort->inputCount(), size_t(1));
      node = sort->getInput(0);
    }
    if (dynamic_cast<const RelScan*>(node)) {
      return steps_to_next_reduction;
    }
    if (dynamic_cast<const RelModify*>(node)) {
      // Modify runs on the leaf automatically, run the same node as a noop on the
      // aggregator
      ++steps_to_next_reduction;
      continue;
    }
    for (size_t input_idx = 0; input_idx < node->inputCount(); input_idx++) {
      if (dynamic_cast<const RelScan*>(node->getInput(input_idx))) {
        return steps_to_next_reduction;
      }
    }
    ++steps_to_next_reduction;
  }
  return steps_to_next_reduction;
}

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().

                                                        {
  size_t num_descriptors = 0;
  size_t crt_vertex = 0;
  while (crt_vertex < ordering_.size()) {
    auto vert = ordering_[crt_vertex++];
    if (joins_.count(vert)) {
      continue;
    }
    auto& node = graph_[vert];
    CHECK(node);
    if (dynamic_cast<const RelScan*>(node)) {
      continue;
    }
    ++num_descriptors;
  }
  return num_descriptors;
}

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

Definition at line 141 of file RelAlgExecutionDescriptor.h.

Referenced by executionFinished(), next(), nextStepId(), and stepsToNextReduction().

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

private

Definition at line 157 of file RelAlgExecutionDescriptor.h.

Referenced by empty(), getDescriptor(), next(), nextStepId(), RaExecutionSequence(), and size().

DAG RaExecutionSequence::graph_

private

Definition at line 137 of file RelAlgExecutionDescriptor.h.

Referenced by next(), RaExecutionSequence(), stepsToNextReduction(), and totalDescriptorsCount().

std::unordered_set<Vertex> RaExecutionSequence::joins_

private

Definition at line 139 of file RelAlgExecutionDescriptor.h.

Referenced by next(), RaExecutionSequence(), stepsToNextReduction(), and totalDescriptorsCount().

std::vector<Vertex> RaExecutionSequence::ordering_

private

Definition at line 140 of file RelAlgExecutionDescriptor.h.

Referenced by executionFinished(), next(), nextStepId(), RaExecutionSequence(), stepsToNextReduction(), and totalDescriptorsCount().

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:

• /home/jenkins-slave/workspace/core-os-doxygen/QueryEngine/Descriptors/RelAlgExecutionDescriptor.h
• /home/jenkins-slave/workspace/core-os-doxygen/QueryEngine/Descriptors/RelAlgExecutionDescriptor.cpp