bk commit into 4.1 tree (sergefp:1.2463) BUG#12915

[Sergey Petrunia]

Below is the list of changes that have just been committed into a local
4.1 repository of psergey. When psergey does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html

ChangeSet
  1.2463 05/09/30 15:21:37 sergefp@stripped +9 -0
  BUG#12915: Added single-table UPDATE/DELTE ... ORDER BY ... LIMIT
  optimization: now can use index to find records to update/delete
  when there is no WHERE clause.

  sql/structs.h
    1.41 05/09/30 15:21:34 sergefp@stripped +1 -0
    BUG#12915: Added init_read_record_idx(), rr_index() that allow to scan
    index using init_read_record()/READ_RECORD::read_record()

  sql/sql_update.cc
    1.144 05/09/30 15:21:34 sergefp@stripped +25 -7
    BUG#12915: Added single-table UPDATE ... ORDER BY ... LIMIT optimization: 
    now can use index to find records to update when there is no WHERE clause.

  sql/sql_delete.cc
    1.137 05/09/30 15:21:34 sergefp@stripped +32 -14
    BUG#12915: Added single-table DELETE ... ORDER BY ... LIMIT optimization: 
    now can use index to find records to delete when there is no WHERE clause.

  sql/records.cc
    1.30 05/09/30 15:21:34 sergefp@stripped +104 -1
    BUG#12915: Added init_read_record_idx(), rr_index() that allow to scan
    index using init_read_record()/read_record.read_record()

  sql/opt_range.h
    1.40 05/09/30 15:21:34 sergefp@stripped +2 -0
    BUG#12915: Added get_index_for_order() function

  sql/opt_range.cc
    1.143 05/09/30 15:21:34 sergefp@stripped +88 -0
    BUG#12915: Added get_index_for_order() - find an index that can be
    used to get first N table records in given ordering cheaper then 
    one would with full table scan.

  sql/mysql_priv.h
    1.368 05/09/30 15:21:34 sergefp@stripped +2 -0
    BUG#12915: Added init_read_record_idx function.

  mysql-test/t/update.test
    1.23 05/09/30 15:21:34 sergefp@stripped +29 -0
    Testcase for BUG#12915

  mysql-test/r/update.result
    1.25 05/09/30 15:21:34 sergefp@stripped +59 -0
    Testcase for BUG#12915

# This is a BitKeeper patch.  What follows are the unified diffs for the
# set of deltas contained in the patch.  The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User:	sergefp
# Host:	pslp.mylan
# Root:	/home/psergey/mysql-4.1-sept30-test

--- 1.367/sql/mysql_priv.h	2005-09-14 16:31:32 +04:00
+++ 1.368/sql/mysql_priv.h	2005-09-30 15:21:34 +04:00
@@ -1105,6 +1105,8 @@
 void init_read_record(READ_RECORD *info, THD *thd, TABLE *reg_form,
 		      SQL_SELECT *select,
 		      int use_record_cache, bool print_errors);
+void init_read_record_idx(READ_RECORD *info, THD *thd, TABLE *table, 
+                          bool print_error, uint idx);
 void end_read_record(READ_RECORD *info);
 ha_rows filesort(THD *thd, TABLE *form,struct st_sort_field *sortorder,
 		 uint s_length, SQL_SELECT *select,

--- 1.142/sql/opt_range.cc	2005-09-06 17:49:08 +04:00
+++ 1.143/sql/opt_range.cc	2005-09-30 15:21:34 +04:00
@@ -582,6 +582,94 @@
   return root;
 }
 
