Query Optimizer

Namespaces
namespace	anonymous_namespace{sql_select.cc}

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

Typedefs
using	Global_tables_iterator = IntrusiveListIterator< Table_ref, &Table_ref::next_global >
using	Global_tables_list = IteratorContainer< Global_tables_iterator >
	A list interface over the Table_ref::next_global pointer. More...

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 TABLE *	get_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_match *	test_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_equal> 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_TAB *	alloc_jtab_array (THD *thd, uint table_count)
static void	revise_cache_usage (JOIN_TAB *join_tab)
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...
Item_field *	get_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, 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 Item *	eliminate_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...
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...
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...
static uint	get_tmp_table_rec_length (const mem_root_deque< Item * > &items)
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_field *	merge_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)
static store_key *	get_store_key (THD *thd, Item *val, table_map used_tables, table_map const_tables, const KEY_PART_INFO *key_part, uchar *key_buff, uint maybe_null)
bool	is_show_cmd_using_system_view (THD *thd)
	Check whether the statement is a SHOW command using INFORMATION_SCHEMA system views. More...
static ulong	get_max_execution_time (THD *thd)
	Get the maximum execution time for a statement. More...
static bool	is_timer_applicable_to_statement (THD *thd)
	Check whether max statement time is applicable to statement or not. More...
bool	set_statement_timer (THD *thd)
	Set the time until the currently running statement is aborted. More...
void	reset_statement_timer (THD *thd)
	Deactivate the timer associated with the statement that was executed. More...
static bool	reads_not_secondary_columns (const LEX *lex)
	Checks if a query reads a column that is not available in the secondary engine (i.e. More...
static bool	has_secondary_engine_defined (const LEX *lex)
static bool	equal_engines (const LEX_CSTRING &engine1, const LEX_CSTRING &engine2)
static const MYSQL_LEX_CSTRING *	get_eligible_secondary_engine_from (const LEX *lex)
const handlerton *	get_secondary_engine_handlerton (const LEX *lex)
	Returns secondary_engine handler for the statement. More...
static const char *	get_secondary_engine_fail_reason (const LEX *lex)
void	set_external_engine_fail_reason (const LEX *lex, const char *reason)
	Sets the reason of failure for the statement to the external engine. More...
static void	external_engine_fail_reason (const LEX *lex)
static bool	set_secondary_engine_fail_reason (const LEX *lex, const char *reason)
static void	set_fail_reason_and_raise_error (const LEX *lex, const char *reason)
static bool	find_and_set_offload_fail_reason (const LEX *lex)
bool	validate_use_secondary_engine (const LEX *lex)
	Validates a query that uses the secondary engine. More...
void	accumulate_statement_cost (const LEX *lex)
	Calculates the cost of executing a statement, including all its subqueries and stores it in thd->m_current_query_cost. More...
static bool	retry_with_secondary_engine (THD *thd)
	Checks if a query should be retried using a secondary storage engine. More...
bool	optimize_secondary_engine (THD *thd)
	Perform query optimizations that are specific to a secondary storage engine. More...
static bool	check_locking_clause_access (THD *thd, Global_tables_list tables)
	Performs access check for the locking clause, if present. More...
bool	types_allow_materialization (Item *outer, Item *inner)
	Check if two items are compatible wrt. More...
static bool	sj_table_is_included (JOIN *join, JOIN_TAB *join_tab)
SJ_TMP_TABLE *	create_sj_tmp_table (THD *thd, JOIN *join, SJ_TMP_TABLE_TAB *first_tab, SJ_TMP_TABLE_TAB *last_tab)
	Set up the support structures (NULL bits, row offsets, etc.) for a semijoin duplicate weedout table. More...
static bool	setup_semijoin_dups_elimination (JOIN *join, uint no_jbuf_after)
	Setup the strategies to eliminate semi-join duplicates. More...
static void	destroy_sj_tmp_tables (JOIN *join)
bool	check_privileges_for_join (THD *thd, mem_root_deque< Table_ref * > *tables)
	Check privileges for column references in a JOIN expression. More...
bool	check_privileges_for_list (THD *thd, const mem_root_deque< Item * > &items, Access_bitmask privileges)
	Check privileges for column references in an item list. More...
void	calc_used_field_length (TABLE *table, bool needs_rowid, uint *p_used_fieldlength)
	Find how much space the previous read not const tables takes in cache. More...
void	calc_length_and_keyparts (Key_use *keyuse, JOIN_TAB *tab, const uint key, table_map used_tables, Key_use **chosen_keyuses, uint *length_out, uint *keyparts_out, table_map *dep_map, bool *maybe_null)
	Calculate properties of ref key: key length, number of used key parts, dependency map, possibility of null. More...
bool	init_ref (THD *thd, unsigned keyparts, unsigned length, unsigned keyno, Index_lookup *ref)
	Initialize the given TABLE_REF; setting basic fields and allocating memory for arrays. More...
bool	init_ref_part (THD *thd, unsigned part_no, Item *val, bool *cond_guard, bool null_rejecting, table_map const_tables, table_map used_tables, bool nullable, const KEY_PART_INFO *key_part_info, uchar *key_buff, Index_lookup *ref)
	Initialize a given keypart in the table ref. More...
bool	create_ref_for_key (JOIN *join, JOIN_TAB *j, Key_use *org_keyuse, table_map used_tables)
	Setup a ref access for looking up rows via an index (a key). More...
static store_key::store_key_result	type_conversion_status_to_store_key (THD *thd, type_conversion_status ts)
bool	and_conditions (Item **e1, Item *e2)
	Extend e1 by AND'ing e2 to the condition e1 points to. More...
static Item *	make_cond_for_index (Item *cond, TABLE *table, uint keyno, bool other_tbls_ok)
static Item *	make_cond_remainder (Item *cond, bool exclude_index)
bool	make_join_readinfo (JOIN *join, uint no_jbuf_after)
	Plan refinement stage: do various setup things for the executor. More...
static void	cleanup_table (TABLE *table)
ORDER *	simple_remove_const (ORDER *order, Item *where)
	Filter out ORDER BY items that are equal to constants in WHERE condition. More...
bool	equality_determines_uniqueness (const Item_func_comparison *func, const Item *v, const Item *c)
	Check if equality can be used to remove sub-clause of GROUP BY/ORDER BY. More...
bool	equality_has_no_implicit_casts (const Item_func_comparison *func, const Item *item1, const Item *item2)
	Check whether equality between two items is exact, ie., there are no implicit casts involved. More...
static bool	equal (const Item *i1, const Item *i2, const Field *f2)
bool	check_field_is_const (Item *cond, const Item *order_item, const Field *order_field, Item **const_item)
	Check if a field is equal to a constant value in a condition. More...
void	count_field_types (const Query_block *query_block, Temp_table_param *param, const mem_root_deque< Item * > &fields, bool reset_with_sum_func, bool save_sum_fields)
	Update TMP_TABLE_PARAM with count of the different type of fields. More...
bool	test_if_subpart (ORDER *a, ORDER *b)
	Return 1 if second is a subpart of first argument. More...
void	calc_group_buffer (JOIN *join, ORDER *group)
	calc how big buffer we need for comparing group entries. More...
void	free_underlaid_joins (Query_block *select)
	Free joins of subselect of this select. More...
bool	CreateFramebufferTable (THD *thd, const Temp_table_param &tmp_table_param, const Query_block &query_block, const mem_root_deque< Item * > &source_fields, const mem_root_deque< Item * > &window_output_fields, Func_ptr_array *mapping_from_source_to_window_output, Window *window)
bool	test_if_cheaper_ordering (const JOIN_TAB *tab, ORDER_with_src *order, TABLE *table, Key_map usable_keys, int ref_key, ha_rows select_limit, int *new_key, int *new_key_direction, ha_rows *new_select_limit, uint *new_used_key_parts, uint *saved_best_key_parts, double *new_read_time)
	Find a cheaper access key than a given key. More...
uint	get_index_for_order (ORDER_with_src *order, TABLE *table, ha_rows limit, AccessPath *range_scan, bool *need_sort, bool *reverse)
	Find a key to apply single table UPDATE/DELETE by a given ORDER. More...
uint	actual_key_parts (const KEY *key_info)
	Returns number of key parts depending on OPTIMIZER_SWITCH_USE_INDEX_EXTENSIONS flag. More...
uint	actual_key_flags (const KEY *key_info)
	Returns key flags depending on OPTIMIZER_SWITCH_USE_INDEX_EXTENSIONS flag. More...
join_type	calc_join_type (AccessPath *path)
	JOIN::JOIN (THD *thd_arg, Query_block *select)
bool	JOIN::alloc_ref_item_slice (THD *thd_arg, int sliceno)
	Allocate a ref_item slice, assume that slice size is in ref_items[0]. More...
bool	JOIN::alloc_indirection_slices ()
bool	JOIN::check_access_path_with_fts () const
	Checks if the chosen plan suffers from a problem related to full-text search and streaming aggregation, which is likely to cause wrong results or make the query misbehave in other ways, and raises an error if so. More...
bool	JOIN::optimize (bool finalize_access_paths)
	Optimizes one query block into a query execution plan (QEP.) More...
void	JOIN::change_to_access_path_without_in2exists ()
	If this query block was planned twice, once with and once without conditions added by in2exists, changes the root access path to the one without in2exists. More...
void	JOIN::create_access_paths_for_zero_rows ()
	Create access paths with the knowledge that there are going to be zero rows coming from tables (before aggregation); typically because we know that all of them would be filtered away by WHERE (e.g. More...
bool	JOIN::push_to_engines ()
	Handle offloading of query parts to the underlying engines, when such is supported by their implementation. More...
void	JOIN::set_plan_state (enum_plan_state plan_state_arg)
	Sets the plan's state of the JOIN. More...
bool	JOIN::alloc_qep (uint n)
void	QEP_TAB::init (JOIN_TAB *jt)
	Initializes the object from a JOIN_TAB. More...
uint	QEP_TAB::get_sj_strategy () const
uint	QEP_TAB::effective_index () const
	Return the index used for a table in a QEP. More...
uint	JOIN_TAB::get_sj_strategy () const
int	JOIN::replace_index_subquery ()
	Check whether this is a subquery that can be evaluated by index look-ups. More...
bool	JOIN::optimize_distinct_group_order ()
	Optimize DISTINCT, GROUP BY, ORDER BY clauses. More...
void	JOIN::test_skip_sort ()
	Test if an index could be used to replace filesort for ORDER BY/GROUP BY. More...
bool	JOIN::prune_table_partitions ()
	Prune partitions for all tables of a join (query block). More...
void	JOIN::adjust_access_methods ()
	An utility function - apply heuristics and optimize access methods to tables. More...
bool	JOIN::get_best_combination ()
	Set up JOIN_TAB structs according to the picked join order in best_positions. More...
table_map	JOIN::calculate_deps_of_remaining_lateral_derived_tables (table_map plan_tables, uint idx) const
	Finds the dependencies of the remaining lateral derived tables. More...
void	JOIN::update_depend_map ()
	Update the dependency map for the tables. More...
void	JOIN::update_depend_map (ORDER *order)
	Update the dependency map for the sort order. More...
bool	JOIN::update_equalities_for_sjm ()
	Update equalities and keyuse references after semi-join materialization strategy is chosen. More...
void	JOIN::set_prefix_tables ()
	Assign set of available (prefix) tables to all tables in query block. More...
bool	JOIN::make_join_plan ()
	Calculate best possible join order and initialize the join structure. More...
bool	JOIN::init_planner_arrays ()
	Initialize scratch arrays for the join order optimization. More...
bool	JOIN::propagate_dependencies ()
	Propagate dependencies between tables due to outer join relations. More...
bool	JOIN::extract_const_tables ()
	Extract const tables based on row counts. More...
bool	JOIN::extract_func_dependent_tables ()
	Extract const tables based on functional dependencies. More...
void	JOIN::update_sargable_from_const (SARGABLE_PARAM *sargables)
	Update info on indexes that can be used for search lookups as reading const tables may has added new sargable predicates. More...
bool	JOIN::estimate_rowcount ()
	Estimate the number of matched rows for each joined table. More...
void	JOIN::set_semijoin_embedding ()
	Set semi-join embedding join nest pointers. More...
bool	Sql_cmd_dml::prepare (THD *thd) override
	Command-specific resolving (doesn't include LEX::prepare()) More...
bool	Sql_cmd_select::accept (THD *thd, Select_lex_visitor *visitor) override
const MYSQL_LEX_CSTRING *	Sql_cmd_select::eligible_secondary_storage_engine () const override
	Is this statement of a type and on a form that makes it eligible for execution in a secondary storage engine? More...
bool	Sql_cmd_select::prepare_inner (THD *thd) override
	Prepare a SELECT statement. More...
bool	Sql_cmd_dml::execute (THD *thd) override
	Execute a DML statement. More...
virtual bool	Sql_cmd_dml::execute_inner (THD *thd)
	The inner parts of query optimization and execution. More...
virtual bool	Sql_cmd_dml::restore_cmd_properties (THD *thd)
	Restore command properties before execution. More...
virtual bool	Sql_cmd_dml::save_cmd_properties (THD *thd)
	Save command properties, such as prepared query details and table props. More...
Query_result *	Sql_cmd_dml::query_result () const
void	Sql_cmd_dml::set_query_result (Query_result *result)
	Set query result object for this query statement. More...
bool	Sql_cmd_select::precheck (THD *thd) override
	Perform an authorization precheck for an unprepared SELECT statement. More...
bool	Sql_cmd_select::check_privileges (THD *thd) override
	Perform an authorization check for a prepared SELECT statement. More...
bool	Sql_cmd_dml::check_all_table_privileges (THD *thd)
	Read and check privileges for all tables in a DML statement. More...
const MYSQL_LEX_CSTRING *	Sql_cmd_dml::get_eligible_secondary_engine () const
	Helper function that checks if the command is eligible for secondary engine and if that's true returns the name of that eligible secondary storage engine. More...
bool	JOIN::clear_sj_tmp_tables ()
	Remove all rows from all temp tables used by NL-semijoin runtime. More...
bool	JOIN::clear_corr_derived_tmp_tables ()
	Empties all correlated materialized derived tables. More...
void	JOIN::reset ()
	Reset the state of this join object so that it is ready for a new execution. More...
bool	JOIN::prepare_result ()
	Prepare join result. More...
void	JOIN::destroy ()
	Clean up and destroy join object. More...
void	JOIN::cleanup_item_list (const mem_root_deque< Item * > &items) const
bool	Query_block::optimize (THD *thd, bool finalize_access_paths)
	Optimize a query block and all inner query expressions. More...
bool	Query_block::check_column_privileges (THD *thd)
	Check privileges for all columns referenced from query block. More...
bool	Query_block::check_privileges_for_subqueries (THD *thd)
	Check privileges for column references in subqueries of a query block. More...
bool	JOIN::init_ref_access ()
	Initialize ref access for all tables that use it. More...
void	JOIN::set_semijoin_info ()
	Set the first_sj_inner_tab and last_sj_inner_tab fields for all tables inside the semijoin nests of the query. More...
	store_key::store_key (THD *thd, Field *to_field_arg, uchar *ptr, uchar *null_ptr_arg, uint length, Item *item_arg)
store_key_result	store_key::copy ()
	sets ignore truncation warnings mode and calls the real copy method More...
enum store_key_result	store_key_hash_item::copy_inner () override
virtual enum store_key_result	store_key::copy_inner ()
void	QEP_TAB::push_index_cond (const JOIN_TAB *join_tab, uint keyno, Opt_trace_object *trace_obj)
	Try to extract and push the index condition down to table handler. More...
bool	JOIN::setup_semijoin_materialized_table (JOIN_TAB *tab, uint tableno, POSITION *inner_pos, POSITION *sjm_pos)
	Setup the materialized table for a semi-join nest. More...
void	QEP_TAB::init_join_cache (JOIN_TAB *join_tab)
	A helper function that allocates appropriate join cache object and sets next_query_block function of previous tab. More...
void	JOIN_TAB::set_table (TABLE *t)
void	JOIN_TAB::init_join_cond_ref (Table_ref *tl)
	Sets the pointer to the join condition of Table_ref. More...
void	JOIN_TAB::cleanup ()
	Clean up associated table after query execution, including resources. More...
void	QEP_TAB::cleanup ()
void	QEP_shared_owner::qs_cleanup ()
uint	QEP_TAB::sjm_query_block_id () const
bool	QEP_shared_owner::and_with_condition (Item *tmp_cond)
	Extend join_tab->cond by AND'ing add_cond to it. More...
void	JOIN::join_free ()
	Release memory and, if possible, the open tables held by this execution plan (and nested plans). More...
void	JOIN::cleanup ()
	Cleanup this JOIN. More...
bool	JOIN::alloc_func_list ()
	Make an array of pointers to sum_functions to speed up sum_func calculation. More...
bool	JOIN::make_sum_func_list (const mem_root_deque< Item * > &fields, bool before_group_by, bool recompute=false)
	Initialize 'sum_funcs' array with all Item_sum objects. More...
bool	Query_block::change_query_result (THD *thd, Query_result_interceptor *new_result, Query_result_interceptor *old_result)
	Change the Query_result object of the query block. More...
bool	JOIN::add_having_as_tmp_table_cond (uint curr_tmp_table)
	Add having condition as a filter condition, which is applied when reading from the temp table. More...
bool	JOIN::make_tmp_tables_info ()
	Init tmp tables usage info. More...
void	JOIN::refresh_base_slice ()
	In the case of rollup (only): After the base slice list was made, we may have modified the field list to add rollup group items and sum switchers, but there may be Items with refs that refer to the base slice. More...
void	JOIN::unplug_join_tabs ()
bool	JOIN::add_sorting_to_table (uint idx, ORDER_with_src *order, bool sort_before_group)
	Add Filesort object to the given table to sort if with filesort. More...

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

Detailed Description

Macro Definition Documentation

KEY_OPTIMIZE_EXISTS

#define KEY_OPTIMIZE_EXISTS   1

KEY_OPTIMIZE_REF_OR_NULL

#define KEY_OPTIMIZE_REF_OR_NULL   2

Typedef Documentation

Global_tables_iterator

using Global_tables_iterator = IntrusiveListIterator<Table_ref, &Table_ref::next_global>

Global_tables_list

using Global_tables_list = IteratorContainer<Global_tables_iterator>

A list interface over the Table_ref::next_global pointer.

Function Documentation

JOIN()

JOIN::JOIN	(	THD *	thd_arg,
		Query_block *	select
	)

store_key()

store_key::store_key	(	THD *	thd,
		Field *	to_field_arg,
		uchar *	ptr,
		uchar *	null_ptr_arg,
		uint	length,
		Item *	item_arg
	)

accept()

bool Sql_cmd_select::accept ( THD *  thd, Select_lex_visitor *  visitor  )

overridevirtual

Reimplemented from Sql_cmd.

accumulate_statement_cost()

void accumulate_statement_cost

(

const LEX *

lex

)

Calculates the cost of executing a statement, including all its subqueries and stores it in thd->m_current_query_cost.

Parameters

lex	the statement

actual_key_flags()

uint actual_key_flags

(

const KEY *

key_info

)

Returns key flags depending on OPTIMIZER_SWITCH_USE_INDEX_EXTENSIONS flag.

Parameters

key_info

pointer to KEY structure

Returns

key flags.

actual_key_parts()

uint actual_key_parts

(

const KEY *

key_info

)

Returns number of key parts depending on OPTIMIZER_SWITCH_USE_INDEX_EXTENSIONS flag.

Parameters

key_info

pointer to KEY structure

Returns

number of key parts.

add_ft_keys()

static bool add_ft_keys ( Key_use_array *  keyuse_array, Item *  cond, table_map  usable_tables, bool  simple_match_expr  )

static

Function parses WHERE condition and add key_use for FT index into key_use array if suitable MATCH function is found.

Condition should be a set of AND expression, OR is not supported. MATCH function should be a part of simple expression. Simple expression is MATCH only function or MATCH is a part of comparison expression ('>=' or '>' operations are supported). It also sets FT_HINTS values(op_type, op_value).

Parameters

keyuse_array	Key_use array
cond	WHERE condition
usable_tables	usable tables
simple_match_expr	true if this is the first call false otherwise. if MATCH function is found at first call it means that MATCH is simple expression, otherwise, in case of AND/OR condition this parameter will be false.

Return values

true	if FT key was added to Key_use array
false	if no key was added to Key_use array

add_having_as_tmp_table_cond()

bool JOIN::add_having_as_tmp_table_cond ( uint  curr_tmp_table )

private

Add having condition as a filter condition, which is applied when reading from the temp table.

Parameters

curr_tmp_table

Table number to which having conds are added.

Returns

false if success, true if error.

add_key_equal_fields()

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  )

static

Add possible keys to array of possible keys originated from a simple predicate.

Parameters

	thd	session context
[in,out]	key_fields	Pointer to add key, if usable is incremented if key was stored in the array
	and_level	And level, to be stored in Key_field
	cond	Condition predicate
	field_item	Field used in comparison
	eq_func	True if we used =, <=> or IS NULL
	val	Value used for comparison with field Is NULL for BETWEEN and IN
	num_values	Number of elements in the array of values
	usable_tables	Tables which can be used for key optimization
	sargables	IN/OUT Array of found sargable candidates

Note

If field items f1 and f2 belong to the same multiple equality and a key is added for f1, the the same key is added for f2.

Returns

false if success, true if error

add_key_field()

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  )

static

Add a possible key to array of possible keys if it's usable as a key.

Parameters

[in,out]	key_fields	Used as an input parameter in the sense that it is a pointer to a pointer to a memory area where an array of Key_field objects will stored. It is used as an out parameter in the sense that the pointer will be updated to point beyond the last Key_field written.
	thd	session context
	and_level	And level, to be stored in Key_field
	cond	Condition predicate
	item_field	Field used in comparison
	eq_func	True if we used =, <=> or IS NULL
	value	Array of values used for comparison with field
	num_values	Number of elements in the array of values
	usable_tables	Tables which can be used for key optimization
	sargables	IN/OUT Array of found sargable candidates. Will be ignored in case eq_func is true.

Note

If we are doing a NOT NULL comparison on a NOT NULL field in a outer join table, we store this to be able to do not exists optimization later.

Returns

false if success, true if error

add_key_fields()

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.

This function, along with the other add_key_* functions, make up a recursive procedure that analyzes a condition expression (a tree of AND and OR predicates) and does many things.

Parameters

	thd	session context
	join	The query block involving the condition.
[in,out]	key_fields	Start of memory buffer, see below.
[in,out]	and_level	Current 'and level', see below.
	cond	The conditional expression to analyze.
	usable_tables	Tables not in this bitmap will not be examined.
[in,out]	sargables	End of memory buffer, see below.

Returns

false if success, true if error

This documentation is the result of reverse engineering and may therefore not capture the full gist of the procedure, but it is known to do the following:

• Populate a raw memory buffer from two directions at the same time. An 'array' of Key_field objects fill the buffer from low to high addresses whilst an 'array' of SARGABLE_PARAM's fills the buffer from high to low addresses. At the first call to this function, it is assumed that key_fields points to the beginning of the buffer and sargables point to the end (except for a poor-mans 'null element' at the very end).
• Update a number of properties in the JOIN_TAB's that can be used to find search keys (sargables).
  • JOIN_TAB::keys
  • JOIN_TAB::key_dependent
  • JOIN_TAB::const_keys (dictates if the range optimizer will be run later.)

The Key_field objects are marked with something called an 'and_level', which does not correspond to their nesting depth within the expression tree. It is rather a tag to group conjunctions together. For instance, in the conditional expression

a = 0 AND b = 0

two Key_field's are produced, both having an and_level of 0.

In an expression such as

a = 0 AND b = 0 OR a = 1

three Key_field's are produced, the first two corresponding to 'a = 0' and 'b = 0', respectively, both with and_level 0. The third one corresponds to 'a = 1' and has an and_level of 1.

A separate function, merge_key_fields() performs ref access validation on the Key_field array on the recursice ascent. If some Key_field's cannot be used for ref access, the key_fields pointer is rolled back. All other modifications to the query plan remain.

add_key_fields_for_nj()

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  )

