5

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.

1
  • 2
    How large are your chunks? Are they smaller than what sort would have made? It sounds like you are basically mimicking what plain sort would have done anyway...
    – Kusalananda
    Dec 3 '18 at 11:27
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.

1
  • No sorting needs to be done at all as the chunks are fully sorted. All that is needed is a merge: basically, open all files, read a line from each, and whichever is "lowest" compared to the others is output. Repeat until all input is exhausted. I could probably code this myself, but I want to check first that there's nothing already available.
    – rowan194
    Dec 3 '18 at 14:05
2

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.

0

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

1
  • I can post the C++ source that I am using. I expect users to compile it and make any modifications they find necessary, as their data may vary from the data I have. My program makes certain hard coded assumptions assuming the maximum line width, but should cover most cases. There is one file handle open for each input file, so the system limit can be exceeded. It is optimized for cases where the input files are fairly disjoint. I'm new to this site. Can someone tell me how to upload the code?
    – Bruce Amos
    Dec 11 '21 at 1:12
-1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.