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

 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.

    added:
      mysql-test/r/single_delete_update.result
      mysql-test/t/single_delete_update.test
    modified:
      sql/opt_range.cc
      sql/opt_range.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-03-11 15:50:27 +0000
@@ -0,0 +1,253 @@
+DROP TABLE IF EXISTS t1, t2;
+CREATE TABLE t1 (i INT);
+INSERT INTO t1 VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),
+(11),(12),(13),(14),(15),(16);
+CREATE TABLE t2(a INT, i INT PRIMARY KEY);
+INSERT INTO t2 (i) SELECT i FROM t1;
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i LIMIT 5;
+a	i
+NULL	1
+NULL	2
+NULL	3
+NULL	4
+NULL	5
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+FLUSH STATUS;
+UPDATE t2 SET a = 10 WHERE i > 0 AND i <= 8 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
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i;
+a	i
+10	1
+10	2
+10	3
+10	4
+10	5
+NULL	6
+NULL	7
+NULL	8
+FLUSH STATUS;
+DELETE FROM t2 WHERE i > 0 AND i <= 8 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
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i;
+a	i
+NULL	6
+NULL	7
+NULL	8
+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 > 0 AND i <= 8 ORDER BY i LIMIT 5;
+a	i
+NULL	1
+NULL	2
+NULL	3
+NULL	4
+NULL	5
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	5
+Sort_scan	1
+FLUSH STATUS;
+UPDATE t2 SET a = 10 WHERE i > 0 AND i <= 8 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
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i;
+a	i
+10	1
+10	2
+10	3
+10	4
+10	5
+NULL	6
+NULL	7
+NULL	8
+FLUSH STATUS;
+DELETE FROM t2 WHERE i > 0 AND i <= 8 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
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i;
+a	i
+NULL	6
+NULL	7
+NULL	8
+DROP TABLE t2;
+# constant inside ORDER BY list, 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
+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
+## should be 5 (previous LIMIT)
+SELECT COUNT(*) FROM t2 WHERE b = 10 AND d = 10 ORDER BY a, c;
+COUNT(*)
+5
+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
+## 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
+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
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+a	b	c	d
+10	10	10	10
+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
+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
+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
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+a	b	c	d
+10	10	10	10
+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
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+a	b	c	d
+DROP TABLE t2;
+# quick select is QUICK_INDEX_MERGE_SELECT, 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 < 3 or key2 < 4 ORDER BY key1;
+i	key1	key2
+NULL	1	1
+NULL	2	2
+NULL	3	3
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	3
+Sort_scan	1
+FLUSH STATUS;
+UPDATE t2 SET i = 123 WHERE key1 < 3 or key2 < 4 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	3
+Sort_scan	1
+SELECT * FROM t2 WHERE key1 < 3 or key2 < 4 ORDER BY key1;
+i	key1	key2
+123	1	1
+123	2	2
+123	3	3
+FLUSH STATUS;
+DELETE FROM t2 WHERE key1 < 3 or key2 < 4 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	3
+Sort_scan	1
+SELECT * FROM t2 WHERE key1 < 3 or key2 < 4 ORDER BY key1;
+i	key1	key2
+DROP TABLE t1, t2;

