MySQL 9.0.0
Source Code Documentation
sql_optimizer.cc File Reference

Optimize query expressions: Make optimal table join order, select optimal access methods per table, apply grouping, sorting and limit processing. More...

#include "sql/sql_optimizer.h"
#include "my_base.h"
#include "sql/sql_optimizer_internal.h"
#include <limits.h>
#include <algorithm>
#include <atomic>
#include <bit>
#include <cmath>
#include <deque>
#include <limits>
#include <new>
#include <string>
#include <utility>
#include <vector>
#include "field_types.h"
#include "ft_global.h"
#include "mem_root_deque.h"
#include "memory_debugging.h"
#include "my_bitmap.h"
#include "my_compiler.h"
#include "my_dbug.h"
#include "my_inttypes.h"
#include "my_sqlcommand.h"
#include "my_sys.h"
#include "mysql/strings/m_ctype.h"
#include "mysql/udf_registration_types.h"
#include "mysql_com.h"
#include "mysqld_error.h"
#include "scope_guard.h"
#include "sql/check_stack.h"
#include "sql/current_thd.h"
#include "sql/debug_sync.h"
#include "sql/derror.h"
#include "sql/enum_query_type.h"
#include "sql/error_handler.h"
#include "sql/handler.h"
#include "sql/item.h"
#include "sql/item_cmpfunc.h"
#include "sql/item_func.h"
#include "sql/item_row.h"
#include "sql/item_subselect.h"
#include "sql/item_sum.h"
#include "sql/iterators/basic_row_iterators.h"
#include "sql/iterators/timing_iterator.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/join_optimizer/bit_utils.h"
#include "sql/join_optimizer/join_optimizer.h"
#include "sql/join_optimizer/optimizer_trace.h"
#include "sql/join_optimizer/relational_expression.h"
#include "sql/join_optimizer/walk_access_paths.h"
#include "sql/key.h"
#include "sql/key_spec.h"
#include "sql/lock.h"
#include "sql/mysqld.h"
#include "sql/nested_join.h"
#include "sql/opt_costmodel.h"
#include "sql/opt_explain.h"
#include "sql/opt_hints.h"
#include "sql/opt_trace.h"
#include "sql/opt_trace_context.h"
#include "sql/parse_tree_node_base.h"
#include "sql/parser_yystype.h"
#include "sql/query_options.h"
#include "sql/query_result.h"
#include "sql/range_optimizer/partition_pruning.h"
#include "sql/range_optimizer/path_helpers.h"
#include "sql/range_optimizer/range_optimizer.h"
#include "sql/sql_base.h"
#include "sql/sql_bitmap.h"
#include "sql/sql_class.h"
#include "sql/sql_const.h"
#include "sql/sql_const_folding.h"
#include "sql/sql_error.h"
#include "sql/sql_join_buffer.h"
#include "sql/sql_list.h"
#include "sql/sql_planner.h"
#include "sql/sql_test.h"
#include "sql/sql_tmp_table.h"
#include "sql/system_variables.h"
#include "sql/table.h"
#include "sql/thd_raii.h"
#include "sql/window.h"
#include "sql_string.h"
#include "template_utils.h"

Classes

class  Plan_change_watchdog
 It is not obvious to see that test_if_skip_sort_order() never changes the plan if no_changes is true. More...
 
class  COND_CMP
 

Macros

#define KEY_OPTIMIZE_EXISTS   1
 
#define KEY_OPTIMIZE_REF_OR_NULL   2
 

Functions

static bool optimize_semijoin_nests_for_materialization (JOIN *join)
 Optimize semi-join nests that could be run with sj-materialization. More...
 
static void calculate_materialization_costs (JOIN *join, Table_ref *sj_nest, uint n_tables, Semijoin_mat_optimize *sjm)
 For {semijoin,subquery} materialization: calculates various cost information, based on a plan in join->best_positions covering the to-be-materialized query block and only this. More...
 
static bool make_join_query_block (JOIN *join, Item *cond)
 Separates the predicates in a join condition and pushes them to the join step where all involved tables are available in the join prefix. More...
 
