# US 2015/0088926 A1 · Methods and systems for fast set-membership tests using one or more processors that support single instruction multiple data instructions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2015/0088926 A1 - Document ID: US20150088926A1 - Status: Published application - Kind: A1 - Application number: 14/338,219 - Filed: 2014-07-22 - Published: 2015-03-26 - Earliest claimed: 2013-09-21 - Assignees: Oracle International Corporation - Applicants: Oracle International Corporation - Inventors: SHASANK K. CHAVAN; PHUMPONG WATANAPRAKORNKUL - Web page: https://patentgrep.com/patent/US20150088926A1 ## CPC - G06F 16/221: {Column-oriented storage; Management thereof} - G06F 3/0604: {Improving or facilitating administration, e.g. storage management} - G06F 3/064: {Management of blocks} - G06F 3/065: {Replication mechanisms} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06F 12/0815: Cache consistency protocols - G06F 12/1018: involving hashing techniques, e.g. inverted page tables - G06F 15/78: comprising a single central processing unit - G06F 15/8007: {single instruction multiple data [SIMD] multiprocessors} - G06F 15/8076: {Details on data register access} - G06F 15/8084: {Special arrangements thereof, e.g. mask or switch} - G06F 16/22: Indexing; Data structures therefor; Storage structures - G06F 16/2379: {Updates performed during online database operations; commit processing} - G06F 16/2455: Query execution - G06F 16/284: {Relational databases} - G06F 2212/1021: Hit rate improvement - G06F 2212/1032: Reliability improvement, data loss prevention, degraded operation etc - G06F 2212/2542: Non-uniform memory access [NUMA] architecture - G06F 2212/313: In storage device - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods and apparatuses for determining set-membership using Single Instruction Multiple Data (“SIMD”) architecture are presented herein. Specifically, methods and apparatuses are discussed for determining, in parallel, whether multiple values in a first set of values are members of a second set of values. Many of the methods and systems discussed herein are applied to determining whether one or more rows in a dictionary-encoded column of a database table satisfy one or more conditions based on the dictionary-encoded column. However, the methods and systems discussed herein may apply to many applications executed on a SIMD processor using set-membership tests. ## Claims ### Claim 1 A method comprising: copying a bit-vector into a first subregister and a second subregister, 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 that corresponds with a first column value in a first row of a particular column in a database table, and shifts bits in the second subregister by a second value that corresponds with a second column value in a second row of the particular column in the database table; after performing the shift operation: determining whether the first column value satisfies a search condition based on a first bit at a particular position in the first subregister; and determining whether the second column value satisfies the search condition based on a second bit in the single SIMD register at the particular position in the second subregister. ### Claim 2 (depends on 1) The method of claim 1 further comprising receiving a query that references the database table, wherein: the query has a predicate that specifies the search condition; the database table comprises a plurality of rows, including the first row and the second row; each value in the particular column corresponds to an index in a dictionary; and each bit in the bit-vector corresponds to a unique value in the dictionary. ### Claim 3 (depends on 2) The method of claim 2 further comprising constructing the bit-vector by performing the following steps for each bit in the bit-vector: setting the bit to one if the unique value that corresponds to the bit satisfies the predicate; and setting the bit to zero if the unique value that corresponds to the bit does not satisfy the predicate. ### Claim 4 (depends on 1) The method of claim 1, wherein the single SIMD register is a first single SIMD register, and further comprising: copying the first value into a third subregister and the second value into a fourth subregister, wherein the third subregister and the fourth subregister are subregisters in a second single SIMD register; multiplying each value in the third subregister and the fourth subregister by a first power of two and a second power of two, respectively; shifting bits in the third subregister and the fourth subregister such that the first value is aligned with the third subregister and the second value is aligned with the fourth subregister. ### Claim 5 (depends on 1) The method of claim 1, wherein the single SIMD register is a first single SIMD register, and further comprising: copying the first value into a third subregister and the second value into a fourth subregister, wherein the third subregister and the fourth subregister are subregisters in a second single SIMD register; shifting bits in the third subregister such that bits representing the first value are aligned with the third subregister; and shifting bits in the fourth subregister such that bits representing the second value are aligned with the fourth subregister; and setting bits that do not represent the first value in the third subregister to zero; and setting bits that do not represent the second value in the fourth subregister to zero. ### Claim 6 (depends on 1) The method of claim 1 comprising: setting a first output bit in an output bit-vector to the first bit in the single SIMD register at the particular position in the first subregister, wherein each bit in the output bit-vector corresponds to a row in the database table and the first output bit corresponds with the first row in the database table; setting a second output bit in the output bit-vector to the second bit in the single SIMD register at the particular position in the second subregister, wherein the second output bit corresponds with the second row in the database table; wherein determining whether the first row satisfies the search condition based on the first output bit; wherein determining whether the second row satisfies the search condition based on the second output bit. ### Claim 7 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. ### Claim 8 (depends on 7) The method of claim 7 comprising: storing a first byte-offset in a third subregister and a second byte-offset in a fourth subregister, wherein the third subregister and the fourth subregister are in a second single SIMD register; storing a first bit-offset in a fifth subregister and a second bit-offset in a sixth subregister, wherein the fifth subregister and the sixth subregister are in a third single SIMD register; wherein gathering the first bit and the second bit comprises: gathering a first byte from the input bit-vector into a seventh subregister based on the first byte-offset and a second byte from the input bit-vector into an eighth subregister based on the second byte-offset, wherein the seventh subregister and the eighth subregister are in a fourth single SIMD register; and shifting bits in the seventh subregister by the first bit-offset and bits in the eighth subregister by the second bit-offset. ### Claim 9 (depends on 8) The method of claim 8, wherein gathering the first bit and the second bit comprises copying the first bit from the seventh subregister and the second bit from the eighth subregister in an output bit-vector using a bit-mask. ### Claim 10 (depends on 8) The method of claim 8, wherein: wherein determining whether the first column value satisfies the search condition and whether the second column value satisfies the search condition comprises: determining whether the first column value satisfies the search condition based on the first bit, which is stored at a particular position in the seventh subregister; and determining whether the second column value satisfies the search condition based on the second bit, which is stored at the particular position in the eighth subregister. ### Claim 11 (depends on 8) The method of claim 8 comprising: determining a first quotient by dividing the first value, stored the first subregister, by eight; determining a second quotient by dividing the second value, stored the second subregister, by eight; and storing the first byte-offset in the third subregister and the second byte-offset in the fourth subregister comprises: storing the first quotient as the first byte-offset in the third subregister; and storing the second quotient as the second byte-offset in the fourth subregister. ### Claim 12 (depends on 8) The method of claim 8 comprising: determining a first remainder by dividing the first value, stored the first subregister, by eight; determining a second remainder by dividing the second value, stored the second subregister, by eight; and wherein storing the first bit-offset in the fifth subregister and the second bit-offset in the sixth subregister comprises: storing the first remainder as the first bit-offset in the fifth subregister; and storing the second remainder as the second bit-offset in the sixth subregister. ### Claim 13 (depends on 8) The method of claim 8 wherein gathering the first byte from the input bit-vector into the seventh subregister is performed in parallel with gathering the second byte from the input bit-vector into the eighth subregister. ### Claim 14 (depends on 8) The method of claim 8, wherein: gathering the first bit and the second bit further comprises: setting a first output bit in an output bit-vector to the first bit in the seventh subregister, wherein each bit in the output bit-vector corresponds to a row in the database table and the first output bit corresponds with the first row in the database table; setting a second output bit in the output bit-vector to the second bit in the eighth subregister, wherein the second output bit corresponds with the second row in the database table; determining whether the first row satisfies the search condition is based on the first output bit; determining whether the second row satisfies the search condition is based on the second output bit. ### Claim 15 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. ### Claim 16 (depends on 15) The processor of claim 15, wherein the first set-membership method is a low-cardinality set-membership method for processing multiple values in parallel. ### Claim 17 (depends on 15) The processor of claim 15, wherein the first set-membership method is a high-cardinality set-membership method for processing multiple values in parallel. ### Claim 18 (depends on 15) The processor of claim 15, wherein the coefficient is a power of two. ### Claim 19 (depends on 15) The processor of claim 15, wherein: the column is a first column in the database table; the cardinality is a first cardinality; and the processor is further configured to: receive a query with a first condition and a second condition, wherein the first condition is based on the first column and the second condition is based on a second column in the database table; perform the first set-membership method based on determining the first cardinality for the first column is low; determine a second cardinality for the second column; perform the second set-membership method based on determining the second cardinality for the first column is high. ### Claim 20 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.