Bug #30584 delete with order by and limit clauses does not use limit efficiently
Submitted: 23 Aug 2007 3:31 Modified: 22 Jan 2009 14:59
Reporter: Mark Callaghan Email Updates:
Status: Duplicate Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:5.0.37,5.1.22 OS:Any
Assigned to: Gleb Shchepa
Tags: bfsm_2007_10_18, delete, limit, Optimizer, order
Triage: Triaged: D3 (Medium) / R3 (Medium) / E4 (High)

[23 Aug 2007 3:31] Mark Callaghan
Description:
This problem also occurs with MySQL 5

On SELECT statements with an ORDER BY and LIMIT clause when the ORDER BY is evaluated using an index, the LIMIT clause limits the number of rows fetched from the index. This does not appear to be done for DELETE statements. For DELETE statements, all rows for which the WHERE clause is true are fetched, the result is sorted, the LIMIT clause is applied to the result set and then the delete is done. This can fetch many more rows than needed.

How to repeat:
create table t(i int primary key) type = innodb;
insert into t values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);

select * from t where i > 0 and i <= 8 order by i limit 5;
show status like 'Sort_rows';
show status like 'Sort_range';

begin; delete from t where i > 0 and i <= 8 order by i limit 5; rollback;
show status like 'Sort_rows';
show status like 'Sort_range';

Sort_rows == 0 after the select and 8 after the delete.
Sort_range == 0 after the select and 1 after the delete.
[23 Aug 2007 4:05] Mark Callaghan
This also occurs with MySQL 4.0.26
[23 Aug 2007 4:12] Lachlan Mulcahy
Verified.
[30 Aug 2007 10:51] Konstantin Osipov
An excellent opportunity to make sure that DELETE is implemented using Select_send  hierarchy.
[4 Oct 2007 3:44] Gary Pendergast
Verified with MySQL 5.1.22 as well.
[11 Jun 2008 18:43] Patrick Feliciano
I am also having an issue with this.  When ever I try to clean up one of my larger tables my system becomes completely bogged down even though I've limited my deletes.  The tables keeps getting bigger but I can't clean up old queries without damaging production performance.  Is there a fix for this?  Seems this bug has come up before and is now reintroduced? http://bugs.mysql.com/12915
[27 Jun 2008 10:05] Sergey Petrunya
See also BUG#36569
[11 Dec 2008 20:40] 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/61409

2732 Gleb Shchepa	2008-12-12
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      During the Execution of single-table UPDATE and DELETE
      statements with ORDER BY clause an optimizer used the
      filesort algorithm even if not required.
      
      Extra optimization has been added.
[22 Jan 2009 10:51] Gleb Shchepa
This bug will be fixed by the fix for bug #36569. Please track the other one
[22 Jan 2009 14:59] Georgi Kodinov
Closing as a duplicate of bug #36569
[11 Mar 2010 6:36] 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/102955

3119 Gleb Shchepa	2010-03-11
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      During the Execution of single-table UPDATE and DELETE
      statements with ORDER BY clause an optimizer used the
      filesort algorithm even if not required.
      
      Extra optimization has been added.
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584 and bug #36569.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584 and bug #36569.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        The QUICK_SELECT_I::is_ordered_by function has been added.
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        The QUICK_SELECT_I::is_ordered_by function has been added.
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_delete: an optimization has been added to skip
        double-sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        1. The const_expression_in_where function has been modified
           to accept both Item and Field pointers via intermediate
           wrap_field_or_item class object.
        2. Public const_in_where functions have been added.
        3. Static test_if_order_by_key function has been moved to
           public scope. Also a part of this function has been
           extracted as a new st_table::get_order_by_usable_keys
           method.
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        1. test_if_order_by_key() has been moved to public scope.
        2. New const_in_where functions have been added.
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_update: an optimization has been added to skip
        double-sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        st_table::const_key_parts,
        st_table::update_const_key_parts,
        st_table::get_order_by_usable_keys,
        st_table::simple_test_if_skip_sort_order and
        st_order::simple_remove_const
        methods have been added.
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        st_table::const_key_parts,
        st_table::update_const_key_parts,
        st_table::get_order_by_usable_keys,
        st_table::simple_test_if_skip_sort_order and
        st_order::simple_remove_const
        methods have been added.
