List:Commits« Previous MessageNext Message »
From:Gleb Shchepa Date:December 11 2008 8:39pm
Subject:bzr commit into mysql-5.0-bugteam branch (gshchepa:2732) Bug#30584
Bug#36569
View as plain text  
#At file:///work/bzr/5.0-30584/ based on revid:kgeorge@stripped

 2732 Gleb Shchepa	2008-12-12
      Bug #30584: delete with order by and limit clauses does not
                  use limit efficiently
      Bug #36569: UPDATE ... WHERE ... ORDER BY... always does a
                  filesort even if not required
      
      During the Execution of single-table UPDATE and DELETE
      statements with ORDER BY clause an optimizer used the
      filesort algorithm even if not required.
      
      Extra optimization has been added.
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

per-file messages:
  mysql-test/r/single_delete_update.result
    Added test case for bug #30584 and bug #36569.
  mysql-test/t/single_delete_update.test
    Added test case for bug #30584 and bug #36569.
  sql/opt_range.cc
    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
    
    The QUICK_SELECT_I::is_ordered_by function has been added.
  sql/opt_range.h
    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
    
    The QUICK_SELECT_I::is_ordered_by function has been added.
  sql/sql_delete.cc
    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
    
    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: 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
    
    1. The const_expression_in_where function has been modified
       to accept both Item and Field pointers via intermediate
       wrap_field_or_item class object.
    2. Public const_in_where functions have been added.
    3. Static test_if_order_by_key function has been moved to
       public scope. Also a part of this function has been
       extracted as a new st_table::get_order_by_usable_keys
       method.
  sql/sql_select.h
    Bug #30584: 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
    
    1. test_if_order_by_key() has been moved to public scope.
    2. New const_in_where functions have been added.
  sql/sql_update.cc
    Bug #30584: 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
    
    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: 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
    
    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: 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
    
    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 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	2008-12-11 20:38:57 +0000
@@ -0,0 +1,245 @@
+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);
+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:
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c, d) 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	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
+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	0
+Sort_scan	0
+SELECT * FROM t2 WHERE b = 10 ORDER BY a, c;
+a	b	c	d
+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	2008-12-11 20:38:57 +0000
@@ -0,0 +1,143 @@
+#
+# 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);
+
+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:
+
+CREATE TABLE t2(a INT, b INT, c INT, d INT, INDEX(a, b, c));
+INSERT INTO t2 (a, b, c, d) 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 + 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	2008-10-10 10:27:58 +0000
+++ b/sql/opt_range.cc	2008-12-11 20:38:57 +0000
@@ -9842,7 +9842,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	2008-08-25 17:02:54 +0000
+++ b/sql/opt_range.h	2008-12-11 20:38:57 +0000
@@ -245,6 +245,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	2008-07-15 14:13:21 +0000
+++ b/sql/sql_delete.cc	2008-12-11 20:38:57 +0000
@@ -26,7 +26,7 @@
 #include "sql_trigger.h"
 
 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)
 {
   int		error;
@@ -36,6 +36,9 @@ bool mysql_delete(THD *thd, TABLE_LIST *
   bool          using_limit=limit != HA_POS_ERROR;
   bool		transactional_table, safe_update, const_cond;
   bool          triggers_applicable;
+  bool          need_sort= TRUE;
+  ORDER *order= (ORDER *) ((order_list && order_list->elements) ?
+                           order_list->first : NULL);
   ha_rows	deleted;
   uint usable_index= MAX_KEY;
   SELECT_LEX   *select_lex= &thd->lex->select_lex;
@@ -63,7 +66,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;
@@ -73,9 +76,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);
@@ -171,21 +174,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,
@@ -213,7 +233,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	2008-11-24 15:30:47 +0000
+++ b/sql/sql_select.cc	2008-12-11 20:38:57 +0000
@@ -109,7 +109,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 *table,TMP_TABLE_PARAM *param,
 				    ulonglong options);
