Methods and systems for fast set-membership tests using one or more processors that support single instruction multiple data instructions

A method comprising:

• copying a first value into a first subregister and a second value into a second subregister;
• wherein the first subregister and the second subregister are subregisters in a first single SIMD register;
• wherein the first value corresponds with a first column value in a first row of a particular column of a database table, and the second value corresponds with a second column value in a second row of the particular column of the database table;
• gathering a first bit from an input bit-vector and a second bit from the input bit-vector based on the first value in the first subregister and the second value in the second subregister, respectively;
• determining whether the first column value satisfies a search condition based on the first bit and whether the second column value satisfies the search condition based on the second bit.

A processor comprising:

• a plurality of SIMD registers, including a particular SIMD register;
• wherein the particular SIMD register is capable of storing a particular maximum number of bits;
• wherein the processor is configured to:
• determine a cardinality for a column of a database table, wherein the cardinality of the column is how many unique values are in the column;
• determine whether the cardinality multiplied by a coefficient is greater than the particular maximum number of bits;
• in response to determining the cardinality multiplied by the coefficient is not greater than the particular maximum number of bits, the processor is configured to perform a first set-membership method;
• and
• in response to determining the cardinality multiplied by the coefficient is greater the particular maximum number of bits, the processor is configured to perform a second set-membership method.

A method comprising:

• copying a bit-vector into a first subregister and a second subregister;
• wherein each bit in the bit-vector corresponds with a value in a first set of values;
• wherein the first subregister and the second subregister are subregisters in a single SIMD register;
• performing a shift operation that:
• shifts bits in the first subregister by a first value in a second set of values, and
• shifts bits in the second subregister by a second value in the second set of values;
• after performing the shift operation:
• determining whether the first value is in the first set of values based on a first bit at a particular position in the first subregister;
• and
• determining whether the second value is in the first set of values based on a second bit in the single SIMD register at the particular position in the second subregister.