apache/spark — pull request #1562 by mengxr (2014-07-24 02:53:05+00:00)
Title: [SPARK-2568] RangePartitioner should run only one job if data is balanced

As of Spark 1.0, RangePartitioner goes through data twice: once to compute the count and once to do sampling. As a result, to do sortByKey, Spark goes through data 3 times (once to count, once to sample, and once to sort).

`RangePartitioner` should go through data only once, collecting samples from input partitions as well as counting. If the data is balanced, this should give us a good sketch. If we see big partitions, we re-sample from them in order to collect enough items.