| Bug #35844 | ORDER BY favours full scan over a faster filesort | ||
|---|---|---|---|
| Submitted: | 4 Apr 2008 19:57 | Modified: | 14 May 2008 2:37 |
| Reporter: | Chris Elsworth | Email Updates: | |
| Status: | Closed | Impact on me: | |
| Category: | MySQL Server: Optimizer | Severity: | S3 (Non-critical) |
| Version: | 5.1.23 | OS: | Any |
| Assigned to: | Igor Babaev | CPU Architecture: | Any |
[4 Apr 2008 20:38]
Sveta Smirnova
Thank you for the report. Verified as described. Bug is repeatable only with InnoDB.
[7 Apr 2008 12:15]
Heikki Tuuri
Hmm... I think someone complained about MySQL not using an ordering index to resolve an ORDER BY query. It might have been only in the DESC case. Maybe the MySQL optimizer was tuned to favor index searches TOO much. This is an optimizer bug report. InnoDB does not have much control on MySQL's query plan. Regards, Heikki
[22 Apr 2008 21:50]
Igor Babaev
This bug can be reproduced with the following MyISAM table: CREATE TABLE t1 ( id1 INT NULL, id2 INT NOT NULL, junk INT NOT NULL, PRIMARY KEY (id1, id2, junk), INDEX id2_j_id1 (id2, junk, id1) ); INSERT INTO t1 VALUES (1, 1, 1), (2, 1, 2), (3, 1, 3), (4, 1, 4); INSERT INTO t1 VALUES (5, 2, 1), (6, 2, 2), (7, 2, 3), (8, 2, 4); INSERT INTO t1 VALUES (9, 3, 1), (10, 3, 2), (11, 3, 3), (12, 3, 4); INSERT INTO t1 VALUES (13, 4, 1), (14, 4, 2), (15, 4, 3), (16, 4, 4); INSERT INTO t1 VALUES (17, 5, 1), (18, 5, 2), (19, 5, 3), (20, 5, 4); INSERT INTO t1 VALUES (21, 6, 1), (22, 6, 2), (23, 6, 3), (24, 6, 4); INSERT INTO t1 VALUES (25, 7, 1), (26, 7, 2), (27, 7, 3), (28, 7, 4); INSERT INTO t1 VALUES (29, 8, 1), (30, 8, 2), (31, 8, 3), (32, 8, 4); INSERT INTO t1 VALUES (33, 9, 1), (34, 9, 2), (35, 9, 3), (36, 9, 4); Here we have the same problem as the reported one: mysql> EXPLAIN SELECT id1 FROM t1 WHERE id2 = 4 ORDER BY id1; +----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+ | 1 | SIMPLE | t1 | index | id2_j_id1 | PRIMARY | 12 | NULL | 36 | Using where; Using index | +----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+ 1 row in set (0.00 sec)
[23 Apr 2008 4:45]
Bugs System
A patch for this bug has been committed. After review, it may be pushed to the relevant source trees for release in the next version. You can access the patch from: http://lists.mysql.com/commits/45859 ChangeSet@1.2562, 2008-04-22 21:49:39-07:00, igor@olga.mysql.com +4 -0 Fixed bug#35844. The function test_if_skip_sort_order ignored any covering index used for ref access of a table in a query with ORDER BY if this index was incompatible with the ORDER BY list and there was another covering index compatible with this list. As a result sub-optimal execution plans were chosen for some queries with ORDER BY clause.
[1 May 2008 6:17]
Bugs System
Pushed into 5.1.25-rc
[1 May 2008 6:19]
Bugs System
Pushed into 6.0.6-alpha
[14 May 2008 2:37]
Paul DuBois
Noted in 5.1.25, 6.0.6 changelogs.
Description: Since 5.1.23, a simple query that should use an index lookup to resolve a WHERE is instead favouring an index to avoid a filesort, even though the filesort would be comparatively cheap as opposed to a full table scan. In 5.1.22, both queries in the how-to-repeat section below correctly use the id2_j_id1 index to return the query while examining only 4 rows. In 5.1.23, the second query examines all 36 rows of the table, just to save itself a filesort. May also be worth noting I only observed this when using InnoDB; MyISAM was fine. How to repeat: DROP TABLE IF EXISTS broken; CREATE TABLE broken ( id1 INT UNSIGNED NOT NULL AUTO_INCREMENT, id2 INT UNSIGNED NOT NULL, junk INT UNSIGNED NOT NULL, PRIMARY KEY (id1), KEY id2_j_id1 (id2, junk, id1) ) ENGINE=InnoDB; INSERT INTO broken (id2, junk) VALUES (1, 1), (1, 2), (1, 3), (1, 4); INSERT INTO broken (id2, junk) VALUES (2, 1), (2, 2), (2, 3), (2, 4); INSERT INTO broken (id2, junk) VALUES (3, 1), (3, 2), (3, 3), (3, 4); INSERT INTO broken (id2, junk) VALUES (4, 1), (4, 2), (4, 3), (4, 4); INSERT INTO broken (id2, junk) VALUES (5, 1), (5, 2), (5, 3), (5, 4); INSERT INTO broken (id2, junk) VALUES (6, 1), (6, 2), (6, 3), (6, 4); INSERT INTO broken (id2, junk) VALUES (7, 1), (7, 2), (7, 3), (7, 4); INSERT INTO broken (id2, junk) VALUES (8, 1), (8, 2), (8, 3), (8, 4); INSERT INTO broken (id2, junk) VALUES (9, 1), (9, 2), (9, 3), (9, 4); /* works (4 rows) */ EXPLAIN SELECT id1 FROM broken where id2 = 4; mysql> EXPLAIN SELECT id1 FROM broken where id2 = 4\G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: broken type: ref possible_keys: id2_j_id1 key: id2_j_id1 key_len: 4 ref: const rows: 4 Extra: Using index 1 row in set (0.00 sec) /* broken in 5.1.23 (36 rows) */ EXPLAIN SELECT id1 FROM broken WHERE id2 = 4 ORDER BY id1; The second query uses the inferior PRIMARY key to avoid the filesort, but by doing so incurs a full table scan which is devastating for performance on a sizeable table: mysql> EXPLAIN SELECT id1 FROM broken WHERE id2 = 4 ORDER BY id1\G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: broken type: index possible_keys: id2_j_id1 key: PRIMARY key_len: 4 ref: NULL rows: 36 Extra: Using where; Using index 1 row in set (0.06 sec)