Semantic optimization of query order requirements using order detection by normalization in a query compiler system

• US 5,619,692 A
• Filed: 02/17/1995
• Issued: 04/08/1997
• Est. Priority Date: 02/17/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shekita, Eugene J., Simmen, David E., Malkemus, Timothy R.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/394,532
• Time in Patent Office: 781 Days
• Field of Search: 395/600, 395/650, 395/700
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A procedure for detecting a reordering requirement in a directed record stream during query execution in a relational database processing system. The query compiler component of a relational database processing system includes procedures for building query execution plans (QEPs) for evaluation preparatory to selecting an optimal plan for execution. These plans are constructed from the bottom up using an internal graphical representation for the user query that has a number of relation nodes interconnected by directed record streams (data flows). A relational operation within each node imposes an "order requirement" on the outflow stream represented by an order requirement vector O_R. The records within each directed record stream have an "order property" represented by an order property vector O_P. Order detection occurs when these two vectors are compared to determine whether the order property satisfies the order requirement. Order detection by normalization (ODN) according to this invention first normalizes the two order specification vectors to remove all attributes made redundant by the effects of predicates and functional dependencies. Query execution plans constructed using ODN are found to execute an order of magnitude faster than those constructed using order detection without normalization.

Claims

1. A method for order detection during processing of a query in a relational database processing system having a stored database including a plurality of base-relations {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N_i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O_Ri, wherein each said relation node N_i is connected to at least one other said relation node N_j by a directed record stream R_ij representing a record stream output from said each relation node N_i and a record stream input to said other relation node N_j ordered according to an order property vector O_Pi, wherein i and j are positive integers, said method comprising the steps of:

(a) normalizing said order property vector O_Pi to produce a normalized order property vector O_PNi for said input record stream R_ji of a first said relation node N_i ;

(b) normalizing said order requirement vector O_Ri to produce a normalized order requirement vector O_RNi for said first relation node N_i ; and

(c) comparing said normalized order requirement vector O_RNi to said normalized order property vector O_PNi to detect an ordering requirement for said first relation node N_i.

2. The method of claim 1 wherein said order property vector O_Pi includes a first ordered list of relation attributes (P₁, . . . , P_P), said order requirement vector O_Ri includes a second ordered list of relation attributes (R₁, . . . , R_r), said relation attributes each belong to a class of equivalent attributes including a head attribute, 0≦

p, r are non-negative integers and wherein said normalizing steps (a) and (b) comprise the steps of;

(a.1) replacing in said order property vector O_Pi each said relation attribute P_P in said first ordered list with the head attribute P_Hp from said equivalence class containing said each relation attribute P_P ;

(a.2) eliminating relation attribute duplicates from said first ordered list in said order property vector O_Pi ;

(b.1) replacing in said order requirement vector O_Ri each said relation attribute R_r in said second ordered list with the head attribute R_Hr from said equivalence class containing said each relation attribute R_r ; and

(b.2) eliminating relation attribute duplicates from said second ordered list in said order requirement vector O_Pi.

3. The method of claim 2 wherein said order property vector O_Pi includes at least one functionally-dependent relation attribute P_j that is fully determined by one or more said relational attributes {P_k } ordered ahead of said functionally-dependent relation attribute P_j in said first ordered list or said order requirement vector O_Ri includes at least one functionally-dependent relation attribute R_j that is fully determined by one or more said relational attributes {R_k } ordered ahead of said functionally-dependent relation attribute R_j in said second ordered list, 1≦

k≦

j are positive integers and wherein said normalizing steps (a) and (b) further comprise the steps of;

(a.

     3) eliminating each said functionally-dependent relation attribute P_j from said order property vector O_Pi ; and

(b.3) eliminating each said functionally-dependent relation attribute R_j from said order requirement vector O_Ri.

4. The method of claim 3 wherein said order property vector O_Pi or said order requirement vector O_Ri includes at least one bound relation attribute that has the same value for every record in said input record stream R_ji and wherein said normalizing steps (a) and (b) further comprise the steps of:

(a.4) eliminating each said bound relation attribute from said order property vector O_Pi ; and

(b.4) eliminating each said bound relation attribute from said order requirement vector O_Ri.

5. The method of claim 1 wherein said order property vector O_Pi includes a first ordered list of relation attributes (P₁, . . . , P_p), said order requirement vector O_Ri includes a second ordered list of relation attributes (R₁, . . . , R_r), said order property vector O_Pi includes at least one functionally-dependent relation attribute P_j that is fully determined by one or more said relational attributes {P_k } ordered ahead of said functionally-dependent relation attribute P_j in said first ordered list or said order requirement vector O_Ri includes at least one functionally-dependent relation attribute R_j that is fully determined by one or more said relational attributes {R_k } ordered ahead of said functionally-dependent relation attribute R_j in said second ordered list, said relation attributes each belong to a class of equivalent attributes including a head attribute, 1≦

k≦

j are positive integers, 0≦

p, r are non-negative integers and wherein said normalizing steps (a) and (b) comprise the steps of;

(a.1) eliminating each said functionally-dependent relation attribute P_j from said order property vector O_Pi ; and

(b.1) eliminating each said functionally-dependent relation attribute R_j from said order requirement vector O_Ri.

6. A query compiler system in a relational database processing system comprising:

a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N_i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O_Ri, wherein each said relation node N_i is connected to at least one other said relation node N_j by a directed record stream R_ij representing a record stream output from said each relation node N_i and a record stream input to said other relation node N_j ordered according to an order property vector O_Pi, wherein i and j are positive integers;

normalizing means in said data processor for normalizing said order property vector O_Pi to produce a normalized order property vector O_PNi for said input record stream P_ji of a first said relation node N_i and for normalizing said order requirement vector O_Ri to produce a normalized order requirement vector O_RNi for said first relation node N_i ; and

order detection means coupled to said normalizing means for comparing said normalized order requirement vector O_RNi to said normalized order property vector O_PNi to detect an ordering requirement for said first relation node N_i.

7. The system of claim 6 wherein said order property vector O_Pi includes a first ordered list of relation attributes (P₁, . . . , P_p), said order requirement vector O_Ri includes a second ordered list of relation attributes (R₁, . . . , R_r), said relation attributes each belong to a class of equivalent attributes including a head attribute, 0≦

p, r are non-negative integers and wherein said normalizing means comprises;

equivalence substitution means for replacing in said order property vector O_Pi each said relation attribute P_p in said first ordered list with the head attribute P_Hp from said equivalence class containing said each relation attribute P_p and for replacing in said order requirement vector O_Ri each said relation attribute R_r in said second ordered list with the head attribute R_Hr from said equivalence class containing said each relation attribute R_r ; and

duplicates squeezing means for eliminating relation attribute duplicates from said first ordered list in said order property vector O_Pi and for eliminating relation attribute duplicates from said second ordered list in said order requirement vector O_Pi.

8. The system of claim 7 wherein said order property vector O_Pi includes at least one functionally-dependent relation attribute P_j that is fully determined by one or more said relational attributes {P_k } ordered ahead of said functionally-dependent relation attribute P_j in said first ordered list or said order requirement vector O_Ri includes at least one functionally-dependent relation attribute R_j that is fully determined by one or more said relational attributes {R_k } ordered ahead of said functionally-dependent relation attribute R_j in said second ordered list, 1≦

k<

j are positive integers and wherein said normalizing means further comprises;

functional-dependencies squeezing means for eliminating each said functionally-dependent relation attribute P_j from said order property vector O_Pi and for eliminating each said functionally-dependent relation attribute R_j from said order requirement vector O_Ri.

9. The system of claim 8 wherein said order property vector O_Pi or said order requirement vector O_Ri includes at least one bound relation attribute that has the same value for every record in said input record stream R_ji and wherein said normalizing means further comprises:

redundancies squeezing means for eliminating each said bound relation attribute from said order property vector O_Pi and for eliminating each said bound relation attribute from said order requirement vector O_Ri.

10. The system of claim 6 wherein said order property vector O_Pi includes a first ordered list of relation attributes (P₁, . . . , P_p), said order requirement vector O_Ri includes a second ordered list of relation attributes (R₁, . . . , R_r), said order property vector O_Pi includes at least one functionally-dependent relation attribute P_j that is fully determined by one or more said relational attributes {P_k } ordered ahead of said functionally-dependent relation attribute P_j in said first ordered list or said order requirement vector O_Ri includes at least one functionally-dependent relation attribute R_j that is fully determined by one or more said relational attributes {R_k } ordered ahead of said functionally-dependent relation attribute R_j in said second ordered list, said relation attributes each belong to a class of equivalent attributes including a head attribute, 1≦

k<

j are positive integers, 0≦

p, r are non-negative integers and wherein said normalizing means comprises;

functional-dependencies squeezing means for eliminating each said functionally-dependent relation attribute P_j from said order property vector O_Pi and for eliminating each said functionally-dependent relation attribute R_j from said order requirement vector O_Ri.

11. A database processing system comprising:

a stored database including a plurality of base-relations {T};

a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N_i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O_Ri, wherein each said relation node N_i is connected to at least one other said relation node N_j by a directed record stream R_ij representing a record stream output from said each relation node N_i and a record stream input to said other relation node N_j ordered according to an order property vector O_Pi, wherein i and j are positive integers;

normalizing means in said data processor for normalizing said order property vector O_Pi to produce a normalized order property vector O_PNi for said input record stream R_ji of a first said relation node N_i and for normalizing said order requirement vector O_Ri to produce a normalized order requirement vector O_RNi for said first relation node N_i ; and

order detection means coupled to said normalizing means for comparing said normalized order requirement vector O_RNi to said normalized order property vector O_PNi to detect an ordering requirement for said first relation node N_i.

12. The system of claim 11 wherein said order property vector O_Pi includes a first ordered list of relation attributes (P₁, . . . , P_p), said order requirement vector O_Ri includes a second ordered list of relation attributes (R₁, . . . , R_r), said relation attributes each belong to a class of equivalent attributes including a head attribute, 0≦

p, r are non-negative integers and wherein said normalizing means comprises;

equivalence substitution means for replacing in said order property vector O_Pi each said relation attribute P_p in said first ordered list with the head attribute P_Hp from said equivalence class containing said each relation attribute P_p and for replacing in said order requirement vector O_Ri each said relation attribute R_r in said second ordered list with the head attribute R_Hr from said equivalence class containing said each relation attribute R_r ; and

duplicates squeezing means for eliminating relation attribute duplicates from said first ordered list in said order property vector O_Pi and for eliminating relation attribute duplicates from said second ordered list in said order requirement vector O_Pi.

13. The system of claim 12 wherein said order property vector O_Pi includes at least one functionally-dependent relation attribute P_j that is fully determined by one or more said relational attributes {P_k } ordered ahead of said functionally-dependent relation attribute P_j in said first ordered list or said order requirement vector O_Ri includes at least one functionally-dependent relation attribute R_j that is fully determined by one or more said relational attributes {R_k } ordered ahead of said functionally-dependent relation attribute R_j in said second ordered list, 1≦

k<

j are positive integers and wherein said normalizing means further comprises;

functional-dependencies squeezing means for eliminating each said functionally-dependent relation attribute P_j from said order property vector O_Pi and for eliminating each said functionally-dependent relation attribute R_j from said order requirement vector O_Ri.

14. The system of claim 13 wherein said order property vector O_Pi or said order requirement vector O_Ri includes at least one bound relation attribute that has the same value for every record in said input record stream R_ji and wherein said normalizing means further comprises:

redundancies squeezing means for eliminating each said bound relation attribute from said order property vector O_Pi and for eliminating each said bound relation attribute from said order requirement vector O_Ri.

15. The system of claim 11 wherein said order property vector O_Pi includes a first ordered list of relation attributes (P₁, . . . , P_p), said order requirement vector O_Ri includes a second ordered list of relation attributes (R₁, . . . , R_r), said order property vector O_Pi includes at least one functionally-dependent relation attribute P_j that is fully determined by one or more said relational attributes {P_k } ordered ahead of said functionally-dependent relation attribute P_j in said first ordered list or said order requirement vector O_Ri includes at least one functionally-dependent relation attribute R_j that is fully determined by one or more said relational attributes {R_k } ordered ahead of said functionally-dependent relation attribute R_j in said second ordered list, said relation attributes each belong to a class of equivalent attributes including a head attribute, 1≦

k<

j are positive integers, 0≦

p, r are non-negative integers and wherein said normalizing means comprises;

functional-dependencies squeezing means for eliminating each said functionally-dependent relation attribute P_j from said order property vector O_Pi and for eliminating each said functionally-dependent relation attribute R_j from said order requirement vector O_Ri.

16. A computer program product, for use with a relational database processing system having a stored database including a plurality of base-relations {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N_i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O_Ri, wherein each said relation node N_i is connected to at least one other said relation node N_j by a directed record stream R_ij representing a record stream output from said each relation node N_i and a record stream input to said other relation node N_j ordered according to an order property vector O_Pi, wherein i and j are positive integers, said computer program product comprising:

a recording medium;

means, recorded on said recording medium, for directing said data processor to normalize said order property vector O_Pi to produce a normalized order property vector O_PNi for said input record stream R_ji of a first said relation node N_i ;

means, recorded on said recording medium, for directing said data processor to normalize said order requirement vector O_Ri to produce a normalized order requirement vector O_RNi for said first relation node N_i ; and

means, recorded on said recording medium, for directing said data processor to compare said normalized order requirement vector O_RNi to said normalized order property vector O_PNi to detect an ordering requirement for said first relation node N_i.

17. The computer program product of claim 16 wherein said order property vector O_Pi includes a first ordered list of relation attributes (P₁, . . . , P_p), said order requirement vector O_Ri includes a second ordered list of relation attributes (R₁, . . . , R_r), said relation attributes each belong to a class of equivalent attributes including a head attribute and wherein 0≦

p, r are non-negative integers, said computer program product further comprising;

means, recorded on said recording medium, for directing said data processor to replace in said order property vector O_Pi each said relation attribute P_p in said first ordered list with the head attribute P_Hp from said equivalence class containing said each relation attribute P_p ;

means, recorded on said recording medium, for directing said data processor to eliminate relation attribute duplicates from said first ordered list in said order property vector O_Pi ;

means, recorded on said recording medium, for directing said data processor to replace in said order requirement vector O_Ri each said relation attribute R_r in said second ordered list with the head attribute R_Hr from said equivalence class containing said each relation attribute R_r ; and

means, recorded on said recording medium, for directing said data processor to eliminate relation attribute duplicates from said second ordered list in said order requirement vector O_Pi.

18. The computer program product of claim 17 wherein said order property vector O_Pi includes at least one functionally-dependent relation attribute P_j that is fully determined by one or more said relational attributes {P_k } ordered ahead of said functionally-dependent relation attribute P_j in said first ordered list or said order requirement vector O_Ri includes at least one functionally-dependent relation attribute R_j that is fully determined by one or more said relational attributes {R_k } ordered ahead of said functionally-dependent relation attribute R_j in said second ordered list and wherein 1≦

k<

j are positive integers, said computer program product further comprising;

means, recorded on said recording medium, for directing said data processor to eliminate each said functionally-dependent relation attribute P_j from said order property vector O_Pi ; and

means, recorded on said recording medium, for directing said data processor to eliminate each said functionally-dependent relation attribute R_j from said order requirement vector O_Ri.

19. The computer program product of claim 18 wherein said order property vector O_Pi or said order requirement vector O_Ri includes at least one bound relation attribute that has the same value for every record in said input record stream R_ji, said computer program product further comprising:

means, recorded on said recording medium, for directing said data processor to eliminate each said bound relation attribute from said order property vector O_Pi ; and

means, recorded on said recording medium, for directing said data processor to eliminate each said bound relation attribute from said order requirement vector O_Ri.

20. The computer program product of claim 16 wherein said order property vector O_Pi includes a first ordered list of relation attributes (P₁, . . . , P_p), said order requirement vector O_Ri includes a second ordered list of relation attributes (R₁, . . . , R_r), said order property vector O_Pi includes at least one functionally-dependent relation attribute P_j that is fully determined by one or more said relational attributes {P_k } ordered ahead of said functionally-dependent relation attribute P_j in said first ordered list or said order requirement vector O_Ri includes at least one functionally-dependent relation attribute R_j that is fully determined by one or more said relational attributes {R_k } ordered ahead of said functionally-dependent relation attribute R_j in said second ordered list, said relation attributes each belong to a class of equivalent attributes including a head attribute, 1≦

k<

j are positive integers and wherein 0≦

p, r are non-negative integers, said computer program product comprising;

means, recorded on said recording medium, for directing said data processor to eliminate each said functionally-dependent relation attribute P_j from said order property vector O_Pi ; and

means, recorded on said recording medium, for directing said data processor to eliminate each said functionally-dependent relation attribute R_j from said order requirement vector O_Ri.