=== 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-03-11 15:50:27 +0000
@@ -0,0 +1,154 @@
+#
+# Single table specific update/delete tests (mysql_update and mysql_delete)
+#
+
+--disable_warnings
+DROP TABLE IF EXISTS t1, t2;
+--enable_warnings
+
+#
+# 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
+#
+
+CREATE TABLE t1 (i INT);
+INSERT INTO t1 VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),
+                      (11),(12),(13),(14),(15),(16);
+
+CREATE TABLE t2(a INT, i INT PRIMARY KEY);
+INSERT INTO t2 (i) SELECT i FROM t1;
+
+FLUSH STATUS;
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+
+FLUSH STATUS;
+UPDATE t2 SET a = 10 WHERE i > 0 AND i <= 8 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i;
+
+DROP TABLE t2;
+
+--echo # 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 > 0 AND i <= 8 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+
+FLUSH STATUS;
+UPDATE t2 SET a = 10 WHERE i > 0 AND i <= 8 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE i > 0 AND i <= 8 ORDER BY i;
+
+DROP TABLE t2;
+
+--echo # constant inside ORDER BY list, 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;
+# After the 1ts fix for bug #28404 (5.1+) the optimizer
+# may optimize queries like below to use filesort on small tables
+# even if there is a small LIMIT (probably a minor regression).
+# Make the table large enough to ignore that and don't use
+# filesort in the first sample SELECT.
+
+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%';
+
+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%';
+--echo ## should be 5 (previous LIMIT)
+SELECT COUNT(*) FROM t2 WHERE b = 10 AND d = 10 ORDER BY a, c;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+--echo ## should be 5 (previous LIMIT)
+eval SELECT $cnt - COUNT(*) FROM t2 WHERE b = 10;
+
+DROP TABLE t2;
+
+--echo # 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;
+SHOW SESSION STATUS LIKE 'Sort%';
+
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+
+DROP TABLE t2;
+
+--echo # 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;
+SHOW SESSION STATUS LIKE 'Sort%';
+
+FLUSH STATUS;
+UPDATE t2 SET d = 10 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE b = 10 ORDER BY a, c LIMIT 5;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+
+DROP TABLE t2;
+
+--echo # quick select is QUICK_INDEX_MERGE_SELECT, 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 < 3 or key2 < 4 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+
+FLUSH STATUS;
+UPDATE t2 SET i = 123 WHERE key1 < 3 or key2 < 4 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE key1 < 3 or key2 < 4 ORDER BY key1;
+
+FLUSH STATUS;
+DELETE FROM t2 WHERE key1 < 3 or key2 < 4 ORDER BY key1;
+SHOW SESSION STATUS LIKE 'Sort%';
+SELECT * FROM t2 WHERE key1 < 3 or key2 < 4 ORDER BY key1;
+
+DROP TABLE t1, t2;

=== modified file 'sql/opt_range.cc'
--- a/sql/opt_range.cc	2010-03-01 09:45:36 +0000
+++ b/sql/opt_range.cc	2010-03-11 15:50:27 +0000
@@ -11778,7 +11778,46 @@ void QUICK_GROUP_MIN_MAX_SELECT::dbug_du
 }
 
 
-#endif /* NOT_USED */
+#endif /* !DBUG_OFF */
+
+
+/*
+  Test if sorting by ORDER BY order is not necessary
+
+  SYNOPSIS
+    QUICK_SELECT_I::is_ordered_by()
+    order       ORDER BY list
+
+  DESCRIPTION
+    Test if quick select result sorting order is equal to ORDER BY ordering,
+    so additional filesort is not necessary and may be skipped.
+
+  NOTE
+    This function is for use in single-table mysql_update and
+    mysql_delete function.
+
+  RETURN
+    TRUE is ORDER BY may be ignored.
+*/
+
+bool QUICK_SELECT_I::is_ordered_by(ORDER *order)
+{
+  if (index == MAX_KEY ||
+      !(head->file->index_flags(index, 0, 1) & HA_READ_ORDER))
+    return FALSE;
+
+  if (!order)
+    return TRUE;
+
+  uint dummy;
+  switch (test_if_order_by_key(order, head, index, &dummy)) {
+  case -1: return reverse_sorted();
+  case  1: return !reverse_sorted();
+  }
+
+  return FALSE;
+}
+
 
 /*****************************************************************************
 ** Instantiate templates 

=== modified file 'sql/opt_range.h'
--- a/sql/opt_range.h	2009-11-24 13:54:59 +0000
+++ b/sql/opt_range.h	2010-03-11 15:50:27 +0000
@@ -259,6 +259,8 @@ public:
   */
   virtual void dbug_dump(int indent, bool verbose)= 0;
 #endif
+
+  bool is_ordered_by(ORDER *order);
 };
 
 