static

add_key_part()

static bool add_key_part ( Key_use_array *  keyuse_array, Key_field *  key_field  )

static

add_loose_index_scan_and_skip_scan_keys()

static void add_loose_index_scan_and_skip_scan_keys ( JOIN *  join, JOIN_TAB *  join_tab  )

static

Discover the indexes that might be used for GROUP BY or DISTINCT queries or indexes that might be used for SKIP SCAN.

If the query has a GROUP BY clause, find all indexes that contain all GROUP BY fields, and add those indexes to join_tab->const_keys and join_tab->keys.

If the query has a DISTINCT clause, find all indexes that contain all SELECT fields, and add those indexes to join_tab->const_keys and join_tab->keys. This allows later on such queries to be processed by a GroupIndexSkipScanIterator.

If the query does not have GROUP BY clause or any aggregate function the function collects possible keys to use for skip scan access.

Note that indexes that are not usable for resolving GROUP BY/DISTINCT may also be added in some corner cases. For example, an index covering 'a' and 'b' is not usable for the following query but is still added: "SELECT DISTINCT a+b FROM t1". This is not a big issue because a) although the optimizer will consider using the index, it will not chose it (so minor calculation cost added but not wrong result) and b) it applies only to corner cases.

Parameters

join	the current join
join_tab	joined table

add_not_null_conds()

static bool add_not_null_conds ( JOIN *  join )

static

Add to join_tab[i]->condition() "table.field IS NOT NULL" conditions we've inferred from ref/eq_ref access performed.

This function is a part of "Early NULL-values filtering for ref access" optimization.

Example of this optimization: For query SELECT * FROM t1,t2 WHERE t2.key=t1.field
and plan " any-access(t1), ref(t2.key=t1.field) "
add "t1.field IS NOT NULL" to t1's table condition.
Description of the optimization:

We look through equalities chosen to perform ref/eq_ref access, pick equalities that have form "tbl.part_of_key = othertbl.field" (where othertbl is a non-const table and othertbl.field may be NULL) and add them to conditions on corresponding tables (othertbl in this example).

Exception from that is the case when referred_tab->join != join. I.e. don't add NOT NULL constraints from any embedded subquery. Consider this query:

SELECT A.f2 FROM t1 LEFT JOIN t2 A ON A.f2 = f1
WHERE A.f3=(SELECT MIN(f3) FROM  t2 C WHERE A.f4 = C.f4) OR A.f3 IS NULL;

Here condition A.f3 IS NOT NULL is going to be added to the WHERE condition of the embedding query. Another example: SELECT * FROM t10, t11 WHERE (t10.a < 10 OR t10.a IS NULL) AND t11.b <=> t10.b AND (t11.a = (SELECT MAX(a) FROM t12 WHERE t12.b = t10.a )); Here condition t10.a IS NOT NULL is going to be added. In both cases addition of NOT NULL condition will erroneously reject some rows of the result set. referred_tab->join != join constraint would disallow such additions.

This optimization doesn't affect the choices that ref, range, or join optimizer make. This was intentional because this was added after 4.1 was GA.

Implementation overview

1. update_ref_and_keys() accumulates info about null-rejecting predicates in in Key_field::null_rejecting 1.1 add_key_part saves these to Key_use.
2. create_ref_for_key copies them to Index_lookup.
3. add_not_null_conds adds "x IS NOT NULL" to join_tab->m_condition of appropriate JOIN_TAB members.

Returns

false on success, true on error

add_sorting_to_table()

bool JOIN::add_sorting_to_table	(	uint	idx,
		ORDER_with_src *	sort_order,
		bool	sort_before_group
	)

Add Filesort object to the given table to sort if with filesort.

Parameters

idx	JOIN_TAB's position in the qep_tab array. The created Filesort object gets attached to this.
sort_order	List of expressions to sort the table by
sort_before_group	If true, this sort happens before grouping is done (potentially as a step of grouping itself), so any wrapped rollup group items should be unwrapped.

Note

This function moves tab->select, if any, to filesort->select

Returns

false on success, true on OOM

adjust_access_methods()

void JOIN::adjust_access_methods ( )

private

An utility function - apply heuristics and optimize access methods to tables.

Note

Side effect - this function could set 'Impossible WHERE' zero result.

Currently this function can change REF to RANGE and ALL to INDEX scan if latter is considered to be better (not cost-based) than the former.

Note

Side effect - this function could set 'Impossible WHERE' zero result.

alloc_func_list()

bool JOIN::alloc_func_list

(

)

Make an array of pointers to sum_functions to speed up sum_func calculation.

Return values

0	ok
1	Error

alloc_indirection_slices()

bool JOIN::alloc_indirection_slices ( )

private

alloc_jtab_array()

static JOIN_TAB * alloc_jtab_array ( THD *  thd, uint  table_count  )

static

alloc_qep()

bool JOIN::alloc_qep ( uint  n )

private

alloc_ref_item_slice()

bool JOIN::alloc_ref_item_slice	(	THD *	thd_arg,
		int	sliceno
	)

Allocate a ref_item slice, assume that slice size is in ref_items[0].

Parameters

thd_arg	thread handler
sliceno	The slice number to allocate in JOIN::ref_items

Returns

false if success, true if error

and_conditions()

bool and_conditions	(	Item **	e1,
		Item *	e2
	)

Extend e1 by AND'ing e2 to the condition e1 points to.

The resulting condition is fixed. Requirement: the input Items must already have been fixed. This is a variant of and_items(); it is intended for use in the optimizer phase.

Parameters

[in,out]	e1	Pointer to condition that will be extended with e2
	e2	Condition that will extend e1

Return values

true	if there was a memory allocation error, in which case e1 remains unchanged
false	otherwise

and_with_condition()

bool QEP_shared_owner::and_with_condition

(

Item *

add_cond

)

Extend join_tab->cond by AND'ing add_cond to it.

Parameters

add_cond

The condition to AND with the existing cond for this JOIN_TAB

Return values

true	if there was a memory allocation error
false	otherwise

build_bitmap_for_nested_joins()

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.

Parameters

