APPLYING VARIOUS HASH METHODS USED IN CONJUNCTION WITH A QUERY WITH A GROUP BY CLAUSE

• US 20090249023A1
• Filed: 03/28/2008
• Published: 10/01/2009
• Est. Priority Date: 03/28/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Qiao, Lin, Swart, Garret Frederick, Raman, Vijayshankar
• Granted Patent: US 8,108,401 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• 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.

2. The computer-based method of claim 1, wherein, for a given drawer, 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.

3. The computer-based method of claim 2, wherein 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.

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

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

6. The computer-based method of claim 3, 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 computer-based method of claim 6, wherein when said load factor is about 60%.

8. The computer-based method of claim 3, 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.

9. An article of manufacture comprising a computer usable medium having computer readable program code embodied therein which implements a computer-based method for applying a plurality of hash methods in a 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.

10. The article of manufacture of claim 9, wherein, for a given drawer, computer readable program code picks said hashing scheme according to the number of distinct groups in said given drawer, said number of distinct groups estimated from a dictionary.

11. The article of manufacture of claim 10, wherein computer readable program code picks said hashing scheme as follows:

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

for correlated Group Bys, computer readable program code 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, computer readable program code using a linear probing hashing scheme using multiplicative hashing as a hashing function.

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

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

14. The article of manufacture of claim 11, wherein, when said linear probing hashing scheme is picked, computer readable program code filling a hash table associated with said give drawer up to a predetermined load factor.

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

16. The article of manufacture of claim 11, 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.

17. 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 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.

18. The computer-based method of claim 17, wherein, for a given drawer, 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.

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

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

21. The computer-based method of claim 17, 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.

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

23. The computer-based method of claim 17, 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.