Optimization of SQL queries using universal quantifiers, set intersection, and max/min aggregation in the presence of nullable columns

• US 5,590,324 A
• Filed: 02/07/1995
• Issued: 12/31/1996
• Est. Priority Date: 02/07/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Simmen, David E., Pirahesh, Mir H., Leung, Ting Y., Jou, Michelle M.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/384,925
• Time in Patent Office: 693 Days
• Field of Search: 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and apparatus for optimizing SQL queries by propagating and exploiting column nullability. Column nullability is identified and propagated using a three-valued logic, wherein a column of a table can be identified nullability information is exploited to optimize query operations through transformations. In one aspect of the present invention, quantified predicates (such as ">ALL") are transformed into simple predicates involving singleton subqueries so that indexing can be exploited. In another aspect of the present invention, "is not null" predicates are generated and pushed for certain aggregate queries. In still another aspect of the present invention, intersect operations are transformed into joins. The end result is that the present invention can significantly enhance the performance of the queries.

Claims

1. A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) propagating column nullability values in the memory of the computer through various SQL operations of the query, wherein the column nullability values are selected from a group comprising null, non-null, and nullable; and

(b) optimizing the SQL operations of the query in the memory of the computer based on the propagated column nullability values.

2. The method of claim 1 above, further comprising the step of translating the query into a query graph model.

3. The method of claim 1 above, further comprising the step of executing the SQL query against the relational database and outputting a result table to the user.

4. The method of claim 1 above, wherein the optimizing step comprises the steps of:

(1) examining the query in the memory of the computer to determine whether it contains a universal quantified predicate between an outer column and an inner column returned by a subquery;

(2) examining the query in the memory of the computer to determine nullability values for the outer and inner columns;

(3) creating a derived table in the memory of the computer representing one or more boundary values for the inner column and the nullability value for the inner column, wherein the boundary values are selected from a group comprising a maximum value and a minimum value returned from the subquery, and wherein the derived table contains only one tuple; and

(4) transforming the query in the memory of the computer using the derived table to replace the universal quantified predicate with a simple predicate containing the outer column and columns of the derived table.

5. The method of claim 4 above, further comprising the step of accessing the outer column using an index when there is an index on the outer column.

6. The method of claim 4 above, wherein the universal quantified predicate comprises a relational operator combined with an "ALL" keyword.

7. The method of claim 4 above, wherein the relational operator is selected from a group comprising =, >

, <

, <

=, and >

=.

8. The method of claim 4 above, wherein the transforming step further comprises the step of replacing the universal quantified predicate with a first simple predicate involving a singleton subquery when both the inner and outer columns are nullable.

9. The method of claim 4 above, wherein the transforming step further comprises the step of replacing the universal quantified predicate with a second simple predicate involving a singleton subquery when the inner column is nullable and the outer column is non-null.

10. The method of claim 4 above, wherein the simple predicate comprises one or more predicates comparing the outer column to the boundary values for the inner column and the nullability value for the inner column.

11. A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine whether it contains a universal quantified predicate between an outer column and an inner column returned by a subquery;

(b) examining the query in the memory of the computer to determine nullability values for the outer and inner columns, wherein the nullability values are selected from a group comprising null, non-null, and nullable;

(c) creating a derived table in the memory of the computer representing one or more boundary values for the inner column and the nullability value for the inner column, wherein the boundary values are selected from a group comprising a maximum value and a minimum value returned from the subquery, and wherein the derived table contains only one tuple; and

(d) transforming the query in the memory of the computer using the derived table to replace the universal quantified predicate with a simple predicate involving a singleton subquery containing the outer column and columns of the derived table.

12. The method of claim 11 above, further comprising the step of accessing the outer column using an index when there is an index on the outer column.

13. The method of claim 11 above, wherein the universal quantified predicate comprises a relational operator combined with an "ALL" keyword.

14. The method of claim 11 above, wherein the relational operator is selected from a group comprising =, >

, <

, <

=, and >

=.

15. The method of claim 11 above, wherein the transforming step further comprises the step of replacing the universal quantified predicate with a first simple predicate involving a singleton subquery when both the inner and outer columns are nullable.

16. The method of claim 11 above, wherein the transforming step further comprises the step of replacing the universal quantified predicate with a second simple predicate involving a singleton subquery when the inner column is nullable and the outer column is non-null.

17. The method of claim 11 above, wherein the simple predicate comprises one or more predicates comparing the outer column to the boundary values for the inner column and the nullability value for the inner column.

18. The method of claim 11 above, further comprising the step of propagating column nullability values through various SQL operations of the query.

19. A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine;

(1) whether the query contains a GROUP BY operation on a table without any GROUP BY columns, (2) whether the query contains only a MAX aggregation function in a SELECT clause of the query, (3) whether a column referenced in the MAX aggregation function has a descending index with a null value as a highest collating value, and (4) whether the column referenced in the MAX aggregation function is nullable; and

