Embracing and exploiting data skew during a join or groupby

1. A computer program product for performing a join operation in a database, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform:

during a query optimization for a 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, by the processor, 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, by the processor, the join operation using a non-skew specific join scheme.

2. The computer program product 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 computer program product 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 computer program product 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 computer program product 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 computer program product of claim 1 , wherein the performing of the join operating 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 computer program product 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 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.

8. A system, comprising:

a processor; and

a computer readable storage medium having program instructions embodied therewith, the program instructions executable by the processor to cause the processor to perform:

during a query optimization for a 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, by the processor, 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, by the processor, the join operation using a non-skew specific join scheme.

9. The system of claim 8 , 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.

10. The system of claim 8 , 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.

11. The system of claim 8 , 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.

12. The system of claim 11 , 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.