#include <assert.h>

#include <string.h>

#include <sys/types.h>

#include "field_types.h"

#include "m_ctype.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/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/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"

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);

static void warn_index_not_applicable(THD *thd, const RANGE_OPT_PARAM *param,

}

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;

}

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<Item_field *>(predicand)->field;

if (op->m_const_array != nullptr && !op->m_const_array->is_row_result()) {

/*

const uint NOT_IN_IGNORE_THRESHOLD = 1000;

// If we have t.key NOT IN (null, null, ...) or the list is too long

if (op->m_const_array->m_used_size == 0 ||

op->m_const_array->m_used_size > NOT_IN_IGNORE_THRESHOLD)

return nullptr;

/*

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 (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;

}

}

}

/*

tree = tree_or(param, remove_jump_scans, tree, tree2);

}

}

if (tree && tree->type != SEL_TREE::IMPOSSIBLE) {

/*

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 (<column>) IN (...)

Field *field = down_cast<Item_field *>(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) {

/*

SEL_TREE *or_tree = &null_sel_tree;

Item_row *row_predicand = down_cast<Item_row *>(predicand);

// Iterate over the rows on the rhs of the in predicate, building an OR.

for (uint i = 1; i < op->argument_count(); ++i) {

/*

Item *in_list_item = op->arguments()[i];

if (in_list_item->type() != Item::ROW_ITEM) return nullptr;

Item_row *row = static_cast<Item_row *>(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)->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);

/*

if (and_tree == nullptr) return nullptr;

}

or_tree = tree_or(param, remove_jump_scans, or_tree, and_tree);

}

return or_tree;

}

return nullptr;

}

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(<array_field>,<JSON array/scalar>), or

// The expression is JSON_OVERLAPS(<JSON array/scalar>, <array_field>), or

// The expression is JSON_CONTAINS(<array_field>, <JSON array/scalar>)

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<Field_typed_array *>(

down_cast<Item_field *>(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<Item_field *>(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<Item_field *>(predicand)));

if (!tree) // OOM

break;

}

}

field->table->const_table = save_const;

return tree;

}

return nullptr;

}

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<Item_field *>(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<Item_field *>(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<Item *>(1) ? Item_func::GT_FUNC

: Item_func::LT_FUNC)

: (value == reinterpret_cast<Item *>(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<Item_func_in *>(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<Field_typed_array *>(

down_cast<Item_field *>(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<Item_field *>(predicand)->field;

/*

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;

}

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;

/*

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<Item_field *>(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->item_equal;

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;

}

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<Item_cond *>(cond)->functype();

SEL_TREE *tree = nullptr;

bool first = true;

for (Item &item : *down_cast<Item_cond *>(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->is_expensive()) {

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;

}

/*

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<Item_field *>(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);

}

/*

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<Item_field *>(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<Item *>(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<Item_equal *>(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<Item_field *>(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,