List:Commits« Previous MessageNext Message »
From:Gleb Shchepa Date:April 21 2010 11:43am
Subject:bzr commit into mysql-next-mr branch (gshchepa:3140) Bug#30584
Bug#36569
View as plain text  
#At file:///mnt/sda7/work/mysql-next-mr/ based on revid:alik@stripped

 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()

    added:
      mysql-test/r/single_delete_update.result
      mysql-test/t/single_delete_update.test
    modified:
      mysql-test/r/update.result
      sql/opt_range.cc
      sql/opt_range.h
      sql/records.cc
      sql/records.h
      sql/sql_delete.cc
      sql/sql_select.cc
      sql/sql_select.h
      sql/sql_update.cc
      sql/table.cc
      sql/table.h
=== added file 'mysql-test/r/single_delete_update.result'
--- a/mysql-test/r/single_delete_update.result	1970-01-01 00:00:00 +0000
+++ b/mysql-test/r/single_delete_update.result	2010-04-21 11:42:35 +0000
@@ -0,0 +1,939 @@
+#
+# Bug #30584: delete with order by and limit clauses does not use
+#             limit efficiently
+#
+CREATE TABLE t1 (i INT);
+INSERT INTO t1 VALUES (10),(11),(12),(13),(14),(15),(16),(17),(18),(19),
+(20),(21),(22),(23),(24),(25);
+CREATE TABLE t2(a INT, i INT PRIMARY KEY);
+INSERT INTO t2 (i) SELECT i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+a	i
+NULL	11
+NULL	12
+NULL	13
+NULL	14
+NULL	15
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	1
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+FLUSH STATUS;
+DELETE FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	1
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i;
+a	i
+NULL	16
+NULL	17
+NULL	18
+DROP TABLE t2;
+#
+# index on field prefix:
+#
+CREATE TABLE t2(a INT, i CHAR(2), INDEX(i(1)));
+INSERT INTO t2 (i) SELECT i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+a	i
+NULL	11
+NULL	12
+NULL	13
+NULL	14
+NULL	15
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	5
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	17
+FLUSH STATUS;
+DELETE FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	8
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	5
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i;
+a	i
+NULL	16
+NULL	17
+NULL	18
+DROP TABLE t2;
+#
+# constant inside ORDER BY list, should use filesort
+# on a small table
+#
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c) SELECT i, i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+a	b	c	d
+10	10	10	NULL
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	17
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	17
+## should be 5 (previous LIMIT)
+SELECT 1 - COUNT(*) FROM t2 WHERE b = 10;
+1 - COUNT(*)
+1
+DROP TABLE t2;
+#
+# same test as above (constant inside ORDER BY list), but with
+# a larger table - should not use filesort
+#
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c) SELECT i, i, i FROM t1;
+INSERT INTO t2 (a, b, c) SELECT t1.i, t1.i, t1.i FROM t1, t1 x1, t1 x2;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+a	b	c	d
+10	10	10	NULL
+10	10	10	NULL
+10	10	10	NULL
+10	10	10	NULL
+10	10	10	NULL
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+## should be 5 (previous LIMIT)
+SELECT 257 - COUNT(*) FROM t2 WHERE b = 10;
+257 - COUNT(*)
+5
+DROP TABLE t2;
+#
+# as above + partial index, should use filesort
+#
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), d CHAR(2), INDEX (a,b(1),c));
+INSERT INTO t2 SELECT i, i, i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+a	b	c	d
+10	10	10	10
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	17
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+a	b	c	d
+DROP TABLE t2;
+#
+# as above but index is without HA_READ_ORDER flag, should use filesort
+#
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), d CHAR(2), INDEX (a,b,c)) ENGINE=HEAP;
+INSERT INTO t2 SELECT i, i, i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+a	b	c	d
+10	10	10	10
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	17
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+a	b	c	d
+DROP TABLE t2;
+#
+# quick select is Index Merge, should use filesort
+#
+CREATE TABLE t2 (i INT, key1 INT, key2 INT, INDEX (key1), INDEX (key2));
+INSERT INTO t2 (key1, key2) SELECT i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+i	key1	key2
+NULL	10	10
+NULL	11	11
+NULL	12	12
+NULL	13	13
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	1
+Sort_rows	4
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	2
+Handler_read_next	7
+Handler_read_prev	0
+Handler_read_rnd	4
+Handler_read_rnd_next	0
+EXPLAIN EXTENDED SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+x	x	x	x	x	x	x	x	x	x	Using sort_union(key1,key2); Using where; Using filesort
+Warnings:
+x	x	x
+FLUSH STATUS;
+DELETE FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	4
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	4
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+i	key1	key2
+EXPLAIN EXTENDED SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+x	x	x	x	x	x	x	x	x	x	Using sort_union(key1,key2); Using where; Using filesort
+Warnings:
+x	x	x
+DROP TABLE t2;
+#
+# mixed sorting direction, should use filesort
+#
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), INDEX (a, b));
+INSERT INTO t2 SELECT i, i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a, b DESC LIMIT 5;
+a	b	c
+10	10	10
+11	11	11
+12	12	12
+13	13	13
+14	14	14
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	5
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	17
+FLUSH STATUS;
+DELETE FROM t2 ORDER BY a, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	16
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	5
+Handler_read_rnd_next	17
+SELECT * FROM t2 ORDER BY a, b DESC;
+a	b	c
+15	15	15
+16	16	16
+17	17	17
+18	18	18
+19	19	19
+20	20	20
+21	21	21
+22	22	22
+23	23	23
+24	24	24
+25	25	25
+DROP TABLE t2;
+#
+# LIMIT with no WHERE and DESC direction, should not use filesort
+#
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), INDEX (a, b));
+INSERT INTO t2 (a, b) SELECT i, i FROM t1;
+INSERT INTO t2 (a, b) SELECT t1.i, t1.i FROM t1, t1 x1, t1 x2;
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a, b LIMIT 5;
+a	b	c
+10	10	NULL
+10	10	NULL
+10	10	NULL
+10	10	NULL
+10	10	NULL
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a DESC, b DESC LIMIT 5;
+a	b	c
+25	25	NULL
+25	25	NULL
+25	25	NULL
+25	25	NULL
+25	25	NULL
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	4
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+FLUSH STATUS;
+DELETE FROM t2 ORDER BY a DESC, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	4
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+SELECT * FROM t2 WHERE c = 10 ORDER BY a DESC, b DESC;
+a	b	c
+DROP TABLE t1, t2;
+#
+# Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a filesort
+#             even if not required
+#
+CREATE TABLE t1 (i INT);
+INSERT INTO t1 VALUES (10),(11),(12),(13),(14),(15),(16),(17),(18),(19),
+(20),(21),(22),(23),(24),(25);
+CREATE TABLE t2(a INT, i INT PRIMARY KEY);
+INSERT INTO t2 (i) SELECT i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+a	i
+NULL	11
+NULL	12
+NULL	13
+NULL	14
+NULL	15
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	1
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+FLUSH STATUS;
+UPDATE t2 SET a = 10 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	1
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	5
+Handler_read_rnd_next	0
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i;
+a	i
+10	11
+10	12
+10	13
+10	14
+10	15
+NULL	16
+NULL	17
+NULL	18
+DROP TABLE t2;
+#
+# index on field prefix:
+#
+CREATE TABLE t2(a INT, i CHAR(2), INDEX(i(1)));
+INSERT INTO t2 (i) SELECT i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+a	i
+NULL	11
+NULL	12
+NULL	13
+NULL	14
+NULL	15
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	5
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	17
+FLUSH STATUS;
+UPDATE t2 SET a = 10 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	5
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	5
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i;
+a	i
+10	11
+10	12
+10	13
+10	14
+10	15
+NULL	16
+NULL	17
+NULL	18
+DROP TABLE t2;
+#
+# constant inside ORDER BY list, should use filesort
+# on a small table
+#
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c) SELECT i, i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+a	b	c	d
+10	10	10	NULL
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	17
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	17
+## should be 5 (previous LIMIT)
+SELECT COUNT(*) FROM t2 WHERE b = 10 AND d = 10 ORDER BY a, c;
+COUNT(*)
+1
+DROP TABLE t2;
+#
+# same test as above (constant inside ORDER BY list), but with
+# a larger table - should not use filesort
+#
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c) SELECT i, i, i FROM t1;
+INSERT INTO t2 (a, b, c) SELECT t1.i, t1.i, t1.i FROM t1, t1 x1, t1 x2;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+a	b	c	d
+10	10	10	NULL
+10	10	10	NULL
+10	10	10	NULL
+10	10	10	NULL
+10	10	10	NULL
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	5
+Handler_read_rnd_next	0
+## should be 5 (previous LIMIT)
+SELECT COUNT(*) FROM t2 WHERE b = 10 AND d = 10 ORDER BY a, c;
+COUNT(*)
+5
+DROP TABLE t2;
+#
+# as above + partial index, should use filesort
+#
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), d CHAR(2), INDEX (a,b(1),c));
+INSERT INTO t2 SELECT i, i, i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+a	b	c	d
+10	10	10	10
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	17
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+a	b	c	d
+10	10	10	10
+DROP TABLE t2;
+#
+# as above but index is without HA_READ_ORDER flag, should use filesort
+#
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), d CHAR(2), INDEX (a,b,c)) ENGINE=HEAP;
+INSERT INTO t2 SELECT i, i, i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+a	b	c	d
+10	10	10	10
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	17
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	1
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+a	b	c	d
+10	10	10	10
+DROP TABLE t2;
+#
+# quick select is Index Merge, should use filesort
+#
+CREATE TABLE t2 (i INT, key1 INT, key2 INT, INDEX (key1), INDEX (key2));
+INSERT INTO t2 (key1, key2) SELECT i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+i	key1	key2
+NULL	10	10
+NULL	11	11
+NULL	12	12
+NULL	13	13
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	1
+Sort_rows	4
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	2
+Handler_read_next	7
+Handler_read_prev	0
+Handler_read_rnd	4
+Handler_read_rnd_next	0
+EXPLAIN EXTENDED SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+x	x	x	x	x	x	x	x	x	x	Using sort_union(key1,key2); Using where; Using filesort
+Warnings:
+x	x	x
+FLUSH STATUS;
+UPDATE t2 SET i = 123 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	4
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	4
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+i	key1	key2
+123	10	10
+123	11	11
+123	12	12
+123	13	13
+EXPLAIN EXTENDED SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+x	x	x	x	x	x	x	x	x	x	Using sort_union(key1,key2); Using where; Using filesort
+Warnings:
+x	x	x
+DROP TABLE t2;
+#
+# mixed sorting direction, should use filesort
+#
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), INDEX (a, b));
+INSERT INTO t2 SELECT i, i, i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a, b DESC LIMIT 5;
+a	b	c
+10	10	10
+11	11	11
+12	12	12
+13	13	13
+14	14	14
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	5
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	17
+FLUSH STATUS;
+UPDATE t2 SET c = 10 ORDER BY a, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	5
+Sort_scan	1
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	5
+Handler_read_rnd_next	17
+SELECT * FROM t2 WHERE c = 10 ORDER BY a, b DESC;
+a	b	c
+10	10	10
+11	11	10
+12	12	10
+13	13	10
+14	14	10
+DROP TABLE t2;
+#
+# LIMIT with no WHERE and DESC direction, should not use filesort
+#
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), INDEX (a, b));
+INSERT INTO t2 (a, b) SELECT i, i FROM t1;
+INSERT INTO t2 (a, b) SELECT t1.i, t1.i FROM t1, t1 x1, t1 x2;
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a, b LIMIT 5;
+a	b	c
+10	10	NULL
+10	10	NULL
+10	10	NULL
+10	10	NULL
+10	10	NULL
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	4
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a DESC, b DESC LIMIT 5;
+a	b	c
+25	25	NULL
+25	25	NULL
+25	25	NULL
+25	25	NULL
+25	25	NULL
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	4
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+FLUSH STATUS;
+UPDATE t2 SET c = 10 ORDER BY a DESC, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SHOW STATUS LIKE 'Handler_read_%';
+Variable_name	Value
+Handler_read_first	0
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	4
+Handler_read_rnd	5
+Handler_read_rnd_next	0
+SELECT * FROM t2 WHERE c = 10 ORDER BY a DESC, b DESC;
+a	b	c
+25	25	10
+25	25	10
+25	25	10
+25	25	10
+25	25	10
+DROP TABLE t1, t2;