join_list	List of tables
first_unused	Number of first unused bit in nested_join_map before the call

Note

This function is called after simplify_joins(), when there are no redundant nested joins. We cannot have more nested joins in a query block than there are tables, so as long as the number of bits in nested_join_map is not less than the maximum number of tables in a query block, nested_join_map can never overflow.

Returns

First unused bit in nested_join_map after the call.

build_equal_items()

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.

The function first applies the build_equal_items_for_cond function to build all multiple equalities for condition cond utilizing equalities referred through the parameter inherited. The extended set of equalities is returned in the structure referred by the cond_equal_ref parameter. After this the function calls itself recursively for all join conditions whose direct references can be found in join_list and who inherit directly the multiple equalities just having built.

Note

The join condition used in an outer join operation inherits all equalities from the join condition of the embedding join, if there is any, or otherwise - from the where condition. This fact is not obvious, but presumably can be proved. Consider the following query:

SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t1.a=t3.a AND t2.a=t4.a
  WHERE t1.a=t2.a;

If the join condition in the query inherits =(t1.a,t2.a), then we can build the multiple equality =(t1.a,t2.a,t3.a,t4.a) that infers the equality t3.a=t4.a. Although the join condition t1.a=t3.a AND t2.a=t4.a AND t3.a=t4.a is not equivalent to the one in the query the latter can be replaced by the former: the new query will return the same result set as the original one.

Interesting that multiple equality =(t1.a,t2.a,t3.a,t4.a) allows us to use t1.a=t3.a AND t3.a=t4.a under the join condition:

SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t1.a=t3.a AND t3.a=t4.a
  WHERE t1.a=t2.a

This query equivalent to:

SELECT * FROM (t1 LEFT JOIN (t3,t4) ON t1.a=t3.a AND t3.a=t4.a),t2
  WHERE t1.a=t2.a

Similarly the original query can be rewritten to the query:

SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t2.a=t4.a AND t3.a=t4.a
  WHERE t1.a=t2.a

that is equivalent to:

SELECT * FROM (t2 LEFT JOIN (t3,t4)ON t2.a=t4.a AND t3.a=t4.a), t1
  WHERE t1.a=t2.a

Thus, applying equalities from the where condition we basically can get more freedom in performing join operations. Although we don't use this property now, it probably makes sense to use it in the future.

Parameters

	thd	Thread handler
	cond	condition to build the multiple equalities for
[out]	retcond	Returned condition
	inherited	path to all inherited multiple equality items
	do_inherit	whether or not to inherit equalities from other parts of the condition
	join_list	list of join tables that the condition refers to
[out]	cond_equal_ref	pointer to the structure to place built equalities in

Returns

false if success, true if error

build_equal_items_for_cond()

static bool build_equal_items_for_cond ( THD *  thd, Item *  cond, Item **  retcond, COND_EQUAL *  inherited, bool  do_inherit  )

static

Replace all equality predicates in a condition by multiple equality items.

At each 'and' level the function detects items for equality predicates and replaces them by a set of multiple equality items of class Item_equal, taking into account inherited equalities from upper levels. If an equality predicate is used not in a conjunction it's just replaced by a multiple equality predicate. For each 'and' level the function set a pointer to the inherited multiple equalities in the cond_equal field of the associated object of the type Item_cond_and. The function also traverses the cond tree and for each field reference sets a pointer to the multiple equality item containing the field, if there is any. If this multiple equality equates fields to a constant the function replaces the field reference by the constant in the cases when the field is not of a string type or when the field reference is just an argument of a comparison predicate. The function also determines the maximum number of members in equality lists of each Item_cond_and object assigning it to thd->lex->current_query_block()->max_equal_elems.

Note

Multiple equality predicate =(f1,..fn) is equivalent to the conjunction of f1=f2, .., fn-1=fn. It substitutes any inference from these equality predicates that is equivalent to the conjunction. Thus, =(a1,a2,a3) can substitute for ((a1=a3) AND (a2=a3) AND (a2=a1)) as it is equivalent to ((a1=a2) AND (a2=a3)). The function always makes a substitution of all equality predicates occurred in a conjunction for a minimal set of multiple equality predicates. This set can be considered as a canonical representation of the sub-conjunction of the equality predicates. E.g. (t1.a=t2.b AND t2.b>5 AND t1.a=t3.c) is replaced by (=(t1.a,t2.b,t3.c) AND t2.b>5), not by (=(t1.a,t2.b) AND =(t1.a,t3.c) AND t2.b>5); while (t1.a=t2.b AND t2.b>5 AND t3.c=t4.d) is replaced by (=(t1.a,t2.b) AND =(t3.c=t4.d) AND t2.b>5), but if additionally =(t4.d,t2.b) is inherited, it will be replaced by (=(t1.a,t2.b,t3.c,t4.d) AND t2.b>5)

The function performs the substitution in a recursive descent of the condition tree, passing to the next AND level a chain of multiple equality predicates which have been built at the upper levels. The Item_equal items built at the level are attached to other non-equality conjuncts as a sublist. The pointer to the inherited multiple equalities is saved in the and condition object (Item_cond_and). This chain allows us for any field reference occurrence to easily find a multiple equality that must be held for this occurrence. For each AND level we do the following:

• scan it for all equality predicate (=) items
• join them into disjoint Item_equal() groups
• process the included OR conditions recursively to do the same for lower AND levels.

We need to do things in this order as lower AND levels need to know about all possible Item_equal objects in upper levels.

Parameters

	thd	thread handle
	cond	condition(expression) where to make replacement
[out]	retcond	returned condition
	inherited	path to all inherited multiple equality items
	do_inherit	whether or not to inherit equalities from other parts of the condition

Returns

false if success, true if error

calc_group_buffer()

void calc_group_buffer	(	JOIN *	join,
		ORDER *	group
	)

calc how big buffer we need for comparing group entries.

calc_join_type()

join_type calc_join_type

(

AccessPath *

path

)

Returns

join type according to quick select type used (which must be a form of range scan, or asserts will happen)

calc_length_and_keyparts()

void calc_length_and_keyparts	(	Key_use *	keyuse,
		JOIN_TAB *	tab,
		const uint	key,
		table_map	used_tables,
		Key_use **	chosen_keyuses,
		uint *	length_out,
		uint *	keyparts_out,
		table_map *	dep_map,
		bool *	maybe_null
	)

Calculate properties of ref key: key length, number of used key parts, dependency map, possibility of null.

After calling this function thd::is_error() needs to be checked, as it can set an error.

Parameters

	keyuse	Array of keys to consider
	tab	join_tab to calculate ref parameters for
	key	number of the key to use
	used_tables	tables read prior to this table
[out]	chosen_keyuses	when given, this function will fill array with chosen keyuses
[out]	length_out	calculated length of the ref
[out]	keyparts_out	calculated number of used keyparts
[out]	dep_map	when given, calculated dependency map
[out]	maybe_null	when given, calculated maybe_null property

calc_used_field_length()

void calc_used_field_length	(	TABLE *	table,
		bool	needs_rowid,
		uint *	p_used_fieldlength
	)

Find how much space the previous read not const tables takes in cache.

calculate_deps_of_remaining_lateral_derived_tables()

table_map JOIN::calculate_deps_of_remaining_lateral_derived_tables	(	table_map	plan_tables,
		uint	idx
	)		const

Finds the dependencies of the remaining lateral derived tables.

Parameters

plan_tables	map of all tables that the planner is processing (tables already in plan and tables to be added to plan).
idx	index of the table which the planner is currently considering.

Returns

A map of the dependencies of the remaining lateral derived tables (from best_ref[idx] and on).

calculate_materialization_costs()

static void calculate_materialization_costs ( JOIN *  join, Table_ref *  sj_nest, uint  n_tables, Semijoin_mat_optimize *  sjm  )

static

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.

Parameters

	join	JOIN where plan can be found
	sj_nest	sj materialization nest (NULL if subquery materialization)
	n_tables	number of to-be-materialized tables
[out]	sjm	where computed costs will be stored

Note

that this function modifies join->map2table, which has to be filled correctly later.

can_switch_from_ref_to_range()

static bool can_switch_from_ref_to_range ( THD *  thd, JOIN_TAB *  tab, enum_order  ordering, bool  recheck_range  )

static

A helper function to check whether it's better to use range than ref.

Heuristic: Switch from 'ref' to 'range' access if 'range' access can utilize more keyparts than 'ref' access. Conditions for doing switching:

1) Range access is possible 2) 'ref' access and 'range' access uses the same index 3) Used parts of key shouldn't have nullable parts & ref_or_null isn't used. 4) 'ref' access depends on a constant, not a value read from a table earlier in the join sequence.

Rationale: if 'ref' depends on a value from another table, the join condition is not used to limit the rows read by 'range' access (that would require dynamic range - 'Range checked for each record'). In other words, if 'ref' depends on a value from another table, we have a query with conditions of the form

this_table.idx_col1 = other_table.col AND <<- used by 'ref' this_table.idx_col1 OP <const> AND <<- used by 'range' this_table.idx_col2 OP <const> AND ... <<- used by 'range'

and an index on (idx_col1,idx_col2,...). But the fact that 'range' access uses more keyparts does not mean that it is more selective than 'ref' access because these access types utilize different parts of the query condition. We therefore trust the cost based choice made by best_access_path() instead of forcing a heuristic choice here. 5) 'range' access uses more keyparts than 'ref' access 6) ORDER BY might make range better than table scan: Check possibility of range scan even if it was previously deemed unviable (for example when table scan was estimated to be cheaper). If yes, range-access should be chosen only for larger key length.

Parameters

thd	To re-run range optimizer.
tab	JOIN_TAB to check
ordering	Used as a parameter to call test_quick_select.
recheck_range	Check possibility of range scan even if it is currently unviable.

Returns

true Range is better than ref

false Ref is better or switch isn't possible

change_cond_ref_to_const()

static bool change_cond_ref_to_const ( THD *  thd, I_List< COND_CMP > *  save_list, Item *  and_father, Item *  cond, Item *  field, Item *  value  )

static

change field = field to field = const for each found field = const in the and_level

Parameters

thd	Thread handler
save_list	saved list of COND_CMP
and_father	father of AND op
cond	Condition where fields are replaced with constant values
field	The field that will be substituted
value	The substitution value

Returns

false if success, true if error

change_query_result()

bool Query_block::change_query_result	(	THD *	thd,
		Query_result_interceptor *	new_result,
		Query_result_interceptor *	old_result
	)

Change the Query_result object of the query block.

If old_result is not used, forward the call to the current Query_result in case it is a wrapper around old_result.

Call prepare() on the new Query_result if we decide to use it.

Parameters

thd	Thread handle
new_result	New Query_result object
old_result	Old Query_result object (NULL to force change)

Return values

false	Success
true	Error

change_to_access_path_without_in2exists()

void JOIN::change_to_access_path_without_in2exists

(

)

If this query block was planned twice, once with and once without conditions added by in2exists, changes the root access path to the one without in2exists.

If not (ie., there were never any such conditions in the first place), does nothing.

check_access_path_with_fts()

bool JOIN::check_access_path_with_fts ( ) const

private

Checks if the chosen plan suffers from a problem related to full-text search and streaming aggregation, which is likely to cause wrong results or make the query misbehave in other ways, and raises an error if so.

Only to be called for queries with full-text search and GROUP BY WITH ROLLUP.

If there are calls to MATCH in the SELECT list (including the hidden elements lifted there from other clauses), and they are not inside an aggregate function, the results of the MATCH clause need to be materialized before streaming aggregation is performed. The hypergraph optimizer adds a materialization step before aggregation if needed (see CreateStreamingAggregationPath()), but the old optimizer only does that for implicitly grouped queries. For explicitly grouped queries, it instead disables streaming aggregation for the queries that would need a materialization step to work correctly (see JOIN::test_skip_sort()).

For explicitly grouped queries WITH ROLLUP, however, streaming aggregation is currently the only alternative. In many cases it still works correctly because an intermediate materialization step has been added for some other reason, typically for a sort. For now, in those cases where a materialization step has not been added, we raise an error instead of going ahead with an invalid execution plan.

Returns

true if an error was raised.

check_all_table_privileges()

bool Sql_cmd_dml::check_all_table_privileges ( THD *  thd )

protected

Read and check privileges for all tables in a DML statement.

Parameters

thd	thread handler

Returns

false if success, true if false

check_column_privileges()

bool Query_block::check_column_privileges

(

THD *

thd

)

Check privileges for all columns referenced from query block.

Check privileges for all columns referenced from this query block.

Also check privileges for referenced subqueries.

Parameters

thd	thread handler

Returns

false if success, true if error (insufficient privileges)

check_equality()

static bool check_equality ( THD *  thd, Item *  item, COND_EQUAL *  cond_equal, List< Item > *  eq_list, bool *  equality  )

static

Eliminate row equalities and form multiple equalities predicates.

This function checks whether the item is a simple equality i.e. the one that equates a field with another field or a constant (field=field_item or field=constant_item), or, a row equality. For a simple equality the function looks for a multiple equality in the lists referenced directly or indirectly by cond_equal inferring the given simple equality. If it doesn't find any, it builds/expands multiple equality that covers the predicate. Row equalities are eliminated substituted for conjunctive regular equalities which are treated in the same way as original equality predicates.

Parameters

	thd	thread handle
	item	predicate to process
	cond_equal	multiple equalities that must hold together with the predicate
	eq_list	results of conversions of row equalities that are not simple enough to form multiple equalities
[out]	equality	true if re-writing rules have been applied false otherwise, i.e. if the predicate is not an equality, or if the equality is neither a simple nor a row equality

Returns

false if success, true if error

Note

If the equality was created by IN->EXISTS, it may be removed later by subquery materialization. So we don't mix this possibly temporary equality with others; if we let it go into a multiple-equality (Item_equal), then we could not remove it later. There is however an exception: if the outer expression is a constant, it is safe to leave the equality even in materialization; all it can do is preventing NULL/FALSE distinction but if such distinction mattered the equality would be in a triggered condition so we would not come to this function. And injecting constants is good because it makes the materialized table smaller.

check_field_is_const()

bool check_field_is_const	(	Item *	cond,
		const Item *	order_item,
		const Field *	order_field,
		Item **	const_item
	)

Check if a field is equal to a constant value in a condition.

Parameters

	cond	condition to search within
	order_item	Item to find in condition (if order_field is NULL)
	order_field	Field to find in condition (if order_item is NULL)
[out]	const_item	Used in calculation with conjunctive predicates, must be NULL in outer-most call.

Returns

true if the field is a constant value in condition, false otherwise

check_locking_clause_access()

static bool check_locking_clause_access ( THD *  thd, Global_tables_list  tables  )

static

Performs access check for the locking clause, if present.

Parameters

thd	Current session, used for checking access and raising error.
tables	Tables in the query's from clause.

Return values

true	There was a locking clause and access was denied. An error has been raised.
false	There was no locking clause or access was allowed to it. This is always returned in an embedded build.

check_privileges()

bool Sql_cmd_select::check_privileges ( THD *  thd )

overrideprotectedvirtual

Perform an authorization check for a prepared SELECT statement.

Implements Sql_cmd_dml.

