MySQL Bugs: #37359: filesort can be more efficient

Bug #37359	filesort can be more efficient
Submitted:	12 Jun 2008 2:55	Modified:	12 Jun 2008 17:34
Reporter:	Neel Nadgir
Status:	Verified
Category:	Server: Optimizer	Severity:	S4 (Feature request)
Version:	6.0.5	OS:	Any
Assigned to:		Target Version:
Tags:	innodb, filesort
Triage:	Triaged: D5 (Feature request)

Description:
filesort() initializes space for 
MIN(Estimate rows in table, max rows that can fit in sort buffer) rows 
before doing the sort. For queries that have a "where" clause, the 
number of rows estimated by estimate_rows_upper_bound can be much 
higher than rows that match the where clause.

The initialization is done via make_char_array() in filesort.cc and is
very expensive when the estimate is off.

For a industry standard workload, the following query
SELECT COL1 FROM BAR WHERE INDEXED_COL_ID = ? ORDER BY NON_INDEXED_FOO
uses filesort. Table BAR has 210 Million rows.

Tracing the code, we see that innodb returns 210 Million for 
estimate_rows_upper_bound(). The number of rows that match 
is 3. For a 2MB sort_buffer_size (default), we end up initializing 
75,000 rows in make_char_array(), whereas we will only use 3!

We can reduce the sort_buffer_size to 32k (lowest allowable value), but
even then we end up initializing 1200 entries.

By reducing the sort_buffer_size to 32k, we see a 18% improvement in 
benchmark throughput.

How to repeat:
The benchmark is quite hard to setup. Please email for details.

Suggested fix:
Possible suggestions are
1. Passdown where clause to estimate_rows_upper_bound() so that it can
   give a better estimate
2. Dont pre-initialize.. Initialize the sort area as records are read.

Thank you for a reasonable feature request. I am not sure that dynamic allocation is a
good solution for a general case. 

Maybe we should just add a session variable/optimizer hint to control maximum number of
entires pre-allocated for cases like yours.

Allocation is not the problem; initializing it is the problem.
The line that takes up the most time is 
<code>while (fields--) *(pos++) = (char_pos+= length); </code> in 
make_char_array() function.

A link to a callstack profile is at 
http://blogs.sun.com/realneel/resource/filesort_trace.svg
(Width of box is proportional to time consumed, and functions stack
up as they are caled). The trace is with a debug build (compiler 
inlines make_char_array with optimization), so the numbers will 
be a higher.

The function estimate_rows_upper_bound() should return a proper estimate in innodb.

The function estimate_rows_upper_bound() should return a proper estimate in innodb.

Igor, it does. It is defined to return the number of rows in the table.
The better estimation is disabled in filesort - search for #ifdef CAN_TRUST_RANGE.

One workaround for this is SHOW GLOBAL STATUS and look at Sort_merge_passes. If the value
is zero or very few per minute, reduce the sort_buffer_size value until you start to see
a few Sort_merge_passes each minute. The value that you are at will still probably be
larger than ideal but it'll be closer than not checking. Sort merge passes are often not
expensive, so don't be reluctant to experiment with lower values of sort_buffer_size.

It's also quite common for production servers to benefit from larger values, so check
that as well. Also note that you can set it larger or smaller for individual connections
as required for the work that they are doing.

This isn't specific to this bug report, it's general server tuning guidance. It doesn't
eliminate the problem, just may reduce the size of the area being initialised and the
speed penalty.

Bug http://bugs.mysql.com/bug.php?id=39401 it was marked as duplicate of this one.

See this blog entry for more discussion:
http://blogs.sun.com/realneel/entry/improving_filesort_performance_in_mysql