Bug #38745 MySQL 5.1 optimizer uses filesort for ORDER BY when it should use index
Submitted: 12 Aug 2008 9:44 Modified: 20 Jul 2010 2:46
Reporter: Marc Isambart Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.1 OS:Any
Assigned to: Gleb Shchepa CPU Architecture:Any
Tags: Optimizer, regression

[12 Aug 2008 9:44] Marc Isambart
Description:
This is a case where MySQL 5.1.26 uses filesort for an ORDER BY when it should use the index. On the exact same query, MySQL 5.0.45 correctly uses the index.

This greatly affects the performance on large databases. By example, the query will take 100s of seconds on large databases when it will take less than a second on 5.0.45.

How to repeat:
We need to consider 3 tables:

CREATE TABLE data1 ( index1 integer NOT NULL, value1 integer NOT NULL, PRIMARY KEY(index1) ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
CREATE TABLE data2 ( index2 integer NOT NULL, value2 integer NOT NULL, PRIMARY KEY(index2) ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
CREATE TABLE data3 ( index3 integer NOT NULL, value3 integer NOT NULL, PRIMARY KEY(index3) ) ENGINE=MyISAM DEFAULT CHARSET=latin1;

Let's add some data to data1 data3, but keep data2 empty:

INSERT INTO data1 VALUES (1, 1),(2, 2),(3, 3),(4, 4),(5, 5),(6, 6),(7, 7),(8, 8),(9, 9),(10, 10),(11, 11),(12, 12);
INSERT INTO data3 VALUES (1, 1),(2, 2),(3, 3),(4, 4),(5, 5),(6, 6),(7, 7),(8, 8),(9, 9),(10, 10),(11, 11),(12, 12);

If we consider the following query:

EXPLAIN SELECT data1.*, data3.*, data2.value2 FROM data1 JOIN data3 ON data3.index3 = data1.index1 LEFT JOIN data2 ON data1.index1 = data2.index2 WHERE data1.index1 BETWEEN 3 AND 10 ORDER BY data1.index1 LIMIT 5\G

5.1.26 will use filesort:

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: data2
         type: system
possible_keys: PRIMARY
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 0
        Extra: const row not found
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: data1
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 7
        Extra: Using where; Using filesort
*************************** 3. row ***************************
           id: 1
  select_type: SIMPLE
        table: data3
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: bugreport.data1.index1
         rows: 1
        Extra:

On the same query, 5.0.45 will correctly optimize it:

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: data2
         type: system
possible_keys: PRIMARY
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 0
        Extra: const row not found
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: data1
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 7
        Extra: Using where
*************************** 3. row ***************************
           id: 1
  select_type: SIMPLE
        table: data3
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: bugreport.data1.index1
         rows: 1
        Extra:

If we now add a single row in data2 and use the same previous select query:

INSERT INTO data2 VALUES (1, 1);

EXPLAIN SELECT data1.*, data3.*, data2.value2 FROM data1 JOIN data3 ON data3.index3 = data1.index1 LEFT JOIN data2 ON data1.index1 = data2.index2 WHERE data1.index1 BETWEEN 3 AND 10 ORDER BY data1.index1 LIMIT 5\G

MySQL 5.1.26 will now optimize it correctly:

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: data1
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 7
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: data2
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: bugreport.data1.index1
         rows: 1
        Extra:
*************************** 3. row ***************************
           id: 1
  select_type: SIMPLE
        table: data3
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: bugreport.data1.index1
         rows: 1
        Extra:
[12 Aug 2008 13:26] Susanne Ebrecht
Many thanks for writing a bug report.

Verified as described.
[27 Apr 2009 9:39] Sergej Pupykin
I just want to notice that this bug seems brake dbmail application.

This query hangs for a very very long time on dbmail with 6.5Gb database and mysql 5.1.34, but works fast on mysql 5.0.77:
SELECT messageblk, is_header FROM dbmail_messageblks WHERE physmessage_id = 278699 ORDER BY messageblk_idnr

I fix it in dbmail using 'use index' expression:
SELECT messageblk, is_header FROM dbmail_messageblks  use index(physmessage_id_index) WHERE physmessage_id = 278699 ORDER BY messageblk_idnr
[14 Sep 2009 8:27] Gleb Shchepa
Simplified test case:

CREATE TABLE t1 (i1 integer NOT NULL PRIMARY KEY);
CREATE TABLE t2 (i2 integer);
CREATE TABLE t3 (i3 integer NOT NULL PRIMARY KEY);

INSERT INTO t1 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (11), (12);
INSERT INTO t3 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (11), (12);

EXPLAIN EXTENDED
SELECT t1.*, t3.* FROM t1 JOIN t3 ON t3.i3 = t1.i1 LEFT JOIN t2 ON t1.i1 = t2.i2 ORDER BY t1.i1 LIMIT 5;

DROP TABLE t1, t2, t3;
[29 Apr 2010 3:25] Andrew A
I think I've also spotted this bug.

Given this simple query to retrieve some information from phpBB:

SELECT t.topic_id, t.topic_title, f.forum_id, f.forum_name, t.topic_replies, t.topic_last_post_time
FROM phpbb_topics t
INNER JOIN phpbb_forums f ON f.forum_id = t.forum_id
ORDER BY t.topic_last_post_time DESC 
LIMIT 7

I get a query plan of:

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	f	ALL	PRIMARY	NULL	NULL	NULL	73	Using temporary; Using filesort
1	SIMPLE	t	ref	forum_id,forum_id_type,forum_appr_last,fid_time_mo...	forum_id	3	f.forum_id	782	 

An index is available on the phpbb_topics table: last_post_time (topic_last_post_time)

Re-writing to include a force index statement:
SELECT t.topic_id, t.topic_title, f.forum_id, f.forum_name, t.topic_replies, t.topic_last_post_time
FROM phpbb_topics t FORCE INDEX ( last_post_time ) 
INNER JOIN phpbb_forums f ON f.forum_id = t.forum_id
ORDER BY t.topic_last_post_time DESC 
LIMIT 7

And I get a query plan of:
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t	index	NULL	last_post_time	4	NULL	7	 
1	SIMPLE	f	eq_ref	PRIMARY	PRIMARY	3	t.forum_id	1	 

Which is obviously much more efficient.

I tried running ANALYZE TABLES on both tables yet there was no difference in query plan. Both tables are InnoDB.

Cardinality on last_post_time is 149467. phpbb_topics contains ~150,000 rows, where-as the forums table contains ~100.

MySQL Server version 5.1.42-community
[29 Apr 2010 3:26] Andrew A
I also wonder why 'Using filesort' is even used on the forums table?

An ORDER BY is done on the topics table, not the forums table.
[25 May 2010 4:12] 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/109113

3057 Gleb Shchepa	2010-05-25
      Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                  when it should use index
      
      Sometimes the LEFT/RIGHT JOIN with an empty table caused an
      unnecessary filesort.
      
      Sample query, where t1.i1 is indexed and t3 is empty:
      
        SELECT t1.*, t2.* FROM t1 JOIN t2 ON t1.i1 = t2.i2
                             LEFT JOIN t3 ON t2.i2 = t3.i3
          ORDER BY t1.i1 LIMIT 5;
      
      The server erroneously used an item of empty outer-joined
      table as a common constant of a Item_equal (multi-equivalence
      expression).
      By the fix for the bug 16590 the constant status of such
      an item has been propagated to st_table::const_key_parts
      map bits related to other Item_equal argument-related
      key parts (those are obviously not constant in our case).
      As far as test_if_skip_sort_order function skips constant
      prefixes of testing keys, this caused an ignorance of
      available indices, since some prefixes were marked as
      constant by mistake.
     @ mysql-test/r/order_by.result
        Test case for bug #38745.
     @ mysql-test/t/order_by.test
        Test case for bug #38745.
     @ sql/item_cmpfunc.cc
        Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                    when it should use index
        
        - Item_equal::is_simple_const() has been added.
        - Item_equal::update_const() and Item_equal::update_used_tables
          have been updated to not take into account constantness
          of empty outer-joined table items.
     @ sql/item_cmpfunc.h
        Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                    when it should use index
        
        Item_equal::is_simple_const() has been added.
[28 May 2010 11:38] 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/109477

3057 Gleb Shchepa	2010-05-28
      Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                  when it should use index
      
      Sometimes the LEFT/RIGHT JOIN with an empty table caused an
      unnecessary filesort.
      
      Sample query, where t1.i1 is indexed and t3 is empty:
      
        SELECT t1.*, t2.* FROM t1 JOIN t2 ON t1.i1 = t2.i2
                             LEFT JOIN t3 ON t2.i2 = t3.i3
          ORDER BY t1.i1 LIMIT 5;
      
      The server erroneously used an item of empty outer-joined
      table as a common constant of a Item_equal (multi-equivalence
      expression).
      By the fix for the bug 16590 the constant status of such
      an item has been propagated to st_table::const_key_parts
      map bits related to other Item_equal argument-related
      key parts (those are obviously not constant in our case).
      As far as test_if_skip_sort_order function skips constant
      prefixes of testing keys, this caused an ignorance of
      available indices, since some prefixes were marked as
      constant by mistake.
     @ mysql-test/r/order_by.result
        Test case for bug #38745.
     @ mysql-test/t/order_by.test
        Test case for bug #38745.
     @ sql/item.h
        Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                    when it should use index
        
        Item::is_outer_field() has been added and overloaded for
        Item_field and Item_ref classes.
     @ sql/item_cmpfunc.cc
        Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                    when it should use index
        
        Item_equal::update_const() and Item_equal::update_used_tables()
        have been updated to not take into account the constantness
        of outer-joined table items.
[31 May 2010 11:50] 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/109610

3079 Gleb Shchepa	2010-05-31
      Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                  when it should use index
      
      Sometimes the LEFT/RIGHT JOIN with an empty table caused an
      unnecessary filesort.
      
      Sample query, where t1.i1 is indexed and t3 is empty:
      
        SELECT t1.*, t2.* FROM t1 JOIN t2 ON t1.i1 = t2.i2
                             LEFT JOIN t3 ON t2.i2 = t3.i3
          ORDER BY t1.i1 LIMIT 5;
      
      The server erroneously used an item of empty outer-joined
      table as a common constant of a Item_equal (multi-equivalence
      expression).
      By the fix for the bug 16590 the constant status of such
      an item has been propagated to st_table::const_key_parts
      map bits related to other Item_equal argument-related
      key parts (those are obviously not constant in our case).
      As far as test_if_skip_sort_order function skips constant
      prefixes of testing keys, this caused an ignorance of
      available indices, since some prefixes were marked as
      constant by mistake.
     @ mysql-test/r/order_by.result
        Test case for bug #38745.
     @ mysql-test/t/order_by.test
        Test case for bug #38745.
     @ sql/item.h
        Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                    when it should use index
        
        Item::is_outer_field() has been added and overloaded for
        Item_field and Item_ref classes.
     @ sql/item_cmpfunc.cc
        Bug #38745: MySQL 5.1 optimizer uses filesort for ORDER BY
                    when it should use index
        
        Item_equal::update_const() and Item_equal::update_used_tables()
        have been updated to not take into account the constantness
        of outer-joined table items.
[15 Jun 2010 8:22] Bugs System
Pushed into 5.5.5-m3 (revid:alik@sun.com-20100615080459-smuswd9ooeywcxuc) (version source revid:mmakela@bk-internal.mysql.com-20100415070122-1nxji8ym4mao13ao) (merge vers: 5.1.47) (pib:16)
[15 Jun 2010 8:40] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100615080558-cw01bzdqr1bdmmec) (version source revid:mmakela@bk-internal.mysql.com-20100415070122-1nxji8ym4mao13ao) (pib:16)
[22 Jun 2010 0:05] Igor Babaev
Gleb,

A proper fix for this bug would be:

+++ sql/sql_select.cc   2010-06-05 17:31:33 +0000
@@ -2663,6 +2663,7 @@ make_join_statistics(JOIN *join, TABLE_L
 #endif
       {                                                // Empty table
         s->dependent= 0;                        // Ignore LEFT JOIN depend.
+       *s->on_expr_ref= 0;
        set_position(join,const_count++,s,(KEYUSE*) 0);
        continue;
       }

Please, reconsider your patch.

Regards,
Igor.
[20 Jul 2010 2:46] Paul DuBois
Noted in 5.5.5 changelog.

The optimizer sometimes used filesort for ORDER BY when it should
have used an index.