[MDEV-465] Optimizer : wrong index choice, leading to strong performances issues - JIRA

Details

Type: Bug
Status: Closed
Priority: Minor
Resolution: Fixed
Affects Version/s: 5.5.25, 5.3.7, 5.2.12, 5.1.62
Fix Version/s: 10.1.1
Component/s: None
Labels:
- optimizer
- order-by-optimization

Description

Hi,

I'm recreating in JIRA a Launchpad bug opened 2 years ago (https://bugs.launchpad.net/maria/+bug/639949), which is itself a follow up of a really annoying MySQL optimiser bug opened 4 years ago (http://bugs.mysql.com/bug.php?id=36817)

To summarize, there are several simple cases where MySQL optimiser doesn't select the right index. This entails strong performance issues (especially when filesorting is involved), and force the developers to hack their applications, using USE INDEX (when it's possible...).

Hoping someone finally takes a look at this serious issue...
Actually it could also help some of my customers to switch to mariadb, because they are also a little bit tired to put USE INDEX everywhere in there code

Thanks and regards,
Jocelyn Fournier

Gliffy Diagrams

Attachments

Issue Links

duplicates

MDEV-626 LP:639949 - Non optimal index choice, depending on index creation order

Closed

relates to

MDEV-6384 It seems like OPTIMIZER take into account the order of indexes in the table.

Closed

links to

Bug #36817 Non optimal index choice, depending on index creation order

Activity

Ascending order - Click to sort in descending order

Hide

Permalink

Sergei Petrunia added a comment - 2012-08-24 00:41

With MariaDB 5.5 and Yoshinori's example, I get the best index:

MariaDB [j3]> explain select * from a where k2=5 order by k3 limit 2;
----------------------------------------------------------------------+

id

select_type

table

type

possible_keys

key

key_len

ref

rows

Extra

----------------------------------------------------------------------+

1

SIMPLE

a

range

i1,i2

i2

5

NULL

2609

Using where

----------------------------------------------------------------------+

This seems to be pure chance though: range optimizer choses the best index with no regards to ORDER BY LIMIT clause, it has identical costs for indexes i1 and i2, and the choice may vary because of how floating-point numbers are compared.
If it choses i2, we're lucky. If it choses i1, then ORDER BY optimization code will not be able to figure out that using i1 would have produced a cheaper plan. This is probably where part of the problem is.

Show

Sergei Petrunia added a comment - 2012-08-24 00:41 With MariaDB 5.5 and Yoshinori's example, I get the best index: MariaDB [j3] > explain select * from a where k2=5 order by k3 limit 2; ----- ----------- ----- ----- ------------- ---- ------- ---- ---- ------------+ id select_type table type possible_keys key key_len ref rows Extra ----- ----------- ----- ----- ------------- ---- ------- ---- ---- ------------+ 1 SIMPLE a range i1,i2 i2 5 NULL 2609 Using where ----- ----------- ----- ----- ------------- ---- ------- ---- ---- ------------+ This seems to be pure chance though: range optimizer choses the best index with no regards to ORDER BY LIMIT clause, it has identical costs for indexes i1 and i2, and the choice may vary because of how floating-point numbers are compared. If it choses i2, we're lucky. If it choses i1, then ORDER BY optimization code will not be able to figure out that using i1 would have produced a cheaper plan. This is probably where part of the problem is.

8 older comments

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-03 10:17

Trying the original testcase from http://bugs.mysql.com/bug.php?id=36817:

Clean MariaDB 10.1:

MariaDB [j11]> CREATE TABLE `a` (
    ->   `id1` int(10) unsigned NOT NULL auto_increment,
    ->   `id2` tinyint(3) unsigned NOT NULL default '0',
    ->   `id3` tinyint(3) unsigned NOT NULL default '0',
    ->   `id4` int(10) unsigned NOT NULL default '0',
    ->   `date` timestamp NOT NULL default CURRENT_TIMESTAMP,
    ->   PRIMARY KEY  (`id1`),
    ->   KEY `id2` (`id2`,`id3`,`id4`,`date`),
    ->   KEY `id2_2` (`id2`,`id3`,`date`)
    -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.08 sec)

