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.
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. 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.