#include "sql/range_optimizer/range_optimizer.h"
#include <float.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <set>
#include "field_types.h"
#include "m_string.h"
#include "my_alloc.h"
#include "my_bitmap.h"
#include "my_compiler.h"
#include "my_dbug.h"
#include "my_sqlcommand.h"
#include "mysql/strings/m_ctype.h"
#include "mysql/udf_registration_types.h"
#include "mysql_com.h"
#include "scope_guard.h"
#include "sql/check_stack.h"
#include "sql/current_thd.h"
#include "sql/field_common_properties.h"
#include "sql/item.h"
#include "sql/item_func.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/key.h"
#include "sql/mem_root_array.h"
#include "sql/mysqld.h"
#include "sql/opt_costmodel.h"
#include "sql/opt_hints.h"
#include "sql/opt_trace.h"
#include "sql/opt_trace_context.h"
#include "sql/psi_memory_key.h"
#include "sql/range_optimizer/group_index_skip_scan_plan.h"
#include "sql/range_optimizer/index_merge_plan.h"
#include "sql/range_optimizer/index_range_scan_plan.h"
#include "sql/range_optimizer/index_skip_scan_plan.h"
#include "sql/range_optimizer/internal.h"
#include "sql/range_optimizer/path_helpers.h"
#include "sql/range_optimizer/range_analysis.h"
#include "sql/range_optimizer/range_opt_param.h"
#include "sql/range_optimizer/rowid_ordered_retrieval_plan.h"
#include "sql/range_optimizer/tree.h"
#include "sql/sql_class.h"
#include "sql/sql_lex.h"
#include "sql/sql_list.h"
#include "sql/sql_optimizer.h"
#include "sql/sql_select.h"
#include "sql/system_variables.h"
#include "sql/table.h"
#include "sql/thr_malloc.h"
#include "sql/uniques.h"

Namespaces
namespace	opt_range
	Shared sentinel node for all trees.

Functions
static AccessPath *	get_best_disjunct_quick (THD thd, RANGE_OPT_PARAM param, TABLE table, bool index_merge_union_allowed, bool index_merge_sort_union_allowed, bool index_merge_intersect_allowed, bool skip_records_in_range, SEL_IMERGE imerge, const double cost_est, Key_map *needed_reg)

static void	print_quick (AccessPath path, const Key_map needed_reg)

void	range_optimizer_init ()
	Global initialization of the null_element. Call on server start. More...

void	range_optimizer_free ()
	Global destruction of the null_element. Call on server stop. More...

void	trace_quick_description (const AccessPath path, Opt_trace_context trace)

bool	setup_range_optimizer_param (THD thd, MEM_ROOT return_mem_root, MEM_ROOT temp_mem_root, Key_map keys_to_use, TABLE table, Query_block query_block, RANGE_OPT_PARAM param)

int	test_quick_select (THD thd, MEM_ROOT return_mem_root, MEM_ROOT temp_mem_root, Key_map keys_to_use, table_map prev_tables, table_map read_tables, ha_rows limit, bool force_quick_range, const enum_order interesting_order, TABLE table, bool skip_records_in_range, Item cond, Key_map needed_reg, bool ignore_table_scan, Query_block query_block, AccessPath *path)

static AccessPath *	get_ror_union_path (THD thd, RANGE_OPT_PARAM param, TABLE table, bool index_merge_intersect_allowed, SEL_IMERGE imerge, const double read_cost, bool force_index_merge, Bounds_checked_array< AccessPath * > roru_read_plans, AccessPath *range_scans, Opt_trace_object trace_best_disjunct)
	Helper function for get_best_disjunct_quick(), dealing with the case of creating a ROR union. More...

bool	comparable_in_index (Item cond_func, const Field field, const Field::imagetype itype, Item_func::Functype comp_type, const Item *value)
	Test if 'value' is comparable to 'field' when setting up range access for predicate "field OP value". More...

static void	debug_print_tree (SEL_ROOT *origin)
	Debugging function to print out a SEL_ROOT and everything it points to, recursively. More...

int	index_next_different (bool is_index_scan, handler file, KEY_PART_INFO key_part, uchar record, const uchar group_prefix, uint group_prefix_len, uint group_key_parts)
	Find the next different key value by skipping all the rows with the same key value. More...

