# US 2019/0377813 A1 · Systems, Methods, And Devices For Managing Data Skew In A Join Operation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0377813 A1
- Document ID: US20190377813A1
- Status: Published application
- Kind: A1
- Application number: 16/005,182
- Filed: 2018-06-11
- Published: 2019-12-12
- Earliest claimed: 2018-06-11
- Assignees: Snowflake Inc.
- Applicants: Snowflake Inc.
- Inventors: Florian Andreas Funke; Thierry Cruanes; Benoit Dageville; Marcin Zukowski
- Web page: https://patentgrep.com/patent/US20190377813A1

## CPC

- G06F 16/24544: {Join order optimisation}
- G06F 16/217: {Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409)}
- G06F 16/2255: {Hash tables}
- G06F 16/24537: {of operators}
- G06F 16/2456: {Join operations}
- G06F 16/273: {Asynchronous replication or reconciliation}
- H04L 67/025: for remote control or remote monitoring of applications
- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- H04L 67/1097: for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Systems, methods, and devices, for managing data skew during a join operation are disclosed. A method includes computing a hash value for a join operation and detecting data skew on a probe side of the join operation at a runtime of the join operation using a lightweight sketch data structure. The method includes identifying a frequent probe-side join key on the probe side of the join operation during a probe phase of the join operation. The method includes identifying a frequent build-side row having a build-side join key corresponding with the frequent probe-side join key. The method includes asynchronously distributing the frequent build-side row to one or more remote servers.

## Claims

### Claim 1

A method for managing data skew, the method comprising:
computing a hash value for a join operation;
detecting data skew on a probe side of the join operation at a runtime of the join operation using a lightweight sketch data structure;
identifying a frequent probe-side join key on the probe side of the join operation during a probe phase of the join operation;
identifying a frequent build-side row having a build-side join key corresponding with the frequent probe-side join key; and
asynchronously distributing the frequent build-side row to one or more remote servers.

### Claim 2 (depends on 1)

The method of claim 1, wherein the one or more remote servers is configured to:
asynchronously receive the frequent build-side row; and
generate a separate hash table for the frequent build-side row.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
selecting a rowset comprising a plurality of rows of the join operation; and
probing each of the plurality of rows of the rowset into a space saving algorithm using the hash value for the join operation.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
updating the space saving algorithm based on incoming data; and
for each update to the space saving algorithm, identifying a frequency indicating how frequently the frequent probe-side join key is probed as a side-effect of the updating the space saving algorithm.

### Claim 5 (depends on 4)

The method of claim 4, wherein asynchronously distributing the frequent build-side row to the one or more remote servers comprises:
in response to the frequency exceeding a predetermined threshold, asynchronously distributing the frequent build-side row to the one or more remote servers; and
in response to the frequency not exceeding the predetermined threshold, retaining the frequent build-side row on a current server.

### Claim 6 (depends on 3)

The method of claim 3, further comprising:
calculating a total number of rows of the join operation that have been probed into the space saving algorithm;
calculating a threshold per worker thread based on the total number of rows of the join operation that have been probed into the space saving algorithm; and
based on the threshold per worker thread, determining whether the frequent build-side join key is frequent among all threads of at least one server.

### Claim 7 (depends on 1)

The method of claim 1, wherein asynchronously distributing the frequent build-side row to the one or more remote servers comprises one of:
broadcasting the frequent build-side row to each of a plurality of available remote servers; or
broadcasting the frequent build-side row only to one or more remote servers that frequently transmitted the frequent build-side join key.

### Claim 8 (depends on 1)

The method of claim 1, further comprising altering an input link of a server to route a frequent probe-side row comprising the frequent probe-side join key to a local instance of the join operation such that network traffic is reduced.

### Claim 9 (depends on 1)

The method of claim 1, wherein asynchronously distributing the frequent build-side row to the one or more remote servers occurs only after determining, to a threshold confidence level, that the frequent probe-side join key is frequent on a server.

### Claim 10 (depends on 3)

The method of claim 3, wherein the lightweight sketch data structure comprises a hash table space saving algorithm.

### Claim 11