Reimplemented in Sql_cmd_show, Sql_cmd_show_schema_base, Sql_cmd_show_table_base, Sql_cmd_show_routine_code, Sql_cmd_show_binlog_events, Sql_cmd_show_binlogs, Sql_cmd_show_create_database, Sql_cmd_show_create_event, Sql_cmd_show_create_function, Sql_cmd_show_create_procedure, Sql_cmd_show_create_table, Sql_cmd_show_create_trigger, Sql_cmd_show_create_user, Sql_cmd_show_databases, Sql_cmd_show_engine_logs, Sql_cmd_show_engine_mutex, Sql_cmd_show_engine_status, Sql_cmd_show_events, Sql_cmd_show_grants, Sql_cmd_show_master_status, Sql_cmd_show_processlist, Sql_cmd_show_relaylog_events, Sql_cmd_show_replicas, and Sql_cmd_show_replica_status.

check_privileges_for_join()

bool check_privileges_for_join	(	THD *	thd,
		mem_root_deque< Table_ref * > *	tables
	)

Check privileges for column references in a JOIN expression.

Check privileges for all columns referenced from join expression.

Parameters

thd	thread handler
tables	list of joined tables

Returns

false if success, true if error (insufficient privileges)

check_privileges_for_list()

bool check_privileges_for_list	(	THD *	thd,
		const mem_root_deque< Item * > &	items,
		Access_bitmask	privileges
	)

Check privileges for column references in an item list.

Check privileges for all columns referenced from an expression list.

Parameters

thd	thread handler
items	list of items
privileges	the required privileges

Returns

false if success, true if error (insufficient privileges)

check_privileges_for_subqueries()

bool Query_block::check_privileges_for_subqueries

(

THD *

thd

)

Check privileges for column references in subqueries of a query block.

Parameters

thd	thread handler

Returns

false if success, true if error (insufficient privileges)

check_row_equality()

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  )

static

Convert row equalities into a conjunction of regular equalities.

The function converts a row equality of the form (E1,...,En)=(E'1,...,E'n) into a list of equalities E1=E'1,...,En=E'n. For each of these equalities Ei=E'i the function checks whether it is a simple equality or a row equality. If it is a simple equality it is used to expand multiple equalities of cond_equal. If it is a row equality it converted to a sequence of equalities between row elements. If Ei=E'i is neither a simple equality nor a row equality the item for this predicate is added to eq_list.

Parameters

	thd	thread handle
	left_row	left term of the row equality to be processed
	right_row	right term of the row equality to be processed
	cond_equal	multiple equalities that must hold together with the predicate
	eq_list	results of conversions of row equalities that are not simple enough to form multiple equalities
[out]	simple_equality	true if the row equality is composed of only simple equalities.

Returns

false if conversion succeeded, true if any error.

check_simple_equality()

static bool check_simple_equality ( THD *  thd, Item *  left_item, Item *  right_item, Item *  item, COND_EQUAL *  cond_equal, bool *  simple_equality  )

static

Check whether an equality can be used to build multiple equalities.

This function first checks whether the equality (left_item=right_item) is a simple equality i.e. one that equates a field with another field or a constant (field=field_item or field=const_item). If this is the case the function looks for a multiple equality in the lists referenced directly or indirectly by cond_equal inferring the given simple equality. If it doesn't find any, it builds a multiple equality that covers the predicate, i.e. the predicate can be inferred from this multiple equality. The built multiple equality could be obtained in such a way: create a binary multiple equality equivalent to the predicate, then merge it, if possible, with one of old multiple equalities. This guarantees that the set of multiple equalities covering equality predicates will be minimal.

EXAMPLE: For the where condition

WHERE a=b AND b=c AND
      (b=2 OR f=e)

the check_equality will be called for the following equality predicates a=b, b=c, b=2 and f=e.

• For a=b it will be called with *cond_equal=(0,[]) and will transform cond_equal into (0,[Item_equal(a,b)]).
• For b=c it will be called with *cond_equal=(0,[Item_equal(a,b)]) and will transform *cond_equal into CE=(0,[Item_equal(a,b,c)]).
• For b=2 it will be called with *cond_equal=(ptr(CE),[]) and will transform *cond_equal into (ptr(CE),[Item_equal(2,a,b,c)]).
• For f=e it will be called with *cond_equal=(ptr(CE), []) and will transform *cond_equal into (ptr(CE),[Item_equal(f,e)]).

Note

Now only fields that have the same type definitions (verified by the Field::eq_def method) are placed to the same multiple equalities. Because of this some equality predicates are not eliminated and can be used in the constant propagation procedure. We could weaken the equality test as soon as at least one of the equal fields is to be equal to a constant. It would require a more complicated implementation: we would have to store, in general case, its own constant for each fields from the multiple equality. But at the same time it would allow us to get rid of constant propagation completely: it would be done by the call to build_equal_items_for_cond.

The implementation does not follow exactly the above rules to build a new multiple equality for the equality predicate. If it processes the equality of the form field1=field2, it looks for multiple equalities me1 containing field1 and me2 containing field2. If only one of them is found the function expands it with the lacking field. If multiple equalities for both fields are found they are merged. If both searches fail a new multiple equality containing just field1 and field2 is added to the existing multiple equalities. If the function processes the predicate of the form field1=const, it looks for a multiple equality containing field1. If found, the function checks the constant of the multiple equality. If the value is unknown, it is setup to const. Otherwise the value is compared with const and the evaluation of the equality predicate is performed. When expanding/merging equality predicates from the upper levels the function first copies them for the current level. It looks acceptable, as this happens rarely. The implementation without copying would be much more complicated.

Parameters

	thd	Thread handler
	left_item	left term of the equality to be checked
	right_item	right term of the equality to be checked
	item	equality item if the equality originates from a condition predicate, 0 if the equality is the result of row elimination
	cond_equal	multiple equalities that must hold together with the equality
[out]	simple_equality	true if the predicate is a simple equality predicate to be used for building multiple equalities false otherwise

Returns

false if success, true if error

check_skip_records_in_range_qualification()

static bool check_skip_records_in_range_qualification ( JOIN_TAB *  tab, THD *  thd  )

static

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.

b) No subquery is present. c) Fulltext Index is not involved. d) No GROUP-BY or DISTINCT clause. e.I) No ORDER-BY clause or e.II) The given index can provide the order.

F2) Not applicable to multi-table query.

Parameters

tab	JOIN_TAB object.
thd	THD object.

cleanup() [1/3]

void QEP_TAB::cleanup

(

void

)

cleanup() [2/3]

void JOIN::cleanup

(

void

)

Cleanup this JOIN.

Free resources of given join.

Not a full cleanup. reusable?

Note

With subquery this function definitely will be called several times, but even for simple query it can be called several times.

cleanup() [3/3]

void JOIN_TAB::cleanup

(

void

)

Clean up associated table after query execution, including resources.

Cleanup table of join operation.

cleanup_item_list()

void JOIN::cleanup_item_list ( const mem_root_deque< Item * > &  items ) const

private

cleanup_table()

static void cleanup_table ( TABLE *  table )

static

clear_corr_derived_tmp_tables()

bool JOIN::clear_corr_derived_tmp_tables

(

)

Empties all correlated materialized derived tables.

clear_sj_tmp_tables()

bool JOIN::clear_sj_tmp_tables

(

)

Remove all rows from all temp tables used by NL-semijoin runtime.

All rows must be removed from all temporary tables before every join re-execution.

compare_fields_by_table_order()

static int compare_fields_by_table_order ( Item_field *  field1, Item_field *  field2, JOIN_TAB **  table_join_idx  )

static

Compare field items by table order in the execution plan.

field1 considered as better than field2 if the table containing field1 is accessed earlier than the table containing field2. The function finds out what of two fields is better according this criteria.

Parameters

field1	first field item to compare
field2	second field item to compare
table_join_idx	index to tables determining table order

Return values

-1	if field1 is better than field2
1	if field2 is better than field1
0	otherwise

copy()

store_key::store_key_result store_key::copy

(

)

sets ignore truncation warnings mode and calls the real copy method

this function makes sure truncation warnings when preparing the key buffers don't end up as errors (because of an enclosing INSERT/UPDATE).

copy_inner() [1/2]

enum store_key::store_key_result store_key::copy_inner ( )

protectedvirtual

Reimplemented in anonymous_namespace{sql_select.cc}::store_key_const_item, anonymous_namespace{sql_select.cc}::store_key_json_item, and store_key_hash_item.

copy_inner() [2/2]

enum store_key::store_key_result store_key_hash_item::copy_inner ( )

overrideprotectedvirtual

Reimplemented from store_key.

count_field_types()

void count_field_types	(	const Query_block *	query_block,
		Temp_table_param *	param,
		const mem_root_deque< Item * > &	fields,
		bool	reset_with_sum_func,
		bool	save_sum_fields
	)

Update TMP_TABLE_PARAM with count of the different type of fields.

This function counts the number of fields, functions and sum functions (items with type SUM_FUNC_ITEM) for use by create_tmp_table() and stores it in the Temp_table_param object. It also updates the allow_group_via_temp_table property if needed.

Parameters

query_block	Query_block of query
param	Description of temp table
fields	List of fields to count
reset_with_sum_func	Whether to reset with_sum_func of func items
save_sum_fields	Count in the way create_tmp_table() expects when given the same parameter.

create_access_paths_for_zero_rows()

void JOIN::create_access_paths_for_zero_rows

(

)

Create access paths with the knowledge that there are going to be zero rows coming from tables (before aggregation); typically because we know that all of them would be filtered away by WHERE (e.g.

SELECT * FROM t1 WHERE 1=2). This will normally yield no output rows, but if we have implicit aggregation, it might yield a single one.

create_ref_for_key()

bool create_ref_for_key	(	JOIN *	join,
		JOIN_TAB *	j,
		Key_use *	org_keyuse,
		table_map	used_tables
	)

Setup a ref access for looking up rows via an index (a key).

Parameters

join	The join object being handled
j	The join_tab which will have the ref access populated
org_keyuse	First key part of (possibly multi-part) key
used_tables	Bitmap of available tables

Returns

False if success, True if error

Given a Key_use structure that specifies the fields that can be used for index access, this function creates and set up the structure used for index look up via one of the access methods {JT_FT, JT_CONST, JT_REF_OR_NULL, JT_REF, JT_EQ_REF} for the plan operator 'j'. Generally the function sets up the structure j->ref (of type Index_lookup), and the access method j->type.

Note

We cannot setup fields used for ref access before we have sorted the items within multiple equalities according to the final order of the tables involved in the join operation. Currently, this occurs in

See also

substitute_for_best_equal_field(). The exception is ref access for const tables, which are fixed before the greedy search planner is invoked.

create_sj_tmp_table()

SJ_TMP_TABLE * create_sj_tmp_table	(	THD *	thd,
		JOIN *	join,
		SJ_TMP_TABLE_TAB *	first_tab,
		SJ_TMP_TABLE_TAB *	last_tab
	)

Set up the support structures (NULL bits, row offsets, etc.) for a semijoin duplicate weedout table.

The object is allocated on the given THD's MEM_ROOT.

Parameters

thd	the THD to allocate the object on
join	the JOIN that will own the temporary table (ie., has the responsibility to destroy it after use)
first_tab	first table in row key (inclusive)
last_tab	last table in row key (exclusive)

CreateFramebufferTable()

bool CreateFramebufferTable	(	THD *	thd,
		const Temp_table_param &	tmp_table_param,
		const Query_block &	query_block,
		const mem_root_deque< Item * > &	source_fields,
		const mem_root_deque< Item * > &	window_output_fields,
		Func_ptr_array *	mapping_from_source_to_window_output,
		Window *	window
	)

destroy()

void JOIN::destroy

(

)

Clean up and destroy join object.

destroy_sj_tmp_tables()

static void destroy_sj_tmp_tables ( JOIN *  join )

static

effective_index()

uint QEP_TAB::effective_index

(

)

const

Return the index used for a table in a QEP.

Returns

the index used for a table in a QEP

The various access methods have different places where the index/key number is stored, so this function is needed to return the correct value.

Returns

index number, or MAX_KEY if not applicable.

JT_SYSTEM and JT_ALL does not use an index, and will always return MAX_KEY.

JT_INDEX_MERGE supports more than one index. Hence MAX_KEY is returned and a further inspection is needed.

eligible_secondary_storage_engine()

const MYSQL_LEX_CSTRING * Sql_cmd_select::eligible_secondary_storage_engine ( ) const

overridevirtual

Is this statement of a type and on a form that makes it eligible for execution in a secondary storage engine?

Returns

the name of the secondary storage engine, or nullptr if the statement is not eligible for execution in a secondary storage engine

Reimplemented from Sql_cmd.

eliminate_item_equal()

static Item * eliminate_item_equal ( THD *  thd, Item *  cond, COND_EQUAL *  upper_levels, Item_equal *  item_equal  )

static

Generate minimal set of simple equalities equivalent to a multiple equality.

The function retrieves the fields of the multiple equality item item_equal and for each field f:

• if item_equal contains const it generates the equality f=const_item;
• otherwise, if f is not the first field, generates the equality f=item_equal->get_first(). All generated equality are added to the cond conjunction.

Parameters

thd	the session context
cond	condition to add the generated equality to
upper_levels	structure to access multiple equality of upper levels
item_equal	multiple equality to generate simple equality from

Note

Before generating an equality function checks that it has not been generated for multiple equalities of the upper levels. E.g. for the following where condition WHERE a=5 AND ((a=b AND b=c) OR c>4) the upper level AND condition will contain =(5,a), while the lower level AND condition will contain =(5,a,b,c). When splitting =(5,a,b,c) into a separate equality predicates we should omit 5=a, as we have it already in the upper level. The following where condition gives us a more complicated case: WHERE t1.a=t2.b AND t3.c=t4.d AND (t2.b=t3.c OR t4.e>5 ...) AND ... Given the tables are accessed in the order t1->t2->t3->t4 for the selected query execution plan the lower level multiple equality =(t1.a,t2.b,t3.c,t4.d) formally should be converted to t1.a=t2.b AND t1.a=t3.c AND t1.a=t4.d. But t1.a=t2.a will be generated for the upper level. Also t3.c=t4.d will be generated there. So only t1.a=t3.c should be left in the lower level. If cond is equal to 0, then not more then one equality is generated and a pointer to it is returned as the result of the function.

Returns

• The condition with generated simple equalities or a pointer to the simple generated equality, if success.
• 0, otherwise.

equal()

static bool equal ( const Item *  i1, const Item *  i2, const Field *  f2  )

static

equal_engines()

static bool equal_engines ( const LEX_CSTRING &  engine1, const LEX_CSTRING &  engine2  )

static

equality_determines_uniqueness()

bool equality_determines_uniqueness	(	const Item_func_comparison *	func,
		const Item *	v,
		const Item *	c
	)

Check if equality can be used to remove sub-clause of GROUP BY/ORDER BY.

Parameters

func	comparison operator (= or <=>)
v	variable comparison operand (validated to be equal to ordering expression)
c	other comparison operand (likely to be a constant)

Returns

whether equality determines uniqueness

