MySQL 8.3.0
Source Code Documentation
sql_optimizer.h File Reference

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"

Go to the source code of this file.

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_useKey_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...
 
Itemsubstitute_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_arraycreate_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_fieldget_best_field (Item_field *item_field, COND_EQUAL *cond_equal)
 Get the best field substitution for a given field. More...
 
Itemmake_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...
 
ORDERcreate_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_equalfind_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)
std::string join(Container cont, const std::string &delim)
join elements of an container into a string separated by a delimiter.
Definition: string.h:150

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

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]subquerythe Item that represents the subquery
[in,out]traceoptimizer 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
thdTHD pointer, for memory allocation
keypartsNumber of key parts in the primary key
fieldsfields
outer_exprsList 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
pathThe access path representing the plan.
num_evaluationsThe number of times this path is expected to be evaluated during a single execution of the query.
limitThe 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
itemthe Item to check
selectthe 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
fField
vExpression

◆ 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
jointhe join to check
[out]out_argsCollect 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_skip_scan.
Returns
does the query qualify for indexed AGGFN(DISTINCT)
Return values
trueit does
falseAGGFN(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
itemAn equality that is a candidate for joining the left side tables with the right side tables.
left_sideThe tables on the left side of the join.
right_sideThe tables on the right side of the join.
Return values
trueIf the equality can be used as a hash join condition.
falseIf 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
thdCurrent session.
condCondition to analyze
tablesTables for which "current field values" are available
used_tableTable(s) that we are extracting the condition for (may also include PSEUDO_TABLE_BITS, and may be zero)
exclude_expensive_condDo not push expensive conditions
Return values
<>NULLGenerated 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
thdThread handler
[in,out]condWHERE or HAVING condition to optimize
[out]cond_equalThe built multiple equalities
join_listlist of join operations with join conditions = NULL: Called for HAVING condition
[out]cond_valueNot 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
thdthread handler
fieldfield that is looked up through an index
right_itemvalue used to perform look up
can_evaluatewhether the function is allowed to evaluate right_item (if true, right_item must be const-for-execution)
[out]subsumestrue 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
thdthread handler
condthe condition to handle
[out]retcondcondition after const removal
[out]cond_valueresulting 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