Method and apparatus for reordering complex SQL queries containing inner and outer join operations

• US 5,832,477 A
• Filed: 05/14/1997
• Issued: 11/03/1998
• Est. Priority Date: 10/20/1994
• Status: Expired due to Term

• 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/856,198
• Time in Patent Office: 538 Days
• Field of Search: 707/1, 707/2, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method and apparatus for reordering complex SQL queries containing joins, outer and full outer joins. The method and apparatus first translates the query into a hypergraph representation. Required sets, conflict sets and preserved sets are then generated for the query hypergraph. Using the required sets, a plurality of plans are enumerated, wherein the plans represent associative re-orderings of relations in the query. SQL operators are selectively assigned to each of the enumerated plans using the conflict sets and/or preserved sets, so that the results from the plans are identical to the original query. A novel Modified General Outer Join (MGOJ) operator may be assigned to the root of a sub-tree, wherein the MGOJ operator is a compensation operator. The operator assignment is performed recursively for the root of each sub-tree in the plan. One of the enumerated plans (generally the most optimal) is then selected for execution.

Claims

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

(a) accepting the query into the memory of the computer;

(b) enumerating one or more plans for the query in the memory of the computer, wherein the enumerated plans represent associative re-orderings of relations in the query; and

(c) selectively assigning a Modified General Outer Join (MGOJ) operator at a root of one or more of the enumerated plans.

2. The method of claim 1, further comprising the step of:

(d) selecting one of the enumerated plans for execution by the computer according to a predefined criteria for the retrieval of the information from the relational database stored in the electronic storage device.

3. The method of claim 1, wherein the MGOJ operator is a compensation operator.

4. The method of claim 1, wherein the MGOJ operator comprises a relation <

R₁ R₂,V₁ V2,E'"'"'>

in an expression comprising;

space="preserve" listing-type="equation">r.sub.1 MGOJ p,X.sub.1, . . . ,X.sub.n,Y.sub.1, . . . ,Y.sub.n'"'"' !r.sub.2

for relations r₁ and r₂ that preserves relations X_i and Y_j, wherein;

r₁ =<

R₁,V₁,E₁ >

, wherein R₁ is a non-empty set of real attributes, V₁ is a non-empty set of virtual attributes, and E₁ is a set of tuples that comprise the relation r₁,

r₂ =<

R₂,V₂,E₂ >

, wherein R₂ is a non-empty set of real attributes, V₂ is a non-empty set of virtual attributes, and E₂ is a set of tuples that comprise the relation r₂,

R₁ ∩

R₂ =φ

,

V₁ ∩

V₂ =φ

,

X_i =<

R_x.sbsb.i,V_x.sbsb.i,E_x.sbsb.i >

for 1≦

i≦

n,

Y_j =<

R_y.sbsb.j,V_y.sbsb.j,E_y.sbsb.j >

for 1≦

j≦

n'"'"', X_i and Y_j are relations such that

R_x.sbsb.i ∩

R_x.sbsb.k =V_x.sbsb.i ∩

V_x.sbsb.k =φ

, R_y.sbsb.j ∩

R_y.sbsb.s =V_y.sbsb.j ∩

V_y.sbsb.s =φ

, R_x.sbsb.i .OR right.R₁ and R_y.sbsb.j .OR right.R₂, where i≠

k, j≠

s, 1≦

i, k≦

n, and 1≦

j,s≦

n'"'"', ##EQU57## p_i,j is a predicate for ##EQU58## ·

ε

{, →

, ←

, ←

→

} defines operators for the query, denotes a join operation, →

denotes a left outer join operation, ←

denotes a right outer join operation, ←

→

denotes a full outer join operation, and

π

^c denotes a projection operation.

5. The method of claim 4, wherein the assigning step comprises replacing:

##EQU59## with;

##EQU60##

6. The method of claim 4, wherein the assigning step comprises replacing:

##EQU61## with;

##EQU62##

7. The method of claim 4, wherein the assigning step comprises replacing:

##EQU63##

8. The method of claim 4, wherein the assigning step comprises replacing:

##EQU64##

9. An apparatus for reordering a query, comprising:

(a) a computer having a memory, the query being used by the computer to direct information retrieval from a relational database stored in an electronic storage device coupled to the computer, the computer further comprising;

(1) means for accepting the query into the memory of the computer;

(2) means for enumerating one or more plans for the query in the memory of the computer, wherein the enumerated plans represent associative re-orderings of relations in the query; and

(3) means for selectively assigning a Modified General Outer Join (MGOJ) operator at a root of one or more of the enumerated plans.

10. The apparatus of claim 9, wherein the computer further comprises:

(4) means for selecting one of the enumerated plans for execution by the computer according to a predefined criteria for the retrieval of the information from the relational database stored in the electronic storage device.

11. The apparatus of claim 9, wherein the MGOJ operator is a compensation operator.

12. The apparatus of claim 9, wherein the MGOJ operator comprises a relation <

R_i R₂,V₁ V2,E'"'"'>

in an expression comprising;

space="preserve" listing-type="equation">r.sub.1 MGOJ p,X.sub.1, . . . ,X.sub.n,Y.sub.1, . . . ,Y.sub.n'"'"' !r.sub.2

