From: Date: September 13 2005 10:19am Subject: bk commit into 4.1 tree (sergefp:1.2419) BUG#12915 List-Archive: http://lists.mysql.com/internals/29715 X-Bug: 12915 Message-Id: <20050913081917.0113C26331F@pslp.mylan> 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;