(b) transforming the query in the memory of the computer to include a new predicate for the column as a Boolean factor in a WHERE clause when the query contains the GROUP BY operation on the table without any GROUP BY columns, the query contains only the MAX aggregation function in the SELECT clause, the column referenced in the MAX aggregation function has a descending index with a null value as a highest collating value, and the column referenced in the MAX aggregation function is nullable, wherein the new predicate is of the form "COLUMN IS NOT NULL."

20. A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine;

(1) whether the query contains a GROUP BY operation on a table without any GROUP BY columns, (2) whether the query contains only a MIN aggregation function in a SELECT clause of the query, (3) whether a column referenced in the MIN aggregation function has an ascending index with a null value as a lowest collating value, and (4) whether the column referenced in the MIN aggregation function is nullable; and

(b) transforming the query in the memory of the computer to include a new predicate for the column as a Boolean factor in a WHERE clause when the query contains the GROUP BY operation on the table without any GROUP BY columns, the query contains only the MIN aggregation function in the SELECT clause, the column referenced in the MIN aggregation function has an ascending index with a null value as a lowest collating value, and the column referenced in the MIN aggregation function is nullable, wherein the new predicate is of the form "COLUMN IS NOT NULL."

21. A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine whether the query contains an INTERSECT operation and whether an output of the query is distinct;

(b) examining the query in the memory of the computer to determine whether each output column of the query has at least one of its corresponding input columns being non-null; and

(c) transforming the query in the memory of the computer by replacing the INTERSECT operation with a join query when the query contains an INTERSECT operation, the output of the query is distinct, and each output column of the query has at least one of its corresponding input columns being non-null.

22. The method of claim 21, wherein the examining step (a) further comprises the step of:

(1) examining the query in the memory of the computer to determine whether any operands of the INTERSECT operation has a key; and

(2) identifying an output of the query as distinct when one of the operands of the INTERSECT operation has a key.

28. The apparatus of claim 22 above, wherein the simple predicate comprises one or more predicates comparing the outer column to the boundary values for the inner column and the nullability value for the inner column.

23. An apparatus for optimizing an SQL query, comprising:

(a) a computer having a memory and an electronic storage device coupled thereto, the data storage device storing a relational database;