=== modified file 'mysql-test/r/update.result'
--- a/mysql-test/r/update.result	2010-03-10 16:10:05 +0000
+++ b/mysql-test/r/update.result	2010-04-21 11:42:35 +0000
@@ -306,8 +306,8 @@ Handler_read_first	0
 Handler_read_key	0
 Handler_read_next	0
 Handler_read_prev	0
-Handler_read_rnd	1
-Handler_read_rnd_next	9
+Handler_read_rnd	0
+Handler_read_rnd_next	0
 alter table t1 disable keys;
 flush status;
 delete from t1 order by a limit 1;

=== added file 'mysql-test/t/single_delete_update.test'
--- a/mysql-test/t/single_delete_update.test	1970-01-01 00:00:00 +0000
+++ b/mysql-test/t/single_delete_update.test	2010-04-21 11:42:35 +0000
@@ -0,0 +1,413 @@
+#
+# Single table specific update/delete tests (mysql_update and mysql_delete)
+#
+
+--echo #
+--echo # Bug #30584: delete with order by and limit clauses does not use
+--echo #             limit efficiently
+--echo #
+
+CREATE TABLE t1 (i INT);
+INSERT INTO t1 VALUES (10),(11),(12),(13),(14),(15),(16),(17),(18),(19),
+                      (20),(21),(22),(23),(24),(25);
+
+CREATE TABLE t2(a INT, i INT PRIMARY KEY);
+INSERT INTO t2 (i) SELECT i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i;
+
+DROP TABLE t2;
+
+--echo #
+--echo # index on field prefix:
+--echo #
+
+CREATE TABLE t2(a INT, i CHAR(2), INDEX(i(1)));
+INSERT INTO t2 (i) SELECT i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i;
+
+DROP TABLE t2;
+
+--echo #
+--echo # constant inside ORDER BY list, should use filesort
+--echo # on a small table
+--echo #
+
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c) SELECT i, i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+let $cnt = `SELECT COUNT(*) FROM t2 WHERE b = 10`;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+--echo ## should be 5 (previous LIMIT)
+eval SELECT $cnt - COUNT(*) FROM t2 WHERE b = 10;
+
+DROP TABLE t2;
+
+--echo #
+--echo # same test as above (constant inside ORDER BY list), but with
+--echo # a larger table - should not use filesort
+--echo #
+
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c) SELECT i, i, i FROM t1;
+
+INSERT INTO t2 (a, b, c) SELECT t1.i, t1.i, t1.i FROM t1, t1 x1, t1 x2;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+let $cnt = `SELECT COUNT(*) FROM t2 WHERE b = 10`;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+--echo ## should be 5 (previous LIMIT)
+eval SELECT $cnt - COUNT(*) FROM t2 WHERE b = 10;
+
+DROP TABLE t2;
+
+--echo #
+--echo # as above + partial index, should use filesort
+--echo #
+
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), d CHAR(2), INDEX (a,b(1),c));
+INSERT INTO t2 SELECT i, i, i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+
+DROP TABLE t2;
+
+--echo #
+--echo # as above but index is without HA_READ_ORDER flag, should use filesort
+--echo #
+
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), d CHAR(2), INDEX (a,b,c)) ENGINE=HEAP;
+INSERT INTO t2 SELECT i, i, i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+
+DROP TABLE t2;
+
+--echo #
+--echo # quick select is Index Merge, should use filesort
+--echo #
+
+CREATE TABLE t2 (i INT, key1 INT, key2 INT, INDEX (key1), INDEX (key2));
+INSERT INTO t2 (key1, key2) SELECT i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+--replace_column 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x
+EXPLAIN EXTENDED SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+--replace_column 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x
+EXPLAIN EXTENDED SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+DROP TABLE t2;
+
+--echo #
+--echo # mixed sorting direction, should use filesort
+--echo #
+
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), INDEX (a, b));
+INSERT INTO t2 SELECT i, i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+DELETE FROM t2 ORDER BY a, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 ORDER BY a, b DESC;
+
+DROP TABLE t2;
+
+--echo #
+--echo # LIMIT with no WHERE and DESC direction, should not use filesort
+--echo #
+
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), INDEX (a, b));
+INSERT INTO t2 (a, b) SELECT i, i FROM t1;
+INSERT INTO t2 (a, b) SELECT t1.i, t1.i FROM t1, t1 x1, t1 x2;
+
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a, b LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a DESC, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+DELETE FROM t2 ORDER BY a DESC, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE c = 10 ORDER BY a DESC, b DESC;
+
+DROP TABLE t1, t2;
+
+
+--echo #
+--echo # Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a filesort
+--echo #             even if not required
+--echo #
+
+CREATE TABLE t1 (i INT);
+INSERT INTO t1 VALUES (10),(11),(12),(13),(14),(15),(16),(17),(18),(19),
+                      (20),(21),(22),(23),(24),(25);
+
+CREATE TABLE t2(a INT, i INT PRIMARY KEY);
+INSERT INTO t2 (i) SELECT i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+UPDATE t2 SET a = 10 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i;
+
+DROP TABLE t2;
+
+--echo #
+--echo # index on field prefix:
+--echo #
+
+CREATE TABLE t2(a INT, i CHAR(2), INDEX(i(1)));
+INSERT INTO t2 (i) SELECT i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+UPDATE t2 SET a = 10 WHERE i > 10 AND i <= 18 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE i > 10 AND i <= 18 ORDER BY i;
+
+DROP TABLE t2;
+
+--echo #
+--echo # constant inside ORDER BY list, should use filesort
+--echo # on a small table
+--echo #
+
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c) SELECT i, i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+let $cnt = `SELECT COUNT(*) FROM t2 WHERE b = 10`;
+
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+--echo ## should be 5 (previous LIMIT)
+SELECT COUNT(*) FROM t2 WHERE b = 10 AND d = 10 ORDER BY a, c;
+
+DROP TABLE t2;
+
+--echo #
+--echo # same test as above (constant inside ORDER BY list), but with
+--echo # a larger table - should not use filesort
+--echo #
+
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c) SELECT i, i, i FROM t1;
+
+INSERT INTO t2 (a, b, c) SELECT t1.i, t1.i, t1.i FROM t1, t1 x1, t1 x2;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+let $cnt = `SELECT COUNT(*) FROM t2 WHERE b = 10`;
+
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+--echo ## should be 5 (previous LIMIT)
+SELECT COUNT(*) FROM t2 WHERE b = 10 AND d = 10 ORDER BY a, c;
+
+DROP TABLE t2;
+
+--echo #
+--echo # as above + partial index, should use filesort
+--echo #
+
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), d CHAR(2), INDEX (a,b(1),c));
+INSERT INTO t2 SELECT i, i, i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+
+DROP TABLE t2;
+
+--echo #
+--echo # as above but index is without HA_READ_ORDER flag, should use filesort
+--echo #
+
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), d CHAR(2), INDEX (a,b,c)) ENGINE=HEAP;
+INSERT INTO t2 SELECT i, i, i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+
+DROP TABLE t2;
+
+--echo #
+--echo # quick select is Index Merge, should use filesort
+--echo #
+
+CREATE TABLE t2 (i INT, key1 INT, key2 INT, INDEX (key1), INDEX (key2));
+INSERT INTO t2 (key1, key2) SELECT i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+--replace_column 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x
+EXPLAIN EXTENDED SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+
+FLUSH STATUS;
+UPDATE t2 SET i = 123 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+--replace_column 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x
+EXPLAIN EXTENDED SELECT * FROM t2 WHERE key1 < 13 or key2 < 14 ORDER BY key1;
+
+DROP TABLE t2;
+
+--echo #
+--echo # mixed sorting direction, should use filesort
+--echo #
+
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), INDEX (a, b));
+INSERT INTO t2 SELECT i, i, i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+UPDATE t2 SET c = 10 ORDER BY a, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE c = 10 ORDER BY a, b DESC;
+
+DROP TABLE t2;
+
+--echo #
+--echo # LIMIT with no WHERE and DESC direction, should not use filesort
+--echo #
+
+CREATE TABLE t2 (a CHAR(2), b CHAR(2), c CHAR(2), INDEX (a, b));
+INSERT INTO t2 (a, b) SELECT i, i FROM t1;
+INSERT INTO t2 (a, b) SELECT t1.i, t1.i FROM t1, t1 x1, t1 x2;
+
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a, b LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+SELECT * FROM t2 ORDER BY a DESC, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+
+FLUSH STATUS;
+UPDATE t2 SET c = 10 ORDER BY a DESC, b DESC LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SHOW STATUS LIKE 'Handler_read_%';
+SELECT * FROM t2 WHERE c = 10 ORDER BY a DESC, b DESC;
+
+DROP TABLE t1, t2;

