MySQL  8.0.19
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 <limits.h>
#include <algorithm>
#include <atomic>
#include <new>
#include <string>
#include <utility>
#include <vector>
#include "field_types.h"
#include "ft_global.h"
#include "m_ctype.h"
#include "memory_debugging.h"
#include "my_bit.h"
#include "my_bitmap.h"
#include "my_compiler.h"
#include "my_dbug.h"
#include "my_inttypes.h"
#include "my_macros.h"
#include "my_sqlcommand.h"
#include "my_sys.h"
#include "mysql/udf_registration_types.h"
#include "mysql_com.h"
#include "mysqld_error.h"
#include "sql/abstract_query_plan.h"
#include "sql/basic_row_iterators.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_sum.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_range.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/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_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/timing_iterator.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
 
struct  Key_field
 A Key_field is a descriptor of a predicate of the form (column <op> val). More...
 

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_LIST *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_select (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_LIST *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, SELECT_LEX *select_lex, 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)
 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...
 
bool substitute_gc (THD *thd, SELECT_LEX *select_lex, 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...
 
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)
 
static 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...
 
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...
 
bool build_equal_items (THD *thd, Item *cond, Item **retcond, COND_EQUAL *inherited, bool do_inherit, List< TABLE_LIST > *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_equal *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 (List< TABLE_LIST > *join_list, uint first_unused)
 Assign each nested join structure a bit in nested_join_map. More...
 
static void semijoin_types_allow_materialization (TABLE_LIST *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...
 
static uint get_tmp_table_rec_length (List< Item > &items)
 
static void 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_LIST *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...
 
static 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, JOIN_TAB *stat, 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_LIST *nested_join_table, Key_field **end, uint *and_level, SARGABLE_PARAM **sargables)
 
bool is_indexed_agg_distinct (JOIN *join, List< 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, List< 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, TABLE_REF *ref, const Field *field)
 
static bool test_if_ref (Item_field *left_item, Item *right_item)
 Identify redundant predicates. More...
 
static Itemreduce_cond_for_table (Item *cond, table_map null_extended)
 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, List< TABLE_LIST > *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, List< 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 SELECT_LEX *select)
 Checks if an Item, which is constant for execution, can be evaluated during optimization. More...
 

Variables

const char * antijoin_null_cond = "<ANTIJOIN-NULL>"
 

Detailed Description

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

Function Documentation

◆ evaluate_during_optimization()

bool evaluate_during_optimization ( const Item item,
const SELECT_LEX 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