If you were interviewing to work at Percona, and I asked you “what does Using filesort mean in EXPLAIN,” what would you say?
I have asked this question in a bunch of interviews so far, with smart people, and not one person has gotten it right. So I consider it to be a bad interview question, and I’m going to put the answer here. If anyone gets it wrong from now on, I know they don’t read this blog!
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.
If the sort is bigger than the sort buffer, it is performed a bit at a time, and then the chunks are merge-sorted to produce the final sorted output. There is a lot more to it than this. I refer you to Sergey Petrunia’s article on How MySQL executes ORDER BY. You can also read about it in our book, but if you read Sergey’s article you won’t need to.