Abstract:
Methods are described to simultaneously apply conjugates of equality, range, and in-list predicates. A first set of methods are described for the simultaneous application of equality predicates. A second set of methods are described for the simultaneous application of a mixture of range and equality predicates. A third method is described for the simultaneous applying a mixture of in-list predicates. The described methods allow for quick evaluation of complex predicates as they efficiently implement the computation done per record, while maintaining the same execution time irrespective of the number of fields.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of Invention 
     The present invention relates generally to the field of predicate evaluation. More specifically, the present invention is related to method for evaluating a conjunction of equity and range predicates using a constant number of operations. 
     2. Discussion of Related Art 
     Conjunctive predicates (e.g., p1 AND p2 AND . . . ) are the most common kind of predicate used in querying databases. The standard way to evaluate a conjunction of predicates on a record is via a method of the form: 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 for each predicate do: 
               
               
                   
                   extract the fields that this predicate is over 
               
               
                   
                   if record satisfies predicate continue 
               
               
                   
                   else return that the record does not satisfy predicate 
               
               
                   
                 // every predicate has been verified 
               
               
                   
                 return that the record satisfies predicate 
               
               
                   
                   
               
             
          
         
       
     
     The performance of this predicate evaluation is a significant fraction of overall query performance in modern high-performance business intelligence (BI) engines that do large amounts of data scans. But at least three drawbacks make this standard method of predicate evaluation to be slow and have variable performance. 
     First, in prior art predicate evaluations, the evaluation time varies based on the number of predicates to be applied. For example, in the paper by Holloway et al. titled “How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans”, it was found that each extra field that is touched adds about 6-8 cycles per record for a scan, which, in turn, causes variability in scan performance. 
     Second, in prior art predicate evaluations, each field needs to be extracted before predicates are applied. The cost associated with such an operation is expensive, especially in newer databases where fields are not aligned at machine-word (64-bit) boundaries. 
     Third, in prior art predicate evaluations, the loop condition and the predicate evaluation within the loop both result in conditional branch statements. Mispredicted branches cost orders of magnitude more than regular instructions on almost all modern processors (e.g., we have timed at 40 cycles on a Pentium® family processor). 
     Whatever the precise merits, features, and advantages of such prior art predicate evaluations, none of them achieves or fulfills the purposes of the present invention. 
     SUMMARY OF THE INVENTION 
     The present invention, in one embodiment, provides a computer-based method to simultaneously evaluate conjunctions of equality predicates on k fields F 1 , F 2 , . . . F k : F 1 =L 1  and F 2 =L 2  and F k =L k  of a record, wherein L 1 , L 2  . . . L k  represent values and fields F 1 , F 2 , . . . F k  are at offsets [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] within the record. The method of this embodiment, as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) constructing a mask to extract values of the fields F 1 , F 2 , . . . F k  within a cell, wherein the mask comprises a bit vector M having 1s in bits [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] and having 0s in remainder of bits; (b) constructing a value vector comprising a bit vector V having values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 0s in remainder of bits; (c) for each record, R, on which said equality predicates need to be applied, evaluating if R AND M=V; and (d) outputting results of said evaluation in (c). 
     In one variation, the bit vector M has 0s in bits [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] and 1s in remaining bits, and the bit vector V has values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 1s in remainder of bits, and instead of evaluating if R AND M=V, the method comprises the step of evaluating if R OR M=V. 
     In another variation of the above-described method, instead of evaluating if R AND M=V, the method evaluates if (R XOR V) AND M=0. 
     In another embodiment, the present invention provides a computer based method to simultaneously evaluate conjunctions of range and equality predicates on k fields of a record being either F 1 , F 2 , . . . F k : F 1 ≦L 1  and F 2 ≦L 2  and F k ≦L k , or F 1 , F 2 , . . . F k : F 1 ≧L 1  and F 2 ≧L 2  and F k ≧L k , wherein L 1 , L 2  . . . L k  represent values and fields F 1 , F 2 , . . . F k  are at offsets [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] within the record. In this embodiment, the method, as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) computing B i =S i −C for said k fields, wherein C is a constant whole number (e.g., C=1); (b) constructing a mask to extract values of k bits B 1 , B 2 , . . . , B k , wherein the mask comprises a bit vector M having 1s in bits at k bit positions, B 1 , B 2 , B k  having 0s in remainder of bits; (c) constructing a value vector containing values of fields F 1 , F 2 , . . . F k , wherein the value vector comprises a bit vector V having values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 0s in remainder of bits; (d) for each record, R, on which the predicates need to be applied, evaluating as follows: 
                                             when F 1 , F 2 , ... F k : F 1  ≦ L 1  and F 2  ≦ L 2  and F k  ≦ L k ,            evaluating ((V−R) AND M) = (V XOR R) AND M), or           when F 1 , F 2 , ... F k : F 1  ≧ L 1  and F 2  ≧ L 2  and F k  ≧ L k  ,            evaluating ((R−V) AND M) = (V XOR R) AND M),                        