Checks if an equality predicate can be used to remove a GROUP BY/ORDER BY sub-clause when it is known to be true for exactly one distinct value (e.g. "expr" == "const"). Arguments must be of the same type because e.g. "string_field" = "int_const" may match more than one distinct value from the column.

equality_has_no_implicit_casts()

bool equality_has_no_implicit_casts	(	const Item_func_comparison *	func,
		const Item *	item1,
		const Item *	item2
	)

Check whether equality between two items is exact, ie., there are no implicit casts involved.

This is especially important for GROUP BY/ORDER BY, as it means they can be treated interchangeably. The primary difference between this and equality_determines_uniqueness() is that item2 does not need to be a constant (which makes it stricter in other aspects).

estimate_rowcount()

bool JOIN::estimate_rowcount ( )

private

Estimate the number of matched rows for each joined table.

Set up range scan for tables that have proper predicates. Eliminate tables that have filter conditions that are always false based on analysis performed in resolver phase or analysis of range scan predicates.

Returns

false if success, true if error

execute()

bool Sql_cmd_dml::execute ( THD *  thd )

overridevirtual

Execute a DML statement.

Parameters

thd	thread handler

Returns

false if success, true if error

Processing a statement goes through 6 phases (parsing is already done)

• Prelocking
• Preparation
• Locking of tables
• Optimization
• Execution or explain
• Cleanup

If the statement is already prepared, this step is skipped.

The queries handled by this function are:

SELECT INSERT ... SELECT INSERT ... VALUES REPLACE ... SELECT REPLACE ... VALUES UPDATE (single-table and multi-table) DELETE (single-table and multi-table) DO

Implements Sql_cmd.

Reimplemented in Sql_cmd_show, Sql_cmd_show_noplan, and Sql_cmd_show_status.

execute_inner()

bool Sql_cmd_dml::execute_inner ( THD *  thd )

protectedvirtual

The inner parts of query optimization and execution.

Execute a DML statement.

Single-table DML operations needs to reimplement this.

Parameters

thd	Thread handler

Returns

false on success, true on error

This is the default implementation for a DML statement and uses a nested-loop join processor per outer-most query block. The implementation is split in two: One for query expressions containing a single query block and one for query expressions containing multiple query blocks combined with UNION.

Reimplemented in Sql_cmd_call, Sql_cmd_delete, Sql_cmd_insert_values, Sql_cmd_show_routine_code, Sql_cmd_show_binlog_events, Sql_cmd_show_binlogs, Sql_cmd_show_create_database, Sql_cmd_show_create_event, Sql_cmd_show_create_function, Sql_cmd_show_create_procedure, Sql_cmd_show_create_table, Sql_cmd_show_create_trigger, Sql_cmd_show_create_user, Sql_cmd_show_engine_logs, Sql_cmd_show_engine_mutex, Sql_cmd_show_engine_status, Sql_cmd_show_errors, Sql_cmd_show_grants, Sql_cmd_show_master_status, Sql_cmd_show_privileges, Sql_cmd_show_processlist, Sql_cmd_show_profiles, Sql_cmd_show_relaylog_events, Sql_cmd_show_replicas, Sql_cmd_show_replica_status, Sql_cmd_show_warnings, and Sql_cmd_update.

external_engine_fail_reason()

static void external_engine_fail_reason ( const LEX *  lex )

static

extract_const_tables()

bool JOIN::extract_const_tables ( )

private

Extract const tables based on row counts.

Returns

false if success, true if error

This extraction must be done for each execution. Tables containing exactly zero or one rows are marked as const, but notice the additional constraints checked below. Tables that are extracted have their rows read before actual execution starts and are placed in the beginning of the join_tab array. Thus, they do not take part in join order optimization process, which can significantly reduce the optimization time. The data read from these tables can also be regarded as "constant" throughout query execution, hence the column values can be used for additional constant propagation and extraction of const tables based on eq-ref properties.

The tables are given the type JT_SYSTEM.

extract_func_dependent_tables()

bool JOIN::extract_func_dependent_tables ( )

private

Extract const tables based on functional dependencies.

Returns

false if success, true if error

This extraction must be done for each execution.

Mark as const the tables that

• are functionally dependent on constant values, or
• are inner tables of an outer join and contain exactly zero or one rows

Tables that are extracted have their rows read before actual execution starts and are placed in the beginning of the join_tab array, just as described for JOIN::extract_const_tables().

The tables are given the type JT_CONST.

find_and_set_offload_fail_reason()

static bool find_and_set_offload_fail_reason ( const LEX *  lex )

static

find_eq_ref_candidate()

static bool find_eq_ref_candidate ( Table_ref *  tl, table_map  sj_inner_tables  )

static

find_field_in_item_list()

static bool find_field_in_item_list ( Field *  field, void *  data  )

static

Helper function for list_contains_unique_index.

Find a field reference in a dynamic list of Items. Finds a direct reference of the Field in the list.

Parameters

[in]	field	The field to search for.
[in]	data	List<Item> *.The list to search in

Return values

1	found
0	not found.

find_field_in_order_list()

static bool find_field_in_order_list ( Field *  field, void *  data  )

static

Helper function for list_contains_unique_index.

Find a field reference in a list of ORDER structures. Finds a direct reference of the Field in the list.

Parameters

field	The field to search for.
data	ORDER *.The list to search in

Return values

1	found
0	not found.

find_item_equal()

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.

The function retrieves the multiple equalities accessed through the cond_equal structure from current level and up looking for an equality containing a field. It stops retrieval as soon as the equality is found and set up inherited_fl to true if it's found on upper levels.

Parameters

	cond_equal	multiple equalities to search in
	item_field	field to look for
[out]	inherited_fl	set up to true if multiple equality is found on upper levels (not on current level of cond_equal)

Returns

• Item_equal for the found multiple equality predicate if a success;
• nullptr otherwise.

find_shortest_key()

uint find_shortest_key	(	TABLE *	table,
		const Key_map *	usable_keys
	)

Find shortest key suitable for full table scan.

Parameters

table	Table to scan
usable_keys	Allowed keys

Note

