Find pairs in 2 files that are too large to fit in memory

Question

I'm looking for a memory efficient way to find pairs in 2 possibly very large files (can be as large as 1TB each) that do not fit into memory. For the sake of simplicity let's say the file contains just integers, but they are unordered and not each integer needs to exist in the other file.

I thought about using an external sorting to sort each file, then read the first entry from each file, and use the following pseudologic:

(read_file() would return something that which you can compare, and call advance() on to shift the cursor to the next line)

left_file = read_file("file-1.txt")
right_file = read_file("file-2.txt")

while (there_are_entries_in_either_file):
    if left_file == right_file:
        # write match to output
        left_file.advance()
        right_file.advance()
    elif left_file < right_file:
        # if left is smaller then we can skip that entry
        left_file.advance()
    elif right_file < left_file:
        # if right is smalelr then we can skip that entry
        right_file.advance()

This would in theory work, but would limit me to a single thead, which would not be very fast.

The process with example data would look like (left column is file 1, right column is file 2)

1   1
2   5
3   6
5   7

1. We read 1 from both left and right, it matches so we advance both files
2. We read 2 from left and 5 from right, left is smaller, so we discard the 2 and advance left
3. We read 3 from left and still have the 5 from right, left is stills maller so we discard 3 and advance left
4. We read 5 from left and still have the 5 from right, which now matches so we advance both
5. repeat...

Are there any algorithms that would allow me to match pairs in a multithreaded way?

Answer 1

The correct way of solving this is using MapReduce which will help to divide these huge files into smaller chunks and once you have the result, you merge them back into a single output.

If you are not looking to setup a cluster for this purpose , you could follow the same algorithm on a single node as well.

Rough pseudocode:

1. Split both the files into x parts. (say 1000 1GB files or maybe even smaller).
2. Write a logic that takes 1 part file from each of the 2 sets and tries to match them by your logic. If matches are there, store them in part_a1_b1_output. Also, make sure that if splitting leads to some metadata loss, try to find an alternate way to compute it.
3. Once you have all the output files ready, do an n-way merge to get the final result.

But if you use an actual cluster, this can be rather quickly.