Classes
class	COND_CMP
struct	Key_field
	Used when finding key fields. More...
class	Plan_change_watchdog
Defines
#define	KEY_OPTIMIZE_EXISTS 1
#define	KEY_OPTIMIZE_REF_OR_NULL 2
#define	ICP_COND_USES_INDEX_ONLY 10
Functions
void	reset_nj_counters (List< TABLE_LIST > *join_list)
Item_equal *	find_item_equal (COND_EQUAL cond_equal, Field field, bool *inherited_fl)
Item_field *	get_best_field (Item_field item_field, COND_EQUAL cond_equal)
Item *	build_equal_items (THD thd, Item cond, COND_EQUAL inherited, bool do_inherit, List< TABLE_LIST > join_list, COND_EQUAL **cond_equal_ref)
Item *	substitute_for_best_equal_field (Item cond, COND_EQUAL cond_equal, void *table_join_idx)
void	update_depend_map (JOIN *join)
bool	uses_index_fields_only (Item item, TABLE tbl, uint keyno, bool other_tbls_ok)
bool	is_indexed_agg_distinct (JOIN join, List< Item_field > out_args)
Key_use_array *	create_keyuse_for_table (THD thd, TABLE table, uint keyparts, Item_field **fields, List< Item > outer_exprs)
Item *	make_cond_for_table (Item *cond, table_map tables, table_map used_table, bool exclude_expensive_cond)
Item *	optimize_cond (THD thd, Item conds, COND_EQUAL *cond_equal, List< TABLE_LIST > join_list, bool build_equalities, Item::cond_result *cond_value)
Item *	remove_eq_conds (THD thd, Item cond, Item::cond_result *cond_value)
bool	const_expression_in_where (Item conds, Item item, Item **comp_item)
uint	find_shortest_key (TABLE table, const key_map usable_keys)
bool	handle_select (THD thd, select_result result, ulong setup_tables_done_option)
bool	types_allow_materialization (Item outer, Item inner)
	Check if two items are compatible wrt. materialization.
bool	mysql_select (THD thd, TABLE_LIST tables, uint wild_num, List< Item > &fields, Item conds, SQL_I_List< ORDER > order, SQL_I_List< ORDER > group, Item having, ulonglong select_options, select_result result, SELECT_LEX_UNIT unit, SELECT_LEX *select_lex)
void	calc_used_field_length (THD thd, JOIN_TAB join_tab)
bool	create_ref_for_key (JOIN join, JOIN_TAB j, Key_use *org_keyuse, table_map used_tables)
bool	and_conditions (Item *e1, Item e2)
bool	make_join_readinfo (JOIN *join, ulonglong options, uint no_jbuf_after)
bool	error_if_full_join (JOIN *join)
ORDER *	simple_remove_const (ORDER order, Item where)
bool	const_expression_in_where (Item cond, Item comp_item, Field comp_field, Item *const_item)
int	test_if_order_by_key (ORDER order, TABLE table, uint idx, uint *used_key_parts)
bool	is_subkey (KEY_PART_INFO key_part, KEY_PART_INFO ref_key_part, KEY_PART_INFO *ref_key_part_end)
bool	is_ref_or_null_optimized (const JOIN_TAB *tab, uint ref_key)
bool	test_if_skip_sort_order (JOIN_TAB tab, ORDER order, ha_rows select_limit, const bool no_changes, const key_map map, const char clause_type)
void	count_field_types (SELECT_LEX select_lex, TMP_TABLE_PARAM param, List< Item > &fields, bool reset_with_sum_func)
bool	test_if_subpart (ORDER a, ORDER b)
void	calc_group_buffer (JOIN join, ORDER group)
void	free_underlaid_joins (THD thd, SELECT_LEX select)
uint	get_index_for_order (ORDER order, TABLE table, SQL_SELECT select, ha_rows limit, bool need_sort, bool *reverse)
uint	actual_key_parts (KEY *key_info)
uint	actual_key_flags (KEY *key_info)
void	JOIN_CACHE::calc_record_fields ()
int	JOIN_CACHE::alloc_fields (uint external_fields)
void	JOIN_CACHE::create_flag_fields ()
void	JOIN_CACHE::create_remaining_fields (bool all_read_fields)
void	JOIN_CACHE::set_constants ()
bool	JOIN_CACHE::alloc_buffer ()
int	JOIN_CACHE_BNL::init ()
int	JOIN_CACHE_BKA::init ()
bool	JOIN_CACHE_BKA::check_emb_key_usage ()
uint	JOIN_CACHE_BKA::aux_buffer_incr ()
uint	JOIN_CACHE_BKA::aux_buffer_min_size () const
bool	JOIN_CACHE_BKA::skip_index_tuple (range_seq_t rseq, char *range_info)
uint	JOIN_CACHE::write_record_data (uchar link, bool is_full)
virtual void	JOIN_CACHE::reset_cache (bool for_writing)
	Reset the join buffer for reading/writing: default implementation.