static bool list_contains_unique_index (JOIN_TAB *tab, bool(*find_func)(Field *, void *), void *data)
 Check if GROUP BY/DISTINCT can be optimized away because the set is already known to be distinct. More...
 
static bool find_field_in_item_list (Field *field, void *data)
 Helper function for list_contains_unique_index. More...
 
static bool find_field_in_order_list (Field *field, void *data)
 Helper function for list_contains_unique_index. More...
 
static TABLEget_sort_by_table (ORDER *a, ORDER *b, Table_ref *tables)
 Return table number if there is only one table in sort order and group and order is compatible, else return 0. More...
 
static void trace_table_dependencies (Opt_trace_context *trace, JOIN_TAB *join_tabs, uint table_count)
 Writes to the optimizer trace information about dependencies between tables. More...
 
static bool update_ref_and_keys (THD *thd, Key_use_array *keyuse, JOIN_TAB *join_tab, uint tables, Item *cond, table_map normal_tables, Query_block *query_block, SARGABLE_PARAM **sargables)
 Update keyuse array with all possible keys we can use to fetch rows. More...
 
static bool pull_out_semijoin_tables (JOIN *join)
 Pull tables out of semi-join nests based on functional dependencies. More...
 
static void add_loose_index_scan_and_skip_scan_keys (JOIN *join, JOIN_TAB *join_tab)
 Discover the indexes that might be used for GROUP BY or DISTINCT queries or indexes that might be used for SKIP SCAN. More...
 
static ha_rows get_quick_record_count (THD *thd, JOIN_TAB *tab, ha_rows limit, Item *condition)
 Returns estimated number of rows that could be fetched by given access method. More...
 
static bool only_eq_ref_tables (JOIN *join, ORDER *order, table_map tables, table_map *cached_eq_ref_tables, table_map *eq_ref_tables)
 
static bool setup_join_buffering (JOIN_TAB *tab, JOIN *join, uint no_jbuf_after)
 Set up join buffering for a specified table, if possible. More...
 
static bool test_if_skip_sort_order (JOIN_TAB *tab, ORDER_with_src &order, ha_rows select_limit, const bool no_changes, const Key_map *map, int *order_idx)
 Test if we can skip ordering by using an index. More...
 
static Item_func_matchtest_if_ft_index_order (ORDER *order)
 Test if ORDER BY is a single MATCH function(ORDER BY MATCH) and sort order is descending. More...
 
static uint32 get_key_length_tmp_table (Item *item)
 (end of group Query_Optimizer) More...
 
static bool can_switch_from_ref_to_range (THD *thd, JOIN_TAB *tab, enum_order ordering, bool recheck_range)
 A helper function to check whether it's better to use range than ref. More...
 
static bool has_not_null_predicate (Item *cond, Item_field *not_null_item)
 Check all existing AND'ed predicates in 'cond' for an existing 'is not null 'not_null_item''-predicate. More...
 
static void SaveCondEqualLists (COND_EQUAL *cond_equal)
 The List<Item_multi_eq> in COND_EQUAL partially overlaps with the argument list in various Item_cond via C-style casts. 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...
 
bool is_prefix_index (TABLE *table, uint idx)
 Test if this is a prefix index. More...
 
int test_if_order_by_key (ORDER_with_src *order_src, TABLE *table, uint idx, uint *used_key_parts, bool *skip_quick)
 Test if one can use the key to resolve ordering. More...
 
uint find_shortest_key (TABLE *table, const Key_map *usable_keys)
 Find shortest key suitable for full table scan. More...
 
bool is_subkey (KEY_PART_INFO *key_part, KEY_PART_INFO *ref_key_part, KEY_PART_INFO *ref_key_part_end)
 Test if a second key is the subkey of the first one. More...
 
static bool is_ref_or_null_optimized (const JOIN_TAB *tab, uint ref_key)
 Test if REF_OR_NULL optimization will be used if the specified ref_key is used for REF-access to 'tab'. More...
 
static uint test_if_subkey (ORDER_with_src *order, JOIN_TAB *tab, uint ref, uint ref_key_parts, const Key_map *usable_keys)
 Test if we can use one of the 'usable_keys' instead of 'ref' key for sorting. More...
 