[11 Mar 2010 15:55] 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/103029

3119 Gleb Shchepa	2010-03-11
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      During the Execution of single-table UPDATE and DELETE
      statements with ORDER BY clause an optimizer used the
      filesort algorithm even if not required.
      
      Extra optimization has been added: when applicable,
      single-table UPDATE/DELETE statements use existing index 
      instead of filesort like similar SELECT queries do (excluding
      cases when UPDATE is trying to update its sorting key).
      I.e. from now most of single-table UPDATE & DELETE
      statements should show same SHOW STATUS LIKE 'Sort%'
      output as similar SELECT queries.
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584 and bug #36569.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584 and bug #36569.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        The QUICK_SELECT_I::is_ordered_by function has been added.
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        The QUICK_SELECT_I::is_ordered_by function has been added.
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_delete: an optimization has been added to skip
        double-sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        1. The const_expression_in_where function has been modified
           to accept both Item and Field pointers via intermediate
           wrap_field_or_item class object.
        2. Public const_item_in_where and const_field_in_where functions
           have been added.
        3. Static test_if_order_by_key function has been moved to
           public scope. Also a part of this function has been
           extracted as a new st_table::get_order_by_usable_keys
           method.
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        1. test_if_order_by_key() has been moved to public scope.
        2. Public const_item_in_where and const_field_in_where functions
           have been added.
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_update: an optimization has been added to skip
        double-sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        st_table::const_key_parts,
        st_table::update_const_key_parts,
        st_table::get_order_by_usable_keys,
        st_table::simple_test_if_skip_sort_order and
        st_order::simple_remove_const
        methods have been added.
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        st_table::const_key_parts,
        st_table::update_const_key_parts,
        st_table::get_order_by_usable_keys,
        st_table::simple_test_if_skip_sort_order and
        st_order::simple_remove_const
        methods have been added.
[31 Mar 2010 12:26] 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/104705

3128 Gleb Shchepa	2010-03-31
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      During the execution of single-table UPDATE and DELETE
      statements with ORDER BY clause an optimizer used the
      filesort algorithm even if not required.
      
      Extra optimization has been added: when applicable,
      single-table UPDATE/DELETE statements use existing index
      instead of filesort like similar SELECT queries do.
      I.e. from now most of single-table UPDATE & DELETE
      statements should show same SHOW STATUS LIKE 'Sort%'
      output as similar SELECT queries.
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584 and bug #36569.
     @ mysql-test/r/update.result
        Updated result for optimized query, bug #30584.
        Note:
        "Handler_read_last 1" omitted, see bug 52312:
        lost Handler_read_last status variable.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584 and bug #36569.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_RANGE_SELECT::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_SELECT_I::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
        * SQL_SELECT::set_quick()
     @ sql/records.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * init_read_record_idx() has been modified to allow reverse index scan
        
        New functions:
        * rr_index_last()
        * rr_index_desc()
     @ sql/records.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        init_read_record_idx() has been modified to allow reverse index scan
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_delete: an optimization has been added to skip
        double-sorting with ORDER BY clause where select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * The const_expression_in_where function has been modified
          to accept both Item and Field pointers via intermediate
          wrap_field_or_item class object.
        
        * Static test_if_order_by_key function has been moved to
          public scope to share with QUICK_SELECT_I::is_ordered_by().
        
        New functions:
        * get_index_for_order()
        * test_if_cheaper_ordering() has been extracted from
          test_if_skip_sort_order() to share with get_index_for_order()
        * simple_remove_const()
        * const_item_in_where() and const_field_in_where()
        
        * new internal wrapper class: wrap_field_or_item.
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * test_if_order_by_key() has been moved to public scope.
        
        New functions:
        * test_if_cheaper_ordering()
        * const_field_in_where() and const_item_in_where()
        * simple_remove_const()
        * get_index_for_order()
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_update: an optimization has been added to skip
        double-sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
