Applying various hash methods used in conjunction with a query with a group by clause

• US 8,108,401 B2
• Filed: 03/28/2008
• Issued: 01/31/2012
• Est. Priority Date: 03/28/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Qiao, Lin, Raman, Vijayshankar, Swart, Garret Frederick
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Rahman, Sabana
• Application Number:
  US12/057,979
• Publication Number:
  US 20090249023A1
• Time in Patent Office: 1,404 Days
• Field of Search: 711/216, 707/769, 395/600
• US Class Current: 707/747
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

A novel method is described for applying various hash methods used in conjunction with a query with a Group By clause. A plurality of drawers are identified, wherein each of the drawers is made up of a collection of cells from a single partition of a Group By column and each of the drawers being defined for a specific query. A separate hash table is independently computed for each of the drawers and a hashing scheme (picked from among a plurality of hashing schemes) is independently applied for each of the drawers.

Claims

1. A computer-based method to apply a plurality of hash methods in a query with a Group By clause comprising:

identifying a plurality of cells, each of said cells representing a combination of disparate attribute partitions, said disparate attribute partitions formed based on partitioning a set of attribute values of each attribute among a plurality of attributes of a database, and said disparate partitions belonging to different attributes of said database;

identifying a plurality of drawers, each of said drawers comprising a collection of cells from a single partition of a Group By column, and each of said drawers being defined for a specific query;

independently computing a separate hash table for each of said drawers; and

independently applying a hashing scheme picked from among a plurality of hashing schemes for each of said drawers, wherein, said hashing scheme is picked according to the number of distinct groups in said given drawer, said number of distinct groups estimated from a dictionary, said hashing scheme is picked from said plurality of hashing schemes as follows;

for single column Group Bys, using a hashing scheme that uses group codes as an index to said given drawer'"'"'s hash table;

for correlated Group Bys, using a pre-computed minimal perfect hash function, said pre-computed minimal perfect hash function having as many buckets as number of groups in said given drawer; and

otherwise, using a linear probing hashing scheme using multiplicative hashing as a hashing function,

wherein when said linear probing hashing scheme is picked, said method comprising the step of filling a hash table associated with said give drawer up to a predetermined load factor.

2. The computer-based method of claim 1, wherein said pre-computed minimal perfect hash function is constructed by computer readable program code during extract-transform-load operations.

3. The computer-based method of claim 1, wherein, when said pre-computed minimal perfect hash function is used, computer readable program code maintains an auxiliary table for computing hash values.

4. The computer-based method claim 1, wherein when said load factor is about 60%.

5. The computer-based method claim 1, wherein said liner probing technique is picked only as a fall-back for correlated multi-column Group Bys when said minimal perfect hash function is not pre-computed.

6. An article of manufacture comprising a non-transitory computer usable storage medium having computer readable program code embodied therein which implements a computer-based method for applying a plurality of hash methods in query with a Group By clause, said computer usable medium comprising:

computer readable program code identifying a plurality of cells, each of said cells representing a combination of disparate attribute partitions, said disparate attribute partitions formed based on partitioning a set of attribute values of each attribute among a plurality of attributes of a database, and said disparate partitions belonging to different attributes of said database;

computer readable program code identifying a plurality of drawers, each of said drawers comprising a collection of cells from a single partition of a Group By column, and each of said drawers being defined for a specific query;

computer readable program code independently computing a separate hash table for each of said drawers; and

computer readable program code independently applying a hashing scheme picked from among a plurality of hashing schemes for each of said drawers wherein, said hashing scheme is picked according to the number of distinct groups in said given drawer, said number of distinct groups estimated from a dictionary, said hashing scheme is picked from said plurality of hashing schemes as follows;

for single column Group Bys, using a hashing scheme that uses group codes as an index to said given drawer'"'"'s hash table;

for correlated Group Bys, using a pre-computed minimal perfect hash function, said pre-computed minimal perfect hash function having as many buckets as number of groups in said given drawer; and

otherwise, using a linear probing hashing scheme using multiplicative hashing as a hashing function,

wherein when said linear probing hashing scheme is picked, said method comprising the step of filling a hash table associated with said give drawer up to a predetermined load factor.

7. The article of manufacture of claim 6, wherein said pre-computed minimal perfect hash function is constructed by computer readable program code during extract-transform-load operations.

8. The article of manufacture of claim 6, wherein, when said pre-computed minimal perfect hash function is used, computer readable program code maintains an auxiliary table for computing hash values.

9. The article of manufacture of claim 6, wherein when said load factor is about 60%.

10. The article of manufacture of claim 6, wherein computer readable program code picks said linear probing technique only as a fall-back for correlated multi-column Group Bys when said minimal perfect hash function is not pre-computed.

11. A computer-based method to apply a plurality of hash methods in a query with a Group By clause comprising:

identifying a plurality of cells, each of said cells representing a combination of disparate attribute partitions, said disparate attribute partitions formed based on partitioning a set of attribute values of each attribute among a plurality of attributes of a database, and said disparate partitions belonging to different attributes of said database;

identifying a plurality of drawers, each of said drawers comprising a collection of cells from a single partition of a Group By column, and each of said drawers being defined for a specific query;

independently computing a separate hash table for each of said drawers;

independently applying any of the following hashing schemes;

for single column Group Bys, using a hashing scheme that uses group codes as an index to said given drawer'"'"'s hash table;

for correlated Group Bys, using a pre-computed minimal perfect hash function, said pre-computed minimal perfect hash function having as many buckets as number of groups in said given drawer; and

otherwise, using a linear probing hashing scheme using multiplicative hashing as a hashing function,

wherein when said linear probing hashing scheme is picked, said method comprising the step of filling a hash table associated with said give drawer up to a predetermined load factor; and

wherein, for a given drawer, a hashing scheme is picked according to the number of distinct groups in said given drawer, said number of distinct groups estimated from a dictionary.

12. The computer-based method of claim 11, wherein said pre-computed minimal perfect hash function is constructed during extract-transform-load operations.

13. The computer-based method of claim 11, wherein said pre-computed minimal perfect hash function maintains an auxiliary table for computing hash values.

14. The computer-based method of claim 11, wherein when said load factor is about 60%.

15. The computer-based method of claim 11, wherein said linear probing technique is picked only as a fall-back for correlated multi-column Group Bys when said minimal perfect hash function is not pre-computed.