Disk-based merge for hash maps

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.

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.