Super User is a question and answer site for computer enthusiasts and power users. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My data:

  • It's a 71 MB file with 1.5 million rows.
  • It has 6 fields
  • All six fields combine to form a unique key - so that's what I need to sort on.

Sort statement:

sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 -k6,6 -o output.csv input.csv

The problem:

  • If I sort without keys, it takes 30 seconds.
  • If I sort with keys, it takes 660 seconds.
  • I need to sort with keys to keep this generic and useful for other files that have non-key fields as well. The 30 second timing is fine, but the 660 is a killer.

More details using unix time:

  • sort input.csv -o output.csv = 28 seconds
  • sort -t ',' -k1 input.csv -o output.csv = 28 seconds
  • sort -t ',' -k1,1 input.csv -o output.csv = 64 seconds
  • sort -t ',' -k1,1 -k2,2 input.csv -o output.csv = 194 seconds
  • sort -t ',' -k1,1 -k2,2 -k3,3 input.csv -o output.csv = 328 seconds
  • sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 input.csv -o output.csv = 483 seconds
  • sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 input.csv -o output.csv = 561 seconds
  • sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 -k6,6 input.csv -o output.csv = 660 seconds

I could theoretically move the temp directory to SSD, and/or split the file into 4 parts, sort them separately (in parallel) then merge the results, etc. But I'm hoping for something simpler since looks like sort is just picking a bad algorithm.

Any suggestions?

Testing Improvements using buffer-size:

  • With 2 keys I got a 5% improvement with 8, 20, 24 MB and best performance of 8% improvement with 16MB, but 6% worse with 128MB
  • With 6 keys I got a 5% improvement with 8, 20, 24 MB and best performance of 9% improvement with 16MB.

Testing improvements using dictionary order (just 1 run each):

  • sort -d --buffer-size=8M -t ',' -k1,1 -k2,2 input.csv -o output.csv = 235 seconds (21% worse)
  • sort -d --buffer-size=8M -t ',' -k1,1 -k2,2 input.csv -o ouput.csv = 232 seconds (21% worse)
  • conclusion: it makes sense that this would slow the process down, not useful

Testing with different file system on SSD - I can't do this on this server now.

Testing with code to consolidate adjacent keys:

def consolidate_keys(key_fields, key_types):
""" Inputs:
         - key_fields - a list of numbers in quotes: ['1','2','3']
         - key_types - a list of types of the key_fields: ['integer','string','integer']
         - key_fields - a consolidated list:  ['1,2','3']
         - key_types - a list of types of the consolidated list: ['string','integer']
assert(len(key_fields) == len(key_types))

def get_min(val):
    vals = val.split(',')
    assert(len(vals) <= 2)
    return vals[0]

def get_max(val):
    vals = val.split(',')
    assert(len(vals) <= 2)
    return vals[len(vals)-1]

i = 0
while True:
        if ( (int(get_max(key_fields[i])) + 1) == int(key_fields[i+1])
        and  key_types[i] == key_types[i+1]):
                key_fields[i] = '%s,%s' % (get_min(key_fields[i]), key_fields[i+1])
                key_types[i]  = key_types[i]
        i = i+1
    except IndexError:
        break  # last entry

return key_fields, key_types

While this code is just a work-around that'll only apply to cases in which I've got a contiguous set of keys - it speeds up the code by 95% in my worst case scenario.

share|improve this question
What's wrong with -k1,6? – Ignacio Vazquez-Abrams Jun 15 '12 at 20:26
The sort is performed within a tool that allows the user to configure which columns are keys. So, it must potentially support multiple, non-continuous keys. I suppose I could write the code to consolidate that when the keys are adjacent. – KenFar Jun 15 '12 at 22:13
Any reasons to not feed the .csv into something like sqlite and build indizes etc on that? – akira Jun 16 '12 at 19:35
I need to access 100% of the data - so indexes won't help me. And in fact, if there's just 1 key, the performance is reasonable. – KenFar Jun 16 '12 at 20:05
I dont understand your argument: where do you lose any data when storing it in something otter than plain .csv and accessing ist via SQL? – akira Jun 16 '12 at 20:26

I have no idea how sort works internally and no 71 MB .csv file at hand to test it, but here's a couple of things you can try:

  • Set --buffer-size (-S) to something big enough to avoid reading from the hard drive more than once.

    Start with -S=1G and work your way down.

  • Eliminate the keys one by one to see if there's a specific one causing problems (e.g. the integers).


    • -k1,1 -k2,2 -k3,3 -k4,4 -k5,5

    • -k1,1 -k2,2 -k3,3 -k4,4 -k6,6

  • Unless this is unacceptable for the integers, set the --dictionary-order (-d) switch.

share|improve this answer
I'm assuming the problem is algorithmic, but I'll try giving it more memory. I already tried it with & without numeric sorting and found no difference. – KenFar Jun 14 '12 at 23:47

Specifying multiple keys requires the data be sorted first by the first key, then items with equal first keys are sorted by the 2nd key, etc. That's a lot of data moving around in RAM. If any of it gets paged out, the algorithm goes from being bounded my memory access times (measured in nanoseconds) to being bounded by disk access times (measured in milliseconds).

share|improve this answer
That makes sense - though the performance is far worse than just 1 pass per key. For example one key takes 30 seconds while three keys takes 10 times as long, or 300 seconds. These seems extremely repeatable and unaffected by using a buffer_size larger than the data. – KenFar Jun 16 '12 at 23:20

I faced precisely this problem, and after taking a quick look at the sort.c source code, noticed that the part that searches a string for keys if the key(s) are not consecutively at the beginning of the string, is a plain string search (till the delimiter). And considering that the sort is a n(log n) operation, this kind of search for keys within a line might be repeated multiple times while comparing two lines, each time a line is compared to some other.

So, I used a combination of awk (to prepend keys consecutively), sort (on first x fields) and cut (to cut out the prepended keys) to prepend sort keys consecutively and remove them after the job is done. Got an improvement of 3x for my use case.

share|improve this answer
An example of the approach in the answer would be useful. – suspectus Feb 25 '15 at 9:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .