Prioritized execution of plans for obtaining and/or processing data

• US 9,389,909 B1
• Filed: 04/28/2015
• Issued: 07/12/2016
• Est. Priority Date: 04/28/2015
• Status: Active Grant

• Current Assignee: Zoomdata, Inc. (Global Software, Inc.)
• Original Assignee: Zoomdata, Inc. (Global Software, Inc.)
• Inventors: Langseth, Justin, Alarcon, Jorge, Farchtchi, Ruhollah, Aref, Farzad
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Kamran, Mehran
• Application Number:
  US14/698,421
• Time in Patent Office: 441 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 9/4818 Priority circuits therefor
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

Systems and methods of prioritizing execution of plans for obtaining and/or processing data based on partial execution of the plans are presented herein. In certain implementations, one or more plans may be executed. Costs associated with individual ones of the plans may be estimated based on partial execution of respective ones of the plans. Based on a comparison between the estimated costs, the execution of at least one of plans may be prioritized over at least the execution of the other ones of the plans.

Claims

1. A computer-implemented method of prioritizing execution of plans for obtaining and/or processing data based on partial execution of the plans, the method being implemented by a computer system that includes one or more physical processors executing one or more computer program instructions which, when executed, perform the method, the method comprising:

determining, by the computer system, at least a first plan and a second plan for obtaining data from one or more data sources and/or processing the obtained data, wherein the first plan comprises utilizing a first path to obtain results related to at least one data set from a data source, and the second plan comprises utilizing a second path different from the first path to obtain results related to the at least one data set from the data source;

executing, by the computer system, the first plan and the second plan;

estimating, by the computer system, based on partial execution of the first plan, a first cost for fully executing the first plan, wherein the estimation of the first cost comprises estimating, based on the partial execution of the first plan, a first delay associated with presenting a set of results related to a data set when the first plan is used such that the first cost is estimated based on the estimated first delay;

estimating, by the computer system, based on partial execution of the second plan, a second cost for fully executing the second plan, wherein the estimation of the second cost comprises estimating, based on the partial execution of the second plan, a second delay associated with presenting a set of results related to the data set when the second plan is used such that the second cost is estimated based on the estimated second delay, and wherein the first cost and the second cost are estimated after the execution of the first plan and the execution of the second plan have begun and before the execution of the first plan and the execution of the second plan are completed; and

prioritizing, by the computer system, the execution of one of the first plan or the second plan over at least the execution of the other one of the first plan or the second plan based on a comparison of the estimated first cost and the estimated second cost, wherein the prioritization occurs after the execution of the first plan and the execution of the second plan have begun and before the execution of the first plan and the execution of the second plan are completed.

2. The method of claim 1, wherein the execution of the first plan is prioritized over at least execution of the second plan based on the comparison indicating that the estimated first cost is less than the estimated second cost, the method further comprising:

continuing, by the computer system, the execution of the first plan based on the prioritization; and

suspending or canceling, by the computer system, the execution of the second plan based on the prioritization.

3. The method of claim 1, further comprising:

estimating, by the computer system, based on the partial execution of the first plan, a percentage of the first plan that has been executed; and

estimating, by the computer system, based on the partial execution of the second plan, a percentage of the second plan that has been executed,

wherein the first cost for fully executing the first plan is estimated based on a cost of the partial execution of the first plan and the percentage of the first plan that has been executed, and

wherein the second cost for fully executing the second plan is estimated based on a cost of the partial execution of the second plan and the percentage of the second plan that has been executed.

4. The method of claim 1, wherein the first plan comprises obtaining results related to a data set from a first data source before obtaining results related to the data set from a second data source, and the second plan comprises obtaining results related to the data set from the second data source before obtaining results related to the data set from the first data source.

5. The method of claim 1, wherein the first plan comprises obtaining results related to a given data set from a data source that is not utilized in the second plan for obtaining results related to the given data set.

6. The method of claim 1, further comprising:

estimating, based on the partial execution of the first plan, first delays between updates to a presentation of a data set to a user when the first plan is used; and

estimating, based on the partial execution of the second plan, second delays between updates to a presentation of a data set to a user when the second plan is used,

wherein the first cost for fully executing the first plan is estimated based on the estimated first delays, and

wherein the second cost for fully executing the second plan is estimated based on the estimated second delays.

7. The method of claim 1, wherein estimating the first cost is based on predefined performance metrics associated with a first data source that is utilized in the first plan, and wherein estimating the second cost is based on predefined performance metrics associated with a second data source that is utilized in the second plan.

8. The method of claim 7, wherein the predefined performance metrics comprise one or both of latency and throughput of data through the data sources.

9. The method of claim 1, wherein estimating the first cost is based on historical cost information associated with one or more aspects of the first plan, and wherein estimating the second cost is based on historical cost information associated with one or more aspects of the second plan.

10. The method of claim 1, wherein the first plan and the second plan are executed in parallel before the prioritization.

11. The method of claim 10, wherein the first cost is estimated based on the partial execution of the first plan that occurred in parallel with the execution of the second plan, and the second cost is estimated based on the partial execution of the second plan that occurred in parallel with the execution of the first plan.

12. A system for prioritizing execution of plans for obtaining and/or processing data based on partial execution of the plans, the system comprising:

one or more physical processors programmed to execute one or more computer program instructions which, when executed, cause the one or more physical processors to;

determine at least a first plan and a second plan for obtaining data from one or more data sources and/or processing the obtained data, wherein the first plan comprises utilizing a first path to obtain results related to at least one data set from a data source, and the second plan comprises utilizing a second path different from the first path to obtain results related to the at least one data set from the data source;

