Query routing of federated information systems for fast response time, load balance, availability, and reliability

• US 7,890,496 B2
• Filed: 04/10/2008
• Issued: 02/15/2011
• Est. Priority Date: 08/29/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Li, Wen-Syan, Narang, Inderpal S.
• Primary Examiner(s): Vy; Hung T
• Application Number:
  US12/100,651
• Publication Number:
  US 20080189243A1
• Time in Patent Office: 1,041 Days
• Field of Search: 707/713, 707/718, 707/719, 707/720
• US Class Current: 707/713
• CPC Class Codes: G06F 16/9032 Query formulation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

Disclosed are embodiments of a system for optimizing query processing in a federated information system. The system may be used to identify alternative query plans in a simulated environment and to calculate cost estimates associated with the alternative query plans, based not only on database statistics and query statements, but also based on workload and processing latencies associated with specific data source and with the federated information system as a whole. In addition the calculated cost estimates may also factor in data source availability and reliability. The system may use the alternative query plans and the associated cost estimates to influence query processing in a federated information system by feeding to the federated information system query plans that allow for cost-efficient query plan-level load distribution, cost-efficient query fragment plan-level load distribution, and load distribution based upon quality of service cost constraints.

Claims

1. A system for optimizing query processing in a federated information system, said system comprising:

a processor;

memory elements comprising a computer readable medium operatively connected to said processor;

a calibrator, operating through said processor and memory elements, in communication with said federated information system and adapted to intercept queries to said federated information system;

a simulator, operating through said processor and memory elements, in communication with said calibrator and adapted to derive alternative query plans for each of said queries,

wherein each of said query plans comprises a plurality of query fragment plans associated with at least one data source,

wherein said simulator is further adapted to determine first query fragment cost estimates for each of said query fragment plans,

wherein said calibrator is further adapted to calibrate source-specific cost factors for each data source in said federated information system based on workload associated with said corresponding data source, and

wherein said simulator is further adapted to calculate second query fragment cost estimates by multiplying each of said first query fragment cost estimates times a corresponding one of said source-specific cost factors.

2. The system of claim 1, further comprising agents, operating through said processor and memory elements, adapted to issue an initial query fragment to said specific data source so that said actual query fragment cost for processing said initial query fragment can be recorded and so that said first query fragment cost estimate and said actual query fragment cost can be processed by said calibrator to determine said source-specific cost factor.

3. The system of claim 1, wherein said simulator is further adapted to determine first query cost estimates for each of said query plans.

4. The system of claim 3, wherein said calibrator is further adapted to calibrate a system cost factor based on at least one of processing latency and workload associated with said federated information system, and

wherein said simulator is further adapted to calculate second query cost estimates for each of said query plans by multiplying each of said first query cost estimates times said system cost factor.

5. The system of claim 1, wherein said calibrator is further adapted to calibrate said system cost factor by dividing a sum of actual query costs associated with processing a plurality of different queries in said federated information system by a sum of corresponding first query cost estimates.

6. The system of claim 1, wherein said simulator is further adapted to select and to submit to said federated information system one of said query plans, wherein said one query plan has a lowest second query cost estimate as compared to other query plans with query fragment plans associated with the same set of data sources and wherein said one query plan also has a second total cost estimate that is closest to without being greater than a predetermined cost requirement.

7. The system of claim 1, further comprising agents, operating through said processor and memory elements, adapted to periodically access and determine availability of said data sources, wherein said simulator is further adapted to set at infinity any query fragment cost estimate corresponding to any data source that is determined to be unavailable.

8. The system of claim 7, wherein said simulator is further adapted to determine a third query fragment cost estimate for each of said query fragment plans based on reliability of each of said data sources by multiplying said reliability-sensitive query fragment cost factors for each of said data sources times said second query fragment cost estimates corresponding to each of said data sources.

9. The system of claim 1, wherein said calibrator is adapted to:

monitor and record errors associated with each of said data sources when executing said query fragments,

calculate for each of said data sources a percentage of query fragment processing that results in said errors,

divide said percentage by a predetermined acceptable percentage so as to determine reliability-sensitive query fragment cost factors for each of said data sources.

10. A system for optimizing query processing in a federated information system, said system comprising:

a processor;

memory elements comprising a computer readable medium operatively connected to said processor;

a calibrator, operating through said processor and memory elements, in communication with said federated information system and adapted to intercept queries to said federated information system; and

a simulator, operating through said processor and memory elements, in communication with said calibrator and adapted to derive alternative query plans for each of said queries and to determine a first query cost estimate for each of said query plans,

wherein said calibrator is adapted to calibrate a system cost factor for said federated information system based on workload associated with said federated information system, and

wherein said simulator is further adapted to calculate second query cost estimates for each of said query plans by multiplying each of said first query cost estimate times said system cost factor and to balance workload distribution by select a plurality of query plans based on said second query cost estimates, and each time said query is requested, submitting any one of said plurality of query plans to said federated information system.

11. The system of claim 10, wherein said simulator is adapted to limit said plurality of query plans by clustering query plans in groups such that each query plan in a given group has query fragments associated with the same set of sources and by selecting the query plans having the lowest second query cost estimates from each of said groups.

12. The system of claim 11, wherein said simulator only balances workload distribution if a query plan with said lowest second query cost estimate is above a predetermined threshold value.

13. The system of claim 10, wherein said simulator is adapted to further limit said plurality of plans by selecting one query plan having the lowest second query cost estimate from amongst said selected query plans having said lowest second query cost estimates from each group and by selecting those query plans having second query cost estimates that are near said lowest second query cost estimate.

14. A system for optimizing query processing in a federated information system, said system comprising:

a processor;

memory elements comprising a computer readable medium operatively connected to said processor;

a calibrator, operating through said processor and memory elements, in communication with said federated information system and adapted to intercept queries to said federated information system; and

a simulator, operating through said processor and memory elements, in communication with said calibrator and adapted to derive alternative query plans for each of said queries and to determine first query fragment cost estimates for each query fragment plan within each of said query plans;

wherein said calibrator is further adapted to calibrate source-specific cost factors for each data source associated with each of said query fragment plans based on workload,

wherein said simulator is further adapted to calculate second query fragment cost estimates for each of said query fragment plans by multiplying each of said first query fragment cost estimates times a corresponding one of said source-specific cost factors, and

wherein said simulator is further adapted to balance workload distribution by selecting one of said query plans for submission to said federated information system each time said query is requested and each time said one query plan is submitted to said federated information system interchanging at least one query fragment plan within said one query plan with other identical query fragment plans based on said second query fragment costs.

15. The system of claim 14, wherein said simulator is further adapted to determine first query cost estimates for each of said query plans.

16. The system of claim 15, wherein said calibrator is further adapted to calibrate a system cost factor based on at least one of processing latency and workload associated with said federated information system.

17. The system of claim 16, wherein said calibrator is further adapted to calculate second query cost estimates for each of said query plans by multiplying said first query cost estimate times said system cost factor.

18. The system of claim 17, wherein said simulator is adapted to select as said one query plan a query plan with the lowest second query cost estimate.

19. The system of claim 17, wherein said simulator only balances workload distribution if a workload of said query fragment plan is determined to be above a predetermined threshold.

20. The system of claim 19, further comprising an agent, operating through said processor and memory elements, adapted to issue an initial query fragment to said specific data source so that said actual query fragment cost for processing said initial query fragment can be recorded and so that said first query fragment cost estimate and said actual query fragment cost can be processed by said calibrator to determine said source-specific cost factor.