Method and apparatus for optimizing database queries involving aggregation predicates

• US 6,088,524 A
• Filed: 12/27/1995
• Issued: 07/11/2000
• Est. Priority Date: 12/27/1995
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Levy, Alon Y., Mumick, Inderpal S.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/579,537
• Time in Patent Office: 1,658 Days
• Field of Search: 395/600, 395/601, 395/602, 395/603, 395/604, 364/419
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A method and apparatus for optimizing a query involving aggregation. Aggregation predicates are represented by a constraint language through which relationships involving aggregation predicates can be shown. As a result, new predicates can be inferred from an initial set of aggregation predicates and optimization techniques which involve inferring new predicates can be applied. It is also shown how to restrict the inferences involving aggregation predicates to only those predicates which will lead to new predicates which are relevant to query optimization. In general, the technique is not limited to query optimization, but may be applied to various applications involving the manipulation of aggregation predicates.

Claims

1. A computer implemented method for performing a database query involving aggregation, given an initial set of predicates which includes one or more aggregation predicates, said method comprising the steps of:

translating at least one of said aggregation predicates into a representative form which is a functional term symbolized by f_{R,X,A,Y}, wherein R is a relation having one or more attributes, Xrepresents said attributes of R which are grouped and A is an aggregation function applied on attribute Y of R, said representative form suitable for illustrating a relationship involving said aggregation predicates;

inferring one or more new predicates, using said representative form from said initial set of predicates; and

solving said database query using said new predicates.

2. A computer implemented method according to claim 1 wherein said inferring step comprises inferring predicates in a relation from other predicates of said relation.

3. A computer implemented method according to claim 1 wherein said inferring step comprises inferring predicates in a first relation from predicates in one or more second relations defining said first relation.

4. A computer implemented method according to claim 1 wherein said inferring step comprises inferring predicates in a first relation from predicates in a second relation defined by said first relation.

5. A computer implemented method according to claim 1 wherein said inferring step further comprises the steps of:

identifying said aggregation predicates in said f_{R,X,A,Y} form which are relevant to said query; and

inferring one or more new predicates from said relevant aggregation predicates in said f_{R,X,A,Y} form.

6. A computer implemented method according to claim 5 wherein said relevant aggregation predicates in f_{R,X,A,Y} form, are those which involve R and a groupby list and aggregation attribute pair, GL_R, where R includes any relation upon which said query does an aggregation, and any relation which defines a view upon which said query does an aggregation, and GL_R includes any groupby list and aggregated attribute pair in R and any projection of a groupby list and aggregated attribute of a relation which defines R.

7. A computer implemented method according to claim 1 wherein said inferring step comprises the steps of:

determining whether one or more of said new predicates is not useful to solve said query; and

eliminating said non-useful new predicate.

8. A computer implemented method according to claim 7 wherein said eliminating step involves eliminating axiomatic predicates.

9. A computer implemented method according to claim 7 wherein said eliminating step involves eliminating redundant predicates.

10. A computer implemented method according to claim 7 wherein said eliminating steps involves eliminating all predicates involving f_{R,X,A,Y}.

11. A computer implemented method according to claim 1 wherein said inferring step involves implementing a predicate pushdown optimization technique.

12. A computer implemented method according to claim 1 wherein said inferring step involves implementing a predicate move-around optimization technique.

13. A computer system for performing database queries involving aggregation given an initial set of predicates which includes one or more aggregation predicates, comprising:

means for translating at least one of said aggregation predicates into a representative form which is a functional term symbolized by f_{R,X,A,Y}, wherein R is a relation having one or more attributes, Xrepresents said attributes of R which are grouped and A is an aggregation function applied on attribute Y of R, said representative form suitable for illustrating a relationship involving said aggregation predicates;

means for inferring one or more new predicates, using said representative form from said initial set of predicates; and

means for solving said database query using said new predicates.

14. A computer system according to claim 13 wherein said means for inferring one or more new predicates comprises means for inferring predicates in a relation from other predicates of said relation.

15. A computer system according to claim 13 wherein said means for inferring one or more new predicates comprises means for inferring predicates in a first relation from predicates in one or more second relations defining said first relation.

16. A computer system according to claim 13 wherein said means for inferring one or more new predicates comprises means for inferring predicates in a first relation from predicates in a second relation defined by said first relation.

17. A computer system according to claim 13 wherein said means for inferring one or more new predicates further comprises:

means for identifying said aggregation predicates in said f_{R,XA,Y} form which are relevant to said query; and

means for inferring one or more new predicates from said relevant aggregation predicates in said f_{R,X,A,Y} form.

18. A computer system according to claim 17 wherein said relevant aggregation predicates in f_{R,X,A,Y} form, are those which involve R and a groupby list and aggregation attribute pair, GL_R, where R includes any relation upon which said query does an aggregation, and any relation which defines a view upon which said query does an aggregation, and GL_R includes any groupby list and aggregated attribute pair in R and any projection of a groupby list and aggregated attribute of a relation which defines R.

19. A computer system according to claim 13 wherein said means for inferring one or more new predicates comprises:

means for determining whether one or more of said new predicates is not useful to solve said query; and

means for eliminating said non-useful new predicate.

20. A computer system according to claim 19 wherein said eliminating means involves means for eliminating axiomatic predicates.

21. A computer system according to claim 19 wherein said eliminating means involves means for eliminating redundant predicates.

22. A computer system according to claim 19 wherein said eliminating meanss involves means for eliminating all predicates involving f_{R,X,A,Y}.

23. A computer system according to claim 13 wherein said means for inferring one or more new predicates involves means for implementing a predicate pushdown optimization technique.

24. A computer system according to claim 13 wherein said means for inferring one or more new predicates involves means for implementing a predicate move-around optimization technique.