Reducing collisions within a hash table

• US 9,317,548 B2
• Filed: 01/30/2013
• Issued: 04/19/2016
• Est. Priority Date: 01/30/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Attaluri, Gopi K., Raman, Vijayshankar
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US13/753,769
• Publication Number:
  US 20140214855A1
• Time in Patent Office: 1,175 Days
• Field of Search: 707/698
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof

Abstract

Collisions in hash tables are reduced by removing each empty bucket from a hash table and compacting the non-empty buckets, generating a map of the hash table indicating a status of the buckets of the hash table, and accessing data in the hash table by applying a hash key to the generated map to determine a corresponding bucket containing the data.

Claims

1. An apparatus comprising:

a processor including;

a hash table compacting module configured to remove each empty bucket from a hash table and to compact the non-empty buckets;

a hash table map generating module configured to generate a map of the hash table indicating a status of the buckets of the hash table; and

a data access module configured to access data in the hash table by applying a hash key to the generated map to determine a corresponding bucket containing the data, wherein each bucket present in the hash table includes an attribute indicating one of a corresponding hash value and a pointer to a next bucket for the same hash value.

2. The apparatus according to claim 1, wherein values that are likely to be frequently looked up are inserted within the hash table prior to values that are likely to be infrequently looked up in the hash table.

3. The apparatus according to claim 1, wherein the hash table is utilized for a join operation for data within a first database table and a second database table, and wherein the rows of the first database table are partitioned based on frequencies and hash values of values to be joined and generating a hash table for each partition.

4. The apparatus according to claim 1, wherein payload data of the hash table is stored separately from the hash table and the buckets of the hash table include pointers to the payload data for the hash table.

5. A computer program product comprising:

a non-transitory computer readable storage medium encoded with instructions that, when executed by a processor, cause the processor to reduce collisions in hash tables by performing the functions of;

removing each empty bucket from a hash table and compacting the non-empty buckets;

generating a map of the hash table indicating a status of the buckets of the hash table; and

accessing data in the hash table by applying a hash key to the generated map to determine a corresponding bucket containing the data, wherein accessing further comprises;

applying the hash key to the generated map to determine a corresponding position in the generated map;

computing a population count in the generated map, of all positions in the generated map up to the determined corresponding position; and

using the computed population count as a bucket position of the corresponding bucket containing the data.

6. The computer program product according to claim 5, wherein the processor further performs the functions of:

precomputing a prefix population count at particular boundaries in the generated map.

7. The computer program product according to claim 6, wherein each prefix population count is stored collocated with corresponding entries of the generated map.

8. The computer program product according to claim 5, wherein each bucket present in the hash table includes an attribute indicating one of a corresponding hash value and a pointer to a next bucket for the same hash value.

9. The computer program product according to claim 5, wherein the hash table is utilized for a join operation for data within a first database object and a second database object, and wherein frequent values of the second database object for the join operation are inserted within the hash table prior to infrequent values for the join.

10. The computer program product according to claim 5, wherein the hash table is utilized for a join operation for data within a first database table and a second database table, and wherein the processor further performs the functions of:

partitioning rows of the first database table based on frequencies and hash values of values to be joined and generating a hash table for each partition.

11. The computer program product according to claim 5, wherein payload data of the hash table is stored separately from the hash table and the buckets of the hash table include pointers to the payload data for the hash table.

12. An apparatus comprising:

a processor including;

a hash table compacting module configured to remove each empty bucket from a hash table and to compact the non-empty buckets;

a hash table map generating module configured to generate a map of the hash table indicating a status of the buckets of the hash table; and

a data access module configured to access data in the hash table by applying a hash key to the generated map to determine a corresponding bucket containing the data, wherein accessing further comprises;

applying the hash key to the generated map to determine a corresponding position in the generated map;

computing a population count in the generated map, of all positions in the generated map up to the determined corresponding position; and

using the computed population count as a bucket position of the corresponding bucket containing the data.

13. The apparatus according to claim 12, wherein the processor further performs the functions of:

precomputing a prefix population count at particular boundaries in the generated map.

14. The apparatus according to claim 13, wherein each prefix population count is stored collocated with corresponding entries of the generated map.

15. The apparatus according to claim 12, wherein each bucket present in the hash table includes an attribute indicating one of a corresponding hash value and a pointer to a next bucket for the same hash value.

16. The apparatus according to claim 12, wherein the hash table is utilized for a join operation for data within a first database object and a second database object, and wherein frequent values of the second database object for the join operation are inserted within the hash table prior to infrequent values for the join.

17. The apparatus according to claim 12, wherein the hash table is utilized for a join operation for data within a first database table and a second database table, and wherein the processor further performs the functions of:

partitioning rows of the first database table based on frequencies and hash values of values to be joined and generating a hash table for each partition.

18. The apparatus according to claim 12, wherein payload data of the hash table is stored separately from the hash table and the buckets of the hash table include pointers to the payload data for the hash table.