# US 2022/0035814 A1 · Detecting 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 2022/0035814 A1
- Document ID: US20220035814A1
- Status: Published application
- Kind: A1
- Application number: 17/502,685
- Filed: 2021-10-15
- Published: 2022-02-03
- 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/US20220035814A1

## 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 comprising:
probing, by a local server, a probe side table for data included in the probe side table that corresponds to any build keys included in a build side table, the probing performed as part of a join operation;
determining, by the local server, a frequency at which data is received from the probe side table during the probing;
in response to determining that the frequency meets or exceeds a threshold frequency, distributing, by the local server, data corresponding to a first build key to a remote server, the remote server processing the data corresponding to the first build key as part of the join operation; and
processing, by the local server, data corresponding to a second build key as part of the join operation.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
generating an output of the join operation based on the processing performed by the local server and the processing performed by the remote server.

### Claim 3 (depends on 1)

The method of claim 1, wherein determining the frequency at which data is received from the probe side table during the probing comprises:
determining a frequency at which the first build key is probed during the probing.

### Claim 4 (depends on 3)

The method of claim 3, wherein determining the frequency at which data is received from the probe side table during the probing further comprises:
determination that the frequency at which the first build key is probed meets or exceeds a predetermined threshold, wherein distributing the data corresponding to the first build key to the remote server is based on the determination that the frequency at which the first build key is probed meets or exceeds a predetermined threshold.

### Claim 5 (depends on 2)

The method of claim 2, wherein the remote server is one of a plurality of remote servers to which data may be distributed for processing as part of the join operation.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
distributing, by the local server, data corresponding to a third build key to a second remote server from the plurality of remote servers, the second remote server processing the data corresponding to the third build key as part of the join operation, wherein the output of the join operation is further generated based on the processing performed by the second remote server.

### Claim 7 (depends on 6)

The method of claim 6, wherein distributing the data corresponding to the third build key to the second remote server is based on a determination that a frequency at which the third build key is probed meets or exceeds a predetermined threshold.

### Claim 8 (depends on 1)

The method of claim 1, wherein probing the probe side table comprises:
computing, by the local server, a hash value for the join operation.

### Claim 9 (depends on 8)

The method of claim 8, wherein probing the probe side table further comprises:
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 10 (depends on 9)

The method of claim 9, further comprising:
calculating a total number of rows of the join operation that have been probed into the space saving algorithm.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
calculating the threshold frequency based on the total number of rows of the join operation that have been probed into the space saving algorithm.

### Claim 12

A local computing system comprising:
one or more computer processors; and
one or more computer-readable mediums storing instructions that, when executed by the one or more computer processors, cause the local computing system to perform operations comprising:
probing a probe side table for data included in the probe side table that corresponds to any build keys included in a build side table, the probing performed as part of a join operation;
determining a frequency at which data is received from the probe side table during the probing;
in response to determining that the frequency meets or exceeds a threshold frequency, distributing data corresponding to a first build key to a remote server, the remote server processing the data corresponding to the first build key as part of the join operation; and
processing data corresponding to a second build key as part of the join operation.

### Claim 13 (depends on 12)

The local computing system of claim 12, the operations further comprising:
generating an output of the join operation based on the processing performed by the local computing system and the processing performed by the remote server.

### Claim 14 (depends on 12)

The local computing system of claim 12, wherein determining the frequency at which data is received from the probe side table during the probing comprises:
determining a frequency at which the first build key is probed during the probing.

### Claim 15 (depends on 14)

The local computing system of claim 14, wherein determining the frequency at which data is received from the probe side table during the probing further comprises:
determination that the frequency at which the first build key is probed meets or exceeds a predetermined threshold, wherein distributing the data corresponding to the first build key to the remote server is based on the determination that the frequency at which the first build key is probed meets or exceeds a predetermined threshold.

### Claim 16 (depends on 13)

The local computing system of claim 13, wherein the remote server is one of a plurality of remote servers to which data may be distributed for processing as part of the join operation.

### Claim 17 (depends on 16)

The local computing system of claim 16, the operations further comprising:
distributing data corresponding to a third build key to a second remote server from the plurality of remote servers, the second remote server processing the data corresponding to the third build key as part of the join operation, wherein the output of the join operation is further generated based on the processing performed by the second remote server.

### Claim 18 (depends on 17)

The local computing system of claim 17, wherein distributing the data corresponding to the third build key to the second remote server is based on a determination that a frequency at which the third build key is probed meets or exceeds a predetermined threshold.

### Claim 19 (depends on 12)

The local computing system of claim 12, wherein probing the probe side table comprises:
computing a hash value for the join operation.

### Claim 20 (depends on 19)

The local computing system of claim 19, wherein probing the probe side table further comprises:
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 21 (depends on 20)

The local computing system of claim 20, the operations further comprising:
calculating a total number of rows of the join operation that have been probed into the space saving algorithm.

### Claim 22 (depends on 21)

The local computing system of claim 21, the operations further comprising:
calculating the threshold frequency based on the total number of rows of the join operation that have been probed into the space saving algorithm.

### Claim 23

A non-transitory computer-readable medium storing instructions that, when executed by one or more local servers, cause the one or more local servers to perform operations comprising:
probing a probe side table for data included in the probe side table that corresponds to any build keys included in a build side table, the probing performed as part of a join operation;
determining a frequency at which data is received from the probe side table during the probing;
in response to determining that the frequency meets or exceeds a threshold frequency, distributing, by the local server, data corresponding to a first build key to a remote server, the remote server processing the data corresponding to the first build key as part of the join operation; and
processing data corresponding to a second build key as part of the join operation.

### Claim 24 (depends on 23)

The non-transitory computer-readable medium of claim 23, the operations further comprising:
generating an output of the join operation based on the processing performed by the one or more local servers and the processing performed by the remote server.

### Claim 25 (depends on 23)

The non-transitory computer-readable medium of claim 23, wherein determining the frequency at which data is received from the probe side table during the probing comprises:
determining a frequency at which the first build key is probed during the probing.

### Claim 26 (depends on 25)

The non-transitory computer-readable medium of claim 25, wherein determining the frequency at which data is received from the probe side table during the probing further comprises:
determination that the frequency at which the first build key is probed meets or exceeds a predetermined threshold, wherein distributing the data corresponding to the first build key to the remote server is based on the determination that the frequency at which the first build key is probed meets or exceeds a predetermined threshold.

### Claim 27 (depends on 24)

The non-transitory computer-readable medium of claim 24, wherein the remote server is one of a plurality of remote servers to which data may be distributed for processing as part of the join operation.

### Claim 28 (depends on 27)

The non-transitory computer-readable medium of claim 27, the operations further comprising:
distributing data corresponding to a third build key to a second remote server from the plurality of remote servers, the second remote server processing the data corresponding to the third build key as part of the join operation, wherein the output of the join operation is further generated based on the processing performed by the second remote server.

### Claim 29 (depends on 28)

The non-transitory computer-readable medium of claim 28, wherein distributing the data corresponding to the third build key to the second remote server is based on a determination that a frequency at which the third build key is probed meets or exceeds a predetermined threshold.

### Claim 30 (depends on 23)

The non-transitory computer-readable medium of claim 23, wherein probing the probe side table comprises:
computing, by the local server, a hash value for the join operation.
