Lock-free creation of hash tables in parallel

摘要

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.