Classes used for query optimizations. More...

#include <sys/types.h>
#include <cstring>
#include <memory>
#include <utility>
#include "field_types.h"
#include "my_alloc.h"
#include "my_base.h"
#include "my_dbug.h"
#include "my_table_map.h"
#include "sql/field.h"
#include "sql/item.h"
#include "sql/iterators/row_iterator.h"
#include "sql/mem_root_array.h"
#include "sql/opt_explain_format.h"
#include "sql/sql_executor.h"
#include "sql/sql_lex.h"
#include "sql/sql_list.h"
#include "sql/sql_opt_exec_shared.h"
#include "sql/sql_select.h"
#include "sql/table.h"
#include "sql/temp_table_param.h"

Classes
struct	SARGABLE_PARAM

class	ORDER_with_src
	Wrapper for ORDER* pointer to trace origins of ORDER list. More...

class	JOIN

struct	JOIN::TemporaryTableToCleanup

class	Switch_ref_item_slice
	RAII class to ease the temporary switching to a different slice of the ref item array. More...

class	Table_map_restorer
	This class restores a table_map object to its original value when '*this' is destroyed. More...

Macros
#define	ASSERT_BEST_REF_IN_JOIN_ORDER(join)
	Use this in a function which depends on best_ref listing tables in the final join order. More...

Typedefs
typedef Mem_root_array< Key_use >	Key_use_array

Functions
bool	uses_index_fields_only (Item item, TABLE tbl, uint keyno, bool other_tbls_ok)
	Check if given expression only uses fields covered by index keyno in the table tbl. More...

bool	remove_eq_conds (THD thd, Item cond, Item *retcond, Item::cond_result cond_value)
	Removes const and eq items. More...

bool	optimize_cond (THD thd, Item conds, COND_EQUAL cond_equal, mem_root_deque< Table_ref > join_list, Item::cond_result cond_value)
	Optimize conditions by. More...

Item *	substitute_for_best_equal_field (THD thd, Item cond, COND_EQUAL cond_equal, JOIN_TAB *table_join_idx)
	Substitute every field reference in a condition by the best equal field and eliminate all multiple equality predicates. More...

bool	build_equal_items (THD thd, Item cond, Item *retcond, COND_EQUAL inherited, bool do_inherit, mem_root_deque< Table_ref * > join_list, COND_EQUAL *cond_equal_ref)
	Build multiple equalities for a WHERE condition and all join conditions that inherit these multiple equalities. More...

bool	is_indexed_agg_distinct (JOIN join, mem_root_deque< Item_field > *out_args)
	Check for the presence of AGGFN(DISTINCT a) queries that may be subject to loose index scan. More...

Key_use_array *	create_keyuse_for_table (THD thd, uint keyparts, Item_field fields, const mem_root_deque< Item > &outer_exprs)
	Create a keyuse array for a table with a primary key. More...

Item_field *	get_best_field (Item_field item_field, COND_EQUAL cond_equal)
	Get the best field substitution for a given field. More...

Item *	make_cond_for_table (THD thd, Item cond, table_map tables, table_map used_table, bool exclude_expensive_cond)
	Extract a condition that can be checked after reading given table. More...

uint	build_bitmap_for_nested_joins (mem_root_deque< Table_ref * > *join_list, uint first_unused)
	Assign each nested join structure a bit in nested_join_map. More...

ORDER *	create_order_from_distinct (THD thd, Ref_item_array ref_item_array, ORDER order_list, mem_root_deque< Item * > fields, bool skip_aggregates, bool convert_bit_fields_to_long, bool all_order_by_fields_used)
	Create an order list that consists of all non-const fields and items. More...

bool	field_time_cmp_date (const Field f, const Item v)
	Returns true if arguments are a temporal Field having no date, part and a temporal expression having a date part. More...

bool	substitute_gc (THD thd, Query_block query_block, Item where_cond, ORDER group_list, ORDER *order)
	Substitute all expressions in the WHERE condition and ORDER/GROUP lists that match generated columns (GC) expressions with GC fields, if any. More...