[16 Apr 2010 9:37] 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/105837

3140 Gleb Shchepa	2010-04-16
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      
      Execution of single-table UPDATE and DELETE statements did not use the
      same optimizer as was used in the compilation of SELECT statements.
      Instead, it had an optimizer of its own that did not take into account
      that you can omit sorting by retrieving rows using an index.
      
      Extra optimization has been added: when applicable, single-table
      UPDATE/DELETE statements use an existing index instead of filesort. A
      corresponding SELECT query would do the former.
      
      Also handling of the DESC ordering expression has been added when
      reverse index scan is applicable.
      
      From now on most single table UPDATE and DELETE statements show the
      same disk access patterns as the corresponding SELECT query. We verify
      this by comparing the result of SHOW STATUS LIKE 'Sort%
      
      Currently the get_index_for_order function
      a) checks quick select index (if any) for compatibility with the
         ORDER expression list or
      b) chooses the cheapest available compatible index, but only if
         the index scan is cheaper than filesort.
      Second way is implemented by the new test_if_cheaper_ordering
      function (extracted part the test_if_skip_sort_order()).
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584 and bug #36569.
     @ mysql-test/r/update.result
        Updated result for optimized query, bug #30584.
        Note:
        "Handler_read_last 1" omitted, see bug 52312:
        lost Handler_read_last status variable.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584 and bug #36569.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_RANGE_SELECT::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_SELECT_I::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
        * SQL_SELECT::set_quick()
     @ sql/records.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * init_read_record_idx() has been modified to allow reverse index scan
        
        New functions:
        * rr_index_last()
        * rr_index_desc()
     @ sql/records.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        init_read_record_idx() has been modified to allow reverse index scan
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_delete: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * The const_expression_in_where function has been modified
          to accept both Item and Field pointers via intermediate
          wrap_field_or_item class object.
        
        * Static test_if_order_by_key function has been moved to
          public scope to share with QUICK_SELECT_I::is_ordered_by().
        
        New functions:
        * get_index_for_order()
        * test_if_cheaper_ordering() has been extracted from
          test_if_skip_sort_order() to share with get_index_for_order()
        * simple_remove_const()
        * const_item_in_where() and const_field_in_where()
        
        * new internal wrapper class: wrap_field_or_item.
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * test_if_order_by_key() has been moved to public scope.
        
        New functions:
        * test_if_cheaper_ordering()
        * const_field_in_where() and const_item_in_where()
        * simple_remove_const()
        * get_index_for_order()
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_update: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
[20 Apr 2010 17: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/106143

3140 Gleb Shchepa	2010-04-20
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      
      Execution of single-table UPDATE and DELETE statements did not use the
      same optimizer as was used in the compilation of SELECT statements.
      Instead, it had an optimizer of its own that did not take into account
      that you can omit sorting by retrieving rows using an index.
      
      Extra optimization has been added: when applicable, single-table
      UPDATE/DELETE statements use an existing index instead of filesort. A
      corresponding SELECT query would do the former.
      
      Also handling of the DESC ordering expression has been added when
      reverse index scan is applicable.
      
      From now on most single table UPDATE and DELETE statements show the
      same disk access patterns as the corresponding SELECT query. We verify
      this by comparing the result of SHOW STATUS LIKE 'Sort%
      
      Currently the get_index_for_order function
      a) checks quick select index (if any) for compatibility with the
         ORDER expression list or
      b) chooses the cheapest available compatible index, but only if
         the index scan is cheaper than filesort.
      Second way is implemented by the new test_if_cheaper_ordering
      function (extracted part the test_if_skip_sort_order()).
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584 and bug #36569.
     @ mysql-test/r/update.result
        Updated result for optimized query, bug #30584.
        Note:
        "Handler_read_last 1" omitted, see bug 52312:
        lost Handler_read_last status variable.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584 and bug #36569.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_RANGE_SELECT::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_SELECT_I::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
        * SQL_SELECT::set_quick()
     @ sql/records.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * init_read_record_idx() has been modified to allow reverse index scan
        
        New functions:
        * rr_index_last()
        * rr_index_desc()
     @ sql/records.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        init_read_record_idx() has been modified to allow reverse index scan
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_delete: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * The const_expression_in_where function has been modified
          to accept both Item and Field pointers.
        
        * Static test_if_order_by_key function has been moved to
          public scope to share with QUICK_SELECT_I::is_ordered_by().
        
        New functions:
        * get_index_for_order()
        * test_if_cheaper_ordering() has been extracted from
          test_if_skip_sort_order() to share with get_index_for_order()
        * simple_remove_const()
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * test_if_order_by_key() and const_expression_in_where() have 
          been moved to public scope.
        
        New functions:
        * test_if_cheaper_ordering()
        * simple_remove_const()
        * get_index_for_order()
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_update: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
[21 Apr 2010 11:44] 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/106247