virtual bool	JOIN_CACHE::put_record_in_cache ()
virtual bool	JOIN_CACHE::get_record ()
virtual void	JOIN_CACHE::get_record_by_pos (uchar *rec_ptr)
virtual bool	JOIN_CACHE::get_match_flag_by_pos (uchar *rec_ptr)
int	JOIN_CACHE::read_some_record_fields ()
void	JOIN_CACHE::read_some_flag_fields ()
uint	JOIN_CACHE::read_record_field (CACHE_FIELD *copy, bool last_record)
bool	JOIN_CACHE::read_referenced_field (CACHE_FIELD copy, uchar rec_ptr, uint *len)
virtual bool	JOIN_CACHE::skip_record_if_match ()
virtual void	JOIN_CACHE::restore_last_record ()
enum_nested_loop_state	JOIN_CACHE::join_records (bool skip_last)
enum_nested_loop_state	JOIN_CACHE_BNL::join_matching_records (bool skip_last)
bool	JOIN_CACHE::set_match_flag_if_none (JOIN_TAB first_inner, uchar rec_ptr)
enum_nested_loop_state	JOIN_CACHE::generate_full_extensions (uchar *rec_ptr)
virtual bool	JOIN_CACHE::check_match (uchar *rec_ptr)
virtual enum_nested_loop_state	JOIN_CACHE::join_null_complements (bool skip_last)
enum_nested_loop_state	JOIN_CACHE_BKA::join_matching_records (bool skip_last)
bool	JOIN_CACHE_BKA::init_join_matching_records (RANGE_SEQ_IF *seq_funcs, uint ranges)
void	JOIN_CACHE::read_all_flag_fields_by_pos (uchar *rec_ptr)
virtual uint	JOIN_CACHE_BKA::get_next_key (uchar **key)
int	JOIN_CACHE_BKA_UNIQUE::init ()
void	JOIN_CACHE_BKA_UNIQUE::reset_cache (bool for_writing)
	Reset the join buffer for reading/writing: default implementation.
bool	JOIN_CACHE_BKA_UNIQUE::put_record_in_cache ()
bool	JOIN_CACHE_BKA_UNIQUE::get_record ()
bool	JOIN_CACHE_BKA_UNIQUE::skip_record_if_match ()
bool	JOIN_CACHE_BKA_UNIQUE::key_search (uchar key, uint key_len, uchar *key_ref_ptr)
bool	JOIN_CACHE_BKA_UNIQUE::skip_index_tuple (range_seq_t rseq, char *range_info)
enum_nested_loop_state	JOIN_CACHE_BKA_UNIQUE::join_matching_records (bool skip_last)
virtual bool	JOIN_CACHE_BKA_UNIQUE::check_all_match_flags_for_key (uchar *key_chain_ptr)
uint	JOIN_CACHE_BKA_UNIQUE::get_next_key (uchar **key)
virtual bool	JOIN_CACHE_BKA_UNIQUE::check_match (uchar *rec_ptr)
int	JOIN::optimize ()
bool	JOIN::update_equalities_for_sjm ()
void	JOIN::set_semijoin_embedding ()
bool	JOIN::flatten_subqueries ()
void	JOIN::remove_subq_pushed_predicates (Item **where)
bool	JOIN::generate_derived_keys ()
	Add keys to derived tables'/views' result tables in a list.
