Baron Schwartz over on the MySQL Performance blog has written a great post about exactly what a filesort in MySQL means. He mentions that he commonly asks the question in interviews and the interviewee rarely knows the answer:
The usual answer is something like “rows are being placed into a temporary table which is too big to fit in memory, so it gets sorted on disk.” Unfortunately, this is not the same thing. First of all, this is Using temporary. Secondly, temporary tables may go to disk if they are too big, but EXPLAIN doesn’t show that. (If I interview you, I might ask you what “too big” means, or I might ask you the other reason temporary tables go to disk!)
The truth is, filesort is badly named. Anytime a sort can’t be performed from an index, it’s a filesort. It has nothing to do with files. Filesort should be called “sort.” It is quicksort at heart.
There you have it. Filesort actually uses the quicksort algorithm since the database is not properly indexed for the queries you’re performing! Make sure you’re setting indexes correctly to optimize performance!
I’ve commonly seen this indicated when EXPLAIN’ing queries, so it’s nice to see what the correct answer is.