MySQL profile on query "Creating Sort Index" using 75% of the total time

We are trying to figure how to optimize a query (taking around 100ms), and running profile we see Creating Sort Index using 75% of the total time. First, what exactly effects creating the sort index? Is it disk/io?

Second, is there any optimization we can make to the query itself?

SELECT r.`id`, 
       r.name, 
       r.public_uri, 
       rv.version, 
       rv.interpreter, 
       rv.notes, 
       rv.content, 
       r.added, 
       r.added_by, 
       r.modified, 
       r.modified_by, 
       r.public, 
       r.public_by
  FROM recipe_heads rh, 
       recipes r, 
       recipe_versions rv
 WHERE rh.recipe = r.`id` 
   AND rh.recipe_version = rv.`id` 
   AND r.`id` = rv.recipe
ORDER BY r.added DESC

Explain:

We had similar problem for huge queries. Often queries ran for hours (upto 7-8) depending upon the load on DB for 400M rows. However, our goal was to achieve group results, such as select col1, col2, col3, count(1), count(distinct col4) from table group by 1,2,3.

Underlying problem is same as yours though, as in both case DB sorts(orders) the results internally.

• How creating sort index work.

On mysql website it says "The thread is processing a SELECT that is resolved using an internal temporary table." Per my algorithm understanding, system is most likely splitting data into chunks, read from disk this chunks one by one, sorting individual chunks, putting back into some temporary disk space and so on. System does this for all chunks and eventually performs merge sort. This involves extensive read/writes.

A possible solution can be to increase your memory for DB (so that it can create bigger chunks that can stay in memory) or if you have a bigger memory somewhere else, you can program the solution by streaming from DB. This can be achieved in nlogn time.

Programmatically, I could reduce time from on an average of 2 hrs to a consistent 7.5 minutes.

StackExchange Database Administrators Q#90061, answer score: 9