4

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
    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.

  • 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
0

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

0

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.

-1

Would this not be something suitable for Spark on an Hadoop file system? I suggest that you get Apache Zeppelin (which is a Jupyter style notebook for Spark) and start playing around with some tutorials. Spark is the way to go for Big Data.

  • Hello and welcome to the U&L stack exchange site! Please review the Help Center to get information on how to best post to this site. To get to your answer, you should try to add additional context as to why you think this is an answer. Please edit your post to include all relevant steps to accomplish this solution. Thank you! – kemotep Dec 13 '18 at 15:21

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.