void	JOIN::drop_unused_derived_keys ()
	Drop unused keys for each materialized derived table/view.
bool	JOIN::cache_const_exprs ()
bool	JOIN::decide_subquery_strategy ()
void	JOIN::refine_best_rowcount ()
void	JOIN::reset ()
bool	JOIN::prepare_result (List< Item > **columns_list)
bool	JOIN::explain ()
bool	JOIN::destroy ()
bool	JOIN::get_best_combination ()
void	st_join_table::cleanup ()
uint	st_join_table::sjm_query_block_id () const
bool	st_join_table::and_with_jt_and_sel_condition (Item *tmp_cond, uint line)
bool	st_join_table::and_with_condition (Item *tmp_cond, uint line)
Item *	st_join_table::unified_condition () const
void	JOIN::join_free ()
void	JOIN::cleanup (bool full)
bool	JOIN::alloc_func_list ()
bool	JOIN::make_sum_func_list (List< Item > &all_fields, List< Item > &send_fields, bool before_group_by, bool recompute=FALSE)
bool	JOIN::rollup_process_const_fields ()
bool	JOIN::rollup_make_fields (List< Item > &all_fields, List< Item > &fields, Item_sum ***func)
void	JOIN::clear ()
bool	JOIN::change_result (select_result *result)
bool	JOIN::add_sorting_to_table (JOIN_TAB tab, ORDER_with_src order)
	Add Filesort object to the given table to sort if with filesort.

Function Documentation

uint actual_key_flags ( KEY * key_info )

Returns key flags depending on OPTIMIZER_SWITCH_USE_INDEX_EXTENSIONS flag.

Parameters:

key_info pointer to KEY structure

Returns:: key flags.

