Optimizing pipelining result sets with fault tolerance in distributed query execution

• US 10,366,084 B2
• Filed: 09/15/2016
• Issued: 07/30/2019
• Est. Priority Date: 09/15/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Yin, Zhicheng, Sun, Jin, Li, Ming, Ekanayake, Jaliya Nishantha, Kwon, Yongchul, Blakeley, Jose A., Friedman, Marc T., Lin, Haibo, Ramakrishnan, Raghunath, Guan, Tao
• Primary Examiner(s): Khong, Alexander
• Application Number:
  US15/267,115
• Publication Number:
  US 20180075098A1
• Time in Patent Office: 1,048 Days
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement

Abstract

Aspects extend to methods, systems, and computer program products for optimally pipelining result sets with fault tolerance in distributed query execution. Distributed computing jobs are optimized by dividing the distributed computing jobs into one or more bubbles for execution. Each bubble can be independently executed, potentially in parallel with other bubbles, when resources to handle the bubble are available. Intra-bubble communication can be streamed between vertices within a bubble. Inter-bubble communication can be stored to durable storage. Bubbles provide a failure boundary for a job graph and re-executing a bubble along with storage of intermediate results in durable storage can be used to recover from failures. When a vertex inside a bubble fails, computation can resume by rescheduling the execution of the failed bubble from the durable inputs for that bubble. Durable storage provides a light-weight failover to handle non-deterministic behavior. Jobs can also leverage streaming to increase performance.

Claims

1. A computer system comprising:

one or more hardware processors;

system memory coupled to the one or more hardware processors, the system memory storing instructions that are executable by the one or more hardware processors;

the one or more hardware processors configured to execute the instructions stored in the system memory to pipeline result sets with fault tolerance in distributed query execution, including the following;

access a job graph, the job graph indicating a plurality of bubbles, each bubble including one or more supervertices from a plurality of supervertices, each supervertex including one or more vertices of a same vertex type, the job graph divided into the plurality of bubbles based on determined resource consumption for each of the plurality of supervertices and dependencies between supervertices within the plurality of supervertices; and

execute the job graph using resources of a distributed system including;

for a bubble in the plurality of bubbles, streaming results from one supervertex within the bubble to another supervertex within the bubble via one of;

memory or a network connection;

for another bubble in the plurality of bubbles, storing other results from a supervertex within the another bubble to durable storage; and

for a further bubble in the plurality of bubbles, accessing the other results from the durable storage.

2. The computer system of claim 1, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to access a job graph comprise the one or more hardware processors configured to execute the instructions stored in the system memory to access a job graph for implementing logical intent of a query.

3. The computer system of claim 1, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to access a job graph comprise the one or more hardware processors configured to execute the instructions stored in the system memory to access a Directed Acyclic Graph.

4. The computer system of claim 1, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to execute the job graph using resources of the distributed system comprise the one or more hardware processors configured to execute the instructions stored in the system memory to execute the job graph using memory and processor resources of the distributed system.

5. The computer system of claim 1, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to execute the job graph using resources of the distributed system comprise the one or more hardware processors configured to execute the instructions stored in the system memory to execute the job graph using resources of a scale-out distributed system.

6. The computer system of claim 1, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to execute the job graph using resources of the distributed system comprise the one or more hardware processors configured to execute the instructions stored in the system memory to:

monitor the availability of distributed system resources on an ongoing basis; and

execute bubbles, from among the plurality of bubbles, in an optimal cost-based optimized manner, as distributed system resources are available to handle the bubbles.

7. The computer system of claim 1, wherein the bubble and the another bubble are the same bubble.

8. The computer system of claim 1, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to execute the job graph using resources of the distributed system comprise the one or more hardware processors configured to execute the instructions stored in the system memory to execute each bubble in plurality of bubbles as input for the bubble is available.

9. The computer system of claim 1, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to execute the job graph using resources of the distributed system comprise the one or more hardware processors configured to execute the instructions stored in the system memory to execute at least one bubble prior to at least one other bubble based bubble priority.

10. A computer system comprising:

one or more hardware processors;

system memory coupled to the one or more hardware processors, the system memory storing instructions that are executable by the one or more hardware processors; and

the one or more hardware processors configured to execute the instructions stored in the system memory to optimize a query for execution in a scale-out distributed system, including the following;