+
+/*
+  Find an index that allows to retrieve first #limit records in the given
+  order cheaper then one would retrieve them using full table scan.
+
+  SYNOPSIS
+    get_index_for_order()
+      table  Table to be accessed
+      order  Required ordering
+      limit  Number of records that will be retrieved
+
+  DESCRIPTION
+    Run through all table indexes and find the shortest index that allows
+    records to be retrieved in given order. If there is such index and
+    reading first #limit records from it is cheaper then scanning the entire
+    table, return 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
+    index number
+    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->keys; idx++)
+  {
+    if (!(table->keys_in_use_for_query.is_set(idx)))
+      continue;
+    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
+    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; 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;
+}
+
+
 /*
   Test if a key can be used in different ranges
 

--- 1.39/sql/opt_range.h	2005-06-04 00:45:57 +04:00
+++ 1.40/sql/opt_range.h	2005-09-30 15:21:34 +04:00
@@ -167,4 +167,6 @@
 QUICK_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
 				       struct st_table_ref *ref);
 
+uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit);
+
 #endif

--- 1.29/sql/records.cc	2004-10-06 20:14:29 +04:00
+++ 1.30/sql/records.cc	2005-09-30 15:21:34 +04:00
@@ -29,7 +29,59 @@
 static int init_rr_cache(READ_RECORD *info);
 static int rr_cmp(uchar *a,uchar *b);
 
-	/* init struct for read with info->read_record */
+static int rr_index(READ_RECORD *info);
+
+
+
+/*
+  Initialize READ_RECORD structure to perform full index scan
+
+  SYNOPSIS 
+    init_read_record_idx()
+      info         READ_RECORD structure to initialize.
+      thd          Thread handle
+      table        Table to be accessed 
+      print_error  If true, call table->file->print_error() if an error
+                   occurs (except for end-of-records error)
+      idx          index to scan
+  
+  DESCRIPTION
+    Initialize READ_RECORD structure to perform full index scan (in forward
+    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
+    join_read_first/next functions.
+*/
+
+void init_read_record_idx(READ_RECORD *info, THD *thd, TABLE *table,
+                          bool print_error, uint idx)
+{
+  bzero((char*) info,sizeof(*info));
+  info->thd=thd;
+  info->table=table;
+  info->file= table->file;
+  info->forms= &info->table;		/* Only one table */
+    
+  info->record= table->record[0];
+  info->ref_length= table->file->ref_length;
+
+  info->select=NULL;
+  info->print_error=print_error;
+  info->ignore_not_found_rows= 0;
+  table->status=0;			/* And it's always found */
+
+  if (!table->file->inited)
+  {
+    table->file->ha_index_init(idx);
+    table->file->extra(HA_EXTRA_RETRIEVE_PRIMARY_KEY);
+  }
+  info->read_record= rr_index;
+  info->first= TRUE;
+}
+
+
+/* init struct for read with info->read_record */
 
 void init_read_record(READ_RECORD *info,THD *thd, TABLE *table,
 		      SQL_SELECT *select,
@@ -181,6 +233,57 @@
   return tmp;
 }
 
+
+/*
+  Read next index record. The calling convention of this function is 
+  compatible with READ_RECORD::read_record.
+
+  SYNOPSIS
+    rr_index()
+      info  Scan info
+
+  RETURN
+    0   Ok
+    -1  End of records 
+    1   Error   
+*/
+
+static int rr_index(READ_RECORD *info)
+{
+  int tmp;
+  while (1)
+  {
+    if (info->first)
+    {
+      info->first= FALSE;
+      tmp= info->file->index_first(info->record);
+    }
+    else
+      tmp= info->file->index_next(info->record);
+    
+    if (!tmp)
+      break;
+    if (info->thd->killed)
+    {
+      my_error(ER_SERVER_SHUTDOWN,MYF(0));
+      return 1;
+    }
+    if (tmp != HA_ERR_RECORD_DELETED)
+    {
+      if (tmp == HA_ERR_END_OF_FILE)
+	tmp= -1;
+      else
+      {
+	if (info->print_error)
+	  info->table->file->print_error(tmp,MYF(0));
+	if (tmp < 0)				// Fix negative BDB errno
+	  tmp=1;
+      }
+      break;
+    }
+  }
+  return tmp;
+}
 
 static int rr_sequential(READ_RECORD *info)
 {

--- 1.136/sql/sql_delete.cc	2005-09-25 22:22:20 +04:00
+++ 1.137/sql/sql_delete.cc	2005-09-30 15:21:34 +04:00
@@ -37,6 +37,7 @@
   bool 		using_limit=limit != HA_POS_ERROR;
   bool		transactional_table, log_delayed, safe_update, const_cond; 
   ha_rows	deleted;
+  uint usable_index= MAX_KEY;
   DBUG_ENTER("mysql_delete");
 
   if ((open_and_lock_tables(thd, table_list)))
@@ -119,30 +120,47 @@
     tables.table = table;
     tables.alias = table_list->alias;
 
-    table->sort.io_cache = (IO_CACHE *) my_malloc(sizeof(IO_CACHE),
-                                             MYF(MY_FAE | MY_ZEROFILL));
       if (thd->lex->select_lex.setup_ref_array(thd, order->elements) ||
 	  setup_order(thd, thd->lex->select_lex.ref_pointer_array, &tables,
-		      fields, all_fields, (ORDER*) order->first) ||
-	  !(sortorder=make_unireg_sortorder((ORDER*) order->first, &length)) ||
+                    fields, all_fields, (ORDER*) order->first))
+    {
+      delete select;
+      free_underlaid_joins(thd, &thd->lex->select_lex);
+      DBUG_RETURN(-1);			// This will force out message
+    }
+    
+    if (!select && limit != HA_POS_ERROR)
+      usable_index= get_index_for_order(table, (ORDER*)(order->first), 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, &length)) ||
 	  (table->sort.found_records = filesort(thd, table, sortorder, length,
 					   select, HA_POS_ERROR,
 					   &examined_rows))
 	  == HA_POS_ERROR)
