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

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.

We claim: 
     
       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 1 , . . . , P P ), said order requirement vector O Ri  includes a second ordered list of relation attributes (R 1 , . . . , 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 1 , . . . , P p ), said order requirement vector O Ri  includes a second ordered list of relation attributes (R 1 , . . . , 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 1 , . . . , P p ), said order requirement vector O Ri  includes a second ordered list of relation attributes (R 1 , . . . , 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 1 , . . . , P p ), said order requirement vector O Ri  includes a second ordered list of relation attributes (R 1 , . . . , 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 1 , . . . , P p ), said order requirement vector O Ri  includes a second ordered list of relation attributes (R 1 , . . . , 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 1 , . . . , P p ), said order requirement vector O Ri  includes a second ordered list of relation attributes (R 1 , . . . , 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 1 , . . . , P p ), said order requirement vector O Ri  includes a second ordered list of relation attributes (R 1 , . . . , 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 1 , . . . , P p ), said order requirement vector O Ri  includes a second ordered list of relation attributes (R 1 , . . . , 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 .