# US 12,001,427 B2 · Systems, methods, and devices for acceleration of merge join operations

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

- Number: US 12,001,427 B2
- Document ID: US12001427B2
- Status: Granted
- Kind: B2
- Application number: 17/174,350
- Filed: 2021-02-11
- Published: 2022-06-30
- Granted: 2024-06-04
- Earliest claimed: 2020-12-28
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Shiyu Li; Yiqun Zhang; Joo Hwan Lee; Yang Seok Ki; Andrew Chang
- Web page: https://patentgrep.com/patent/US12001427B2

## CPC

- G06F 16/24537: {of operators}
- G06F 16/24532: {of parallel queries}
- G06F 16/2456: {Join operations}
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method of processing data may include receiving a stream of first keys associated with first data, receiving a stream of second keys associated with second data, comparing, in parallel, a batch of the first keys and a batch of the second keys, collecting one or more results from the comparing, and gathering one or more results from the collecting. The collecting may include reducing an index matrix and a mask matrix. Gathering one or more results may include storing, in a leftover vector, at least a portion of the one or more results from the collecting. Gathering one or more results further may include combining at least a portion of the leftover vector from a first cycle with at least a portion of the one or more results from the collecting from a second cycle.

## Claims

### Claim 1

A method of processing data, the method comprising:
loading, using a first register, at least one first key associated with first data;
loading, using a second register, at least one second key associated with second data;
comparing, based on a join key, the at least one first key and the at least one second key to generate a first result, wherein the join key is derived from the at least one first key, and wherein the first result comprises an index matrix, the index matrix comprising an indicator of the at least one first key corresponding to the at least one second key;
storing, using a buffer, the first result;
collecting the first result and a second result to generate a first collected result; and
gathering the first collected result and a second collected result.

### Claim 2 (depends on 1)

The method of claim 1, wherein the comparing comprises generating at least one matrix based on the at least one first key and the at least one second key.

### Claim 3 (depends on 2)

The method of claim 2, wherein the collecting the first result comprises reducing the at least one matrix.

### Claim 4 (depends on 3)

The method of claim 3, wherein the at least one matrix comprises the index matrix and a mask matrix, and reducing the at least one matrix comprises:
reducing the index matrix to an index vector; and
reducing the mask matrix to a mask vector.

### Claim 5 (depends on 4)

The method of claim 4, further comprising generating an offset vector based on the mask vector.

### Claim 6 (depends on 1)

The method of claim 1, wherein the collecting the first result and the second result comprises generating a result vector based on an offset and the at least one first key.

### Claim 7 (depends on 1)

The method of claim 1, wherein the gathering the first collected result and a second collected result comprises storing, in a leftover vector, the first collected result.

### Claim 8 (depends on 7)

The method of claim 7, wherein the gathering the first collected result and a second collected result further comprises combining at least a portion of the leftover vector from a first cycle with at least a portion of a leftover vector from a second cycle.

### Claim 9 (depends on 1)

The method of claim 1, wherein the first data comprises at least one index to at least one row associated with the at least one first key.

### Claim 10 (depends on 1)

The method of claim 1, wherein the comparing, the collecting, and the gathering perform a merge join operation.

### Claim 11

An apparatus comprising a merge core comprising:
a parallel comparison circuit comprising at least one processor configured to:
receive a stream of first keys associated with first data;
receive a stream of second keys associated with second data;
compare, based on a join key, at least one of the first keys and at least one of the second keys to generate a first result, wherein the join key is derived from one of the first keys, and wherein the first result comprises an index matrix, the index matrix comprising an indicator of the first keys corresponding to the second keys; and
a collection circuit configured to collect one or more results from the parallel comparison circuit; and
a gathering circuit configured to gather one or more results from the collection circuit.

### Claim 12 (depends on 11)

The apparatus of claim 11, further comprising:
a first reader configured to read the stream of first keys from a memory; and
a second reader configured to read the stream of second keys from the memory.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein:
the first reader is further configured to read a stream of the first data from the memory; and
the second reader is further configured to read a stream of the second data from the memory.

### Claim 14 (depends on 13)

The apparatus of claim 13, further comprising a writer configured to write a stream of output keys from the gathering circuit to the memory.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein:
the first reader is further configured to read a stream of the first data from the memory;
the second reader is further configured to read a stream of the second data from memory; and
the writer is further configured to write a stream of output data associated with the stream of output keys from the gathering circuit to the memory.

### Claim 16 (depends on 11)

The apparatus of claim 11, wherein the parallel comparison circuit, the collection circuit, and the gathering circuit are integral with an accelerator device.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the accelerator device comprises a field programmable gate array.

### Claim 18

A system comprising:
a storage device;
a memory configured to receive a dataset from the storage device; and
an accelerator device coupled to the storage device, wherein the accelerator device comprises:
a parallel comparison circuit configured to receive a stream of first keys associated with first data of the dataset from the memory, receive a stream of second keys associated with second data of the dataset from the memory, and compare, in parallel, using a join key, at least one of the first keys and at least one of the second keys to generate a first result, wherein the join key is derived from one of the first keys, and wherein the first result comprises an index matrix, the index matrix comprising an indicator of the first keys corresponding to the second keys;
a collection circuit configured to collect one or more results from the parallel comparison circuit; and
a gathering circuit configured to gather one or more results from the collection circuit.

### Claim 19 (depends on 18)

The system of claim 18, further comprising a point-to-point connection between the storage device and the accelerator device.

### Claim 20 (depends on 19)

The system of claim 19, wherein the memory and the accelerator device are integral with the storage device.