Detecting and processing cache hits for queries with aggregates

• US 9,563,662 B2
• Filed: 10/31/2007
• Issued: 02/07/2017
• Est. Priority Date: 06/27/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Schneider, Donovan Alfred, Suen, Edward Shaw-Lee, Zaman, Kazi Atif-Uz
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): Black, Linh
• Application Number:
  US11/931,947
• Publication Number:
  US 20080077557A1
• Time in Patent Office: 3,387 Days
• Field of Search: 707 4- 5, 707713-715, 707765-767
• 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 non-transitory computer-usable storage medium storing instructions executable by a processor, said instructions comprising:

a first set of instructions configured to maintain a select list index of a plurality of cached queries, wherein

said select list index comprises key field entries and data item field entries,

said select list index stores one or more unique items,

each of said one or more unique items is extracted from a clause of a statement of at least one cached query of said plurality of cached queries,

said plurality of cached queries are stored in a cache,

each key field entry stores a unique item of said one or more unique items,

said each key field entry is associated with a corresponding data item field entry of said data item field entries,

said corresponding data item field entry is configured to store information identifying said at least one cached query that comprises said unique item stored in said each key field entry, and

at least one of said one or more unique items comprises a precomputed aggregate from a previously cached query; and

a second set of instructions configured to determine a list of candidate queries configured to be used to answer a new query that includes at least a first unique item and a second unique item, wherein

the list of candidate queries is determined based on an intersection of a first set of cached queries that include the first unique item and a second set of cached queries that include the second unique item.

2. The non-transitory computer-usable storage medium of claim 1, wherein

said list of candidate queries comprises a subset of said plurality of cached queries,

said new query comprises a new query aggregate,

said new query uses a cross-section of results of previously computed non-identical queries,

said new query aggregate does not exactly match any of said unique items in said select list index,

said aggregate in said select list is evaluated to be usable for performing aggregate roll-up for said new query aggregate, and

said at least one cached query that comprises said aggregate is identified as a candidate query to potentially be used to answer said new query.

3. The non-transitory computer-usable storage medium of claim 1, wherein

said one or more unique items further comprise a first unique item, wherein said first unique item is an expression comprising a mathematical operator.

8. The non-transitory computer-usable storage medium of claim 1, wherein,

said one or more unique items further comprise a first unique item and a second unique item,

said first unique item is a first subexpression generated by a decomposition of an expression,

said second unique item is a second subexpression generated by said decomposition of said expression,

said decomposition comprises storing as said first unique item a first portion of

said expression in said select list index,

said decomposition further comprises storing as said second unique item a second portion of said expression in said select list index, and

said first portion and said second portion are distinct.

9. The non-transitory computer-usable storage medium of claim 8, wherein,

said new query uses a cross-section of results of previously computed non-identical queries,

said new query comprises an expression comprising a mathematical operator, said first unique item, and said second unique item, and

said list of candidate queries comprises an intersection of cached queries for said first unique item and said second unique item.

10. The non-transitory computer-usable storage medium of claim 1, wherein

said select list index is revised to reflect additions to and deletions from said cache.

20. The non-transitory computer-usable storage medium of claim 2, wherein

said at least one cached query identified as said candidate query is part of a first set of potential candidate queries,

said new query comprises a new query item that matches one of said unique items in said select list index,

a second subset of cached queries comprising said one unique item are identified as a second set of potential candidate queries, and

said list is determined by intersecting said first set of potential candidate queries with said second set of potential candidate queries.

4. A non-transitory computer-usable storage medium storing instructions executable by a processor, said instructions comprising:

a first set of instructions configured to maintain an index of a plurality of aggregates, wherein

said index comprises key field entries and data item field entries,

said index stores one or more unique items comprising a precomputed aggregate from a previously cached query,

each of said one or more unique items is aggregated upon by one or more aggregates extracted from a clause of a statement of at least one cached query of a plurality of cached queries,

said plurality of cached queries are stored in a cache, and

each key field entry stores a unique item of said one or more unique items,

said each key field entry is associated with a corresponding data item field entry of said data item field entries,

said corresponding data item field entry is configured to store information identifying said one or more aggregates that operate upon said unique item, wherein said one or more aggregates are drawn from a select list index; and

a second set of instructions configured to access said index and rewrite a selected aggregate in a new query, said second set of instructions is configured to rewrite said selected aggregate only if an exact match for said selected aggregate cannot be found in said select list index.

5. The non-transitory computer-usable storage medium of claim 4, wherein

said one or more unique items further comprise a first unique item,

said first unique item is a first subexpression generated by a decomposition of an expression.

6. The non-transitory computer-usable storage medium of claim 4, wherein

said one or more aggregates in said data item field comprise only distributive aggregates.

7. The non-transitory computer-usable storage medium of claim 5, wherein,

said decomposition comprises storing a first portion of said expression in said index, and

said decomposition further comprises excluding from said first portion a mathematical operator and a constant.

11. The non-transitory computer-usable storage medium of claim 4, wherein

said select list index comprises one entry for each of said one or more unique items, and

each entry corresponds to a set of cached queries that comprise said each unique item.

12. The non-transitory computer-usable storage medium of claim 4, wherein

said index is revised to reflect additions to and deletions from said cache.

13. The non-transitory computer-usable storage medium of claim 4, wherein

said select list index is revised to reflect said additions to and said deletions from said cache.

14. The non-transitory computer-usable storage medium of claim 4, wherein

said instructions configured to rewrite said selected aggregate are limited to rolling up results of said one or more aggregates.

15. The non-transitory computer-usable storage medium of claim 4, wherein

said instructions configured to rewrite said selected aggregate further comprise a third set of instructions configured to perform a rewrite evaluation of said at least one cached query that comprises said at least one aggregate, and

said rewrite evaluation comprises a check to ensure that all columns associated with said selected aggregate are present in said at least one cached query.

16. The non-transitory computer-usable storage medium of claim 4, further comprising a third set of instructions configured to ensure that all filters of said are compatible with said selected aggregate.

17. The non-transitory computer-usable storage medium of claim 16, wherein said filters comprise a where clause.

18. The non-transitory computer-usable storage medium of claim 16, wherein said filters comprise a having clause.

19. The non-transitory computer-usable storage medium of claim 4, wherein

said selected aggregate operates on a new query item,

said new query item matches at least one unique item in said index,

at least one aggregate of said one or more aggregates that operate upon said one unique item is evaluated to be usable for performing aggregate rewrite for said selected aggregate, and

said selected aggregate in said new query is rewritten in terms of said at least one aggregate of said one or more aggregates.