Back to results
US 8,135,738 B2Granted
Efficient predicate evaluation via in-list
AssigneeInternational Business Machines Corporation
InventorsLin Qiao, Vijayshankar Raman, Frederick Ralph Reiss, Richard S. Sidle, Garret Frederick Swart, F. Ryan Johnson
Life of this patent
Estimating the term…
Abstract
A predicate over a single column of a table is converted into at least one IN-list, wherein the IN-list is generated for a set of tuples of the column, and the generation is done over a data structure representing a set of distinct values of the column where the predicate applies and having a smaller cardinality than the table. The generated IN-list is evaluated over the set of tuples and the results of the evaluation are outputted as an evaluation of the predicate.
Claims20
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.
3 more elements
A computer program product comprising:
- a non-transitory computer usable medium having computer usable program code for evaluating a predicate, said computer program product including:
- computer usable program code converting 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;
- computer usable program code evaluating 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, extracting the value in the corresponding column and checking for containment in the above data structure;
- and
- computer usable program code outputting results of said evaluating said generated IN-list as an evaluation of said predicate.
4 more elements
A system comprising:
- a processor;
- and
- a non-transitory storage medium storing computer readable computer code executed by said processor to implement a method in a relational database comprising,
- wherein said processor executing computer readable program code stored in said non-transitory storage medium 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 computer readable program code stored in said non-transitory storage medium to evaluate said generated IN-list over said set of tuples, said evaluating further comprising the steps of:
- said processor executing computer readable program code to compute 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 computer readable program code stored in said non-transitory storage medium to extract the value in the corresponding column and checking for containment in the above data structure;
- and
- said processor executing computer readable program code stored in said non-transitory storage medium to output results of said evaluating said generated IN-list as an evaluation of said predicate.
6 more elements
Dependencies are inferred from the claim text.