MYSQL ORDER BY Performance We have a query like this:

SELECT 
 PROJECT.PROJECTID, REQUEST.REQUESTID,
 SAMPLE.SAMPLEID,SAMPLE.OTHERSAMPLEID, 
 ILLUMINASEQPROTOCOL2.SAMPLEID 
FROM 
 ILLUMINASEQPROTOCOL2,
 PROJECT,
 SAMPLE,
 REQUEST, 
 ANCESTORS A1, 
 ANCESTORS A2, 
 ANCESTORS A3 
WHERE (
 ILLUMINASEQPROTOCOL2.RECORDID = A1.RECORDID AND 
 A1.ANCESTORID = SAMPLE.RECORDID AND 
 SAMPLE.RECORDID = A2.RECORDID AND 
 A2.ANCESTORID = REQUEST.RECORDID AND 
 REQUEST.RECORDID = A3.RECORDID AND 
 A3.ANCESTORID = PROJECT.RECORDID) 
AND  (
 (((ILLUMINASEQPROTOCOL2.RecordId &gt; 0) AND  
  ((SAMPLE.EXEMPLARSAMPLETYPE LIKE 'DNA') AND  
  (REQUEST.RecordId &gt; 0))) 
 AND  (PROJECT.RecordId &gt; 0))
) 
ORDER BY SAMPLE.RECORDID LIMIT 0,501;


The RecordId column on all the tables is indexed as is AncestorId.  No other columns are indexed.  Here is what makes no sense.  When i have the query as above, it takes 130 seconds to run on our machines here.  The ORDER BY is what takes all the time since if I remove it the query runs instantly.  But what is weirder is if I change to the ORDER BY to use a non-indexed column like SAMPLE.SAMPLEID, it also comes back instantly.

So when I run this wanting to ORDER BY an indexed field it is MUCH slower than ordering by a non-indexed field.  Any help greatly appreciated.
What sometimes works in this situation is

SELECT * FROM
(
SELECT 
 PROJECT.PROJECTID, REQUEST.REQUESTID,
 SAMPLE.SAMPLEID,SAMPLE.OTHERSAMPLEID, 
 ILLUMINASEQPROTOCOL2.SAMPLEID 
FROM 
 ILLUMINASEQPROTOCOL2,
 PROJECT,
 SAMPLE,
 REQUEST, 
 ANCESTORS A1, 
 ANCESTORS A2, 
 ANCESTORS A3 
WHERE (
 ILLUMINASEQPROTOCOL2.RECORDID = A1.RECORDID AND 
 A1.ANCESTORID = SAMPLE.RECORDID AND 
 SAMPLE.RECORDID = A2.RECORDID AND 
 A2.ANCESTORID = REQUEST.RECORDID AND 
 REQUEST.RECORDID = A3.RECORDID AND 
 A3.ANCESTORID = PROJECT.RECORDID) 
AND  (
 (((ILLUMINASEQPROTOCOL2.RecordId &gt; 0) AND  
  ((SAMPLE.EXEMPLARSAMPLETYPE LIKE 'DNA') AND  
  (REQUEST.RecordId &gt; 0))) 
 AND  (PROJECT.RecordId &gt; 0))
) AS mytable 
) ORDER BY SAMPLE.RECORDID LIMIT 0,501;


i.e. transform your original query into a subquery within the outer SELECT. Then, put your ORDER BY and LIMIT as subclauses of your outer SELECT.

This should eliminate the bottleneck with the ORDER BY and LIMIT. The reason your query slows down with the ORDER BY is that the query has to retrieve all records and then SORT them - without the ORDER BY, the system can just spit out the first 500 records. 

It is puzzling that you do have indexes on the relevant fields. If what I have suggested doesn't work, you could post the table structures and the query execution plan.