Back to results
US 12,001,428 B2Granted
Build-side skew handling for hash-partitioning hash joins
AssigneeSnowflake Inc.
InventorsXinzhu Cai, Florian Andreas Funke
Life of this patent
Estimating the term…
Abstract
Provided herein are systems and methods for handling build-side skew. For example, a method includes computing a plurality of hash values for a join operation. The join operation uses a corresponding plurality of row sets. The plurality of hash values are sampled to detect a frequent hash value. A build-side row set is partitioned using the frequent hash value to generate a partitioned build-side row set. The build-side row set is selected from the plurality of row sets. The partitioned build-side row set is distributed to a plurality of hash-join-build (HJB) instances executing at a corresponding plurality of servers.
Claims30
A system comprising:
- at least one hardware processor of a first server;
- and
- at least one memory storing instructions that cause the at least one hardware processor to perform operations comprising:
- generating at the first server, a plurality of build-side row sets using build-side row data received from a second server;
- computing, at the first server, a plurality of hash values for a join operation using the build-side row data, the join operation using the plurality of build-side row sets as build-side input and a plurality of probe-side row sets of probe-side row data originating from a third server as probe-side input, data from the probe-side input being probed to detect a match with data from build-side input during the join operation;
- sampling the plurality of hash values associated with the plurality of build-side row sets to detect a frequent hash value, the frequent hash value appearing at least a threshold number of times in the plurality of hash values for the build-side row data;
- partitioning a build-side row set of the plurality of build-side row sets to generate a partitioned build-side row set, the build-side row set using the frequent hash value, and the partitioned build-side row set including a plurality of hash partitions of the build-side row data, a number of rows in the build-side row data being smaller than a number of rows in the probe-side row data after the partitioning of the build-side row set;
- distributing the plurality of hash partitions to a plurality of hash-join-build (HJB) instances executing at a corresponding plurality of additional servers, each server of the plurality of additional servers executing one of the plurality of HJB instances using a hash partition of the plurality of hash partitions;
- and
- outputting a result of the join operation based on completion of execution of the plurality of HJB instances at the plurality of additional servers.
7 more elements
A method comprising:
- generating, by at least one hardware processor of a first server, a plurality of build-side row sets using build-side row data received from a second server;
- computing, by the at least one hardware processor, a plurality of hash values for a join operation using the build-side row data, the join operation using the plurality of build-side row sets as build-side input and a plurality of probe-side row sets of probe-side row data originating from a third server as probe-side input, data from the probe-side input being probed to detect a match with data from build-side input during the join operation;
- sampling the plurality of hash values associated with the plurality of build-side row sets to detect a frequent hash value, the frequent hash value appearing at least a threshold number of times in the plurality of hash values for the build-side row data;
- partitioning a build-side row set of the plurality of build-side row sets to generate a partitioned build-side row set, the build-side row set using the frequent hash value, and the partitioned build-side row set including a plurality of hash partitions of the build-side row data, a number of rows in the build-side row data being smaller than a number of rows in the probe-side row data after the partitioning of the build-side row set;
- distributing the plurality of hash partitions to a plurality of hash-join-build (HJB) instances executing at a corresponding plurality of additional servers, each server of the plurality of additional servers executing one of the plurality of HJB instances using a hash partition of the plurality of hash partitions;
- and
- outputting a result of the join operation based on completion of execution of the plurality of HJB instances at the plurality of additional servers.
4 more elements
A computer-storage medium comprising instructions that, when executed by one or more processors of a machine, configure the machine to perform operations comprising:
- generating, by at least one hardware processor of a first server, a plurality of build-side row sets using build-side row data received from a second server;
- computing, by the at least one hardware processor, a plurality of hash values for a join operation using the build-side row data, the join operation using the plurality of build-side row sets as build-side input and a plurality of probe-side row sets of probe-side row data originating from a third server as probe-side input, data from the probe-side input being probed to detect a match with data from build-side input during the join operation;
- sampling the plurality of hash values associated with the plurality of build-side row sets to detect a frequent hash value, the frequent hash value appearing at least a threshold number of times in the plurality of hash values for the build-side row data;
- partitioning a build-side row set of the plurality of build-side row sets to generate a partitioned build-side row set, the build-side row set using the frequent hash value, and the partitioned build-side row set including a plurality of hash partitions of the build-side row data, a number of rows in the build-side row data being smaller than a number of rows in the probe-side row data after the partitioning of the build-side row set;
- distributing the plurality of hash partitions to a plurality of hash-join-build (HJB) instances executing at a corresponding plurality of additional servers, each server of the plurality of additional servers executing one of the plurality of HJB instances using a hash partition of the plurality of hash partitions;
- and
- outputting a result of the join operation based on completion of execution of the plurality of HJB instances at the plurality of additional servers.
4 more elements
Dependencies are inferred from the claim text.