Hybrid push-down/pull-up of unions with expensive operations in a federated query processor

• US 20070067274A1
• Filed: 09/16/2005
• Published: 03/22/2007
• Est. Priority Date: 09/16/2005
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Han, Wei, Raman, Vijayshankar, Narang, Inderpal
• Application Number:
  US11/228,888
• Publication Number:
  US 20070067274A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

Disclosed are a method and a system for executing a query that requires an expensive process, such as a join, between two or more datasets. If each dataset has multiple partitions that are located at multiple sources, then each of the multiple partitions for each dataset must be unioned prior to completing execution of the query. The method and system develop both a query execution plan and at least one alternative query execution plan to indicate when the process should be pushed down below the unions and when the process should be pulled up above the unions based on collocation of partitions. The query execution plan and the alternative query execution plan(s) are embedded in a composite query execution plan which is evaluated and re-evaluated at run time to determine which of the query execution plan and the alternative query execution plan is currently the most efficient plan and the query is executed, accordingly.

Claims

1. A method for executing a query in a database management system having a plurality of data sources, said method comprising:

receiving said query, wherein said query requires performing a process on multiple first partitions of a first dataset and on multiple second partitions of a second dataset; and

developing a query execution plan such that;

if a first partition is collocated with a second partition on a same source that has a query processor adapted to perform said process, then said process is performed by said query processor on said first partition and on said second partition prior to performing unions of said multiple first partitions and a union of said multiple second partitions; and

if an additional first partition is located on a different source from an additional second partition, then said process is performed on said additional first partition and on said additional second partition after performing a union of at least one of said additional first partition with at least one other first partition and said additional second partition with at least one other second partition.

2. The method of claim 1, further comprising developing at least one alternative query execution plan.

3. The method of claim 2, further comprising:

converting said query execution plan and said alternative query execution plan into query language; and

embedding both said query execution plan and said alternative query execution plan into a composite query execution plan

4. The method of claim 3, further comprising:

dynamically evaluating and re-evaluating said composite query execution plan to determine which of said query execution plan and said alternative query execution plan is currently a most efficient plan based on at least one of current estimated time consumptions, current estimated processor costs, current estimated processor loads and current processor availabilities; and

executing said most efficient plan.

5. The method of claim 1, further comprising after said receiving of said query,

accessing a directory comprising said multiple first partitions of said first dataset, said multiple second partitions of said second dataset, and a list of sources where each of said multiple first partitions and each of said multiple second partitions are located;

and

determining which of said multiple first partitions and said multiple second partitions are collocated on said same source.

6. The method of claim 1, wherein said process further comprises a process between said first dataset, said second dataset and at least one additional dataset.

7. The method of claim 1, wherein said process further comprises one of a joining process, a sorting process, a hashing process and a grouping-by process.

8. A method of executing a query in a database management system having a plurality of data sources, said method comprising:

receiving said query, wherein said query requires performing a join between multiple first partitions of a first dataset and multiple second partitions of a second dataset; and

developing a query execution plan such that;

if a first partition is collocated with a second partition on a same source that has a query processor adapted to perform said join, then said join is performed between said first partition and said second partition by said query processor prior to performing unions of said multiple first partitions and said multiple second partitions; and

if an additional first partition is located on a different source from an additional second partition, then said join is performed between said additional first partition and said additional second partition after performing a union of at least one of said additional first partition with at least one other first partition and said additional second partition with at least one other second partition.

9. The method of claim 8, further comprising developing at least one alternative query execution plan.

10. The method of claim 9, further comprising:

converting said query execution plan and said alternative query execution plan into query language; and

embedding both said query execution plan and said alternative query execution plan into a composite query execution plan

11. The method of claim 10, further comprising:

dynamically evaluating and re-evaluating said composite query execution plan to determine which of said query execution plan and said alternative query execution plan is currently a most efficient plan based on at least one of current estimated time consumptions, current estimated processor costs, current estimated processor loads and current processor availabilities; and

executing said most efficient plan.

12. The method of claim 8, further comprising after said receiving of said query,

accessing a directory comprising said multiple first partitions of said first dataset, said multiple second partitions of said second dataset, and a list of sources where each of said multiple first partitions and each of said multiple second partitions are located;

and

determining which of said multiple first partitions and said multiple second partitions are collocated on said same source.

13. A system for executing a query in a database management system having a plurality of data sources, said system comprising:

a primary operator adapted develop a query execution plan for a query that requires performing a process on multiple first partitions of a first dataset and on multiple second partitions of a second dataset such that;

if a first partition is collocated with a second partition on a same source having a query processor adapted to perform said process, then said process is performed between said first partition and said second partition by said query processor prior to performing unions of said multiple first partitions and said multiple second partitions; and

if an additional first partition is located on a different source from an additional second partition, then said process is performed between said additional first partition and said additional second partition after performing a union between at least one of said additional first partition with at least one other first partition and said additional second partition with at least one other second partition;

an additional query processor in communication with said primary operator and adapted to perform said process; and

a secondary operator in communication with said additional query processor and a plurality of sources for said first dataset and adapted to perform a union of said multiple first partitions.

14. The system of claim 13, wherein said primary operator is further adapted to develop at least one alternative query execution plan and to embed said query execution plan and said alternative query execution plan into a composite query execution plan.

15. The system of claim 14, further comprising an optimizer in communication with said primary operator and adapted to evaluate said composite query execution plan to determine which of said query execution plan and said alternative query execution plan is a most efficient plan based on at least one of estimated time consumptions, estimated processor costs, estimated processor loads and estimated processor availabilities.

16. The system of claim 14, wherein said secondary operator is adapted to dynamically evaluate and re-evaluate said composite query execution plan to determine which of said query execution plan and said alternative query execution plan is currently a most efficient plan based on at least one of current estimated time consumptions, current estimated processor costs, current estimated processor loads and current processor availabilities and to perform said union according to said most efficient plan.

17. The system of claim 16, wherein said additional query processor is further adapted to receive a set of unioned first partitions from said at least one secondary operator and to perform said process on said set of unioned first partitions.

18. The system of claim 13, further comprising a directory comprising source locations for each of said multiple first partitions of said first dataset and each of said multiple second partitions of said second dataset, wherein said primary operator is further adapted to access said directory to determine which of said first partitions and said second partitions are collocated on said same source.

19. The system of claim 13, wherein said query processor of said same source comprises a federated query processor.

20. A program storage device readable by a computer, tangibly embodying a program of instructions executable by said computer to perform a method of executing a query in a database management system having a plurality of data sources, said method comprising:

receiving said query, wherein said query requires performing a process on multiple first partitions of a first dataset and on multiple second partitions of a second dataset; and

developing a query execution plan such that;

if a first partition is collocated with a second partition on a same source that has a query processor adapted to perform said process, then said process is performed on said first partition and on said second partition by said query processor, prior to performing unions of said multiple first partitions and said multiple second partitions; and

if an additional first partition is located on a different source from an additional second partition, then said process is performed on said additional first partition and on said additional second partition after performing a union of at least one of said additional first partition with at least one other first partition and said additional second partition with at least one other second partition.