3140 Gleb Shchepa	2010-04-21
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      
      Execution of single-table UPDATE and DELETE statements did not use the
      same optimizer as was used in the compilation of SELECT statements.
      Instead, it had an optimizer of its own that did not take into account
      that you can omit sorting by retrieving rows using an index.
      
      Extra optimization has been added: when applicable, single-table
      UPDATE/DELETE statements use an existing index instead of filesort. A
      corresponding SELECT query would do the former.
      
      Also handling of the DESC ordering expression has been added when
      reverse index scan is applicable.
      
      From now on most single table UPDATE and DELETE statements show the
      same disk access patterns as the corresponding SELECT query. We verify
      this by comparing the result of SHOW STATUS LIKE 'Sort%
      
      Currently the get_index_for_order function
      a) checks quick select index (if any) for compatibility with the
         ORDER expression list or
      b) chooses the cheapest available compatible index, but only if
         the index scan is cheaper than filesort.
      Second way is implemented by the new test_if_cheaper_ordering
      function (extracted part the test_if_skip_sort_order()).
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584 and bug #36569.
     @ mysql-test/r/update.result
        Updated result for optimized query, bug #30584.
        Note:
        "Handler_read_last 1" omitted, see bug 52312:
        lost Handler_read_last status variable.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584 and bug #36569.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_RANGE_SELECT::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_SELECT_I::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
        * SQL_SELECT::set_quick()
     @ sql/records.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * init_read_record_idx() has been modified to allow reverse index scan
        
        New functions:
        * rr_index_last()
        * rr_index_desc()
     @ sql/records.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        init_read_record_idx() has been modified to allow reverse index scan
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_delete: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * The const_expression_in_where function has been modified
          to accept both Item and Field pointers.
        
        * Static test_if_order_by_key function has been moved to
          public scope to share with QUICK_SELECT_I::is_ordered_by().
        
        New functions:
        * get_index_for_order()
        * test_if_cheaper_ordering() has been extracted from
          test_if_skip_sort_order() to share with get_index_for_order()
        * simple_remove_const()
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * test_if_order_by_key() and const_expression_in_where() have 
          been moved to public scope.
        
        New functions:
        * test_if_cheaper_ordering()
        * simple_remove_const()
        * get_index_for_order()
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_update: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
[17 May 2010 16: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/108458

3140 Gleb Shchepa	2010-05-17
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      
      Execution of single-table UPDATE and DELETE statements did not use the
      same optimizer as was used in the compilation of SELECT statements.
      Instead, it had an optimizer of its own that did not take into account
      that you can omit sorting by retrieving rows using an index.
      
      Extra optimization has been added: when applicable, single-table
      UPDATE/DELETE statements use an existing index instead of filesort. A
      corresponding SELECT query would do the former.
      
      Also handling of the DESC ordering expression has been added when
      reverse index scan is applicable.
      
      From now on most single table UPDATE and DELETE statements show the
      same disk access patterns as the corresponding SELECT query. We verify
      this by comparing the result of SHOW STATUS LIKE 'Sort%
      
      Currently the get_index_for_order function
      a) checks quick select index (if any) for compatibility with the
         ORDER expression list or
      b) chooses the cheapest available compatible index, but only if
         the index scan is cheaper than filesort.
      Second way is implemented by the new test_if_cheaper_ordering
      function (extracted part the test_if_skip_sort_order()).
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584 and bug #36569.
     @ mysql-test/r/update.result
        Updated result for optimized query, bug #30584.
        Note:
        "Handler_read_last 1" omitted, see bug 52312:
        lost Handler_read_last status variable.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584 and bug #36569.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_RANGE_SELECT::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_SELECT_I::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
        * SQL_SELECT::set_quick()
     @ sql/records.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * init_read_record_idx() has been modified to allow reverse index scan
        
        New functions:
        * rr_index_last()
        * rr_index_desc()
     @ sql/records.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        init_read_record_idx() has been modified to allow reverse index scan
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_delete: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * The const_expression_in_where function has been modified
          to accept both Item and Field pointers.
        
        * Static test_if_order_by_key function has been moved to
          public scope to share with QUICK_SELECT_I::is_ordered_by().
        
        New functions:
        * get_index_for_order()
        * test_if_cheaper_ordering() has been extracted from
          test_if_skip_sort_order() to share with get_index_for_order()
        * simple_remove_const()
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * test_if_order_by_key() and const_expression_in_where() have 
          been moved to public scope.
        
        New functions:
        * test_if_cheaper_ordering()
        * simple_remove_const()
        * get_index_for_order()
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_update: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
[17 Jun 2010 12:37] 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/111436

