Parallel build of non-partitioned join hash tables and non-enforced N:1 join hash tables

• US 9,922,064 B2
• Filed: 03/20/2015
• Issued: 03/20/2018
• Est. Priority Date: 03/20/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Attaluri, Gopi K., Barber, Ronald J., Pandis, Ippokratis, Raman, Vijayshankar
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US14/664,710
• Publication Number:
  US 20160275078A1
• Time in Patent Office: 1,096 Days
• Field of Search: 707600-899
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

A method for building a hash table over a subset of data in a data set includes mapping keys in the data set to values in the data set using multiple parallel computation threads. Each thread scans a subset of the keys and values and partitioning the subset of the keys and values into multiple partitions. A cumulative count for keys and values in each partition is determined. A hash table with space reserved for each partition is formed based on the determined cumulative counts. Each thread selects one or more partitions and inserts keys and values belonging to the selected one or more partitions into the hash table in the reserved space for those partitions.

Claims

1. A method for building a hash table over a subset of data in a data set comprising:

mapping keys in the data set to values in the data set using multiple parallel computation threads;

each thread scanning a subset of the keys and values and partitioning the subset of the keys and values into a plurality of partitions;

determining a cumulative count for a number of keys and values in each partition;

forming a hash table with space reserved for each partition based on the determined cumulative counts;

each thread selecting one or more partitions and inserting keys and values belonging to the selected one or more partitions into the hash table in the reserved space for those partitions; and

creating a compact hash table comprising a bitmap and a compacted array.

2. The method of claim 1, wherein the data set comprises an input to a join operation, and partitioning the subset of keys and values is performed using bits of a hash value computed on a column used in a join predicate.

3. The method of claim 1, wherein determining the cumulative count for keys and values in each partition comprises each thread exchanging, with other threads, a number of keys in each partition in its subset, and summing a number of keys received for each partition from each of the other threads to determine the number of keys for each of the partitions, and summing the number of keys for each of the partitions for determining the cumulative count.

4. The method of claim 3, wherein each thread takes ownership of one or more partitions and builds a sub-range of the hash table for that partition, and the sub-range comprises a sub-range of an array holding keys and payloads and starts at a position indicated by the cumulative count of the partitions up to and excluding a current partition being built, and extends to a length equal to a number of keys in the current partition.

5. The method of claim 1, wherein creating the compact hash table comprises:

scanning the subset of the keys, and for each key, performing a hash operation and inserting hashed keys into the bitmap;

determining cumulative population counts for keys and values within the bitmap;

repeating scanning of the subset of the keys and values; and

inserting the keys and values into the compacted array using the cumulative population counts.

6. The method of claim 5, wherein duplicate keys are treated as a hash collision until a collision chain length reaches a predetermined threshold, and then tracking of keys is performed.

7. The method of claim 6, wherein tracking of keys comprises:

inserting the duplicate keys in a local data structure; and

using the local data structure for detecting and eliminating frequent duplicate keys, wherein un-detected keys in the local data structure are treated as collisions and placed in the bitmap.

8. The method of claim 6, wherein tracking of keys comprises:

placing the duplicate keys into an overflow hash table.

9. The method of claim 5, wherein duplicate keys are marked for avoidance of returning the marked duplicate keys as join matches and avoiding copying the marked duplicate keys into the hash table.

10. A computer program product for building a hash table over a subset of data in a data set, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

map, by the processor, hash keys in the data set to values in the data set using multiple parallel computation threads;

scan, by each thread, a subset of the keys and values and partitions the subset of the keys and values into a plurality of partitions;

determine, by the processor, a cumulative count for a number of keys and values in each partition;

form, by the processor, a hash table with space reserved for each partition based on the determined cumulative counts;

select, by each thread, one or more partitions and inserts its keys and values into the hash table in the reserved space for those partitions; and

create, by the processor, a compact hash table comprising a bit a and a compacted array.

11. The computer program product of claim 10, wherein:

the data set comprises an input to a join operation;

partitioning the subset of the keys and values is performed using bits of a hash value computed on a column used in a join predicate; and

the cumulative count for keys and values in each partition is determined based on each thread exchanging, with other threads, a number of keys in each partition in its subset, and summing a number of keys received for each partition from each of the other threads to determine the number of keys for each of the partitions, and summing the number of keys for each of the partitions for determining the cumulative count.

12. The computer program product of claim 11, wherein each thread takes ownership of one or more partitions and builds a sub-range of the hash table for that partition, wherein the sub-range comprises a sub-range of an array holding keys and payloads and starts at a position indicated by the cumulative count of the partitions up to a current and excluding a current partition being built, and extends to a length equal to a number of keys in the current partition.

13. The computer program product of claim 10, wherein the compact hash table is created by:

scanning the subset of the keys, and for each key, performing a hash operation and inserting hashed keys into the bitmap;

determining cumulative population counts of keys and values within the bitmap;

repeating scanning of the subset of the keys and values; and

inserting the keys and values into the compacted array using the cumulative population counts,

wherein duplicate keys are treated as a hash collision until a collision chain length reaches a predetermined threshold, and then tracking of keys is performed.

14. The computer program product of claim 13, wherein tracking of keys comprises:

inserting the duplicate keys in a local data structure; and

using the local data structure for detecting and eliminating frequent duplicate keys, wherein un-detected keys in the local data structure are treated as collisions and placed in the bitmap.

15. The computer program product of claim 13, wherein tracking of keys comprises:

placing the duplicate keys into an overflow hash table, wherein duplicate keys are marked for avoidance of returning the marked duplicate keys as join matches and avoiding copying the marked duplicate keys into the hash table.