As far as 1) clustered primary key entry data set is a set of all record fields (key fields and not key fields) and 2) secondary index entry data is a union of its key fields and primary key fields (at least InnoDB and its derivatives don't duplicate primary key fields there, even if the primary and the secondary keys have a common subset of key fields), then secondary index entry data is always a subset of primary key entry. Unfortunately, key_info[nr].key_length doesn't show the length of key/pointer pair but a sum of key field lengths only, thus we can't estimate index IO volume comparing only this key_length value of secondary keys and clustered PK. So, try secondary keys first, and choose PK only if there are no usable secondary covering keys or found best secondary key include all table fields (i.e. same as PK):

Returns

MAX_KEY no suitable key found key index otherwise

find_worst_seeks()

double find_worst_seeks	(	const TABLE *	table,
		double	num_rows,
		double	table_scan_cost
	)

Find an artificial cap for ref access.

This is mostly a crutch to mitigate that we don't estimate the cache effects of ref accesses properly (ie., normally, if we do many, they will hit cache instead of being separate seeks). Given to find_cost_for_ref().

free_underlaid_joins()

void free_underlaid_joins

(

Query_block *

select

)

Free joins of subselect of this select.

Parameters

select

pointer to Query_block which subselects joins we will free

get_best_combination()

bool JOIN::get_best_combination

(

)

Set up JOIN_TAB structs according to the picked join order in best_positions.

This allocates execution structures so may be called only after we have the very final plan. It must be called after Optimize_table_order::fix_semijoin_strategies().

Returns

False if success, True if error

• create join->join_tab array and copy from existing JOIN_TABs in join order
• create helper structs for materialized semi-join handling
• finalize semi-join strategy choices
• Number of intermediate tables "tmp_tables" is calculated.
• "tables" and "primary_tables" are recalculated.
• for full and index scans info of estimated # of records is updated.
• in a helper function:
  • all heuristics are applied and the final access method type is picked for each join_tab (only test_if_skip_sort_order() could override it)
  • AM consistency is ensured (e.g only range and index merge are allowed to have quick select set).
  • if "Impossible WHERE" is detected - appropriate zero_result_cause is set.

Notice that intermediate tables will not have a POSITION reference; and they will not have a TABLE reference before the final stages of code generation.

get_best_field()

Item_field * get_best_field	(	Item_field *	item_field,
		COND_EQUAL *	cond_equal
	)

Get the best field substitution for a given field.

If the field is member of a multiple equality, look up that equality and return the most appropriate field. Usually this is the equivalenced field belonging to the outer-most table in the join order, but

See also

Item_field::get_subst_item() for details. Otherwise, return the same field.

Parameters

item_field	The field that we are seeking a substitution for.
cond_equal	multiple equalities to search in

Returns

The substituted field.

get_eligible_secondary_engine()

const MYSQL_LEX_CSTRING * Sql_cmd_dml::get_eligible_secondary_engine ( ) const

protected

Helper function that checks if the command is eligible for secondary engine and if that's true returns the name of that eligible secondary storage engine.

Returns

nullptr if not eligible or the name of the engine otherwise

get_eligible_secondary_engine_from()

static const MYSQL_LEX_CSTRING * get_eligible_secondary_engine_from ( const LEX *  lex )

static

get_index_for_order()

uint get_index_for_order	(	ORDER_with_src *	order,
		TABLE *	table,
		ha_rows	limit,
		AccessPath *	range_scan,
		bool *	need_sort,
		bool *	reverse
	)

Find a key to apply single table UPDATE/DELETE by a given ORDER.

Parameters

	order	Linked list of ORDER BY arguments
	table	Table to find a key
	limit	LIMIT clause parameter
	range_scan	Range scan used for this table, if any
[out]	need_sort	true if filesort needed
[out]	reverse	true if the key is reversed again given ORDER (undefined if key == MAX_KEY)

Returns

• MAX_KEY if no key found (need_sort == true)
• MAX_KEY if quick select result order is OK (need_sort == false)
• key number (either index scan or quick select) (need_sort == false)

Note

Side effects:

• may deallocate or deallocate and replace select->quick;
• may set table->quick_condition_rows and table->quick_rows[...] to table->file->stats.records.

get_key_length_tmp_table()

static uint32 get_key_length_tmp_table ( Item *  item )

static

(end of group Query_Optimizer)

This function is used to get the key length of Item object on which one tmp field will be created during create_tmp_table. This function references KEY_PART_INFO::init_from_field().

Parameters

item	A inner item of outer join

Returns

The length of a item to be as a key of a temp table

get_max_execution_time()

static ulong get_max_execution_time ( THD *  thd )

inlinestatic

Get the maximum execution time for a statement.

Returns

Length of time in milliseconds.

Remarks

A zero timeout means that no timeout should be applied to this particular statement.

get_quick_record_count()

static ha_rows get_quick_record_count ( THD *  thd, JOIN_TAB *  tab, ha_rows  limit, Item *  condition  )

static

Returns estimated number of rows that could be fetched by given access method.

The function calls the range optimizer to estimate the cost of the cheapest QUICK_* index access method to scan one or several of the 'keys' using the conditions 'select->cond'. The range optimizer compares several different types of 'quick select' methods (range scan, index merge, loose index scan) and selects the cheapest one.

If the best index access method is cheaper than a table- and an index scan, then the range optimizer also constructs the corresponding QUICK_* object and assigns it to select->quick. In most cases this is the QUICK_* object used at later (optimization and execution) phases.

Parameters

thd	Session that runs the query.
tab	JOIN_TAB of source table.
limit	maximum number of rows to select.
condition	the condition to be used for the range check,

Note

In case of valid range, a RowIterator object will be constructed and saved in select->quick.

Returns

Estimated number of result rows selected from 'tab'.

Return values

HA_POS_ERROR	For derived tables/views or if an error occur.
0	If impossible query (i.e. certainly no rows will be selected.)

get_secondary_engine_fail_reason()

static const char * get_secondary_engine_fail_reason ( const LEX *  lex )

static

get_secondary_engine_handlerton()

const handlerton * get_secondary_engine_handlerton

(

const LEX *

lex

)

Returns secondary_engine handler for the statement.

If none exist, nullptr is returned.

Parameters

lex	the statement

get_semi_join_select_list_index()

static uint get_semi_join_select_list_index ( Item_field *  item_field )

static

Given a field, return its index in semi-join's select list, or UINT_MAX.

Parameters

item_field

Field to be looked up in select list

Return values

=UINT_MAX	Field is not from a semijoin-transformed subquery
<UINT_MAX	Index in select list of subquery

Given a field, find its table; then see if the table is within a semi-join nest and if the field was in select list of the subquery (if subquery was part of a quantified comparison predicate), or the field was a result of subquery decorrelation. If it was, then return the field's index in the select list. The value is used by LooseScan strategy.

get_sj_strategy() [1/2]

uint QEP_TAB::get_sj_strategy

(

)

const

Returns

semijoin strategy for this table.

get_sj_strategy() [2/2]

uint JOIN_TAB::get_sj_strategy

(

)

const

Returns

semijoin strategy for this table.

get_sort_by_table()

static TABLE * get_sort_by_table ( ORDER *  a, ORDER *  b, Table_ref *  tables  )

static

Return table number if there is only one table in sort order and group and order is compatible, else return 0.

get_store_key()

static store_key * get_store_key ( THD *  thd, Item *  val, table_map  used_tables, table_map  const_tables, const KEY_PART_INFO *  key_part, uchar *  key_buff, uint  maybe_null  )

static

get_tmp_table_rec_length()

static uint get_tmp_table_rec_length ( const mem_root_deque< Item * > &  items )

static

has_not_null_predicate()

static bool has_not_null_predicate ( Item *  cond, Item_field *  not_null_item  )

static

Check all existing AND'ed predicates in 'cond' for an existing 'is not null 'not_null_item''-predicate.

A condition consisting of multiple AND'ed terms is recursively decomposed in the search for the specified not null predicate.

Parameters

cond	Condition to be checked.
not_null_item	The item in: 'is not null 'item'' to search for

Returns

true if 'is not null 'not_null_item'' is a predicate in the specified 'cond'.

has_secondary_engine_defined()

static bool has_secondary_engine_defined ( const LEX *  lex )

static

init()

void QEP_TAB::init

(

JOIN_TAB *

jt

)

Initializes the object from a JOIN_TAB.

init_join_cache()

void QEP_TAB::init_join_cache

(

JOIN_TAB *

join_tab

)

A helper function that allocates appropriate join cache object and sets next_query_block function of previous tab.

A helper function that sets the right op type for join cache (BNL/BKA).

init_join_cond_ref()

void JOIN_TAB::init_join_cond_ref

(

Table_ref *

tl

)

Sets the pointer to the join condition of Table_ref.

init_planner_arrays()

bool JOIN::init_planner_arrays ( )

private

Initialize scratch arrays for the join order optimization.

Returns

false if success, true if error

Note

If something fails during initialization, JOIN::cleanup() will free anything that has been partially allocated and set up. Arrays are created in the execution mem_root, so they will be deleted automatically when the mem_root is re-initialized.

init_ref()

bool init_ref	(	THD *	thd,
		unsigned	keyparts,
		unsigned	length,
		unsigned	keyno,
		Index_lookup *	ref
	)

Initialize the given TABLE_REF; setting basic fields and allocating memory for arrays.

Call init_ref_part() for each keypart (index field) that is to take part in the ref lookup.

init_ref_access()

bool JOIN::init_ref_access ( )

private

Initialize ref access for all tables that use it.

Returns

False if success, True if error

Note

We cannot setup fields used for ref access before we have sorted the items within multiple equalities according to the final order of the tables involved in the join operation. Currently, this occurs in

See also

substitute_for_best_equal_field().

init_ref_part()

bool init_ref_part	(	THD *	thd,
		unsigned	part_no,
		Item *	val,
		bool *	cond_guard,
		bool	null_rejecting,
		table_map	const_tables,
		table_map	used_tables,
		bool	nullable,
		const KEY_PART_INFO *	key_part_info,
		uchar *	key_buff,
		Index_lookup *	ref
	)

Initialize a given keypart in the table ref.

In particular, sets up the right function pointer to copy the value from “val” into the ref at execution time (or copies the value right now, if it is constant).

is_local_field()

static bool is_local_field ( Item *  field )

static

Check if an expression is a non-outer field.

Checks if an expression is a field and belongs to the current select.

Parameters

field

Item expression to check

Returns

boolean

Return values

true	the expression is a local field
false	it's something else

is_prefix_index()

bool is_prefix_index	(	TABLE *	table,
		uint	idx
	)

Test if this is a prefix index.

Parameters

table	table
idx	index to check

Returns

TRUE if this is a prefix index

is_ref_or_null_optimized()

static bool is_ref_or_null_optimized ( const JOIN_TAB *  tab, uint  ref_key  )

static

Test if REF_OR_NULL optimization will be used if the specified ref_key is used for REF-access to 'tab'.

Return values

true	JT_REF_OR_NULL will be used
false	no JT_REF_OR_NULL access

is_row_of_local_columns()

static bool is_row_of_local_columns ( Item_row *  item_row )

static

Check if a row constructor expression is over columns in the same query block.

Parameters

item_row

Row expression to check.

Returns

boolean

Return values

true	The expression is a local column reference.
false	It's something else.

is_show_cmd_using_system_view()

bool is_show_cmd_using_system_view ( THD *  thd )

inline

Check whether the statement is a SHOW command using INFORMATION_SCHEMA system views.

Parameters

thd	Thread (session) context.

Returns

true if command uses INFORMATION_SCHEMA system view, false otherwise

is_subkey()

bool is_subkey ( KEY_PART_INFO *  key_part, KEY_PART_INFO *  ref_key_part, KEY_PART_INFO *  ref_key_part_end  )

inline

Test if a second key is the subkey of the first one.

Parameters

key_part	First key parts
ref_key_part	Second key parts
ref_key_part_end	Last+1 part of the second key

Note

Second key MUST be shorter than the first one.

Return values

1	is a subkey
0	no sub key

is_timer_applicable_to_statement()

static bool is_timer_applicable_to_statement ( THD *  thd )

inlinestatic

Check whether max statement time is applicable to statement or not.

Parameters

thd	Thread (session) context.

Returns

true if max statement time is applicable to statement

false otherwise.

join_free()

void JOIN::join_free

(

)

Release memory and, if possible, the open tables held by this execution plan (and nested plans).

Partially cleanup JOIN after it has executed: close index or rnd read (table cursors), free quick selects.

It's used to release some tables before the end of execution in order to increase concurrency and reduce memory consumption.

This function is called in the end of execution of a JOIN, before the used tables are unlocked and closed.

For a join that is resolved using a temporary table, the first sweep is performed against actual tables and an intermediate result is inserted into the temporary table. The last sweep is performed against the temporary table. Therefore, the base tables and associated buffers used to fill the temporary table are no longer needed, and this function is called to free them.

For a join that is performed without a temporary table, this function is called after all rows are sent, but before EOF packet is sent.

For a simple SELECT with no subqueries this function performs a full cleanup of the JOIN and calls mysql_unlock_read_tables to free used base tables.

If a JOIN is executed for a subquery or if it has a subquery, we can't do the full cleanup and need to do a partial cleanup only.

• If a JOIN is not the top level join, we must not unlock the tables because the outer select may not have been evaluated yet, and we can't unlock only selected tables of a query.
• Additionally, if this JOIN corresponds to a correlated subquery, we should not free quick selects and join buffers because they will be needed for the next execution of the correlated subquery.
• However, if this is a JOIN for a [sub]select, which is not a correlated subquery itself, but has subqueries, we can free it fully and also free JOINs of all its subqueries. The exception is a subquery in SELECT list, e.g:

  SELECT a, (select max(b) from t1) group by c

  This subquery will not be evaluated at first sweep and its value will not be inserted into the temporary table. Instead, it's evaluated when selecting from the temporary table. Therefore, it can't be freed here even though it's not correlated.

list_contains_unique_index()

static bool list_contains_unique_index ( JOIN_TAB *  tab, bool(*)(Field *, void *)  find_func, void *  data  )

static

Check if GROUP BY/DISTINCT can be optimized away because the set is already known to be distinct.

Used in removing the GROUP BY/DISTINCT of the following types of statements:

SELECT [DISTINCT] <unique_key_cols>... FROM <single_table_ref>
  [GROUP BY <unique_key_cols>,...]

If (a,b,c is distinct) then <any combination of a,b,c>,{whatever} is also distinct

This function checks if all the key parts of any of the unique keys of the table are referenced by a list : either the select list through find_field_in_item_list or GROUP BY list through find_field_in_order_list. If the above holds and the key parts cannot contain NULLs then we can safely remove the GROUP BY/DISTINCT, as no result set can be more distinct than an unique key.

Parameters

tab	The join table to operate on.
find_func	function to iterate over the list and search for a field
data	data that's passed through to to find_func

Return values

1	found
0	not found.

Note

The function assumes that make_outerjoin_info() has been called in order for the check for outer tables to work.

make_cond_for_index()

static Item * make_cond_for_index ( Item *  cond, TABLE *  table, uint  keyno, bool  other_tbls_ok  )

static

make_cond_remainder()

static Item * make_cond_remainder ( Item *  cond, bool  exclude_index  )

static

make_join_plan()

bool JOIN::make_join_plan ( )

private

Calculate best possible join order and initialize the join structure.

Returns

true if success, false if error.

The JOIN object is populated with statistics about the query, and a plan with table order and access method selection is made.

The list of tables to be optimized is taken from query_block->leaf_tables. JOIN::where_cond is also used in the optimization. As a side-effect, JOIN::keyuse_array is populated with key_use information.

Here is an overview of the logic of this function:

• Initialize JOIN data structures and setup basic dependencies between tables.
• Update dependencies based on join information.
• Make key descriptions (update_ref_and_keys()).
• Pull out semi-join tables based on table dependencies.
• Extract tables with zero or one rows as const tables.
• Read contents of const tables, substitute columns from these tables with actual data. Also keep track of empty tables vs. one-row tables.
• After const table extraction based on row count, more tables may have become functionally dependent. Extract these as const tables.
• Add new sargable predicates based on retrieved const values.
• Calculate number of rows to be retrieved from each table.
• Calculate cost of potential semi-join materializations.
• Calculate best possible join order based on available statistics.
• Fill in remaining information for the generated join order.

make_join_query_block()

static bool make_join_query_block ( JOIN *  join, Item *  cond  )

static

Separates the predicates in a join condition and pushes them to the join step where all involved tables are available in the join prefix.

ON clauses from JOIN expressions are also pushed to the most appropriate step.

Parameters

join	Join object where predicates are pushed.
cond	Pointer to condition which may contain an arbitrary number of predicates, combined using AND, OR and XOR items. If NULL, equivalent to a predicate that returns true for all row combinations.

Return values

true	Found impossible WHERE clause, or out-of-memory
false	Other

make_join_readinfo()

bool make_join_readinfo	(	JOIN *	join,
		uint	no_jbuf_after
	)

Plan refinement stage: do various setup things for the executor.

Parameters

join	Join being processed
no_jbuf_after	Don't use join buffering after table with this number.

Returns

false if successful, true if error (Out of memory)

Plan refinement stage: do various set ups for the executioner

• setup join buffering use
• push index conditions
• increment relevant counters
• etc

make_sum_func_list()

bool JOIN::make_sum_func_list	(	const mem_root_deque< Item * > &	fields,
		bool	before_group_by,
		bool	recompute = false
	)

Initialize 'sum_funcs' array with all Item_sum objects.

Parameters

fields	All items
before_group_by	Set to 1 if this is called before GROUP BY handling
recompute	Set to true if sum_funcs must be recomputed

Return values

0	ok
1	error

make_tmp_tables_info()

bool JOIN::make_tmp_tables_info ( )

private

Init tmp tables usage info.

This function finalizes execution plan by taking following actions: .) tmp tables are created, but not instantiated (this is done during execution). QEP_TABs dedicated to tmp tables are filled appropriately. see JOIN::create_intermediate_table. .) prepare fields lists (fields, all_fields, ref_item_array slices) for each required stage of execution. These fields lists are set for tmp tables' tabs and for the tab of last table in the join. .) fill info for sorting/grouping/dups removal is prepared and saved to appropriate tabs. Here is an example: SELECT * from t1,t2 WHERE ... GROUP BY t1.f1 ORDER BY t2.f2, t1.f2 and lets assume that the table order in the plan is t1,t2. In this case optimizer will sort for group only the first table as the second one isn't mentioned in GROUP BY. The result will be materialized in tmp table. As filesort can't sort join optimizer will sort tmp table also. The first sorting (for group) is called simple as is doesn't require tmp table. The Filesort object for it is created here - in JOIN::create_intermediate_table. Filesort for the second case is created here, in JOIN::make_tmp_tables_info.

Note

This function may change tmp_table_param.precomputed_group_by. This affects how create_tmp_table() treats aggregation functions, so count_field_types() must be called again to make sure this is taken into consideration.

Returns

false - Ok true - Error

merge_key_fields()

static Key_field * merge_key_fields ( Key_field *  start, Key_field *  new_fields, Key_field *  end, uint  and_level  )

static

Merge new key definitions to old ones, remove those not used in both.

This is called for OR between different levels.

To be able to do 'ref_or_null' we merge a comparison of a column and 'column IS NULL' to one test. This is useful for sub select queries that are internally transformed to something like:.

SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL

Key_field::null_rejecting is processed as follows:
result has null_rejecting=true if it is set for both ORed references. for example:

