Enumerating projections in SQL queries containing outer and full outer joins in the presence of inner joins

• US 5,687,362 A
• Filed: 01/30/1995
• Issued: 11/11/1997
• Est. Priority Date: 01/30/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bhargava, Gautam, Goel, Piyush, Iyer, Balakrishna Ragmavendra
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/379,891
• Time in Patent Office: 1,016 Days
• Field of Search: 395/601, 395/602, 395/603, 395/604, 395/605
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

The present invention discloses a method and apparatus for the enumeration of projections (i.e., "SELECT DISTINCT" operations) in SQL queries containing outer and full outer joins in the presence of inner joins without encountering any regression in performance. The present invention removes projections from a given user query by moving the projections to the top of an expression tree representation of the query, wherein the projection removal is performed using algebraic identities rather than rule-based transformations. The present invention also discloses several methods of enumerating different plans or schedules for projection operations and binary operations in the given user query. The present invention can significantly reduce the execution time of a query by selecting the optimal schedule for binary operations and projections between the binary operations. However, the present invention ensures that there is no regression in performance by comparing the cost of the query with the cost of enumerated plans or schedules, thereby ensuring that the optimizations or transformations do not introduce performance penalties.

Claims

1. A method of optimizing an SQL query in a computer having a memory, the SQL query being used by the computer to direct information retrieval from a relational database stored in an electronic storage device, the method comprising the steps of:

(a) generating an expression tree for the query in the memory of the computer, wherein the query comprises at least one outer join;

(b) removing projection operations from the expression tree in the memory of the computer by moving the projection operations to a top node of the expression tree;

(c) generating projection sets and required sets for the expression tree in the memory of the computer; and

(d) enumerating plans for the expression tree in the memory of the computer, wherein the enumerated plans contain reorderings of the projection operations and binary operations in accordance with the projection sets and required sets.

2. The method of claim 1 above, further comprising the step of selecting an enumerated plan from the memory of the computer for execution by the computer to direct the information retrieval from the relational database stored in the electronic storage device.

3. The method of claim 1 above, wherein the enumerated plans have a projection operation at the top node of the expression tree.

4. A method of optimizing an SQL query in a computer having a memory, the SQL query being used by the computer to direct information retrieval from a relational database stored in an electronic storage device, the method comprising the steps of:

(a) generating an expression tree for the query in the memory of the computer, wherein the query comprises at least one outer join; and

(b) removing projection operations from the expression tree by moving the projection operations to the top of the expression tree in the memory of the computer, further comprising the steps of determining whether a first operand of a binary operation in the expression tree has a projection operation specified therein, determining whether a second operand of the binary operation in the expression tree does not have a projection operation specified therein, and retaining virtual attributes from the second operand for use in subsequent operations in the expression tree when the second operand does not have a projection operation specified therein.

5. The method of claim 4 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

6. The method of claim 4 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.2 δ

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.2 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.X ⊙

e.sub.y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ R_X, and X₂ X₁,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y) is a set of tuples, Y₁ R_Y, and Y₂ Y₁,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

7. The method of claim 4 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1.sub.Y.sbsb.1 δ

.sub.V.sbsb.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

8. The method of claim 4 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ R_X, and X₂ X₁,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

9. The method of claim 4 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sub.1 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.X ⊙

e.sub.Y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ R_X, and X₂ X₁,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

10. A method of optimizing an SQL query in a computer having a memory, the SQL query being used by the computer to direct information retrieval from a relational database stored in an electronic storage device, the method comprising the steps of:

(a) accepting an SQL query from an operator into the memory of the computer;

(b) translating the SQL query into a expression tree in the memory of the computer, wherein the expression tree is comprised of interior nodes representing operations and leaves representing base relations, and wherein the expression tree is comprised of one or more expression subtrees;

(c) generating an exhaustive enumeration of all possible plans for the expression tree in the memory of the computer, wherein the enumerated plans comprise reorderings of binary and projection operations performed by the query, the generating step further comprising the step of constructing the plans incrementally from the bottom up using the expression tree by combining, at each step, two subtrees of the expression tree to obtain a new subtree of the expression tree provided all conditions specified in the two subtrees are satisfied, and by scheduling a distinct projection operation at a root node of the new subtree.

11. A method of optimizing an SQL query in a computer having a memory, the SQL query being used by the computer to direct information retrieval from a relational database stored in an electronic storage device, the method comprising the steps of:

(a) accepting an SQL query from an operator into the memory of the computer;

