Unix sort keys cause performance problems
- by KenFar
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.