Non-transitory computer readable storage media storing instructions that, when executed by one or more processors, cause the one or more processors to:
compute a hash value for a join operation;
detect data skew on a probe side of the join operation at a runtime of the join operation using a lightweight sketch data structure;
identify a frequent probe-side join key on the probe side of the join operation during a probe phase of the join operation;
identify a frequent build-side row having a build-side join key corresponding with the frequent probe-side join key; and
asynchronously distribute the frequent build-side row to one or more remote servers.

### Claim 12 (depends on 11)

The non-transitory computer readable storage media of claim 11, wherein the instructions further cause the one or more processors to:
select a rowset comprising a plurality of rows of the join operation; and
probe each of the plurality of rows of the rowset into a space saving algorithm using the hash value for the join operation.

### Claim 13 (depends on 12)

The non-transitory computer readable storage media of claim 12, wherein the instructions further cause the one or more processors to:
update the space saving algorithm based on incoming data; and
for each update to the space saving algorithm, identify a frequency indicating how frequently the frequent probe-side join key is probed as a side-effect of the one or more processors updating the space saving algorithm.

### Claim 14 (depends on 13)

The non-transitory computer readable storage media of claim 13, wherein causing the one or more processors to asynchronously distribute the frequent build-side row to the one or more remote servers comprises:
in response to the frequency exceeding a predetermined threshold, asynchronously distribute the frequent build-side row to the one or more remote servers; and
in response to the frequency not exceeding the predetermined threshold, retaining the frequent build-side row on a current server.

### Claim 15 (depends on 12)

The non-transitory computer readable storage media of claim 12, wherein the instructions further cause the one or more processors to:
calculate a total number of rows of the join operation that have been probed into the space saving algorithm;
calculate a threshold per worker thread based on the total number of rows of the join operation that have been probed into the space saving algorithm; and
based on the threshold per worker thread, determining whether the frequent build-side join key is frequent among all threads of at least one server.

### Claim 16 (depends on 11)

The non-transitory computer readable storage media of claim 11, wherein causing the one or more processors to asynchronously distribute the frequent build-side row to the one or more remote servers comprises one of:
broadcasting the frequent build-side row to each of a plurality of available remote servers; or
broadcasting the frequent build-side row only to one or more remote servers that frequently transmitted the frequent build-side join key.

### Claim 17 (depends on 11)

The non-transitory computer readable storage media of claim 11, wherein the instructions further cause the one or more processors to alter an input link of a server to route a frequent probe-side row comprising the frequent probe-side join key to a local instance of the join operation such that network traffic is reduced.

### Claim 18

A system for managing data skew, the system comprising:
a means for computing a hash value for a join operation;
a means for detecting data skew on a probe side of the join operation at a runtime of the join operation using a lightweight sketch data structure;
a means for identifying a frequent probe-side join key on the probe side of the join operation during a probe phase of the join operation;
a means for identifying a frequent build-side row having a build-side join key corresponding with the frequent probe-side join key; and
a means for asynchronously distributing the frequent build-side row to one or more remote servers.

### Claim 19 (depends on 18)

The system of claim 18, further comprising:
a means for selecting a rowset comprising a plurality of rows of the join operation; and
a means for probing each of the plurality of rows of the rowset into a space saving algorithm using the hash value for the join operation.

### Claim 20 (depends on 19)

The system of claim 19, further comprising:
a means for updating the space saving algorithm based on incoming data; and
for each update to the space saving algorithm, a means for identifying a frequency indicating how frequently the frequent probe-side join key is probed as a side-effect of the updating the space saving algorithm.

### Claim 21 (depends on 20)

The system of claim 20, wherein the means for asynchronously distributing the frequent build-side row to the one or more remote servers is further configured to:
in response to the frequency exceeding a predetermined threshold, asynchronously distribute the frequent build-side row to the one or more remote servers; and
in response to the frequency not exceeding the predetermined threshold, retaining the frequent build-side row on a current server.

### Claim 22 (depends on 19)

The system of claim 19, further comprising:
a means for calculating a total number of rows of the join operation that have been probed into the space saving algorithm;
a means for calculating a threshold per worker thread based on the total number of rows of the join operation that have been probed into the space saving algorithm; and
a means for determining, based on the threshold per worker thread, whether the frequent build-side join key is frequent among all threads of at least one server.
