Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

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']
    Outputs:
         - 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:
    try:
        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]
                key_fields.pop(i+1)
                key_types.pop(i+1)
                continue
        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
2  
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
show 1 more comment

2 Answers

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

    Examples:

    • -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
add comment

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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