void	print_key_value (String out, const KEY_PART_INFO key_part, const uchar *key)
	Print a key to a string. More...

static bool	range_is_equality (const uchar min_key, const uchar max_key, unsigned store_length, bool is_nullable)

void	append_range (String out, const KEY_PART_INFO key_part, const uchar min_key, const uchar max_key, const uint flag)
	Append range info for a key part to a string. More...

void	append_range_all_keyparts (Opt_trace_array range_trace, String range_string, String range_so_far, SEL_ROOT keypart, const KEY_PART_INFO *key_parts, const bool print_full)
	Traverse an R-B tree of range conditions and append all ranges for this keypart and consecutive keyparts to range_trace (if non-NULL) or to range_string (if range_trace is NULL). More...

void	append_range_to_string (const QUICK_RANGE range, const KEY_PART_INFO first_key_part, String *out)

void	print_tree (String out, const char tree_name, SEL_TREE tree, const RANGE_OPT_PARAM param, const bool print_full)

Function Documentation

◆ append_range()

void append_range	(	String *	out,
		const KEY_PART_INFO *	key_part,
		const uchar *	min_key,
		const uchar *	max_key,
		const uint	flag
	)

Append range info for a key part to a string.

Parameters

[in,out]	out	String the range info is appended to
[in]	key_part	Indexed column used in a range select
[in]	min_key	Key tuple describing lower bound of range
[in]	max_key	Key tuple describing upper bound of range
[in]	flag	Key range flags defining what min_key and max_key represent

See also: my_base.h

◆ append_range_all_keyparts()

void append_range_all_keyparts	(	Opt_trace_array *	range_trace,
		String *	range_string,
		String *	range_so_far,
		SEL_ROOT *	keypart,
		const KEY_PART_INFO *	key_parts,
		const bool	print_full
	)

Traverse an R-B tree of range conditions and append all ranges for this keypart and consecutive keyparts to range_trace (if non-NULL) or to range_string (if range_trace is NULL).

See description of R-B trees/SEL_ARG for details on how ranges are linked.

Parameters

[in,out]	range_trace	Optimizer trace array ranges are appended to
[in,out]	range_string	The string where range predicates are appended when the last keypart has been reached.
	range_so_far	String containing ranges for keyparts prior to this keypart.
	keypart	The R-B tree containing intervals for this keypart.
	key_parts	Index components description, used when adding information to the optimizer trace
	print_full	Whether or not ranges on unusable keyparts should be printed. Useful for debugging.

Note: This function mimics the behavior of sel_arg_range_seq_next()

◆ append_range_to_string()

void append_range_to_string	(	const QUICK_RANGE *	range,
		const KEY_PART_INFO *	first_key_part,
		String *	out
	)

◆ comparable_in_index()

bool comparable_in_index	(	Item *	cond_func,
		const Field *	field,
		const Field::imagetype	itype,
		Item_func::Functype	comp_type,
		const Item *	value
	)

Test if 'value' is comparable to 'field' when setting up range access for predicate "field OP value".

'field' is a field in the table being optimized for while 'value' is whatever 'field' is compared to.

Parameters

cond_func	the predicate item that compares 'field' with 'value'
field	field in the predicate
itype	itMBR if indexed field is spatial, itRAW otherwise
comp_type	comparator for the predicate
value	whatever 'field' is compared to

Returns: true if 'field' and 'value' are comparable, false otherwise

◆ debug_print_tree()

static void debug_print_tree ( SEL_ROOT * origin )

static

Debugging function to print out a SEL_ROOT and everything it points to, recursively.

Used only when tracking bugs in the range optimizer (for printf debugging); will not normally have any calls to it.

◆ get_best_disjunct_quick()

static AccessPath * get_best_disjunct_quick	(	THD *	thd,
		RANGE_OPT_PARAM *	param,
		TABLE *	table,
		bool	index_merge_union_allowed,
		bool	index_merge_sort_union_allowed,
		bool	index_merge_intersect_allowed,
		bool	skip_records_in_range,
		SEL_IMERGE *	imerge,
		const double	cost_est,
		Key_map *	needed_reg
	)

static

◆ get_ror_union_path()