static JOIN_TABalloc_jtab_array (THD *thd, uint table_count)
 
static void revise_cache_usage (JOIN_TAB *join_tab)
 
Item_multi_eqfind_item_equal (COND_EQUAL *cond_equal, const Item_field *item_field, bool *inherited_fl)
 Find the multiple equality predicate containing a field. More...
 
Item_fieldget_best_field (Item_field *item_field, COND_EQUAL *cond_equal)
 Get the best field substitution for a given field. More...
 
static bool check_simple_equality (THD *thd, Item *left_item, Item *right_item, Item *item, COND_EQUAL *cond_equal, bool *simple_equality)
 Check whether an equality can be used to build multiple equalities. More...
 
static bool check_row_equality (THD *thd, Item *left_row, Item_row *right_row, COND_EQUAL *cond_equal, List< Item > *eq_list, bool *simple_equality)
 Convert row equalities into a conjunction of regular equalities. More...
 
static bool check_equality (THD *thd, Item *item, COND_EQUAL *cond_equal, List< Item > *eq_list, bool *equality)
 Eliminate row equalities and form multiple equalities predicates. More...
 
static bool build_equal_items_for_cond (THD *thd, Item *cond, Item **retcond, COND_EQUAL *inherited, bool do_inherit)
 Replace all equality predicates in a condition by multiple equality items. More...
 
static 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...
 
static int compare_fields_by_table_order (Item_field *field1, Item_field *field2, JOIN_TAB **table_join_idx)
 Compare field items by table order in the execution plan. More...
 
static Itemeliminate_item_equal (THD *thd, Item *cond, COND_EQUAL *upper_levels, Item_multi_eq *item_equal)
 Generate minimal set of simple equalities equivalent to a multiple equality. 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...
 
static bool change_cond_ref_to_const (THD *thd, I_List< COND_CMP > *save_list, Item *and_father, Item *cond, Item *field, Item *value)
 change field = field to field = const for each found field = const in the and_level More...
 
static bool propagate_cond_constants (THD *thd, I_List< COND_CMP > *save_list, Item *and_father, Item *cond)
 Propagate constant values in a condition. 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...
 
double find_worst_seeks (const TABLE *table, double num_rows, double table_scan_cost)
 Find an artificial cap for ref access. More...
 
static void semijoin_types_allow_materialization (Table_ref *sj_nest)
 Check if semijoin's compared types allow materialization. More...
 
static bool check_skip_records_in_range_qualification (JOIN_TAB *tab, THD *thd)
 Index dive can be skipped if the following conditions are satisfied: F1) For a single table query: a) FORCE INDEX applies to a single index. More...
 
uint get_tmp_table_rec_length (const mem_root_deque< Item * > &items, bool include_hidden, bool can_skip_aggs)
 
static bool add_not_null_conds (JOIN *join)
 Add to join_tab[i]->condition() "table.field IS NOT NULL" conditions we've inferred from ref/eq_ref access performed. More...
 
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...
 
static bool find_eq_ref_candidate (Table_ref *tl, table_map sj_inner_tables)
 
static Key_fieldmerge_key_fields (Key_field *start, Key_field *new_fields, Key_field *end, uint and_level)
 Merge new key definitions to old ones, remove those not used in both. More...
 
static uint get_semi_join_select_list_index (Item_field *item_field)
 Given a field, return its index in semi-join's select list, or UINT_MAX. More...
 
static void warn_index_not_applicable (THD *thd, const Field *field, const Key_map cant_use_index)
 If EXPLAIN or if the –safe-updates option is enabled, add a warning that an index cannot be used for ref access. More...
 
static bool add_key_field (THD *thd, Key_field **key_fields, uint and_level, Item_func *cond, Item_field *item_field, bool eq_func, Item **value, uint num_values, table_map usable_tables, SARGABLE_PARAM **sargables)
 Add a possible key to array of possible keys if it's usable as a key. More...
 
static bool add_key_equal_fields (THD *thd, Key_field **key_fields, uint and_level, Item_func *cond, Item_field *field_item, bool eq_func, Item **val, uint num_values, table_map usable_tables, SARGABLE_PARAM **sargables)
 Add possible keys to array of possible keys originated from a simple predicate. More...
 
