3 ms·

Isn't the mapreduce sort NlogN in the number of entries? That would make 1e13 log 1e13/(1e10 log 1e10) 68s/4 = 6.1h. So they were actually faster than the possi

• russell 18y ago
  Sounds dead on to me. The typical sort is O(N logN). O can be slightly different between the 1T runs and 1P runs, e.g. slightly difference latency or pattern of disk failures. Every sort is sensitive to the data distribution. There is probably an interesting distribution of results across the runs.
• bd 18y ago
  They mention that they did some extra optimizations ("stragglers") for petabyte test (that were not there yet for the terabyte test).
• jwilliams 18y ago
  This is a really good point. I was assuming that the sort was actually a partial sort - returning the top "x" (admittedly - even then isn't linear). However, I was also assuming (n << x), which would almost certainly be the case with a large data set. It's a fairly common approach, but not sure why I automatically assumed it. If the sort is complete, then yeah, that changes things.