uint actual_key_parts ( 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.

bool JOIN::add_sorting_to_table	(	JOIN_TAB *	tab,
		ORDER_with_src *	order
	)

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

Parameters:

tab	the JOIN_TAB object to attach created Filesort object to
order	List of expressions to sort the table by

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

Returns:: false on success, true on OOM

bool JOIN_CACHE::alloc_buffer ( ) [protected]

Allocate memory for a join buffer.

The function allocates a lump of memory for the join buffer. The size of the allocated memory is 'buff_size' bytes.

Returns:: false if success, otherwise true.

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

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.

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

bool JOIN_TAB::and_with_condition	(	Item *	add_cond,
		uint	line
	)

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
line	Code line this method was called from

Return values:

true	if there was a memory allocation error
false	otherwise

bool JOIN_TAB::and_with_jt_and_sel_condition	(	Item *	add_cond,
		uint	line
	)

Extend join_tab->m_condition and join_tab->select->cond by AND'ing add_cond to them

Parameters:

add_cond	The condition to AND with the existing conditions
line	Code line this method was called from

Return values:

true	if there was a memory allocation error
false	otherwise

uint JOIN_CACHE_BKA::aux_buffer_incr ( ) [protected, virtual]

Calculate the increment of the MRR buffer for a record write

Reimplemented from JOIN_CACHE.

uint JOIN_CACHE_BKA::aux_buffer_min_size ( ) const [protected, virtual]

Calculate the minimume size for the MRR buffer

Calculate the minimume size for the MRR buffer.

Returns:: The minumum size that must be allocated for the MRR buffer

Reimplemented from JOIN_CACHE.

Item* build_equal_items	(	THD *	thd,
		Item *	cond,
		COND_EQUAL *	inherited,
		bool	do_inherit,
		List< TABLE_LIST > *	join_list,
		COND_EQUAL **	cond_equal_ref
	)

Build multiple equalities for a condition and all on expressions 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 on expressions whose direct references can be found in join_list and who inherit directly the multiple equalities just having built.

Note:

The on expression used in an outer join operation inherits all equalities from the on expression 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 on expression 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 on expression 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 on 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. Althogh 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
	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 to which the condition refers to
[out]	cond_equal_ref	pointer to the structure to place built equalities in

Returns:: pointer to the transformed condition containing multiple equalities

bool JOIN::cache_const_exprs ( )

Cache constant expressions in WHERE, HAVING, ON conditions.

Returns:: False if success, True if error

Note:: This function is run after conditions have been pushed down to individual tables, so transformation is applied to JOIN_TAB::condition and not to the WHERE condition.

void calc_group_buffer	(	JOIN *	join,
		ORDER *	group
	)

calc how big buffer we need for comparing group entries.

void calc_used_field_length	(	THD *	thd,
		JOIN_TAB *	join_tab
	)

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

Todo:: why don't we count the rowids that we might need to store when using DuplicateElimination?

bool JOIN::change_result ( select_result * res )

change select_result object of JOIN.

Parameters:

res	new select_result object

Return values:

FALSE	OK
TRUE	error

bool JOIN_CACHE_BKA_UNIQUE::check_match ( uchar * rec_ptr ) [protected, virtual]

Check matching to a partial join record from the join buffer, an implementation specialized for JOIN_CACHE_BKA_UNIQUE. Only JOIN_CACHE_BKA_UNIQUE needs that, because it's the only cache using distinct keys. JOIN_CACHE_BKA, on the other hand, does one key lookup per cached record, so can take a per-record individualized decision for the pushed index condition as soon as it has the index tuple.

See also:: JOIN_CACHE_BKA_UNIQUE::skip_index_tuple; JOIN_CACHE::check_match

Reimplemented from JOIN_CACHE.

void JOIN::cleanup ( bool full )

Cleanup this JOIN, possibly for reuse

Free resources of given join.

Parameters:

fill	true if we should free all resources, call with full==1 should be last, before it this function can be called with full==0

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

void JOIN_TAB::cleanup ( )

Clean up associated table after query execution, including resources

Cleanup table of join operation.

Note:: Notice that this is not a complete cleanup. In some situations, the object may be reused after a cleanup operation, hence we cannot set the table pointer to NULL in this function.

void JOIN::clear ( )

clear results if there are not rows found for group (end_send_group/end_write_group)

bool const_expression_in_where	(	Item *	cond,
		Item *	comp_item,
		Field *	comp_field,
		Item **	const_item
	)

Test if a field or an item is equal to a constant value in WHERE

Parameters:

	cond	WHERE clause expression
	comp_item	Item to find in WHERE expression (if comp_field != NULL)
	comp_field	Field to find in WHERE expression (if comp_item != NULL)
[out]	const_item	intermediate arg, set to Item pointer to NULL

Returns:: TRUE if the field is a constant value in WHERE

Note:: comp_item and comp_field parameters are mutually exclusive.

void count_field_types	(	SELECT_LEX *	select_lex,
		TMP_TABLE_PARAM *	param,
		List< Item > &	fields,
		bool	reset_with_sum_func
	)

Update join with count of the different type of fields.

Key_use_array* create_keyuse_for_table	(	THD *	thd,
		TABLE *	table,
		uint	keyparts,
		Item_field **	fields,
		List< Item >	outer_exprs
	)

Create a keyuse array for a table with a primary key. To be used when creating a materialized temporary table.

Parameters:

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

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

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
first_keyuse	First key part of (possibly multi-part) key
used_tables	Bitmap of available tables

Returns:: False if success, True if error

This function will set up a ref access using the best key found during access path analysis and cost analysis.

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.

bool JOIN::decide_subquery_strategy ( )

Decides between EXISTS and materialization; performs last steps to set up the chosen strategy.

Returns:: 'false' if no error

Note:: If UNION this is called on each contained JOIN.

bool JOIN::destroy ( )

Clean up and destroy join object.

Returns:: false if previous execution was successful, and true otherwise

void JOIN::drop_unused_derived_keys ( )

Drop unused keys for each materialized derived table/view.

For each materialized derived table/view, call TABLE::use_index to save one index chosen by the optimizer and ignore others. If no key is chosen, then all keys will be ignored.

bool error_if_full_join ( JOIN * join )

Give error if we some tables are done with a full join.

This is used by multi_table_update and multi_table_delete when running in safe mode.

Parameters:

join	Join condition

Return values:

0	ok
1	Error (full join used)

bool JOIN::explain ( )

Explain join.

Item_equal* find_item_equal	(	COND_EQUAL *	cond_equal,
		Field *	field,
		bool *	inherited_fl
	)

Find the multiple equality predicate containing a field.

The function retrieves the multiple equalities accessed through the con_equal structure from current level and up looking for an equality containing 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
	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;
NULL otherwise.

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

void free_underlaid_joins	(	THD *	thd,
		SELECT_LEX *	select
	)

Free joins of subselect of this select.

Parameters:

thd	THD pointer
select	pointer to st_select_lex which subselects joins we will free

bool JOIN::generate_derived_keys ( )

Add keys to derived tables'/views' result tables in a list.

Parameters:

select_lex generate derived keys for select_lex's derived tables

This function generates keys for all derived tables/views of the select_lex to which this join corresponds to with help of the TABLE_LIST:generate_keys function.

Returns:: FALSE all keys were successfully added.; TRUE OOM error

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.

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.

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.

uint get_index_for_order	(	ORDER *	order,
		TABLE *	table,
		SQL_SELECT *	select,
		ha_rows	limit,
		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
	select	Pointer to access/update select->quick (if any)
	limit	LIMIT clause parameter
[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.

bool handle_select	(	THD *	thd,
		select_result *	result,
		ulong	setup_tables_done_option
	)

This handles SELECT with and without UNION

int JOIN_CACHE_BNL::init ( void ) [virtual]

Initialize operation's internal state. Called once per query execution.

Implements JOIN_CACHE.

int JOIN_CACHE_BKA::init ( void ) [virtual]

Initialize operation's internal state. Called once per query execution.

Implements JOIN_CACHE.

Reimplemented in JOIN_CACHE_BKA_UNIQUE.

int JOIN_CACHE_BKA_UNIQUE::init ( void ) [virtual]

Initialize operation's internal state. Called once per query execution.

Reimplemented from JOIN_CACHE_BKA.

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

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

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

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

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

Parameters:

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

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

Return values:

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

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'

Return values:

true	JT_REF_OR_NULL will be used
false	no JT_REF_OR_NULL access

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

void JOIN::join_free ( )

Release memory and, if possible, the open tables held by this execution plan (and nested plans). It's used to release some tables before the end of execution in order to increase concurrency and reduce memory consumption.

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

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

Todo:: Unlock tables even if the join isn't top level select in the tree

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

Extract a condition that can be checked after reading given table

Parameters:

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

Return values:

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

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

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

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

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

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

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

bool make_join_readinfo	(	JOIN *	join,
		ulonglong	options,
		uint	no_jbuf_after
	)

Plan refinement stage: do various setup things for the executor

Parameters:

join	Join being processed
options	Join's options (checking for SELECT_DESCRIBE, SELECT_NO_JOIN_CACHE)
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

bool JOIN::make_sum_func_list	(	List< Item > &	field_list,
		List< Item > &	send_result_set_metadata,
		bool	before_group_by,
		bool	recompute = `FALSE`
	)

Initialize 'sum_funcs' array with all Item_sum objects.

Parameters:

field_list	All items
send_result_set_metadata	Items in select list
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

bool mysql_select	(	THD *	thd,
		TABLE_LIST *	tables,
		uint	wild_num,
		List< Item > &	fields,
		Item *	conds,
		SQL_I_List< ORDER > *	order,
		SQL_I_List< ORDER > *	group,
		Item *	having,
		ulonglong	select_options,
		select_result *	result,
		SELECT_LEX_UNIT *	unit,
		SELECT_LEX *	select_lex
	)

An entry point to single-unit select (a select without UNION).

Parameters:

thd	thread handler
tables	list of all tables used in this query. The tables have been pre-opened.
wild_num	number of wildcards used in the top level select of this query. For example statement SELECT , t1., catalog.t2.* FROM t0, t1, t2; has 3 wildcards.
fields	list of items in SELECT list of the top-level select e.g. SELECT a, b, c FROM t1 will have Item_field for a, b and c in this list.
conds	top level item of an expression representing WHERE clause of the top level select
order	linked list of ORDER BY agruments
group	linked list of GROUP BY arguments
having	top level item of HAVING expression
select_options	select options (BIG_RESULT, etc)
result	an instance of result set handling class. This object is responsible for send result set rows to the client or inserting them into a table.
unit	top-level UNIT of this query UNIT is an artificial object created by the parser for every SELECT clause. e.g. SELECT * FROM t1 WHERE a1 IN (SELECT * FROM t2) has 2 unions.
select_lex	the only SELECT_LEX of this query

Return values:

false	success
true	an error

int JOIN::optimize ( )

global select optimisation.

Note:: error code saved in field 'error'

Return values:

0	success
1	error

Todo:: Above we passed unique=false. But for this query: (oe1, oe2) IN (SELECT primary_key, non_key_maybe_null_field FROM tbl) we could use "unique=true" for the first index component and let Item_is_not_null_test(non_key_maybe_null_field) handle the second.

Push joins to handler(s) whenever possible. The handlers will inspect the QEP through the AQP (Abstract Query Plan), and extract from it whatewer it might implement of pushed execution. It is the responsibility if the handler to store any information it need for later execution of pushed queries.

Currently pushed joins are only implemented by NDB. It only make sense to try pushing if > 1 non-const tables.

Set up access functions for the tables as required by the selected access type.

Item* optimize_cond	(	THD *	thd,
		Item *	conds,
		COND_EQUAL **	cond_equal,
		List< TABLE_LIST > *	join_list,
		bool	build_equalities,
		Item::cond_result *	cond_value
	)

Optimize conditions by

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

Parameters:

	join	pointer to the structure providing all context info for the query
	conds	conditions to optimize
	join_list	list of join tables to which the condition refers to
[out]	cond_value	Not changed if conds was empty COND_TRUE if conds is always true COND_FALSE if conds is impossible COND_OK otherwise

Returns:: optimized conditions

bool JOIN::prepare_result ( List< Item > ** columns_list )

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

void JOIN_CACHE::read_all_flag_fields_by_pos ( uchar * rec_ptr ) [protected]

Reads all flag fields of a positioned record from the join buffer. Including all flag fields (of this record) stored in the previous join buffers.

Parameters:

rec_ptr position of the first field of the record in the join buffer

void JOIN_CACHE::read_some_flag_fields ( ) [protected]

Read some flag fields of a record from the join buffer.

Reads all flag fields stored in this join buffer, for the current record (at 'pos'). If the buffer is incremental, flag fields of this record which are stored in previous join buffers are _not_ read so remain unknown: caller must then make sure to call this function on previous buffers too.

The flag fields are read starting from the position 'pos'. The function increments the value of 'pos' by the length of the read data.

Flag fields are copied back to their source.

int JOIN_CACHE::read_some_record_fields ( ) [protected]

Read some flag and data fields of a record from the join buffer.

Reads all fields (flag and data fields) stored in this join buffer, for the current record (at 'pos'). If the buffer is incremental, fields of this record which are stored in previous join buffers are _not_ read so remain unknown: caller must then make sure to call this function on previous buffers too.

The fields are read starting from the position 'pos' which is supposed to point to the beginning of the first record field. The function increments the value of 'pos' by the length of the read data.

Flag fields are copied back to their source; data fields are copied to the record's buffer.

Return values:

(-1)	if there are no more records in the join buffer
<>(-1)	length of the data read from the join buffer

void JOIN::refine_best_rowcount ( )

Refine the best_rowcount estimation based on what happens after tables have been joined: LIMIT and type of result sink.

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

Remove const and eq items. Return new item, or NULL if no condition cond_value is set to according: COND_OK query is possible (field = constant) COND_TRUE always true ( 1 = 1 ) COND_FALSE always false ( 1 = 2 )

SYNPOSIS remove_eq_conds() thd THD environment cond the condition to handle cond_value the resulting value of the condition

NOTES calls the inner_remove_eq_conds to check all the tree reqursively

RETURN Item with the simplified condition

void JOIN::reset ( void )

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

void JOIN_CACHE::reset_cache ( bool for_writing ) [virtual]

Reset the join buffer for reading/writing: default implementation.

Parameters:

for_writing if it's TRUE the function reset the buffer for writing

This default implementation of the virtual function reset_cache() resets the join buffer for reading or writing. If the buffer is reset for reading only the 'pos' value is reset to point to the very beginning of the join buffer. If the buffer is reset for writing additionally:

the counter of the records in the buffer is set to 0,
the the value of 'last_rec_pos' gets pointing at the position just before the buffer,
'end_pos' is set to point to the beginning of the join buffer,
the size of the auxiliary buffer is reset to 0,
the flag 'last_rec_blob_data_is_in_rec_buff' is set to 0.

Reimplemented in JOIN_CACHE_BKA_UNIQUE.

void JOIN_CACHE_BKA_UNIQUE::reset_cache ( bool for_writing ) [virtual]

Reset the join buffer for reading/writing: default implementation.

Parameters:

for_writing if it's TRUE the function reset the buffer for writing

This default implementation of the virtual function reset_cache() resets the join buffer for reading or writing. If the buffer is reset for reading only the 'pos' value is reset to point to the very beginning of the join buffer. If the buffer is reset for writing additionally:

the counter of the records in the buffer is set to 0,
the the value of 'last_rec_pos' gets pointing at the position just before the buffer,
'end_pos' is set to point to the beginning of the join buffer,
the size of the auxiliary buffer is reset to 0,
the flag 'last_rec_blob_data_is_in_rec_buff' is set to 0.

Reimplemented from JOIN_CACHE.

void reset_nj_counters ( List< TABLE_LIST > * join_list )

Set NESTED_JOIN::counter=0 in all nested joins in passed list.

Recursively set NESTED_JOIN::counter=0 for all nested joins contained in the passed join_list.

Parameters:

join_list List of nested joins to process. It may also contain base tables which will be ignored.

bool JOIN::rollup_make_fields	(	List< Item > &	fields_arg,
		List< Item > &	sel_fields,
		Item_sum ***	func
	)

Fill up rollup structures with pointers to fields to use.

Creates copies of item_sum items for each sum level.

Parameters:

fields_arg	List of all fields (hidden and real ones)
sel_fields	Pointer to selected fields
func	Store here a pointer to all fields

Return values:

0	if ok; In this case func is pointing to next not used element.
1	on error

bool JOIN::rollup_process_const_fields ( )

Wrap all constant Items in GROUP BY list.

For ROLLUP queries each constant item referenced in GROUP BY list is wrapped up into an Item_func object yielding the same value as the constant item. The objects of the wrapper class are never considered as constant items and besides they inherit all properties of the Item_result_field class. This wrapping allows us to ensure writing constant items into temporary tables whenever the result of the ROLLUP operation has to be written into a temporary table, e.g. when ROLLUP is used together with DISTINCT in the SELECT list. Usually when creating temporary tables for a intermidiate result we do not include fields for constant expressions.

Return values:

0	if ok
1	on error

void JOIN::set_semijoin_embedding ( )

Set semi-join embedding join nest pointers.

Set pointer to embedding semi-join nest for all semi-joined tables. 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_LIST objects that are outer join nests within semi-join nests.

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

Filter out ORDER items those are equal to constants in WHERE

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
cond	WHERE expression

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

Note:: This function overwrites input order list.

uint JOIN_TAB::sjm_query_block_id ( ) const

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

bool JOIN_CACHE_BKA_UNIQUE::skip_index_tuple	(	range_seq_t	rseq,
		char *	range_info
	)

Check if the record combination matches the index condition

Parameters:

rseq	Value returned by bka_range_seq_init()
range_info	MRR range association data

See also:: JOIN_CACHE_BKA::skip_index_tuple(). This function is the variant for use with JOIN_CACHE_BKA_UNIQUE. The difference from JOIN_CACHE_BKA case is that there may be multiple previous table record combinations that share the same key, i.e. they map to the same MRR range. And for all of those records, we have just done one single key lookup in the current table, found an index tuple. If in this function we discard this index tuple, all those records will be eliminated from the result. Thus, in this function we can discard the index tuple only if _all_ those cached records and the index tuple don't match the pushed index condition. It's a "group-wide decision". Thus we must here loop through all previous table records combinations that match the given MRR range key range_info, searching for a single one matching the index condition. If we find none, we can safely discard the index tuple here, which avoids retrieving the record from the current table. If we instead find one, we cannot discard the index tuple here; later in execution, in join_matching_records(), we can finally take one "case-by-case decision" per cached record, by checking again the index condition (; JOIN_CACHE_BKA_UNIQUE::check_match).

Note:: Possible optimization: Before we unpack the record from a previous table check if this table is used in the condition. If so then unpack the record otherwise skip the unpacking. This should be done by a special virtual method get_partial_record_by_pos().

Return values:

false	The record combination satisfies the index condition
true	Otherwise

Reimplemented from JOIN_CACHE_BKA.

Item* substitute_for_best_equal_field	(	Item *	cond,
		COND_EQUAL *	cond_equal,
		void *	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 it replacing it by 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 substitute every field reference by the field reference to the first equal field or equal constant if there are any.

Parameters:

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

int test_if_order_by_key	(	ORDER *	order,
		TABLE *	table,
		uint	idx,
		uint *	used_key_parts
	)

Test if one can use the key to resolve ORDER BY.

Parameters:

order	Sort order
table	Table to sort
idx	Index to check
used_key_parts	[out] NULL by default, otherwise return value for used key parts.

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

bool test_if_skip_sort_order	(	JOIN_TAB *	tab,
		ORDER *	order,
		ha_rows	select_limit,
		const bool	no_changes,
		const key_map *	map,
		const char *	clause_type
	)

Test if we can skip the ORDER BY by using an index.

SYNOPSIS test_if_skip_sort_order() tab order select_limit no_changes map

If we can use an index, 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.
clause_type	"ORDER BY" etc for printing in optimizer trace

Todo:

sergeyp: Results of all index merge selects actually are ordered by clustered PK values.

Return values:

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

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)

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.

Item * JOIN_TAB::unified_condition ( ) const

Check if JOIN_TAB condition was moved to Filesort condition. If yes then return condition belonging to Filesort, otherwise return condition belonging to JOIN_TAB.

void update_depend_map ( JOIN * join )

Update the dependency map for the tables.

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

Classes

Defines

Functions

Function Documentation