Bug #46011 Regression after applying fix for bug #45828
Submitted: 7 Jul 2009 14:05 Modified: 12 Oct 2010 8:17
Reporter: Philip Stoev Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.1-bugteam OS:Any
Assigned to: Tor Didriksen CPU Architecture:Any
Tags: GROUP BY, order by
Triage: Triaged: D3 (Medium) / R5 (Severe) / E5 (Major)

[7 Jul 2009 14:05] Philip Stoev
Description:
After applying the fix for bug#45828, the following query:

SELECT `int` FROM `table1000000_innodb_int_autoinc` WHERE ( `int_key` BETWEEN 10 AND 168 ) AND ( `int_key` > 113 ) ORDER BY `pk`

against a table with 1M rows is more than 2 times slower as compared to the 
current 5.1-bugteam.

with the patch:

mysql> explain SELECT `int` FROM `table1000000_innodb_int_autoinc` WHERE ( `int_key` BETWEEN 10 AND 168 ) AND ( `int_key` > 113 ) ORDER BY `pk` \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: table1000000_innodb_int_autoinc
         type: range
possible_keys: int_key
          key: int_key
      key_len: 5
          ref: NULL
         rows: 24738
        Extra: Using where; Using filesort
1 row in set (0.00 sec)

without the patch:

mysql> explain SELECT `int` FROM `table1000000_innodb_int_autoinc` WHERE ( `int_key` BETWEEN 10 AND 168 ) AND ( `int_key` > 113 ) ORDER BY `pk` \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: table1000000_innodb_int_autoinc
         type: index
possible_keys: int_key
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 1000422
        Extra: Using where
1 row in set (0.00 sec)

As discussed with Joro, this is caused by a bad row estimate, in turn caused by the compound predicate in the WHERE. Nevertheless, it may be considered a regression from the viewpoint of the customer.

How to repeat:
The datadir with the table will be uploaded shortly.
[7 Jul 2009 14:11] Philip Stoev
Datadir is at http://mysql-systemqa.s3.amazonaws.com/var-bug46011.zip
[7 Jul 2009 15:09] Philip Stoev
I just got a query with a 240-fold performance regression:

SELECT * FROM `table1000000_innodb_int_autoinc` WHERE ( `int_key` < 135069696 ) AND ( `int_key` BETWEEN 6 AND 8 ) GROUP BY `pk` LIMIT 208;

Unlike any other automatically-generated queries, which may have two BETWEENs and other weird stuff, this one is fairly realistic and I can totally imagine that a customer will need to run it.

with patch, it takes 1.74:

mysql> explain SELECT * FROM `table1000000_innodb_int_autoinc` WHERE ( `int_key` < 135069696 ) AND ( `int_key` BETWEEN 6 AND 8 ) GROUP BY `pk` LIMIT 208\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: table1000000_innodb_int_autoinc
         type: range
possible_keys: int_key
          key: int_key
      key_len: 5
          ref: NULL
         rows: 6110
        Extra: Using where; Using filesort
1 row in set (0.00 sec)

without patch, it takes less than 0.01 wallclock seconds:

mysql> explain SELECT * FROM `table1000000_innodb_int_autoinc` WHERE ( `int_key` < 135069696 ) AND ( `int_key` BETWEEN 6 AND 8 ) GROUP BY `pk` LIMIT 208\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: table1000000_innodb_int_autoinc
         type: index
possible_keys: int_key
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 34052
        Extra: Using where
1 row in set (0.00 sec)
[7 Jul 2009 15:15] Philip Stoev
Replacing GROUP BY `pk` with ORDER BY `pk` produces the same performance profile, and makes the query fairly aestetically correct.
[7 Jul 2009 16:53] Philip Stoev
Here is the test setup:

database:

1M rows, a PK, an integer key and a non-keyed integer column;

data:

33% digits 0..9, 33% tiny signed integers -127..+127 ; 33% signed integers 

queries:

SELECT * or SELECT on a single field +
WHERE with a single or a compound (with AND) predicate +
ORDER BY or GROUP BY by key +
no LIMIT or random LIMIT from 1 to a large insigned integer

A total of 10000 queries were run, out of which 194 took more than 1 second to execute and were thus suitable for comparison. The ratio in running time between the patched and the unpatched version is as follows:

ratio	count	%
0	45	23.20%
0.6	1	0.52%
0.7	2	1.03%
0.8	4	2.06%
0.9	5	2.58%
1	113	58.25%
1.1	10	5.15%
1.2	1	0.52%
1.3	1	0.52%
1.4	2	1.03%
1.5	1	0.52%
1.9	1	0.52%
2	1	0.52%
3.3	1	0.52%
5.4	1	0.52%
7.8	1	0.52%
9.8	1	0.52%
10.4	1	0.52%
11.4	1	0.52%
242	1	0.52%

A ratio of 0 means that after the patch the query became essentially instantaneos. A ratio of 0.9 means the query was 10% faster with the patch, 1 means there was no change in the runtime, 1.1% means 10% slower with the patch and ratio 242 signifies a 242-fold slow-down with the patch.

From this data it is obvious that many queries benefited immensely from the patch, however there are still 7% queries that became slower by 20% or more with some extreme values present.

A paper by Microsoft appears to indicate that they set a goal of less than 5% regressions when they modify their optimizer, however they use real customer databases and queries to compute the regression percentage, rather than a purely random, unintelligent workload.