(b) translating the SQL query into an expression tree in the memory of the computer, wherein the expression tree is comprised of interior nodes representing operations and leaves representing base relations, and wherein the expression tree is comprised of one or more expression subtrees; and

(c) using a heuristic to enumerate a plurality of plans for the expression tree in the memory of the computer, wherein the enumerated plans comprise all possible schedules for join operations and a limited number of schedules for distinct projection operations, wherein the using step further comprises the steps of;

(1) pushing projection operations down the expression tree in the memory of the computer;

(2) constructing a projection set in the memory of the computer from the expression tree, wherein the projection set is comprised of distinct projection operations specified in the expression tree;

(3) constructing a required set in the memory of the computer for each subtree of the expression tree containing a distinct projection operation at a top of the subtree, wherein the required set is comprised of all relations that must be present in the subtree before the distinct projection operation can be scheduled at a root node of the subtree; and

(4) enumerating plans for the expression tree in the memory of the computer, wherein the enumerated plans contain reorderings of the projection operations and binary operations in accordance with the projection sets and required sets.

12. The method of claim 11 above, wherein the pushing step further comprises the step of recursively applying an identity to the expression tree in the memory of the computer to push projection operations down in the expression tree, wherein the identity comprises:

##EQU15## and wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X) is a set of tuples, and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

space="preserve" listing-type="equation">p.sub.xy is a predicate,

space="preserve" listing-type="equation">sch(p.sub.xy) is a schema of p.sub.xy,

space="preserve" listing-type="equation">(sch(p.sub.xy)∪

R.sub.X)X.sub.1,

space="preserve" listing-type="equation">(sch(p.sub.xy)∪

R.sub.Y)Y.sub.1,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

13. The method of claim 11 above, wherein the enumerating step further comprises the steps of:

(i) removing projection operations from the expression tree by moving the projection operations to the top of the expression tree in the memory of the computer;

(ii) constructing the plans in the memory of the computer incrementally from the bottom up using the subtrees of the expression tree, by combining two subtrees of the expression tree to obtain a new subtree provided that all the conditions specified in the two subtrees are satisfied; and

(iii) scheduling a distinct projection operation at the root of the new subtree in the memory of the computer when elements of the projection set for the new subtree contain attributes such that corresponding required sets are subsets of the new subtree.

14. 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 generating an expression tree for the query in the memory of the computer, wherein the query comprises at least one outer join;

(d) means, performed by the computer, for removing projection operations from the expression tree in the memory of the computer by moving the projection operations to a top node of the expression tree;

(e) means, performed by the computer, for generating projection sets and required sets for the expression tree in the memory of the computer; and

(f) means, performed by the computer, for enumerating plans for the expression tree in the memory of the computer, wherein the enumerated plans contain reorderings of the projection operations and binary operations in accordance with the projection sets and required sets.

15. The apparatus of claim 14 above, further comprising means for selecting an enumerated plan from the memory of the computer for execution by the computer to direct the information retrieval from the relational database stored in the electronic storage device.

16. The apparatus of claim 14 above, wherein the enumerated plans have a projection operation at the top node of the expression tree.

17. 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 generating an expression tree for the query in the memory of the computer, wherein the query is comprised of at least one outer join; and

(d) means, performed by the computer, for removing projection operations from the expression tree by moving the projection operations to the top of the expression tree in the memory of the computer, further comprising means for determining whether a first operand of a binary operation in the expression tree has a projection operation specified therein, means for determining whether a second operand of the binary operation in the expression tree does not have a projection operation specified therein, and means for retaining virtual attributes from the second operand for use in subsequent operations in the expression tree when the second operand does not have a projection operation specified therein.

18. The apparatus of claim 17 above, wherein the means for removing further comprises:

(1) means, performed by the computer, for identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.i (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) means, performed by the computer, for replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

19. The apparatus of claim 17 above, wherein the means for removing further comprises:

(1) means, performed by the computer, for identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.2 δ

.sub.Y.sub.1 (e.sub.y)

(2) means, performed by the computer, for replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.2 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ R_X, and X₂ X₁,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, Y₁ R_Y, and Y₂ Y₁,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

20. The apparatus of claim 17 above, wherein the means for removing further comprises:

(1) means, performed by the computer, for identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) means, performed by the computer, for replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1.sub.Y.sbsb.1 δ

.sub.V.sub.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

21. The apparatus of claim 17 above, wherein the means for removing further comprises:

(1) means, performed by the computer, for identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.1 (e.sub.y)

