diff options
Diffstat (limited to 'sql/opt_range.cc')
| -rw-r--r-- | sql/opt_range.cc | 89 |
1 files changed, 89 insertions, 0 deletions
diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 1a6d97caa6a..ff2b14a27ee 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -1363,6 +1363,95 @@ SEL_ARG *SEL_ARG::clone_tree() /* + Find the best index to retrieve first N records in given order + + SYNOPSIS + get_index_for_order() + table Table to be accessed + order Required ordering + limit Number of records that will be retrieved + + DESCRIPTION + Find the best index that allows to retrieve first #limit records in the + given order cheaper then one would retrieve them using full table scan. + + IMPLEMENTATION + Run through all table indexes and find the shortest index that allows + records to be retrieved in given order. We look for the shortest index + as we will have fewer index pages to read with 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->s->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; +} + + +/* Table rows retrieval plan. Range optimizer creates QUICK_SELECT_I-derived objects from table read plans. */ |