How to merge pre-sorted files into a single BIG file, without excessive memory or temporary disk use

Question

I'm trying to sort (and ideally remove duplicate lines) from a 1.4TB file.

Splitting and sorting the individual chunks is not an issue, but reassembling them is turning out to be a challenge. I expected from the man page that 'sort -m' (Under FreeBSD 11) would do a simple merge, creating an aggregate perfectly sorted output, optionally suppressing duplicates with the -u option.

But after leaving it to run for a while, I discovered that sort had (so far) generated several hundred gigs worth of temporary files, just as if it was sorting the input like normal.

I don't have enough disk space to be able to store the same data 3 times. Are there any utilities that can do a simple merge of already sorted files, without requiring temporary disk space?

=== Outcome ===

I ended up using a "standard" sort. It took around 50 hours of high CPU and disk load to process, including the generation of several hundred temporary files. This was despite the input already being perfectly sorted. I'm still interested in learning if there is a simple utility to neatly merge pre-sorted files.

Answer 1

Doing some more experimenting today with different data, I believe I may have found the problem: by default, sort (BSD) will only open 16 files at once (the man page seems to imply this includes both input and temporary files).

The --batch-size= switch will allow this count to be increased.

Using pre-sorted files of 100MB in size:

1. sort -u -m <...15 filenames...>

   • immediate output

2. sort -u -m <...16 filenames...>

   • appears to process input in at least two separate chunks, including intermediate use of temporary files

3. sort --batch-size=20 -u -m <...16 filenames...>

   • immediate output

Note that I have not been able to test this on the original data, but I'm fairly sure this was the issue.

Hope this helps someone with the same problem.

Answer 2

Your requirements (so spare ram/storrage/cloud) is going to make this really slow but it is possible by writing your own file system driver. However if you have the time/skill to do that it would be faster/cheaper to rent/buy/sell/return a $37 2TB drive and use

https://en.m.wikipedia.org/wiki/External_sorting

A workaround might be zram and/or 7z/fs-compression if the file is compressable, you could make room for a 2nd copy

https://en.m.wikipedia.org/wiki/Zram

https://en.m.wikipedia.org/wiki/Category:Compression_file_systems

If there is space for output without removing input and input is pre-sorted then it's trivial.

Answer 3

I have a similar problem while trying to solve a very large sliding block puzzle. Currently I have to merge about 100 sorted files, each containing about 60 million positions and occupying 15 gigabytes. The files are individually sorted without duplicates, but different files can have the same record.

I wrote a utility in C++ which basically opens all the files and reads one record at a time from each. At each step, it finds the alphabetically earliest one (using the SHELL sort) and writes that record. It reads in the next record from that file and any other files that also had the same record. It ran for 5 hours on a new MAC laptop in order to get the answer.

Memory requirements are not large and each file is only read once. It runs far faster than a comm solution which is limited to two files at a time and involves multiple reading of files.

The program has been compiled and run on two computers: A MAC laptop where the program was originally developed, and a MAC M1. The largest job run so far had 676 files, each with about 60 million records or size 1.5 GB and it ran in a little over 10 hours.

Source code: bruceamos/comb

Answer 4

I think what you're looking for is comm. I'm not sure how much memory or temp space it uses, but considering the requirement that the input files are sorted and that the people who write these utilities aren't stupid, I'd bet it's really efficient.

You can remove duplicates with uniq because that also assumes sorted input.

https://www.tutorialspoint.com/unix_commands/comm.htm