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

• US 9,886,459 B2
• Filed: 07/22/2014
• Issued: 02/06/2018
• Est. Priority Date: 09/21/2013
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chavan, Shasank K., Watanaprakornkul, Phumpong
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US14/338,219
• Publication Number:
  US 20150088926A1
• Time in Patent Office: 1,295 Days
• Field of Search: 707769, 708209, 712 4, 345505
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 15/78 comprising a single central processing unit
• CPC Class Codes: G06F 15/8007 single instruction multiple data [SIMD] multiprocessors
• CPC Class Codes: G06F 15/8076 Details on data register access
• CPC Class Codes: G06F 15/8084 Special arrangements thereof, e.g. mask or switch
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

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

1. A method comprising:

receiving a query that references a database table, wherein;

the query has a predicate that specifies a search condition on a particular column of the database table;

the particular column of the database table has been encoded based on a dictionary;

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;

wherein the bit-vector that is copied into both the first subregister and the second subregister indicates which values, in the dictionary, satisfy the search condition;

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 the particular column in the 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;

wherein the first value by which the bits in the first subregister are shifted is different than the second value by which the bits in the second subregister are shifted;

after performing the shift operation;

determining whether the first column value satisfies the search condition based on a resulting shifted first bit in the single SIMD register at a particular position in the first subregister;

determining whether the second column value satisfies the search condition based on a resulting shifted second bit in the single SIMD register at the particular position in the second subregister; and

providing results to the query based on whether the first column value satisfies the search condition and whether the second column value satisfies the search condition.

2. The method of claim 1 wherein:

the database table comprises a plurality of rows, including the first row and the second row;

each value in the particular column is an index into the dictionary; and

each bit in the bit-vector corresponds to a unique value in the dictionary.

3. 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.

4. 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; and

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.

5. 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.

6. 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; and

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; and

wherein determining whether the second row satisfies the search condition based on the second output bit.

7. A non-transitory computer-readable medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform steps comprising:

receiving a query that references a database table, wherein;

the query has a predicate that specifies a search condition on a particular column of the database table;

the particular column of the database table has been encoded based on a dictionary;

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;

wherein the bit-vector that is copied into both the first subregister and the second subregister indicates which values, in the dictionary, satisfy the search condition;

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 the particular column in the 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;

wherein the first value by which the bits in the first subregister are shifted is different than the second value by which the bits in the second subregister are shifted;

after performing the shift operation;

determining whether the first column value satisfies the search condition based on a resulting shifted first bit in the single SIMD register at a particular position in the first subregister;

determining whether the second column value satisfies the search condition based on a resulting shifted second bit in the single SIMD register at the particular position in the second subregister; and

providing results to the query based on whether the first column value satisfies the search condition and whether the second column value satisfies the search condition.

8. The non-transitory computer-readable medium of claim 7, wherein:

the database table comprises a plurality of rows, including the first row and the second row;

each value in the particular column is an index into the dictionary; and

each bit in the bit-vector corresponds to a unique value in the dictionary.

9. The non-transitory computer-readable medium of claim 8, further comprising instructions for 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.

10. The non-transitory computer-readable medium of claim 7, wherein the single SIMD register is a first single SIMD register, and further comprising instructions for:

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; and

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.

11. The non-transitory computer-readable medium of claim 7, wherein the single SIMD register is a first single SIMD register, and further comprising instructions for:

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.

12. The non-transitory computer-readable medium of claim 7, comprising instructions for:

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; and

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; and

wherein determining whether the second row satisfies the search condition based on the second output bit.

13. A hardware processor configured to:

receive a query that references a database table, wherein;

the query has a predicate that specifies a search condition on a particular column of the database table;

the particular column of the database table has been encoded based on a dictionary;

copy 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;

wherein the bit-vector that is copied into both the first subregister and the second subregister indicates which values, in the dictionary, satisfy the search condition;

perform 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 the particular column in the 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;

wherein the first value by which the bits in the first subregister are shifted is different than the second value by which the bits in the second subregister are shifted;

after performing the shift operation;

determine whether the first column value satisfies the search condition based on a resulting shifted first bit in the single SIMD register at a particular position in the first subregister;

determine whether the second column value satisfies the search condition based on a resulting shifted second bit in the single SIMD register at the particular position in the second subregister; and

providing results to the query based on whether the first column value satisfies the search condition and whether the second column value satisfies the search condition.

14. The hardware processor of claim 13 wherein:

the database table comprises a plurality of rows, including the first row and the second row;

each value in the particular column is an index into the dictionary; and

each bit in the bit-vector corresponds to a unique value in the dictionary.

15. The hardware processor of claim 14 further configured to construct 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.

16. The hardware processor of claim 13, wherein the single SIMD register is a first single SIMD register, and the processor is further configured to:

copy 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;

multiply each value in the third subregister and the fourth subregister by a first power of two and a second power of two, respectively; and

shift 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.

17. The hardware processor of claim 13, wherein the single SIMD register is a first single SIMD register, and the processor further is configured to:

copy 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;

shift bits in the third subregister such that bits representing the first value are aligned with the third subregister; and

shift bits in the fourth subregister such that bits representing the second value are aligned with the fourth subregister; and

set bits that do not represent the first value in the third subregister to zero; and

set bits that do not represent the second value in the fourth subregister to zero.

18. The hardware processor of claim 13 further configured to:

set 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; and

set 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; and

wherein determining whether the second row satisfies the search condition based on the second output bit.