Partitioning-based vectorized hash join with compact storage footprint

A computer implemented method, comprising:

• storing a build key array comprising build key array elements;
• generating hash table comprising:
• a hash bucket array comprising hash bucket elements, each hash bucket element of the hash bucket elements corresponding to a hash bucket of the hash table;
• a link array comprising link array elements, wherein the link array is index aligned with the build key array elements;
• wherein each hash bucket element includes an offset value that identifies a respective link array element of the link array elements, wherein the respective link array element:
• identifies an offset value of the link array that corresponds to a member build key array element of the build key array elements that is a member of said each hash bucket element;
• or
• specifies that there is no other member build key array elements of the build key array elements for the hash bucket corresponding to the hash bucket element;
• selecting at least a subset of build key array elements of the build key array elements and calculating hash values for each build key array element in the subset of build key array elements;
• generating a temporary array that maps each build key array element of the subset of build key array elements to hash bucket elements of the hash bucket array based on the calculated hash values for the subset of build key array elements;
• for each of the hash bucket elements mapped in the temporary array, copying existing offset values from the hash bucket elements to corresponding link array elements that have an offset values equal to the offset values of the subset of build key array elements in the temporary array;
• and
• for each build key array element of the subset of build key array elements mapped in the temporary array, inserting the offset value from the each build key array element into the corresponding hash bucket element of the hash bucket elements that is mapped to the build key array element in the temporary array.

One or more non-transitory computer-readable media storing sequences of instructions, wherein said sequences of instructions which, when executed by one or more hardware processors, cause:

• storing a partition comprising build key array elements of a build key array;
• generating a hash table comprising:
• a hash bucket array comprising hash bucket elements, each hash bucket element of the hash bucket elements corresponding to a hash bucket of the hash table;
• a link array comprising link array elements, wherein the link array is index aligned with the with the build key array;
• wherein each hash bucket element includes an offset value that identifies a respective link array element of the link array elements, wherein the respective link array element:
• identifies an offset value of the link array that corresponds to a member build key array element of the build key array elements that is a member of said each hash bucket element;
• or
• specifies that there is no other member build key array elements of the build key array elements for the hash bucket corresponding to the hash bucket element;
• for a particular build key array element of the build key array, determining a particular hash bucket element that corresponds to the particular build key array element based upon a calculated hash value for the particular build key array element;
• if the particular hash bucket element contains an existing offset value that identifies an existing link array element, then copying the existing offset value from the particular hash bucket element to a particular link array element identified by a particular offset value that also identifies the particular build key array element;
• and
• inserting the offset value of the particular build key array element into the particular hash bucket element of the hash bucket array.

One or more non-transitory computer-readable media storing sequences of instructions, wherein said sequences of instructions which, when executed by one or more hardware processors, cause:

• storing a build key array comprising build key array elements;
• generating hash table comprising:
• a hash bucket array comprising hash bucket elements, each hash bucket element of the hash bucket elements corresponding to a hash bucket of the hash table;
• a link array comprising link array elements, wherein the link array is index aligned with the build key array elements;
• wherein each hash bucket element includes an offset value that identifies a respective link array element of the link array elements, wherein the respective link array element:
• identifies an offset value of the link array that corresponds to a member build key array element of the build key array elements that is a member of said each hash bucket element;
• or
• specifies that there is no other member build key array elements of the build key array elements for the hash bucket corresponding to the hash bucket element;
• selecting at least a subset of build key array elements of the build key array elements and calculating hash values for each build key array element in the subset of build key array elements;
• generating a temporary array that maps each build key array element of the subset of build key array elements to hash bucket elements of the hash bucket array based on the calculated hash values for the subset of build key array elements;
• for each of the hash bucket elements mapped in the temporary array, copying existing offset values from the hash bucket elements to corresponding link array elements that have an offset values equal to the offset values of the subset of build key array elements in the temporary array;
• and
• for each build key array element of the subset of build key array elements mapped in the temporary array, inserting the offset value from the each build key array element into the corresponding hash bucket element of the hash bucket elements that is mapped to the build key array element in the temporary array.