#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"

Functions
static SEL_TREE	null_sel_tree (SEL_TREE::IMPOSSIBLE, &null_root, 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)
	Add a new key test to a key when scanning through all keys This will never be called for same key parts. More...

static void	warn_index_not_applicable (THD thd, const RANGE_OPT_PARAM param, const uint key_num, const Field *field)
	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. More...

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)

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)
	Factory function to build a SEL_TREE from an <in predicate> More...

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)
	Factory function to build a SEL_TREE from a JSON_OVERLAPS or JSON_CONTAINS functions. More...

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)
	Build a SEL_TREE for a simple predicate. More...

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)
	The Range Analysis Module, which finds range access alternatives applicable to single or multi-index (UNION) access. More...

static bool	is_spatial_operator (Item_func::Functype op_type)
	Test whether a comparison operator is a spatial comparison operator, i.e. More...

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)
	Saves 'value' in 'field' and handles potential type conversion problems. More...

Variables
static MEM_ROOT	null_root

static uchar	is_null_string [2] = {1, 0}

Function Documentation

◆ get_full_func_mm_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
	)

static

◆ get_func_mm_tree()

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
	)

static

Build a SEL_TREE for a simple predicate.

Parameters

param	RANGE_OPT_PARAM from test_quick_select
remove_jump_scans	See get_mm_tree()
predicand	field in the predicate
cond_func	item for the predicate
value	constant in the predicate
inv	true <> NOT cond_func is considered (makes sense only when cond_func is BETWEEN or IN)

Returns: Pointer to the built tree.

◆ get_func_mm_tree_from_in_predicate()

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
	)

static

Factory function to build a SEL_TREE from an <in predicate>

Parameters

thd	Thread handle
param	Information on 'just about everything'.
prev_tables	See test_quick_select()
read_tables	See test_quick_select()
remove_jump_scans	See get_mm_tree()
predicand	The <in predicate's> predicand, i.e. the left-hand side of the <in predicate> expression.
op	The 'in' operator itself.
is_negated	If true, the operator is NOT IN, otherwise IN.

◆ get_func_mm_tree_from_json_overlaps_contains()

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
	)

static

Factory function to build a SEL_TREE from a JSON_OVERLAPS or JSON_CONTAINS functions.

  This function builds SEL_TREE out of JSON_OEVRLAPS() of form:
    JSON_OVERLAPS(typed_array_field, "[<val>,...,<val>]")
    JSON_OVERLAPS("[<val>,...,<val>]", typed_array_field)
    JSON_CONTAINS(typed_array_field, "[<val>,...,<val>]")
  where
    typed_array_field is a field which has multi-valued index defined on it
    <val>             each value in the array is coercible to the array's
                      type
  These conditions are pre-checked in substitute_gc().

Parameters

thd	Thread handle
param	Information on 'just about everything'.
prev_tables	See test_quick_select()
read_tables	See test_quick_select()
remove_jump_scans	See get_mm_tree()
predicand	the typed array JSON_CONTAIN's argument
op	The 'JSON_OVERLAPS' operator itself.

Returns: non-NULL constructed SEL_TREE NULL in case of any error

◆ get_mm_leaf()

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

◆ get_mm_parts()

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

◆ get_mm_tree()

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
	)

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 also: 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.; 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.

◆ get_ne_mm_tree()

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
	)

static

◆ is_spatial_operator()

static bool is_spatial_operator ( Item_func::Functype op_type )

static

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.

Parameters

op_type The comparison operator.

Returns: true if 'op_type' is a spatial comparison operator, false otherwise.

◆ null_sel_tree()

static SEL_TREE null_sel_tree	(	SEL_TREE::IMPOSSIBLE	,
		&	null_root,
		0
	)

static

◆ save_value_and_handle_conversion()

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
	)

static

Saves 'value' in 'field' and handles potential type conversion problems.

Parameters

[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.
	value	The Item that contains a value that shall be stored in 'field'.
	comp_op	Comparison operator: >, >=, <=> etc.
	field	The field that 'value' is stored into.
[out]	impossible_cond_cause	Set to a descriptive string if an impossible condition is found.
	memroot	Memroot for creation of new SEL_ARG.
	query_block	Query block the field is part of
	inexact	Set to true on lossy conversion

Return values

false	if saving went fine and it makes sense to continue optimizing for this predicate.
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.

◆ sel_add()

static SEL_ROOT * sel_add	(	SEL_ROOT *	key1,
		SEL_ROOT *	key2
	)

static

Add a new key test to a key when scanning through all keys This will never be called for same key parts.

Parameters

key1	Old root of key
key2	Element to insert (must be a single element)

Returns: New root of key

◆ warn_index_not_applicable()

static void warn_index_not_applicable	(	THD *	thd,
		const RANGE_OPT_PARAM *	param,
		const uint	key_num,
		const Field *	field
	)

static

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.

Parameters

thd	Thread handle
param	RANGE_OPT_PARAM from test_quick_select
key_num	Key number
field	Field in the predicate

Variable Documentation

◆ is_null_string

uchar is_null_string[2] = {1, 0}

static

◆ null_root

MEM_ROOT null_root

static

Functions

Variables

Function Documentation

◆ get_full_func_mm_tree()

◆ get_func_mm_tree()

◆ get_func_mm_tree_from_in_predicate()

◆ get_func_mm_tree_from_json_overlaps_contains()

◆ get_mm_leaf()

◆ get_mm_parts()

◆ get_mm_tree()

◆ get_ne_mm_tree()

◆ is_spatial_operator()

◆ null_sel_tree()

◆ save_value_and_handle_conversion()

◆ sel_add()

◆ warn_index_not_applicable()

Variable Documentation

◆ is_null_string

◆ null_root