MariaDB [j11]> INSERT INTO a (id2,id3,id4) VALUES (1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1);
Query OK, 7 rows affected (0.01 sec)
Records: 7  Duplicates: 0  Warnings: 0

MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4;
+------+-------------+-------+------+---------------+------+---------+-------------+------+-----------------------------+
| id   | select_type | table | type | possible_keys | key  | key_len | ref         | rows | Extra                       |
+------+-------------+-------+------+---------------+------+---------+-------------+------+-----------------------------+
|    1 | SIMPLE      | a     | ref  | id2,id2_2     | id2  | 2       | const,const |    3 | Using where; Using filesort |
+------+-------------+-------+------+---------------+------+---------+-------------+------+-----------------------------+

MariaDB [j11]> DROP TABLE IF EXISTS a;
MariaDB [j11]> CREATE TABLE `a` (
    ->   `id1` int(10) unsigned NOT NULL auto_increment,
    ->   `id2` tinyint(3) unsigned NOT NULL default '0',
    ->   `id3` tinyint(3) unsigned NOT NULL default '0',
    ->   `id4` int(10) unsigned NOT NULL default '0',
    ->   `date` timestamp NOT NULL default CURRENT_TIMESTAMP,
    ->   PRIMARY KEY  (`id1`),
    ->   KEY `id2` (`id2`,`id3`,`date`),
    ->   KEY `id2_2` (`id2`,`id3`,`id4`,`date`)
    -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.06 sec)

MariaDB [j11]> INSERT INTO a (id2,id3,id4) VALUES (1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1);
Query OK, 7 rows affected (0.00 sec)
Records: 7  Duplicates: 0  Warnings: 0

MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4;
+------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+
| id   | select_type | table | type | possible_keys | key  | key_len | ref         | rows | Extra       |
+------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+
|    1 | SIMPLE      | a     | ref  | id2,id2_2     | id2  | 2       | const,const |    3 | Using where |
+------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+

10.1 tree with fixes for ~~MDEV-6384~~, ~~MDEV-6480~~:

MariaDB [j11]> CREATE TABLE `a` (
    ->   `id1` int(10) unsigned NOT NULL auto_increment,
    ->   `id2` tinyint(3) unsigned NOT NULL default '0',
    ->   `id3` tinyint(3) unsigned NOT NULL default '0',
    ->   `id4` int(10) unsigned NOT NULL default '0',
    ->   `date` timestamp NOT NULL default CURRENT_TIMESTAMP,
    ->   PRIMARY KEY  (`id1`),
    ->   KEY `id2` (`id2`,`id3`,`id4`,`date`),
    ->   KEY `id2_2` (`id2`,`id3`,`date`)
    -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.12 sec)

MariaDB [j11]> INSERT INTO a (id2,id3,id4) VALUES (1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1);
Query OK, 7 rows affected (0.00 sec)
Records: 7  Duplicates: 0  Warnings: 0

MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4;
+------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+
| id   | select_type | table | type  | possible_keys | key   | key_len | ref  | rows | Extra       |
+------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+
|    1 | SIMPLE      | a     | range | id2,id2_2     | id2_2 | 2       | NULL |    3 | Using where |
+------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+

MariaDB [j11]> DROP TABLE IF EXISTS a;
Query OK, 0 rows affected (0.00 sec)

MariaDB [j11]> CREATE TABLE `a` (
    ->   `id1` int(10) unsigned NOT NULL auto_increment,
    ->   `id2` tinyint(3) unsigned NOT NULL default '0',
    ->   `id3` tinyint(3) unsigned NOT NULL default '0',
    ->   `id4` int(10) unsigned NOT NULL default '0',
    ->   `date` timestamp NOT NULL default CURRENT_TIMESTAMP,
    ->   PRIMARY KEY  (`id1`),
    ->   KEY `id2` (`id2`,`id3`,`date`),
    ->   KEY `id2_2` (`id2`,`id3`,`id4`,`date`)
    -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.07 sec)