static bool is_local_field (Item *field)
 Check if an expression is a non-outer field. More...
 
static bool is_row_of_local_columns (Item_row *item_row)
 Check if a row constructor expression is over columns in the same query block. More...
 
bool add_key_fields (THD *thd, JOIN *join, Key_field **key_fields, uint *and_level, Item *cond, table_map usable_tables, SARGABLE_PARAM **sargables)
 The guts of the ref optimizer. More...
 
static bool add_key_part (Key_use_array *keyuse_array, Key_field *key_field)
 
static bool add_ft_keys (Key_use_array *keyuse_array, Item *cond, table_map usable_tables, bool simple_match_expr)
 Function parses WHERE condition and add key_use for FT index into key_use array if suitable MATCH function is found. More...
 
static bool sort_keyuse (const Key_use &a, const Key_use &b)
 Compares two keyuse elements. More...
 
static bool add_key_fields_for_nj (THD *thd, JOIN *join, Table_ref *nested_join_table, Key_field **end, uint *and_level, SARGABLE_PARAM **sargables)
 
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...
 
static void trace_indexes_added_group_distinct (Opt_trace_context *trace, const JOIN_TAB *join_tab, const Key_map new_keys, const char *cause)
 Print keys that were appended to join_tab->const_keys because they can be used for GROUP BY or DISTINCT to the optimizer trace. 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...
 
static Itemadd_found_match_trig_cond (JOIN *join, plan_idx idx, Item *cond, plan_idx root_idx)
 Build a condition guarded by match variables for embedded outer joins. More...
 
static Itempart_of_refkey (TABLE *table, Index_lookup *ref, const Field *field)
 
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...
 
static bool test_if_ref (THD *thd, Item_field *left_item, Item *right_item, bool *redundant)
 Identify redundant predicates. More...
 
static bool reduce_cond_for_table (THD *thd, Item *cond, table_map null_extended, Item **reduced)
 Remove redundant predicates from condition, return the reduced condition. 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...
 
static bool eq_ref_table (JOIN *join, ORDER *start_order, JOIN_TAB *tab, table_map *cached_eq_ref_tables, table_map *eq_ref_tables)
 Remove the following expressions from ORDER BY and GROUP BY: Constant expressions
Expression that only uses tables that are of type EQ_REF and the reference is in the ORDER list or if all refereed tables are of the above type. More...
 
static bool duplicate_order (const ORDER *first_order, const ORDER *possible_dup)
 Check if an expression in ORDER BY or GROUP BY is a duplicate of a preceding expression. More...
 
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. More...
 
static bool can_evaluate_condition (THD *thd, Item *condition)
 Checks if a condition can be evaluated during constant folding. More...
 
static bool fold_condition_exec (THD *thd, Item *cond, Item **retcond, Item::cond_result *cond_value)
 Calls fold_condition. More...
 
bool remove_eq_conds (THD *thd, Item *cond, Item **retcond, Item::cond_result *cond_value)
 Removes const and eq items. 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...
 
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...
 
static bool ReferencesSecondaryEngineBaseTables (AccessPath *path)
 Does this path scan any base tables in a secondary engine? More...
 
bool IteratorsAreNeeded (const THD *thd, AccessPath *root_path)
 Checks if we need to create iterators for this query. More...
 
static double GetRowsNeededFromOuterTable (const AccessPath *join_path, const AccessPath *outer, double limit)
 Estimates how many rows that have to be read from the outer table of a join in order to reach the given limit. More...
 
static double EstimateRowAccessesInNestedLoopJoin (const AccessPath *join_path, const AccessPath *outer, const AccessPath *inner, double num_evaluations, double limit)
 Estimates the number of row accesses that will be performed by a nested loop join. More...
 
static double EstimateRowAccessesInItem (Item *item, double num_evaluations)
 Estimates the number of row accesses performed by the subqueries contained in an item. 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 = "<ANTIJOIN-NULL>"
 
static constexpr double kNoLimit = std::numeric_limits<double>::infinity()
 Constant used to signal that there is no limit in EstimateRowAccesses(). More...
 

