Pipeline dependent tree query optimizer and scheduler

1. A method comprising:

extracting, by one or more processors, multiple pipelines from a query plan tree for a query for data, the query plan tree having multiple nodes and being stored in a memory, wherein each node is representative of an operation on the data, the extracting comprising:

traversing the query plan tree to identify a sequence of nodes for each pipeline; initiating a node stack with nodes of the query plan tree, including a root node; initiating a pipeline stack; and

starting a new pipeline based on encountering a pipeline breaker node that corresponds to a node representing an operation that materializes an intermediate result, wherein the starting of the new pipeline comprises:

based on a current node being the pipeline breaker node and not being a join node:

appending the current node to a current pipeline in the pipeline stack;

initiating the new pipeline in the pipeline stack; and

specifying a parent-child relationship between the current pipeline and the new pipeline;

identifying dependencies between the multiple extracted pipelines; and

generating a pipeline dependent tree based on the dependencies between the multiple extracted pipelines for execution of the operations represented by the sequence of nodes in each pipeline by multiple processors.

2. The method of claim 1 , wherein the traversing of the query plan tree comprises using an iterative post-order traversal of the query plan tree to visit each node only once, starting with the root node.

3. The method of claim 1 , wherein if a second current node is not a pipeline breaker, the second current node is appended to Ha 11 the current pipeline in the pipeline stack.

4. The method of claim 1 , further comprising:

scheduling the multiple pipelines to execute in parallel on multiple processors; and

executing the multiple pipelines on the multiple processors in accordance with the scheduling.

5. The method of claim 4 , wherein the multiple pipelines are scheduled to execute in parallel on the multiple processors based on a least wait time for parent pipelines without violating data dependencies among pipelines.

6. The method of claim 4 , wherein the multiple pipelines are scheduled to execute in parallel based on not exceeding computation resources of a host and maximizing overlapping pipeline execution times across host resources.

7. The method of claim 4 , wherein the multiple pipelines are scheduled to execute in parallel based on locality aware dispatching without violating resource constraints and avoiding unnecessary data shuffles.

8. A device comprising:

a non-transitory memory storage comprising instructions; and

one or more processors in communications with the memory storage, wherein the one or more processors execute the instructions to:

extract multiple pipelines from a query plan tree for a query for data, the query plan tree having multiple nodes and being stored in a memory, wherein each node is representative of an operation on the data, the extracting comprising:

traversing the query plan tree to identify a sequence of nodes for each pipeline;

initiating a node stack with nodes of the query plan tree, including a root node;

initiating a pipeline stack; and

starting a new pipeline based on encountering a pipeline breaker node that corresponds to a node representing an operation that materializes an intermediate result, wherein the starting of the new pipeline comprises:

based on a current node being the pipeline breaker node and not being a join node:

appending the current node to a current pipeline in the pipeline stack;

initiating the new pipeline in the pipeline stack; and

specifying a parent-child relationship between the current pipeline and the new pipeline;

identify dependencies between the multiple extracted pipelines; and

generate a pipeline dependent tree based on the dependencies between the multiple extracted pipelines for execution of the operations represented by the sequence of nodes in each pipeline by multiple processors.

9. The device of claim 8 , wherein the traversing of the query plan tree comprises using an iterative post-order traversal of the query plan tree to visit each node only once, starting with the root node.

10. The device of claim 8 , wherein the one or more processors are further to:

schedule the multiple pipelines to execute in parallel on multiple processors; and

execute the multiple pipelines on the multiple processors in accordance with the scheduling.

11. The device of claim 10 , wherein the multiple pipelines are scheduled to execute in parallel on the multiple processors based on a least wait time for parent pipelines without violating data dependencies among pipelines.

12. The device of claim 11 , wherein the multiple pipelines are scheduled to execute in parallel based on not exceeding computation resources of a host and maximizing overlapping pipeline execution times across host resources.

13. A non-transitory computer-readable media storing computer instructions, that when executed by one or more processors, cause the one or more processors to perform the steps of:

extracting multiple pipelines from a query plan tree for a query for data, the query plan tree having multiple nodes and being stored in a memory, wherein each node is representative of an operation on the data, the extracting comprising:

traversing the query plan tree to identify a sequence of nodes for each pipeline;

initiating a node stack with nodes of the query plan tree, including a root node;

initiating a pipeline stack; and

starting a new pipeline based on encountering a pipeline breaker node that corresponds to a node representing an operation that materializes an intermediate result, wherein the starting of the new pipeline comprises:

based on a current node being the pipeline breaker node and not being a join node:

appending the current node to a current pipeline in the pipeline stack;

initiating the new pipeline in the pipeline stack; and

specifying a parent-child relationship between the current pipeline and the new pipeline:

identifying dependencies between the multiple extracted pipelines; and

providing a pipeline dependent tree based on the dependencies between the multiple extracted pipelines for execution of the query by multiple processors.

14. The non-transitory computer-readable media of claim 13 , wherein the traversing of the query plan tree comprises using an iterative post-order traversal of the query plan tree to visit each node only once.

15. The non-transitory computer-readable media of claim 13 , wherein the steps further comprise:

scheduling the multiple pipelines to execute in parallel on multiple processors based on a least wait time for parent pipelines without violating data dependencies among pipelines; and

executing the multiple pipelines on the multiple processors in accordance with the scheduling.

16. The non-transitory computer-readable media of claim 13 , wherein the multiple pipelines are further scheduled to execute in parallel based on not exceeding computation resources of a host and maximizing overlapping pipeline execution times across host resources.

17. The non-transitory computer-readable media of claim 13 , wherein t multiple pipelines are further scheduled to execute in parallel based on locality aware dispatching without violating resource constraints and avoiding unnecessary data shuffles.