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

                                                                    {
  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() [2/2]

RaExecutionSequence::RaExecutionSequence

(

std::unique_ptr< RaExecutionDesc >

exec_desc

)

Definition at line 205 of file RelAlgExecutionDescriptor.cpp.

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

Member Function Documentation

empty()

bool RaExecutionSequence::empty ( ) const

inline

Definition at line 132 of file RelAlgExecutionDescriptor.h.

Referenced by RelAlgExecutor::executeRelAlgSeq().

{ return descs_.empty(); }

Here is the caller graph for this function:

executionFinished()

bool RaExecutionSequence::executionFinished

(

)

const

Definition at line 239 of file RelAlgExecutionDescriptor.cpp.

                                                  {
  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;
}

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

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

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.

                                           {
  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;
}

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.

                                                                        {
  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();
  }
}

size()

size_t RaExecutionSequence::size ( ) const

inline

Definition at line 131 of file RelAlgExecutionDescriptor.h.

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

{ return descs_.size(); }

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.

                                                       {
  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;
}

totalDescriptorsCount()

size_t RaExecutionSequence::totalDescriptorsCount

(

)

const

Definition at line 255 of file RelAlgExecutionDescriptor.cpp.

References CHECK.

                                                        {
  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;
}

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:

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