Rewriting inequality queries

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for expressing inequality expressions as a bounded number of equality expressions. One of the methods includes receiving an original query having an inequality expression for an original attribute. A new query that replaces the inequality expression with a bounded number of equality expressions is generated, wherein each equality expression references a respective auxiliary attribute, each auxiliary attribute representing intervals of values for the original attribute. The new query having the bounded number of equality expressions is provided to a database system instead of the original query. Query results that satisfy the inequality expression for the original attribute are received from the database system.

What is claimed is: 
     
       1. A computer-implemented method comprising:
 generating, for an original attribute of a relation maintained in a database system, a respective auxiliary attribute for each interval size of a plurality of interval sizes, each interval size corresponding to a different respective power of a particular exponent base; 
 computing, for each data entry of the relation and for each interval size of the plurality of interval sizes, a respective interval number for the interval size to which an original attribute value of the data entry belongs; 
 storing each respective computed interval number for each data entry in the database system as an auxiliary attribute value of a corresponding auxiliary attribute for the data entry; 
 receiving, by a query rewriter of a user device in communication with the database system, an original query having an inequality expression for the original attribute; 
 generating a new query that replaces the inequality expression with multiple equality expressions, wherein each equality expression references a different respective auxiliary attribute, each auxiliary attribute representing a different respective interval size for values of the original attribute; 
 providing, by the user device to the database system, the new query having the multiple equality expressions instead of the original query; and 
 receiving, by the user device from the database system, query results that satisfy the inequality expression for the original attribute. 
 
     
     
       2. The method of  claim 1 , wherein generating the new query that replaces the inequality expression with a bounded number of equality expressions comprises:
 generating a disjunct of equality expressions including determining, for each interval size of a plurality of interval sizes other than a maximum interval size, whether respective equality expressions that test for an auxiliary attribute value belonging to a first interval at the interval size, a last interval at the interval size, or both, should be added to the disjunct of equality expressions. 
 
     
     
       3. The method of  claim 1 , wherein the inequality expression specifies a range of values, and wherein the multiple equality expressions are a bounded number of equality expressions that collectively represent intervals that cover all values in the range of values with no overlap. 
     
     
       4. The method of  claim 1 , wherein the plurality of interval sizes correspond to sequential powers of two. 
     
     
       5. The method of  claim 1 , wherein the database system limits a number of disjunct expressions that can occur in a query. 
     
     
       6. The method of  claim 1 , wherein the database system forbids ordering query results by one or more attributes used in inequality expressions. 
     
     
       7. The method of  claim 1 , wherein the original query specifies an ordering of the query results by an attribute in the inequality expression, and wherein the database system restricts ordering query results occurring in inequality expressions. 
     
     
       8. The method of  claim 1 , further comprising generating the multiple equality expressions including:
 initializing a variable n to be equal to 1, initializing a variable nbegin to be equal to a start of a range of values specified by the inequality expression, and initializing a variable nend to be equal to an end of the range of values specified by the inequality expression; and 
 iteratively performing the following operations until the variable n is greater than or equal to a maximum interval size:
 determining whether nbegin is odd and adding an equality expression testing for an auxiliary attribute having a value belonging to a first interval of size n whenever nbegin is odd; 
 determining whether nend is even and adding an equality expression testing for an auxiliary attribute having a value belonging to a last interval of size n whenever nend is odd; 
 setting the variable n to be equal to n×2; 
 setting nbegin to be equal to (nbegin+1)/2 and discarding any remainder; and 
 setting nend to be equal to (nend−1)/2 and discarding any remainder. 
 
 
     
     
       9. The method of  claim 8 , further comprising performing the following operations until nbegin is greater than nend:
 adding an equality expression testing for the auxiliary attribute belonging to an interval identified by nbegin; and 
 setting nbegin to be equal to nbegin+1. 
 
     
     
       10. A system comprising:
 one or more computers comprising one or more processors and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising: 
 generating, for an original attribute of a relation maintained in a database system, a respective auxiliary attribute for each interval size of a plurality of interval sizes, each interval size corresponding to a different respective power of a particular exponent base; 
 computing, for each data entry of the relation and for each interval size of the plurality of interval sizes, a respective interval number for the interval size to which an original attribute value of the data entry belongs; 
 storing each respective computed interval number for each data entry in the database system as an auxiliary attribute value of a corresponding auxiliary attribute for the data entry; 
 receiving, by a query rewriter of a user device in communication with the database system, an original query having an inequality expression for the original attribute; 
 generating a new query that replaces the inequality expression with multiple equality expressions, wherein each equality expression references a different respective auxiliary attribute, each auxiliary attribute representing a different respective interval size for values of the original attribute; 
 providing, by the user device to the database system, the new query having the multiple equality expressions instead of the original query; and 
 receiving, by the user device from the database system, query results that satisfy the inequality expression for the original attribute. 
 
     
     
       11. The system of  claim 10 , wherein generating the new query that replaces the inequality expression with a bounded number of equality expressions comprises:
 generating a disjunct of equality expressions including determining, for each interval size of a plurality of interval sizes other than a maximum interval size, whether respective equality expressions that test for an auxiliary attribute value belonging to a first interval at the interval size, a last interval at the interval size, or both, should be added to the disjunct of equality expressions. 
 
     
     
       12. The system of  claim 10 , wherein the inequality expression specifies a range of values, and wherein the multiple equality expressions are a bounded number of equality expressions that collectively represent intervals that cover all values in the range of values with no overlap. 
     
     
       13. The system of  claim 10 , wherein the plurality of interval sizes correspond to sequential powers of two. 
     
     
       14. The system of  claim 10 , wherein the database system limits a number of disjunct expressions that can occur in a query. 
     
     
       15. The system of  claim 10 , wherein the database system forbids ordering query results by one or more attributes used in inequality expressions. 
     
     
       16. The system of  claim 10 , wherein the original query specifies an ordering of the query results by an attribute in the inequality expression, and wherein the database system restricts ordering query results occurring in inequality expressions. 
     
     
       17. The system of  claim 10 , wherein the operations further comprise generating the multiple equality expressions including:
 initializing a variable n to be equal to 1, initializing a variable nbegin to be equal to a start of a range of values specified by the inequality expression, and initializing a variable nend to be equal to an end of the range of values specified by the inequality expression; and 
 iteratively performing the following operations until the variable n is greater than or equal to a maximum interval size:
 determining whether nbegin is odd and adding an equality expression testing for an auxiliary attribute having a value belonging to a first interval of size n whenever nbegin is odd; 
 determining whether nend is even and adding an equality expression testing for an auxiliary attribute having a value belonging to a last interval of size n whenever nend is odd; 
 setting the variable n to be equal to n×2; 
 setting nbegin to be equal to (nbegin+1)/2 and discarding any remainder; and 
 setting nend to be equal to (nend−1)/2 and discarding any remainder. 
 
 
     
     
       18. The system of  claim 17 , wherein the operations further comprise performing the following operations until nbegin is greater than nend:
 adding an equality expression testing for the auxiliary attribute belonging to an interval identified by nbegin; and 
 setting nbegin to be equal to nbegin+1. 
 
     
     
       19. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
 generating, for an original attribute of a relation maintained in a database system, a respective auxiliary attribute for each interval size of a plurality of interval sizes, each interval size corresponding to a different respective power of a particular exponent base; 
 computing, for each data entry of the relation and for each interval size of the plurality of interval sizes, a respective interval number for the interval size to which an original attribute value of the data entry belongs; 
 storing each respective computed interval number for each data entry in the database system as an auxiliary attribute value of a corresponding auxiliary attribute for the data entry, 
 receiving, by a query rewriter of a user device in communication with the database system, an original query having an inequality expression for the original attribute, 
 generating a new query that replaces the inequality expression with multiple equality expressions, wherein each equality expression references a different respective auxiliary attribute, each auxiliary attribute representing a different respective interval size for values of the original attribute; 
 providing, by the user device to the database system, the new query having the multiple equality expressions instead of the original query; and 
 receiving, by the user device from the database system, query results that satisfy the inequality expression for the original attribute. 
 
     
     
       20. The computer program product of  claim 19 , wherein generating the new query that replaces the inequality expression with a bounded number of equality expressions comprises:
 generating a disjunct of equality expressions including determining, for each interval size of a plurality of interval sizes other than a maximum interval size, whether respective equality expressions that test for an auxiliary attribute value belonging to a first interval at the interval size, a last interval at the interval size, or both, should be added to the disjunct of equality expressions. 
 
     
     
       21. The computer program product of  claim 19 , wherein the inequality expression specifies a range of values, and wherein the multiple equality expressions are a bounded number of equality expressions that collectively represent intervals that cover all values in the range of values with no overlap. 
     
     
       22. The computer program product of  claim 19 , wherein the plurality of interval sizes correspond to sequential powers of two. 
     
     
       23. The computer program product of  claim 19 , wherein the operations further comprise generating the multiple equality expressions including:
 initializing a variable n to be equal to 1, initializing a variable nbegin to be equal to a start of a range of values specified by the inequality expression, and initializing a variable nend to be equal to an end of the range of values specified by the inequality expression; and 
 iteratively performing the following operations until the variable n is greater than or equal to a maximum interval size:
 determining whether nbegin is odd and adding an equality expression testing for an auxiliary attribute having a value belonging to a first interval of size n whenever nbegin is odd; 
 determining whether nend is even and adding an equality expression testing for an auxiliary attribute having a value belonging to a last interval of size n whenever nend is odd; 
 setting the variable n to be equal to n×2; 
 setting nbegin to be equal to (nbegin+1)/2 and discarding any remainder; and 
 setting nend to be equal to (nend−1)/2 and discarding any remainder. 
 
 
     
     
       24. The computer program product of  claim 23 , wherein the operations further comprise performing the following operations until nbegin is greater than nend:
 adding an equality expression testing for the auxiliary attribute belonging to an interval identified by nbegin; and 
 setting nbegin to be equal to nbegin+1.