Efficient join on dynamically compressed inner for improved fit into cache hierarchy

• US 10,303,791 B2
• Filed: 03/20/2015
• Issued: 05/28/2019
• 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., Chainani, Naresh K., Lohman, Guy M., Pandis, Ippokratis, Raman, Vijayshankar, Sidle, Richard S.
• Primary Examiner(s): Pham, Khanh B
• Application Number:
  US14/664,714
• Publication Number:
  US 20160275145A1
• Time in Patent Office: 1,530 Days
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

A method includes joining data between at least two data sets. Values of one or more join attributes of each of the data sets is represented in a compressed form, indicated by an encoding scheme. A compression scheme for the one or more join attributes is dynamically selected.

Claims

1. A method comprising:

joining, using a hash join process, data between at least two column data sets from hash table columns from at least two hash tables, wherein values of one or more join keys of each of the data sets is represented in a compressed form, indicated by an encoding scheme; and

dynamically compressing the one or more join keys with a compression scheme during an outer scan operation of the hash join process, the compression scheme being dynamically selected based on join key data type, wherein different compression schemes are selected for the hash table columns including;

numerical typed key columns, decimal typed key columns and character string typed key columns.

2. The method of claim 1, wherein for numerical typed key columns, the compression scheme selected comprises assigning codes for encoding in a range from minimum value to maximum value of one of the data sets involved in the join, and for N possible values within the range, the N possible values are represented as a ceiling function that rounds up log N in bits, where N is a positive integer.

3. The method of claim 2, further comprising scanning all records of the one of the data sets prior to assigning the codes.

4. The method of claim 1, wherein for decimal typed key columns, tracking a largest used scale in the values present in one of the data sets involved in the join, and only encoding values within that scale.

5. The method of claim 1, wherein for character string typed key columns, if a common prefix exists among the values present in one of the data sets involved in the join, assign codes in a range from minimum value to maximum value of a suffix of those values.

6. The method of claim 1, further comprising:

during an inner scan operation;

hashing unencoded join keys onto a particular one of two hash tables; and

partitioning the particular one hash table;

wherein for composite join keys, concatenating encoded join keys after said partitioning.

7. The method of claim 1, further comprising:

for join inner-joins, any records containing join column values that are not representable in the compression scheme selected are eliminated; and

for left outer joins, for any records containing join column values that are not representable in the compression scheme selected, the join column values are marked as NULL, and assigned a dummy code.

8. The method of claim 1, further comprising:

building a bitmap based on a range from minimum value to maximum value indicating join keys found during a scan, wherein the bitmap is used as a join filter; and

for left outer joins, join column values for records that fail to find a match when looking up the join filter are marked as NULL.

9. A computer program product for performing a hash join process, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

joining, using the hash join process, data between at least two column data sets from hash table columns from at least two hash tables, wherein values of one or more join keys of each of the column data sets is represented in a compressed form, indicated by an encoding scheme; and

dynamically compressing the one or more join keys with a compression scheme during an outer scan operation of the hash join process, the compression scheme being dynamically selected based on join keys data type, wherein different compression schemes are selected for the hash table columns including;

numerical typed key columns, decimal typed key columns and character string typed key columns.

10. The computer program product of claim 9, wherein for numerical typed key columns, the compression scheme selected comprises assigning codes for encoding in a range from minimum value to maximum value of one of the datasets involved in the join, and for N possible values within the range, the N possible values are represented as a ceiling function that rounds up log N in bits, where N is a positive integer.

11. The computer program product of claim 10, further comprising scanning all records of the one of the data sets prior to assigning the codes.

12. The computer program product of claim 9, wherein for decimal typed key columns, tracking a largest used scale in the values present in one of the data sets involved in the join, and only encoding values within that scale.

13. The computer program product of claim 9, wherein for character string typed key columns, if a common prefix exists among the values present in one of the data sets involved in the join, assign codes in a range from minimum value to maximum value of a suffix of those values.

14. The computer program product of claim 9, further comprising:

during an inner scan operation;

hashing unencoded join keys onto a hash table; and

partitioning the hash table;

wherein or composite join keys, concatenating encoded join keys after said partitioning.

15. The computer program product of claim 9, further comprising:

for join inner-joins, any records containing join column values that are not representable in the compression scheme selected are eliminated; and

for left outer joins, for any records containing join column values that are not representable in the compression scheme selected, the join column values are marked as NULL, and assigned a dummy code.

16. The computer program product of claim 9, further comprising:

building a bitmap based on a range from minimum value to maximum value indicating join keys found during a scan, wherein the bitmap is used as a join filter; and

for left outer joins, join column values for records that fail to find a match when looking up the join filter are marked as NULL.

17. A method comprising:

hashing join keys onto a particular one of at least two hash tables and partitioning the particular one hash table;

performing a hash join process on column data sets from hash table columns from the at least two hash tables, wherein one or more join keys of each of the data sets are represented in a compressed form, indicated by an encoding scheme; and

dynamically compressing the one or more join keys with an encoding scheme during an outer scan operation of the hash join process, the encoding scheme being dynamically selected based on join attribute data type, wherein different encoding schemes for the one or more join keys are selected for the hash table columns including;

numerical typed key columns, decimal typed key columns and character string typed key columns.

18. The method of claim 17, wherein:

for numerical typed key columns, the encoding scheme selected comprises assigning codes for encoding in a range from minimum value to maximum value of one of the data sets involved in the join, and for N possible values within the range, the N possible values are represented as a ceiling function that rounds up log N in bits, where N is a positive integer;

for decimal typed key columns, the encoding scheme selected comprises tracking a largest used scale in the values present in one of the data sets involved in the join, and only encoding values within that scale;

for character string typed key columns, the encoding scheme selected comprises if a common prefix exists among the values present in one of the data sets involved in the join, assign codes in a range from minimum value to maximum value of a suffix of those values;

for join inner-joins, any records containing join column values that are not representable in the encoding scheme selected are eliminated; and

for left outer joins, for any records containing join column values that are not representable in the encoding scheme selected, the join column values are marked as NULL.