=== modified file 'sql/opt_range.cc'
--- a/sql/opt_range.cc	2010-03-31 14:05:33 +0000
+++ b/sql/opt_range.cc	2010-04-21 11:42:35 +0000
@@ -1838,96 +1838,6 @@ SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_P
 
 
 /*
-  Find the best index to retrieve first N records in given order
-
-  SYNOPSIS
-    get_index_for_order()
-      table  Table to be accessed
-      order  Required ordering
-      limit  Number of records that will be retrieved
-
-  DESCRIPTION
-    Find the best index that allows to retrieve first #limit records in the 
-    given order cheaper then one would retrieve them using full table scan.
-
-  IMPLEMENTATION
-    Run through all table indexes and find the shortest index that allows
-    records to be retrieved in given order. We look for the shortest index
-    as we will have fewer index pages to read with it.
-
-    This function is used only by UPDATE/DELETE, so we take into account how
-    the UPDATE/DELETE code will work:
-     * index can only be scanned in forward direction
-     * HA_EXTRA_KEYREAD will not be used
-    Perhaps these assumptions could be relaxed.
-
-  RETURN
-    Number of the index that produces the required ordering in the cheapest way
-    MAX_KEY if no such index was found.
-*/
-
-uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit)
-{
-  uint idx;
-  uint match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
-  ORDER *ord;
-  
-  for (ord= order; ord; ord= ord->next)
-    if (!ord->asc)
-      return MAX_KEY;
-
-  for (idx= 0; idx < table->s->keys; idx++)
-  {
-    if (!(table->keys_in_use_for_query.is_set(idx)))
-      continue;
-    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
-    uint n_parts=  table->key_info[idx].key_parts;
-    uint partno= 0;
-    
-    /* 
-      The below check is sufficient considering we now have either BTREE 
-      indexes (records are returned in order for any index prefix) or HASH 
-      indexes (records are not returned in order for any index prefix).
-    */
-    if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER))
-      continue;
-    for (ord= order; ord && partno < n_parts; ord= ord->next, partno++)
-    {
-      Item *item= order->item[0];
-      if (!(item->type() == Item::FIELD_ITEM &&
-           ((Item_field*)item)->field->eq(keyinfo[partno].field)))
-        break;
-    }
-    
-    if (!ord && table->key_info[idx].key_length < match_key_len)
-    {
-      /* 
-        Ok, the ordering is compatible and this key is shorter then
-        previous match (we want shorter keys as we'll have to read fewer
-        index pages for the same number of records)
-      */
-      match_key= idx;
-      match_key_len= table->key_info[idx].key_length;
-    }
-  }
-
-  if (match_key != MAX_KEY)
-  {
-    /* 
-      Found an index that allows records to be retrieved in the requested 
-      order. Now we'll check if using the index is cheaper then doing a table
-      scan.
-    */
-    double full_scan_time= table->file->scan_time();
-    double index_scan_time= table->file->read_time(match_key, 1, limit);
-    if (index_scan_time > full_scan_time)
-      match_key= MAX_KEY;
-  }
-  return match_key;
-}
-
-
-/*
   Table rows retrieval plan. Range optimizer creates QUICK_SELECT_I-derived
   objects from table read plans.
 */
@@ -11696,6 +11606,52 @@ void QUICK_RANGE_SELECT::dbug_dump(int i
   /* purecov: end */    
 }
 
+
+/**
+  Create a compatible quick select with the result ordered in an opposite way
+
+  @retval NULL in case of errors (OOM etc)
+  @retval pointer to a newly created QUICK_SELECT_DESC if success
+*/
+
+QUICK_SELECT_I *QUICK_RANGE_SELECT::make_reverse()
+{
+  QUICK_SELECT_DESC *new_quick= new QUICK_SELECT_DESC(this, used_key_parts);
+  if (new_quick == NULL || new_quick->error != 0)
+  {
+    delete new_quick;
+    return NULL;
+  }
+  return new_quick;
+}
+
+
+/**
+  Test if the result set sorting order is compatible with ORDER BY
+
+  @param order            Linked list of ORDER BY arguments
+
+  @return TRUE if ORDER BY may be ignored
+*/
+
+bool QUICK_SELECT_I::is_ordered_by(ORDER *order)
+{
+  if (!order)
+    return TRUE;
+
+  if (index == MAX_KEY ||
+      !(head->file->index_flags(index, 0, 1) & HA_READ_ORDER))
+    return FALSE;
+
+  uint dummy;
+  switch (test_if_order_by_key(order, head, index, &dummy)) {
+  case -1: return reverse_sorted();
+  case  1: return !reverse_sorted();
+  default: return FALSE;
+  }
+}
+
+
 void QUICK_INDEX_MERGE_SELECT::dbug_dump(int indent, bool verbose)
 {
   List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
@@ -11784,7 +11740,7 @@ void QUICK_GROUP_MIN_MAX_SELECT::dbug_du
 }
 
 
-#endif /* NOT_USED */
+#endif /* !DBUG_OFF */
 
 /*****************************************************************************
 ** Instantiate templates 

=== modified file 'sql/opt_range.h'
--- a/sql/opt_range.h	2010-03-31 14:05:33 +0000
+++ b/sql/opt_range.h	2010-04-21 11:42:35 +0000
@@ -273,6 +273,13 @@ public:
   */
   virtual void dbug_dump(int indent, bool verbose)= 0;
 #endif
+
+  /*
+    Returns a QUICK_SELECT with reverse order of to the index.
+  */
+  virtual QUICK_SELECT_I *make_reverse() { return NULL; }
+
+  bool is_ordered_by(ORDER *order);
 };
 
 
@@ -358,6 +365,7 @@ public:
 #ifndef DBUG_OFF
   void dbug_dump(int indent, bool verbose);
 #endif
+  QUICK_SELECT_I *make_reverse();
 private:
   /* Default copy ctor used by QUICK_SELECT_DESC */
 };
@@ -704,6 +712,7 @@ public:
   int get_next();
   bool reverse_sorted() { return 1; }
   int get_type() { return QS_TYPE_RANGE_DESC; }
+  QUICK_SELECT_I *make_reverse() { return this; } // is already reverse sorted
 private:
   bool range_reads_after_key(QUICK_RANGE *range);
   int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); }
