# US 12,216,634 B1 · Disk-based merge for hash maps

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

- Number: US 12,216,634 B1
- Document ID: US12216634B1
- Status: Granted
- Kind: B1
- Application number: 18/228,187
- Filed: 2023-07-31
- Published: 2025-02-06
- Granted: 2025-02-04
- Earliest claimed: 2023-07-31
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Christian Bensberg; Frederik Transier; Kai Stammerjohann
- Web page: https://patentgrep.com/patent/US12216634B1

## CPC

- G06F 16/2272: {Management thereof}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0647: {Migration mechanisms}
- G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays}
- G06F 16/152: {using file content signatures, e.g. hash values}
- G06F 16/2453: Query optimisation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Various embodiments for a disk-based merge for hash maps are described herein. An embodiment operates by identifying a plurality of hash maps with a plurality of disjunctions, ordering the one or more entries in each disjunction based on the hash value, and assigning an index value to each data value based on the ordering. The hash values of each of the entries may be moved to memory and compared for a particular disjunction. A data value with a lower hash value as determined based on the comparison is selected and stored in a merged hash map. The process is repeated until all the data values have been compared. A query is received, and processed based on the merged hash map.

## Claims

### Claim 1

A method, comprising:
identifying a plurality of hash maps stored in a memory of a computing system, each of the plurality of hash maps comprising a plurality of disjunctions, each of the plurality of disjunctions comprising one or more entries, wherein each of the one or more entries comprise a data value and a corresponding hash value;
ordering the one or more entries in each disjunction based on the hash value;
assigning an index value to each data value based on the ordering;
storing the data value across the plurality of disjunctions on a disk of the computing system, wherein the data values are grouped by disjunction and ordered based on their assigned index value;
selecting a subset of entries from a first disjunction of the plurality of disjunctions stored on the disk;
moving the selected subset of entries of the first disjunction from the disk to the memory;
comparing the hash values of each of the subset of entries;
selecting a data value based on the comparison, wherein the selected data value corresponds to a lower hash value as determined based on the comparison;
storing the selected data value in a merged hash map;
repeating the selecting the subset of entries, moving, comparing, selecting the data value based on the comparison, and the storing the selected data value in the merged hash map until all the data values have been compared;
receiving a query comprising one of a query data value or a query index value; and
returning a result to the query, wherein the query was processed based on the merged hash map.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
moving the merged hash map to the disk prior to the receiving.

### Claim 3 (depends on 1)

The method of claim 1, wherein the merged hash map comprises a corresponding hash value, index value, and data value for each of the one or more entries across the plurality of disjunctions, across the plurality of hash maps.

### Claim 4 (depends on 1)

The method of claim 1, wherein a first disjunction of a first hash map of the plurality of hash maps corresponds to a first disjunction of a second hash map of the plurality of hash maps.

### Claim 5 (depends on 1)

The method of claim 1, wherein the repeating comprises:
removing at least one of the subset of entries from the memory; and
loading a new entry from the disk onto the memory, wherein the comparing is performed on the new entry.

### Claim 6 (depends on 1)

The method of claim 1, wherein the hash value includes a number corresponding to a particular one of the plurality of disjunctions in which the hash value is stored.

### Claim 7 (depends on 1)

The method of claim 1, further comprising removing the index value of each data value from merged hash map.

### Claim 8

A system comprising at least one processor, the at least one processor configured to perform operations comprising:
identifying a plurality of hash maps stored in a memory of a computing system, each of the plurality of hash maps comprising a plurality of disjunctions, each of the plurality of disjunctions comprising one or more entries, wherein each of the one or more entries comprise a data value and a corresponding hash value;
ordering the one or more entries in each disjunction based on the hash value;
assigning an index value to each data value based on the ordering;
storing the data value across the plurality of disjunctions on a disk of the computing system, wherein the data values are grouped by disjunction and ordered based on their assigned index value;
selecting a subset of entries from a first disjunction of the plurality of disjunctions stored on the disk;
moving the selected subset of entries of the first disjunction from the disk to the memory;
comparing the hash values of each of the subset of entries;
selecting a data value based on the comparison, wherein the selected data value corresponds to a lower hash value as determined based on the comparison;
storing the selected data value in a merged hash map;
repeating the selecting the subset of entries, moving, comparing, selecting the data value based on the comparison, and the storing the selected data value in the merged hash map until all the data values have been compared;
receiving a query comprising one of a query data value or a query index value; and
returning a result to the query, wherein the query was processed based on the merged hash map.

### Claim 9 (depends on 8)

The system of claim 8, the operations further comprising:
moving the merged hash map to the disk prior to the receiving.

### Claim 10 (depends on 8)

The system of claim 8, wherein the merged hash map comprises a corresponding hash value, index value, and data value for each of the one or more entries across the plurality of disjunctions, across the plurality of hash maps.

### Claim 11 (depends on 8)

The system of claim 8, wherein a first disjunction of a first hash map of the plurality of hash maps corresponds to a first disjunction of a second hash map of the plurality of hash maps.

### Claim 12 (depends on 8)

The system of claim 8, wherein the repeating comprises:
removing at least one of the subset of entries from the memory; and
loading a new entry from the disk onto the memory, wherein the comparing is performed on the new entry.

### Claim 13 (depends on 8)

The system of claim 8, wherein the hash value includes a number corresponding to a particular one of the plurality of disjunctions in which the hash value is stored.

### Claim 14 (depends on 8)

The system of claim 8, further comprising removing the index value of each data value from merged hash map.

### Claim 15

A non-transitory computer-readable medium having instructions stored thereon that, when executed by at least one computing device, cause the at least one computing device to perform operations comprising:
identifying a plurality of hash maps stored in a memory of a computing system, each of the plurality of hash maps comprising a plurality of disjunctions, each of the plurality of disjunctions comprising one or more entries, wherein each of the one or more entries comprise a data value and a corresponding hash value;
ordering the one or more entries in each disjunction based on the hash value;
assigning an index value to each data value based on the ordering;
storing the data value across the plurality of disjunctions on a disk of the computing system, wherein the data values are grouped by disjunction and ordered based on their assigned index value;
selecting a subset of entries from a first disjunction of the plurality of disjunctions stored on the disk;
moving the selected subset of entries of the first disjunction from the disk to the memory;
comparing the hash values of each of the subset of entries;
selecting a data value based on the comparison, wherein the selected data value corresponds to a lower hash value as determined based on the comparison;
storing the selected data value in a merged hash map;
repeating the selecting the subset of entries, moving, comparing, selecting the data value based on the comparison, and the storing the selected data value in the merged hash map until all the data values have been compared;
receiving a query comprising one of a query data value or a query index value; and
returning a result to the query, wherein the query was processed based on the merged hash map.

### Claim 16 (depends on 15)

The non-transitory computer-readable medium of claim 15, the operations further comprising:
moving the merged hash map to the disk prior to the receiving.

### Claim 17 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the merged hash map comprises a corresponding hash value, index value, and data value for each of the one or more entries across the plurality of disjunctions, across the plurality of hash maps.

### Claim 18 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein a first disjunction of a first hash map of the plurality of hash maps corresponds to a first disjunction of a second hash map of the plurality of hash maps.

### Claim 19 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the repeating comprises:
removing at least one of the subset of entries from the memory; and
loading a new entry from the disk onto the memory, wherein the comparing is performed on the new entry.

### Claim 20 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the hash value includes a number corresponding to a particular one of the plurality of disjunctions in which the hash value is stored.