MariaDB [j11]> INSERT INTO a (id2,id3,id4) VALUES (1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1);
Query OK, 7 rows affected (0.00 sec)
Records: 7  Duplicates: 0  Warnings: 0

MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4;
+------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+
| id   | select_type | table | type | possible_keys | key  | key_len | ref         | rows | Extra       |
+------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+
|    1 | SIMPLE      | a     | ref  | id2,id2_2     | id2  | 2       | const,const |    3 | Using where |
+------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+

Show

Sergei Petrunia added a comment - 2014-09-03 10:17 Trying the original testcase from http://bugs.mysql.com/bug.php?id=36817: Clean MariaDB 10.1: MariaDB [j11]> CREATE TABLE `a` ( -> `id1` int(10) unsigned NOT NULL auto_increment, -> `id2` tinyint(3) unsigned NOT NULL default '0', -> `id3` tinyint(3) unsigned NOT NULL default '0', -> `id4` int(10) unsigned NOT NULL default '0', -> `date` timestamp NOT NULL default CURRENT_TIMESTAMP, -> PRIMARY KEY (`id1`), -> KEY `id2` (`id2`,`id3`,`id4`,`date`), -> KEY `id2_2` (`id2`,`id3`,`date`) -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1; Query OK, 0 rows affected (0.08 sec) MariaDB [j11]> INSERT INTO a (id2,id3,id4) VALUES (1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1); Query OK, 7 rows affected (0.01 sec) Records: 7 Duplicates: 0 Warnings: 0 MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4; +------+-------------+-------+------+---------------+------+---------+-------------+------+-----------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +------+-------------+-------+------+---------------+------+---------+-------------+------+-----------------------------+ | 1 | SIMPLE | a | ref | id2,id2_2 | id2 | 2 | const,const | 3 | Using where; Using filesort | +------+-------------+-------+------+---------------+------+---------+-------------+------+-----------------------------+ MariaDB [j11]> DROP TABLE IF EXISTS a; MariaDB [j11]> CREATE TABLE `a` ( -> `id1` int(10) unsigned NOT NULL auto_increment, -> `id2` tinyint(3) unsigned NOT NULL default '0', -> `id3` tinyint(3) unsigned NOT NULL default '0', -> `id4` int(10) unsigned NOT NULL default '0', -> `date` timestamp NOT NULL default CURRENT_TIMESTAMP, -> PRIMARY KEY (`id1`), -> KEY `id2` (`id2`,`id3`,`date`), -> KEY `id2_2` (`id2`,`id3`,`id4`,`date`) -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1; Query OK, 0 rows affected (0.06 sec) MariaDB [j11]> INSERT INTO a (id2,id3,id4) VALUES (1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1); Query OK, 7 rows affected (0.00 sec) Records: 7 Duplicates: 0 Warnings: 0 MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4; +------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+ | 1 | SIMPLE | a | ref | id2,id2_2 | id2 | 2 | const,const | 3 | Using where | +------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+ 10.1 tree with fixes for MDEV-6384 , MDEV-6480 : MariaDB [j11]> CREATE TABLE `a` ( -> `id1` int(10) unsigned NOT NULL auto_increment, -> `id2` tinyint(3) unsigned NOT NULL default '0', -> `id3` tinyint(3) unsigned NOT NULL default '0', -> `id4` int(10) unsigned NOT NULL default '0', -> `date` timestamp NOT NULL default CURRENT_TIMESTAMP, -> PRIMARY KEY (`id1`), -> KEY `id2` (`id2`,`id3`,`id4`,`date`), -> KEY `id2_2` (`id2`,`id3`,`date`) -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1; Query OK, 0 rows affected (0.12 sec) MariaDB [j11]> INSERT INTO a (id2,id3,id4) VALUES (1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1); Query OK, 7 rows affected (0.00 sec) Records: 7 Duplicates: 0 Warnings: 0 MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4; +------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+ | 1 | SIMPLE | a | range | id2,id2_2 | id2_2 | 2 | NULL | 3 | Using where | +------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+ MariaDB [j11]> DROP TABLE IF EXISTS a; Query OK, 0 rows affected (0.00 sec) MariaDB [j11]> CREATE TABLE `a` ( -> `id1` int(10) unsigned NOT NULL auto_increment, -> `id2` tinyint(3) unsigned NOT NULL default '0', -> `id3` tinyint(3) unsigned NOT NULL default '0', -> `id4` int(10) unsigned NOT NULL default '0', -> `date` timestamp NOT NULL default CURRENT_TIMESTAMP, -> PRIMARY KEY (`id1`), -> KEY `id2` (`id2`,`id3`,`date`), -> KEY `id2_2` (`id2`,`id3`,`id4`,`date`) -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1; Query OK, 0 rows affected (0.07 sec) MariaDB [j11]> INSERT INTO a (id2,id3,id4) VALUES (1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1); Query OK, 7 rows affected (0.00 sec) Records: 7 Duplicates: 0 Warnings: 0 MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4; +------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+ | 1 | SIMPLE | a | ref | id2,id2_2 | id2 | 2 | const,const | 3 | Using where | +------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-03 10:18