• (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
• (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false

only_eq_ref_tables()

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

See also

eq_ref_table()

optimize() [1/2]

bool JOIN::optimize

(

bool

finalize_access_paths

)

Optimizes one query block into a query execution plan (QEP.)

This is the entry point to the query optimization phase. This phase applies both logical (equivalent) query rewrites, cost-based join optimization, and rule-based access path selection. Once an optimal plan is found, the member function creates/initializes all structures needed for query execution. The main optimization phases are outlined below:

1. Logical transformations:
   • Outer to inner joins transformation.
   • Equality/constant propagation.
   • Partition pruning.
   • COUNT(*), MIN(), MAX() constant substitution in case of implicit grouping.
   • ORDER BY optimization.
2. Perform cost-based optimization of table order and access path selection. See JOIN::make_join_plan()
3. Post-join order optimization:
   • Create optimal table conditions from the where clause and the join conditions.
   • Inject outer-join guarding conditions.
   • Adjust data access methods after determining table condition (several times.)
   • Optimize ORDER BY/DISTINCT.
4. Code generation
   • Set data access functions.
   • Try to optimize away sorting/distinct.
   • Setup temporary table usage for grouping and/or sorting.

Return values

false	Success.
true	Error, error code saved in member JOIN::error.

optimize() [2/2]

bool Query_block::optimize	(	THD *	thd,
		bool	finalize_access_paths
	)

Optimize a query block and all inner query expressions.

Parameters

thd	thread handler
finalize_access_paths	if true, finalize access paths, cf. FinalizePlanForQueryBlock

Returns

false if success, true if error

optimize_distinct_group_order()

bool JOIN::optimize_distinct_group_order ( )

private

Optimize DISTINCT, GROUP BY, ORDER BY clauses.

Return values

false	ok
true	an error occurred

optimize_secondary_engine()

bool optimize_secondary_engine

(

THD *

thd

)

Perform query optimizations that are specific to a secondary storage engine.

Parameters

thd	the current session

Returns

true on error, false on success

optimize_semijoin_nests_for_materialization()

static bool optimize_semijoin_nests_for_materialization ( JOIN *  join )

static

Optimize semi-join nests that could be run with sj-materialization.

Parameters

join	The join to optimize semi-join nests for

Optimize each of the semi-join nests that can be run with materialization. For each of the nests, we

• Generate the best join order for this "sub-join" and remember it;
• Remember the sub-join execution cost (it's part of materialization cost);
• Calculate other costs that will be incurred if we decide to use materialization strategy for this semi-join nest.

All obtained information is saved and will be used by the main join optimization pass.

Returns

false if successful, true if error

precheck()

bool Sql_cmd_select::precheck ( THD *  thd )

overrideprotectedvirtual

Perform an authorization precheck for an unprepared SELECT statement.

This function will check that we have some privileges to all involved tables of the query (and possibly to other entities).

Implements Sql_cmd_dml.

Reimplemented in Sql_cmd_show.

prepare()

bool Sql_cmd_dml::prepare ( THD *  thd )

overridevirtual

Command-specific resolving (doesn't include LEX::prepare())

Parameters

thd	Current THD.

Returns

false on success, true on error

Reimplemented from Sql_cmd.

prepare_inner()

bool Sql_cmd_select::prepare_inner ( THD *  thd )

overrideprotectedvirtual

Prepare a SELECT statement.

Implements Sql_cmd_dml.

prepare_result()

bool JOIN::prepare_result

(

)

Prepare join result.

Prepare join result prior to join execution or describing. Instantiate derived tables and get schema tables result if necessary.

Returns

true An error during derived or schema tables instantiation. false Ok

propagate_cond_constants()

static bool propagate_cond_constants ( THD *  thd, I_List< COND_CMP > *  save_list, Item *  and_father, Item *  cond  )

static

Propagate constant values in a condition.

Parameters

thd	Thread handler
save_list	saved list of COND_CMP
and_father	father of AND op
cond	Condition for which constant values are propagated

Returns

false if success, true if error

propagate_dependencies()

bool JOIN::propagate_dependencies

(

)

Propagate dependencies between tables due to outer join relations.

Returns

false if success, true if error

false if success, true if error

Build transitive closure for relation 'to be dependent on'. This will speed up the plan search for many cases with outer joins, as well as allow us to catch illegal cross references. Warshall's algorithm is used to build the transitive closure. As we may restart the outer loop up to 'table_count' times, the complexity of the algorithm is O((number of tables)^3). However, most of the iterations will be shortcircuited when there are no dependencies to propagate.

prune_table_partitions()

bool JOIN::prune_table_partitions ( )

private

Prune partitions for all tables of a join (query block).

Requires that tables have been locked.

Returns

false if success, true if error

pull_out_semijoin_tables()

static bool pull_out_semijoin_tables ( JOIN *  join )

static

Pull tables out of semi-join nests based on functional dependencies.

Parameters

join	The join where to do the semi-join table pullout

Returns

False if successful, true if error (Out of memory)

Pull tables out of semi-join nests based on functional dependencies, ie. if a table is accessed via eq_ref(outer_tables). The function may be called several times, the caller is responsible for setting up proper key information that this function acts upon.

PRECONDITIONS When this function is called, the join may have several semi-join nests but it is guaranteed that one semi-join nest does not contain another. For functionally dependent tables to be pulled out, key information must have been calculated (see update_ref_and_keys()).

POSTCONDITIONS Tables that were pulled out are removed from the semi-join nest they belonged to and added to the parent join nest. For these tables, the used_tables and not_null_tables fields of the semi-join nest they belonged to will be adjusted. The semi-join nest is also marked as correlated, and sj_corr_tables and sj_depends_on are adjusted if necessary. Semi-join nests' sj_inner_tables is set equal to used_tables

NOTE Table pullout may make uncorrelated subquery correlated. Consider this example:

... WHERE oe IN (SELECT it1.primary_key WHERE p(it1, it2) ... )

here table it1 can be pulled out (we have it1.primary_key=oe which gives us functional dependency). Once it1 is pulled out, all references to it1 from p(it1, it2) become references to outside of the subquery and thus make the subquery (i.e. its semi-join nest) correlated. Making the subquery (i.e. its semi-join nest) correlated prevents us from using Materialization or LooseScan to execute it.

push_index_cond()

void QEP_TAB::push_index_cond	(	const JOIN_TAB *	join_tab,
		uint	keyno,
		Opt_trace_object *	trace_obj
	)

Try to extract and push the index condition down to table handler.

Parameters

join_tab	join_tab for table
keyno	Index for which extract and push the condition
trace_obj	trace object where information is to be added

push_to_engines()

bool JOIN::push_to_engines

(

)

Handle offloading of query parts to the underlying engines, when such is supported by their implementation.

Push (parts of) the query execution down to the storage engines if they can provide faster execution of the query, or part of it.

Returns

false if success, true if error

The handler will inspect the QEP through the AQP (Abstract Query Plan) and extract from it whatever it might implement of pushed execution.

It is the responsibility of the handler to store any information it need for the later execution of pushed queries and conditions.

Return values

false	Success.
true	Error, error code saved in member JOIN::error.

qs_cleanup()

void QEP_shared_owner::qs_cleanup

(

)

query_result()

Query_result * Sql_cmd_dml::query_result

(

)

const

Returns

the query result associated with a prepared query

reads_not_secondary_columns()

static bool reads_not_secondary_columns ( const LEX *  lex )

static

Checks if a query reads a column that is not available in the secondary engine (i.e.

a column defined with NOT SECONDARY).

Parameters

lex	Parse tree descriptor.

Returns

True if at least one of the read columns is not in the secondary engine, false otherwise.

refresh_base_slice()

void JOIN::refresh_base_slice

(

)

In the case of rollup (only): After the base slice list was made, we may have modified the field list to add rollup group items and sum switchers, but there may be Items with refs that refer to the base slice.

This function refreshes the base slice (and its copy, REF_SLICE_SAVED_BASE) with a fresh copy of the list from “fields”.

When we get rid of slices entirely, we can get rid of this, too.

replace_index_subquery()

int JOIN::replace_index_subquery ( )

private

Check whether this is a subquery that can be evaluated by index look-ups.

If so, change subquery engine to subselect_indexsubquery_engine.

Return values

1	engine was changed
0	engine wasn't changed
-1	OOM or other error

reset()

void JOIN::reset

(

void

)

Reset the state of this join object so that it is ready for a new execution.

reset_statement_timer()

void reset_statement_timer

(

THD *

thd

)

Deactivate the timer associated with the statement that was executed.

Parameters

thd	Thread (session) context.

restore_cmd_properties()

bool Sql_cmd_dml::restore_cmd_properties ( THD *  thd )

protectedvirtual

Restore command properties before execution.

• Bind metadata for tables and fields
• Restore clauses (e.g ORDER BY, GROUP BY) that were destroyed in last optimization.

Reimplemented in Sql_cmd_insert_base.

retry_with_secondary_engine()

static bool retry_with_secondary_engine ( THD *  thd )

static

Checks if a query should be retried using a secondary storage engine.

Parameters

thd	the current session

Return values

true	if the statement should be retried in a secondary engine
false	if the statement should not be retried

revise_cache_usage()

static void revise_cache_usage ( JOIN_TAB *  join_tab )

static

save_cmd_properties()

bool Sql_cmd_dml::save_cmd_properties ( THD *  thd )

protectedvirtual

Save command properties, such as prepared query details and table props.

SaveCondEqualLists()

static void SaveCondEqualLists ( COND_EQUAL *  cond_equal )

static

The List<Item_equal> in COND_EQUAL partially overlaps with the argument list in various Item_cond via C-style casts.

However, the hypergraph optimizer can modify the lists in Item_cond (by calling compile()), causing an Item_equal to be replaced with Item_func_eq, and this can cause a List<Item_equal> not to contain Item_equal pointers anymore. This is is obviously bad if anybody wants to actually look into these lists after optimization (in particular, NDB wants this).

Since untangling this spaghetti seems very hard, we solve it by brute force: Make a copy of all the COND_EQUAL lists, so that they no longer reach into the Item_cond. This allows us to modify the Item_cond at will.

semijoin_types_allow_materialization()

static void semijoin_types_allow_materialization ( Table_ref *  sj_nest )

static

Check if semijoin's compared types allow materialization.

Parameters

[in,out]

sj_nest

Semi-join nest containing information about correlated expressions. Set nested_join->sjm.scan_allowed to true if MaterializeScan strategy allowed. Set nested_join->sjm.lookup_allowed to true if MaterializeLookup strategy allowed

This is a temporary fix for BUG#36752.

There are two subquery materialization strategies for semijoin:

1. Materialize and do index lookups in the materialized table. See BUG#36752 for description of restrictions we need to put on the compared expressions.

   In addition, since indexes are not supported for BLOB columns, this strategy can not be used if any of the columns in the materialized table will be BLOB/GEOMETRY columns. (Note that also columns for non-BLOB values that may be greater in size than CONVERT_IF_BIGGER_TO_BLOB, will be represented as BLOB columns.)

2. Materialize and then do a full scan of the materialized table. The same criteria as for MaterializeLookup are applied, except that BLOB/GEOMETRY columns are allowed.

set_external_engine_fail_reason()

void set_external_engine_fail_reason	(	const LEX *	lex,
		const char *	reason
	)

Sets the reason of failure for the statement to the external engine.

Parameters

lex	the statement
reason	the reason of failure

set_fail_reason_and_raise_error()

static void set_fail_reason_and_raise_error ( const LEX *  lex, const char *  reason  )

static

set_plan_state()

void JOIN::set_plan_state ( enum_plan_state  plan_state_arg )

private

Sets the plan's state of the JOIN.

This is always the final step of optimization; starting from this call, we expose the plan to other connections (via EXPLAIN CONNECTION) so the plan has to be final. keyread_optim is set here.

set_prefix_tables()

void JOIN::set_prefix_tables ( )

private

Assign set of available (prefix) tables to all tables in query block.

Also set added tables, ie the tables added in each JOIN_TAB compared to the previous JOIN_TAB. This function must be called for every query block after the table order has been determined.

set_query_result()

void Sql_cmd_dml::set_query_result

(

Query_result *

result

)

Set query result object for this query statement.

set_secondary_engine_fail_reason()

static bool set_secondary_engine_fail_reason ( const LEX *  lex, const char *  reason  )

static

set_semijoin_embedding()

void JOIN::set_semijoin_embedding ( )

private

Set semi-join embedding join nest pointers.

Set pointer to embedding semi-join nest for all semi-joined tables. This is the closest semi-join or anti-join nest. Note that this must be done for every table inside all semi-join nests, even for tables within outer join nests embedded in semi-join nests. A table can never be part of multiple semi-join nests, hence no ambiguities can ever occur. Note also that the pointer is not set for Table_ref objects that are outer join nests within semi-join nests.

set_semijoin_info()

void JOIN::set_semijoin_info ( )

private

Set the first_sj_inner_tab and last_sj_inner_tab fields for all tables inside the semijoin nests of the query.

set_statement_timer()

bool set_statement_timer

(

THD *

thd

)

Set the time until the currently running statement is aborted.

Parameters

thd	Thread (session) context.

Returns

true if the timer was armed.

whether timer can be set for the statement or not should be checked before calling set_statement_timer function.

set_table()

void JOIN_TAB::set_table

(

TABLE *

t

)

setup_join_buffering()

static bool setup_join_buffering ( JOIN_TAB *  tab, JOIN *  join, uint  no_jbuf_after  )

static

Set up join buffering for a specified table, if possible.

Parameters

tab	joined table to check join buffer usage for
join	join for which the check is performed
no_jbuf_after	don't use join buffering after table with this number

Returns

false if successful, true if error. Currently, allocation errors for join cache objects are ignored, and regular execution is chosen silently.

The function finds out whether the table 'tab' can be joined using a join buffer. This check is performed after the best execution plan for 'join' has been chosen. If the function decides that a join buffer can be employed then it selects the most appropriate join cache type, which later will be instantiated by init_join_cache(). If it has already been decided to not use join buffering for this table, no action is taken.

Often it is already decided that join buffering will be used earlier in the optimization process, and this will also ensure that the most correct cost for the operation is calculated, and hence the probability of choosing an optimal join plan is higher. However, some join buffering decisions cannot currently be taken before this stage, hence we need this function to decide the most accurate join buffering strategy.

The result of the check and the type of the join buffer to be used depend on:

• the access method to access rows of the joined table
• whether the join table is an inner table of an outer join or semi-join
• the optimizer_switch settings for join buffering
• the join 'options'. In any case join buffer is not used if the number of the joined table is greater than 'no_jbuf_after'.

If block_nested_loop is turned on, and if all other criteria for using join buffering is fulfilled (see below), then join buffer is used for any join operation (inner join, outer join, semi-join) with 'JT_ALL' access method. In that case, a JOIN_CACHE_BNL type is always employed.

If an index is used to access rows of the joined table and batched_key_access is on, then a JOIN_CACHE_BKA type is employed.

If the function decides that a join buffer can be used to join the table 'tab' then it sets tab->use_join_cache to reflect the chosen algorithm.

Note

For a nested outer join/semi-join, currently, we either use join buffers for all inner tables or for none of them.

Join buffering is enabled for a few more cases for secondary engine. Currently if blocked nested loop(BNL) is employed for join buffering, it is replaced by hash joins in the executor. So the reasons for disabling join buffering because of the way BNL works are no more valid. This gives us an oppotunity to enable join buffering for more cases. However, we enable it only for secondary engine (in particular for semijoins), because of the following reasons: Secondary engine does not care about the cost based decisions involved in arriving at the best possible semijoin strategy; because it can only interpret a plan using "FirstMatch" strategy and can only do table scans. So the choices are very limited. However, it's not the case for mysql. There are serveral semijoin stratagies that could be picked. And these are picked based on the assumption that a nested-loop join(NLJ) would be used because optimizer currently generates plans only for NLJs and not hash joins. So, when executor replaces with hash joins, the number of rows that would be looked into for a particular semijoin strategy will differ from what the optimizer presumed while picking that strategy. For mysql server, we could enable join buffering for more cases, when a cost model for using hash joins is developed and optimizer could generate plans for hash joins.

      JOIN_TAB *first_tab= join->join_tab+join->const_tables;
      uint n_tables= i-join->const_tables;
      / *
        We normally put all preceding tables into the join buffer, except
        for the constant tables.
        If we're inside a semi-join materialization nest, e.g.

           outer_tbl1  outer_tbl2  ( inner_tbl1, inner_tbl2 ) ...
                                                     ^-- we're here

        then we need to put into the join buffer only the tables from
        within the nest.
      * /
      if (i >= first_sjm_table && i < last_sjm_table)
      {
        n_tables= i - first_sjm_table; // will be >0 if we got here
        first_tab= join->join_tab + first_sjm_table;
      }

setup_semijoin_dups_elimination()

static bool setup_semijoin_dups_elimination ( JOIN *  join, uint  no_jbuf_after  )

static

Setup the strategies to eliminate semi-join duplicates.

Parameters

join	Join to process
no_jbuf_after	Do not use join buffering after the table with this number

Return values

false	OK
true	Out of memory error

Setup the strategies to eliminate semi-join duplicates. At the moment there are 5 strategies:

1. DuplicateWeedout (use of temptable to remove duplicates based on rowids of row combinations)
2. FirstMatch (pick only the 1st matching row combination of inner tables)
3. LooseScan (scanning the sj-inner table in a way that groups duplicates together and picking the 1st one)
4. MaterializeLookup (Materialize inner tables, then setup a scan over outer correlated tables, lookup in materialized table)
5. MaterializeScan (Materialize inner tables, then setup a scan over materialized tables, perform lookup in outer tables)

The join order has "duplicate-generating ranges", and every range is served by one strategy or a combination of FirstMatch with with some other strategy.

"Duplicate-generating range" is defined as a range within the join order that contains all of the inner tables of a semi-join. All ranges must be disjoint, if tables of several semi-joins are interleaved, then the ranges are joined together, which is equivalent to converting

SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )

to

SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...).

Applicability conditions are as follows:

DuplicateWeedout strategy

(ot|nt)*  [ it ((it|ot|nt)* (it|ot))]  (nt)*
+------+  +=========================+  +---+
  (1)                 (2)               (3)

1. Prefix of OuterTables (those that participate in IN-equality and/or are correlated with subquery) and outer Non-correlated tables.
2. The handled range. The range starts with the first sj-inner table, and covers all sj-inner and outer tables Within the range, Inner, Outer, outer non-correlated tables may follow in any order.
3. The suffix of outer non-correlated tables.

FirstMatch strategy

(ot|nt)*  [ it (it)* ]  (nt)*
+------+  +==========+  +---+
  (1)          (2)        (3)

1. Prefix of outer correlated and non-correlated tables
2. The handled range, which may contain only inner tables.
3. The suffix of outer non-correlated tables.

LooseScan strategy

(ot|ct|nt) [ loosescan_tbl (ot|nt|it)* it ]  (ot|nt)*
+--------+   +===========+ +=============+   +------+
   (1)           (2)          (3)              (4)

1. Prefix that may contain any outer tables. The prefix must contain all the non-trivially correlated outer tables. (non-trivially means that the correlation is not just through the IN-equality).
2. Inner table for which the LooseScan scan is performed. Notice that special requirements for existence of certain indexes apply to this table,

   See also

   class Loose_scan_opt.

3. The remainder of the duplicate-generating range. It is served by application of FirstMatch strategy. Outer IN-correlated tables must be correlated to the LooseScan table but not to the inner tables in this range. (Currently, there can be no outer tables in this range because of implementation restrictions,

   See also

   Optimize_table_order::advance_sj_state()).

4. The suffix of outer correlated and non-correlated tables.

MaterializeLookup strategy

(ot|nt)*  [ it (it)* ]  (nt)*
+------+  +==========+  +---+
   (1)         (2)        (3)

1. Prefix of outer correlated and non-correlated tables.
2. The handled range, which may contain only inner tables. The inner tables are materialized in a temporary table that is later used as a lookup structure for the outer correlated tables.
3. The suffix of outer non-correlated tables.

MaterializeScan strategy

(ot|nt)*  [ it (it)* ]  (ot|nt)*
+------+  +==========+  +-----+
   (1)         (2)         (3)

1. Prefix of outer correlated and non-correlated tables.
2. The handled range, which may contain only inner tables. The inner tables are materialized in a temporary table which is later used to setup a scan.
3. The suffix of outer correlated and non-correlated tables.

Note that MaterializeLookup and MaterializeScan has overlap in their patterns. It may be possible to consolidate the materialization strategies into one.

The choice between the strategies is made by the join optimizer (see advance_sj_state() and fix_semijoin_strategies()). This function sets up all fields/structures/etc needed for execution except for setup/initialization of semi-join materialization which is done in setup_materialized_table().

setup_semijoin_materialized_table()

bool JOIN::setup_semijoin_materialized_table ( JOIN_TAB *  tab, uint  tableno, POSITION *  inner_pos, POSITION *  sjm_pos  )

private

Setup the materialized table for a semi-join nest.

Parameters

tab	join_tab for the materialized semi-join table
tableno	table number of materialized table
inner_pos	information about the first inner table of the subquery
sjm_pos	information about the materialized semi-join table, to be filled with data.

Setup execution structures for one semi-join materialization nest:

• Create the materialization temporary table, including Table_ref object.
• Create a list of Item_field objects per column in the temporary table.
• Create a keyuse array describing index lookups into the table (for MaterializeLookup)

Returns

False if OK, True if error

simple_remove_const()

ORDER * simple_remove_const	(	ORDER *	order,
		Item *	where
	)

Filter out ORDER BY items that are equal to constants in WHERE condition.

This function is a limited version of remove_const() for use with non-JOIN statements (i.e. single-table UPDATE and DELETE).

Parameters

order	Linked list of ORDER BY arguments.
where	Where condition.

Returns

pointer to new filtered ORDER list or NULL if whole list eliminated

Note

This function overwrites input order list.

sj_table_is_included()

static bool sj_table_is_included ( JOIN *  join, JOIN_TAB *  join_tab  )

static

sjm_query_block_id()

uint QEP_TAB::sjm_query_block_id

(

)

const

Returns

query block id for an inner table of materialized semi-join, and 0 for all other tables.

Note

implementation is not efficient (loops over all tables) - use this function only in EXPLAIN.

sort_keyuse()

static bool sort_keyuse ( const Key_use &  a, const Key_use &  b  )

static

Compares two keyuse elements.

Parameters

a	first Key_use element
b	second Key_use element

Compare Key_use elements so that they are sorted as follows:

1. By table.
2. By key for each table.
3. By keypart for each key.
4. Const values.
5. Ref_or_null.

Return values

true	If a < b.
false	If a >= b.

substitute_for_best_equal_field()

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.

The function retrieves the cond condition and for each encountered multiple equality predicate it sorts the field references in it according to the order of tables specified by the table_join_idx parameter. Then it eliminates the multiple equality predicate by replacing it with the conjunction of simple equality predicates equating every field from the multiple equality to the first field in it, or to the constant, if there is any. After this, the function retrieves all other conjuncted predicates and substitutes every field reference by the field reference to the first equal field or equal constant if there are any.

Parameters

thd	the session context
cond	condition to process
cond_equal	multiple equalities to take into consideration
table_join_idx	index to tables determining field preference

Note

At the first glance, a full sort of fields in multiple equality seems to be an overkill. Yet it's not the case due to possible new fields in multiple equality item of lower levels. We want the order in them to comply with the order of upper levels.

Returns

The transformed condition, or NULL in case of error

substitute_gc()

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.

This function does 3 things: 1) Creates list of all GC fields that are a part of a key and the GC expression is a function. All query tables are scanned. If there's no such fields, function exits. 2) By means of Item::compile() WHERE clause is transformed.

See also

Item_func::gc_subst_transformer() for details. 3) If there's ORDER/GROUP BY clauses, this function tries to substitute expressions in these lists with GC too. It removes from the list of indexed GC all elements which index blocked by hints. This is done to reduce amount of further work. Next it goes through ORDER/GROUP BY list and matches the expression in it against GC expressions in indexed GC list. When a match is found, the expression is replaced with a new Item_field for the matched GC field. Also, this new field is added to the hidden part of all_fields list.