(b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer;

(c) means, performed by the computer, for propagating column nullability values in the memory of the computer through various SQL operations of the query, wherein the column nullability values are selected from a group comprising null, non-null, and nullable; and

(d) means, performed by the computer, for optimizing the SQL operations of the query in the memory of the computer based on the propagated column nullability values.

24. An apparatus for optimizing an SQL query, comprising:

(a) a computer having a memory and an electronic storage device coupled thereto, the data storage device storing a relational database;

(b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer;

(c) means, performed by the computer, for examining the query in the memory of the computer to determine whether it contains a universal quantified predicate between an outer column and an inner column returned by a subquery;

(d) means, performed by the computer, for examining the query in the memory of the computer to determine nullability values for the outer and inner columns, wherein the nullability values are selected from a group comprising null, non-null, and nullable;

(e) means, performed by the computer, for creating a derived table in the memory of the computer representing one or more boundary values for the inner column and the nullability value for the inner column, wherein the boundary values are selected from a group comprising a maximum value and a minimum value returned from the subquery, and wherein the derived table contains only one tuple; and

(f) means, performed by the computer, for transforming the query in the memory of the computer using the derived table to replace the universal quantified predicate with a simple predicate involving a singleton subquery containing the outer column and columns of the derived table.

25. The apparatus of claim 24 above, further comprising means for accessing the outer column using an index when there is an index on the outer column.

26. The apparatus of claim 24 above, wherein the means for transforming further comprises means for replacing the universal quantified predicate with a first simple predicate involving a singleton subquery when both the inner and outer columns are nullable.

27. The apparatus of claim 24 above, wherein the means for transforming further comprises means for replacing the universal quantified predicate with a second simple predicate involving a singleton subquery when the inner column is nullable and the outer column is non-null.

29. The apparatus of claim 24 above, further comprising means for propagating column nullability values through various SQL operations of the query.

30. An apparatus for optimizing an SQL query, comprising:

(a) a computer having a memory and an electronic storage device coupled thereto, the data storage device storing a relational database;

(b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer;

(c) means, performed by the computer, for examining the query in the memory of the computer to determine;

(1) whether the query contains a GROUP BY operation on a table without any GROUP BY columns, (2) whether the query contains only a MAX aggregation function in a SELECT clause of the query, (3) whether a column referenced in the MAX aggregation function has a descending index with a null value as a highest collating value, and (4) whether the column referenced in the MAX aggregation function is nullable; and

(d) means, performed by the computer, for transforming the query in the memory of the computer to include a new predicate for the column as a Boolean factor in a WHERE clause when the query contains the GROUP BY operation on the table without any GROUP BY columns, the query contains only the MAX aggregation function in the SELECT clause, the column referenced in the MAX aggregation function has a descending index with a null value as a highest collating value, and the column referenced in the MAX aggregation function is nullable, wherein the new predicate is of the form "COLUMN IS NOT NULL."

31. An apparatus for optimizing an SQL query, comprising:

(a) a computer having a memory and an electronic storage device coupled thereto, the data storage device storing a relational database;

(b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer;

(c) means, performed by the computer, for examining the query in the memory of the computer to determine;

(1) whether the query contains a GROUP BY operation on a table without any GROUP BY columns, (2) whether the query contains only a MIN aggregation function in a SELECT clause of the query, (3) whether a column referenced in the MIN aggregation function has an ascending index with a null value as a lowest collating value, and (4) whether the column referenced in the MIN aggregation function is nullable; and

(d) means, performed by the computer, for transforming the query in the memory of the computer to include a new predicate for the column as a Boolean factor in a WHERE clause when the query contains the GROUP BY operation on the table without any GROUP BY columns, the query contains only the MIN aggregation function in the SELECT clause, the column referenced in the MIN aggregation function has an ascending index with a null value as a lowest collating value, and the column referenced in the MIN aggregation function is nullable, wherein the new predicate is of the form "COLUMN IS NOT NULL."

32. An apparatus for optimizing an SQL query, comprising:

(a) a computer having a memory and an electronic storage device coupled thereto, the data storage device storing a relational database;

(b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer;

(c) means, performed by the computer, for examining the query in the memory of the computer to determine whether the query contains an INTERSECT operation and whether an output of the query is distinct;

(d) means, performed by the computer, for examining the query in the memory of the computer to determine whether each output column of the query has at least one of its corresponding input columns being non-null; and

(e) means, performed by the computer, for transforming the query in the memory of the computer by replacing the INTERSECT operation with a join query when the query contains an INTERSECT operation, the output of the query is distinct, and each output column of the query has at least one of its corresponding input columns being non-null.

33. The apparatus of claim 32, wherein the means for examining (c) further comprises:

(1) means for examining the query in the memory of the computer to determine whether any operands of the INTERSECT operation has a key; and

(2) means for identifying an output of the query as distinct when one of the operands of the INTERSECT operation has a key.

34. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) propagating column nullability values in the memory of the computer through various SQL operations of the query, wherein the column nullability values are selected from a group comprising null, non-null, and nullable; and

(b) optimizing the SQL operations of the query in the memory of the computer based on the propagated column nullability values.

35. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine whether it contains a universal quantified predicate between an outer column and an inner column returned by a subquery;

(b) examining the query in the memory of the computer to determine nullability values for the outer and inner columns, wherein the nullability values are selected from a group comprising null, non-null, and nullable;

(c) creating a derived table in the memory of the computer representing one or more boundary values for the inner column and the nullability value for the inner column, wherein the boundary values are selected from a group comprising a maximum value and a minimum value returned from the subquery, and wherein the derived table contains only one tuple; and

(d) transforming the query in the memory of the computer using the derived table to replace the universal quantified predicate with a simple predicate involving a singleton subquery containing the outer column and columns of the derived table.

36. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine;

(1) whether the query contains a GROUP BY operation on a table without any GROUP BY columns, (2) whether the query contains only a MAX aggregation function in a SELECT clause of the query, (3) whether a column referenced in the MAX aggregation function has a descending index with a null value as a highest collating value, and (4) whether the column referenced in the MAX aggregation function is nullable; and

(b) transforming the query in the memory of the computer to include a new predicate involving the column as a Boolean factor in a WHERE clause when the query contains the GROUP BY operation on the table without any GROUP BY columns, the query contains only the MAX aggregation function in the SELECT clause, the column referenced in the MAX aggregation function has a descending index with a null value as a highest collating value, and the column referenced in the MAX aggregation function is nullable, wherein the new predicate is of the form "COLUMN IS NOT NULL."

37. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine;

(1) whether the query contains a GROUP BY operation on a table without any GROUP BY columns, (2) whether the query contains only a MIN aggregation function in a SELECT clause of the query, (3) whether a column referenced in the MIN aggregation function has an ascending index with a null value as a lowest collating value, and (4) whether the column referenced in the MIN aggregation function is nullable; and

(b) transforming the query in the memory of the computer to include a new predicate for the column as a Boolean factor in a WHERE clause when the query contains the GROUP BY operation on the table without any GROUP BY columns, the query contains only the MIN aggregation function in the SELECT clause, the column referenced in the MIN aggregation function has an ascending index with a null value as a lowest collating value, and the column referenced in the MIN aggregation function is nullable, wherein the new predicate is of the form "COLUMN IS NOT NULL."

38. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine whether the query contains an INTERSECT operation and whether an output of the query is distinct;

(b) examining the query in the memory of the computer to determine whether each output column of the query has at least one of its corresponding input columns being non-null; and

(c) transforming the query in the memory of the computer by replacing the INTERSECT operation with a join query when the query contains an INTERSECT operation, the output of the query is distinct, and each output column of the query has at least one of its corresponding input columns being non-null.