access a query plan, the query plan to implement logical intent of the query within the scale-out distributed system, the query plan including a plurality of supervertices, each supervertex including one or more vertices of a same vertex type;

determine resource consumption and dependencies for each of the plurality of supervertices;

based at least on the determined resource consumption and dependencies for each of the plurality of supervertices, assign the plurality of supervertices into a plurality of bubbles, each of the plurality of bubbles assigned one or more of the plurality of supervertices; and

annotate the query plan with bubble annotations and bubble boundary annotations, the bubble annotations identifying supervertices, from among the plurality of supervertices, that are to be scheduled as a group for execution within the scale-out distributed system, bubble boundary annotations identifying when intermediate outputs are to be stored to durable storage within the scale-out distributed system.

11. The computer system of claim 10, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to access a query plan comprise the one or more hardware processors configured to execute the instructions stored in the system memory to access an Abstract Syntax Tree.

12. The computer system of claim 10, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to assign the plurality of supervertices into a plurality of bubbles comprise the one or more hardware processors configured to execute the instructions stored in the system memory to assign a sub-plurality of supervertices, from among the plurality of supervertices, to at least one of the plurality of bubbles.

13. The computer system of claim 10, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to assign the plurality of supervertices into a plurality of bubbles comprise the one or more hardware processors configured to execute the instructions stored in the system memory to assign the plurality of supervertices into a plurality of bubbles in a cost-based optimized manner based on a parallelism metric and an intermediate data size metric.

14. A computer system comprising:

one or more hardware processors;

system memory coupled to the one or more hardware processors, the system memory storing instructions that are executable by the one or more hardware processors; and

the one or more hardware processors configured to execute the instructions stored in the system memory to implement query plan execution in a distributed system, including the following;

access an annotated query plan, the annotated query plan representing a logical intent of a query to retrieve specified data from a data source, the annotated query plan annotated with bubble annotations and bubble boundary annotations, the bubble annotations defining how a plurality of supervertices are to be allocated among a plurality of bubbles in a job graph, each supervertex including one or more vertices of a same vertex type, the bubble boundary annotations defining boundaries between the plurality of bubbles;

form the job graph for the annotated query plan, the job graph including the plurality of bubbles, at least one of the plurality of supervertices allocated to each bubble in the plurality of bubbles based at least on the bubble annotations, boundaries between adjacent bubbles in the plurality of bubbles representing when intermediate results are to be stored to durable storage; and

execute the job graph to implement the annotated query plan, including for each bubble of the plurality of bubbles;

execute each vertex in the bubble including;

send any intra-bubble output to a next vertex in the bubble via a non-durable medium; and

store any inter-bubble output for a subsequent vertex in another bubble in durable storage to provide fault tolerance for the another bubble.

15. The computer system of claim 14, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to execute the job graph to implement the annotated query plan comprise the one or more hardware processors configured to execute the instructions stored in the system memory to, for each bubble:

assign the bubble to a pre-scheduling queue; and

schedule the bubble from the pre-scheduling queue for execution when input for each vertex in the bubble is ready and in view of vertex priority and resource availability in the distributed system.

16. The computer system of claim 15, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to schedule the bubble from the pre-scheduling queue for execution comprise the one or more hardware processors configured to execute the instructions stored in the system memory to schedule the bubble for execution based on the bubble having a higher priority than at least one other bubble.

17. The computer system of claim 15, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to schedule the bubble from the pre-scheduling queue for execution comprise the one or more hardware processors configured to execute the instructions stored in the system memory to schedule the bubble for execution based on the input from the bubble being stored in durable storage.

18. The computer system of claim 15, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to schedule the bubble from the pre-scheduling queue for execution comprise the one or more hardware processors configured to execute the instructions stored in the system memory to schedule the bubble for execution in parallel with at least one other bubble in view of the resource availability in the distributed system.

19. The computer system of claim 14, wherein the one or more hardware processors configured to execute the instructions stored in the system memory to send any intra-bubble output to a next vertex in the bubble via the non-durable medium comprise the one or more hardware processors configured to execute the instructions stored in the system memory to send any intra-bubble output to the next vertex in the bubble via network communication.

20. The computer system of claim 14, wherein each vertex implements one or more of the following:

extracting data, transforming data, filtering data, joining data, sorting data, aggregating data, merging data, grouping data, accessing data, or storing data.