Detailed Description

Optimize query expressions: Make optimal table join order, select optimal access methods per table, apply grouping, sorting and limit processing.

Function Documentation

◆ add_found_match_trig_cond()

static Item * add_found_match_trig_cond ( JOIN join,
plan_idx  idx,
Item cond,
plan_idx  root_idx 
)
static

Build a condition guarded by match variables for embedded outer joins.

When generating a condition for a table as part of an outer join condition or the WHERE condition, the table in question may also be part of an embedded outer join. In such cases, the condition must be guarded by the match variable for this embedded outer join. Such embedded outer joins may also be recursively embedded in other joins.

The function recursively adds guards for a condition ascending from tab to root_tab, which is the first inner table of an outer join, or NULL if the condition being handled is the WHERE clause.

Parameters
jointhe current join
idxindex of the first inner table for the inner-most outer join
condthe predicate to be guarded (must be set)
root_idxindex of the inner table to stop at (is NO_PLAN_IDX if this is the WHERE clause)
Returns
  • pointer to the guarded predicate, if success
  • NULL if error

◆ 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

◆ can_evaluate_condition()

static bool can_evaluate_condition ( THD thd,
Item condition 
)
static

Checks if a condition can be evaluated during constant folding.

It can be evaluated if it is constant during execution and not expensive to evaluate. If it contains a subquery, it should not be evaluated if the option OPTION_NO_SUBQUERY_DURING_OPTIMIZATION is active.

◆ 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.

◆ duplicate_order()

static bool duplicate_order ( const ORDER first_order,
const ORDER possible_dup 
)
static

Check if an expression in ORDER BY or GROUP BY is a duplicate of a preceding expression.

Parameters
first_orderthe first expression in the ORDER BY or GROUP BY clause
possible_dupthe expression that might be a duplicate of another expression preceding it the ORDER BY or GROUP BY clause
Returns
true if possible_dup is a duplicate, false otherwise

◆ eq_ref_table()

static bool eq_ref_table ( JOIN join,
ORDER start_order,
JOIN_TAB tab,
table_map cached_eq_ref_tables,
table_map eq_ref_tables 
)
static

Remove the following expressions from ORDER BY and GROUP BY: Constant expressions
Expression that only uses tables that are of type EQ_REF and the reference is in the ORDER list or if all refereed tables are of the above type.

In the following, the X field can be removed:

SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t1.a,t2.X
SELECT * FROM t1,t2,t3 WHERE t1.a=t2.a AND t2.b=t3.b ORDER BY t1.a,t3.X
const std::string SELECT("SELECT")
Name of the static privileges.
@ WHERE
Definition: sql_yacc.h:687
@ FROM
Definition: sql_yacc.h:250
@ BY
Definition: sql_yacc.h:101
Definition: table.h:286

These can't be optimized:

SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.X,t1.a
SELECT * FROM t1,t2 WHERE t1.a=t2.a AND t1.b=t2.b ORDER BY t1.a,t2.c
SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.b,t1.a
Parameters
joinjoin object
start_orderclause being analyzed (ORDER BY, GROUP BY...)
tabtable
cached_eq_ref_tablesbitmap: bit Z is set if the table of map Z was already the subject of an eq_ref_table() call for the same clause; then the return value of this previous call can be found at bit Z of 'eq_ref_tables'
eq_ref_tablessee above.

◆ 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.

◆ EstimateRowAccessesInItem()

static double EstimateRowAccessesInItem ( Item item,
double  num_evaluations 
)
static

Estimates the number of row accesses performed by the subqueries contained in an item.

The returned estimate is pessimistic, as it assumes the contained subqueries are evaluated each time the item is evaluated. If the item for example is an Item_cond_or, say, x=y OR (SELECT ...), the subquery is not evaluated if x=y is true, but the estimate does not take the selectivity of x=y into account.

Parameters
itemThe item to check.
num_evaluationsThe number of times the item is evaluated.
Returns
An estimate of the number of row accesses.

◆ EstimateRowAccessesInNestedLoopJoin()

static double EstimateRowAccessesInNestedLoopJoin ( const AccessPath join_path,
const AccessPath outer,
const AccessPath inner,
double  num_evaluations,
double  limit 
)
static

