diff options
Diffstat (limited to 'sql/opt_sum.cc')
| -rw-r--r-- | sql/opt_sum.cc | 1092 |
1 files changed, 1092 insertions, 0 deletions
diff --git a/sql/opt_sum.cc b/sql/opt_sum.cc new file mode 100644 index 00000000..27360d4a --- /dev/null +++ b/sql/opt_sum.cc @@ -0,0 +1,1092 @@ +/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. + Copyright (c) 2008, 2017, MariaDB Corporation. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */ + + +/** + @file + + Optimising of MIN(), MAX() and COUNT(*) queries without 'group by' clause + by replacing the aggregate expression with a constant. + + Given a table with a compound key on columns (a,b,c), the following + types of queries are optimised (assuming the table handler supports + the required methods) + + @verbatim + SELECT COUNT(*) FROM t1[,t2,t3,...] + SELECT MIN(b) FROM t1 WHERE a=const + SELECT MAX(c) FROM t1 WHERE a=const AND b=const + SELECT MAX(b) FROM t1 WHERE a=const AND b<const + SELECT MIN(b) FROM t1 WHERE a=const AND b>const + SELECT MIN(b) FROM t1 WHERE a=const AND b BETWEEN const AND const + SELECT MAX(b) FROM t1 WHERE a=const AND b BETWEEN const AND const + @endverbatim + + Instead of '<' one can use '<=', '>', '>=' and '=' as well. + Instead of 'a=const' the condition 'a IS NULL' can be used. + + If all selected fields are replaced then we will also remove all + involved tables and return the answer without any join. Thus, the + following query will be replaced with a row of two constants: + @verbatim + SELECT MAX(b), MIN(d) FROM t1,t2 + WHERE a=const AND b<const AND d>const + @endverbatim + (assuming a index for column d of table t2 is defined) +*/ + +#include "mariadb.h" +#include "sql_priv.h" +#include "key.h" // key_cmp_if_same +#include "sql_select.h" + +static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref, Field* field, + COND *cond, uint *range_fl, + uint *key_prefix_length); +static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field, + COND *cond, uint range_fl, uint prefix_len); +static int maxmin_in_range(bool max_fl, Field* field, COND *cond); + + +/* + Get exact count of rows in all tables + + SYNOPSIS + get_exact_records() + tables List of tables + + NOTES + When this is called, we know all table handlers supports HA_HAS_RECORDS + or HA_STATS_RECORDS_IS_EXACT + + RETURN + ULONGLONG_MAX Error: Could not calculate number of rows + # Multiplication of number of rows in all tables +*/ + +static ulonglong get_exact_record_count(List<TABLE_LIST> &tables) +{ + ulonglong count= 1; + TABLE_LIST *tl; + List_iterator<TABLE_LIST> ti(tables); + while ((tl= ti++)) + { + ha_rows tmp= tl->table->file->records(); + if (tmp == HA_POS_ERROR) + return ULONGLONG_MAX; + count*= tmp; + } + return count; +} + + +/** + Use index to read MIN(field) value. + + @param table Table object + @param ref Reference to the structure where we store the key value + @item_field Field used in MIN() + @range_fl Whether range endpoint is strict less than + @prefix_len Length of common key part for the range + + @retval + 0 No errors + HA_ERR_... Otherwise +*/ + +static int get_index_min_value(TABLE *table, TABLE_REF *ref, + Item_field *item_field, uint range_fl, + uint prefix_len) +{ + int error; + + if (!ref->key_length) + error= table->file->ha_index_first(table->record[0]); + else + { + /* + Use index to replace MIN/MAX functions with their values + according to the following rules: + + 1) Insert the minimum non-null values where the WHERE clause still + matches, or + 2) a NULL value if there are only NULL values for key_part_k. + 3) Fail, producing a row of nulls + + Implementation: Read the smallest value using the search key. If + the interval is open, read the next value after the search + key. If read fails, and we're looking for a MIN() value for a + nullable column, test if there is an exact match for the key. + */ + if (!(range_fl & NEAR_MIN)) + /* + Closed interval: Either The MIN argument is non-nullable, or + we have a >= predicate for the MIN argument. + */ + error= table->file->ha_index_read_map(table->record[0], + ref->key_buff, + make_prev_keypart_map(ref->key_parts), + HA_READ_KEY_OR_NEXT); + else + { + /* + Open interval: There are two cases: + 1) We have only MIN() and the argument column is nullable, or + 2) there is a > predicate on it, nullability is irrelevant. + We need to scan the next bigger record first. + Open interval is not used if the search key involves the last keypart, + and it would not work. + */ + DBUG_ASSERT(prefix_len < ref->key_length); + error= table->file->ha_index_read_map(table->record[0], + ref->key_buff, + make_prev_keypart_map(ref->key_parts), + HA_READ_AFTER_KEY); + /* + If the found record is outside the group formed by the search + prefix, or there is no such record at all, check if all + records in that group have NULL in the MIN argument + column. If that is the case return that NULL. + + Check if case 1 from above holds. If it does, we should read + the skipped tuple. + */ + if (item_field->field->real_maybe_null() && + ref->key_buff[prefix_len] == 1 && + /* + Last keypart (i.e. the argument to MIN) is set to NULL by + find_key_for_maxmin only if all other keyparts are bound + to constants in a conjunction of equalities. Hence, we + can detect this by checking only if the last keypart is + NULL. + */ + (error == HA_ERR_KEY_NOT_FOUND || + key_cmp_if_same(table, ref->key_buff, ref->key, prefix_len))) + { + DBUG_ASSERT(item_field->field->real_maybe_null()); + error= table->file->ha_index_read_map(table->record[0], + ref->key_buff, + make_prev_keypart_map(ref->key_parts), + HA_READ_KEY_EXACT); + } + } + } + return error; +} + + +/** + Use index to read MAX(field) value. + + @param table Table object + @param ref Reference to the structure where we store the key value + @range_fl Whether range endpoint is strict greater than + + @retval + 0 No errors + HA_ERR_... Otherwise +*/ + +static int get_index_max_value(TABLE *table, TABLE_REF *ref, uint range_fl) +{ + return (ref->key_length ? + table->file->ha_index_read_map(table->record[0], ref->key_buff, + make_prev_keypart_map(ref->key_parts), + range_fl & NEAR_MAX ? + HA_READ_BEFORE_KEY : + HA_READ_PREFIX_LAST_OR_PREV) : + table->file->ha_index_last(table->record[0])); +} + + + +/** + Substitutes constants for some COUNT(), MIN() and MAX() functions. + + @param thd thread handler + @param tables list of leaves of join table tree + @param all_fields All fields to be returned + @param conds WHERE clause + + @note + This function is only called for queries with aggregate functions and no + GROUP BY part. This means that the result set shall contain a single + row only + + @retval + 0 no errors + @retval + 1 if all items were resolved + @retval + HA_ERR_KEY_NOT_FOUND on impossible conditions + @retval + HA_ERR_... if a deadlock or a lock wait timeout happens, for example + @retval + ER_... e.g. ER_SUBQUERY_NO_1_ROW +*/ + +int opt_sum_query(THD *thd, + List<TABLE_LIST> &tables, List<Item> &all_fields, COND *conds) +{ + List_iterator_fast<Item> it(all_fields); + List_iterator<TABLE_LIST> ti(tables); + TABLE_LIST *tl; + int const_result= 1; + bool recalc_const_item= 0; + ulonglong count= 1; + bool is_exact_count= TRUE, maybe_exact_count= TRUE; + table_map removed_tables= 0, outer_tables= 0, used_tables= 0; + table_map where_tables= 0; + Item *item; + int error= 0; + DBUG_ENTER("opt_sum_query"); + + thd->lex->current_select->min_max_opt_list.empty(); + + if (conds) + where_tables= conds->used_tables(); + + /* + Analyze outer join dependencies, and, if possible, compute the number + of returned rows. + */ + while ((tl= ti++)) + { + TABLE_LIST *embedded; + for (embedded= tl ; embedded; embedded= embedded->embedding) + { + if (embedded->on_expr) + break; + } + if (embedded) + /* Don't replace expression on a table that is part of an outer join */ + { + outer_tables|= tl->table->map; + + /* + We can't optimise LEFT JOIN in cases where the WHERE condition + restricts the table that is used, like in: + SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition + WHERE t2.field IS NULL; + */ + if (tl->table->map & where_tables) + DBUG_RETURN(0); + } + else + used_tables|= tl->table->map; + + /* + If the storage manager of 'tl' gives exact row count as part of + statistics (cheap), compute the total number of rows. If there are + no outer table dependencies, this count may be used as the real count. + Schema tables are filled after this function is invoked, so we can't + get row count + */ + if (!(tl->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) || + tl->schema_table) + { + maybe_exact_count&= MY_TEST(!tl->schema_table && + (tl->table->file->ha_table_flags() & + HA_HAS_RECORDS)); + is_exact_count= FALSE; + count= 1; // ensure count != 0 + } + else if (tl->is_materialized_derived() || + tl->jtbm_subselect) + { + /* + Can't remove a derived table as it's number of rows is just an + estimate. + */ + DBUG_RETURN(0); + } + else + { + error= tl->table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK); + if (unlikely(error)) + { + tl->table->file->print_error(error, MYF(ME_FATAL)); + DBUG_RETURN(error); + } + count*= tl->table->file->stats.records; + } + } + + /* + Iterate through all items in the SELECT clause and replace + COUNT(), MIN() and MAX() with constants (if possible). + */ + + while ((item= it++)) + { + if (item->type() == Item::SUM_FUNC_ITEM) + { + Item_sum *item_sum= (((Item_sum*) item)); + switch (item_sum->sum_func()) { + case Item_sum::COUNT_FUNC: + /* + If the expr in COUNT(expr) can never be null we can change this + to the number of rows in the tables if this number is exact and + there are no outer joins. + */ + if (!conds && !((Item_sum_count*) item)->get_arg(0)->maybe_null && + !outer_tables && maybe_exact_count && + ((item->used_tables() & OUTER_REF_TABLE_BIT) == 0)) + { + if (!is_exact_count) + { + if ((count= get_exact_record_count(tables)) == ULONGLONG_MAX) + { + /* Error from handler in counting rows. Don't optimize count() */ + const_result= 0; + continue; + } + is_exact_count= 1; // count is now exact + } + ((Item_sum_count*) item)->make_const((longlong) count); + recalc_const_item= 1; + } + else + const_result= 0; + break; + case Item_sum::MIN_FUNC: + case Item_sum::MAX_FUNC: + { + int is_max= MY_TEST(item_sum->sum_func() == Item_sum::MAX_FUNC); + /* + If MIN/MAX(expr) is the first part of a key or if all previous + parts of the key is found in the COND, then we can use + indexes to find the key. + */ + Item *expr=item_sum->get_arg(0); + if (((expr->used_tables() & OUTER_REF_TABLE_BIT) == 0) && + expr->real_item()->type() == Item::FIELD_ITEM) + { + uchar key_buff[MAX_KEY_LENGTH]; + TABLE_REF ref; + uint range_fl, prefix_len; + + ref.key_buff= key_buff; + Item_field *item_field= (Item_field*) (expr->real_item()); + TABLE *table= item_field->field->table; + + /* + Look for a partial key that can be used for optimization. + If we succeed, ref.key_length will contain the length of + this key, while prefix_len will contain the length of + the beginning of this key without field used in MIN/MAX(). + Type of range for the key part for this field will be + returned in range_fl. + */ + if (table->file->inited || (outer_tables & table->map) || + !find_key_for_maxmin(is_max, &ref, item_field->field, conds, + &range_fl, &prefix_len)) + { + const_result= 0; + break; + } + longlong info_limit= 1; + error= 0; + + table->file->info_push(INFO_KIND_FORCE_LIMIT_BEGIN, &info_limit); + if (!table->const_table) + { + if (likely(!(error= table->file->ha_index_init((uint) ref.key, + 1)))) + error= (is_max ? + get_index_max_value(table, &ref, range_fl) : + get_index_min_value(table, &ref, item_field, range_fl, + prefix_len)); + } + /* Verify that the read tuple indeed matches the search key */ + if (!error && + reckey_in_range(is_max, &ref, item_field->field, + conds, range_fl, prefix_len)) + error= HA_ERR_KEY_NOT_FOUND; + if (!table->const_table) + { + table->file->ha_end_keyread(); + table->file->ha_index_end(); + } + table->file->info_push(INFO_KIND_FORCE_LIMIT_END, NULL); + if (error) + { + if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE) + DBUG_RETURN(HA_ERR_KEY_NOT_FOUND); // No rows matching WHERE + /* HA_ERR_LOCK_DEADLOCK or some other error */ + table->file->print_error(error, MYF(0)); + DBUG_RETURN(error); + } + removed_tables|= table->map; + } + else if (!expr->const_item() || !is_exact_count || conds) + { + /* + The optimization is not applicable in both cases: + (a) 'expr' is a non-constant expression. Then we can't + replace 'expr' by a constant. + (b) 'expr' is a costant. According to ANSI, MIN/MAX must return + NULL if the query does not return any rows. Thus, if we are not + able to determine if the query returns any rows, we can't apply + the optimization and replace MIN/MAX with a constant. + (c) there is a WHERE clause. The WHERE conditions may result in + an empty result, but the clause cannot be taken into account here. + */ + const_result= 0; + break; + } + item_sum->set_aggregator(item_sum->has_with_distinct() ? + Aggregator::DISTINCT_AGGREGATOR : + Aggregator::SIMPLE_AGGREGATOR); + /* + If count == 0 (so is_exact_count == TRUE) and + there're no outer joins, set to NULL, + otherwise set to the constant value. + */ + if (!count && !outer_tables) + { + item_sum->aggregator_clear(); + } + else + { + item_sum->reset_and_add(); + /* + Save a reference to the item for possible rollback + of the min/max optimizations for this select + */ + thd->lex->current_select->min_max_opt_list.push_back(item_sum); + } + item_sum->make_const(); + recalc_const_item= 1; + break; + } + default: + const_result= 0; + break; + } + } + else if (const_result) + { + if (recalc_const_item) + item->update_used_tables(); + if (!item->const_item() && item->type() != Item::WINDOW_FUNC_ITEM) + const_result= 0; + } + } + + if (unlikely(thd->is_error())) + DBUG_RETURN(thd->get_stmt_da()->sql_errno()); + + /* + If we have a where clause, we can only ignore searching in the + tables if MIN/MAX optimisation replaced all used tables + We do not use replaced values in case of: + SELECT MIN(key) FROM table_1, empty_table + removed_tables is != 0 if we have used MIN() or MAX(). + */ + if (removed_tables && used_tables != removed_tables) + const_result= 0; // We didn't remove all tables + DBUG_RETURN(const_result); +} + + +/* + Check if both item1 and item2 are strings, and item1 has fewer characters + than item2. +*/ + +static bool check_item1_shorter_item2(Item *item1, Item *item2) +{ + if (item1->cmp_type() == STRING_RESULT && + item2->cmp_type() == STRING_RESULT) + { + int len1= item1->max_length / item1->collation.collation->mbmaxlen; + int len2= item2->max_length / item2->collation.collation->mbmaxlen; + return len1 < len2; + } + return false; /* When the check is not applicable, it means "not bigger" */ +} + + +/** + Test if the predicate compares a field with constants. + + @param func_item Predicate item + @param[out] args Here we store the field followed by constants + @param[out] inv_order Is set to 1 if the predicate is of the form + 'const op field' + + @retval + 0 func_item is a simple predicate: a field is compared with a constant + whose length does not exceed the max length of the field values + @retval + 1 Otherwise +*/ + +bool simple_pred(Item_func *func_item, Item **args, bool *inv_order) +{ + Item *item; + *inv_order= 0; + switch (func_item->argument_count()) { + case 0: + /* MULT_EQUAL_FUNC */ + { + Item_equal *item_equal= (Item_equal *) func_item; + if (!(args[1]= item_equal->get_const())) + return 0; + Item_equal_fields_iterator it(*item_equal); + if (!(item= it++)) + return 0; + args[0]= item->real_item(); + if (check_item1_shorter_item2(args[0], args[1])) + return 0; + if (it++) + return 0; + } + break; + case 1: + /* field IS NULL */ + item= func_item->arguments()[0]->real_item(); + if (item->type() != Item::FIELD_ITEM) + return 0; + args[0]= item; + break; + case 2: + /* 'field op const' or 'const op field' */ + item= func_item->arguments()[0]->real_item(); + if (item->type() == Item::FIELD_ITEM) + { + args[0]= item; + item= func_item->arguments()[1]->real_item(); + if (!item->const_item()) + return 0; + args[1]= item; + } + else if (item->const_item()) + { + args[1]= item; + item= func_item->arguments()[1]->real_item(); + if (item->type() != Item::FIELD_ITEM) + return 0; + args[0]= item; + *inv_order= 1; + } + else + return 0; + if (check_item1_shorter_item2(args[0], args[1])) + return 0; + break; + case 3: + /* field BETWEEN const AND const */ + item= func_item->arguments()[0]->real_item(); + if (item->type() == Item::FIELD_ITEM) + { + args[0]= item; + for (int i= 1 ; i <= 2; i++) + { + item= func_item->arguments()[i]->real_item(); + if (!item->const_item()) + return 0; + args[i]= item; + if (check_item1_shorter_item2(args[0], args[i])) + return 0; + } + } + else + return 0; + } + return 1; +} + + +/** + Check whether a condition matches a key to get {MAX|MIN}(field):. + + For the index specified by the keyinfo parameter and an index that + contains the field as its component (field_part), the function + checks whether + + - the condition cond is a conjunction, + - all of its conjuncts refer to columns of the same table, and + - each conjunct is on one of the following forms: + - f_i = const_i or const_i = f_i or f_i IS NULL, + where f_i is part of the index + - field {<|<=|>=|>|=} const + - const {<|<=|>=|>|=} field + - field BETWEEN const_1 AND const_2 + + As a side-effect, the key value to be used for looking up the MIN/MAX value + is actually stored inside the Field object. An interesting feature is that + the function will find the most restrictive endpoint by over-eager + evaluation of the @c WHERE condition. It continually stores the current + endpoint inside the Field object. For a query such as + + @code + SELECT MIN(a) FROM t1 WHERE a > 3 AND a > 5; + @endcode + + the algorithm will recurse over the conjuction, storing first a 3 in the + field. In the next recursive invocation the expression a > 5 is evaluated + as 3 > 5 (Due to the dual nature of Field objects as value carriers and + field identifiers), which will obviously fail, leading to 5 being stored in + the Field object. + + @param[in] max_fl Set to true if we are optimizing MAX(), + false means we are optimizing %MIN() + @param[in, out] ref Reference to the structure where the function + stores the key value + @param[in] keyinfo Reference to the key info + @param[in] field_part Pointer to the key part for the field + @param[in] cond WHERE condition + @param[in,out] key_part_used Map of matchings parts. The function will output + the set of key parts actually being matched in + this set, yet it relies on the caller to + initialize the value to zero. This is due + to the fact that this value is passed + recursively. + @param[in,out] range_fl Says whether endpoints use strict greater/less + than. + @param[out] prefix_len Length of common key part for the range + where MAX/MIN is searched for + + @retval + false Index can't be used. + @retval + true We can use the index to get MIN/MAX value +*/ + +static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo, + KEY_PART_INFO *field_part, COND *cond, + key_part_map *key_part_used, uint *range_fl, + uint *prefix_len) +{ + DBUG_ENTER("matching_cond"); + if (!cond) + DBUG_RETURN(TRUE); + Field *field= field_part->field; + table_map cond_used_tables= cond->used_tables(); + if (cond_used_tables & OUTER_REF_TABLE_BIT) + { + DBUG_RETURN(FALSE); + } + if (!(cond_used_tables & field->table->map) && + MY_TEST(cond_used_tables & ~PSEUDO_TABLE_BITS)) + { + /* Condition doesn't restrict the used table */ + DBUG_RETURN(!cond->const_item()); + } + else if (cond->is_expensive()) + DBUG_RETURN(FALSE); + if (cond->type() == Item::COND_ITEM) + { + if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC) + DBUG_RETURN(FALSE); + + /* AND */ + List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list()); + Item *item; + while ((item= li++)) + { + if (!matching_cond(max_fl, ref, keyinfo, field_part, item, + key_part_used, range_fl, prefix_len)) + DBUG_RETURN(FALSE); + } + DBUG_RETURN(TRUE); + } + + if (cond->type() != Item::FUNC_ITEM) + DBUG_RETURN(FALSE); // Not operator, can't optimize + + bool eq_type= 0; // =, <=> or IS NULL + bool is_null_safe_eq= FALSE; // The operator is NULL safe, e.g. <=> + bool noeq_type= 0; // < or > + bool less_fl= 0; // < or <= + bool is_null= 0; // IS NULL + bool between= 0; // BETWEEN ... AND ... + + switch (((Item_func*) cond)->functype()) { + case Item_func::ISNULL_FUNC: + is_null= 1; /* fall through */ + case Item_func::EQ_FUNC: + eq_type= TRUE; + break; + case Item_func::EQUAL_FUNC: + eq_type= is_null_safe_eq= TRUE; + break; + case Item_func::LT_FUNC: + noeq_type= 1; /* fall through */ + case Item_func::LE_FUNC: + less_fl= 1; + break; + case Item_func::GT_FUNC: + noeq_type= 1; /* fall through */ + case Item_func::GE_FUNC: + break; + case Item_func::BETWEEN: + if (((Item_func_between*) cond)->negated) + DBUG_RETURN(FALSE); + between= 1; + break; + case Item_func::MULT_EQUAL_FUNC: + eq_type= 1; + break; + default: + DBUG_RETURN(FALSE); // Can't optimize function + } + + Item *args[3]; + bool inv; + + /* Test if this is a comparison of a field and constant */ + if (!simple_pred((Item_func*) cond, args, &inv)) + DBUG_RETURN(FALSE); + + if (!is_null_safe_eq && !is_null && + (args[1]->is_null() || (between && args[2]->is_null()))) + DBUG_RETURN(FALSE); + + if (inv && !eq_type) + less_fl= 1-less_fl; // Convert '<' -> '>' (etc) + + /* Check if field is part of the tested partial key */ + uchar *key_ptr= ref->key_buff; + KEY_PART_INFO *part; + for (part= keyinfo->key_part; ; key_ptr+= part++->store_length) + + { + if (part > field_part) + DBUG_RETURN(FALSE); // Field is beyond the tested parts + if (part->field->eq(((Item_field*) args[0])->field)) + break; // Found a part of the key for the field + } + + bool is_field_part= part == field_part; + if (!(is_field_part || eq_type)) + DBUG_RETURN(FALSE); + + key_part_map org_key_part_used= *key_part_used; + if (eq_type || between || max_fl == less_fl) + { + uint length= (uint)(key_ptr-ref->key_buff)+part->store_length; + if (ref->key_length < length) + { + /* Ultimately ref->key_length will contain the length of the search key */ + ref->key_length= length; + ref->key_parts= (uint)(part - keyinfo->key_part) + 1; + } + if (!*prefix_len && part+1 == field_part) + *prefix_len= length; + if (is_field_part && eq_type) + *prefix_len= ref->key_length; + + *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part); + } + + if (org_key_part_used == *key_part_used && + /* + The current search key is not being extended with a new key part. This + means that the a condition is added a key part for which there was a + previous condition. We can only overwrite such key parts in some special + cases, e.g. a > 2 AND a > 1 (here range_fl must be set to something). In + all other cases the WHERE condition is always false anyway. + */ + (eq_type || *range_fl == 0)) + DBUG_RETURN(FALSE); + + if (org_key_part_used != *key_part_used || + (is_field_part && + (between || eq_type || max_fl == less_fl) && !cond->val_int())) + { + /* + It's the first predicate for this part or a predicate of the + following form that moves upper/lower bounds for max/min values: + - field BETWEEN const AND const + - field = const + - field {<|<=} const, when searching for MAX + - field {>|>=} const, when searching for MIN + */ + + if (is_null || (is_null_safe_eq && args[1]->is_null())) + { + /* + If we have a non-nullable index, we cannot use it, + since set_null will be ignored, and we will compare uninitialized data. + */ + if (!part->field->real_maybe_null()) + DBUG_RETURN(FALSE); + part->field->set_null(); + *key_ptr= (uchar) 1; + } + else + { + /* Update endpoints for MAX/MIN, see function comment. */ + Item *value= args[between && max_fl ? 2 : 1]; + value->save_in_field_no_warnings(part->field, 1); + if (part->null_bit) + *key_ptr++= (uchar) MY_TEST(part->field->is_null()); + part->field->get_key_image(key_ptr, part->length, Field::itRAW); + } + if (is_field_part) + { + if (between || eq_type) + { + *range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE); + *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN); + } + else + { + *range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE); + if (noeq_type) + *range_fl|= (max_fl ? NEAR_MAX : NEAR_MIN); + else + *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN); + } + } + } + else if (eq_type) + { + if ((!is_null && !cond->val_int()) || + (is_null && !MY_TEST(part->field->is_null()))) + DBUG_RETURN(FALSE); // Impossible test + } + else if (is_field_part) + *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE); + DBUG_RETURN(TRUE); +} + + +/** + Check whether we can get value for {max|min}(field) by using a key. + + If where-condition is not a conjunction of 0 or more conjuct the + function returns false, otherwise it checks whether there is an + index including field as its k-th component/part such that: + + -# for each previous component f_i there is one and only one conjunct + of the form: f_i= const_i or const_i= f_i or f_i is null + -# references to field occur only in conjucts of the form: + field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or + field BETWEEN const1 AND const2 + -# all references to the columns from the same table as column field + occur only in conjucts mentioned above. + -# each of k first components the index is not partial, i.e. is not + defined on a fixed length proper prefix of the field. + + If such an index exists the function through the ref parameter + returns the key value to find max/min for the field using the index, + the length of first (k-1) components of the key and flags saying + how to apply the key for the search max/min value. + (if we have a condition field = const, prefix_len contains the length + of the whole search key) + + @param[in] max_fl 0 for MIN(field) / 1 for MAX(field) + @param[in,out] ref Reference to the structure we store the key value + @param[in] field Field used inside MIN() / MAX() + @param[in] cond WHERE condition + @param[out] range_fl Bit flags for how to search if key is ok + @param[out] prefix_len Length of prefix for the search range + + @note + This function may set field->table->key_read to true, + which must be reset after index is used! + (This can only happen when function returns 1) + + @retval + 0 Index can not be used to optimize MIN(field)/MAX(field) + @retval + 1 Can use key to optimize MIN()/MAX(). + In this case ref, range_fl and prefix_len are updated +*/ + +static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref, + Field* field, COND *cond, + uint *range_fl, uint *prefix_len) +{ + if (!(field->flags & PART_KEY_FLAG)) + return FALSE; // Not key field + + DBUG_ENTER("find_key_for_maxmin"); + + TABLE *table= field->table; + uint idx= 0; + + KEY *keyinfo,*keyinfo_end; + for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->s->keys ; + keyinfo != keyinfo_end; + keyinfo++,idx++) + { + KEY_PART_INFO *part,*part_end; + key_part_map key_part_to_use= 0; + /* + Perform a check if index is not disabled by ALTER TABLE + or IGNORE INDEX. + */ + if (!table->keys_in_use_for_query.is_set(idx)) + continue; + uint jdx= 0; + *prefix_len= 0; + part_end= keyinfo->key_part+table->actual_n_key_parts(keyinfo); + for (part= keyinfo->key_part ; + part != part_end ; + part++, jdx++, key_part_to_use= (key_part_to_use << 1) | 1) + { + if (!(table->file->index_flags(idx, jdx, 0) & HA_READ_ORDER)) + DBUG_RETURN(FALSE); + + /* Check whether the index component is partial */ + Field *part_field= table->field[part->fieldnr-1]; + if ((part_field->flags & BLOB_FLAG) || + part->length < part_field->key_length()) + break; + + if (field->eq(part->field)) + { + ref->key= idx; + ref->key_length= 0; + ref->key_parts= 0; + key_part_map key_part_used= 0; + *range_fl= NO_MIN_RANGE | NO_MAX_RANGE; + if (matching_cond(max_fl, ref, keyinfo, part, cond, + &key_part_used, range_fl, prefix_len) && + !(key_part_to_use & ~key_part_used)) + { + if (!max_fl && key_part_used == key_part_to_use && part->null_bit) + { + /* + The query is on this form: + + SELECT MIN(key_part_k) + FROM t1 + WHERE key_part_1 = const and ... and key_part_k-1 = const + + If key_part_k is nullable, we want to find the first matching row + where key_part_k is not null. The key buffer is now {const, ..., + NULL}. This will be passed to the handler along with a flag + indicating open interval. If a tuple is read that does not match + these search criteria, an attempt will be made to read an exact + match for the key buffer. + */ + /* Set the first byte of key_part_k to 1, that means NULL */ + ref->key_buff[ref->key_length]= 1; + ref->key_length+= part->store_length; + ref->key_parts++; + DBUG_ASSERT(ref->key_parts == jdx+1); + *range_fl&= ~NO_MIN_RANGE; + *range_fl|= NEAR_MIN; // Open interval + } + /* + The following test is false when the key in the key tree is + converted (for example to upper case) + */ + if (field->part_of_key.is_set(idx)) + table->file->ha_start_keyread(idx); + DBUG_RETURN(TRUE); + } + } + } + } + DBUG_RETURN(FALSE); +} + + +/** + Check whether found key is in range specified by conditions. + + @param[in] max_fl 0 for MIN(field) / 1 for MAX(field) + @param[in] ref Reference to the key value and info + @param[in] field Field used the MIN/MAX expression + @param[in] cond WHERE condition + @param[in] range_fl Says whether there is a condition to to be checked + @param[in] prefix_len Length of the constant part of the key + + @retval + 0 ok + @retval + 1 WHERE was not true for the found row +*/ + +static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field, + COND *cond, uint range_fl, uint prefix_len) +{ + if (key_cmp_if_same(field->table, ref->key_buff, ref->key, prefix_len)) + return 1; + if (!cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE))) + return 0; + return maxmin_in_range(max_fl, field, cond); +} + + +/** + Check whether {MAX|MIN}(field) is in range specified by conditions. + + @param[in] max_fl 0 for MIN(field) / 1 for MAX(field) + @param[in] field Field used the MIN/MAX expression + @param[in] cond WHERE condition + + @retval + 0 ok + @retval + 1 WHERE was not true for the found row +*/ + +static int maxmin_in_range(bool max_fl, Field* field, COND *cond) +{ + /* If AND/OR condition */ + if (cond->type() == Item::COND_ITEM) + { + List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list()); + Item *item; + while ((item= li++)) + { + if (maxmin_in_range(max_fl, field, item)) + return 1; + } + return 0; + } + + if (cond->used_tables() != field->table->map) + return 0; + bool less_fl= 0; + switch (((Item_func*) cond)->functype()) { + case Item_func::BETWEEN: + return cond->val_int() == 0; // Return 1 if WHERE is false + case Item_func::LT_FUNC: + case Item_func::LE_FUNC: + less_fl= 1; + /* fall through */ + case Item_func::GT_FUNC: + case Item_func::GE_FUNC: + { + Item *item= ((Item_func*) cond)->arguments()[1]; + /* In case of 'const op item' we have to swap the operator */ + if (!item->const_item()) + less_fl= 1-less_fl; + /* + We only have to check the expression if we are using an expression like + SELECT MAX(b) FROM t1 WHERE a=const AND b>const + not for + SELECT MAX(b) FROM t1 WHERE a=const AND b<const + */ + if (max_fl != less_fl) + return cond->val_int() == 0; // Return 1 if WHERE is false + return 0; + } + default: + break; // Ignore + } + return 0; +} + |