=== modified file 'sql/sql_delete.cc'
--- a/sql/sql_delete.cc	2010-02-24 17:04:00 +0000
+++ b/sql/sql_delete.cc	2010-03-11 15:50:27 +0000
@@ -34,7 +34,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;
@@ -47,6 +47,9 @@ bool mysql_delete(THD *thd, TABLE_LIST *
   bool          const_cond_result;
   ha_rows	deleted= 0;
   bool          triggers_applicable;
+  bool          need_sort= TRUE;
+  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;
@@ -72,7 +75,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;
@@ -82,9 +85,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);
@@ -221,21 +224,38 @@ bool mysql_delete(THD *thd, TABLE_LIST *
   if (options & OPTION_QUICK)
     (void) table->file->extra(HA_EXTRA_QUICK);
 
-  if (order && order->elements)
+  if (select && order)
+  {
+    table->update_const_key_parts(conds);
+    order= order->simple_remove_const(conds);
+    if (select->quick)
+    {
+      if (select->quick->is_ordered_by(order))
+      {
+        usable_index= select->quick->index;
+        need_sort= FALSE;
+      }
+    } else {
+      usable_index= table->simple_test_if_skip_sort_order(order, limit);
+      need_sort= (usable_index == MAX_KEY);
+    }
+  }
+
+  if (order && need_sort)
   {
     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);
+      usable_index= get_index_for_order(table, order, limit);
 
     if (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,
+      if (!(sortorder= make_unireg_sortorder(order,
                                              &length, NULL)) ||
 	  (table->sort.found_records = filesort(thd, table, sortorder, length,
                                                 select, HA_POS_ERROR, 1,
@@ -263,7 +283,7 @@ 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);

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2010-03-01 09:45:36 +0000
+++ b/sql/sql_select.cc	2010-03-11 15:50:27 +0000
@@ -118,7 +118,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,
@@ -7291,8 +7290,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_item_in_where(cond, order->item[0]))
 	{
 	  DBUG_PRINT("info",("removing: %s", order->item[0]->full_name()));
 	  continue;
@@ -9475,12 +9473,38 @@ 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.
+/*
+  Generic wrapper to pass Field* or Item* to const_expression_in_where().
 */
+class wrap_field_or_item {
+  Field *field;
+  Item  *item;
+public:
+  explicit wrap_field_or_item(Field *field_arg) : field(field_arg), item(NULL)
+  {}
+  explicit wrap_field_or_item(Item *item_arg) : field(NULL), item(item_arg)
+  {}
+  bool eq(Item *item_arg) const
+  {
+    return item ? item_arg->eq(item, 1)
+                : (item_arg->type() == Item::FIELD_ITEM &&
+                   ((Item_field *)item_arg)->field->eq(field));
+  }
+};
+
+
+/**
+  Test if a field or an item is a constant value in the WHERE clause expression
+
+  @param        cond            WHERE clause expression
+  @param        comp            Item or Field to find in WHERE expression
+  @param[out]   const_item      intermediate arg, set to Item pointer to NULL 
 
+  @return TRUE if the field is a constant value in WHERE
+*/
 static bool
-const_expression_in_where(COND *cond, Item *comp_item, Item **const_item)
+const_expression_in_where(COND *cond, const wrap_field_or_item &comp,
+                          Item **const_item)
 {
   if (cond->type() == Item::COND_ITEM)
   {
@@ -9490,7 +9514,7 @@ 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, const_item);
       if (res)					// Is a const value
       {
 	if (and_level)
@@ -9509,7 +9533,7 @@ const_expression_in_where(COND *cond, It
       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 (comp.eq(left_item))
     {
       if (test_if_equality_guarantees_uniqueness (left_item, right_item))
       {
@@ -9519,7 +9543,7 @@ const_expression_in_where(COND *cond, It
 	return 1;
       }
     }
-    else if (right_item->eq(comp_item,1))
+    else if (comp.eq(right_item))
     {
       if (test_if_equality_guarantees_uniqueness (right_item, left_item))
       {
@@ -9533,6 +9557,37 @@ const_expression_in_where(COND *cond, It
   return 0;
 }
 
+
+/**
+  Test if an item is a constant value in the WHERE clause expression
+
+  @param        where           WHERE clause expression
+  @param        item            Item to find in WHERE expression
+
+  @return TRUE if the item is a constant value in WHERE
+*/
+bool const_item_in_where(COND *where, Item *item)
+{
+  Item *dummy= NULL;
+  return const_expression_in_where(where, wrap_field_or_item(item), &dummy);
+}
+
+
+/**
+  Test if a field is a constant value in the WHERE clause expression
+
+  @param        where           WHERE clause expression
+  @param        field           Field to find in WHERE expression
+
+  @return TRUE if the field is a constant value in WHERE
+*/
+bool const_field_in_where(COND *where, Field *field)
+{
+  Item *dummy= NULL;
+  return const_expression_in_where(where, wrap_field_or_item(field), &dummy);
+}
+
+
 /****************************************************************************
   Create internal temporary table
 ****************************************************************************/
@@ -13004,8 +13059,8 @@ 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;
@@ -13347,24 +13402,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
   DBUG_ENTER("test_if_skip_sort_order");
   LINT_INIT(ref_key_parts);
 
-  /*
-    Keys disabled by ALTER TABLE ... DISABLE KEYS should have already
-    been taken into account.
-  */
-  usable_keys= *map;
-
-  for (ORDER *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)
-  {
-    Item *item= (*tmp_order->item)->real_item();
-    if (item->type() != Item::FIELD_ITEM)
-    {
-      usable_keys.clear_all();
-      DBUG_RETURN(0);
-    }
-    usable_keys.intersect(((Item_field*) item)->field->part_of_sortkey);
-    if (usable_keys.is_clear_all())
-      DBUG_RETURN(0);					// No usable keys
-  }
+  usable_keys= table->get_order_by_usable_keys(order, *map);
 
   ref_key= -1;
   /* Test if constant range in WHERE */

=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h	2010-03-01 09:45:36 +0000
+++ b/sql/sql_select.h	2010-03-11 15:50:27 +0000
@@ -804,4 +804,9 @@ 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);
+bool const_field_in_where(COND *where, Field *field);
+bool const_item_in_where(COND *where, Item *field);
+
 #endif /* SQL_SELECT_INCLUDED */

=== modified file 'sql/sql_update.cc'
--- a/sql/sql_update.cc	2010-02-24 13:52:27 +0000
+++ b/sql/sql_update.cc	2010-03-11 15:50:27 +0000
@@ -374,9 +374,30 @@ int mysql_update(THD *thd,
   
   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));
+    if (!used_key_is_modified)
+    {
+      table->update_const_key_parts(conds);
+      order= order->simple_remove_const(conds);
+      if (select->quick->is_ordered_by(order))
+      {
+        used_index= select->quick->index;
+        need_sort= FALSE;
+      }
+    }
+  }
+  else if (select && order)
+  {
+    used_key_is_modified= 0;
+    table->update_const_key_parts(conds);
+    order= order->simple_remove_const(conds);
+    used_index= table->simple_test_if_skip_sort_order(order, limit);
+    if (used_index != MAX_KEY)
+    {
+      if (!(used_key_is_modified= is_key_used(table, used_index, table->write_set)))
+        need_sort= FALSE;
+    }
   }
   else
   {

=== modified file 'sql/table.cc'
--- a/sql/table.cc	2010-02-24 13:52:27 +0000
+++ b/sql/table.cc	2010-03-11 15:50:27 +0000
@@ -20,6 +20,7 @@
 #include "sql_trigger.h"
 #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")};
@@ -4893,6 +4894,160 @@ void init_mdl_requests(TABLE_LIST *table
 }
 
 
+/*
+  Update TABLE::const_key_parts for single table UPDATE query
+
+  SYNOPSIS
+    TABLE::update_const_key_parts()
+    conds               WHERE clause expression
+
+  NOTE
+    This is a simplified version of make_join_statistics() -- unfortunately
+    that function is not suitable for single table UPDATE query preparation.
+    This function is for use in single-table mysql_update and mysql_delete
+    functions.
+*/
+
+void TABLE::update_const_key_parts(COND *conds)
+{
+  bzero((char*) const_key_parts, sizeof(key_part_map) * s->keys);
+
+  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;
+
+    const_key_parts[index]= (key_part_map)0;
+
+    for (key_part_map part_map= (key_part_map)1; 
+        keyinfo < keyinfo_end;
+        keyinfo++, part_map<<= 1)
+    {
+      if (const_field_in_where(conds, keyinfo->field))
+        const_key_parts[index]|= part_map;
+    }
+  }
+}
+
+
+/*
+  Calculate bitmap of table keys that ORDER BY can use for ordering
+
+  SYNOPSIS
+    TABLE::get_order_by_usable_keys()
+    order               ORDER BY list
+    map                 initial usable key map
+
+  RETURN
+    Bitmap of usable keys
+
+  NOTE
+    This function is a former part of the test_if_skip_sort_order function.
+*/
+
+key_map TABLE::get_order_by_usable_keys(const ORDER *order, const key_map &map) const
+{
+  /*
+    Keys disabled by ALTER TABLE ... DISABLE KEYS should have already
+    been taken into account.
+  */
+  key_map usable_keys= map;
+  DBUG_ASSERT(usable_keys.is_subset(s->keys_in_use));
+
+  for (const ORDER *tmp_order= order; tmp_order; tmp_order= tmp_order->next)
+  {
+    Item *item= (*tmp_order->item)->real_item();
+    if (item->type() != Item::FIELD_ITEM)
+      return key_map_empty;
+    usable_keys.intersect(((Item_field*) item)->field->part_of_sortkey);
+    if (usable_keys.is_clear_all())
+      return key_map_empty;
+  }
+  return usable_keys;
+}
+
+
+/*
+  Test if we can skip the ORDER BY using an index.
+
+  SYNOPSIS
+    TABLE::simple_test_if_skip_sort_order()
+    order               ORDER BY list
+    select_limit        LIMIT clause
+
+  RETURN
+    Usable key number if we can skip ORDER BY, otherwise MAX_KEY
+
+  NOTE
+    This function is a simplified one-table version of the
+    test_if_skip_sort_order function.
+*/
+
+uint
+TABLE::simple_test_if_skip_sort_order(ORDER *order, ha_rows select_limit)
+{
+  key_map keys;
+  key_map usable_keys= get_order_by_usable_keys(order, keys_in_use_for_query);
+
+  /*
+    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 >= file->stats.records)
+  {
+    keys= *file->keys_to_use_for_scanning();
+    keys.merge(covering_keys);
+    keys.intersect(usable_keys);
+  }
+  else
+    keys= usable_keys;
+
+  for (uint nr= 0; nr < s->keys ; nr++)
+  {
+    uint not_used;
+    if (keys.is_set(nr) && test_if_order_by_key(order, this, nr, &not_used))
+      return nr;
+  }
+  return MAX_KEY;
+}
+
+
+/*
+  Simplified one-table version of remove_const
+
+  SYNOPSIS
+    remove_const_head()
+    where               WHERE clause expression
+
+  RETURNS
+    NULL if order list is a list of constants (in WHERE).
+
+  NOTE
+    This function overwrites order list.
+*/
+
+st_order * st_order::simple_remove_const(COND *where)
+{
+  st_order *first= NULL, *prev= NULL;
+  for (st_order *order= this; order; order= order->next)
+  {
+    DBUG_ASSERT(!order->item[0]->with_sum_func); // should never happen
+    if (!const_item_in_where(where, order->item[0]))
+    {
+      if (!first)
+        first= order;
+      if (prev)
+        prev->next= order;
+      prev= order;
+    }
+  }
+  if (prev)
+    prev->next= NULL;
+  return first;
+}
+
+
 /*****************************************************************************
 ** Instansiate templates
 *****************************************************************************/

=== modified file 'sql/table.h'
--- a/sql/table.h	2010-02-24 13:52:27 +0000
+++ b/sql/table.h	2010-03-11 15:50:27 +0000
@@ -72,6 +72,8 @@ typedef struct st_order {
   Field  *field;			/* If tmp-table group */
   char	 *buff;				/* If tmp-table group */
   table_map used, depend_map;
+
+  st_order * simple_remove_const(COND *where);
 } ORDER;
 
 /**
@@ -965,6 +967,10 @@ public:
       file->extra(HA_EXTRA_NO_KEYREAD);
     }
   }
+
+  void update_const_key_parts(COND *conds);
+  key_map get_order_by_usable_keys(const ORDER *order, const key_map &map) const;
+  uint simple_test_if_skip_sort_order(ORDER *order, ha_rows select_limit);
 };
 
 


Attachment: [text/bzr-bundle] bzr/gshchepa@mysql.com-20100311155027-3wvxqcjh3qbanhu6.bundle
Thread
bzr commit into mysql-next-mr branch (gshchepa:3119) Bug#30584Bug#36569Gleb Shchepa11 Mar