Method and apparatus for reordering complex SQL queries using a modified generalized outer join operator

• US 5,701,455 A
• Filed: 06/05/1995
• Issued: 12/23/1997
• Est. Priority Date: 10/20/1994
• 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/464,263
• Time in Patent Office: 932 Days
• Field of Search: 395/601, 395/602, 395/603, 395/604
• 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 reorderings 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 an SQL query in a computer having a memory, comprising the steps of:

(a) accepting a query into the memory of the computer, wherein a first expression of the query comprises;

##EQU51## (b) replacing the first expression with a second expression comprising;

##EQU52## wherein the MGOJ operator comprises a relation (R₁,2 R₃,V₁,2 V₃,E'"'"') and the second expression preserves relation X₁, wherein;

##EQU53## wherein R₁,2 is a non-empty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a set of tuples in the relation R₁,2,

r₃ =X₃ =(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 in the relation r₃, ##EQU54## P_i,j is a predicate for ##EQU55## and π

^c denotes a projection operation.

2. A method of reordering an SQL query in a computer having a memory, comprising the steps of:

(a) accepting a query into the memory of the computer, wherein a first expression of the query comprises;

##EQU56## (b) replacing the first expression with a second expression comprising;

##EQU57## wherein the MGOJ operator comprises a relation (R₁,2 R₃,V₁,2 V₃,E'"'"') and the second expression preserves relation X₁, wherein;

##EQU58## wherein R₁,2 is a nonempty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a set of tuples for the relation r₁,2,

r₃ =X₃ =(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 for the relation r₃, ##EQU59## p_i,j is a predicate for ##EQU60## and π

^c denotes a projection operation.

3. A method of reordering an SQL query in a computer having a memory, comprising the steps of:

(a) accepting a query into the memory of the computer, wherein a first expression of the query comprises;

##EQU61## (b) replacing the first expression with a second expression comprising;

##EQU62## wherein the MGOJ operator comprises a relation (R₁ R₂, V₁ V₂,E'"'"') and the second expression preserves relations X₁ and X₃, wherein;

##EQU63## wherein R₁,2 is a nonempty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a set of tuples for the relation r₁,2,

r₃ =X₃ =(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 for the relation r₃,

R₁,2 ∩

R₃ =.o slashed.,

V₁,2 ∩

V₃ =.o slashed.,

X₁ =(R₁,V₁,E₁)

X₁ and X₃ are relations such that ##EQU64## P_i,j is a predicate for ##EQU65## and π

^c denotes a projection operation.

4. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query in the method comprising the steps of:

(a) accepting a query into the computer, wherein a first expression of the query comprises;

##EQU66## (b) replacing the first expression with a second expression comprising;

##EQU67## wherein the MGOJ operator comprises a relation (R₁,2 R₃,V₁,2 V₃,E'"'"') and the second expression preserves relation X₁, wherein;

r₁,2 =(X₁→

^P1,2 X₂)=(R₁,2,V₁,2,E₁,2), wherein R₁,2 is a non-empty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a set of tuples in the relation r₁,2,

r₃ =X₃ =(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 in the relation r₃, ##EQU68## P_i,j is a predicate for ##EQU69## and π

^c denotes a projection operation.

5. A program storage device readable by a computer having a memory, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query, the method comprising the steps of:

(a) accepting a query into the memory of the computer, wherein a first expression of the query comprises;

##EQU70## (b) replacing the first expression with a second expression comprising;

##EQU71## wherein the MGOJ operator comprises a relation and the second expression preserves relation

wherein;

r₁,2 =(X₁⃡

^P.sbsp.1,2 X₂)=(R₁,2,V₁,2,E₁,2), wherein R₁,2 is a non-empty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a set of tuples for the relation r₁,2,

r₃ =X₃ =(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 for the relation r₃, ##EQU72## P_i,j is a predicate for ##EQU73## and π

^c denotes a projection operation.

6. A program storage device readable by a computer having a memory, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query, the method comprising the steps of:

(a) accepting a query into the memory of the computer, wherein a first expression of the query comprises;

##EQU74## (b) replacing the first expression with a second expression comprising;

##EQU75## wherein the MGOJ operator comprises a relation (R₁ R₂,V₁ V₁,E'"'"') and the second expression preserves relations X₁ and X₃, wherein;

##EQU76## wherein R₁,2 is a non-empty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a relation r₁,2,

r₃ =X₃ =(R₃,V₃,E₃), wherein real attributes, V₃ is a non-attributes, and E₃ is a set

R₁,2 ∩

R₃ =.o slashed.,

V₁,2 ∩

V₃ =.o slashed.,

X₁ =(R₁,V₁,E₁),

X₁ and X₃ are relations such that ##EQU77## P_i,j is a predicate for ##EQU78## and π

^c denotes a projection operation.

7. An apparatus for reordering an SQL query, comprising:

a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising;

means for accepting a query into the memory of the computer, wherein a first expression of the query comprises;

##EQU79## means for replacing the first expression with a second expression comprising;

##EQU80## wherein the MGOJ operator comprises a relation (R₁,2 R₃,V₁,2 V₃,E'"'"') and the second expression preserves relation X₁, wherein;

##EQU81## wherein R₁,2 is a non-empty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a set of tuples in the relation r₁,2,

r₃ =X₃ =(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 in the relation r₃, ##EQU82## P_i,j is a predicate for ##EQU83## and π

^c denotes a projection operation.

8. An apparatus for reordering an SQL query, comprising:

a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising;

means for accepting a query into the memory of the computer, wherein a first expression of the query comprises;

##EQU84## means for replacing the first expression with a second expression comprising;

##EQU85## wherein the MGOJ operator comprises a relation (R₁,2 R₃,V₁,2 V₃,E'"'"') and the second expression preserves relation X₁, wherein;

##EQU86## wherein R₁,2 is a nonempty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a set of tuples for the relation r₁,2,

r₃ =X₃ =(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 for the relation r₃, ##EQU87## p_i,j is a predicate for ##EQU88## and π

^c denotes a projection operation.

9. An apparatus for reordering an SQL query, comprising:

a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising;

means for accepting a query into the memory of the computer, wherein a first expression of the query comprises;

##EQU89## means for replacing the first expression with a second expression comprising;

##EQU90## wherein the MGOJ operator comprises a relation (R₁ R₂,V₁ V₂,E'"'"') and the second expression preserves relations X₁ and X₃, wherein;

##EQU91## wherein R₁,2 is a non-empty set of real attributes, V₁,2 is a non-empty set of virtual attributes, and E₁,2 is a set of tuples for the relation r₁,2,

r₃ =X₃ =(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 for the relation r₃,

R₁,2 ∩

R₃ =.o slashed.,

V₁,2 ∩

V₃ =.o slashed.,

X₁ =(R₁,V₁,E₁),

X₁ and X₃ are relations such that R_x.sbsb.1 ∩

R_x.sbsb.3 =V_x.sbsb.1 ∩

V_x.sbsb.3 =.o slashed.,

R_x.sbsb.1 .OR right.R₁,2 and R_x.sbsb.3 .OR right.R₁,2, ##EQU92## p_i,j is a predicate for ##EQU93## and π

^c denotes a projection operation.