execute the first plan and the second plan;

estimate, based on partial execution of the first plan, a first cost for fully executing the first plan, wherein the estimation of the first cost comprises estimating, based on the partial execution of the first plan, a first delay associated with presenting a set of results related to a data set when the first plan is used such that the first cost is estimated based on the estimated first delay;

estimate, based on partial execution of the second plan, a second cost for fully executing the second plan, wherein the estimation of the second cost comprises estimating, based on the partial execution of the second plan, a second delay associated with presenting a set of results related to the data set when the second plan is used such that the second cost is estimated based on the estimated second delay, and wherein the first cost and the second cost are estimated after the execution of the first plan and the execution of the second plan have begun and before the execution of the first plan and the execution of the second plan are completed; and

prioritize the execution of one of the first plan or the second plan over at least the execution of the other one of the first plan or the second plan based on a comparison of the estimated first cost and the estimated second cost, wherein the prioritization occurs after the execution of the first plan and the execution of the second plan have begun and before the execution of the first plan and the execution of the second plan are completed.

13. The system of claim 12, wherein the execution of the first plan is prioritized over at least execution of the second plan based on the comparison indicating that the estimated first cost is less than the estimated second cost, and wherein the one or more physical processors are further caused to:

continue the execution of the first plan based on the prioritization; and

suspend or cancel the execution of the second plan based on the prioritization.

14. The system of claim 12, wherein the one or more physical processors are further caused to:

estimate, based on the partial execution of the first plan, a percentage of the first plan that has been executed; and

estimate, based on the partial execution of the second plan, a percentage of the second plan that has been executed,

wherein the first cost for fully executing the first plan is estimated based on a cost of the partial execution of the first plan and the percentage of the first plan that has been executed, and

wherein the second cost for fully executing the second plan is estimated based on a cost of the partial execution of the second plan and the percentage of the second plan that has been executed.

15. The system of claim 12, wherein first plan comprises obtaining results related to a data set from a data source, and the second plan comprises obtaining results related to the data set from the data source.

16. The system of claim 15, wherein the first plan comprises utilizing a first path to obtain results related to the data set from the data source, and the second plan comprises utilizing a second path different than the first path to obtain results related to the data set from the data source.

17. The system of claim 12, wherein the first plan comprises obtaining results related to a data set from a first data source before obtaining results related to the data set from a second data source, and the second plan comprises obtaining results related to the data set from the second data source before obtaining results related to the data set from the first data source.

18. The system of claim 12, wherein the first plan comprises obtaining results related to a given data set from a data source that is not utilized in the second plan for obtaining results related to the given data set.

19. A computer-implemented method of prioritizing execution of plans for obtaining and/or processing data based on partial execution of the plans, the method being implemented by a computer system that includes one or more physical processors executing one or more computer program instructions which, when executed, perform the method, the method comprising:

determining, by the computer system, at least a first plan and a second plan for obtaining data from one or more data sources and/or processing the obtained data, wherein the first plan comprises utilizing a first path to obtain results related to at least one data set from a data source, and the second plan comprises utilizing a second path different from the first path to obtain results related to the at least one data set from the data source;

executing, by the computer system, the first plan and the second plan;

estimating, by the computer system, based on partial execution of the first plan, a first cost for fully executing the first plan wherein the estimation of the first cost comprises estimating, based on the partial execution of the first plan, first delays between updates to a presentation of a data set to a user when the first plan is used such that the first cost is estimated based on the estimated first delays;

estimating, by the computer system, based on partial execution of the second plan, a second cost for fully executing the second plan, wherein the estimation of the second cost comprises estimating, based on the partial execution of the second plan, second delays between updates to a presentation of a data set to a user when the second plan is used such that the second cost is estimated based on the estimated second delays, and wherein the first cost and the second cost are estimated after the execution of the first plan and the execution of the second plan have begun and before the execution of the first plan and the execution of the second plan are completed; and

prioritizing, by the computer system, the execution of one of the first plan or the second plan over at least the execution of the other one of the first plan or the second plan based on a comparison of the estimated first cost and the estimated second cost, wherein the prioritization occurs after the execution of the first plan and the execution of the second plan have begun and before the execution of the first plan and the execution of the second plan are completed.

20. The method of claim 19, wherein the execution of the first plan is prioritized over at least execution of the second plan based on the comparison indicating that the estimated first cost is less than the estimated second cost, the method further comprising:

continuing, by the computer system, the execution of the first plan based on the prioritization; and

suspending or canceling, by the computer system, the execution of the second plan based on the prioritization.

21. The method of claim 19, further comprising:

estimating, by the computer system, based on the partial execution of the first plan, a percentage of the first plan that has been executed; and

estimating, by the computer system, based on the partial execution of the second plan, a percentage of the second plan that has been executed,

wherein the first cost for fully executing the first plan is estimated based on a cost of the partial execution of the first plan and the percentage of the first plan that has been executed, and

wherein the second cost for fully executing the second plan is estimated based on a cost of the partial execution of the second plan and the percentage of the second plan that has been executed.

22. The method of claim 19, wherein the first plan comprises obtaining results related to a given data set from a data source that is not utilized in the second plan for obtaining results related to the given data set.

23. The method of claim 19, wherein the first plan and the second plan are executed in parallel before the prioritization.

24. The method of claim 23, wherein the first cost is estimated based on the partial execution of the first plan that occurred in parallel with the execution of the second plan, and the second cost is estimated based on the partial execution of the second plan that occurred in parallel with the execution of the first plan.