/* Copyright (c) 2000, 2024, Oracle and/or its affiliates. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License, version 2.0, as published by the Free Software Foundation. This program is designed to work with certain software (including but not limited to OpenSSL) that is licensed under separate terms, as designated in a particular file or component or in included license documentation. The authors of MySQL hereby grant you an additional permission to link the program and your derivative works with the separately licensed software that they have either included with the program or referenced in the documentation. 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, version 2.0, 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-1301 USA */ #include #include #include #include "field_types.h" #include "memory_debugging.h" #include "mf_wcomp.h" #include "my_alloc.h" #include "my_base.h" #include "my_byteorder.h" #include "my_compiler.h" #include "my_dbug.h" #include "my_inttypes.h" #include "my_table_map.h" #include "mysql/strings/m_ctype.h" #include "mysql/udf_registration_types.h" #include "mysql_com.h" #include "mysqld_error.h" #include "sql-common/json_dom.h" #include "sql/current_thd.h" #include "sql/derror.h" #include "sql/field.h" #include "sql/field_common_properties.h" #include "sql/handler.h" #include "sql/item.h" #include "sql/item_cmpfunc.h" #include "sql/item_func.h" #include "sql/item_json_func.h" #include "sql/item_row.h" #include "sql/key.h" #include "sql/mem_root_array.h" #include "sql/opt_trace.h" #include "sql/opt_trace_context.h" #include "sql/query_options.h" #include "sql/range_optimizer/internal.h" #include "sql/range_optimizer/range_optimizer.h" #include "sql/range_optimizer/tree.h" #include "sql/sql_bitmap.h" #include "sql/sql_class.h" #include "sql/sql_const.h" #include "sql/sql_error.h" #include "sql/sql_lex.h" #include "sql/sql_list.h" #include "sql/sql_optimizer.h" #include "sql/system_variables.h" #include "sql/table.h" #include "sql_string.h" #include "template_utils.h" /* A null_sel_tree is used in get_func_mm_tree_from_in_predicate to pass as an argument to tree_or. It is used only to influence the return value from tree_or function. */ static MEM_ROOT null_root; static SEL_TREE null_sel_tree(SEL_TREE::IMPOSSIBLE, &null_root, 0); static uchar is_null_string[2] = {1, 0}; static SEL_TREE *get_mm_parts(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, Item_func *cond_func, Field *field, Item_func::Functype type, Item *value); static SEL_ROOT *get_mm_leaf(THD *thd, RANGE_OPT_PARAM *param, Item *cond_func, Field *field, KEY_PART *key_part, Item_func::Functype type, Item *value, bool *inexact); static SEL_TREE *get_full_func_mm_tree(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, table_map current_table, bool remove_jump_scans, Item *predicand, Item_func *op, Item *value, bool inv); static SEL_ROOT *sel_add(SEL_ROOT *key1, SEL_ROOT *key2); /** If EXPLAIN or if the --safe-updates option is enabled, add a warning that the index cannot be used for range access due to either type conversion or different collations on the field used for comparison @param thd Thread handle @param param RANGE_OPT_PARAM from test_quick_select @param key_num Key number @param field Field in the predicate */ static void warn_index_not_applicable(THD *thd, const RANGE_OPT_PARAM *param, const uint key_num, const Field *field) { if (param->using_real_indexes && (thd->lex->is_explain() || thd->variables.option_bits & OPTION_SAFE_UPDATES)) push_warning_printf(thd, Sql_condition::SL_WARNING, ER_WARN_INDEX_NOT_APPLICABLE, ER_THD(thd, ER_WARN_INDEX_NOT_APPLICABLE), "range", field->table->key_info[param->real_keynr[key_num]].name, field->field_name); } /* Build a SEL_TREE for <> or NOT BETWEEN predicate SYNOPSIS get_ne_mm_tree() param RANGE_OPT_PARAM from test_quick_select prev_tables See test_quick_select() read_tables See test_quick_select() remove_jump_scans See get_mm_tree() cond_func item for the predicate field field in the predicate lt_value constant that field should be smaller gt_value constant that field should be greaterr RETURN # Pointer to tree built tree 0 on error */ static SEL_TREE *get_ne_mm_tree(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, bool remove_jump_scans, Item_func *cond_func, Field *field, Item *lt_value, Item *gt_value) { SEL_TREE *tree = nullptr; if (param->has_errors()) return nullptr; tree = get_mm_parts(thd, param, prev_tables, read_tables, cond_func, field, Item_func::LT_FUNC, lt_value); if (tree) { tree = tree_or(param, remove_jump_scans, tree, get_mm_parts(thd, param, prev_tables, read_tables, cond_func, field, Item_func::GT_FUNC, gt_value)); } return tree; } /** Factory function to build a SEL_TREE from an @ @param thd Thread handle @param param Information on 'just about everything'. @param prev_tables See test_quick_select() @param read_tables See test_quick_select() @param remove_jump_scans See get_mm_tree() @param predicand The @ predicand, i.e. the left-hand side of the @ expression. @param op The 'in' operator itself. @param is_negated If true, the operator is NOT IN, otherwise IN. */ static SEL_TREE *get_func_mm_tree_from_in_predicate( THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, bool remove_jump_scans, Item *predicand, Item_func_in *op, bool is_negated) { if (param->has_errors()) return nullptr; // Populate array as we need to examine its values here if (op->m_const_array != nullptr && !op->m_populated) { op->populate_bisection(thd); } if (is_negated) { // We don't support row constructors (multiple columns on lhs) here. if (predicand->type() != Item::FIELD_ITEM) return nullptr; Field *field = down_cast(predicand)->field; if (op->m_const_array != nullptr && !op->m_const_array->is_row_result()) { /* We get here for conditions on the form "t.key NOT IN (c1, c2, ...)", where c{i} are constants. Our goal is to produce a SEL_TREE that represents intervals: ($MINm_const_array->m_used_size == 0 || op->m_const_array->m_used_size > NOT_IN_IGNORE_THRESHOLD) return nullptr; /* Create one Item_type constant object. We'll need it as get_mm_parts only accepts constant values wrapped in Item_Type objects. We create the Item on thd->mem_root which points to per-statement mem_root. */ Item_basic_constant *value_item = op->m_const_array->create_item(thd->mem_root); if (value_item == nullptr) return nullptr; /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval. */ uint i = 0; SEL_TREE *tree = nullptr; do { op->m_const_array->value_to_item(i, value_item); tree = get_mm_parts(thd, param, prev_tables, read_tables, op, field, Item_func::LT_FUNC, value_item); if (!tree) break; i++; } while (i < op->m_const_array->m_used_size && tree->type == SEL_TREE::IMPOSSIBLE); if (!tree || tree->type == SEL_TREE::IMPOSSIBLE) /* We get here in cases like "t.unsigned NOT IN (-1,-2,-3) */ return nullptr; SEL_TREE *tree2 = nullptr; Item_basic_constant *previous_range_value = op->m_const_array->create_item(thd->mem_root); for (; i < op->m_const_array->m_used_size; i++) { // Check if the value stored in the field for the previous range // is greater, lesser or equal to the actual value specified in the // query. Used further down to set the flags for the current range // correctly (as the max value for the previous range will become // the min value for the current range). op->m_const_array->value_to_item(i - 1, previous_range_value); int cmp_value = stored_field_cmp_to_item(thd, field, previous_range_value); if (op->m_const_array->compare_elems(i, i - 1)) { /* Get a SEL_TREE for "-inf < X < c_i" interval */ op->m_const_array->value_to_item(i, value_item); tree2 = get_mm_parts(thd, param, prev_tables, read_tables, op, field, Item_func::LT_FUNC, value_item); if (!tree2) { tree = nullptr; break; } /* Change all intervals to be "c_{i-1} < X < c_i" */ for (uint idx = 0; idx < param->keys; idx++) { SEL_ARG *last_val; if (tree->keys[idx] && tree2->keys[idx] && ((last_val = tree->keys[idx]->root->last()))) { SEL_ARG *new_interval = tree2->keys[idx]->root; new_interval->min_value = last_val->max_value; // We set the max value of the previous range as the beginning // for this range interval. However we need values higher than // this value: // For ex: If the range is "not in (1,2)" we first construct // X < 1 before this loop and add 1 < X < 2 in this loop and // follow it up with 2 < X below. // While fetching values for the second interval, we set // "NEAR_MIN" flag so that we fetch values higher than "1". // However, when the values specified are not compatible // with the field that is being compared to, they are rounded // off. // For the example above, if the range given was "not in (0.9, // 1.9)", range optimizer rounds of the values to (1,2). In such // a case, setting the flag to "NEAR_MIN" is not right. Because // we need values higher than "0.9" not "1". We check this // before we set the flag below. if (cmp_value <= 0) new_interval->min_flag = NEAR_MIN; else new_interval->min_flag = 0; /* If the interval is over a partial keypart, the interval must be "c_{i-1} <= X < c_i" instead of "c_{i-1} < X < c_i". Reason: Consider a table with a column "my_col VARCHAR(3)", and an index with definition "INDEX my_idx my_col(1)". If the table contains rows with my_col values "f" and "foo", the index will not distinguish the two rows. Note that tree_or() below will effectively merge this range with the range created for c_{i-1} and we'll eventually end up with only one range: "NULL < X". Partitioning indexes are never partial. */ if (param->using_real_indexes) { const KEY key = param->table->key_info[param->real_keynr[idx]]; const KEY_PART_INFO *kpi = key.key_part + new_interval->part; if (kpi->key_part_flag & HA_PART_KEY_SEG) new_interval->min_flag = 0; } } } /* The following doesn't try to allocate memory so no need to check for NULL. */ tree = tree_or(param, remove_jump_scans, tree, tree2); } } if (tree && tree->type != SEL_TREE::IMPOSSIBLE) { /* Get the SEL_TREE for the last "c_last < X < +inf" interval (value_item contains c_last already) */ tree2 = get_mm_parts(thd, param, prev_tables, read_tables, op, field, Item_func::GT_FUNC, value_item); tree = tree_or(param, remove_jump_scans, tree, tree2); } return tree; } else { SEL_TREE *tree = get_ne_mm_tree(thd, param, prev_tables, read_tables, remove_jump_scans, op, field, op->arguments()[1], op->arguments()[1]); if (tree) { Item **arg, **end; for (arg = op->arguments() + 2, end = arg + op->argument_count() - 2; arg < end; arg++) { tree = tree_and( param, tree, get_ne_mm_tree(thd, param, prev_tables, read_tables, remove_jump_scans, op, field, *arg, *arg)); } } return tree; } return nullptr; } // The expression is IN, not negated. if (predicand->type() == Item::FIELD_ITEM) { // The expression is () IN (...) Field *field = down_cast(predicand)->field; SEL_TREE *tree = get_mm_parts(thd, param, prev_tables, read_tables, op, field, Item_func::EQ_FUNC, op->arguments()[1]); if (tree) { Item **arg, **end; for (arg = op->arguments() + 2, end = arg + op->argument_count() - 2; arg < end; arg++) { tree = tree_or(param, remove_jump_scans, tree, get_mm_parts(thd, param, prev_tables, read_tables, op, field, Item_func::EQ_FUNC, *arg)); } } return tree; } if (predicand->type() == Item::ROW_ITEM) { /* The expression is (,...) IN (...) We iterate over the rows on the rhs of the in predicate, building an OR tree of ANDs, a.k.a. a DNF expression out of this. E.g: (col1, col2) IN ((const1, const2), (const3, const4)) becomes (col1 = const1 AND col2 = const2) OR (col1 = const3 AND col2 = const4) */ SEL_TREE *or_tree = &null_sel_tree; Item_row *row_predicand = down_cast(predicand); // Iterate over the rows on the rhs of the in predicate, building an OR. for (uint i = 1; i < op->argument_count(); ++i) { /* We only support row value expressions. Some optimizations rewrite the Item tree, and we don't handle that. */ Item *in_list_item = op->arguments()[i]; if (in_list_item->type() != Item::ROW_ITEM) return nullptr; Item_row *row = static_cast(in_list_item); // Iterate over the columns, building an AND tree. SEL_TREE *and_tree = nullptr; for (uint j = 0; j < row_predicand->cols(); ++j) { Item *item = row_predicand->element_index(j); // We only support columns in the row on the lhs of the in predicate. if (item->type() != Item::FIELD_ITEM) return nullptr; Field *field = static_cast(item)->field; Item *value = row->element_index(j); SEL_TREE *and_expr = get_mm_parts(thd, param, prev_tables, read_tables, op, field, Item_func::EQ_FUNC, value); and_tree = tree_and(param, and_tree, and_expr); /* Short-circuit evaluation: If and_expr is NULL then no key part in this disjunct can be used as a search key. Or in other words the condition is always true. Hence the whole disjunction is always true. */ if (and_tree == nullptr) return nullptr; } or_tree = tree_or(param, remove_jump_scans, or_tree, and_tree); } return or_tree; } return nullptr; } /** Factory function to build a SEL_TREE from a JSON_OVERLAPS or JSON_CONTAINS functions \verbatim This function builds SEL_TREE out of JSON_OEVRLAPS() of form: JSON_OVERLAPS(typed_array_field, "[,...,]") JSON_OVERLAPS("[,...,]", typed_array_field) JSON_CONTAINS(typed_array_field, "[,...,]") where typed_array_field is a field which has multi-valued index defined on it each value in the array is coercible to the array's type These conditions are pre-checked in substitute_gc(). \endverbatim @param thd Thread handle @param param Information on 'just about everything'. @param prev_tables See test_quick_select() @param read_tables See test_quick_select() @param remove_jump_scans See get_mm_tree() @param predicand the typed array JSON_CONTAIN's argument @param op The 'JSON_OVERLAPS' operator itself. @returns non-NULL constructed SEL_TREE NULL in case of any error */ static SEL_TREE *get_func_mm_tree_from_json_overlaps_contains( THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, bool remove_jump_scans, Item *predicand, Item_func *op) { if (param->has_errors()) return nullptr; // The expression is JSON_OVERLAPS(,), or // The expression is JSON_OVERLAPS(, ), or // The expression is JSON_CONTAINS(, ) if (predicand->type() == Item::FIELD_ITEM && predicand->returns_array()) { Json_wrapper wr, elt; String str; uint values; if (op->functype() == Item_func::JSON_OVERLAPS) { // If the predicand is the 1st arg, then the values arg is 2nd. values = (predicand == op->arguments()[0]) ? 1 : 0; } else { assert(op->functype() == Item_func::JSON_CONTAINS); values = 1; } if (get_json_wrapper(op->arguments(), values, &str, op->func_name(), &wr)) return nullptr; /* purecov: inspected */ // Should be pre-checked already assert(!(op->arguments()[values])->null_value && wr.type() != enum_json_type::J_OBJECT && wr.type() != enum_json_type::J_ERROR); if (wr.length() == 0) return nullptr; Field_typed_array *field = down_cast( down_cast(predicand)->field); if (wr.type() == enum_json_type::J_ARRAY) wr.remove_duplicates( field->type() == MYSQL_TYPE_VARCHAR ? field->charset() : nullptr); size_t i = 0; const size_t len = (wr.type() == enum_json_type::J_ARRAY) ? wr.length() : 1; // Skip leading JSON null values as they can't be indexed and thus doesn't // exist in index. while (i < len && wr[i].type() == enum_json_type::J_NULL) ++i; // No non-null values were found. if (i == len) return nullptr; // Fake const table for get_mm_parts, as we're using constants from JSON // array const bool save_const = field->table->const_table; field->table->const_table = true; field->set_notnull(); // Get the SEL_ARG tree for the first non-null element.. elt = wr[i++]; field->coerce_json_value(&elt, true, nullptr); SEL_TREE *tree = get_mm_parts(thd, param, prev_tables, read_tables, op, field, Item_func::EQ_FUNC, down_cast(predicand)); // .. and OR with others if (tree) { for (; i < len; i++) { elt = wr[i]; field->coerce_json_value(&elt, true, nullptr); tree = tree_or(param, remove_jump_scans, tree, get_mm_parts(thd, param, prev_tables, read_tables, op, field, Item_func::EQ_FUNC, down_cast(predicand))); if (!tree) // OOM break; } } field->table->const_table = save_const; return tree; } return nullptr; } /** Build a SEL_TREE for a simple predicate. @param param RANGE_OPT_PARAM from test_quick_select @param remove_jump_scans See get_mm_tree() @param predicand field in the predicate @param cond_func item for the predicate @param value constant in the predicate @param inv true <> NOT cond_func is considered (makes sense only when cond_func is BETWEEN or IN) @return Pointer to the built tree. @todo Remove the appaling hack that 'value' can be a 1 cast to an Item*. */ static SEL_TREE *get_func_mm_tree(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, bool remove_jump_scans, Item *predicand, Item_func *cond_func, Item *value, bool inv) { SEL_TREE *tree = nullptr; DBUG_TRACE; if (param->has_errors()) return nullptr; switch (cond_func->functype()) { case Item_func::XOR_FUNC: return nullptr; // Always true (don't use range access on XOR). break; // See WL#5800 case Item_func::NE_FUNC: if (predicand->type() == Item::FIELD_ITEM) { Field *field = down_cast(predicand)->field; tree = get_ne_mm_tree(thd, param, prev_tables, read_tables, remove_jump_scans, cond_func, field, value, value); } break; case Item_func::BETWEEN: if (predicand->type() == Item::FIELD_ITEM) { Field *field = down_cast(predicand)->field; if (!value) { if (inv) { tree = get_ne_mm_tree(thd, param, prev_tables, read_tables, remove_jump_scans, cond_func, field, cond_func->arguments()[1], cond_func->arguments()[2]); } else { tree = get_mm_parts(thd, param, prev_tables, read_tables, cond_func, field, Item_func::GE_FUNC, cond_func->arguments()[1]); if (tree) { tree = tree_and(param, tree, get_mm_parts(thd, param, prev_tables, read_tables, cond_func, field, Item_func::LE_FUNC, cond_func->arguments()[2])); } } } else tree = get_mm_parts( thd, param, prev_tables, read_tables, cond_func, field, (inv ? (value == reinterpret_cast(1) ? Item_func::GT_FUNC : Item_func::LT_FUNC) : (value == reinterpret_cast(1) ? Item_func::LE_FUNC : Item_func::GE_FUNC)), cond_func->arguments()[0]); } break; case Item_func::IN_FUNC: { Item_func_in *in_pred = down_cast(cond_func); tree = get_func_mm_tree_from_in_predicate(thd, param, prev_tables, read_tables, remove_jump_scans, predicand, in_pred, inv); } break; case Item_func::JSON_CONTAINS: case Item_func::JSON_OVERLAPS: { tree = get_func_mm_tree_from_json_overlaps_contains( thd, param, prev_tables, read_tables, remove_jump_scans, predicand, cond_func); } break; case Item_func::MEMBER_OF_FUNC: if (predicand->type() == Item::FIELD_ITEM && predicand->returns_array()) { Field_typed_array *field = down_cast( down_cast(predicand)->field); Item *arg = cond_func->arguments()[0]; Json_wrapper wr; if (arg->val_json(&wr)) { break; } assert(!arg->null_value && wr.type() != enum_json_type::J_ERROR); if (wr.type() == enum_json_type::J_NULL) { break; } // Fake const table for get_mm_parts(), as we are using constants from // JSON array const bool save_const = field->table->const_table; field->table->const_table = true; field->set_notnull(); field->coerce_json_value(&wr, true, nullptr); tree = get_mm_parts(thd, param, prev_tables, read_tables, cond_func, field, Item_func::EQ_FUNC, predicand); field->table->const_table = save_const; } break; default: if (predicand->type() == Item::FIELD_ITEM) { Field *field = down_cast(predicand)->field; /* Here the function for the following predicates are processed: <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL and GIS functions. If the predicate is of the form (value op field) it is handled as the equivalent predicate (field rev_op value), e.g. 2 <= a is handled as a >= 2. */ Item_func::Functype func_type = (value != cond_func->arguments()[0]) ? cond_func->functype() : ((Item_bool_func2 *)cond_func)->rev_functype(); tree = get_mm_parts(thd, param, prev_tables, read_tables, cond_func, field, func_type, value); } } return tree; } /* Build conjunction of all SEL_TREEs for a simple predicate applying equalities SYNOPSIS get_full_func_mm_tree() param RANGE_OPT_PARAM from test_quick_select prev_tables See test_quick_select() read_tables See test_quick_select() remove_jump_scans See get_mm_tree() predicand column or row constructor in the predicate's left-hand side. op Item for the predicate operator value constant in the predicate (or a field already read from a table in the case of dynamic range access) For BETWEEN it contains the number of the field argument. inv If true, the predicate is negated, e.g. NOT IN. (makes sense only when cond_func is BETWEEN or IN) DESCRIPTION For a simple SARGable predicate of the form (f op c), where f is a field and c is a constant, the function builds a conjunction of all SEL_TREES that can be obtained by the substitution of f for all different fields equal to f. NOTES If the WHERE condition contains a predicate (fi op c), then not only SELL_TREE for this predicate is built, but the trees for the results of substitution of fi for each fj belonging to the same multiple equality as fi are built as well. E.g. for WHERE t1.a=t2.a AND t2.a > 10 a SEL_TREE for t2.a > 10 will be built for quick select from t2 and a SEL_TREE for t1.a > 10 will be built for quick select from t1. A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated in a similar way: we build a conjunction of trees for the results of all substitutions of fi for equal fj. Yet a predicate of the form (c BETWEEN f1i AND f2i) is processed differently. It is considered as a conjunction of two SARGable predicates (f1i <= c) and (f2i <=c) and the function get_full_func_mm_tree is called for each of them separately producing trees for AND j (f1j <=c ) and AND j (f2j <= c) After this these two trees are united in one conjunctive tree. It's easy to see that the same tree is obtained for AND j,k (f1j <=c AND f2k<=c) which is equivalent to AND j,k (c BETWEEN f1j AND f2k). The validity of the processing of the predicate (c NOT BETWEEN f1i AND f2i) which equivalent to (f1i > c OR f2i < c) is not so obvious. Here the function get_full_func_mm_tree is called for (f1i > c) and (f2i < c) producing trees for AND j (f1j > c) and AND j (f2j < c). Then this two trees are united in one OR-tree. The expression (AND j (f1j > c) OR AND j (f2j < c) is equivalent to the expression AND j,k (f1j > c OR f2k < c) which is just a translation of AND j,k (c NOT BETWEEN f1j AND f2k) In the cases when one of the items f1, f2 is a constant c1 we do not create a tree for it at all. It works for BETWEEN predicates but does not work for NOT BETWEEN predicates as we have to evaluate the expression with it. If it is true then the other tree can be completely ignored. We do not do it now and no trees are built in these cases for NOT BETWEEN predicates. As to IN predicates only ones of the form (f IN (c1,...,cn)), where f1 is a field and c1,...,cn are constant, are considered as SARGable. We never try to narrow the index scan using predicates of the form (c IN (c1,...,f,...,cn)). RETURN Pointer to the tree representing the built conjunction of SEL_TREEs */ static SEL_TREE *get_full_func_mm_tree(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, table_map current_table, bool remove_jump_scans, Item *predicand, Item_func *op, Item *value, bool inv) { SEL_TREE *tree = nullptr; SEL_TREE *ftree = nullptr; const table_map param_comp = ~(prev_tables | read_tables | current_table); DBUG_TRACE; if (param->has_errors()) return nullptr; /* Here we compute a set of tables that we consider as constants suppliers during execution of the SEL_TREE that we produce below. */ table_map ref_tables = 0; for (uint i = 0; i < op->arg_count; i++) { Item *arg = op->arguments()[i]->real_item(); if (arg != predicand) ref_tables |= arg->used_tables(); } if (predicand->type() == Item::FIELD_ITEM) { Item_field *item_field = static_cast(predicand); Field *field = item_field->field; if (!((ref_tables | item_field->table_ref->map()) & param_comp)) ftree = get_func_mm_tree(thd, param, prev_tables, read_tables, remove_jump_scans, predicand, op, value, inv); Item_equal *item_equal = item_field->multi_equality(); if (item_equal != nullptr) { for (Item_field &item : item_equal->get_fields()) { Field *f = item.field; if (!field->eq(f) && !((ref_tables | item.table_ref->map()) & param_comp)) { tree = get_func_mm_tree(thd, param, prev_tables, read_tables, remove_jump_scans, &item, op, value, inv); ftree = !ftree ? tree : tree_and(param, ftree, tree); } } } } else if (predicand->type() == Item::ROW_ITEM) { ftree = get_func_mm_tree(thd, param, prev_tables, read_tables, remove_jump_scans, predicand, op, value, inv); return ftree; } return ftree; } /** The Range Analysis Module, which finds range access alternatives applicable to single or multi-index (UNION) access. The function does not calculate or care about the cost of the different alternatives. get_mm_tree() employs a relaxed boolean algebra where the solution may be bigger than what the rules of boolean algebra accept. In other words, get_mm_tree() may return range access plans that will read more rows than the input conditions dictate. In it's simplest form, consider a condition on two fields indexed by two different indexes: "WHERE fld1 > 'x' AND fld2 > 'y'" In this case, there are two single-index range access alternatives. No matter which access path is chosen, rows that are not in the result set may be read. In the case above, get_mm_tree() will create range access alternatives for both indexes, so boolean algebra is still correct. In other cases, however, the conditions are too complex to be used without relaxing the rules. This typically happens when ORing a conjunction to a multi-index disjunctions (@see e.g. imerge_list_or_tree()). When this happens, the range optimizer may choose to ignore conjunctions (any condition connected with AND). The effect of this is that the result includes a "bigger" solution than necessary. This is OK since all conditions will be used as filters after row retrieval. @see SEL_TREE::keys and SEL_TREE::merges for details of how single and multi-index range access alternatives are stored. remove_jump_scans: Aggressively remove "scans" that do not have conditions on first keyparts. Such scans are usable when doing partition pruning but not regular range optimization. A return value of nullptr from get_mm_tree() means that this condition could not be represented by a range. Normally, this means that the best thing to do is to keep that condition entirely out of the range optimization, since ANDing it with other conditions (in tree_and()) would make the entire tree inexact and no predicates subsumable (see SEL_TREE::inexact). However, the old join optimizer does not care, and always just gives in the entire condition (with different parts ANDed together) in one go, since it never subsumes anything anyway. */ SEL_TREE *get_mm_tree(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, table_map current_table, bool remove_jump_scans, Item *cond) { SEL_TREE *ftree = nullptr; bool inv = false; DBUG_TRACE; if (param->has_errors()) return nullptr; if (cond->type() == Item::COND_ITEM) { Item_func::Functype functype = down_cast(cond)->functype(); SEL_TREE *tree = nullptr; bool first = true; for (Item &item : *down_cast(cond)->argument_list()) { SEL_TREE *new_tree = get_mm_tree(thd, param, prev_tables, read_tables, current_table, remove_jump_scans, &item); if (param->has_errors()) return nullptr; if (first) { tree = new_tree; first = false; continue; } if (functype == Item_func::COND_AND_FUNC) { tree = tree_and(param, tree, new_tree); dbug_print_tree("after_and", tree, param); if (tree && tree->type == SEL_TREE::IMPOSSIBLE) break; } else { // OR. tree = tree_or(param, remove_jump_scans, tree, new_tree); dbug_print_tree("after_or", tree, param); if (tree == nullptr || tree->type == SEL_TREE::ALWAYS) break; } } dbug_print_tree("tree_returned", tree, param); return tree; } if (cond->const_item() && !cond->cost().IsExpensive()) { const SEL_TREE::Type type = cond->val_int() ? SEL_TREE::ALWAYS : SEL_TREE::IMPOSSIBLE; SEL_TREE *tree = new (param->temp_mem_root) SEL_TREE(type, param->temp_mem_root, param->keys); if (param->has_errors()) return nullptr; dbug_print_tree("tree_returned", tree, param); return tree; } // This used to be a guard against predicates like “WHERE x;”. But these are // now always rewritten to “x <> 0”, so it does not trigger there. // However, it is still relevant for subselects. if (cond->type() != Item::FUNC_ITEM) { return nullptr; } Item_func *cond_func = (Item_func *)cond; if (cond_func->functype() == Item_func::BETWEEN || cond_func->functype() == Item_func::IN_FUNC) inv = ((Item_func_opt_neg *)cond_func)->negated; else { Item_func::optimize_type opt_type = cond_func->select_optimize(thd); if (opt_type == Item_func::OPTIMIZE_NONE) return nullptr; } /* Notice that all fields that are outer references are const during the execution and should not be considered for range analysis like fields coming from the local query block are. */ switch (cond_func->functype()) { case Item_func::BETWEEN: { Item *const arg_left = cond_func->arguments()[0]; if (!arg_left->is_outer_reference() && arg_left->real_item()->type() == Item::FIELD_ITEM) { Item_field *field_item = down_cast(arg_left->real_item()); ftree = get_full_func_mm_tree(thd, param, prev_tables, read_tables, current_table, remove_jump_scans, field_item, cond_func, nullptr, inv); } /* Concerning the code below see the NOTES section in the comments for the function get_full_func_mm_tree() */ SEL_TREE *tree = nullptr; for (uint i = 1; i < cond_func->arg_count; i++) { Item *const arg = cond_func->arguments()[i]; if (!arg->is_outer_reference() && arg->real_item()->type() == Item::FIELD_ITEM) { Item_field *field_item = down_cast(arg->real_item()); SEL_TREE *tmp = get_full_func_mm_tree( thd, param, prev_tables, read_tables, current_table, remove_jump_scans, field_item, cond_func, reinterpret_cast(i), inv); if (inv) { tree = !tree ? tmp : tree_or(param, remove_jump_scans, tree, tmp); if (tree == nullptr) break; } else tree = tree_and(param, tree, tmp); } else if (inv) { tree = nullptr; break; } } ftree = tree_and(param, ftree, tree); break; } // end case Item_func::BETWEEN case Item_func::JSON_CONTAINS: case Item_func::JSON_OVERLAPS: case Item_func::MEMBER_OF_FUNC: case Item_func::IN_FUNC: { Item *predicand = cond_func->key_item(); if (!predicand) return nullptr; predicand = predicand->real_item(); if (predicand->type() != Item::FIELD_ITEM && predicand->type() != Item::ROW_ITEM) return nullptr; ftree = get_full_func_mm_tree(thd, param, prev_tables, read_tables, current_table, remove_jump_scans, predicand, cond_func, nullptr, inv); break; } // end case Item_func::IN_FUNC case Item_func::MULT_EQUAL_FUNC: { Item_equal *item_equal = down_cast(cond); Item *value = item_equal->const_arg(); if (value == nullptr) return nullptr; table_map ref_tables = value->used_tables(); for (Item_field &field_item : item_equal->get_fields()) { Field *field = field_item.field; table_map param_comp = ~(prev_tables | read_tables | current_table); if (!((ref_tables | field_item.table_ref->map()) & param_comp)) { SEL_TREE *tree = get_mm_parts(thd, param, prev_tables, read_tables, item_equal, field, Item_func::EQ_FUNC, value); ftree = !ftree ? tree : tree_and(param, ftree, tree); } } dbug_print_tree("tree_returned", ftree, param); return ftree; } // end case Item_func::MULT_EQUAL_FUNC default: { Item *const arg_left = cond_func->arguments()[0]; assert(!ftree); if (!arg_left->is_outer_reference() && arg_left->real_item()->type() == Item::FIELD_ITEM) { Item_field *field_item = down_cast(arg_left->real_item()); Item *value = cond_func->arg_count > 1 ? cond_func->arguments()[1] : nullptr; ftree = get_full_func_mm_tree(thd, param, prev_tables, read_tables, current_table, remove_jump_scans, field_item, cond_func, value, inv); } /* Even if get_full_func_mm_tree() was executed above and did not return a range predicate it may still be possible to create one by reversing the order of the operands. Note that this only applies to predicates where both operands are fields. Example: A query of the form WHERE t1.a OP t2.b In this case, arguments()[0] == t1.a and arguments()[1] == t2.b. When creating range predicates for t2, get_full_func_mm_tree() above will return NULL because 'field' belongs to t1 and only predicates that applies to t2 are of interest. In this case a call to get_full_func_mm_tree() with reversed operands (see below) may succeed. */ Item *arg_right; if (!ftree && cond_func->have_rev_func() && (arg_right = cond_func->arguments()[1]) && !arg_right->is_outer_reference() && arg_right->real_item()->type() == Item::FIELD_ITEM) { Item_field *field_item = down_cast(arg_right->real_item()); Item *value = arg_left; ftree = get_full_func_mm_tree(thd, param, prev_tables, read_tables, current_table, remove_jump_scans, field_item, cond_func, value, inv); } } // end case default } // end switch dbug_print_tree("tree_returned", ftree, param); return ftree; } /** Test whether a comparison operator is a spatial comparison operator, i.e. Item_func::SP_*. Used to check if range access using operator 'op_type' is applicable for a non-spatial index. @param op_type The comparison operator. @return true if 'op_type' is a spatial comparison operator, false otherwise. */ static bool is_spatial_operator(Item_func::Functype op_type) { switch (op_type) { case Item_func::SP_EQUALS_FUNC: case Item_func::SP_DISJOINT_FUNC: case Item_func::SP_DISTANCE_FUNC: case Item_func::SP_INTERSECTS_FUNC: case Item_func::SP_TOUCHES_FUNC: case Item_func::SP_CROSSES_FUNC: case Item_func::SP_WITHIN_FUNC: case Item_func::SP_CONTAINS_FUNC: case Item_func::SP_COVEREDBY_FUNC: case Item_func::SP_COVERS_FUNC: case Item_func::SP_OVERLAPS_FUNC: case Item_func::SP_STARTPOINT: case Item_func::SP_ENDPOINT: case Item_func::SP_EXTERIORRING: case Item_func::SP_POINTN: case Item_func::SP_GEOMETRYN: case Item_func::SP_INTERIORRINGN: return true; default: return false; } } static SEL_TREE *get_mm_parts(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables, table_map read_tables, Item_func *cond_func, Field *field, Item_func::Functype type, Item *value) { DBUG_TRACE; if (param->has_errors()) return nullptr; if (field->table != param->table) return nullptr; KEY_PART *key_part = param->key_parts; KEY_PART *end = param->key_parts_end; SEL_TREE *tree = nullptr; if (value && value->used_tables() & ~(prev_tables | read_tables)) return nullptr; for (; key_part != end; key_part++) { if (field->eq(key_part->field)) { /* Cannot do range access for spatial operators when a non-spatial index is used. */ if (key_part->image_type != Field::itMBR && is_spatial_operator(cond_func->functype())) continue; SEL_ROOT *sel_root = nullptr; if (!tree && !(tree = new (param->temp_mem_root) SEL_TREE(param->temp_mem_root, param->keys))) return nullptr; // OOM if (!value || !(value->used_tables() & ~read_tables)) { sel_root = get_mm_leaf(thd, param, cond_func, key_part->field, key_part, type, value, &tree->inexact); if (!sel_root) continue; if (sel_root->type == SEL_ROOT::Type::IMPOSSIBLE) { tree->type = SEL_TREE::IMPOSSIBLE; return tree; } } else { /* The index may not be used by dynamic range access unless 'field' and 'value' are comparable. */ if (!comparable_in_index(cond_func, key_part->field, key_part->image_type, type, value)) { warn_index_not_applicable(thd, param, key_part->key, field); return nullptr; } if (!(sel_root = new (param->temp_mem_root) SEL_ROOT(param->temp_mem_root, SEL_ROOT::Type::MAYBE_KEY))) return nullptr; // OOM } sel_root->root->part = (uchar)key_part->part; tree->set_key(key_part->key, sel_add(tree->release_key(key_part->key), sel_root)); tree->keys_map.set_bit(key_part->key); // A range constructed for a multi-valued index is never exact. // So it needs the filter to be placed on top of the range access. if (param->using_real_indexes) { int index = param->real_keynr[key_part->key]; if (param->table->key_info[index].flags & HA_MULTI_VALUED_KEY) { tree->inexact = true; } } } } if (tree && tree->merges.is_empty() && tree->keys_map.is_clear_all()) tree = nullptr; return tree; } /** Saves 'value' in 'field' and handles potential type conversion problems. @param [out] tree The SEL_ROOT leaf under construction. If an always false predicate is found it is modified to point to a SEL_ROOT with type == SEL_ROOT::Type::IMPOSSIBLE. @param value The Item that contains a value that shall be stored in 'field'. @param comp_op Comparison operator: >, >=, <=> etc. @param field The field that 'value' is stored into. @param [out] impossible_cond_cause Set to a descriptive string if an impossible condition is found. @param memroot Memroot for creation of new SEL_ARG. @param query_block Query block the field is part of @param inexact Set to true on lossy conversion @retval false if saving went fine and it makes sense to continue optimizing for this predicate. @retval true if always true/false predicate was found, in which case 'tree' has been modified to reflect this: NULL pointer if always true, SEL_ARG with type IMPOSSIBLE if always false. */ static bool save_value_and_handle_conversion( SEL_ROOT **tree, Item *value, const Item_func::Functype comp_op, Field *field, const char **impossible_cond_cause, MEM_ROOT *memroot, Query_block *query_block, bool *inexact) { // A SEL_ARG should not have been created for this predicate yet. assert(*tree == nullptr); THD *const thd = current_thd; if (!(value->const_item() || thd->lex->is_query_tables_locked())) { /* We cannot evaluate the value yet (i.e. required tables are not yet locked.) This is the case of prune_partitions() called during Query_block::prepare(). */ return true; } /* Don't evaluate subqueries during optimization if they are disabled. This function can be called during execution when doing dynamic range access, and we only want to disable subquery evaluation during optimization, so check if we're in the optimization phase by calling Query_expression::is_optimized(). */ if (!query_block->master_query_expression()->is_optimized() && !evaluate_during_optimization(value, query_block)) return true; // For comparison purposes allow invalid dates like 2000-01-32 const sql_mode_t orig_sql_mode = thd->variables.sql_mode; thd->variables.sql_mode |= MODE_INVALID_DATES; /* We want to change "field > value" to "field OP V" where: * V is what is in "field" after we stored "value" in it via save_in_field_no_warning() (such store operation may have done rounding...) * OP is > or >=, depending on what's correct. For example, if c is an INT column, "c > 2.9" is changed to "c OP 3" where OP is ">=" (">" would not be correct, as 3 > 2.9, a comparison done with stored_field_cmp_to_item()). And "c > 3.1" is changed to "c OP 3" where OP is ">" (3 < 3.1...). */ // Note that value may be a stored function call, executed here. const type_conversion_status err = value->save_in_field_no_warnings(field, true); thd->variables.sql_mode = orig_sql_mode; switch (err) { case TYPE_OK: return false; case TYPE_NOTE_TRUNCATED: // Insignificant truncation (trailing zero/space). Use it as an inexact // range predicate. *inexact = true; return false; case TYPE_WARN_TRUNCATED: // Truncation of possibly significant parts. We may still be able to use // it as a range predicate, but we need a filter to make sure we don't // return too many rows. *inexact = true; // Use the truncated value in the range predicate, unless it's a string // with a non-binary collation with a non-trivial strnxfrm function. For // example, if c is a VARCHAR(1) column with the utf8mb4_0900_ai_ci // collation, c <= 'ss' should match the value 'ß', but if we truncate it // to c <= 's' to fit in the column type, it will not match 'ß'. For such // predicates, we assume the predicate is always true, and let a filter // decide the outcome. return is_string_type(field->type()) && !my_binary_compare(field->charset()) && use_strnxfrm(field->charset()); case TYPE_WARN_INVALID_STRING: /* An invalid string does not produce any rows when used with equality operator. */ if (comp_op == Item_func::EQUAL_FUNC || comp_op == Item_func::EQ_FUNC) { *impossible_cond_cause = "invalid_characters_in_string"; goto impossible_cond; } /* For other operations on invalid strings, we assume that the range predicate is always true and let a filter decide the outcome. */ *inexact = true; return true; case TYPE_ERR_BAD_VALUE: /* In the case of incompatible values, MySQL's SQL dialect has some strange interpretations. For example, "int_col > 'foo'" is interpreted as "int_col > 0" instead of always false. Because of this, we assume that the range predicate is always true instead of always false and let a filter decide the outcome. */ *inexact = true; return true; case TYPE_ERR_NULL_CONSTRAINT_VIOLATION: // Checking NULL value on a field that cannot contain NULL. *impossible_cond_cause = "null_field_in_non_null_column"; goto impossible_cond; case TYPE_WARN_OUT_OF_RANGE: /* value to store was either higher than field::max_value or lower than field::min_value. The field's max/min value has been stored instead. */ if (comp_op == Item_func::EQUAL_FUNC || comp_op == Item_func::EQ_FUNC) { /* Independent of data type, "out_of_range_value =/<=> field" is always false. */ *impossible_cond_cause = "value_out_of_range"; goto impossible_cond; } // If the field is numeric, we can interpret the out of range value. if ((field->type() != FIELD_TYPE_BIT) && (field->result_type() == REAL_RESULT || field->result_type() == INT_RESULT || field->result_type() == DECIMAL_RESULT)) { /* value to store was higher than field::max_value if a) field has a value greater than 0, or b) if field is unsigned and has a negative value (which, when cast to unsigned, means some value higher than LLONG_MAX). */ if ((field->val_int() > 0) || // a) (field->is_unsigned() && field->val_int() < 0)) // b) { if (comp_op == Item_func::LT_FUNC || comp_op == Item_func::LE_FUNC) { /* '<' or '<=' compared to a value higher than the field can store is always true. */ return true; } if (comp_op == Item_func::GT_FUNC || comp_op == Item_func::GE_FUNC) { /* '>' or '>=' compared to a value higher than the field can store is always false. */ *impossible_cond_cause = "value_out_of_range"; goto impossible_cond; } } else // value is lower than field::min_value { if (comp_op == Item_func::GT_FUNC || comp_op == Item_func::GE_FUNC) { /* '>' or '>=' compared to a value lower than the field can store is always true. */ return true; } if (comp_op == Item_func::LT_FUNC || comp_op == Item_func::LE_FUNC) { /* '<' or '=' compared to a value lower than the field can store is always false. */ *impossible_cond_cause = "value_out_of_range"; goto impossible_cond; } } } /* Value is out of range on a datatype where it can't be decided if it was underflow or overflow. It is therefore not possible to determine whether or not the condition is impossible or always true and we have to assume always true. */ return true; case TYPE_NOTE_TIME_TRUNCATED: if (field->type() == FIELD_TYPE_DATE && (comp_op == Item_func::GT_FUNC || comp_op == Item_func::GE_FUNC || comp_op == Item_func::LT_FUNC || comp_op == Item_func::LE_FUNC)) { /* We were saving DATETIME into a DATE column, the conversion went ok but a non-zero time part was cut off. In MySQL's SQL dialect, DATE and DATETIME are compared as datetime values. Index over a DATE column uses DATE comparison. Changing from one comparison to the other is possible: datetime(date_col)< '2007-12-10 12:34:55' -> date_col<='2007-12-10' datetime(date_col)<='2007-12-10 12:34:55' -> date_col<='2007-12-10' datetime(date_col)> '2007-12-10 12:34:55' -> date_col>='2007-12-10' datetime(date_col)>='2007-12-10 12:34:55' -> date_col>='2007-12-10' but we'll need to convert '>' to '>=' and '<' to '<='. This will be done together with other types at the end of get_mm_leaf() (grep for stored_field_cmp_to_item) */ return false; } if (comp_op == Item_func::EQ_FUNC || comp_op == Item_func::EQUAL_FUNC) { // Equality comparison is always false when time info has been // truncated. goto impossible_cond; } return true; case TYPE_ERR_OOM: return true; /* No default here to avoid adding new conversion status codes that are unhandled in this function. */ } assert(false); // Should never get here. impossible_cond: *tree = new (memroot) SEL_ROOT(memroot, SEL_ROOT::Type::IMPOSSIBLE); return true; } static SEL_ROOT *get_mm_leaf(THD *thd, RANGE_OPT_PARAM *param, Item *cond_func, Field *field, KEY_PART *key_part, Item_func::Functype type, Item *value, bool *inexact) { const size_t null_bytes = field->is_nullable() ? 1 : 0; bool optimize_range; SEL_ROOT *tree = nullptr; MEM_ROOT *const alloc = param->temp_mem_root; uchar *str; const char *impossible_cond_cause = nullptr; DBUG_TRACE; if (param->has_errors()) goto end; if (!value) // IS NULL or IS NOT NULL { if (field->table->pos_in_table_list->outer_join) /* Range scan cannot be used to scan the inner table of an outer join if the predicate is IS NULL. */ goto end; if (!field->is_nullable()) // NOT NULL column { if (type == Item_func::ISNULL_FUNC) tree = new (alloc) SEL_ROOT(alloc, SEL_ROOT::Type::IMPOSSIBLE); goto end; } uchar *null_string = static_cast(alloc->Alloc(key_part->store_length + 1)); if (!null_string) goto end; // out of memory TRASH(null_string, key_part->store_length + 1); memcpy(null_string, is_null_string, sizeof(is_null_string)); SEL_ARG *root; if (!(root = new (alloc) SEL_ARG(field, null_string, null_string, !(key_part->flag & HA_REVERSE_SORT)))) goto end; // out of memory if (!(tree = new (alloc) SEL_ROOT(root))) goto end; // out of memory if (type == Item_func::ISNOTNULL_FUNC) { root->min_flag = NEAR_MIN; /* IS NOT NULL -> X > NULL */ root->max_flag = NO_MAX_RANGE; } goto end; } /* The range access method cannot be used unless 'field' and 'value' are comparable in the index. Examples of non-comparable field/values: different collation, DATETIME vs TIME etc. */ if (!comparable_in_index(cond_func, field, key_part->image_type, type, value)) { warn_index_not_applicable(thd, param, key_part->key, field); goto end; } if (key_part->image_type == Field::itMBR) { // @todo: use is_spatial_operator() instead? switch (type) { case Item_func::SP_EQUALS_FUNC: case Item_func::SP_DISJOINT_FUNC: case Item_func::SP_INTERSECTS_FUNC: case Item_func::SP_TOUCHES_FUNC: case Item_func::SP_CROSSES_FUNC: case Item_func::SP_WITHIN_FUNC: case Item_func::SP_CONTAINS_FUNC: case Item_func::SP_OVERLAPS_FUNC: break; default: /* We cannot involve spatial indexes for queries that don't use MBREQUALS(), MBRDISJOINT(), etc. functions. */ goto end; } } if (param->using_real_indexes) optimize_range = field->optimize_range(param->real_keynr[key_part->key], key_part->part); else optimize_range = true; if (type == Item_func::LIKE_FUNC) { bool like_error; char buff1[MAX_FIELD_WIDTH]; uchar *min_str, *max_str; String tmp(buff1, sizeof(buff1), value->collation.collation), *res; size_t length, offset, min_length, max_length; size_t field_length = field->pack_length() + null_bytes; if (!optimize_range) goto end; if (!(res = value->val_str(&tmp))) { tree = new (alloc) SEL_ROOT(alloc, SEL_ROOT::Type::IMPOSSIBLE); goto end; } /* TODO: Check if this was a function. This should have be optimized away in the sql_select.cc */ if (res != &tmp) { tmp.copy(*res); // Get own copy res = &tmp; } if (field->cmp_type() != STRING_RESULT) goto end; // Can only optimize strings offset = null_bytes; length = key_part->store_length; if (length != key_part->length + null_bytes) { /* key packed with length prefix */ offset += HA_KEY_BLOB_LENGTH; field_length = length - HA_KEY_BLOB_LENGTH; } else { if (unlikely(length < field_length)) { /* This can only happen in a table created with UNIREG where one key overlaps many fields */ length = field_length; } else field_length = length; } length += offset; if (!(min_str = (uchar *)alloc->Alloc(length * 2))) goto end; max_str = min_str + length; if (field->is_nullable()) max_str[0] = min_str[0] = 0; Item_func_like *like_func = down_cast(cond_func); // We can only optimize with LIKE if the escape string is known. if (!like_func->escape_is_evaluated()) goto end; field_length -= null_bytes; like_error = my_like_range( field->charset(), res->ptr(), res->length(), like_func->escape(), wild_one, wild_many, field_length, (char *)min_str + offset, (char *)max_str + offset, &min_length, &max_length); if (like_error) // Can't optimize with LIKE goto end; // LIKE is tricky to get 100% exact, especially with Unicode collations // (which can have contractions etc.), and will frequently be a bit too // broad. To be safe, we currently always set that LIKE range scans are // inexact and must be rechecked by means of a filter afterwards. *inexact = true; if (offset != null_bytes) // BLOB or VARCHAR { int2store(min_str + null_bytes, static_cast(min_length)); int2store(max_str + null_bytes, static_cast(max_length)); } SEL_ARG *root = new (alloc) SEL_ARG(field, min_str, max_str, !(key_part->flag & HA_REVERSE_SORT)); if (!root || !(tree = new (alloc) SEL_ROOT(root))) goto end; // out of memory goto end; } if (!optimize_range && type != Item_func::EQ_FUNC && type != Item_func::EQUAL_FUNC) goto end; // Can't optimize this /* Geometry operations may mix geometry types, e.g., we may be checking ST_Contains(, ). In such cases, field->geom_type will be a different type than the value we're trying to store in it, and the conversion will fail. Therefore, set the most general geometry type while saving, and revert to the original geometry type afterwards. */ { const Field::geometry_type save_geom_type = (field->type() == MYSQL_TYPE_GEOMETRY) ? field->get_geometry_type() : Field::GEOM_GEOMETRY; if (field->type() == MYSQL_TYPE_GEOMETRY) { down_cast(field)->geom_type = Field::GEOM_GEOMETRY; // R-tree queries are based on bounds, and must be rechecked. *inexact = true; } bool always_true_or_false = save_value_and_handle_conversion( &tree, value, type, field, &impossible_cond_cause, alloc, param->query_block, inexact); if (field->type() == MYSQL_TYPE_GEOMETRY && save_geom_type != Field::GEOM_GEOMETRY) { down_cast(field)->geom_type = save_geom_type; } if (always_true_or_false) goto end; } /* Any sargable predicate except "<=>" involving NULL as a constant is always false */ if (type != Item_func::EQUAL_FUNC && field->is_real_null()) { impossible_cond_cause = "comparison_with_null_always_false"; tree = new (alloc) SEL_ROOT(alloc, SEL_ROOT::Type::IMPOSSIBLE); goto end; } str = (uchar *)alloc->Alloc(key_part->store_length + 1); if (!str) goto end; if (field->is_nullable()) *str = (uchar)field->is_real_null(); // Set to 1 if null field->get_key_image(str + null_bytes, key_part->length, key_part->image_type); SEL_ARG *root; root = new (alloc) SEL_ARG(field, str, str, !(key_part->flag & HA_REVERSE_SORT)); if (!root || !(tree = new (alloc) SEL_ROOT(root))) goto end; // out of memory /* Check if we are comparing an UNSIGNED integer with a negative constant. In this case we know that: (a) (unsigned_int [< | <=] negative_constant) == false (b) (unsigned_int [> | >=] negative_constant) == true In case (a) the condition is false for all values, and in case (b) it is true for all values, so we can avoid unnecessary retrieval and condition testing, and we also get correct comparison of unsigned integers with negative integers (which otherwise fails because at query execution time negative integers are cast to unsigned if compared with unsigned). */ if (field->result_type() == INT_RESULT && value->result_type() == INT_RESULT && ((field->type() == FIELD_TYPE_BIT || field->is_unsigned()) && !(value)->unsigned_flag)) { longlong item_val = value->val_int(); if (item_val < 0) { if (type == Item_func::LT_FUNC || type == Item_func::LE_FUNC) { impossible_cond_cause = "unsigned_int_cannot_be_negative"; tree->type = SEL_ROOT::Type::IMPOSSIBLE; goto end; } if (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC) { tree = nullptr; goto end; } } } switch (type) { case Item_func::LT_FUNC: case Item_func::LE_FUNC: /* Don't use open ranges for partial key_segments */ if (!(key_part->flag & HA_PART_KEY_SEG)) { /* Set NEAR_MAX to read values lesser than the stored value. */ const int cmp_value = stored_field_cmp_to_item(thd, field, value); if ((type == Item_func::LT_FUNC && cmp_value >= 0) || (type == Item_func::LE_FUNC && cmp_value > 0)) tree->root->max_flag = NEAR_MAX; } if (!field->is_nullable()) tree->root->min_flag = NO_MIN_RANGE; /* From start */ else { // > NULL if (!(tree->root->min_value = static_cast( alloc->Alloc(key_part->store_length + 1)))) goto end; TRASH(tree->root->min_value, key_part->store_length + 1); memcpy(tree->root->min_value, is_null_string, sizeof(is_null_string)); tree->root->min_flag = NEAR_MIN; } break; case Item_func::GT_FUNC: case Item_func::GE_FUNC: /* Don't use open ranges for partial key_segments */ if (!(key_part->flag & HA_PART_KEY_SEG)) { /* Set NEAR_MIN to read values greater than the stored value. */ const int cmp_value = stored_field_cmp_to_item(thd, field, value); if ((type == Item_func::GT_FUNC && cmp_value <= 0) || (type == Item_func::GE_FUNC && cmp_value < 0)) tree->root->min_flag = NEAR_MIN; } tree->root->max_flag = NO_MAX_RANGE; break; case Item_func::SP_EQUALS_FUNC: tree->root->set_gis_index_read_function(HA_READ_MBR_EQUAL); break; case Item_func::SP_DISJOINT_FUNC: tree->root->set_gis_index_read_function(HA_READ_MBR_DISJOINT); break; case Item_func::SP_INTERSECTS_FUNC: tree->root->set_gis_index_read_function(HA_READ_MBR_INTERSECT); break; case Item_func::SP_TOUCHES_FUNC: tree->root->set_gis_index_read_function(HA_READ_MBR_INTERSECT); break; case Item_func::SP_CROSSES_FUNC: tree->root->set_gis_index_read_function(HA_READ_MBR_INTERSECT); break; case Item_func::SP_WITHIN_FUNC: /* Adjust the rkey_func_flag as it's assumed and observed that both MyISAM and Innodb implement this function in reverse order. */ tree->root->set_gis_index_read_function(HA_READ_MBR_CONTAIN); break; case Item_func::SP_CONTAINS_FUNC: /* Adjust the rkey_func_flag as it's assumed and observed that both MyISAM and Innodb implement this function in reverse order. */ tree->root->set_gis_index_read_function(HA_READ_MBR_WITHIN); break; case Item_func::SP_OVERLAPS_FUNC: tree->root->set_gis_index_read_function(HA_READ_MBR_INTERSECT); break; default: break; } end: if (impossible_cond_cause != nullptr) { Opt_trace_object wrapper(&thd->opt_trace); Opt_trace_object(&thd->opt_trace, "impossible_condition", Opt_trace_context::RANGE_OPTIMIZER) .add_alnum("cause", impossible_cond_cause); } return tree; } /** Add a new key test to a key when scanning through all keys This will never be called for same key parts. @param key1 Old root of key @param key2 Element to insert (must be a single element) @return New root of key */ static SEL_ROOT *sel_add(SEL_ROOT *key1, SEL_ROOT *key2) { if (!key1) return key2; if (!key2) return key1; // key2 is assumed to be a single element. assert(!key2->root->next_key_part); if (key2->root->part < key1->root->part) { // key2 fits in the start of the list. key2->root->set_next_key_part(key1); return key2; } // Find out where in the chain in key1 to put key2. SEL_ARG *node = key1->root; while (node->next_key_part && node->next_key_part->root->part > key2->root->part) node = node->next_key_part->root; key2->root->set_next_key_part(node->release_next_key_part()); node->set_next_key_part(key2); return key1; }