-    {
+      {
+        delete select;
+        free_underlaid_joins(thd, &thd->lex->select_lex);
+        DBUG_RETURN(-1);			// This will force out message
+      }
+      /*
+        Filesort has already found and selected the rows we want to delete,
+        so we don't need the where clause
+      */
       delete select;
-      free_underlaid_joins(thd, &thd->lex->select_lex);
-      DBUG_RETURN(-1);			// This will force out message
+      select= 0;
     }
-    /*
-      Filesort has already found and selected the rows we want to delete,
-      so we don't need the where clause
-    */
-    delete select;
-    select= 0;
   }
 
-  init_read_record(&info,thd,table,select,1,1);
+  if (usable_index==MAX_KEY)
+    init_read_record(&info,thd,table,select,1,1);
+  else
+    init_read_record_idx(&info, thd, table, 1, usable_index);
+
   deleted=0L;
   init_ftfuncs(thd, &thd->lex->select_lex, 1);
   thd->proc_info="updating";

--- 1.143/sql/sql_update.cc	2005-09-25 22:22:21 +04:00
+++ 1.144/sql/sql_update.cc	2005-09-30 15:21:34 +04:00
@@ -61,7 +61,8 @@
   bool		safe_update= thd->options & OPTION_SAFE_UPDATES;
   bool		used_key_is_modified, transactional_table, log_delayed;
   int		error=0;
-  uint		used_index;
+  uint		used_index= MAX_KEY;
+  bool          need_sort= TRUE;
 #ifndef NO_EMBEDDED_ACCESS_CHECKS
   uint		want_privilege;
 #endif
@@ -145,6 +146,11 @@
     send_ok(thd);				// No matching records
     DBUG_RETURN(0);
   }
+  if (!select && limit != HA_POS_ERROR)
+  {
+    if (MAX_KEY != (used_index= get_index_for_order(table, order, limit)))
+      need_sort= FALSE;
+  }
   /* If running in safe sql mode, don't allow updates without keys */
   if (table->quick_keys.is_clear_all())
   {
@@ -157,6 +163,7 @@
     }
   }
   init_ftfuncs(thd, &thd->lex->select_lex, 1);
+  
   /* Check if we are modifying a key that we are used to search with */
   if (select && select->quick)
   {
@@ -164,13 +171,15 @@
     used_key_is_modified= (!select->quick->unique_key_range() &&
 			   check_if_key_used(table, used_index, fields));
   }
+  else if (used_index != MAX_KEY)
+  {
+    used_key_is_modified= check_if_key_used(table, used_index, fields);
+  }
   else if ((used_index=table->file->key_used_on_scan) < MAX_KEY)
     used_key_is_modified=check_if_key_used(table, used_index, fields);
   else