Since Robert McNamara died yesterday, a word of caution with respect to statistics is in order. He thought that he would be able to win the Vietnam war using flow charts, histograms and statistics. Instead, 20 years later, someone recognized him on a ferry and tried to throw him overboard. He died a "haunted man" (NYT).
[7 Jul 2009 17:47] Philip Stoev
Sinisa, running this test with MyISAM does not cause any measurable regressions to be reported (e.g. at least a two-fold slow-down on a query that takes at least 1 second).
[7 Jul 2009 17:57] Philip Stoev
Sinisa, I ran ANALYZE table on the MyISAM tables (took less than 1 second to complete, so I assume it did not do much) however the results are still the same -- no measurable regressions.

I can provide you with the test framework so that you can experiment further.
[7 Jul 2009 18:06] Sinisa Milivojevic
Philip,

Thank you.

No need for me to repeat anything. The fact that MyISAM does not produce any regression is more then good enough for me ....
[8 Jul 2009 8:54] Philip Stoev
Here are some more numbers, as requested by Joro:

On 148 random queries that took more than 1 second against random data:

Queries that were more than 10% faster - 17.5% . Average speed-up: 11.4 times.
Queries that were more than 10% slower - 13.5% . Average slow-down: 2.6 times.
[8 Jul 2009 9:14] Philip Stoev
The test framework has been uploaded to mysql-test-extra-6.0. To reproduce, please branch the mysql-test-extra-6.0 tree, and cd to mysql-test/gentest. Then run:

$ perl runall.pl \
--basedir1=/build/bzr/bug45828/ \
--basedir2=/build/bzr/5.1-bugteam/ \
--vardir1=/tmp/vardir1 \
--vardir2=/tmp/vardir2 \
--grammar=conf/bug45828.yy \
--gendata=conf/bug45828.zz \
--threads=1 \
--validator=ExecutionTimeComparator \
--queries=100000

Populating the databasec can take a while, so you can use --start-dirty on subsequent runs in order to reuse the existing populated vardirs.
[29 Jan 2010 16:54] Sveta Smirnova
See also bug #47884
[2 Feb 2010 19:13] Sinisa Milivojevic
Turns out this is not a regression of #45828 ... 

This is because a test case never passes through the code that is changed. It exists skip_sort_order() function at the condition:

 if (tab->type == JT_ALL && tab->join->tables > tab->join->const_tables + 1) 
   DBUG_RETURN(0);
[3 Feb 2010 19:45] Sinisa Milivojevic
The problem is the addition of this code in test_if_skip_sort_order() in version 5.1:

      if (tab->type == JT_ALL && tab->join->tables > tab->join->const_tables + 1)
        DBUG_RETURN(0);

This code makes exit from the function and forces creation of temporary table. However, this code does not take into account that if best index is clustered, then filesort() and join cache are NOT usually faster than reading in  index order and not using join cache.

Solution to the problem is moving this condition down in the code with the addition of the clause on whether the best index is clustered.
[4 Feb 2010 16:03] Sinisa Milivojevic
This is patch that effectively resolves this bug. This patch is not final yet as tests are still running now ....

=== modified file 'sql/sql_select.cc'
--- sql/sql_select.cc   2009-09-28 13:48:40 +0000
+++ sql/sql_select.cc   2010-02-04 15:54:03 +0000
@@ -13091,12 +13091,6 @@
     */
     if (select_limit >= table_records)
     {
-      /* 
-        filesort() and join cache are usually faster than reading in 
-        index order and not using join cache
-        */
-      if (tab->type == JT_ALL && tab->join->tables > tab->join->const_tables + 1)
-        DBUG_RETURN(0);
       keys= *table->file->keys_to_use_for_scanning();
       keys.merge(table->covering_keys);
 
@@ -13239,6 +13233,19 @@
        }      
       }
     }
+
+    /*
+
+    This is repeated here due to bug #46011
+
+    filesort() and join cache are usually faster than reading in 
+    index order and not using join cache, except in case that chosen
+    index is clustered Primary Key
+
+    */
+    if ((select_limit >= table_records) && (tab->type == JT_ALL && tab->join->tables > tab->join->const_tables + 1) && ! ((unsigned) best_key == table->s->primary_key && table->file->primary_key_is_clustered()))
+      DBUG_RETURN(0);
+
     if (best_key >= 0)
     {
       bool quick_created= FALSE;
[12 Feb 2010 14:25] Sinisa Milivojevic
The above patch is now a final one as all tests passed. Beside the tests, I also ran some of my own, just to test for possible regressions.
[24 Feb 2010 8:19] Evgeny Potemkin
The fix for #45828 made ref access/covering index access choice cost-based. It's correct by itself but the cost model for it is wrong. It compares ref access cost to covering index access cost and doesn't take into account that after records being found with ref access they should be sorted with filesort.
The correct fix for this bug should introduce a cost calculation of filesort and take it into account.
[4 Mar 2010 10:07] Manyi Lu
Introducing a cost calculation of filesort justifies a worklog.Please create one when the developer starts working on this bug.
[15 May 2010 11:05] Philip Stoev
Sinisa, the table is available by mounting the vardir located at 

http://mysql-systemqa.s3.amazonaws.com/var-bug46011.zip