Detecting and processing cache hits for queries with aggregates

• US 20070208690A1
• Filed: 06/27/2002
• Published: 09/06/2007
• 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, Zaman, Kazi, Suen, Edward
• Granted Patent: US 7,499,910 B2
• Time in Patent Office: Days
• 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 program product operative to support query caching, comprising a computer-usable medium having embodied therein computer-readable program codes for

determining a list of candidate queries stored in a cache that potentially could be used to answer a new query;

and

evaluating each of at least one candidate query in the list to determine whether or not there is a cache hit for the candidate query, the cache hit indicating that the candidate query could be used to answer the new query, wherein the evaluating is performed using a set of rules that allows for inexact matches of aggregates, if any, included in the new query.

2. The computer program product of claim 1, wherein the list of candidate queries includes all cached queries.

3. The computer program product of claim 1, wherein the list of candidate queries is determined by matching items in a select list of the new query with items in the select list of each cached query.

4. The computer program product of claim 3, wherein the matching of the select list items is performed using a select list index.

5. The computer program product of claim 1, wherein the list of candidate queries is determined by comparing the new query against each cached query.

6. The computer program product of claim 5, wherein the comparing includes rewriting one or more aggregates included in a select list of the new query based on the cached query being compared against.

7. The computer program product of claim 6, wherein an aggregate 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 being compared against.

8. The computer program product of claim 6, wherein only distributive aggregates, if any, included in the select list of the new query are rewritten.

9. The computer program product of claim 6, wherein the rewriting of each aggregate in the select list of the new query is performed using an aggregate index.

10. The computer program product of claim 5, wherein the comparing includes rewriting one or more subexpressions of one or more expressions included in a select list of the new query based on the cached query being compared against.

11. The computer program product of claim 1, wherein the computer-readable program codes for determining include computer-readable program codes for

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

forming the list of candidate queries by intersecting sets of cached queries obtained for all select list items in the new query.

12. The computer program product of claim 1, wherein the computer-readable program codes for determining include computer-readable program codes for

for each item in a select list of the new query with an exact match in the select list of at least one cached query, obtaining a set of cached queries that include the select list item,

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

forming the list of candidate queries by intersecting sets of cached queries obtained for all select list items in the new query.

13. The computer program product of claim 12, wherein the set of cached queries for each select list item without an exact match is obtained by

obtaining a set of aggregates in the cached queries that could be used to rewrite an aggregate for the select list item without the exact match,

for each aggregate in the aggregate set, obtaining a set of cached queries that include the aggregate, and

performing a union of sets of cached queries obtained for all aggregates in the aggregate set.

14. The computer program product of claim 1, wherein the set of rules check for permissible roll-ups of aggregates.

15. The computer program product of claim 14, wherein the permissible aggregate roll-ups are determined by evaluating restrictions included in the new query against restrictions included in the cached query.

16. The computer program product of claim 1, wherein the computer-usable medium is further embodied with computer-readable program codes for generating a query plan for the new query based on a selected candidate query with a cache hit.

17. The computer program product of claim 16, wherein the candidate queries in the list are evaluated one at a time and the selected candidate query is the first candidate query with a cache hit.

18. A computer program product comprising a computer-usable medium having embodied therein computer-readable program codes for maintaining a data structure used to support query caching, the data structure including

a key field for storing unique items in one or more clauses of statements used for queries stored in a cache, wherein the unique items include aggregates;

and

a data item field for storing information indicative of which cached queries include the unique items in the key field in their statements, and

wherein the data structure is accessed to determine a list of candidate queries from among the queries stored in the cache that potentially could be used to answer a new query, and wherein the aggregates in the key field are usable for performing aggregate roll-up.

19. The computer program product of claim 18, wherein the data structure includes one entry for each unique item, and wherein each entry includes a respective unique item and a set of cached queries that include that unique item.

20. The computer program product of claim 18, wherein the unique items further include expressions.

21. A computer program product comprising a computer-usable medium having embodied therein computer-readable program codes for maintaining a data structure used to support query caching, the data structure including

a key field for storing unique items being aggregated by aggregates in queries stored in a cache;

and

a data item field for storing aggregates that operate on the unique items in the key field, and

wherein the data structure is accessed to rewrite an aggregate in a new query based on aggregates in the cached queries.

22. The computer program product of claim 21, wherein the data structure includes one entry for each unique item, and wherein each entry includes a respective unique item and a set of aggregates in the cached queries that operate on that unique item.

23. The computer program product of claim 21, wherein the data item field includes only distributive aggregates in the cached queries.

24. In a computer system, a method for supporting query caching, comprising:

determining a list of candidate queries stored in a cache that potentially could be used to answer a new query; and

evaluating each of at least one candidate query in the list to determine whether or not there is a cache hit for the candidate query, the cache hit indicating that the candidate query could be used to answer the new query, wherein the evaluating is performed using a set of rules to allow for inexact matches of aggregates, if any, included in the new query.

25. The method of claim 24, further comprising:

generating a query plan for the new query based on a selected candidate query with a cache hit.