# US 2021/0232598 A1 · Adaptive distribution for hash operations

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

- Number: US 2021/0232598 A1
- Document ID: US20210232598A1
- Status: Published application
- Kind: A1
- Application number: 17/231,752
- Filed: 2021-04-15
- Published: 2021-07-29
- Earliest claimed: 2014-02-19
- Assignees: Snowflake Inc.
- Applicants: Snowflake Inc.
- Inventors: Benoit Dageville; Thierry Cruanes; Marcin Zukowski; Allison Waingold Lee; Philipp Thomas Unterbrunner
- Web page: https://patentgrep.com/patent/US20210232598A1

## CPC

- G06F 16/273: {Asynchronous replication or reconciliation}
- A61F 5/566: {Intra-oral devices}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5016: {the resource being the memory}
- G06F 9/5044: {considering hardware capabilities}
- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- G06F 9/5088: {involving task migration}
- G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)}
- G06F 16/148: {File search processing}
- G06F 16/1827: {Management specifically adapted to NAS (management of storage area networks [SAN] G06F3/067)}
- G06F 16/211: {Schema design and management}
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/24532: {of parallel queries}
- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/24552: {Database cache management}
- G06F 16/2456: {Join operations}
- G06F 16/2471: {Distributed queries}
- G06F 16/254: {Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses}
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 16/283: {Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP}
- G06F 16/951: Indexing; Web crawling techniques
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 16/9538: Presentation of query results
- H04L 67/1095: Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
- 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]
- H04L 67/568: Storing data temporarily at an intermediate stage, e.g. caching
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- A61F: FILTERS IMPLANTABLE INTO BLOOD VESSELS; PROSTHESES; DEVICES PROVIDING PATENCY TO, OR PREVENTING COLLAPSING OF, TUBULAR STRUCTURES OF THE BODY, e.g. STENTS; ORTHOPAEDIC, NURSING OR CONTRACEPTIVE DEVICES; FOMENTATION; TREATMENT OR PROTECTION OF EYES OR EARS; BANDAGES, DRESSINGS OR ABSORBENT PADS; FIRST-AID KITS (dental prosthetics A61C)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method, apparatus, and system for join operations of a plurality of relations that are distributed over a plurality of storage locations over a network of computing components.

## Claims

### Claim 1

A method for joining relations, the method comprising:
receiving a relational join query for a join operation for a plurality of relations, wherein the plurality of relations comprises a first relation and a second relation;
determining, by a processing device, a type of join to be performed on the plurality of relations based on an actual size of the second relation and an estimated size of the first relation, wherein the type of join is a broadcasting join or a re-partitioning join; and
managing, by the processing device, one or more communication links between at least one build operator and at least one probe operator to perform the join operation based on the type of join to be performed.

### Claim 2 (depends on 1)

The method of claim 1, wherein managing the one or more communication links comprises, in response to determining to join the plurality of relations via the broadcasting join, converting a link between the at least one build operator and the at least one probe operator into a synchronous link.

### Claim 3 (depends on 2)

The method of claim 2, wherein the synchronous link denotes a local one-to-one link between the at least one build operator and the at least one probe operator, and wherein the at least one probe operator performs the broadcasting join.

### Claim 4 (depends on 3)

The method of claim 3, wherein converting the link comprises converting a communication link between the at least one build operator and the at least one probe operator from an initially inactive and adaptive state to the synchronous link.

### Claim 5 (depends on 1)

The method of claim 1, wherein managing the one or more communication links comprises, in response to determining to join the plurality of relations via the re-partitioning join, converting a link between the at least one build operator and the at least one probe operator into a partition link.

### Claim 6 (depends on 5)

The method of claim 5, wherein the first relation and the second relation are partitioned among a plurality of processors.

### Claim 7 (depends on 5)

The method of claim 5, further comprising during a re-partition join, sending a partition of the second relation to a local probe operator instance as a single pointer to a block of memory or a file on a disk.

### Claim 8 (depends on 7)

The method of claim 7, wherein partitioning the second relation comprises a partitioning operator comprising a hash function over at least one column of the second relation.

### Claim 9 (depends on 1)

The method of claim 1, wherein during a broadcasting join, a local partition of the first relation is forwarded to a local instance of the at least one probe operator for performing the relational join query.

