Efficient processing of queries in federated database systems

• US 8,538,985 B2
• Filed: 03/11/2008
• Issued: 09/17/2013
• Est. Priority Date: 03/11/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Betawadkar-Norwood, Anjali, Pirahesh, Hamid, Simmen, David Everett
• Primary Examiner(s): GEBRESENBET, DINKU W
• Application Number:
  US12/046,273
• Publication Number:
  US 20090234799A1
• Time in Patent Office: 2,016 Days
• Field of Search: None
• US Class Current: 707/770
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

Methods and apparatus, including computer program products, implementing and using techniques for processing a federated query in a federated database system. A federated query is received at a federated database server. A federated query execution plan is generated based on the received federated query. The federated query execution plan defines one or more source servers of the federated database and a unique subquery to be executed on each of the source servers. The subqueries are distributed to the source servers in accordance with the federated query execution plan. The respective subqueries are executed asynchronously at the source servers. The subquery results are passed to a first designated source server defined in the federated query execution plan. The subquery results are joined and aggregated at the first designated source server into a final query result. The final query result is returned to the federated database server.

Claims

1. A computer-implemented method for processing a federated query in a federated database system, wherein a database table is physically distributed across a first designated source server and a second designated source server, the method comprising:

receiving a federated query at a federated database server;

generating a federated query execution plan at the federated database server, based on the received federated query, the federated query execution plan defining one or more source servers of the federated database and a unique subquery to be executed on each of the defined one or more source servers;

distributing each unique subquery to a defined source server, in accordance with the federated query execution plan;

executing each unique subquery asynchronously by the defined source server;

connecting a source server to a first designated source server among the one or more source servers, using a first message queue, and without the connection passing through the federated database server;

connecting a source server to a second designated source server among the one or more source servers, using a second message queue, and without the connection passing through the federated database server;

passing, based on parameters specified in the federated query, a first subset of the subquery results to the first designated source server, using the first message queue, and a second subset of the subquery results to the second designated source server, using the second message queue;

joining and aggregating the first subset of the subquery results by the first designated source server into a first final query result;

joining and aggregating the second subset of the subquery results by the second designated source server into a second final query result;

returning the first and second final query results to the federated database server; and

combining the first and second final query results at the federated database server.

2. The method of claim 1, wherein passing the first and second subsets of the query results comprises:

determining whether a subquery result is to be sent to the first designated source server or to the second designated source server;

inserting the subquery results from the source server into the first message queue in response to determining that the subquery results should be sent to the first designated source server; and

inserting the subquery results from the source server into the second message queue in response to determining that the subquery should be sent to the second designated source server.

3. The method of claim 2, wherein inserting the subquery results in the first and second message queues, respectively, includes inserting the subquery results into either the first message queue or into the second message queue as rows are produced.

4. The method of claim 1, wherein joining and aggregating the first subset comprises:

receiving the first subset of subquery results from the first message queue; and

formatting the received first subset of subquery results into rows and columns of appropriate types to generate a first final query result.

5. The method of claim 1, wherein joining and aggregating the second subset comprises:

receiving the second subset of subquery results from the first message queue; and

formatting the received second subset of subquery results into rows and columns of appropriate types to generate a second final query result.

6. The method of claim 1, further comprising:

replicating the physically distributed database table onto one or more additional source servers in the federated database system; and

using the information about the replicas of the distributed database table in generating the federated query execution plan.

7. The method of claim 1, wherein generating a federated query execution plan includes:

optimizing the federated query based on metadata to generate an execution strategy involving sideways data movement.

8. The method of claim 7, wherein the metadata includes one or more of:

a server group representing a set of source servers over which partitions or replicas of the distributed database table reside, and a distribution function and a partitioning key indicating how rows of the distributed database table are distributed across the source servers identified by the server group.

9. A computer program product comprising a non-transitory tangible computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

receive a federated query at a federated database server;