for relations r₁ and r₂ that preserves relations X_i and Y_j, wherein;

r₁ =<

R₁,V₁,E₁ >

, wherein R₁ is a non-empty set of real attributes, V₁ is a non-empty set of virtual attributes, and E₁ is a set of tuples that comprise the relation r₁,

r₂ =<

R₂,V₂,E₂ >

, wherein R₂ is a non-empty set of real attributes, V₂ is a non-empty set of virtual attributes, and E₂ is a set of tuples that comprise the relation r₂,

R₁ ∩

R₂ =φ

,

V₁ ∩

V₂ =φ

,

X_i =<

R_x.sbsb.i,V_x.sbsb.1,E_x.sbsb.i >

for 1≦

i≦

n,

Y_j =<

R_y.sbsb.j,V_y.sbsb.j,E_y.sbsb.j >

for 1≦

j≦

n'"'"',

X_i and Y_j are relations such that

R_x.sbsb.i ∩

R_x.sbsb.k =V_x.sbsb.i ∩

V_x.sbsb.k =φ

, R_y.sbsb.j ∩

R_y.sbsb.s =V_y.sbsb.j ∩

V_y.sbsb.s =φ

, R_x.sbsb.i .OR right.R₁ and R_y.sbsb.j .OR right.R₂, where i≠

k, j≠

s, 1≦

i,k≦

n, and 1≦

j,s≦

n'"'"', ##EQU65## p_i,j is a predicate for ##EQU66## ·

ε

{, →

, ←

, ←

→

} defines operators for the query, denotes a join operation, →

denotes a left outer join operation, ←

denotes a right outer join operation, ←

→

denotes a full outer join operation, and

π

^c denotes a projection operation.

13. The apparatus of claim 12, wherein the means for assigning comprises means for replacing:

##EQU67##

14. The apparatus of claim 12, wherein the means for assigning comprises means for replacing:

##EQU68##

15. The apparatus of claim 12, wherein the means for assigning comprises means for replacing:

##EQU69##

16. The apparatus of claim 12, wherein the means for assigning comprises means for replacing:

##EQU70##

17. A program storage device, readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps reordering a query in a computer having a memory, the query being used by the computer to direct information retrieval from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the memory of the computer;

(b) enumerating one or more plans for the query in the memory of the computer, wherein the enumerated plans represent associative re-orderings of relations in the query; and

(c) selectively assigning a Modified General Outer Join (MGOJ) operator at a root of one or more of the enumerated plans.

18. The method of claim 17, further comprising the step of:

(d) selecting one of the enumerated plans for execution by the computer according to a predefined criteria for the retrieval of the information from the relational database stored in the electronic storage device.

19. The method of claim 17, wherein the MGOJ operator is a compensation operator.

20. The method of claim 17, wherein the MGOJ operator comprises a relation <

R₁ R₂,V₁ V₂,E'"'"'>

in an expression comprising;

space="preserve" listing-type="equation">r.sub.1 MGOJ p,X.sub.1, . . . ,X.sub.n,Y.sub.1, . . . ,Y.sub.n'"'"' !r.sub.2

for relations r₁ and r₂ that preserves relations X_i and Y_j, wherein;

r₁ =<

R₁,V₁,E₁ >

, wherein R₁ is a non-empty set of real attributes, V₁ is a non-empty set of virtual attributes, and E₁ is a set of tuples that comprise the relation r₁,

r₂ =<

R₂,V₂,E₂ >

, wherein R₂ is a non-empty set of real attributes, V.sub. is a non-empty set of virtual attributes, and E₂ is a set of tuples that comprise the relation r₂,

R₁ ∩

R₂ =φ

,

V₁ ∩

V₂ =φ

,

X_i =<

R_x.sbsb.i,V_x.sbsb.i,E_x.sbsb.i >

for 1≦

i≦

n,

Y_j =<

R_y.sbsb.j,V_y.sbsb.j,E_y.sbsb.j >

for 1≦

j≦

n'"'"',

X_i and Y_j are relations such that

R_x.sbsb.i ∩

R_x.sbsb.k =V_x.sbsb.i ∩

V_x.sbsb.k =φ

, R_y.sbsb.j ∩

R_y.sbsb.s =V_y.sbsb.j ∩

V_y.sbsb.s =φ

, R_x.sbsb.i .OR right.R₁ and R_y.sbsb.j .OR right.R₂, where i≠

k, j≠

s, 1≦

i,k≦

n, and 1≦

j,s≦

n'"'"', ##EQU71## p_i,j is a predicate for ##EQU72## ·

ε

{, →

, ←

, ←

→

} defines operators for the query, denotes a join operation, →

denotes a left outer join operation, ←

denotes a right outer join operation, ←

→

denotes a full outer join operation, and

π

^c denotes a projection operation.

21. The method of claim 20, wherein the assigning step comprises replacing:

##EQU73##

22. The method of claim 20, wherein the assigning step comprises replacing:

##EQU74##

23. The method of claim 20, wherein the assigning step comprises replacing:

##EQU75##

24. The method of claim 20, wherein the assigning step comprises replacing:

##EQU76##