@@ -6704,8 +6703,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_in_where(cond, order->item[0]))
 	{
 	  DBUG_PRINT("info",("removing: %s", order->item[0]->full_name()));
 	  continue;
@@ -8802,11 +8800,35 @@ test_if_equality_guarantees_uniqueness(I
 }
 
 /*
-  Return 1 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:
+  wrap_field_or_item(Field *field_arg) : field(field_arg), item(NULL) {}
+  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)
   {
@@ -8816,7 +8838,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)
@@ -8835,7 +8857,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))
       {
@@ -8845,7 +8867,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))
       {
@@ -8859,6 +8881,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_in_where(COND *where, Item *item)
+{
+  Item *dummy= NULL;
+  return const_expression_in_where(where, 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_in_where(COND *where, Field *field)
+{
+  Item *dummy= NULL;
+  return const_expression_in_where(where, field, &dummy);
+}
+
+
 /****************************************************************************
   Create internal temporary table
 ****************************************************************************/
@@ -12139,8 +12192,8 @@ part_of_refkey(TABLE *table,Field *field
     @retval -1  Reverse read on the 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;
@@ -12474,25 +12527,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= table->keys_in_use_for_query;
-  DBUG_ASSERT(usable_keys.is_subset(table->s->keys_in_use));
-
-  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);
 
   ref_key= -1;
   /* Test if constant range in WHERE */

=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h	2008-10-24 02:16:22 +0000
+++ b/sql/sql_select.h	2008-12-11 20:38:57 +0000
@@ -660,3 +660,7 @@ bool error_if_full_join(JOIN *join);
 int report_error(TABLE *table, int error);
 int safe_index_read(JOIN_TAB *tab);
 COND *remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value);
+int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
+                         uint *used_key_parts);
+bool const_in_where(COND *where, Field *field);
+bool const_in_where(COND *where, Item *field);

=== modified file 'sql/sql_update.cc'
--- a/sql/sql_update.cc	2008-11-27 13:57:34 +0000
+++ b/sql/sql_update.cc	2008-12-11 20:38:57 +0000
@@ -275,9 +275,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(&fields));
+    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, fields)))
+        need_sort= FALSE;
+    }
   }
   else
   {

=== modified file 'sql/table.cc'
--- a/sql/table.cc	2008-10-07 21:34:00 +0000
+++ b/sql/table.cc	2008-12-11 20:38:57 +0000
@@ -20,6 +20,7 @@
 #include <errno.h>
 #include <m_ctype.h>
 #include "my_md5.h"
+#include "sql_select.h"
 
 	/* Functions defined in this file */
 
@@ -3133,6 +3134,160 @@ Item_subselect *TABLE_LIST::containing_s
   return (select_lex ? select_lex->master_unit()->item : 0);
 }
 
+
+/*
+  Update st_table::const_key_parts for single table UPDATE query
+
+  SYNOPSIS
+    st_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 st_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_in_where(conds, keyinfo->field))
+        const_key_parts[index]|= part_map;
+    }
+  }
+}
+
+
+/*
+  Calculate bitmap of table keys that ORDER BY can use for ordering
+
+  SYNOPSIS
+    st_table::get_order_by_usable_keys()
+    ORDER               ORDER BY list
+
+  RETURN
+    Bitmap of usable keys
+
+  NOTE
+    This function is a former part of the test_if_skip_sort_order function.
+*/
+
+key_map st_table::get_order_by_usable_keys(const ORDER *order) const
+{
+  /*
+    Keys disabled by ALTER TABLE ... DISABLE KEYS should have already
+    been taken into account.
+  */
+  key_map usable_keys= keys_in_use_for_query;
+  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 by using an index.
+
+  SYNOPSIS
+    st_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
+st_table::simple_test_if_skip_sort_order(ORDER *order, ha_rows select_limit)
+{
+  key_map keys;
+  key_map usable_keys= this->get_order_by_usable_keys(order);
+
+  /*
+    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 >= this->file->records)
+  {
+    keys= *this->file->keys_to_use_for_scanning();
+    keys.merge(this->used_keys);
+    keys.intersect(usable_keys);
+  }
+  else
+    keys= usable_keys;
+
+  for (uint nr= 0; nr < this->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_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	2008-11-14 17:25:57 +0000
+++ b/sql/table.h	2008-12-11 20:38:57 +0000
@@ -41,6 +41,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;
 
 typedef struct st_grant_info
@@ -348,6 +350,10 @@ struct st_table {
   */
   inline bool needs_reopen_or_name_lock()
   { return s->version != refresh_version; }
+
+  void update_const_key_parts(COND *conds);
+  key_map get_order_by_usable_keys(const ORDER *order) const;
+  uint simple_test_if_skip_sort_order(ORDER *order, ha_rows select_limit);
 };
 
 enum enum_schema_table_state

Thread
bzr commit into mysql-5.0-bugteam branch (gshchepa:2732) Bug#30584Bug#36569Gleb Shchepa11 Dec