Progressive refinement of a federated query plan during query execution

• US 20070226186A1
• Filed: 03/24/2006
• Published: 09/27/2007
• Est. Priority Date: 03/24/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kache, Holger, Raman, Vijayshankar, Markl, Volker, Ewen, Stephan
• Granted Patent: US 7,877,381 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

A way for progressively refining a query execution plan during query execution in a federated data system is provided. Re-optimization constraints are placed in the query execution plan during query compilation. When a re-optimization constraint is violated during query execution, a model of the query execution plan is refined using a partially executed query to form a new query execution plan. The new query execution plan is compiled. The compiled new query execution plan is executed.

Claims

1. A computer program product comprising a computer usable medium including computer usable program code for progressively refining a federated query execution plan in a federated data system, the computer program product comprising:

computer usable program code for executing a federated query according to a federated query execution plan; and

computer usable program code for refining the federated query execution plan during execution of the federated query.

2. The computer program product of claim 1, wherein the computer usable program code for refining the federated query execution plan further comprises:

computer usable program code for placing at least one re-optimization constraint in the federated query execution plan at a location where remote data is received and further processed by the federated data system during compilation of the federated query;

computer usable program code, responsive to the at least one re-optimization constraint being violated during execution of the federated query execution plan, for optimizing the federated query execution plan by refining a model of the federated query execution plan using a partially executed federated query execution plan;

computer usable program code for recompiling the federated query; and

computer usable program code for re-executing the federated query execution plan.

3. The computer program product of claim 2, wherein the computer usable program code for re-executing the federated query execution plan re-uses intermediate results from the partially executed federated query execution plan.

4. The computer program product of claim 3, further comprising:

computer usable program code for using heuristics to determine whether to retain the intermediate results.

5. The computer program product of claim 2, wherein the re-optimization constraints comprise a measure used in a cost model of a federated query optimizer.

6. The computer program product of claim 5, wherein the measure comprises constraints in at least one of estimated cardinality, query execution cost, CPU time, IO time, or communication time.

7. The computer program product of claim 2, wherein the re-optimization constraints are materialized.

8. The computer program product of claim 7, wherein costs of materialization are not considered when optimizing the federated query execution plan.

9. The computer program product of claim 7, wherein costs of materialization are considered when optimizing the federated query execution plan.

10. The computer program product of claim 2, further comprising:

computer usable program code for repeating the placing, optimizing, recompiling, and re-executing steps until a query result is achieved.

11. The computer program product of claim 2, wherein the re-optimization constraints are materialized only up to a certain expected size.

12. The computer program product of claim 2, wherein the re-optimization constraints are not materialized for robust spots.

13. A computer program product comprising a computer usable medium including computer usable program code for progressively refining a query execution plan in a data system, the computer program product comprising:

computer usable program code for placing at least one re-optimization constraint in the query execution plan during compilation of the query;

computer usable program code responsive to the at least one re-optimization constraint being violated during execution of the query execution plan, for optimizing the query execution plan by refining a model of the query execution plan using a partially executed query execution plan;

computer usable program code for recompiling the query;

computer usable program code for re-executing the query execution plan; and

computer usable program code for repeating the placing, optimizing, recompiling, and re-executing steps until a query result is achieved.

14. The computer program product of claim 13, wherein the computer usable program code for re-executing the query execution plan re-uses intermediate results from the partially executed query execution plan.

15. The computer program product of claim 14, further comprising:

computer usable program code for using heuristics to determine whether to retain the intermediate results.

16. A computer implemented method for progressively refining a federated query execution plan in a federated data system, the computer implemented method comprising:

executing a federated query according to a federated query execution plan; and

refining the federated query execution plan during execution of the federated query.

17. The computer implemented method of claim 16, wherein the step of refining the federated query execution plan further comprises:

placing at least one re-optimization constraint in the federated query execution plan at a location where remote data is received and further processed by the federated data system during compilation of the federated query;

responsive to the at least one re-optimization constraint being violated during execution of the federated query execution plan, optimizing the federated query execution plan by refining a model of the federated query execution plan using a partially executed federated query execution plan;

recompiling the federated query; and

re-executing the federated query execution plan.

18. The computer implemented method of claim 17, wherein re-executing the federated query execution plan re-uses intermediate results from the partially executed federated query execution plan.

19. The computer implemented method of claim 18, further comprising:

using heuristics to determine whether to retain the intermediate results.

20. The computer implemented method of claim 17, wherein the re-optimization constraints comprise a measure used in a cost model of a federated query optimizer.

21. The computer implemented method of claim 20, wherein the measure comprises constraints in estimated cardinality, or query execution cost, or CPU time, or IO time, or communication time.

22. The computer implemented method of claim 17, wherein the re-optimization constraints are materialized.

23. The computer implemented method of claim 22, wherein costs of materialization are not considered when optimizing the federated query execution plan.

24. The computer implemented method of claim 22, wherein costs of materialization are considered when optimizing the federated query execution plan.

25. The computer implemented method of claim 17, further comprising:

repeating the placing, optimizing, recompiling, and re-executing steps until a query result is achieved.

26. The computer implemented method of claim 17, wherein the re-optimization constraints are materialized only up to a certain expected size.

27. The computer implemented method of claim 17, wherein the re-optimization constraints are not materialized for robust spots.

29. The computer implemented method of claim 26, wherein re-executing the query execution plan re-uses intermediate results from the partially executed federated query execution plan.

30. The computer implemented method of claim 29, further comprising:

using heuristics to determine whether to retain the intermediate results.

28. A computer implemented method for progressively refining a query execution plan in a data system, the computer implemented method comprising:

placing at least one re-optimization constraint in the query execution plan during compilation of the federated query;

responsive to the at least one re-optimization constraint being violated during execution of the query execution plan, optimizing the query execution plan by refining a model of the query execution plan using a partially executed federated query execution plan;

recompiling the query;

re-executing the query execution plan; and

repeating the placing, optimizing, recompiling, and re-executing steps until a query result is achieved.