bk commit into 4.1 tree (sergefp:1.2419) 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.2419 05/09/13 12:19:11 sergefp@stripped +7 -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.40 05/09/13 12:19:08 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.143 05/09/13 12:19:08 sergefp@stripped +15 -2
    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.136 05/09/13 12:19:08 sergefp@stripped +35 -17
    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/13 12:19:08 sergefp@stripped +68 -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/13 12:19:08 sergefp@stripped +2 -0
    BUG#12915: Added get_index_for_order() function

  sql/opt_range.cc
    1.143 05/09/13 12:19:08 sergefp@stripped +62 -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.367 05/09/13 12:19:08 sergefp@stripped +2 -0
    BUG#12915: Added init_read_record_idx function.

# 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-bug12915

--- 1.366/sql/mysql_priv.h	2005-09-06 13:09:55 +04:00
+++ 1.367/sql/mysql_priv.h	2005-09-13 12:19:08 +04:00
@@ -1103,6 +1103,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-13 12:19:08 +04:00
@@ -582,6 +582,68 @@
   return root;
 }
 
+
+/*
+  Find an index that allows to retrieve #limit least records in the given
+  order cheaper cheaper then full table scan.
+
+  NOTE
+    Assume HA_EXTRA_KEYREAD will not be used.
+
+  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;
+
+  for (idx= 0; idx < table->keys; idx++)
+  {
+    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
+    uint partno= 0;
+    ORDER *ord;
+    /* 
+      The below check is sufficient considering we now have BTREE indexes
+      (returns records in order for any index prefix) or HASH indexes (can't
+      return records 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 */
+      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-13 12:19:08 +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-13 12:19:08 +04:00
@@ -29,7 +29,35 @@
 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);
+
+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 +209,45 @@
   return tmp;
 }
 
+
+inline int first_or_next(READ_RECORD *info)
+{
+  if (info->first)
+  {
+    info->first= FALSE;
+    return info->file->index_first(info->record);
+  }
+  else
+    return info->file->index_next(info->record);
+}
+
+
+static int rr_index(READ_RECORD *info)
+{
+  int tmp;
+  while ((tmp=first_or_next(info)))
+  {
+    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.135/sql/sql_delete.cc	2005-08-29 19:01:42 +04:00
+++ 1.136/sql/sql_delete.cc	2005-09-13 12:19:08 +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)) ||
-	  (table->sort.found_records = filesort(thd, table, sortorder, length,
-					   select, HA_POS_ERROR,
-					   &examined_rows))
-	  == HA_POS_ERROR)
+    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))
     {
       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;
-    select= 0;
+    
+    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;
+      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.142/sql/sql_update.cc	2005-02-18 16:14:10 +03:00
+++ 1.143/sql/sql_update.cc	2005-09-13 12:19:08 +04:00
@@ -73,6 +73,7 @@
   READ_RECORD	info;
   TABLE_LIST    *update_table_list= ((TABLE_LIST*)
 				     thd->lex->select_lex.table_list.first);
+  uint          usable_index= MAX_KEY;
   DBUG_ENTER("mysql_update");
 
   LINT_INIT(timestamp_query_id);
@@ -145,6 +146,8 @@
     send_ok(thd);				// No matching records
     DBUG_RETURN(0);
   }
+  if (!select && limit != HA_POS_ERROR)
+    usable_index= get_index_for_order(table, order, limit);
   /* If running in safe sql mode, don't allow updates without keys */
   if (table->quick_keys.is_clear_all())
   {
@@ -164,6 +167,8 @@
     used_key_is_modified= (!select->quick->unique_key_range() &&
 			   check_if_key_used(table, used_index, fields));
   }
+  else if (usable_index != MAX_KEY)
+    used_key_is_modified= check_if_key_used(table, usable_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
@@ -225,7 +230,11 @@
 			   DISK_BUFFER_SIZE, MYF(MY_WME)))
 	goto err;
 
-      init_read_record(&info,thd,table,select,0,1);
+      if (usable_index == MAX_KEY)
+        init_read_record(&info,thd,table,select,0,1);
+      else
+        init_read_record_idx(&info, thd, table, 1, usable_index);
+
       thd->proc_info="Searching rows for update";
       uint tmp_limit= limit;
 
@@ -280,7 +289,11 @@
 
   if (ignore)
     table->file->extra(HA_EXTRA_IGNORE_DUP_KEY);
-  init_read_record(&info,thd,table,select,0,1);
+
+  if (usable_index == MAX_KEY)
+    init_read_record(&info,thd,table,select,0,1);
+  else
+    init_read_record_idx(&info, thd, table, 1, usable_index);
 
   updated= found= 0;
   thd->count_cuted_fields= CHECK_FIELD_WARN;		/* calc cuted fields */

--- 1.39/sql/structs.h	2005-03-23 21:19:10 +03:00
+++ 1.40/sql/structs.h	2005-09-13 12:19:08 +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;