Improving filesort performance in MySQL

I recently filed Bug #37359 filesort can be more efficient based on some performance work with an industry standard benchmark. Read on if the internals of how MySQL implements filesort interests you.

Filesort, as the name implies, is used to sort records when there is an ORDER BY clause in the query. The reason it has the prefix "file" is because temporary files may be used to store intermediate results. filesort() uses a per thread sort buffer of size sort_buffer_size to sort the table. filesort() is implemented in sql/filesort.cc.

filesort may not know how many records need to be sorted. It asks the storage engine for an estimate of the number of records in the table via estimate_rows_upper_bound(). If the number of records that fit in the sort buffer is less than the estimate, filesort will use temporary files to store intermediate results. The flow is as follows (or atleast the important steps to understand the bug mentioned above)

  1. records = Min(estimate records in table, records that can fit in sort buffer)
  2. Initialize the sort buffer via make_char_array
  3. Do the actual sort.
A pictorial way of looking at this is shown below. Width of the box is proportional to time taken to execute the function, and height is the stack depth. Move the mouse over the image to see more details. Source: http://blogs.sun.com/realneel/resource/filesort_trace.svg

Initializing the sort buffer can be very expensive when the estimate for the number of rows is off. For example, in my benchmark, the table has 210 Million rows. Innodb returns 210 Million for estimate_rows_upper_bound(). The actual number of rows that fulfill the WHERE clause of my query is 3!. For a default sort buffer size of 2MB, the number of rows that fit in the sort buffer is 70,000. So filesort() unnecessarily initializes space for 70,000 rows, and does the sort. You might think initializing space for 70,000 rows is not a big deal, but when it constitutes 10% of the query execution time, it IS a big deal.

So how can we improve this?

  • Do not use filesort! Rewrite your query to make use of an index, or add an index which will help the optimizer avoid the filesort.
  • For cases where the estimate for number of queries is wrong, reduce the sort buffer size to a low value (mysql> set global sort_buffer_size=32\*1024;)
  • Enhance estimate_rows_upper_bound() to passdown the WHERE clause so that the storage engine can give a better estimate.
Comments:

Sorry for stupid question, how can I see your svg image?

Posted by xuekun on June 25, 2008 at 07:09 PM PDT #

I think this is the best visual explanation I've seen of how this works and why the sort buffer size is so important. I've seen people setting it to 128MB (!!!!). Explaining why that's a bad idea is always time-consuming.

Posted by Xaprb on June 25, 2008 at 10:06 PM PDT #

xuekun, you can use firefox to view the svg file.

Posted by realneel on June 25, 2008 at 11:17 PM PDT #

Baron, Thanks! Setting the sort_buffer_size to 128MB would have definitely killed the performance of my benchmark. BTW, you can generate your own callstacks using ruby and dtrace! checkout http://blogs.sun.com/realneel/entry/visualizing_callstacks_via_dtrace_and

Posted by realneel on June 25, 2008 at 11:26 PM PDT #

Post a Comment:
Comments are closed for this entry.
About

realneel

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today