### Claim 10 (depends on 9)

The method of claim 9, wherein the broadcasting join further comprises broadcasting each partition of a plurality of partitions of the second relation to every instance of the at least one probe operator in a distributed system.

### Claim 11 (depends on 1)

The method of claim 1, wherein during a re-partitioning join, a partitioning operation partitions the first relation across a plurality of processing nodes of a distributed system and the re-partitioning join is performed by the at least one probe operator at each of the plurality of processing nodes.

### Claim 12

A system for joining relations, the system comprising:
a memory to store a plurality of relations; and
a processing device, operatively coupled to the memory, the processing device to:
receive a relational join query for a join operation comprising a predicate and a plurality of relations, wherein the plurality of relations comprises a first relation and a second relation;
determine a type of join to be performed on the plurality of relations based on an actual size of the second relation and an estimated size of the first relation, wherein the type of join is a broadcasting join or a re-partitioning join; and
manage one or more communication links between at least one build operator and at least one probe operator to perform the join operation based on the type of join to be performed.

### Claim 13 (depends on 12)

The system of claim 12, wherein to manage the one or more communication links, the processing device is to, in response to determining to join the plurality of relations via the broadcasting join, convert a link between the at least one build operator and the at least one probe operator into a synchronous link.

### Claim 14 (depends on 13)

The system of claim 13, wherein the synchronous link denotes a local one-to-one link between the at least one build operator and the at least one probe operator, and wherein the at least one probe operator performs the broadcasting join.

### Claim 15 (depends on 14)

The system of claim 14, wherein the processing device is to convert a communication link between the at least one build operator and the at least one probe operator from an initially inactive and adaptive state to the synchronous link.

### Claim 16 (depends on 12)

The system of claim 12, wherein to manage the one or more communication links, the processing device is further to, in response to determining to join the plurality of relations via the re-partitioning join, convert a link between a build operator and a probe operator into a partition link.

### Claim 17 (depends on 12)

The system of claim 12, wherein the first relation and the second relation are partitioned among a plurality of processors of a distributed system.

### Claim 18 (depends on 12)

The system of claim 12, wherein to perform the re-partition join, the processing device is to:
send a partition of the second relation to a local probe operator instance as a single pointer to a block of memory or a file on a disk.

### Claim 19 (depends on 12)

The system of claim 12, wherein to perform a broadcasting join, the processing device is to:
forward a local partition of the first relation to a local instance of a probe operator for performing the relational join query.

### Claim 20

A non-transitory computer readable medium having instructions stored thereon that, when executed by a processing device, cause the processing device to:
receive a relational join query for a join operation comprising a predicate and a plurality of relations, wherein the plurality of relations comprises a first relation and a second relation;
determine, by the processing device, a type of join to be performed on the plurality of relations based on an actual size of the second relation and an estimated size of the first relation, wherein the type of join is a broadcasting join or a re-partitioning join; and
manage, by the processing device, one or more communication links between at least one build operator and at least one probe operator to perform the join operation based on the type of join to be performed.

### Claim 21 (depends on 20)

The non-transitory computer readable medium of claim 20, wherein the relations are distributed over a plurality of processing nodes.

### Claim 22 (depends on 20)

The non-transitory computer readable medium of claim 20, wherein to manage the one or more communication links, the processing device is to:
in response to determining to join the plurality of relations via the broadcasting join, convert a link between the at least one build operator and at least one probe operator into a synchronous link.

### Claim 23 (depends on 22)

The non-transitory computer readable medium of claim 22, wherein the synchronous link denotes a local one-to-one link between the at least one build operator and the at least one probe operator, and wherein the probe operator performs the broadcasting join.

### Claim 24 (depends on 20)

The non-transitory computer readable medium of claim 20, wherein to manage the one or more communication links, the processing device is to:
in response to determining to join the plurality of relations via the re-partitioning join, convert a link between the at least one build operator and the at least one probe operator into a partition link.

### Claim 25 (depends on 20)

The non-transitory computer readable medium of claim 20, wherein during a broadcasting join, a local partition of the first relation is forwarded to a local instance of the at least one probe operator for performing the relational join query.
