title: What is the most efficient way to do a sorted reduce in PySpark?
body: <p>I am analyzing on-time performance records of US domestic flights from 2015. I need to group by tail number, and store a date sorted list of all the flights for each tail number in a database, to be retrieved by my application. I am not sure which of two options for achieving this is the best one.</p>
  
  <pre><code># Load the parquet file
  on_time_dataframe = sqlContext.read.parquet('../data/on_time_performance.parquet')
  
  # Filter down to the fields we need to identify and link to a flight
  flights = on_time_dataframe.rdd.map(lambda x: 
    (x.Carrier, x.FlightDate, x.FlightNum, x.Origin, x.Dest, x.TailNum)
    )
  </code></pre>
  
  <p>I can achieve this in a reduce sort...</p>
  
  <pre><code># Group flights by tail number, sorted by date, then flight number, then 
  origin/dest
  flights_per_airplane = flights\
    .map(lambda nameTuple: (nameTuple[5], [nameTuple]))\
    .reduceByKey(lambda a, b: sorted(a + b, key=lambda x: (x[1],x[2],x[3],x[4])))
  </code></pre>
  
  <p>Or I can achieve it in a subsequent map job...</p>
  
  <pre><code># Do same in a map step, more efficient or does pySpark know how to optimize the above?
  flights_per_airplane = flights\
    .map(lambda nameTuple: (nameTuple[5], [nameTuple]))\
    .reduceByKey(lambda a, b: a + b)\
    .map(lambda tuple: 
      (
        tuple[0], sorted(tuple[1], key=lambda x: (x[1],x[2],x[3],x[4])))
      )
  </code></pre>
  
  <p>Doing this in the reduce seems really inefficient, but in fact both are very slow. sorted() looks like the way to do this in the PySpark docs, so I'm wondering if PySpark doesn't make this kosher internally? Which option is the most efficient or the best choice for some other reason?</p>
  
  <p>My code is also in a gist here: <a href="https://gist.github.com/rjurney/af27f70c76dc6c6ae05c465271331ade" rel="noreferrer">https://gist.github.com/rjurney/af27f70c76dc6c6ae05c465271331ade</a></p>
  
  <p>If you're curious about the data, it is from the Bureau of Transportation Statistics, here: <a href="http://www.transtats.bts.gov/DL_SelectFields.asp?Table_ID=236&amp;DB_Short_Name=On-Time" rel="noreferrer">http://www.transtats.bts.gov/DL_SelectFields.asp?Table_ID=236&amp;DB_Short_Name=On-Time</a></p>