(2) means, performed by the computer, for replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sub.1 δ

.sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X) is a set of tuples X₁ R_X, and X₂ X₁,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, Y_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y, p1 π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

22. The apparatus of claim 17 above, wherein the means for removing further comprises:

(1) means, performed by the computer, for identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) means, performed by the computer, for replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.X.sub.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ R_X, and X₂ X₁,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

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 translating the SQL query into a expression tree in the memory of the computer, wherein the expression tree is comprised of interior nodes representing operations and leaves representing base relations, and wherein the expression tree is comprised of one or more expression subtrees;

(d) means, performed by the computer, for generating an exhaustive enumeration of all possible plans for the expression tree in the memory of the computer, wherein the enumerated plans comprise reorderings of binary and projection operations performed by the query, the means for generating further comprising means for constructing the plans incrementally from the bottom up using the expression tree by combining, at each step, two subtrees of the expression tree to obtain a new subtree of the expression tree provided all conditions specified in the two subtrees are satisfied, and means for scheduling a distinct projection operation at a root node of the new subtree.

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 translating the SQL query into an expression tree in the memory of the computer, wherein the expression tree is comprised of interior nodes representing operations and leaves representing base relations, and wherein the expression tree is comprised of one or more expression subtrees; and

(d) means, performed by the computer, for using a heuristic to enumerate a plurality of plans for the expression tree in the memory of the computer, wherein the enumerated plans comprise all possible schedules for join operations and a limited number of schedules for distinct protection operations, wherein the means for using comprises;

(1) means, performed by the computer, for pushing projection operations down the expression tree in the memory of the computer;

(2) means, performed by the computer, for constructing a projection set in the memory of the computer from the expression tree, wherein the projection set is comprised of distinct projection operations specified in the expression tree;

(3) means, performed by the computer, for constructing a required set in the memory of the computer for each subtree of the expression tree containing a distinct projection operation at a top of the subtree, wherein the required set is comprised of all relations that must be present in the subtree before the distinct projection operation can be scheduled at a root node of the subtree; and

(4) means, performed by the computer, for enumerating plans for the expression tree in the memory of the computer, wherein the enumerated plans contain reorderings of the projection operations and binary operations in accordance with the projection sets and required sets.

25. The apparatus of claim 24 above, wherein the means for pushing further comprises means for recursively applying an identity to the expression tree in the memory of the computer to push projection operations down in the expression tree, wherein the identity comprises:

##EQU16## and wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y) is a set of tuples, and Y₁ R_Y,

space="preserve" listing-type="equation">p.sub.xy is a predicate,

space="preserve" listing-type="equation">sch(p.sub.xy) is a schema of p.sub.xy,

space="preserve" listing-type="equation">(sch(p.sub.xy)∩

R.sub.X)X.sub.1,

space="preserve" listing-type="equation">(sch(p.sub.xy)∩

R.sub.Y)Y.sub.1,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

26. The apparatus of claim 24 above, wherein the means for enumerating further comprises:

(i) means, performed by the computer, for removing projection operations from the expression tree by moving the projection operations to the top of the expression tree in the memory of the computer;

(ii) means, performed by the computer, for constructing the plans in the memory of the computer incrementally from the bottom up using the subtrees of the expression tree, by combining two subtrees of the expression tree to obtain a new subtree provided that all the conditions specified in the two subtrees are satisfied; and

(iii) means, performed by the computer, for scheduling a distinct projection operation at the root of the new subtree in the memory of the computer when elements of the projection set for the new subtree contain attributes such that corresponding required sets are subsets of the new subtree.

27. 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) generating an expression tree for the query in the memory of the computer;

(b) removing projection operations from the expression tree in the memory of the computer by moving the projection operations to a top node of the expression tree;

(c) generating projection sets and required sets for the expression tree in the memory of the computer; and

(d) enumerating plans for the expression tree in the memory of the computer, wherein the enumerated plans contain reorderings of the projection operations and binary operations in accordance with the projection sets and required sets.

28. The method of claim 27 above, further comprising the step of selecting an enumerated plan from the memory of the computer for execution by the computer to direct the information retrieval from the relational database stored in the electronic storage device.

29. The method of claim 27 above, wherein the enumerated plans have a projection operation at the top node of the expression tree.

30. 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) generating an expression tree for the query in the memory of the computer, wherein the query comprises at least one outer join; and