double	calculate_subquery_executions (const Item_subselect subquery, Opt_trace_context trace)
	Estimates how many times a subquery will be executed as part of a query execution. More...

bool	evaluate_during_optimization (const Item item, const Query_block select)
	Checks if an Item, which is constant for execution, can be evaluated during optimization. More...

Item_equal *	find_item_equal (COND_EQUAL cond_equal, const Item_field item_field, bool *inherited_fl)
	Find the multiple equality predicate containing a field. More...

double	find_worst_seeks (const TABLE *table, double num_rows, double table_scan_cost)
	Find an artificial cap for ref access. More...

bool	ref_lookup_subsumes_comparison (THD thd, Field field, Item right_item, bool can_evaluate, bool subsumes)
	Whether a ref lookup of “right_item” on “field” will give an exact comparison in all cases, ie., one can remove any further checks on field = right_item. More...

bool	IteratorsAreNeeded (const THD thd, AccessPath root_path)
	Checks if we need to create iterators for this query. More...

double	EstimateRowAccesses (const AccessPath *path, double num_evaluations, double limit)
	Estimates the number of base table row accesses that will be performed when executing a query using the given plan. More...

bool	IsHashEquijoinCondition (const Item_eq_base *item, table_map left_side, table_map right_side)
	Returns true if "item" can be used as a hash join condition between the tables given by "left_side" and "right_side". More...

Variables
const char *	antijoin_null_cond

Detailed Description

Classes used for query optimizations.

Macro Definition Documentation

◆ ASSERT_BEST_REF_IN_JOIN_ORDER

#define ASSERT_BEST_REF_IN_JOIN_ORDER ( join )

Value:

  do {                                                                      \
    assert((join)->tables == 0 || ((join)->best_ref && !(join)->join_tab)); \
  } while (0)

Use this in a function which depends on best_ref listing tables in the final join order.

If 'tables==0', one is not expected to consult best_ref cells, and best_ref may not even have been allocated.

Typedef Documentation

◆ Key_use_array

typedef Mem_root_array<Key_use> Key_use_array

Function Documentation

◆ calculate_subquery_executions()

double calculate_subquery_executions	(	const Item_subselect *	subquery,
		Opt_trace_context *	trace
	)

Estimates how many times a subquery will be executed as part of a query execution.

If it is a cacheable subquery, the estimate tells how many times the subquery will be executed if it is not cached.

Parameters

[in]	subquery	the Item that represents the subquery
[in,out]	trace	optimizer trace context

Returns: the number of times the subquery is expected to be executed

◆ create_keyuse_for_table()

Key_use_array * create_keyuse_for_table	(	THD *	thd,
		uint	keyparts,
		Item_field **	fields,
		const mem_root_deque< Item * > &	outer_exprs
	)

Create a keyuse array for a table with a primary key.

To be used when creating a materialized temporary table.

Parameters

thd	THD pointer, for memory allocation
keyparts	Number of key parts in the primary key
fields	fields
outer_exprs	List of items used for key lookup

Returns: Pointer to created keyuse array, or NULL if error

◆ create_order_from_distinct()

ORDER * create_order_from_distinct	(	THD *	thd,
		Ref_item_array	ref_item_array,
		ORDER *	order_list,
		mem_root_deque< Item * > *	fields,
		bool	skip_aggregates,
		bool	convert_bit_fields_to_long,
		bool *	all_order_by_fields_used
	)

Create an order list that consists of all non-const fields and items.

This is usable for e.g. converting DISTINCT into GROUP or ORDER BY. Is ref_item_array is non-null (is_null() returns false), the items will point into the slice given by it. Otherwise, it points directly into *fields (this is the only reason why fields is not const).

Try to put the items in "order_list" first, to allow one to optimize away a later ORDER BY.

◆ EstimateRowAccesses()

double EstimateRowAccesses	(	const AccessPath *	path,
		double	num_evaluations,
		double	limit
	)

Estimates the number of base table row accesses that will be performed when executing a query using the given plan.

Parameters

path	The access path representing the plan.
num_evaluations	The number of times this path is expected to be evaluated during a single execution of the query.
limit	The maximum number of rows expected to be read from this path.