3245 Gleb Shchepa	2010-06-16
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      
      Execution of single-table UPDATE and DELETE statements did not use the
      same optimizer as was used in the compilation of SELECT statements.
      Instead, it had an optimizer of its own that did not take into account
      that you can omit sorting by retrieving rows using an index.
      
      Extra optimization has been added: when applicable, single-table
      UPDATE/DELETE statements use an existing index instead of filesort. A
      corresponding SELECT query would do the former.
      
      Also handling of the DESC ordering expression has been added when
      reverse index scan is applicable.
      
      From now on most single table UPDATE and DELETE statements show the
      same disk access patterns as the corresponding SELECT query. We verify
      this by comparing the result of SHOW STATUS LIKE 'Sort%
      
      Currently the get_index_for_order function
      a) checks quick select index (if any) for compatibility with the
         ORDER expression list or
      b) chooses the cheapest available compatible index, but only if
         the index scan is cheaper than filesort.
      Second way is implemented by the new test_if_cheaper_ordering
      function (extracted part the test_if_skip_sort_order()).
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584 and bug #36569.
     @ mysql-test/r/update.result
        Updated result for optimized query, bug #30584.
        Note:
        "Handler_read_last 1" omitted, see bug 52312:
        lost Handler_read_last status variable.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584 and bug #36569.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_RANGE_SELECT::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_SELECT_I::make_reverse()
        * QUICK_SELECT_I::is_ordered_by()
        * SQL_SELECT::set_quick()
     @ sql/records.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * init_read_record_idx() has been modified to allow reverse index scan
        
        New functions:
        * rr_index_last()
        * rr_index_desc()
     @ sql/records.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        init_read_record_idx() has been modified to allow reverse index scan
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_delete: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * The const_expression_in_where function has been modified
          to accept both Item and Field pointers.
        
        * Static test_if_order_by_key function has been moved to
          public scope to share with QUICK_SELECT_I::is_ordered_by().
        
        New functions:
        * get_index_for_order()
        * test_if_cheaper_ordering() has been extracted from
          test_if_skip_sort_order() to share with get_index_for_order()
        * simple_remove_const()
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * test_if_order_by_key() and const_expression_in_where() have
          been moved to public scope.
        
        New functions:
        * test_if_cheaper_ordering()
        * simple_remove_const()
        * get_index_for_order()
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        mysql_update: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
[22 Jun 2010 21:06] 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/111832

