Lock-free creation of hash tables in parallel
View Patent ↗A hash table is created in parallel without requiring a lock or random accesses to memory. The hash table of a database system is logically partitioned and a separate thread is assigned to each partition of the hash table. As many separate threads as can fit their corresponding hash table partitions into the processor's cache are executed in parallel with other threads without a lock. Execution of a number of separate threads includes: scanning an input data table for a thread's partition and applying a hash function to each key, inserting data of keys that hash to the thread's partition into the thread's partition, and ignoring keys that do not hash to the thread's partition.
1. A method of lock-free creation of partitioned hash tables in parallel for an input data table, comprising:
partitioning a hash table of a database system;
assigning a separate thread to each partition of the hash table; and
executing a number of the separate threads in parallel with other threads without a lock, the executing comprising for each of said number:
scanning the input data table and applying a hash function to each key in the input data table; and
in response to the scanning:
inserting data of keys that hash to the thread's partition into the thread's partition of the hash table; and
ignoring keys that do not hash to the thread's partition,
wherein an index is created for active buckets of the partition such that inactive buckets of the partition are no longer referenced and are automatically flushed to main memory, and
wherein overflow data, in the partition, are stored in separate overflow buckets to be processed by another thread.
2. The method of claim 1 , wherein the scanning of the input data table results in strictly sequential memory accesses.
3. The method of claim 1 , wherein the contents of the thread's partition are flushed to main memory in response to completing the executed thread.
4. The method of claim 1 , wherein each partition size is less than or equal to a cache size of the processing device.
5. The method of claim 1 , wherein an input queue is provided for each partition, enabling a thread processing of a preceding partition to add overflow data to a subsequent input queue.
6. A database system of lock-free creation of partitioned hash tables in parallel, comprising:
a memory having computer readable instructions; and a processor for executing the computer readable instructions, the instructions comprising:
partitioning a hash table of a database system;
assigning a separate thread to each partition of the hash table; and
executing a number of the separate threads in parallel with other threads without a lock, the executing comprising for each of said number:
scanning an input data table and applying a hash function to each key in the input data table; and
in response to the scanning:
inserting data of keys that hash to the thread's partition into the thread's partition of the hash table; and
ignoring keys that do not hash to the thread's partition,
wherein an index is created for active buckets of the partition such that inactive buckets of the partition are no longer referenced and are automatically flushed to main memory, and
wherein overflow data, in the partition, are stored in separate overflow buckets to be processed by another thread.
7. The database system of claim 6 , wherein the scanning of the input data table results in strictly sequential memory accesses.
8. The database system of claim 6 , wherein contents of the thread's partition are flushed to main memory in response to completing the executed thread.
9. The database system of claim 6 , wherein each partition size is less than or equal to a cache size of the processor.
10. The database system of claim 6 , wherein an input queue is provided for each partition, enabling a thread processing of a preceding partition to add overflow data to a subsequent input queue.
11. A computer program product for lock-free creation of partitioned hash tables in parallel for an input data table, the computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by a processor to:
partition a hash table of a database system;
assign a separate thread to each partition of the hash table; and
execute a number of the separate threads in parallel with other threads without a lock, the executing comprising for each of said number:
scanning the input data table and applying a hash function to each key in the input data table; and
in response to the scanning:
inserting data of keys that hash to the thread's partition into the thread's partition of the hash table; and
ignoring keys that do not hash to the thread's partition,
wherein an index is created for active buckets of the partition such that inactive buckets of the partition are no longer referenced and are automatically flushed to main memory, and
wherein overflow data, in the partition, are stored in separate overflow buckets to be processed by another thread.
12. The computer program product of claim 11 , wherein the scanning of the input data table results in strictly sequential memory accesses.
13. The computer program product of claim 11 , wherein the contents of the thread's partition are flushed to main memory in response to completing the executed thread.