@@ -729,6 +738,7 @@ class SQL_SELECT :public Sql_alloc {
   SQL_SELECT();
   ~SQL_SELECT();
   void cleanup();
+  void set_quick(QUICK_SELECT_I *new_quick) { delete quick; quick= new_quick; }
   bool check_quick(THD *thd, bool force_quick_range, ha_rows limit)
   {
     key_map tmp;
@@ -755,7 +765,6 @@ public:
 QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
                                              struct st_table_ref *ref,
                                              ha_rows records);
-uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit);
 SQL_SELECT *make_select(TABLE *head, table_map const_tables,
 			table_map read_tables, COND *conds,
                         bool allow_null_cond,  int *error);

=== modified file 'sql/records.cc'
--- a/sql/records.cc	2010-03-31 14:05:33 +0000
+++ b/sql/records.cc	2010-04-21 11:42:35 +0000
@@ -42,12 +42,14 @@ static int rr_from_cache(READ_RECORD *in
 static int init_rr_cache(THD *thd, READ_RECORD *info);
 static int rr_cmp(uchar *a,uchar *b);
 static int rr_index_first(READ_RECORD *info);
+static int rr_index_last(READ_RECORD *info);
 static int rr_index(READ_RECORD *info);
+static int rr_index_desc(READ_RECORD *info);
 
 
 /**
-  Initialize READ_RECORD structure to perform full index scan (in forward
-  direction) using read_record.read_record() interface.
+  Initialize READ_RECORD structure to perform full index scan in desired 
+  direction using read_record.read_record() interface
 
     This function has been added at late stage and is used only by
     UPDATE/DELETE. Other statements perform index scans using
@@ -59,10 +61,11 @@ static int rr_index(READ_RECORD *info);
   @param print_error  If true, call table->file->print_error() if an error
                       occurs (except for end-of-records error)
   @param idx          index to scan
+  @param reverse      Scan in the reverse direction
 */
 
 void init_read_record_idx(READ_RECORD *info, THD *thd, TABLE *table,
-                          bool print_error, uint idx)
+                          bool print_error, uint idx, bool reverse)
 {
   empty_record(table);
   bzero((char*) info,sizeof(*info));
@@ -77,7 +80,7 @@ void init_read_record_idx(READ_RECORD *i
   if (!table->file->inited)
     table->file->ha_index_init(idx, 1);
   /* read_record will be changed to rr_index in rr_index_first */
-  info->read_record= rr_index_first;
+  info->read_record= reverse ? rr_index_last : rr_index_first;
 }
 
 
@@ -365,6 +368,29 @@ static int rr_index_first(READ_RECORD *i
 
 
 /**
+  Reads last row in an index scan.
+
+  @param info  	Scan info
+
+  @retval
+    0   Ok
+  @retval
+    -1   End of records
+  @retval
+    1   Error
+*/
+
+static int rr_index_last(READ_RECORD *info)
+{
+  int tmp= info->file->index_last(info->record);
+  info->read_record= rr_index_desc;
+  if (tmp)
+    tmp= rr_handle_error(info, tmp);
+  return tmp;
+}
+
+
+/**
   Reads index sequentially after first row.
 
   Read the next index record (in forward direction) and translate return
@@ -389,6 +415,31 @@ static int rr_index(READ_RECORD *info)
 }
 
 
+/**
+  Reads index sequentially from the last row to the first.
+
+  Read the prev index record (in backward direction) and translate return
+  value.
+
+  @param info  Scan info
+
+  @retval
+    0   Ok
+  @retval
+    -1   End of records
+  @retval
+    1   Error
+*/
+
+static int rr_index_desc(READ_RECORD *info)
+{
+  int tmp= info->file->index_prev(info->record);
+  if (tmp)
+    tmp= rr_handle_error(info, tmp);
+  return tmp;
+}
+
+
 int rr_sequential(READ_RECORD *info)
 {
   int tmp;

=== modified file 'sql/records.h'
--- a/sql/records.h	2009-11-06 16:13:33 +0000
+++ b/sql/records.h	2010-04-21 11:42:35 +0000
@@ -71,7 +71,7 @@ void init_read_record(READ_RECORD *info,
 		      SQL_SELECT *select, int use_record_cache,
                       bool print_errors, bool disable_rr_cache);
 void init_read_record_idx(READ_RECORD *info, THD *thd, TABLE *table,
-                          bool print_error, uint idx);
+                          bool print_error, uint idx, bool reverse);
 void end_read_record(READ_RECORD *info);
 
 void rr_unlock_row(st_join_table *tab);

=== modified file 'sql/sql_delete.cc'
--- a/sql/sql_delete.cc	2010-04-01 19:34:09 +0000
+++ b/sql/sql_delete.cc	2010-04-21 11:42:35 +0000
@@ -48,7 +48,7 @@
 */
 
 bool mysql_delete(THD *thd, TABLE_LIST *table_list, COND *conds,
-                  SQL_LIST *order, ha_rows limit, ulonglong options,
+                  SQL_LIST *order_list, ha_rows limit, ulonglong options,
                   bool reset_auto_increment)
 {
   bool          will_batch;
@@ -61,6 +61,9 @@ bool mysql_delete(THD *thd, TABLE_LIST *
   bool          const_cond_result;
   ha_rows	deleted= 0;
   bool          triggers_applicable;
+  bool          reverse= FALSE;
+  ORDER *order= (ORDER *) ((order_list && order_list->elements) ?
+                           order_list->first : NULL);
   uint usable_index= MAX_KEY;
   SELECT_LEX   *select_lex= &thd->lex->select_lex;
   THD::killed_state killed_status= THD::NOT_KILLED;
@@ -87,7 +90,7 @@ bool mysql_delete(THD *thd, TABLE_LIST *
     DBUG_RETURN(TRUE);
 
   /* check ORDER BY even if it can be ignored */
-  if (order && order->elements)
+  if (order)
   {
     TABLE_LIST   tables;
     List<Item>   fields;
@@ -97,9 +100,9 @@ bool mysql_delete(THD *thd, TABLE_LIST *
     tables.table = table;
     tables.alias = table_list->alias;
 
-      if (select_lex->setup_ref_array(thd, order->elements) ||
+      if (select_lex->setup_ref_array(thd, order_list->elements) ||
 	  setup_order(thd, select_lex->ref_pointer_array, &tables,
-                    fields, all_fields, (ORDER*) order->first))
+                    fields, all_fields, order))
     {
       delete select;
       free_underlaid_joins(thd, &thd->lex->select_lex);
@@ -197,6 +200,7 @@ bool mysql_delete(THD *thd, TABLE_LIST *
 
   table->covering_keys.clear_all();
   table->quick_keys.clear_all();		// Can't use 'only index'
+
   select=make_select(table, 0, 0, conds, 0, &error);
   if (error)
     DBUG_RETURN(TRUE);
@@ -238,22 +242,25 @@ bool mysql_delete(THD *thd, TABLE_LIST *
   if (options & OPTION_QUICK)
     (void) table->file->extra(HA_EXTRA_QUICK);
 
-  if (order && order->elements)
+  if (order)
   {
     uint         length= 0;
     SORT_FIELD  *sortorder;
     ha_rows examined_rows;
     
-    if ((!select || table->quick_keys.is_clear_all()) && limit != HA_POS_ERROR)
-      usable_index= get_index_for_order(table, (ORDER*)(order->first), limit);
+    table->update_const_key_parts(conds);
+    order= simple_remove_const(order, conds);
 
-    if (usable_index == MAX_KEY)
+    bool need_sort;
+    usable_index= get_index_for_order(order, table, select, limit,
+                                      &need_sort, &reverse);
+    if (need_sort)
     {
+      DBUG_ASSERT(usable_index == MAX_KEY);
       table->sort.io_cache= (IO_CACHE *) my_malloc(sizeof(IO_CACHE),
                                                    MYF(MY_FAE | MY_ZEROFILL));
     
-      if (!(sortorder= make_unireg_sortorder((ORDER*) order->first,
-                                             &length, NULL)) ||
+      if (!(sortorder= make_unireg_sortorder(order, &length, NULL)) ||
 	  (table->sort.found_records = filesort(thd, table, sortorder, length,
                                                 select, HA_POS_ERROR, 1,
                                                 &examined_rows))
@@ -280,10 +287,10 @@ bool mysql_delete(THD *thd, TABLE_LIST *
     free_underlaid_joins(thd, select_lex);
     DBUG_RETURN(TRUE);
   }
-  if (usable_index==MAX_KEY)
+  if (usable_index == MAX_KEY || (select && select->quick))
     init_read_record(&info, thd, table, select, 1, 1, FALSE);
   else
-    init_read_record_idx(&info, thd, table, 1, usable_index);
+    init_read_record_idx(&info, thd, table, 1, usable_index, reverse);
 
   init_ftfuncs(thd, select_lex, 1);
   thd_proc_info(thd, "updating");

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2010-04-01 19:34:09 +0000
+++ b/sql/sql_select.cc	2010-04-21 11:42:35 +0000
@@ -135,7 +135,6 @@ static uint build_bitmap_for_nested_join
 static COND *optimize_cond(JOIN *join, COND *conds,
                            List<TABLE_LIST> *join_list,
 			   Item::cond_result *cond_value);
-static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
 static bool open_tmp_table(TABLE *table);
 static bool create_myisam_tmp_table(TABLE *,TMP_TABLE_PARAM *, ulonglong, my_bool);
 static int do_select(JOIN *join,List<Item> *fields,TABLE *tmp_table,
@@ -188,6 +187,13 @@ static COND *make_cond_for_table(COND *c
 				 table_map used_table);
 static Item* part_of_refkey(TABLE *form,Field *field);
 uint find_shortest_key(TABLE *table, const key_map *usable_keys);
+static bool test_if_cheaper_ordering(const JOIN_TAB *tab,
+                                     ORDER *order, TABLE *table,
+                                     key_map usable_keys, int key,
+                                     ha_rows select_limit,
+                                     int *new_key, int *new_key_direction,
+                                     ha_rows *new_select_limit,
+                                     uint *new_used_key_parts= NULL);
 static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,
 				    ha_rows select_limit, bool no_changes,
                                     key_map *map);
@@ -7343,8 +7349,7 @@ remove_const(JOIN *join,ORDER *first_ord
 	*simple_order=0;
       else
       {
-	Item *comp_item=0;
-	if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
+	if (cond && const_expression_in_where(cond,order->item[0]))
 	{
 	  DBUG_PRINT("info",("removing: %s", order->item[0]->full_name()));
 	  continue;
@@ -7374,6 +7379,46 @@ remove_const(JOIN *join,ORDER *first_ord
 }
 
 
+/**
+  Filter out ORDER items those are equal to constants in WHERE
+
+  This function is a limited version of remove_const() for use
+  with non-JOIN statements (i.e. single-table UPDATE and DELETE).
+
+
+  @param order            Linked list of ORDER BY arguments
+  @param cond             WHERE expression
+
+  @return pointer to new filtered ORDER list or NULL if whole list eliminated
+
+  @note
+    This function overwrites input order list.
+*/
+
+ORDER *simple_remove_const(ORDER *order, COND *where)
+{
+  if (!order || !where)
+    return order;
+
+  ORDER *first= NULL, *prev= NULL;
+  for (; order; order= order->next)
+  {
+    DBUG_ASSERT(!order->item[0]->with_sum_func); // should never happen
+    if (!const_expression_in_where(where, order->item[0]))
+    {
+      if (!first)
+        first= order;
+      if (prev)
+        prev->next= order;
+      prev= order;
+    }
+  }
+  if (prev)
+    prev->next= NULL;
+  return first;
+}
+
+
 static int
 return_zero_rows(JOIN *join, select_result *result,TABLE_LIST *tables,
 		 List<Item> &fields, bool send_row, ulonglong select_options,
@@ -9527,13 +9572,50 @@ test_if_equality_guarantees_uniqueness(I
         l->collation.collation == r->collation.collation)));
 }
 
-/**
-  Return TRUE if the item is a const value in all the WHERE clause.
+
+/*
+  Return TRUE if i1 and i2 (if any) are equal items,
+  or if i1 is a wrapper item around the f2 field.
 */
 
-static bool
-const_expression_in_where(COND *cond, Item *comp_item, Item **const_item)
+static bool equal(Item *i1, Item *i2, Field *f2)
 {
+  DBUG_ASSERT(i2 == NULL ^ f2 == NULL);
+
+  if (i2 != NULL)
+    return i1->eq(i2, 1);
+  else if (i1->type() == Item::FIELD_ITEM)
+    return f2->eq(((Item_field *) i1)->field);
+  else
+    return FALSE;
+}
+
+
+/**
+  Test if a field or an item is equal to a constant value in WHERE
+
+  @param        cond            WHERE clause expression
+  @param        comp_item       Item to find in WHERE expression
+                                (if comp_field != NULL)
+  @param        comp_field      Field to find in WHERE expression
+                                (if comp_item != NULL)
+  @param[out]   const_item      intermediate arg, set to Item pointer to NULL 
+
+  @return TRUE if the field is a constant value in WHERE
+
+  @note
+    comp_item and comp_field parameters are mutually exclusive.
+*/
+bool
+const_expression_in_where(COND *cond, Item *comp_item, Field *comp_field,
+                          Item **const_item)
+{
+  DBUG_ASSERT(comp_item == NULL ^ comp_field == NULL);
+
+  Item *intermediate= NULL;
+  if (const_item == NULL)
+    const_item= &intermediate;
+
   if (cond->type() == Item::COND_ITEM)
   {
     bool and_level= (((Item_cond*) cond)->functype()
@@ -9542,7 +9624,8 @@ const_expression_in_where(COND *cond, It
     Item *item;
     while ((item=li++))
     {
-      bool res=const_expression_in_where(item, comp_item, const_item);
+      bool res=const_expression_in_where(item, comp_item, comp_field,
+                                         const_item);
       if (res)					// Is a const value
       {
 	if (and_level)
@@ -9554,14 +9637,14 @@ const_expression_in_where(COND *cond, It
     return and_level ? 0 : 1;
   }
   else if (cond->eq_cmp_result() != Item::COND_OK)
-  {						// boolan compare function
+  {						// boolean compare function
     Item_func* func= (Item_func*) cond;
     if (func->functype() != Item_func::EQUAL_FUNC &&
 	func->functype() != Item_func::EQ_FUNC)
       return 0;
     Item *left_item=	((Item_func*) cond)->arguments()[0];
     Item *right_item= ((Item_func*) cond)->arguments()[1];
-    if (left_item->eq(comp_item,1))
+    if (equal(left_item, comp_item, comp_field))
     {
       if (test_if_equality_guarantees_uniqueness (left_item, right_item))
       {
@@ -9571,7 +9654,7 @@ const_expression_in_where(COND *cond, It
 	return 1;
       }
     }
-    else if (right_item->eq(comp_item,1))
+    else if (equal(right_item, comp_item, comp_field))
     {
       if (test_if_equality_guarantees_uniqueness (right_item, left_item))
       {
@@ -9585,6 +9668,7 @@ const_expression_in_where(COND *cond, It
   return 0;
 }
 
+
 /****************************************************************************
   Create internal temporary table
 ****************************************************************************/
@@ -13038,7 +13122,8 @@ part_of_refkey(TABLE *table,Field *field
   @param order                 Sort order
   @param table                 Table to sort
   @param idx                   Index to check
-  @param used_key_parts        Return value for used key parts.
+  @param used_key_parts [out]  NULL by default, otherwise return value for
+                               used key parts.
 
 
   @note
@@ -13056,14 +13141,15 @@ part_of_refkey(TABLE *table,Field *field
     -1   Reverse key can be used
 */
 
-static int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
-				uint *used_key_parts)
+int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
+                         uint *used_key_parts)
 {
   KEY_PART_INFO *key_part,*key_part_end;
   key_part=table->key_info[idx].key_part;
   key_part_end=key_part+table->key_info[idx].key_parts;
   key_part_map const_key_parts=table->const_key_parts[idx];
   int reverse=0;
+  uint key_parts;
   my_bool on_pk_suffix= FALSE;
   DBUG_ENTER("test_if_order_by_key");
 
@@ -13104,8 +13190,9 @@ static int test_if_order_by_key(ORDER *o
         */
         if (key_part == key_part_end && reverse == 0)
         {
-          *used_key_parts= 0;
-          DBUG_RETURN(1);
+          key_parts= 0;
+          reverse= 1;
+          goto ok;
         }
       }
       else
@@ -13128,7 +13215,7 @@ static int test_if_order_by_key(ORDER *o
     uint used_key_parts_secondary= table->key_info[idx].key_parts;
     uint used_key_parts_pk=
       (uint) (key_part - table->key_info[table->s->primary_key].key_part);
-    *used_key_parts= used_key_parts_pk + used_key_parts_secondary;
+    key_parts= used_key_parts_pk + used_key_parts_secondary;
 
     if (reverse == -1 &&
         (!(table->file->index_flags(idx, used_key_parts_secondary - 1, 1) &
@@ -13139,11 +13226,14 @@ static int test_if_order_by_key(ORDER *o
   }
   else
   {
-    *used_key_parts= (uint) (key_part - table->key_info[idx].key_part);
+    key_parts= (uint) (key_part - table->key_info[idx].key_part);
     if (reverse == -1 && 
-        !(table->file->index_flags(idx, *used_key_parts-1, 1) & HA_READ_PREV))
+        !(table->file->index_flags(idx, key_parts-1, 1) & HA_READ_PREV))
       reverse= 0;                               // Index can't be used
   }
+ok:
+  if (used_key_parts != NULL)
+    *used_key_parts= key_parts;
   DBUG_RETURN(reverse);
 }
 
@@ -13237,7 +13327,6 @@ test_if_subkey(ORDER *order, TABLE *tabl
   uint nr;
   uint min_length= (uint) ~0;
   uint best= MAX_KEY;
-  uint not_used;
   KEY_PART_INFO *ref_key_part= table->key_info[ref].key_part;
   KEY_PART_INFO *ref_key_part_end= ref_key_part + ref_key_parts;
 
@@ -13248,7 +13337,7 @@ test_if_subkey(ORDER *order, TABLE *tabl
 	table->key_info[nr].key_parts >= ref_key_parts &&
 	is_subkey(table->key_info[nr].key_part, ref_key_part,
 		  ref_key_part_end) &&
-	test_if_order_by_key(order, table, nr, &not_used))
+	test_if_order_by_key(order, table, nr))
     {
       min_length= table->key_info[nr].key_length;
       best= nr;
@@ -13540,183 +13629,16 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
       goto check_reverse_order;
   }
   {
-    /*
-      Check whether there is an index compatible with the given order
-      usage of which is cheaper than usage of the ref_key index (ref_key>=0)
-      or a table scan.
-      It may be the case if ORDER/GROUP BY is used with LIMIT.
-    */
-    uint nr;
-    key_map keys;
     uint best_key_parts= 0;
     int best_key_direction= 0;
-    ha_rows best_records= 0;
-    double read_time;
     int best_key= -1;
-    bool is_best_covering= FALSE;
-    double fanout= 1;
     JOIN *join= tab->join;
-    uint tablenr= tab - join->join_tab;
     ha_rows table_records= table->file->stats.records;
-    bool group= join->group && order == join->group_list;
-    ha_rows ref_key_quick_rows= HA_POS_ERROR;
-
-    /*
-      If not used with LIMIT, only use keys if the whole query can be
-      resolved with a key;  This is because filesort() is usually faster than
-      retrieving all rows through an index.
-    */
-    if (select_limit >= table_records)
-    {
-      keys= *table->file->keys_to_use_for_scanning();
-      keys.merge(table->covering_keys);
-
-      /*
-	We are adding here also the index specified in FORCE INDEX clause, 
-	if any.
-        This is to allow users to use index in ORDER BY.
-      */
-      if (table->force_index) 
-	keys.merge(group ? table->keys_in_use_for_group_by :
-                           table->keys_in_use_for_order_by);
-      keys.intersect(usable_keys);
-    }
-    else
-      keys= usable_keys;
 
-    if (ref_key >= 0 && table->covering_keys.is_set(ref_key))
-      ref_key_quick_rows= table->quick_rows[ref_key];
-
-    read_time= join->best_positions[tablenr].read_time;
-    for (uint i= tablenr+1; i < join->tables; i++)
-      fanout*= join->best_positions[i].records_read; // fanout is always >= 1
-
-    for (nr=0; nr < table->s->keys ; nr++)
-    {
-      int direction;
-
-      if (keys.is_set(nr) &&
-          (direction= test_if_order_by_key(order, table, nr, &used_key_parts)))
-      {
-        /*
-          At this point we are sure that ref_key is a non-ordering
-          key (where "ordering key" is a key that will return rows
-          in the order required by ORDER BY).
-        */
-        DBUG_ASSERT (ref_key != (int) nr);
-
-        bool is_covering= table->covering_keys.is_set(nr) ||
-                          (nr == table->s->primary_key &&
-                          table->file->primary_key_is_clustered());
-	
-        /* 
-          Don't use an index scan with ORDER BY without limit.
-          For GROUP BY without limit always use index scan
-          if there is a suitable index. 
-          Why we hold to this asymmetry hardly can be explained
-          rationally. It's easy to demonstrate that using
-          temporary table + filesort could be cheaper for grouping
-          queries too.
-	*/ 
-        if (is_covering ||
-            select_limit != HA_POS_ERROR || 
-            (ref_key < 0 && (group || table->force_index)))
-        { 
-          double rec_per_key;
-          double index_scan_time;
-          KEY *keyinfo= tab->table->key_info+nr;
-          if (select_limit == HA_POS_ERROR)
-            select_limit= table_records;
-          if (group)
-          {
-            /* 
-              Used_key_parts can be larger than keyinfo->key_parts
-              when using a secondary index clustered with a primary 
-              key (e.g. as in Innodb). 
-              See Bug #28591 for details.
-            */  
-            rec_per_key= used_key_parts &&
-                         used_key_parts <= keyinfo->key_parts ?
-                         keyinfo->rec_per_key[used_key_parts-1] : 1;
-            set_if_bigger(rec_per_key, 1);
-            /*
-              With a grouping query each group containing on average
-              rec_per_key records produces only one row that will
-              be included into the result set.
-	    */  
-            if (select_limit > table_records/rec_per_key)
-                select_limit= table_records;
-            else
-              select_limit= (ha_rows) (select_limit*rec_per_key);
-          }
-          /* 
-            If tab=tk is not the last joined table tn then to get first
-            L records from the result set we can expect to retrieve
-            only L/fanout(tk,tn) where fanout(tk,tn) says how many
-            rows in the record set on average will match each row tk.
-            Usually our estimates for fanouts are too pessimistic.
-            So the estimate for L/fanout(tk,tn) will be too optimistic
-            and as result we'll choose an index scan when using ref/range
-            access + filesort will be cheaper.
-	  */
-          select_limit= (ha_rows) (select_limit < fanout ?
-                                   1 : select_limit/fanout);
-          /*
-            We assume that each of the tested indexes is not correlated
-            with ref_key. Thus, to select first N records we have to scan
-            N/selectivity(ref_key) index entries. 
-            selectivity(ref_key) = #scanned_records/#table_records =
-            table->quick_condition_rows/table_records.
-            In any case we can't select more than #table_records.
-            N/(table->quick_condition_rows/table_records) > table_records 
-            <=> N > table->quick_condition_rows.
-          */ 
-          if (select_limit > table->quick_condition_rows)
-            select_limit= table_records;
-          else
-            select_limit= (ha_rows) (select_limit *
-                                     (double) table_records /
-                                      table->quick_condition_rows);
-          rec_per_key= keyinfo->rec_per_key[keyinfo->key_parts-1];
-          set_if_bigger(rec_per_key, 1);
-          /*
-            Here we take into account the fact that rows are
-            accessed in sequences rec_per_key records in each.
-            Rows in such a sequence are supposed to be ordered
-            by rowid/primary key. When reading the data
-            in a sequence we'll touch not more pages than the
-            table file contains.
-            TODO. Use the formula for a disk sweep sequential access
-            to calculate the cost of accessing data rows for one 
-            index entry.
-	  */
-          index_scan_time= select_limit/rec_per_key *
-	                   min(rec_per_key, table->file->scan_time());
-          if ((ref_key < 0 && is_covering) || 
-              (ref_key < 0 && (group || table->force_index)) ||
-              index_scan_time < read_time)
-          {
-            ha_rows quick_records= table_records;
-            if ((is_best_covering && !is_covering) ||
-                (is_covering && ref_key_quick_rows < select_limit))
-              continue;
-            if (table->quick_keys.is_set(nr))
-              quick_records= table->quick_rows[nr];
-            if (best_key < 0 ||
-                (select_limit <= min(quick_records,best_records) ?
-                 keyinfo->key_parts < best_key_parts :
-                 quick_records < best_records))
-            {
-              best_key= nr;
-              best_key_parts= keyinfo->key_parts;
-              best_records= quick_records;
-              is_best_covering= is_covering;
-              best_key_direction= direction; 
-            }
-          }   
-	}      
-      }
-    }
+    test_if_cheaper_ordering(tab, order, table, usable_keys,
+                             ref_key, select_limit,
+                             &best_key, &best_key_direction,
+                             &select_limit, &best_key_parts);
 
     /*
       filesort() and join cache are usually faster than reading in 
@@ -17374,5 +17296,354 @@ void JOIN::cache_const_exprs()
 
 
 /**
+  Find a cheaper access key than a given @a key
+
+  @param          tab                 NULL or JOIN_TAB of the accessed table
+  @param          order               Linked list of ORDER BY arguments
+  @param          table               Table if tab == NULL or tab->table
+  @param          usable_keys         Key map to find a cheaper key in
+  @param          ref_key             
+                * 0 <= key < MAX_KEY   - key number (hint) to start the search
+                * -1                   - no key number provided
+  @param          select_limit        LIMIT value
+  @param [out]    new_key             Key number if success, otherwise undefined
+  @param [out]    new_key_direction   Return -1 (reverse) or +1 if success,
+                                      otherwise undefined
+  @param [out]    new_select_limit    Return adjusted LIMIT
+  @param [out]    new_used_key_parts  NULL by default, otherwise return number
+                                      of new_key prefix columns if success
+                                      or undefined if the function fails
+
+  @note
+    This function takes into account table->quick_condition_rows statistic
+    (that is calculated by the make_join_statistics function).
+    However, single table procedures such as mysql_update() and mysql_delete()
+    never call make_join_statistics, so they have to update it manually
+    (@see get_index_for_order()).
+*/
+
+static bool
+test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
+                         key_map usable_keys,  int ref_key,
+                         ha_rows select_limit,
+                         int *new_key, int *new_key_direction,
+                         ha_rows *new_select_limit, uint *new_used_key_parts)
+{
+  DBUG_ENTER("test_if_cheaper_ordering");
+  /*
+    Check whether there is an index compatible with the given order
+    usage of which is cheaper than usage of the ref_key index (ref_key>=0)
+    or a table scan.
+    It may be the case if ORDER/GROUP BY is used with LIMIT.
+  */
+  ha_rows best_select_limit= HA_POS_ERROR;
+  JOIN *join= tab ? tab->join : NULL;
+  uint nr;
+  key_map keys;
+  uint best_key_parts= 0;
+  int best_key_direction= 0;
+  ha_rows best_records= 0;
+  double read_time;
+  int best_key= -1;
+  bool is_best_covering= FALSE;
+  double fanout= 1;
+  ha_rows table_records= table->file->stats.records;
+  bool group= join && join->group && order == join->group_list;
+  ha_rows ref_key_quick_rows= HA_POS_ERROR;
+
+  /*
+    If not used with LIMIT, only use keys if the whole query can be
+    resolved with a key;  This is because filesort() is usually faster than
+    retrieving all rows through an index.
+  */
+  if (select_limit >= table_records)
+  {
+    keys= *table->file->keys_to_use_for_scanning();
+    keys.merge(table->covering_keys);
+
+    /*
+      We are adding here also the index specified in FORCE INDEX clause, 
+      if any.
+      This is to allow users to use index in ORDER BY.
+    */
+    if (table->force_index) 
+      keys.merge(group ? table->keys_in_use_for_group_by :
+                         table->keys_in_use_for_order_by);
+    keys.intersect(usable_keys);
+  }
+  else
+    keys= usable_keys;
+
+  if (ref_key >= 0 && table->covering_keys.is_set(ref_key))
+    ref_key_quick_rows= table->quick_rows[ref_key];
+
+  if (join)
+  {
+    uint tablenr= tab - join->join_tab;
+    read_time= join->best_positions[tablenr].read_time;
+    for (uint i= tablenr+1; i < join->tables; i++)
+      fanout*= join->best_positions[i].records_read; // fanout is always >= 1
+  }
+  else
+    read_time= table->file->scan_time();
+
+  for (nr=0; nr < table->s->keys ; nr++)
+  {
+    int direction;
+    uint used_key_parts;
+
+    if (keys.is_set(nr) &&
+        (direction= test_if_order_by_key(order, table, nr, &used_key_parts)))
+    {
+      /*
+        At this point we are sure that ref_key is a non-ordering
+        key (where "ordering key" is a key that will return rows
+        in the order required by ORDER BY).
+      */
+      DBUG_ASSERT (ref_key != (int) nr);
+
+      bool is_covering= table->covering_keys.is_set(nr) ||
+                        (nr == table->s->primary_key &&
+                        table->file->primary_key_is_clustered());
+      
+      /* 
+        Don't use an index scan with ORDER BY without limit.
+        For GROUP BY without limit always use index scan
+        if there is a suitable index. 
+        Why we hold to this asymmetry hardly can be explained
+        rationally. It's easy to demonstrate that using
+        temporary table + filesort could be cheaper for grouping
+        queries too.
+      */ 
+      if (is_covering ||
+          select_limit != HA_POS_ERROR || 
+          (ref_key < 0 && (group || table->force_index)))
+      { 
+        double rec_per_key;
+        double index_scan_time;
+        KEY *keyinfo= table->key_info+nr;
+        if (select_limit == HA_POS_ERROR)
+          select_limit= table_records;
+        if (group)
+        {
+          /* 
+            Used_key_parts can be larger than keyinfo->key_parts
+            when using a secondary index clustered with a primary 
+            key (e.g. as in Innodb). 
+            See Bug #28591 for details.
+          */  
+          rec_per_key= used_key_parts &&
+                       used_key_parts <= keyinfo->key_parts ?
+                       keyinfo->rec_per_key[used_key_parts-1] : 1;
+          set_if_bigger(rec_per_key, 1);
+          /*
+            With a grouping query each group containing on average
+            rec_per_key records produces only one row that will
+            be included into the result set.
+          */  
+          if (select_limit > table_records/rec_per_key)
+              select_limit= table_records;
+          else
+            select_limit= (ha_rows) (select_limit*rec_per_key);
+        }
+        /* 
+          If tab=tk is not the last joined table tn then to get first
+          L records from the result set we can expect to retrieve
+          only L/fanout(tk,tn) where fanout(tk,tn) says how many
+          rows in the record set on average will match each row tk.
+          Usually our estimates for fanouts are too pessimistic.
+          So the estimate for L/fanout(tk,tn) will be too optimistic
+          and as result we'll choose an index scan when using ref/range
+          access + filesort will be cheaper.
+        */
+        select_limit= (ha_rows) (select_limit < fanout ?
+                                 1 : select_limit/fanout);
+        /*
+          We assume that each of the tested indexes is not correlated
+          with ref_key. Thus, to select first N records we have to scan
+          N/selectivity(ref_key) index entries. 
+          selectivity(ref_key) = #scanned_records/#table_records =
+          table->quick_condition_rows/table_records.
+          In any case we can't select more than #table_records.
+          N/(table->quick_condition_rows/table_records) > table_records 
+          <=> N > table->quick_condition_rows.
+        */ 
+        if (select_limit > table->quick_condition_rows)
+          select_limit= table_records;
+        else
+          select_limit= (ha_rows) (select_limit *
+                                   (double) table_records /
+                                    table->quick_condition_rows);
+        rec_per_key= keyinfo->rec_per_key[keyinfo->key_parts-1];
+        set_if_bigger(rec_per_key, 1);
+        /*
+          Here we take into account the fact that rows are
+          accessed in sequences rec_per_key records in each.
+          Rows in such a sequence are supposed to be ordered
+          by rowid/primary key. When reading the data
+          in a sequence we'll touch not more pages than the
+          table file contains.
+          TODO. Use the formula for a disk sweep sequential access
+          to calculate the cost of accessing data rows for one 
+          index entry.
+        */
+        index_scan_time= select_limit/rec_per_key *
+                         min(rec_per_key, table->file->scan_time());
+        if ((ref_key < 0 && is_covering) || 
+            (ref_key < 0 && (group || table->force_index)) ||
+            index_scan_time < read_time)
+        {
+          ha_rows quick_records= table_records;
+          if ((is_best_covering && !is_covering) ||
+              (is_covering && ref_key_quick_rows < select_limit))
+            continue;
+          if (table->quick_keys.is_set(nr))
+            quick_records= table->quick_rows[nr];
+          if (best_key < 0 ||
+              (select_limit <= min(quick_records,best_records) ?
+               keyinfo->key_parts < best_key_parts :
+               quick_records < best_records))
+          {
+            best_key= nr;
+            best_key_parts= keyinfo->key_parts;
+            best_records= quick_records;
+            is_best_covering= is_covering;
+            best_key_direction= direction; 
+            best_select_limit= select_limit;
+          }
+        }   
+      }      
+    }
+  }
+
+  if (best_key < 0 || best_key == ref_key)
+    DBUG_RETURN(FALSE);
+  
+  *new_key= best_key;
+  *new_key_direction= best_key_direction;
+  *new_select_limit= best_select_limit;
+  if (new_used_key_parts != NULL)
+    *new_used_key_parts= best_key_parts;
+
+  DBUG_RETURN(TRUE);
+}
+
+
+/**
+  Find a key to apply single table UPDATE/DELETE by a given ORDER
+
+  @param       order           Linked list of ORDER BY arguments
+  @param       table           Table to find a key
+  @param       select          Pointer to access/update select->quick (if any)
+  @param       limit           LIMIT clause parameter 
+  @param [out] need_sort       TRUE if filesort needed
+  @param [out] reverse
+    TRUE if the key is reversed again given ORDER (undefined if key == MAX_KEY)
+
+  @return
+    - MAX_KEY if no key found                        (need_sort == TRUE)
+    - MAX_KEY if quick select result order is OK     (need_sort == FALSE)
+    - key number (either index scan or quick select) (need_sort == FALSE)
+
+  @note
+    Side effects:
+    - may deallocate or deallocate and replace select->quick;
+    - may set table->quick_condition_rows and table->quick_rows[...]
+      to table->file->stats.records. 
+*/
+
+uint get_index_for_order(ORDER *order, TABLE *table, SQL_SELECT *select,
+                         ha_rows limit, bool *need_sort, bool *reverse)
+{
+  if (select && select->quick && select->quick->unique_key_range())
+  { // Single row select (always "ordered"): Ok to use with key field UPDATE
+    *need_sort= FALSE;
+    /*
+      Returning of MAX_KEY here prevents updating of used_key_is_modified
+      in mysql_update(). Use quick select "as is".
+    */
+    return MAX_KEY;
+  }
+
+  if (!order)
+  {
+    *need_sort= FALSE;
+    if (select && select->quick)
+      return select->quick->index; // index or MAX_KEY, use quick select as is
+    else
+      return table->file->key_used_on_scan; // MAX_KEY or index for some engines
+  }
+
+  if (!is_simple_order(order)) // just to cut further expensive checks
+  {
+    if (select)
+      select->set_quick(NULL);
+    *need_sort= TRUE;
+    return MAX_KEY;
+  }
+
+  if (select && select->quick)
+  {
+    if (select->quick->index == MAX_KEY)
+    {
+      *need_sort= TRUE;
+      select->set_quick(NULL);
+      return MAX_KEY;
+    }
+
+    switch (test_if_order_by_key(order, table, select->quick->index)) {
+    case 1: // desired order
+      *need_sort= FALSE;
+      return select->quick->index;
+    case 0: // unacceptable order
+      *need_sort= TRUE;
+      select->set_quick(NULL);
+      return MAX_KEY;
+    case -1: // desired order, but opposite direction
+      {
+        QUICK_SELECT_I *reverse_quick;
+        if ((reverse_quick= select->quick->make_reverse()))
+        {
+          select->set_quick(reverse_quick);
+          *need_sort= FALSE;
+          return select->quick->index;
+        }
+        else
+        {
+          select->set_quick(NULL);
+          *need_sort= TRUE;
+          return MAX_KEY;
+        }
+      }
+    }
+    DBUG_ASSERT(0);
+  }
+  else if (limit != HA_POS_ERROR)
+  { // check if some index scan & LIMIT is more efficient than filesort
+    
+    /*
+      Update quick_condition_rows since single table UPDATE/DELETE procedures
+      don't call make_join_statistics() and leave this variable uninitialized.
+    */
+    table->quick_condition_rows= table->file->stats.records;
+    
+    int key, direction;
+    if (test_if_cheaper_ordering(NULL, order, table,
+                                 table->keys_in_use_for_order_by, -1,
+                                 limit,
+                                 &key, &direction, &limit) &&
+        !is_key_used(table, key, table->write_set))
+    {
+      *need_sort= FALSE;
+      *reverse= (direction < 0);
+      return key;
+    }
+  }
+  *need_sort= TRUE;
+  return MAX_KEY;
+}
+
+
+/**
   @} (end of group Query_Optimizer)
 */

=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h	2010-04-01 19:34:09 +0000
+++ b/sql/sql_select.h	2010-04-21 11:42:35 +0000
@@ -848,4 +848,14 @@ inline bool optimizer_flag(THD *thd, uin
   return (thd->variables.optimizer_switch & flag);
 }
 
+int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
+                         uint *used_key_parts= NULL);
+uint get_index_for_order(ORDER *order, TABLE *table, SQL_SELECT *select,
+                         ha_rows limit, bool *need_sort, bool *reverse);
+ORDER *simple_remove_const(ORDER *order, COND *where);
+bool const_expression_in_where(COND *cond, Item *comp_item,
+                               Field *comp_field= NULL,
+                               Item **const_item= NULL);
+
+
 #endif /* SQL_SELECT_INCLUDED */

=== modified file 'sql/sql_update.cc'
--- a/sql/sql_update.cc	2010-04-07 12:02:19 +0000
+++ b/sql/sql_update.cc	2010-04-21 11:42:35 +0000
@@ -203,12 +203,13 @@ int mysql_update(THD *thd,
 {
   bool		using_limit= limit != HA_POS_ERROR;
   bool		safe_update= test(thd->variables.option_bits & OPTION_SAFE_UPDATES);
-  bool		used_key_is_modified, transactional_table, will_batch;
+  bool          used_key_is_modified= FALSE, transactional_table, will_batch;
   bool		can_compare_record;
   int           res;
   int		error, loc_error;
-  uint		used_index= MAX_KEY, dup_key_found;
+  uint          used_index, dup_key_found;
   bool          need_sort= TRUE;
+  bool          reverse= FALSE;
 #ifndef NO_EMBEDDED_ACCESS_CHECKS
   uint		want_privilege;
 #endif
@@ -359,11 +360,7 @@ int mysql_update(THD *thd,
     my_ok(thd);				// No matching records
     DBUG_RETURN(0);
   }
-  if (!select && limit != HA_POS_ERROR)
-  {
-    if ((used_index= get_index_for_order(table, order, limit)) != MAX_KEY)
-      need_sort= FALSE;
-  }
+
   /* If running in safe sql mode, don't allow updates without keys */
   if (table->quick_keys.is_clear_all())
   {
@@ -379,23 +376,19 @@ int mysql_update(THD *thd,
 
   table->mark_columns_needed_for_update();
 
-  /* Check if we are modifying a key that we are used to search with */
-  
-  if (select && select->quick)
-  {
-    used_index= select->quick->index;
-    used_key_is_modified= (!select->quick->unique_key_range() &&
-                          select->quick->is_keys_used(table->write_set));
+  table->update_const_key_parts(conds);
+  order= simple_remove_const(order, conds);
+        
+  used_index= get_index_for_order(order, table, select, limit,
+                                  &need_sort, &reverse);
+  if (need_sort)
+  { // Assign table scan index to check below for modified key fields:
+    used_index= table->file->key_used_on_scan;
+  }
+  if (used_index != MAX_KEY)
+  { // Check if we are modifying a key that we are used to search with:
+    used_key_is_modified= is_key_used(table, used_index, table->write_set);
   }
-  else
-  {
-    used_key_is_modified= 0;
-    if (used_index == MAX_KEY)                  // no index for sort order
-      used_index= table->file->key_used_on_scan;
-    if (used_index != MAX_KEY)
-      used_key_is_modified= is_key_used(table, used_index, table->write_set);
-  }
-
 
 #ifdef WITH_PARTITION_STORAGE_ENGINE
   if (used_key_is_modified || order ||
@@ -415,7 +408,7 @@ int mysql_update(THD *thd,
       table->use_all_columns();
     }
 
-    /* note: We avoid sorting avoid if we sort on the used index */
+    /* note: We avoid sorting if we sort on the used index */
     if (order && (need_sort || used_key_is_modified))
     {
       /*
@@ -476,7 +469,7 @@ int mysql_update(THD *thd,
       if (used_index == MAX_KEY || (select && select->quick))
         init_read_record(&info, thd, table, select, 0, 1, FALSE);
       else
-        init_read_record_idx(&info, thd, table, 1, used_index);
+        init_read_record_idx(&info, thd, table, 1, used_index, reverse);
 
       thd_proc_info(thd, "Searching rows for update");
       ha_rows tmp_limit= limit;

=== modified file 'sql/table.cc'
--- a/sql/table.cc	2010-04-07 11:58:40 +0000
+++ b/sql/table.cc	2010-04-21 11:42:35 +0000
@@ -33,6 +33,7 @@
 #include "sql_base.h"            // release_table_share
 #include <m_ctype.h>
 #include "my_md5.h"
+#include "sql_select.h"
 
 /* INFORMATION_SCHEMA name */
 LEX_STRING INFORMATION_SCHEMA_NAME= {C_STRING_WITH_LEN("information_schema")};
@@ -4904,6 +4905,61 @@ void init_mdl_requests(TABLE_LIST *table
 }
 
 
+/**
+  Update TABLE::const_key_parts for single table UPDATE/DELETE query
+
+  @param conds               WHERE clause expression
+
+  @retval TRUE   error (OOM)
+  @retval FALSE  success
+
+  @note
+    Set const_key_parts bits if key fields are equal to constants in
+    the WHERE expression.
+*/
+
+bool TABLE::update_const_key_parts(COND *conds)
+{
+  bzero((char*) const_key_parts, sizeof(key_part_map) * s->keys);
+
+  if (conds == NULL)
+    return FALSE;
+
+  for (uint index= 0; index < s->keys; index++)
+  {
+    KEY_PART_INFO *keyinfo= key_info[index].key_part;
+    KEY_PART_INFO *keyinfo_end= keyinfo + key_info[index].key_parts;
+
+    for (key_part_map part_map= (key_part_map)1; 
+        keyinfo < keyinfo_end;
+        keyinfo++, part_map<<= 1)
+    {
+      if (const_expression_in_where(conds, NULL, keyinfo->field))
+        const_key_parts[index]|= part_map;
+    }
+  }
+  return FALSE;
+}
+
+/**
+  Test if the order list consists of simple field expressions
+
+  @param order                Linked list of ORDER BY arguments
+
+  @return TRUE if @a order is empty or consist of simple field expressions
+*/
+
+bool is_simple_order(ORDER *order)
+{
+  for (ORDER *ord= order; ord; ord= ord->next)
+  {
+    if (ord->item[0]->real_item()->type() != Item::FIELD_ITEM)
+      return FALSE;
+  }
+  return TRUE;
+}
+
+
 /*****************************************************************************
 ** Instansiate templates
 *****************************************************************************/

=== modified file 'sql/table.h'
--- a/sql/table.h	2010-04-12 13:18:07 +0000
+++ b/sql/table.h	2010-04-21 11:42:35 +0000
@@ -1098,6 +1098,8 @@ public:
       file->extra(HA_EXTRA_NO_KEYREAD);
     }
   }
+
+  bool update_const_key_parts(COND *conds);
 };
 
 
@@ -2068,6 +2070,8 @@ inline void mark_as_null_row(TABLE *tabl
   bfill(table->null_flags,table->s->null_bytes,255);
 }
 
+bool is_simple_order(ORDER *order);
+
 #endif /* MYSQL_CLIENT */
 
 #endif /* TABLE_INCLUDED */


Attachment: [text/bzr-bundle] bzr/gshchepa@mysql.com-20100421114235-sob6j13n5rff3ncj.bundle
Thread
bzr commit into mysql-next-mr branch (gshchepa:3140) Bug#30584Bug#36569Gleb Shchepa21 Apr