# US 9,519,668 B2 · Lock-free creation of hash tables in parallel

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,519,668 B2
- Document ID: US9519668B2
- Status: Granted
- Kind: B2
- Application number: 13/887,422
- Filed: 2013-05-06
- Published: 2014-11-06
- Granted: 2016-12-13
- Earliest claimed: 2013-05-06
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Tim Kaldewey; Guy M. Lohman; Peter B. Volk
- Web page: https://patentgrep.com/patent/US9519668B2

## CPC

- G06F 16/2255: {Hash tables}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

The method of claim 1, wherein the scanning of the input data table results in strictly sequential memory accesses.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

The method of claim 1, wherein each partition size is less than or equal to a cache size of the processing device.

### Claim 5 (depends on 1)

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.

### Claim 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.

### Claim 7 (depends on 6)

The database system of claim 6, wherein the scanning of the input data table results in strictly sequential memory accesses.

### Claim 8 (depends on 6)

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.

### Claim 9 (depends on 6)

The database system of claim 6, wherein each partition size is less than or equal to a cache size of the processor.

### Claim 10 (depends on 6)

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.

### Claim 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.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein the scanning of the input data table results in strictly sequential memory accesses.

### Claim 13 (depends on 11)

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.