System and method for optimizing queries with aggregates and collection conversions

• US 6,240,406 B1
• Filed: 08/31/1998
• Issued: 05/29/2001
• Est. Priority Date: 08/31/1998
• Status: Expired due to Term

• Current Assignee: Trustees Of The University Of Pennsylvania (University of Pennsylvania)
• Original Assignee: Trustees Of The University Of Pennsylvania (University of Pennsylvania)
• Inventors: Tannen, Val Breazu
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/144,281
• Time in Patent Office: 1,002 Days
• Field of Search: 707/2, 707/1, 707/3, 707/4, 707/5, 707/6, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Systems and methods for optimizing database queries involving aggregates identify instantiations of rules in an internal language representation of the original query, and then applies the rules to those instantiations to form an optimized query execution plan.

Claims

1. A method of optimizing a query of a database comprising

translating the query into an internal language;

identifying, in the translated query, candidates for optimization; and

applying a set of optimization rules to the identified candidates to form a transformed query;

where the query comprises an operation selected from the group consisting of aggregate operations and collection conversion operations; and

where the identified candidates comprise a translation of the operation selected from the group consisting of aggregate operations and collection conversion operations.

2. The method of claim 1, wherein

identifying candidates for optimization includes

identifying one candidate for optimization, wherein

applying a set of optimization rules includes

applying the one of the set of optimization rules corresponding to the identified candidate, and

further including

repeating the identifying and applying operations until no other candidates can be identified.

3. The method of claim 1 wherein

identifying candidates for optimization includes

looking for predetermined patterns, and wherein

applying a set of optimization rules includes

applying a set of rules corresponding to the pattern.

4. The method of claim 3, wherein looking for predetermined patterns includes

looking for horizontal grouping patterns.

5. The method of claim 1, wherein the step of identifying query candidates includes

identifying a loop singleton instance.

6. The method of claim 1, wherein the step of identifying query candidates includes

identifying a loop associate instance.

7. The method of claim 1, wherein the step of identifying query candidates includes

identifying a loop operation instance.

8. The method of claim 1, wherein the step of identifying query candidates includes

identifying a loop record algebra instance.

9. The method of claim 1, wherein the step of identifying query candidates includes

identifying an operation record algebra instance.

10. The method of claim 1, wherein the step of identifying query candidates includes

identifying a convert singleton instance.

11. The method of claim 1, wherein the step of identifying query candidates includes

identifying a convert algebra instance.

12. The method of claim 1, wherein the step of identifying query candidates includes

identifying a convert operation instance.

13. A computer system optimizing a query of a database comprising:

compiler means for translating the query into an internal language;

means for identifying, in the translated query, candidates for optimization; and

means for applying a set of optimization rules to the identified candidates to form a transformed query;

where the query comprises an operation selected from the group consisting of aggregate operations and collection conversion operations; and

where the identified candidates comprise a translation of the operation selected from the group consisting of aggregate operations and collection conversion operations.

14. The computer system of claim 13, wherein the

means for identifying candidates for optimization includes

means for identifying one candidate for optimization, wherein the means for applying a set of optimization rules includes

means for applying the one of the set of optimization rules corresponding to the identified candidate, and

further including

means for activating the identifying means and the applying means until no other candidates can be identified.