That is, the fix for ~~MDEV-6384~~ fixes this issue.

Show

Sergei Petrunia added a comment - 2014-09-03 10:18 That is, the fix for MDEV-6384 fixes this issue.

Hide

Permalink

jocelyn fournier added a comment - 2014-09-03 10:23

Hi Sergei,

The explain

MariaDB [j11]> EXPLAIN SELECT id1 FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4;
+------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+
| id   | select_type | table | type  | possible_keys | key   | key_len | ref  | rows | Extra       |
+------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+
|    1 | SIMPLE      | a     | range | id2,id2_2     | id2_2 | 2       | NULL |    3 | Using where |
+------+-------------+-------+-------+---------------+-------+---------+------+------+-------------+

looks weird.
Why a range access is used here with id2_2, instead of ref ? (although no more filesort is used, which is great !)

Show

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-03 11:42

range and ref(const) are for the most part the same thing. Code for range access is able to scan arbitrary ranges, code for ref access handles lookups on tbl.key=expr, where expr can also be constant.

Internally, ref(const) is converted into range in most cases (or maybe even all cases).

Here, we use index to read rows in order. We can use arbitrary range access, but not arbitrary ref access. that's why ORDER BY optimizer switches to range access. ref access is constructed by the join optimizer. however, ORDER BY optimizer is invoked after join optimizer, so range does not get replaced with ref. But, as I said, there is hardly any difference.

Show

Sergei Petrunia added a comment - 2014-09-03 11:42 range and ref(const) are for the most part the same thing. Code for range access is able to scan arbitrary ranges, code for ref access handles lookups on tbl.key=expr, where expr can also be constant. Internally, ref(const) is converted into range in most cases (or maybe even all cases). Here, we use index to read rows in order. We can use arbitrary range access, but not arbitrary ref access. that's why ORDER BY optimizer switches to range access. ref access is constructed by the join optimizer. however, ORDER BY optimizer is invoked after join optimizer, so range does not get replaced with ref. But, as I said, there is hardly any difference.

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-09 12:16

Fixed in 10.1 by fix for ~~MDEV-6384~~.

Show

Sergei Petrunia added a comment - 2014-09-09 12:16 Fixed in 10.1 by fix for MDEV-6384 .

Optimizer : wrong index choice, leading to strong performances issues

Details

Description

Gliffy Diagrams

Attachments

Issue Links

Activity

People

Dates

Time Tracking

Agile