Optimizing pipelining result sets with fault tolerance in distributed query execution
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification