|
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.
|
|
Jocelyn, re your comment at http://bugs.mysql.com/bug.php?id=36817, dated [5 Jul 2009 12:24]:
Why do you think one query plan is better than the other? Each of the provided query plans expects to read 3 rows from a 7-row table. The costs should be the same : read one index page, and one disk page.
I suppose, you've had bigger examples in mind, where both the table and scanned ranges have lots of records?
I see the following possible problem: when MySQL/MariaDB estimates cost of doing a non-"Using index" range scan, the estimate doesn't take into account the size of index entry. This way, for a query
select * from tbl where keypart1=const
we may end up choosing to use index I1 (keypart1, keypart2, keypart3), instead of index I2(keypart1), which has shorter index tuples, and ought to be faster. I don't know, how critical this is, though. There is a lot of stuff we don't take into account. One could imagine that index with more columns is used more frequently, and thus there is a greater chance that its entries are in the buffer pool.
|
|
Please clarify, if this issue covers case with ORDER BY, or without ORDER BY also.
|
|
Hi Sergei,
The most critical point is with order by (note however that my first example in the testcase doesn't involve range access, only ref).
If you want to reproduce it with InnoDB as well :
DROP TABLE IF EXISTS a;
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=InnoDB DEFAULT CHARSET=latin1;
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);
EXPLAIN SELECT * FROM a WHERE id2=1 AND id3=1 ORDER BY date DESC LIMIT 0,4;
MariaDB [t1]> EXPLAIN SELECT * 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 |
4 |
Using where; Using index; Using filesort |
-----
1 row in set (0.00 sec)
Here id2_2 should have been choosing since it avoid a filesort.
If I'm doing
MariaDB [t1]> 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_2,id2 |
id2_2 |
2 |
const,const |
4 |
Using where; Using index |
-----
1 row in set (0.00 sec)
it properly choose id2_2.
I can grab more "real" case if you want.
As for my comment dated [5 Jul 2009 12:24], the first execution plan using id2 is using an index with (keypart1, keypart2) and the second case is using (keypart1, keypart2, keypart3) which is better because the WHERE clause is on keypart1=const AND keypart2=const AND keypart3=const.
In my example, I have only one value in keypart3 so indeed it doesn't really change the final cost, but I experienced a lot of case where keypart3 was containing a lot of different value, and the optimiser was still choosing (keypart1, keypart2) even after an ANALYZE, and in this case the difference in performances between the two index is huge.
However, I'm not able anymore to reproduce the case in a simple testcase, so this may have been fixed through the year.
|
|
Note that the range optimizer issue could be pretty bad, since it could randomly lead to the use of a filesort, hence the need to use "USE INDEX" hint each time a query with an ORDER BY ... DESC ... LIMIT is used.
|
|
I confirm that the comment dated 2012-08-24 07:28 shows a problem. One can modify table definition slightly, so that indexes are defined as:
KEY `id2_id3_date` (`id2`,`id3`,`date`),
KEY `id2_id3_id4_date` (`id2`,`id3`,`id4`,`date`)
then, depending on the order in which the table defines the indexes, one will get
MariaDB [j4]> EXPLAIN SELECT id1 FROM t2 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 |
t2 |
ref |
id2_id3_date,id2_id3_id4_date |
id2_id3_date |
2 |
const,const |
3 |
Using where |
-----
or
-----
| id |
select_type |
table |
type |
possible_keys |
key |
key_len |
ref |
rows |
Extra |
-----
| 1 |
SIMPLE |
t1 |
ref |
id2_id3_id4_date,id2_id3_date |
id2_id3_id4_date |
2 |
const,const |
3 |
Using where; Using filesort |
-----
1 row in set (8.67 sec)
|
|
I was trying to understand code in test_if_cheaper_ordering(), but so far I was not successful, despite all the comments that are there.
|
|
Investigated, discussed with Igor. We've identified the following problems:
1. test_if_cheaper_ordering() assumes that the WHERE condition is not correlated with the ranges we're going to scan on the key it is considering (id2_id3_date in the example).
This is used to predict how many record we will need to scan before we produce N records required by the "LIMIT N" clause.
(For example: if WHERE condition's selectivity is 0.33 then we need to scan N/0.33 = N*3 records to produce N output rows). However, in this example, WHERE condition is perfectly correlated with the ranges we're going to scan. Every single record returned by the ref access will satisfy the "id2=1 AND id3=1".
2. test_if_cheaper_ordering() uses a different formula to calculate cost of scanning the index than one used in opt_range.cc or best_access_path(). That way, the numbers we're comparing are not exactly comparable.
3. Cost of sorting is not taken into account (right. it is a known 'property' of ORDER BY optimization).
In order to fix this bug (and other similar cases),
- we will certainly need to fix #2.
- I have not checked whether we must fix #1, but probably it is true. Condition selectivity estimation code planned for 10.0 might help there
- we will certainly need to fix #3. If we don't, the costs of using id2_id3_date, id2_id3_id4_date will be the same (provided we've fixed #2), and the optimizer will have problem with choosing not to sort.
the first try at cost of filesort can be a simple, optimistic
sort_input_records / TIME_FOR_COMPARE
The idea is that any sorting algorithm (incl. optimized variants for getting top-N element) will still need to enumerate all input records, and perform at least one comparison for each input record. (todo: check if we should use TIME_FOR_COMPARE or other constant?) .
|
|
Trying testcase from http://bugs.mysql.com/bug.php?id=59131,
comment [23 Dec 2010 13:47] Yoshinori Matsunobu
(the same as testcase from http://bugs.mysql.com/bug.php?id=36817,
comment [23 Dec 2010 14:49] Yoshinori Matsunobu):
create table a (id int auto_increment primary key,
|
k1 int, k2 int, k3 int, value int,
|
index i1 (k2, k1, k3), index i2 (k2, k3)) engine=innodb;
|
|
Then insert lots of rows with low enough cardinality on k2 (I tested inserting 2.6 mil rows, cardinality on k2 was 1000):
|
|
insert into a (k1, k2, k3, value)values (1,1,1,1), (2,2,2,2),(3,3,3,3),(4,4,4,4),(5,5,5,5),(6,6,6,6),(7,7,7,7),(8,8,8,8),(9,9,9,9),(10,10,10,10);
|
insert into a (k1, k2, k3, value) select rand()*1000000, rand()*1000, rand()*1000000, value from a;
|
insert into a (k1, k2, k3, value) select rand()*1000000, rand()*1000, rand()*1000000, value from a;
|
insert into a (k1, k2, k3, value) select rand()*1000000, rand()*1000, rand()*1000000, value from a;
|
....
|
|
insert into a (k1, k2, k3, value) select rand()*1000000, rand()*1000, rand()*1000000, value from a;
|
Query OK, 1310720 rows affected (51.06 sec)
|
Records: 1310720 Duplicates: 0 Warnings: 0
|
10.1 tree:
MariaDB [j11]> 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 | 2603 | Using where |
|
+------+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|
1 row in set (0.06 sec)
|
|
MariaDB [j11]> explain select * from a where k2=5 order by k3 limit 20;
|
+------+-------------+-------+------+---------------+------+---------+-------+------+-----------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|
+------+-------------+-------+------+---------------+------+---------+-------+------+-----------------------------+
|
| 1 | SIMPLE | a | ref | i1,i2 | i1 | 5 | const | 2603 | Using where; Using filesort |
|
+------+-------------+-------+------+---------------+------+---------+-------+------+-----------------------------+
|
1 row in set (0.00 sec)
|
10.1 tree with fixes for MDEV-6384, MDEV-6480:
MariaDB [j11]> 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 | 2603 | Using where |
|
+------+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|
1 row in set (0.00 sec)
|
|
MariaDB [j11]> explain select * from a where k2=5 order by k3 limit 20;
|
+------+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|
+------+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|
| 1 | SIMPLE | a | range | i1,i2 | i2 | 5 | NULL | 2603 | Using where |
|
+------+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|
1 row in set (0.00 sec)
|
|
|
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 |
|
+------+-------------+-------+------+---------------+------+---------+-------------+------+-------------+
|
|
|
That is, the fix for MDEV-6384 fixes this issue.
|
|
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 !)
|
|
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.
|
|
Fixed in 10.1 by fix for MDEV-6384.
|
