Patent Document ID: 8135738
Application ID: 12195035
Patent Status: 1

Claim One:
1. A computer-based method as implemented in a relational database, said method implemented by a processor by executing instructions stored in a computer storage, said computer-based method implemented by processor comprising: said processor executing instructions to convert a predicate over a single column associated with a table into at least one IN-list, said IN-list comprising values of said column where said predicate applies and said IN-list generated for a set of tuples of said column, wherein generation of said IN-list is done over a data structure representing a set of distinct values of said column; said processor executing instructions to evaluate said generated IN-list over said set of tuples, said evaluating further comprising the steps of: computing a data density in an IN-list as number of values in an IN-list divided by a max value-min value of that IN-list, and if the density>1/C, where C is a constant factor that is proportional to a number of bits used for storing a value from a domain of said column, the values are stored as a bitmap implemented as an array of integers, else a perfect hash table is generated containing all the items in the IN-list with a space which is equal to C/2 multiplied by a number of entries bits multiplied by 2; and for each tuple, said processor executing instructions to extract the value in the corresponding column and checking for containment in the above data structure; and said processor executing instructions to output results of said evaluating said generated IN-list as an evaluation of said predicate.