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:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.1.23 OS:Any
Assigned to: Igor Babaev CPU Architecture:Any
Triage: D2 (Serious) / R4 (High) / E3 (Medium)

[4 Apr 2008 19:57] Chris Elsworth
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)
[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.