static AccessPath * get_ror_union_path	(	THD *	thd,
		RANGE_OPT_PARAM *	param,
		TABLE *	table,
		bool	index_merge_intersect_allowed,
		SEL_IMERGE *	imerge,
		const double	read_cost,
		bool	force_index_merge,
		Bounds_checked_array< AccessPath * >	roru_read_plans,
		AccessPath **	range_scans,
		Opt_trace_object *	trace_best_disjunct
	)

static

Helper function for get_best_disjunct_quick(), dealing with the case of creating a ROR union.

Returns nullptr if either an error occurred, or if the ROR union was found to be more expensive than read_cost (which is presumably the cost for the index merge plan).

◆ index_next_different()

int index_next_different	(	bool	is_index_scan,
		handler *	file,
		KEY_PART_INFO *	key_part,
		uchar *	record,
		const uchar *	group_prefix,
		uint	group_prefix_len,
		uint	group_key_parts
	)

Find the next different key value by skipping all the rows with the same key value.

Implements a specialized loose index access method for queries containing aggregate functions with distinct of the form: SELECT SUM|COUNT|AVG FROM t This method comes to replace the index scan + Unique class (distinct selection) for loose index scan that visits all the rows of a covering index instead of jumping in the beginning of each group. TODO: Placeholder function. To be replaced by a handler API call

Parameters

is_index_scan	hint to use index scan instead of random index read to find the next different value.
file	table handler
key_part	group key to compare
record	row data
group_prefix	current key prefix data
group_prefix_len	length of the current key prefix data
group_key_parts	number of the current key prefix columns

Returns: status

Return values

0	success
!0	failure

◆ print_key_value()

void print_key_value	(	String *	out,
		const KEY_PART_INFO *	key_part,
		const uchar *	key
	)

Print a key to a string.

Parameters

[out]	out	String the key is appended to
[in]	key_part	Index components description
[in]	key	Key tuple

◆ print_quick()

static void print_quick	(	AccessPath *	path,
		const Key_map *	needed_reg
	)

static

◆ print_tree()

void print_tree	(	String *	out,
		const char *	tree_name,
		SEL_TREE *	tree,
		const RANGE_OPT_PARAM *	param,
		const bool	print_full
	)

◆ range_is_equality()

static bool range_is_equality	(	const uchar *	min_key,
		const uchar *	max_key,
		unsigned	store_length,
		bool	is_nullable
	)

static

◆ range_optimizer_free()

void range_optimizer_free ( )

Global destruction of the null_element. Call on server stop.

◆ range_optimizer_init()

void range_optimizer_init ( )

Global initialization of the null_element. Call on server start.

◆ setup_range_optimizer_param()

bool setup_range_optimizer_param	(	THD *	thd,
		MEM_ROOT *	return_mem_root,
		MEM_ROOT *	temp_mem_root,
		Key_map	keys_to_use,
		TABLE *	table,
		Query_block *	query_block,
		RANGE_OPT_PARAM *	param
	)

◆ test_quick_select()

int test_quick_select	(	THD *	thd,
		MEM_ROOT *	return_mem_root,
		MEM_ROOT *	temp_mem_root,
		Key_map	keys_to_use,
		table_map	prev_tables,
		table_map	read_tables,
		ha_rows	limit,
		bool	force_quick_range,
		const enum_order	interesting_order,
		TABLE *	table,
		bool	skip_records_in_range,
		Item *	cond,
		Key_map *	needed_reg,
		bool	ignore_table_scan,
		Query_block *	query_block,
		AccessPath **	path
	)

◆ trace_quick_description()

void trace_quick_description	(	const AccessPath *	path,
		Opt_trace_context *	trace
	)

Namespaces

Functions

Function Documentation

◆ append_range()

◆ append_range_all_keyparts()

◆ append_range_to_string()

◆ comparable_in_index()

◆ debug_print_tree()

◆ get_best_disjunct_quick()

◆ get_ror_union_path()

◆ index_next_different()

◆ print_key_value()

◆ print_quick()

◆ print_tree()

◆ range_is_equality()

◆ range_optimizer_free()

◆ range_optimizer_init()

◆ setup_range_optimizer_param()

◆ test_quick_select()

◆ trace_quick_description()