Class RaExecutionSequence

class RaExecutionSequence

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.

Public Functions

RaExecutionSequence(const RelAlgNode *sink, Executor *executor, const bool build_sequence = true)

RaExecutionSequence(std::unique_ptr<RaExecutionDesc> exec_desc)

RaExecutionDesc *next()

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

RaExecutionDesc *prev()

Return the previous execution descriptor in the sequence. If the sequence is made up of 0 or 1 descriptors, returns nullptr.

std::optional<size_t> 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 std::nullopt if no execution descriptors remain in the graph.

bool executionFinished() const

void extractQueryStepSkippingInfo()

Extracts a topological information of the query plan DAG about the relationship among query steps where a parent step and its child steps can be skipped if we have a cached resultset of the parent step

void skipQuerySteps()

Optimizes the query execution step based on the information extracted from the extractQueryStepSkippingInfo function

std::vector<Vertex> mergeSortWithInput(const std::vector<Vertex> &vertices, const DAG &graph)

const std::unordered_map<int, QueryPlanHash> getSkippedQueryStepCacheKeys() const

RaExecutionDesc *getDescriptor(size_t idx) const

RaExecutionDesc *getDescriptorByBodyId(unsigned const body_id, size_t const start_idx) const

size_t size() const

bool empty() const

size_t totalDescriptorsCount() const

const bool hasQueryStepForUnion() const

Private Functions

size_t stepsToNextBroadcast() const

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.

Private Members

DAG graph_

Executor *executor_

std::unordered_set<Vertex> joins_

std::vector<Vertex> ordering_

size_t current_vertex_ = 0

size_t scan_count_ = 0

std::unordered_map<const RelAlgNode *, int> node_ptr_to_vert_idx_

std::unordered_map<int, std::unordered_set<int>> skippable_steps_

std::unordered_set<int> cached_query_steps_

std::unordered_map<int, QueryPlanHash> cached_resultset_keys_

bool has_step_for_union_ = {false}

bool has_limit_clause_ = {false}

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