3069 Gleb Shchepa	2010-06-23
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      Also two bugs reported after QA review (before the commit
      of bugs above to public trees, no documentation needed):
      
      Bug #53737: Performance regressions after applying patch
                  for bug 36569
      Bug #53742: UPDATEs have no effect after applying patch
                  for bug 36569
      
      
      Execution of single-table UPDATE and DELETE statements did not use the 
      same optimizer as was used in the compilation of SELECT statements. 
      Instead, it had an optimizer of its own that did not take into account 
      that you can omit sorting by retrieving rows using an index.
      
      Extra optimization has been added: when applicable, single-table 
      UPDATE/DELETE statements use an existing index instead of filesort. A 
      corresponding SELECT query would do the former.
      
      Also handling of the DESC ordering expression has been added when
      reverse index scan is applicable.
      
      From now on most single table UPDATE and DELETE statements show the 
      same disk access patterns as the corresponding SELECT query. We verify 
      this by comparing the result of SHOW STATUS LIKE 'Sort%
      
      Currently the get_index_for_order function 
      a) checks quick select index (if any) for compatibility with the
         ORDER expression list or
      b) chooses the cheapest available compatible index, but only if 
         the index scan is cheaper than filesort.
      Second way is implemented by the new test_if_cheaper_ordering
      function (extracted part the test_if_skip_sort_order()).
     @ mysql-test/r/log_state.result
        Updated result for optimized query, bug #36569.
     @ mysql-test/r/single_delete_update.result
        Test case for bug #30584, bug #36569 and bug #53742.
     @ mysql-test/r/update.result
        Updated result for optimized query, bug #30584.
        Note:
        "Handler_read_last 1" omitted, see bug 52312:
        lost Handler_read_last status variable.
     @ mysql-test/t/single_delete_update.test
        Test case for bug #30584, bug #36569 and bug #53742.
     @ sql/opt_range.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New QUICK_RANGE_SELECT::make_reverse method has been added.
     @ sql/opt_range.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * get_index_for_order() has been rewritten entirely and moved
          to sql_select.cc
        
        New functions:
        * QUICK_SELECT_I::make_reverse()
        * SQL_SELECT::set_quick()
     @ sql/records.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        * init_read_record_idx() has been modified to allow reverse index scan
        
        New functions:
        * rr_index_last()
        * rr_index_desc()
     @ sql/records.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        init_read_record_idx() has been modified to allow reverse index scan
     @ sql/sql_delete.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
            
        mysql_delete: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where select
        result ordering is acceptable.
     @ sql/sql_select.cc
        Bug #30584, bug #36569, bug #53737, bug #53742:
          UPDATE/DELETE ... WHERE ... ORDER BY...  always does a filesort
          even if not required
            
        The const_expression_in_where function has been modified
        to accept both Item and Field pointers.
        
        New functions:
        * get_index_for_order()
        * test_if_cheaper_ordering() has been extracted from
          test_if_skip_sort_order() to share with get_index_for_order()
        * simple_remove_const()
     @ sql/sql_select.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
            
        New functions:
        * test_if_cheaper_ordering()
        * simple_remove_const()
        * get_index_for_order()
     @ sql/sql_update.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
            
        mysql_update: an optimization has been added to skip
        unnecessary sorting with ORDER BY clause where a select
        result ordering is acceptable.
     @ sql/table.cc
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
     @ sql/table.h
        Bug #30584, bug #36569: UPDATE/DELETE ... WHERE ... ORDER BY...
                                always does a filesort even if not required
        
        New functions:
        * TABLE::update_const_key_parts()
        * is_simple_order()
[23 Jul 2010 12:28] Bugs System
Pushed into mysql-trunk 5.5.6-m3 (revid:alik@sun.com-20100723121820-jryu2fuw3pc53q9w) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:18)
[23 Jul 2010 12:31] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100723121929-90e9zemk3jkr2ocy) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (pib:18)