Hmmmm - "order by" . . . . . 400,000 records . . . tell me - what indexes are on the table(s) you are doing your SELECT on? I have not used MySQL, but I suspect its query optimiser is not as flash as with (say), Oracle, Informix or DB/2.

You may need to look at your physical data base design, to make sure your queries are not scanning through the whole table multiple times.