Returns: An estimate of the number of row accesses.

◆ evaluate_during_optimization()

bool evaluate_during_optimization	(	const Item *	item,
		const Query_block *	select
	)

Checks if an Item, which is constant for execution, can be evaluated during optimization.

It cannot be evaluated if it contains a subquery and the OPTION_NO_SUBQUERY_DURING_OPTIMIZATION query option is active.

Parameters

item	the Item to check
select	the query block that contains the Item

Returns: false if this Item contains a subquery and subqueries cannot be evaluated during optimization, or true otherwise

◆ field_time_cmp_date()

bool field_time_cmp_date	(	const Field *	f,
		const Item *	v
	)

inline

Returns true if arguments are a temporal Field having no date, part and a temporal expression having a date part.

Parameters

f	Field
v	Expression

◆ is_indexed_agg_distinct()

bool is_indexed_agg_distinct	(	JOIN *	join,
		mem_root_deque< Item_field * > *	out_args
	)

Check for the presence of AGGFN(DISTINCT a) queries that may be subject to loose index scan.

Check if the query is a subject to AGGFN(DISTINCT) using loose index scan (GroupIndexSkipScanIterator). Optionally (if out_args is supplied) will push the arguments of AGGFN(DISTINCT) to the list

Check for every COUNT(DISTINCT), AVG(DISTINCT) or SUM(DISTINCT). These can be resolved by Loose Index Scan as long as all the aggregate distinct functions refer to the same fields. Thus:

SELECT AGGFN(DISTINCT a, b), AGGFN(DISTINCT b, a)... => can use LIS SELECT AGGFN(DISTINCT a), AGGFN(DISTINCT a) ... => can use LIS SELECT AGGFN(DISTINCT a, b), AGGFN(DISTINCT a) ... => cannot use LIS SELECT AGGFN(DISTINCT a), AGGFN(DISTINCT b) ... => cannot use LIS etc.

Parameters

	join	the join to check
[out]	out_args	Collect the arguments of the aggregate functions to a list. We don't worry about duplicates as these will be sorted out later in get_best_group_min_max.

Returns: does the query qualify for indexed AGGFN(DISTINCT)

Return values

true	it does
false	AGGFN(DISTINCT) must apply distinct in it.

◆ IsHashEquijoinCondition()

bool IsHashEquijoinCondition	(	const Item_eq_base *	item,
		table_map	left_side,
		table_map	right_side
	)

Returns true if "item" can be used as a hash join condition between the tables given by "left_side" and "right_side".

This is used to determine whether an equijoin condition needs to be attached as an "extra" condition.

It can be used as a hash join condition if the item on one side of the equality references some table in left_side and none in right_side, and the other side of the equality references some table in right_side and none in left_side.

Parameters

item	An equality that is a candidate for joining the left side tables with the right side tables.
left_side	The tables on the left side of the join.
right_side	The tables on the right side of the join.

Return values

true	If the equality can be used as a hash join condition.
false	If the equality must be added as an extra condition to be evaluated after the join.

◆ IteratorsAreNeeded()

bool IteratorsAreNeeded	(	const THD *	thd,
		AccessPath *	root_path
	)

Checks if we need to create iterators for this query.

We usually have to. The exception is if a secondary engine is used, and that engine will offload the query execution to an external executor using JOIN::override_executor_func. In this case, the external executor will use its own execution structures and we don't need to bother with creating the iterators needed by the MySQL executor.

◆ make_cond_for_table()

Item * make_cond_for_table	(	THD *	thd,
		Item *	cond,
		table_map	tables,
		table_map	used_table,
		bool	exclude_expensive_cond
	)

Extract a condition that can be checked after reading given table.

Parameters

thd	Current session.
cond	Condition to analyze
tables	Tables for which "current field values" are available
used_table	Table(s) that we are extracting the condition for (may also include PSEUDO_TABLE_BITS, and may be zero)
exclude_expensive_cond	Do not push expensive conditions

Return values

<>NULL	Generated condition
=	NULL Already checked, OR error

Extract the condition that can be checked after reading the table(s) specified in used_table, given that current-field values for tables specified in tables bitmap are available. If used_table is 0, extract conditions for all tables in tables.

