| 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: | |
| 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 | ||
[7 Jul 2009 14:05]
Philip Stoev
[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]
MySQL Verification Team
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]
MySQL Verification Team
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]
MySQL Verification Team
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]
MySQL Verification Team
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]
MySQL Verification Team
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
