Joined table expression optimization by query transformation

• US 6,385,603 B1
• Filed: 06/14/1999
• Issued: 05/07/2002
• Est. Priority Date: 06/14/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Fen-Ling, Chen, Yao-Ching Stephen, Tie, Hong, Wang, Yun, Mukai, Jerry
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/332,544
• Time in Patent Office: 1,058 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• 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

Abstract

A query optimizer analyzes a query and triggers a sequence of transformations to achieve optimal performance for joined table expressions. The transformations include pushing down predicates for joined table expressions and pushing down non-null predicates to simplify join operators for joined table expressions.

Claims

1. A method of optimizing a query in a relational database management system, comprising:

(a) analyzing the query to determine whether it contains at least one joined table expression; and

(b) transforming the joined table expressions by simplifying joins within the joined table expressions;

(c) wherein the transforming step comprises transforming a join when a non-null predicate from a WHERE clause references a null-supplying side of the joined table expression.

2. A method of optimizing a query in a relational database management system, comprising:

(a) analyzing the query to determine whether it contains at least one joined table expression; and

(b) transforming the joined table expressions by simplifying joins within the joined table expressions;

(c) wherein the transforming step comprises transforming a join when an ON clause from a parent joined table expression references a null supplying side of a child joined table expression.

3. A method of optimizing a query in a relational database management system, comprising:

(a) analyzing the query to determine whether it contains at least one joined table expression; and

(b) transforming the joined table expressions by pushing down predicates within the query.

4. The method of claim 3, wherein the transforming step comprises pushing down predicates from the joined table expression to a child joined table expression when a predicate from a WHERE clause references a preserved side of the child joined table expression.

5. The method of claim 3, wherein the transforming step comprises pushing down predicates from the joined table expression to a child joined table expression an ON clause references a null supplying side of the child joined table expression.

6. An apparatus for optimizing a query in a relational database management system, comprising:

(a) a computer system having a data storage device coupled thereto for storing a database;

(b) means, performed by the computer system, for analyzing the query to determine whether it contains at least one joined table expression; and

(c) means, performed by the computer system, for transforming the joined table expressions by simplifying at least one join within the joined table expressions;

(d) wherein the means for transforming comprises means for transforming a join when a non-null predicate from a WHERE clause references a null-supplying side of the joined table expression.

7. An apparatus for optimizing a query in a relational database management system, comprising:

(a) a computer system having a data storage device coupled thereto for storing a database;

(b) means, performed by the computer system, for analyzing the query to determine whether it contains at least one joined table expression; and

(c) means, performed by the computer system, for transforming the joined table expressions by simplifying at least one join within the joined table expressions;

(d) wherein the means for transforming comprises transforming a join when an ON clause from a parent joined table expression references a null supplying side of a child joined table expression.

8. An apparatus for optimizing a query in a relational database management system, comprising:

(a) a computer system having a data storage device coupled thereto for storing a database;

(b) means, performed by the computer system, for analyzing the query to determine whether it contains at least one joined table expression; and

(c) means, performed by the computer system, for transforming the joined table expressions by pushing down predicates within the query.

9. The apparatus of claim 8, wherein the means for transforming comprises means for pushing down predicates from the joined table expression to a child joined table expression when a predicate from a WHERE clause references a preserved side of the child joined table expression.

10. The apparatus of claim 8, wherein the means for transforming comprises means for pushing down predicates from the joined table expression to a child joined table expression an ON clause references a null supplying side of the child joined table expression.

11. An article of manufacture embodying logic for performing a method of optimizing a query in a relational database management system, the method comprising:

(a) analyzing the query to determine whether it contains at least one joined table expression; and

(b) transforming the joined table expressions by simplifying joins within the joined table expressions;

(c) wherein the transforming step comprises transforming a join when a non-null predicate from a WHERE clause references a null-supplying side of the joined table expression.

12. An article of manufacture embodying logic for performing a method of optimizing a query in a relational database management system, the method comprising:

(a) analyzing the query to determine whether it contains at least one joined table expression; and

(b) transforming the joined table expressions by simplifying joins within the joined table expressions;

(c) wherein the transforming step comprises transforming a join when an ON clause from a parent joined table expression references a null supplying side of a child joined table expression.

13. An article of manufacture embodying logic for performing a method of optimizing a query in a relational database management system, the method comprising:

(a) analyzing the query to determine whether it contains at least one joined table expression; and

(b) transforming the joined table expressions by pushing down predicates within the query.

14. The method of claim 13, wherein the transforming step comprises pushing down predicates from the joined table expression to a child joined table expression when a predicate from a WHERE clause references a preserved side of the child joined table expression.

15. The method of claim 13, wherein the transforming step comprises pushing down predicates from the joined table expression to a child joined table expression an ON clause references a null supplying side of the child joined table expression.