This function can be used to extract conditions relevant for a table in a join order. Together with its caller, it will ensure that all conditions are attached to the first table in the join order where all necessary fields are available, and it will also ensure that a given condition is attached to only one table. To accomplish this, first initialize tables to the empty set. Then, loop over all tables in the join order, set used_table to the bit representing the current table, accumulate used_table into the tables set, and call this function. To ensure correct handling of const expressions and outer references, add the const table map and OUTER_REF_TABLE_BIT to used_table for the first table. To ensure that random expressions are evaluated for the final table, add RAND_TABLE_BIT to used_table for the final table.

The function assumes that constant, inexpensive parts of the condition have already been checked. Constant, expensive parts will be attached to the first table in the join order, provided that the above call sequence is followed.

The call order will ensure that conditions covering tables in tables minus those in used_table, have already been checked.

The function takes into account that some parts of the condition are guaranteed to be true by employed 'ref' access methods (the code that does this is located at the end, search down for "EQ_FUNC").

Note: make_cond_for_info_schema() uses an algorithm similar to make_cond_for_table().

◆ optimize_cond()

bool optimize_cond	(	THD *	thd,
		Item **	cond,
		COND_EQUAL **	cond_equal,
		mem_root_deque< Table_ref * > *	join_list,
		Item::cond_result *	cond_value
	)

Optimize conditions by.

a) applying transitivity to build multiple equality predicates (MEP): if x=y and y=z the MEP x=y=z is built. b) apply constants where possible. If the value of x is known to be 42, x is replaced with a constant of value 42. By transitivity, this also applies to MEPs, so the MEP in a) will become 42=x=y=z. c) remove conditions that are always false or always true

Parameters

	thd	Thread handler
[in,out]	cond	WHERE or HAVING condition to optimize
[out]	cond_equal	The built multiple equalities
	join_list	list of join operations with join conditions = NULL: Called for HAVING condition
[out]	cond_value	Not changed if cond was empty COND_TRUE if cond is always true COND_FALSE if cond is impossible COND_OK otherwise

Returns: false if success, true if error

◆ ref_lookup_subsumes_comparison()

bool ref_lookup_subsumes_comparison	(	THD *	thd,
		Field *	field,
		Item *	right_item,
		bool	can_evaluate,
		bool *	subsumes
	)

Whether a ref lookup of “right_item” on “field” will give an exact comparison in all cases, ie., one can remove any further checks on field = right_item.

If not, there may be false positives, and one needs to keep the comparison after the ref lookup.

Parameters

	thd	thread handler
	field	field that is looked up through an index
	right_item	value used to perform look up
	can_evaluate	whether the function is allowed to evaluate right_item (if true, right_item must be const-for-execution)
[out]	subsumes	true if an exact comparison can be done, false otherwise

Returns: false if success, true if error

◆ remove_eq_conds()

bool remove_eq_conds	(	THD *	thd,
		Item *	cond,
		Item **	retcond,
		Item::cond_result *	cond_value
	)

Removes const and eq items.

Returns the new item, or nullptr if no condition.

Parameters

	thd	thread handler
	cond	the condition to handle
[out]	retcond	condition after const removal
[out]	cond_value	resulting value of the condition =COND_OK condition must be evaluated (e.g. field = constant) =COND_TRUE always true (e.g. 1 = 1) =COND_FALSE always false (e.g. 1 = 2)

Returns: false if success, true if error

Classes

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ ASSERT_BEST_REF_IN_JOIN_ORDER

Typedef Documentation

◆ Key_use_array

Function Documentation

◆ calculate_subquery_executions()

◆ create_keyuse_for_table()

◆ create_order_from_distinct()

◆ EstimateRowAccesses()

◆ evaluate_during_optimization()

◆ field_time_cmp_date()

◆ is_indexed_agg_distinct()

◆ IsHashEquijoinCondition()

◆ IteratorsAreNeeded()

◆ make_cond_for_table()

◆ optimize_cond()

◆ ref_lookup_subsumes_comparison()

◆ remove_eq_conds()