Embracing and exploiting data skew during a join or groupby

• US 10,489,403 B2
• Filed: 05/06/2015
• Issued: 11/26/2019
• Est. Priority Date: 10/08/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Attaluri, Gopi K., Raman, Vijayshankar
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US14/705,377
• Publication Number:
  US 20160103880A1
• Time in Patent Office: 1,665 Days
• Field of Search: 707600-899
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/86 Mapping to a database

Abstract

A hybrid approach for performing a join in a database includes: obtaining a distribution of data values in a join column of an inner table; using the distribution, identifying one or more data ranges containing skew; for each data range identified as containing skew, performing, by the processor, the join operation using a skew specific join scheme; and for each data range not identified as containing skew, performing, by the processor, the join operation using a non-skew specific join scheme. One skew specific join scheme involves a compact array table, a highly populated array that represents the range of values that the inner table join column contains. One non-skew specific join scheme involves a compact hash table, an optimized hash table that allows high load factors with a small memory overhead. In combining multiple join techniques, joins may be performed more efficiently for skewed and non-skewed data.

Claims

1. A method, comprising:

during a query optimization for a database query involving a join operation, obtaining a distribution of data values in a join column of an inner table;

using the distribution, identifying one or more data ranges containing skew;

performing a cost-benefit analysis for a skew specific join scheme, wherein the cost benefit analysis is based on a tradeoff between a number of the data values in a data range of the one or more data ranges and additional overhead costs of processing the number of data values using the skew specific join scheme;

for each data range identified as containing skew, performing the join operation using the skew specific join scheme based on the cost-benefit analysis; and

for each data range not identified as containing skew, performing the join operation using a non-skew specific join scheme.

2. The method of claim 1, wherein the identifying of the one or more data ranges containing skew comprises:

identifying minimum and maximum values in the distribution and excluding outlier values; and

identifying one or more densely populated ranges or cluster of ranges.

3. The method of claim 1, wherein the identifying of the one or more data ranges containing skew comprises:

finding a plurality of clusters of values in the distribution;

for each cluster, identifying a median value; and

for each cluster, selecting a largest number of values in the cluster within a distance from the median value which benefits from the skew specific join scheme.

4. The method of claim 3, wherein the performing the cost-benefit analysis comprises:

for each cluster, performing the cost benefit analysis to include values in increasing distance from the median value until a benefit from the skew specific join scheme drops below a threshold.

5. The method of claim 1, wherein the identifying of the one or more data ranges containing skew comprises:

obtaining a plurality of bits in join keys of the inner table;

identifying variant bits and invariant bits in the plurality of bits; and

defining the variant bits as a data range containing skew.

6. The method of claim 1, wherein the performing of the join operation using the skew specific join scheme comprises creating a compact array table, comprising:

identifying keys in a database, the keys each having an associated value;

identifying bits that are common between the keys;

removing the identified bits to form condensed keys;

modulating the condensed keys using identified bits to create transformed keys; and

populating the one or more array tables using the transformed keys and the keys'"'"' associated values.

7. The method of claim 1, wherein the performing of the join operation using a non-skew specific join scheme comprises creating a compact hash table, comprising:

removing each empty bucket from a hash table and compacting 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.