wherein the AND operator represents bit-wise AND of two bit vectors and said XOR operator represents bit-wise Exclusive OR of two bit vectors; and (e) outputting results of said evaluation operation in (d).
 
     In one variation of the above-described embodiment, the method in step (d), instead of evaluating if ((V−R) AND M)=(V XOR R) AND M), evaluates if (((V−R) XOR V XOR R) AND M)=0. 
     In another variation of the above-described embodiment, the method in step (d), instead of evaluating if ((V−R) AND M)=(VXOR R) AND M), evaluates if ((V−R) XOR VXOR R) OR (NOT M)=(NOT M). 
     The present invention in another embodiment provides for a computer based method to simultaneously evaluate conjunctions of one or more range or equality predicates on k fields F 1 , F 2 , . . . F k  of a record, where each predicate is one of four forms: (i) L i ≦F i  or (ii) F i ≦U i  or (iii) F i =L i  or (iv) L i ≦F 1 ≦U i , and wherein L 1 , L 2  . . . L k  represent values and the k fields being at offsets [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] of the record. The method of this embodiment comprises the steps of: (a) computing B i =S i −C for the k fields, wherein C is a constant whole number (e.g., C=1); (b) constructing a mask to extract values of k bits B 1 , B 2 , . . . , B k , wherein the mask comprises a bit vector M having 1s in bits at k bit positions, B 1 , B 2 , . . . , B k  having 0s in remainder of bits; (c) constructing a first value vector containing lower bound values, wherein the first value vector comprises a bit vector V L  having 0s everywhere except one or more of the following: L 1  at bit positions [S 1 , E 1 ], L 2  at bit positions [S 2 , E 2 ] . . . L k  at bit positions [S k , E k ]; (d) constructing a second value vector containing upper bound values, wherein the second value vector comprises a bit vector V U  having 1s everywhere except one or more of the following: U 1  at bit positions [S 1 , E 1 ], U 2  at bit positions [S 2 , E 2 ] . . . U k  at bit positions [S k , E k ]; (e) for each record, R, on which said predicates need to be applied, evaluating (((V U −R) XOR (R−V L )) AND M)=(V U  XOR V L ) AND M), wherein the AND operator represents bit-wise AND of two bit vectors and said XOR operator represents bit-wise Exclusive OR of two bit vectors; and (f) outputting results of the evaluation operation in (e). 
     In an extended embodiment, the above-described method further comprises the step of precomputing (V U  XOR V L ) AND M, and evaluating remainder of expression in (e) on a per record basis. 
     In a variation to the above-described embodiment, the method, in step (e), evaluates if ((V U −R) XOR (R−V L ) XOR VuXOR V L ) AND M=0. 
     In another variation to the above-described embodiment, the method, in step (e), evaluates if ((V U −R) XOR (R−V L ) XOR V U  XOR V L ) OR (NOT M)=(NOT M). 
     The present invention, in another embodiment, provides for a computer based method to simultaneously evaluate conjunctions of a mixture of in-list predicates on k fields F 1 , F 2 , . . . F k  of the form F 1  in (L 11 , L 12  . . . L 1n ) and F 2  in (L 21 , L 22  . . . L 2n ) and . . . F k  in (L k1 , L k2  . . . L kn ), wherein the k fields are at offsets [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ]. In this embodiment, the method, as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) constructing a first mask to extract values of k fields, wherein the first mask comprises a bit vector M having 1s in bits [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] and having 0s in remainder of bits; (b) constructing a second mask to extract most significant bit of each field, wherein the second mask comprises a bit vector S having 0s in bits S 1 , S 2 , . . . , S k  and having 1s in remainder of bits; (c) for each 1 through n, computing a bit vector of values V 1 , V 2 , . . . , V n , wherein V i  has 0s in all bits except values L 1i , L 2i , . . . . L ki  at [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively; (d) for each record, R, on which said predicates need to be applied, evaluating n numbers as follows: 
     N 1 =((((V 1  XOR R) AND S)+S) OR (V 1  XOR R)); 
     N 2 =((((V 2  XOR R) ANDS)+S) OR (V 2  XOR R)); . . . 
     N n =((((V n  XOR R) AND S)+S) OR (V n  XOR R)); 
     and then evaluating the following condition:
 
((N 1  AND N 2  AND . . . N n ) OR S)=S
 
wherein the AND operator represents bit-wise AND of two bit vectors, the XOR operator represents bit-wise Exclusive OR of two bit vectors, and the + operator represents addition, and OR represents bit-wise OR; and (e) outputting results of said evaluation operation in (d).
 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIGS. 1-3  illustrate various examples of the first embodiment&#39;s computer-based method to simultaneously evaluate conjunctions of equality predicates. 
         FIGS. 4-9  illustrate various examples of the second embodiment&#39;s computer-based method to simultaneously evaluate range and equality predicates. 
         FIG. 10  illustrates an example of the third embodiment&#39;s computer-based method to simultaneously evaluate a mixture of in-list predicates. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The paper by Raman et al. entitled, “Constant-Time Query Processing,” to be published in the Proceedings of the 24 th  IEEE International Conference on Data Engineering, held Apr. 7-12, 2008, in Cancun, Mexico, attached in Appendix A, provides additional details regarding a simplified database architecture that achieves constant time query processing. 
     While this invention is illustrated and described in a preferred embodiment, the invention may be produced in many different configurations. There is depicted in the drawings, and will herein be described in detail, a preferred embodiment of the invention, with the understanding that the present disclosure is to be considered as an exemplification of the principles of the invention and the associated functional specifications for its construction and is not intended to limit the invention to the embodiment illustrated. Those skilled in the art will envision many other possible variations within the scope of the present invention. 
     The present invention teaches a method to efficiently apply conjunctions of one or more predicates (a predicate is a condition such as weight&lt;=150) on fields in a database, such as: 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 age&gt;10 AND 
               
               
                   
                 salary between [10000,20002] AND 
               
               
                   
                 state in (‘CA’, ‘MI’) AND 
               
               
                   
                 hairColor in (‘black’, ‘blue’, ‘orange’) AND 
               
               
                   
                 weight&lt; 150 AND 
               
               
                   
                 shoeSize = 10 
               
               
                   
                   
               
             
          
         
       
     
     In the example above, conditions such as ‘shoeSize=10’ are called equality predicates and conditions such as ‘age&gt;10’ and ‘salary between [10000,20002]’ are called range predicates. Conditions such as ‘hairColor in (‘black’, ‘blue’, ‘orange’)’ are called in-list predicates. 
     Conjunction refers to all of the clauses that have to be simultaneously true for the overall condition to be satisfied. Such conjunctions are the most common kinds of predicates that occur in databases, search engines, etc. 
     It should be noted that the present invention&#39;s methods apply even in instances where the conjunction is only a part of the overall predicate. For example: 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                   (age&gt;10 AND salary between 10000 and 20002)  AND 
               
               
                   
                 ( (weight&lt; 150 AND shoeSize = 10)  OR ( state in (‘CA’, ‘MI’) AND   
               
               
                   
                   (hairColor in (‘black’, ‘blue’, ‘orange’) ) )   
               
               
                   
                   
               
             
          
         
       
     
     In the above-example, the overall predicate is not a conjunction because of the ORs, but our methods apply to each of the underlined parts. 
     The present invention&#39;s methods apply conjunctions simultaneously on fields in a database. The present invention is based on the following conditions, wherein these conditions apply to many of the current databases:
         the fields involved in the predicate are at fixed offsets within each record (if some fields are not at fixed offsets, our methods still apply to the part of the predicate that is on fields at fixed offsets)   the predicates can be evaluated on the fields as they are represented within the record.       

     First Embodiment 
     Applying Equality Predicates Simultaneously 
     Treat each record R as a single bit-vector of N bits (N is usually set to be a machine word size, such as 8, 16, 32, or 64 bits and if R is too large to fit into a single machine word, it is broken up into multiple words). If equality predicates are evaluated on k fields F 1  . . . F k : F 1 =L 1  and F 2 =L 2  and . . . F k =L k  (the fields F 1  . . . F k  are the attributes of the record, such as shoeSize in the previous example and L 1  . . . L k  are the corresponding constants, such as 10 for the condition ‘shoeSize=10’, wherein such constants are also referred to as literals). Fields F 1  . . . F k  are at bit offsets [S 1 , E 1 ], [S 2 , E 2 ], . . . [S k , E k ] respectively, i.e., the first field lies in bits S 1  through E 1  of the record, the second field lies in bits S 2  through E 2  of the record, and so on. The corresponding literals are L 1 , L 2 , . . . L k . The method of the first embodiment, computes a bit-wise AND of the tuple with a pre-computed mask that has the literals at the same positions as the corresponding fields, and check if the result is equal to the mask. 
       FIG. 1  illustrates an example of the first embodiment&#39;s computer-based method to simultaneously evaluate conjunctions of equality predicates on k fields F 1 , F 2 , . . . F k : F 1 =L 1  and F 2 =L 2  and F k =L k  of a record, with L 1 , L 2  . . . L k  representing values and fields F 1 , F 2 , . . . F k  being at offsets [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] within the record, wherein an offset [X, Y] represents bits X through Y. 
     Method  100 , according to this example, is implemented in computer readable program code stored in computer storage and comprises the steps of: (a) constructing a mask to extract values of said fields F 1 , F 2 , . . . F k  within a cell, wherein the mask comprises a bit vector M having 1s in bits [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] and having 0s in remainder of bits—step  102 ; (b) constructing a value vector comprising a bit vector V having the values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 0s in remainder of bits—step  104 ; (c) for each record, R, on which the equality predicates need to be applied, evaluating if R AND M=V—step  106 ; and (d) outputting results of the evaluation in (c)—step  108 . 
     Variations of the method of  FIG. 1  are envisioned and are within the scope of the present invention. 
     For example,  FIG. 2  illustrates such a variation of the method of the first embodiment. Method  200 , according to this example, is implemented in computer readable program code stored in computer storage and comprises the steps of: (a) constructing a mask to extract values of said fields F 1 , F 2 , . . . F k  within a cell, wherein the mask comprises a bit vector M having 0s in bits [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] and having 1s in remainder of bits—step  202 ; (b) constructing a value vector comprising a bit vector V having the values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 1s in remainder of bits—step  204 ; (c) for each record, R, on which the equality predicates need to be applied, evaluating if R OR M=V—step  206 ; and (d) outputting results of the evaluation in (c)—step  208 . 
       FIG. 3  illustrates yet another variation of the method of the first embodiment. Method  300 , according to this example, is implemented in computer readable program code stored in computer storage and comprises the steps of: (a) constructing a mask to extract values of said fields F 1 , F 2 , . . . F k  within a cell, wherein the mask comprises a bit vector M having 1s in bits [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] and having 0s in remainder of bits—step  302 ; (b) constructing a value vector comprising a bit vector V having the values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 0s in remainder of bits—step  304 ; (c) for each record, R, on which the equality predicates need to be applied, evaluating if (R XOR V) AND M=0—step  306 ; and (d) outputting results of the evaluation in (c)—step  308 . 
     The benefit of the methods of the first embodiment is that computation done per record (a bitwise and an equality comparison) is efficiently done (with hardware or software instructions), and takes the same amount of time irrespective of k. This allows for very complex predicates to be evaluated quickly. 
     It should be noted that bit-wise AND could be implemented by combinations of other operators, and such modifications are considered within the scope of the present invention. 
     Second Embodiment 
     Applying a Mixture of Range and Equality Predicates Simultaneously 
     In this embodiment, equality predicates (such as ‘shoeSize=10’) are rewritten into range predicates such as shoeSize&lt;=10 and shoeSize&gt;=10. Predicates such as ‘weight&lt;150’ are rewritten into predicates of the form ‘weight&lt;=149’ by subtracting 1. Conjunction of predicates are of two forms: field&lt;=literal, field&gt;=literal. 
       FIG. 4  illustrates an example of the second embodiment&#39;s computer-based method to simultaneously evaluate conjunctions of range and equality predicates on k fields of a record being either F 1 , F 2 , . . . F k : F 1 ≦L 1  and F 2 ≦L 2  and F k ≦L k , or F 1 , F 2 , . . . F k : F 1 ≧L 1  and F 2 ≧L 2  and F k ≧L k , wherein L 1 , L 2  . . . L k  represent values and the fields F 1 , F 2 , . . . F k  are at offsets [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] within the record. As mentioned earlier, an offset [X, Y] represents all bits X through Y. 
     Method  400  of  FIG. 4 , as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) computing B i =S i −C for k fields, wherein C is a constant whole number (e.g., C=1)—step  402 ; (b) constructing a mask to extract values of k bits B 1 , B 2 , . . . , B k , wherein the mask comprises a bit vector M having 1s in bits at k bit positions, B 1 , B 2 , . . . , B k  having 0s in remainder of bits—step  404 ; (c) constructing a value vector containing the values of fields F 1 , F 2 , . . . F k , wherein the value vector comprises a bit vector V having the values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 0s in remainder of bits—step  406 ; (d) for each record, R, on which the predicates need to be applied, evaluating as follows: when F 1 , F 2 , . . . F k : F 1 ≦L 1  and F 2 ≦L 2  and F k ≦L k , evaluating ((V−R) AND M)=(V XOR R) AND M), or, when F 1 , F 2 , . . . F k : F 1 ≧L 1  and F 2 ≧L 2  and F k ≧L k , evaluating ((R−P) AND M)=(V XOR R) AND M), wherein the AND operator represents bit-wise AND of two bit vectors and the XOR operator represents bit-wise Exclusive OR of two bit vectors—step  408 ; and (e) outputting results of the evaluation operation in (d)—step  410 . 
     Variations of the method of  FIG. 4  are envisioned and are within the scope of the present invention. 
     For example, method  500  of  FIG. 5 , as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) computing B i =S i −C for k fields, wherein C is a constant whole number (e.g., C=1)—step  502 ; (b) constructing a mask to extract values of k bits B 1 , B 2 , . . . , B k , wherein the mask comprises a bit vector M having 1s in bits at k bit positions, B 1 , B 2 , . . . , B k  having 0s in remainder of bits—step  504 ; (c) constructing a value vector containing the values of fields F 1 , F 2 , . . . F k , wherein the value vector comprises a bit vector V having the values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 0s in remainder of bits—step  506 ; (d) for each record, R, on which the predicates need to be applied, evaluating (((V−R) XOR V XOR R) AND M)=0, wherein the AND operator represents bit-wise AND of two bit vectors and the XOR operator represents bit-wise Exclusive OR of two bit vectors—step  508 ; and (e) outputting results of the evaluation operation in (d)—step  510 . 
     As another example, method  600  of  FIG. 6 , as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) computing B i =S i −C for k fields, wherein C is a constant whole number (e.g., C=1)—step  602 ; (b) constructing a mask to extract values of k bits B 1 , B 2 , . . . , B k , wherein the mask comprises a bit vector M having 1s in bits at k bit positions, B 1 , B 2 , . . . , B k  having 0s in remainder of bits—step  604 ; (c) constructing a value vector containing the values of fields F 1 , F 2 , . . . F k , wherein the value vector comprises a bit vector V having the values L 1 , L 2  . . . L k  at bit positions [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively, and having 0s in remainder of bits—step  606 ; (d) for each record, R, on which the predicates need to be applied, evaluating ((V−R) XOR V XOR R) OR (NOT M)=(NOT M), wherein the AND operator represents bit-wise AND of two bit vectors and the XOR operator represents bit-wise Exclusive OR of two bit vectors—step  608 ; and (e) outputting results of the evaluation operation in (d)—step  610 . 
       FIG. 7  illustrates yet another variation in the method of the second embodiment.  FIG. 7  illustrates a computer based method to simultaneously evaluate conjunctions of one or more range or equality predicates on k fields F 1 , F 2 , . . . F k  of a record, where each predicate is one of four forms: (i) L i ≦F i  or (ii) F i ≦U i  or (iii) F i =L i  or (iv) L i ≦F i ≦U i , wherein L 1 , L 2  . . . L k  represent values, and the k fields are at offsets [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] of said record. 
     Method  700  of  FIG. 7 , as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) computing B i =S i −C for k fields, wherein C is a constant whole number (e.g., C=1)—step  702 ; (b) constructing a mask to extract values of k bits B 1 , B 2 , . . . , B k , wherein the mask comprises a bit vector M having 1s in bits at k bit positions, B 1 , B 2 , . . . , B k  having 0s in remainder of bits—step  704 ; (c) constructing a first value vector containing lower bound values, wherein the first value vector comprises a bit vector V L  having 0s everywhere except one or more of the following: L 1  at bit positions [S 1 , E 1 ], L 2  at bit positions [S 2 , E 2 ] . . . L k  at bit positions [S k , E k ]—step  706 ; (d) constructing a second value vector containing upper bound values, wherein the second value vector comprises a bit vector Vu having 1s everywhere except one or more of the following: U 1  at bit positions [S 1 , E 1 ], U 2  at bit positions [S 2 , E 2 ] . . . U k  at bit positions [S k , E k ]—step  708 ; (e) for each record, R, on which said predicates need to be applied, evaluating (((V U −R) XOR (R−V L )) AND M)=((V U  XOR V L ) AND M)—step  710 , wherein the AND operator represents bit-wise AND of two bit vectors and the XOR operator represents bit-wise Exclusive OR of two bit vectors; and (f) outputting results of said evaluation operation in (e)—step  712 . 
     In one example, the value of ((V U  XOR V L ) AND M) is pre-computed, such that only the remaining part of the expression (i.e., (((V U −R) XOR (R−V L )) AND M)) is evaluated on a per-record basis: using two subtractions, an XOR, a bit-wise ANDs and a bitwise comparison (all of which can be performed efficiently on most current processors using, for example, hardware instructions). 
     Variations of the method of  FIG. 7  are envisioned and are within the scope of the present invention. For example, method  800  of  FIG. 8 , as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) computing B i =S i −C for k fields, wherein C is a constant whole number (e.g., C=1)—step  802 ; (b) constructing a mask to extract values of k bits B 1 , B 2 , . . . , B k , wherein the mask comprises a bit vector M having 1s in bits at k bit positions, B 1 , B 2 , . . . , B k  having 0s in remainder of bits—step  804 ; (c) constructing a first value vector containing lower bound values, wherein the first value vector comprises a bit vector V L  having 0s everywhere except one or more of the following: L 1  at bit positions [S 1 , E 1 ], L 2  at bit positions [S 2 , E 2 ] . . . L k  at bit positions [S k , E k ]—step  806 ; (d) constructing a second value vector containing upper bound values, wherein the second value vector comprises a bit vector Vu having is everywhere except one or more of the following: U 1  at bit positions [S 1 , E 1 ], U 2  at bit positions [S 2 , E 2 ] . . . U k  at bit positions [S k , E k ]—step  808 ; (e) for each record, R, on which said predicates need to be applied, evaluating ((V U −R) XOR (R−V L ) XOR Vu XOR V L ) AND M=0—step  810 , wherein the AND operator represents bit-wise AND of two bit vectors and the XOR operator represents bit-wise Exclusive OR of two bit vectors; and (f) outputting results of said evaluation operation in (e)—step  812 . 
     Another variation of the method of  FIG. 7  is shown in  FIG. 9 . Method  900  of  FIG. 9 , as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) computing B i =S i −C for k fields, wherein C is a constant whole number (e.g., C=1)—step  902 ; (b) constructing a mask to extract values of k bits B 1 , B 2 , . . . B k , wherein the mask comprises a bit vector M having 1s in bits at k bit positions, B 1 , B 2 , . . . , B k  having 0s in remainder of bits—step  904 ; (c) constructing a first value vector containing lower bound values, wherein the first value vector comprises a bit vector V L  having 0s everywhere except one or more of the following: L 1  at bit positions [S 1 , E 1 ], L 2  at bit positions [S 2 , E 2 ] . . . L k  at bit positions [S k , E k ]—step  906 ; (d) constructing a second value vector containing upper bound values, wherein the second value vector comprises a bit vector Vu having 1s everywhere except one or more of the following: U 1  at bit positions [S 1 , E 1 ], U 2  at bit positions [S 2 , E 2 ] . . . U k  at bit positions [S k , E k ]—step  908 ; (e) for each record, R, on which said predicates need to be applied, evaluating ((V U −R) XOR (R−V L ) XOR V U  XOR V L ) OR (NOT M)=(NOT M)—step  910 , wherein the AND operator represents bit-wise AND of two bit vectors and the XOR operator represents bit-wise Exclusive OR of two bit vectors; and (f) outputting results of said evaluation operation in (e)—step  912 . 
     The benefit of the methods of the second embodiment is that computation done per record (a bitwise and an equality comparison) is efficiently done (with hardware or software instructions), and takes the same amount of time irrespective of k. This allows for very complex predicates to be evaluated quickly. 
     Embodiment 3 
     Applying a Mixture of In-List Predicates Simultaneously 
       FIG. 10  illustrates an example of the third embodiment&#39;s computer-based method to simultaneously evaluating conjunctions of a mixture of in-list predicates on k fields F 1 , F 2 , . . . F k  of the form F 1  in (L 11 , L 12  . . . L 1n ) and F 2  in (L 21 , L 22  . . . L 2n ) and . . . F k  in (L k1 , L k2  . . . L kn ), wherein the k fields are at offsets [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ]. 
     Method  1000  of  FIG. 10 , as implemented in computer readable program code stored in computer storage, comprises the steps of: (a) constructing a first mask to extract values of k fields, wherein the mask comprises a bit vector M having 1s in bits [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ] and having 0s in remainder of bits—step  1002 ; (b) constructing a second mask to extract most significant bit of each field, wherein the second mask comprises a bit vector S having 0s in bits S 1 , S 2 , . . . , S k  and having 1s in remainder of bits—step  1004 ; (c) for each 1 through n, computing a bit vector of values V 1 , V 2 , . . . , V n , wherein V i  has 0s in all bits except values L 1i , L 2i , . . . . L ki  at [S 1 , E 1 ], [S 2 , E 2 ] . . . [S k , E k ], respectively—step  1006 ; (d) for each record, R, on which said predicates need to be applied, evaluating n numbers as follows—step  1008 : 
     N 1 =((((V 1  XOR R) AND S)+S) OR (V XOR R)); 
     N 2 =((((V 2 XOR R) ANDS)+S) OR (V 2 XOR R)); . . . 
     N n =((((V n  XOR R) AND S)+S) OR (V XOR R)); 
     and then evaluating the following condition:
 