Parameters

thd	thread handle
query_block	the current select
where_cond	the WHERE condition, possibly NULL
group_list	the GROUP BY clause, possibly NULL
order	the ORDER BY clause, possibly NULL

Returns

true if the GROUP BY clause or the ORDER BY clause was changed, false otherwise

test_if_cheaper_ordering()

bool test_if_cheaper_ordering	(	const JOIN_TAB *	tab,
		ORDER_with_src *	order,
		TABLE *	table,
		Key_map	usable_keys,
		int	ref_key,
		ha_rows	select_limit,
		int *	new_key,
		int *	new_key_direction,
		ha_rows *	new_select_limit,
		uint *	new_used_key_parts,
		uint *	saved_best_key_parts,
		double *	new_read_time
	)

Find a cheaper access key than a given key.

Parameters

	tab	NULL or JOIN_TAB of the accessed table
	order	Linked list of ORDER BY arguments
	table	Table if tab == NULL or tab->table()
	usable_keys	Key map to find a cheaper key in
	ref_key	0 <= key < MAX_KEY - key number (hint) to start the search -1 - no key number provided
	select_limit	LIMIT value, or HA_POS_ERROR if no limit
[out]	new_key	Key number if success, otherwise undefined
[out]	new_key_direction	Return -1 (reverse) or +1 if success, otherwise undefined
[out]	new_select_limit	Return adjusted LIMIT
[out]	new_used_key_parts	NULL by default, otherwise return number of new_key prefix columns if success or undefined if the function fails
[out]	saved_best_key_parts	NULL by default, otherwise preserve the value for further use in ReverseIndexRangeScanIterator
[out]	new_read_time	NULL by default, otherwise return the cost of access using new_key if success or undefined if the function fails

Note

This function takes into account table->quick_condition_rows statistic (that is calculated by JOIN::make_join_plan()). However, single table procedures such as mysql_update() and mysql_delete() never call JOIN::make_join_plan(), so they have to update it manually (

See also

get_index_for_order()). This function resets bits in TABLE::quick_keys for indexes with mixed ASC/DESC keyparts as range scan doesn't support range reordering required for them.

test_if_ft_index_order()

static Item_func_match * test_if_ft_index_order ( ORDER *  order )

static

Test if ORDER BY is a single MATCH function(ORDER BY MATCH) and sort order is descending.

Parameters

order

pointer to ORDER struct.

Return values

Pointer	to MATCH function if order is 'ORDER BY MATCH() DESC'
NULL	otherwise

test_if_order_by_key()

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.

Parameters

	order_src	Sort order
	table	Table to sort
	idx	Index to check
[out]	used_key_parts	NULL by default, otherwise return value for used key parts.
[out]	skip_quick	Whether found index can be used for backward range scans

Note

used_key_parts is set to correct key parts used if return value != 0 (On other cases, used_key_part may be changed) Note that the value may actually be greater than the number of index key parts. This can happen for storage engines that have the primary key parts as a suffix for every secondary key.

Return values

1	key is ok.
0	Key can't be used
-1	Reverse key can be used

test_if_skip_sort_order()

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  )

static

Test if we can skip ordering by using an index.

If the current plan is to use an index that provides ordering, the plan will not be changed. Otherwise, if an index can be used, the JOIN_TAB / tab->select struct is changed to use the index.

The index must cover all fields in <order>, or it will not be considered.

Parameters

	tab	NULL or JOIN_TAB of the accessed table
	order	Linked list of ORDER BY arguments
	select_limit	LIMIT value, or HA_POS_ERROR if no limit
	no_changes	No changes will be made to the query plan.
	map	Key_map of applicable indexes.
[out]	order_idx	Number of index selected, -1 if no applicable index found

Note

This function may change tmp_table_param.precomputed_group_by. This affects how create_tmp_table() treats aggregation functions, so count_field_types() must be called again to make sure this is taken into consideration.

Return values

0	We have to use filesort to do the sorting
1	We can use an index.

test_if_subkey()

static uint test_if_subkey ( ORDER_with_src *  order, JOIN_TAB *  tab, uint  ref, uint  ref_key_parts, const Key_map *  usable_keys  )

static

Test if we can use one of the 'usable_keys' instead of 'ref' key for sorting.

Parameters

order	The query block's order clause.
tab	Current JOIN_TAB.
ref	Number of key, used for WHERE clause
ref_key_parts	Index columns used for ref lookup.
usable_keys	Keys for testing

Returns

• MAX_KEY If we can't use other key
• the number of found key Otherwise

test_if_subpart()

bool test_if_subpart	(	ORDER *	a,
		ORDER *	b
	)

Return 1 if second is a subpart of first argument.

If first parts has different direction, change it to second part (group is sorted like order)

test_skip_sort()

void JOIN::test_skip_sort ( )

private

Test if an index could be used to replace filesort for ORDER BY/GROUP BY.

Investigate whether we may use an ordered index as part of either DISTINCT, GROUP BY or ORDER BY execution. An ordered index may be used for only the first of any of these terms to be executed. This is reflected in the order which we check for test_if_skip_sort_order() below. However we do not check for DISTINCT here, as it would have been transformed to a GROUP BY at this stage if it is a candidate for ordered index optimization. If a decision was made to use an ordered index, the availability if such an access path is stored in 'm_ordered_index_usage' for later use by 'execute' or 'explain'

trace_table_dependencies()

static void trace_table_dependencies ( Opt_trace_context *  trace, JOIN_TAB *  join_tabs, uint  table_count  )

static

Writes to the optimizer trace information about dependencies between tables.

Parameters

trace	optimizer trace
join_tabs	all JOIN_TABs of the join
table_count	how many JOIN_TABs in the 'join_tabs' array

type_conversion_status_to_store_key()

static store_key::store_key_result type_conversion_status_to_store_key ( THD *  thd, type_conversion_status  ts  )

static

types_allow_materialization()

bool types_allow_materialization	(	Item *	outer,
		Item *	inner
	)

Check if two items are compatible wrt.

materialization.

Parameters

outer	Expression from outer query
inner	Expression from inner query

Return values

true	If subquery types allow materialization.
false	Otherwise.

Note

the purpose is similar to that of comparable_in_index().

unplug_join_tabs()

void JOIN::unplug_join_tabs ( )

private

update_depend_map() [1/2]

void JOIN::update_depend_map ( )

private

Update the dependency map for the tables.

update_depend_map() [2/2]

void JOIN::update_depend_map ( ORDER *  order )

private

Update the dependency map for the sort order.

update_equalities_for_sjm()

bool JOIN::update_equalities_for_sjm

(

)

Update equalities and keyuse references after semi-join materialization strategy is chosen.

For each multiple equality that contains a field that is selected from a subquery, and that subquery is executed using a semi-join materialization strategy, add the corresponding column in the materialized temporary table to the equality. For each injected semi-join equality that is not converted to multiple equality, replace the reference to the expression selected from the subquery with the corresponding column in the temporary table.

This is needed to properly reflect the equalities that involve injected semi-join equalities when materialization strategy is chosen.

See also

eliminate_item_equal() for how these equalities are used to generate correct equality predicates.

The MaterializeScan semi-join strategy requires some additional processing: All primary tables after the materialized temporary table must be inspected for keyuse objects that point to expressions from the subquery tables. These references must be replaced with references to corresponding columns in the materialized temporary table instead. Those primary tables using ref access will thus be made to depend on the materialized temporary table instead of the subquery tables.

Only the injected semi-join equalities need this treatment, other predicates will be handled correctly by the regular item substitution process.

Returns

False if success, true if error

update_ref_and_keys()

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  )

static

Update keyuse array with all possible keys we can use to fetch rows.

Parameters

	thd	session context
[out]	keyuse	Put here ordered array of Key_use structures
	join_tab	Array in table number order
	tables	Number of tables in join
	cond	WHERE condition (note that the function analyzes join_tab[i]->join_cond() too)
	normal_tables	Tables not inner w.r.t some outer join (ones for which we can make ref access based the WHERE clause)
	query_block	current SELECT
[out]	sargables	Array of found sargable candidates

Returns

false if success, true if error

update_sargable_from_const()

void JOIN::update_sargable_from_const ( SARGABLE_PARAM *  sargables )

private

Update info on indexes that can be used for search lookups as reading const tables may has added new sargable predicates.

uses_index_fields_only()

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.

The expression can use any fields in any other tables.

The expression is guaranteed not to be AND or OR - those constructs are handled outside of this function.

Restrict some function types from being pushed down to storage engine: a) Don't push down the triggered conditions with exception for IS_NOT_NULL_COMPL trigger condition since the NULL-complemented rows are added at a later stage in the iterators, so we won't see NULL-complemented rows when evaluating it as an index condition. Nested outer joins execution code may need to evaluate a condition several times (both triggered and untriggered). TODO: Consider cloning the triggered condition and using the copies for:

1. push the first copy down, to have most restrictive index condition possible.
2. Put the second copy into tab->m_condition. b) Stored functions contain a statement that might start new operations (like DML statements) from within the storage engine. This does not work against all SEs. c) Subqueries might contain nested subqueries and involve more tables. TODO: ROY: CHECK THIS d) Do not push down internal functions of type DD_INTERNAL_FUNC. When ICP is enabled, pushing internal functions to storage engine for evaluation will open data-dictionary tables. In InnoDB storage engine this will result in situation like recursive latching of same page by the same thread. To avoid such situation, internal functions of type DD_INTERNAL_FUNC are not pushed to storage engine for evaluation.

Parameters

item	Expression to check
tbl	The table having the index
keyno	The index number
other_tbls_ok	true <=> Fields of other non-const tables are allowed

Returns

false if No, true if Yes

validate_use_secondary_engine()

bool validate_use_secondary_engine

(

const LEX *

lex

)

Validates a query that uses the secondary engine.

No validations are done if query has not been prepared against the secondary engine.

Parameters

lex	Parse tree descriptor.

Returns

True if error, false otherwise.

warn_index_not_applicable()

static void warn_index_not_applicable ( THD *  thd, const Field *  field, const Key_map  cant_use_index  )

static

If EXPLAIN or if the –safe-updates option is enabled, add a warning that an index cannot be used for ref access.

If EXPLAIN or if the –safe-updates option is enabled, add a warning for each index that cannot be used for ref access due to either type conversion or different collations on the field used for comparison

Example type conversion (char compared to int):

CREATE TABLE t1 (url char(1) PRIMARY KEY); SELECT * FROM t1 WHERE url=1;

Example different collations (danish vs german2):

CREATE TABLE t1 (url char(1) PRIMARY KEY) collate latin1_danish_ci; SELECT * FROM t1 WHERE url='1' collate latin1_german2_ci;

Parameters

thd	Thread for the connection that submitted the query
field	Field used in comparison
cant_use_index	Indexes that cannot be used for lookup

Variable Documentation

antijoin_null_cond

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