System and method for loading a cache with query results

• US 6,934,699 B1
• Filed: 09/01/1999
• Issued: 08/23/2005
• Est. Priority Date: 09/01/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kossmann, Donald, Ursu, Ioana Mihaela, Haas, Laura Myers
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/388,190
• Time in Patent Office: 2,183 Days
• Field of Search: 707/2, 707/10, 707/104, 707/3, 707/102, 707/100, 711/119, 711/122
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for avoiding accessing a remote database twice, once during query execution and again to retrieve objects identified by the query, when an application requires objects on which to operate. During query plan generation in response to a request for database objects from an application, a query optimizer inserts cache operators into the candidate plans, and then a cost-benefit analysis is undertaken to identify the best plan. The best plan is then used to execute the query, with the cache operators causing objects identified during query execution to be cached locally to the requesting application as the query is being executed, thereby avoiding requiring the application to access the database after query execution.

Claims

1. A computer-implemented method, comprising:

receiving, from a local application program, a query request for objects stored in a remote database, a local cache being accessible to the local application program;

storing objects in the local cache while executing a query in response to the query request;

accessing the objects in the local cache using the local application program, whereby the application program is not required to access the database to retrieve the objects after query execution;

generating at least one query plan in response to the query request, wherein the query plan includes at least one query execution operator, the query plan being characterizable by a plan tree defining top and bottom; and

establishing at least one cache operator for the query plan, the cache operator including a first parameter specifying objects in an input stream to the operator to be copied into the cache and a second parameter specifying which data attributes to be passed through to a next operator in the query plan.

2. The method of claim 1, further comprising:

for at least some query plans, determining a cost and a benefit of including at least one cache operator in the plans; and

selecting a plan to execute, based on the act of determining a cost and a benefit.

3. The method of claim 2, further comprising:

identifying at least one candidate collection of objects in at least one query plan;

for at least a candidate collection, inserting a cache operator for the collection above the plan relative to the respective plan tree; and

estimating a cost and a benefit of the query plan after placement of the cache operator.

4. The method of claim 3, further comprising pruning a query plan based at least in part on the estimating act.

5. The method of claim 3, wherein the estimating act further comprises:

defining a cost of a cache operator of a plan to be proportional to a cardinality of an input stream to the plan; and

defining a benefit of a cache operator of a plan to be proportional to a minimum of;

the cardinality, an output having a most selective local predicate, and an output having a most selective join predicate.

6. The method of claim 1, wherein at least one plan is generated by placing a cache operator high in the plan relative to the respective plan tree.

7. The method of claim 6, wherein the method acts undertaken by the computer include moving at least one cache operator down in the plan relative to the respective plan tree through at least one non-reductive query operator.

8. The method of claim 1, wherein at least one plan is generated by placing a cache operator low in the plan relative to the respective plan tree.

9. The method of claim 8, further comprising selectively moving at least one cache operator up in the plan relative to the respective plan tree through at least one of:

a leaf query operator, and a pipelining operator.

10. A computer program device, comprising:

computer program storage device readable by a digital processing apparatus; and

a program on the program storage device and including instructions executions executable by the digital processing apparatus for performing method acts for caching objects in accordance with query results during query execution, the program comprising;

computer readable code means for receiving a query request for object from and application at a local computer site, the objects being stored in a database remote from the local site;

computer readable code means for generating at least one query plan to identify objects in the database satisfying the request;

computer readable code means for executing the query plan, wherein the query plan includes at least one query execution operator, the query plan being characterizable by a plan tree defining top and a bottom;

computer readable code means for causing at least some objects identified by the means for executing to be copied into a cache at the local computer site contemporaneously with the executing step undertaken by the means for executing, whereby the application program can access the objects in the cache without accessing the database after the query is executed; and

computer readable code means for establishing at least one cache operator for the query plan, the cache operator including a first parameter specifying objects in an input stream to the operator to be copied into the cache and a second parameter specifying which data attributes to be passed through to a next operator in the query plan.

11. The device of claim 10, comprising:

computer readable code means for determining, for at least some query plans, a cost and a benefit of including at least one cache operator in the plans; and

computer readable code means for selecting a plan to execute, based on the means for determining a cost and a benefit.

12. The device of claim 11, further comprising:

computer readable code means for identifying at least one candidate collection of objects in at least one query plan;

computer readable code means for inserting, for at least a candidate collection, a cache operator for the collection above the plan relative to the respective plan tree; and

computer readable code means for estimating a cost and a benefit of the query plan after placement of the cache operator.

13. The device of claim 12, further comprising computer readable code means for pruning a query plan based at least in part on the means for estimating.

14. The device of claim 12, wherein the means for estimating further comprises:

computer readable code means for defining a cost of a cache operator of a plan to be proportional to a cardinality of an input stream to the plan; and

computer readable code means for defining a benefit of a cache operator a plan to be proportional to a minimum of;

the cardinality, an output having a most selective local predicate, and an output having a most selective join predicate.

15. The device of claim 10, wherein at least one plan is generated by placing a cache operator high in the plan relative to the respective plan tree.

16. The device of claim 15, wherein device include computer readable code means for moving at least one cache operator down in the plan relative to the respective plan tree through at least one non-reductive query operator.

17. The device of claim 10, wherein at least one plan is generated by placing a cache operator low in the plan relative to the respective plan tree.

18. The device of claim 17, wherein the device further includes computer readable code means for selectively moving at least one cache operator up in the plan relative to the respective plan tree through at least one of:

a leaf query operator, and a pipelining operator.