((N 1  AND N 2  AND . . . N n ) OR S)=S
 
wherein said AND operator represents bit-wise AND of two bit vectors, said XOR operator represents bit-wise Exclusive OR of two bit vectors, + represents subtraction, and OR represents bit-wise OR; and (e) outputting results of said evaluation operation in (d)—step  1010 .
 
     The benefit of the method of the third embodiment is that computation done per record (a bitwise and an equality comparison) is efficiently done (with hardware or software instructions), and takes the same amount of time irrespective of k. This allows for very complex predicates to be evaluated quickly. 
     In one example, the k fields F 1 , F 2 , . . . F k  described in the above-mentioned methods associated with embodiments 1 through 3 have a single codeword length. 
     In another example, evaluations described in the above-mentioned methods associated with embodiments 1 through 3 are computed exclusively via processor instructions. 
     In yet another example, the computer-based methods of embodiments 1 through 3 are used in constant-time query processing. 
     Additionally, the present invention provides for an article of manufacture comprising computer readable program code contained within implementing one or more modules to implement each of the above described methods of  FIGS. 1 through 10 . Furthermore, the present invention includes a computer program code-based product, which is a storage medium having program code stored therein which can be used to instruct a computer to perform any of the methods associated with the present invention. The computer storage medium includes any of, but is not limited to, the following: CD-ROM, DVD, magnetic tape, optical disc, hard drive, floppy disk, ferroelectric memory, flash memory, ferromagnetic memory, optical storage, charge coupled devices, magnetic or optical cards, smart cards, EEPROM, EPROM, RAM, ROM, DRAM, SRAM, SDRAM, or any other appropriate static or dynamic memory or data storage devices.