(b) removing projection operations from the expression tree by moving the projection operations to the top of the expression tree in the memory of the computer, further comprising the steps of determining whether a first operand of a binary operation in the expression tree has a projection operation specified therein, determining whether a second operand of the binary operation in the expression tree does not have a projection operation specified therein, and retaining virtual attributes from the second operand for use in subsequent operations in the expression tree when the second operand does not have a projection operation specified therein.

31. The program storage device of claim 30 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

32. The program storage device of claim 30 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.2 δ

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.2 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ R_X, and X₂ X₂,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, Y₁ R_Y, and Y₂ Y₁,

π

_X (I) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

33. The program storage device of claim 30 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1.sub.Y.sbsb.1 δ

.sub.V.sbsb.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

34. The program storage device of claim 30 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ R_X, and X₂ X₁,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y) is a set of tuples, and Y₁ R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

35. The program storage device of claim 30 above, wherein the removing step further comprises the steps of:

(1) identifying a first expression in the expression tree, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

(2) replacing the first expression in the expression tree with a second expression, wherein the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.X ⊙

e.sub.Y)

wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ R_X, and X₂ X₁,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y) is a set of tuples, and Y₁ R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

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) accepting an SQL query from an operator into the memory of the computer;

(b) translating the SQL query into a expression tree in the memory of the computer, wherein the expression tree is comprised of interior nodes representing operations and leaves representing base relations, and wherein the expression tree is comprised of one or more expression subtrees;

(c) generating an exhaustive enumeration of all possible plans for the expression tree in the memory of the computer, wherein the enumerated plans comprise reorderings of binary and projection operations performed by the query, the generating step further comprising the step of constructing the plans incrementally from the bottom up using the expression tree by combining, at each step, two subtrees of the expression tree to obtain a new subtree of the expression tree provided all conditions specified in the two subtrees are satisfied, and by scheduling a distinct projection operation at a root node of the new subtree.

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) accepting an SQL query from an operator into the memory of the computer;

(b) translating the SQL query into an expression tree in the memory of the computer, wherein the expression tree is comprised of interior nodes representing operations and leaves representing base relations, and wherein the expression tree is comprised of one or more expression subtrees; and

(c) using a heuristic to enumerate a plurality of plans for the expression tree in the memory of the computer, wherein the enumerated plans comprise all possible schedules for join operations and a limited number of schedules for distinct protection operations, wherein the using step comprises the steps of;

(1) pushing projection operations down the expression tree in the memory of the computer;

(2) constructing a projection set in the memory of the computer from the expression tree, wherein the projection set is comprised of distinct projection operations specified in the expression tree;

(3) constructing a required set in the memory of the computer for each subtree of the expression tree containing a distinct projection operation at a top of the subtree, wherein the required set is comprised of all relations that must be present in the subtree before the distinct projection operation can be scheduled at a root node of the subtree; and

(4) enumerating plans for the expression tree in the memory of the computer, wherein the enumerated plans contain reorderings of the projection operations and binary operations in accordance with the projection sets and required sets.

38. The program storage device of claim 37 above, wherein the pushing step further comprises the step of recursively applying an identity to the expression tree in the memory of the computer to push projection operations down in the expression tree, wherein the identity comprises:

##EQU17## and wherein;

e_X =<

R_X,V_X,E_X >

is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ R_X,

e_Y =<

R_Y,V_Y,E_Y >

is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ R_Y,

space="preserve" listing-type="equation">p.sub.xy is a predicate,

space="preserve" listing-type="equation">sch(p.sub.xy) is a schema of p.sub.xy,

space="preserve" listing-type="equation">(sch(p.sub.xy)∩

R.sub.X)X.sub.1,

space="preserve" listing-type="equation">(sch(p.sub.xy)∩

R.sub.Y)Y.sub.1,

δ

_X (r) is a distinct projection operation of relation r onto attributes X,

⊙

ε

{,←

,→

,⃡

}, wherein represents a join operation, ⃡

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

39. The program storage device of claim 37 above, wherein the enumerating step further comprises the steps of:

(i) removing projection operations from the expression tree by moving the projection operations to the top of the expression tree in the memory of the computer;

(ii) constructing the plans in the memory of the computer incrementally from the bottom up using the subtrees of the expression tree, by combining two subtrees of the expression tree to obtain a new subtree provided that all the conditions specified in the two subtrees are satisfied; and

(iii) scheduling a distinct projection operation at the root of the new subtree in the memory of the computer when elements of the projection set for the new subtree contain attributes such that corresponding required sets are subsets of the new subtree.