generate a federated query execution plan at the federated database server, based on the received federated query, the federated query execution plan defining one or more source servers of the federated database and a unique subquery to be executed on each of the defined one or more source servers, wherein a database table is physically distributed across a first designated source server and a second designated source server;

distribute each unique subquery to a defined source server, in accordance with the federated query execution plan;

execute each unique subquery asynchronously by the defined source server;

connect a source server to a first designated source server among the one or more source servers, using a first message queue, and without the connection passing through the federated database server;

connect a source server to a second designated source server among the one or more source servers, using a second message queue, and without the connection passing through the federated database server;

pass, based on parameters specified in the federated query, a first subset of the subquery results to the first designated source server, using the first message queue, and a second subset of the subquery results to the second designated source server, using the second message queue;

join and aggregate the first subset of the subquery results by the first designated source server into a first final query result;

join and aggregate the second subset of the subquery results by the second designated source server into a second final query result;

return the first and second final query results to the federated database server; and

combine the first and second final query results at the federated database server.

10. The computer program product of claim 9, wherein passing the first and second subsets of the query results comprises:

determining whether a subquery result is to be sent to the first designated source server or to the second designated source server;

inserting the subquery results from the source server into the first message queue in response to determining that the subquery results should be sent to the first designated source server; and

inserting the subquery results from the source server into the second message queue in response to determining that the subquery should be sent to the second designated source server.

11. The computer program product of claim 10, wherein inserting the subquery results in the first and second message queues, respectively, includes inserting the subquery results into either the first message queue or into the second message queue as rows are produced.

12. The computer program product of claim 9, wherein joining and aggregating the first subset comprises:

receiving the first subset of subquery results from the first message queue; and

formatting the received first subset of subquery results into rows and columns of appropriate types to generate a first final query result.

13. The computer program product of claim 9, wherein joining and aggregating the second subset comprises:

receiving the second subset of subquery results from the first message queue; and

formatting the received second subset of subquery results into rows and columns of appropriate types to generate a second final query result.

14. The computer program product of claim 9, wherein the computer readable program when executed on a computer further causes the computer to:

replicate the physically distributed database table onto one or more additional source servers in the federated database system; and

use the information about the replicas of the distributed database table in generating the federated query execution plan.

15. The computer program product of claim 9, wherein generating a federated query execution plan includes:

optimizing the federated query based on metadata to generate an execution strategy involving sideways data movement.

16. The computer program product of claim 15, wherein the metadata includes one or more of:

a server group representing a set of source servers over which partitions or replicas of the distributed database table reside, and a distribution function and a partitioning key indicating how rows of the distributed database table are distributed across the source servers identified by the server group.

17. A federated database system for processing federated queries, comprising:

a federated database server;

one or more source servers, wherein a database table is physically distributed across a first designated source server and a second designated source server; and

a messaging system connecting the federated database server and the one or more source servers, wherein;

the federated database server is operable to;

receive a federated query;

generate a federated query execution plan based on the received federated query, the federated query execution plan defining one or more source servers of the federated database and a unique subquery to be executed on each of the defined one or more source servers;

distribute each unique subquery to a defined source server, in accordance with the federated query execution plan;

the one or more source servers are operable to;

execute each unique subquery asynchronously by the defined source server;

connect a source server to a first designated source server among the one or more source servers, using a first message queue, and without the connection passing through the federated database server;

connect a source server to a second designated source server among the one or more source servers, using a second message queue, and without the connection passing through the federated database server;

pass, based on parameters specified in the federated query, a first subset of the subquery results to the first designated source server, using the first message queue, and a second subset of the subquery results to the second designated source server, using the second message queue;

join and aggregate the first subset of the subquery results by the first designated source server into a first final query result;

join and aggregate the second subset of the subquery results by the second designated source server into a second final query result;

return the first and second final query results to the federated database server; and

combine the first and second final query results at the federated database server.