-  {
     used_key_is_modified=0;
-    used_index= MAX_KEY;
-  }
+
   if (used_key_is_modified || order)
   {
     /*
@@ -181,10 +190,11 @@
     if (used_index < MAX_KEY && old_used_keys.is_set(used_index))
     {
       table->key_read=1;
-      table->file->extra(HA_EXTRA_KEYREAD);
+      table->file->extra(HA_EXTRA_KEYREAD); //todo: psergey: check
     }
 
-    if (order)
+    /* note: can actually avoid sorting below.. */
+    if (order && need_sort)
     {
       /*
 	Doing an ORDER BY;  Let filesort find and sort the rows we are going
@@ -225,7 +235,11 @@
 			   DISK_BUFFER_SIZE, MYF(MY_WME)))
 	goto err;
 
-      init_read_record(&info,thd,table,select,0,1);
+      if (used_index == MAX_KEY)
+        init_read_record(&info,thd,table,select,0,1);
+      else
+        init_read_record_idx(&info, thd, table, 1, used_index);
+
       thd->proc_info="Searching rows for update";
       uint tmp_limit= limit;
 
@@ -251,6 +265,10 @@
 	error= 1;				// Aborted
       limit= tmp_limit;
       end_read_record(&info);
+
+      /* if we got here we must not use index in the main update loop below */
+      used_index= MAX_KEY;
+      
       /* Change select to use tempfile */
       if (select)
       {

--- 1.40/sql/structs.h	2005-09-14 15:18:11 +04:00
+++ 1.41/sql/structs.h	2005-09-30 15:21:34 +04:00
@@ -132,6 +132,7 @@
   byte	*cache,*cache_pos,*cache_end,*read_positions;
   IO_CACHE *io_cache;
   bool print_error, ignore_not_found_rows;
+  bool first; /* used only with rr_index_read */
 } READ_RECORD;
 
 

--- 1.24/mysql-test/r/update.result	2005-09-22 01:38:24 +04:00
+++ 1.25/mysql-test/r/update.result	2005-09-30 15:21:34 +04:00
@@ -263,3 +263,62 @@
 delete from t1 where count(*)=1;
 ERROR HY000: Invalid use of group function
 drop table t1;
+create table t1 ( a int, index (a) );
+insert into t1 values (0),(0),(0),(0),(0),(0),(0),(0);
+flush status;
+select a from t1 order by a limit 1;
+a
+0
+show status like 'handler_read%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+flush status;
+update t1 set a=unix_timestamp() order by a limit 1;
+show status like 'handler_read%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	1
+Handler_read_rnd_next	0
+flush status;
+delete from t1 order by a limit 1;
+show status like 'handler_read%';
+Variable_name	Value
+Handler_read_first	1
+Handler_read_key	0
+Handler_read_next	0
+Handler_read_prev	0
+Handler_read_rnd	0
+Handler_read_rnd_next	0
+flush status;
+delete from t1 order by a desc limit 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	9
+alter table t1 disable keys;
+flush status;
+delete from t1 order by a limit 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	9
+select count(*) from t1;
+count(*)
+5
+drop table t1;

--- 1.22/mysql-test/t/update.test	2005-09-22 01:38:16 +04:00
+++ 1.23/mysql-test/t/update.test	2005-09-30 15:21:34 +04:00
@@ -227,4 +227,33 @@
 delete from t1 where count(*)=1;
 drop table t1;
 
+# BUG#12915: Optimize "DELETE|UPDATE ... ORDER BY ... LIMIT n" to use an index
+create table t1 ( a int, index (a) );
+insert into t1 values (0),(0),(0),(0),(0),(0),(0),(0);
+
+flush status;
+select a from t1 order by a limit 1;
+show status like 'handler_read%';
+
+flush status;
+update t1 set a=unix_timestamp() order by a limit 1;
+show status like 'handler_read%';
+
+flush status;
+delete from t1 order by a limit 1;
+show status like 'handler_read%';
+
+flush status;
+delete from t1 order by a desc limit 1;
+show status like 'handler_read%';
+
+alter table t1 disable keys;
+
+flush status;
+delete from t1 order by a limit 1;
+show status like 'handler_read%';
+
+select count(*) from t1;
+
+drop table t1;
 # End of 4.1 tests