Estimates the number of row accesses that will be performed by a nested loop join.

Nested loop join reads the outer table once, and the inner table once per row in the outer table. If there is a limit on the query, it might not need to read all rows in the outer table.

Parameters
join_pathThe AccessPath representing the nested loop join.
num_evaluationsThe number of times the join will be executed.
limitThe maximum number of rows to read from the join result.
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

◆ fold_condition_exec()

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

Calls fold_condition.

If that made the condition constant for execution, simplify and fold again.

See also
fold_condition() for arguments.

◆ GetRowsNeededFromOuterTable()

static double GetRowsNeededFromOuterTable ( const AccessPath join_path,
const AccessPath outer,
double  limit 
)
static

Estimates how many rows that have to be read from the outer table of a join in order to reach the given limit.

Parameters
join_pathThe AccessPath representing the join.
outerThe AccessPath representing the outer table in the join.
limitThe maximum number of rows to read from the join result.
Returns
The number of rows to read from the outer table before reaching the limit, or kNoLimit if the entire table is expected to be read.

◆ 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

◆ part_of_refkey()

static Item * part_of_refkey ( TABLE table,
Index_lookup ref,
const Field field 
)
static

◆ reduce_cond_for_table()

static bool reduce_cond_for_table ( THD thd,
Item cond,
table_map  null_extended,
Item **  reduced 
)
static

Remove redundant predicates from condition, return the reduced condition.

A predicate of the form 'field = value' may be redundant if the (ref-) access chosen for the table use an index containing 'field', where 'value' is specified as (part of) its ref-key. This method remove such redundant predicates, thus reducing the condition, possibly eliminating it entirely.

If comparing 'values' against outer-joined tables, these are possibly 'null-extended'. Thus the usage of these values in the ref-key, is not sufficient anymore to guarantee that 'field = value' is 'TRUE'. The 'null_extended' argument hold the table_map of any such possibly null-extended tables which are excluded from the above 'reduce' logic.

Any tables referred in Item_func_trig_cond(FOUND_MATCH) conditions are aggregated into this null_extended table_map.

Parameters
thdthread handler
condThe condition to be 'reduced'.
null_extendedtable_map of possibly null-extended outer-tables.
[out]reducedThe condition with redundant predicates removed, possibly nullptr.
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

◆ ReferencesSecondaryEngineBaseTables()

static bool ReferencesSecondaryEngineBaseTables ( AccessPath path)
static

Does this path scan any base tables in a secondary engine?

◆ 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

◆ test_if_ref()

static bool test_if_ref ( THD thd,
Item_field left_item,
Item right_item,
bool *  redundant 
)
static

Identify redundant predicates.

Test if the equality predicate 'left_item = right_item' is redundant due to a REF-access already being set up on the table, where 'left_item' is part of the REF-key being used, and 'right_item' is equal to the key value specified for that field in the key. In such cases the predicate is known to be 'true' for any rows retrieved from that table. Thus it is redundant.

Parameters
thdsession context
left_itemThe Item_field possibly being part of A ref-KEY.
right_itemThe equality value specified for 'left_item'.
[out]redundanttrue if predicate is redundant, false otherwise
Returns
false if success, true if error
Note
See comments in reduce_cond_for_table() about careful usage/modifications of test_if_ref().

◆ trace_indexes_added_group_distinct()

static void trace_indexes_added_group_distinct ( Opt_trace_context trace,
const JOIN_TAB join_tab,
const Key_map  new_keys,
const char *  cause 
)
static

Print keys that were appended to join_tab->const_keys because they can be used for GROUP BY or DISTINCT to the optimizer trace.

Parameters
traceThe optimizer trace context we're adding info to
join_tabThe table the indexes cover
new_keysThe keys that are considered useful because they can be used for GROUP BY or DISTINCT
causeZero-terminated string with reason for adding indexes to const_keys
See also
add_group_and_distinct_keys()

Variable Documentation

◆ kNoLimit

constexpr double kNoLimit = std::numeric_limits<double>::infinity()
staticconstexpr

Constant used to signal that there is no limit in EstimateRowAccesses().