Patent · US Active

Lock-free creation of hash tables in parallel

US9519668B2 · kind B2 · utility

2Cited by

1References

13Claims

0Family size

Assignee

International Business Machines Corporation · US

Inventors

Tim Kaldewey · Bala-Cynwyd, US
Guy M. Lohman · San Jose, US
Peter Völk · Dresden, DE

Key dates

Filing date	May 6, 2013
Grant date	Dec 13, 2016
Priority date	—
Expiry date	Feb 21, 2035

Classification

Technology area (CPC G)Physics
CPC primaryG06F16/2255
WIPO fieldComputer technology
WIPO sectorElectrical engineering

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.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.