Detecting and processing cache hits for queries with aggregates

• US 7,499,910 B2
• Filed: 06/27/2002
• Issued: 03/03/2009
• Est. Priority Date: 06/27/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Siebel Systems Inc. (Oracle Corporation)
• Inventors: Schneider, Donovan Alfred, Zaman, Kazi Atif-Uz, Suen, Edward Shaw-Lee
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): DANG, THANH HA T
• Application Number:
  US10/186,344
• Publication Number:
  US 20070208690A1
• Time in Patent Office: 2,441 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24553 of query operations
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Techniques to improve query caching performance by efficiently selecting queries stored in a cache for evaluation and increasing the cache hit rate by allowing for inexact matches. A list of candidate queries stored in the cache that potentially could be used to answer a new query is first determined. This list may include all cached queries, cached queries containing exact matches for select list items, or cached queries containing exact and/or inexact matches. Each of at least one candidate query is then evaluated to determine whether or not there is a cache hit, which indicates that the candidate query could be used to answer the new query. The evaluation is performed using a set of rules that allows for inexact matches of aggregates, if any, in the new query. A query plan is generated for the new query based on a specific candidate query with a cache hit.

Claims

1. A computer-readable program code embedded in a memory, wherein when a computer system executes the computer-readable program code embedded in the memory to perform a method for supporting query caching, the method comprising:

determining a list of candidate queries from a plurality of queries that are stored in a cache in response to receiving a new query, wherein the list comprises a subset of the plurality of queries, wherein the subset is less than all of the plurality of queries, and wherein the determining comprises

for each item in a select list of the new query, obtaining a set of cached queries that include the each item in the select list,

for the each item in the select list of the new query without an exact match in the select list of at least one cached query, obtaining a set of cached queries using aggregate rewrite, and

forming the list of candidate queries by intersecting the set of cached queries for the each item in the select list of the new query and the set of cached queries for the each item in the select list of the new query without an exact match in the select list of the at least one cached query;

evaluating each of the candidate queries in the list to determine one candidate query that is a cache hit, the cache hit indicating a stored result of the one candidate query which answers the new query, wherein the evaluating is performed using a set of rules that allows for inexact matches between one or more aggregates included in the new query and one or more aggregates included in the candidate queries in the list;

generating a result for the new query using the stored result for the one candidate query; and

storing the result of the new query.

2. The computer-readable program code embedded in the memory of claim 1, wherein the list of candidate queries includes all of the plurality of cached queries.

3. The computer-readable program code embedded in the memory of claim 1, wherein the list of candidate queries is determined by matching items in the select list of the new query with items in the select list of each of the plurality of cached queries.

4. The computer-readable program code embedded in the memory of claim 3, wherein the matching items in the select list is performed using a select list index.

5. The computer-readable program code embedded in the memory of claim 4, wherein

a matched item is an item in the select list of the new query that is found in the select list index, and

an unmatched item is an item in the select list of the new query that is not found in the select list index.

6. The computer-readable program code embedded in the memory of claim 4, wherein the matching further comprises:

looking up a key for each item in the select list of the new query; and

retrieving a data item associated with the key.

7. The computer-readable program code embedded in the memory of claim 1, wherein the list of candidate queries is determined by comparing the new query against each of the plurality of cached queries.

8. The computer-readable program code embedded in the memory of claim 7, wherein the comparing includes rewriting the one or more aggregates included in the select list of the new query based on the cached query against which the new query is being compared.

9. The computer-readable program code embedded in the memory of claim 8, wherein the one or more aggregates included in the select list of the new query is only rewritten if an exact match is not found in the select list for the cached query against which the new query is being compared.

10. The computer-readable program code embedded in the memory of claim 8, wherein only distributive aggregates, if any, included in the select list of the new query are rewritten.

11. The computer-readable program code embedded in the memory of claim 8, wherein the rewriting of each aggregate in the select list of the new query is performed using an aggregate index.

12. The computer-readable program code embedded in the memory of claim 7, wherein the comparing includes rewriting one or more subexpressions of one or more expressions included in the select list of the new query based on the cached query against which the new query is being compared.

13. The computer-readable program code embedded in the memory of claim 1, wherein the set of rules, when implemented, checks for permissible roll-ups of aggregates.

14. The computer-readable program code embedded in the memory of claim 13, wherein the permissible aggregate roll-ups are determined by evaluating restrictions included in the new query against restrictions included in the cached query.

15. The computer-readable program code embedded in the memory of claim 1, further comprises generating a query plan for the new query based on the one candidate query.

16. The computer-readable program code embedded in the memory of claim 15, wherein the candidate queries in the list are evaluated one at a time and the one candidate query is the first candidate query with a cache hit.

17. The computer-readable program code embedded in the memory of claim 1, wherein the new query contains a SELECT field of “

lastname, firstname”

, a FROM field of “

employees” and

a WHERE field of “

gender= “

male”

AND age >

50”

.

18. The computer-readable program code embedded in the memory of claim 1, wherein obtaining the set of cached queries for the select list using aggregate rewrite further comprises:

obtaining a set of aggregates for that select list in the new query without an exact match in the select list of the at least one cached query; and

performing a union on the set of cached queries for all aggregates in the set of aggregates.

19. The computer-readable program code embedded in the memory of claim 18, wherein the union is the set of cached queries that supports the select list in the new query without an exact match in the select list of the at least one cached query.

20. In a computer system, a method comprising:

determining a list of at least two candidate queries from a plurality of queries stored in a cache in response to receiving a new query, wherein the list comprises a subset of the plurality of queries, wherein the subset is less than all of the plurality of queries, and wherein the determining comprises

for each item in a select list of the new query, obtaining a set of cached queries that include the each item in the select list,

for the each item in the select list of the new query without an exact match in the select list of at least one cached query, obtaining a set of cached queries using aggregate rewrite, and

forming the list of candidate queries by intersecting the set of cached queries for the each item in the select list of the new query and the set of cached queries for the each item in the select list of the new query without an exact match in the select list of the at least one cached query;

evaluating each of the candidate queries in the list to determine one candidate query that is a cache hit, the cache hit indicating a stored result of the one candidate query which answers the new query, wherein the evaluating is performed using a set of rules to allow for inexact matches between one or more aggregates included in the new query and one or more aggregates in the one candidate query;

generating a result for the new query using the stored result of the one candidate query; and

storing the result of the new query.

21. The method of claim 20, further comprising:

generating a query plan for the new query based on the one candidate query.