My Project
Classes | Defines | Functions
Query Optimizer

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_equalfind_item_equal (COND_EQUAL *cond_equal, Field *field, bool *inherited_fl)
Item_fieldget_best_field (Item_field *item_field, COND_EQUAL *cond_equal)
Itembuild_equal_items (THD *thd, Item *cond, COND_EQUAL *inherited, bool do_inherit, List< TABLE_LIST > *join_list, COND_EQUAL **cond_equal_ref)
Itemsubstitute_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_arraycreate_keyuse_for_table (THD *thd, TABLE *table, uint keyparts, Item_field **fields, List< Item > outer_exprs)
Itemmake_cond_for_table (Item *cond, table_map tables, table_map used_table, bool exclude_expensive_cond)
Itemoptimize_cond (THD *thd, Item *conds, COND_EQUAL **cond_equal, List< TABLE_LIST > *join_list, bool build_equalities, Item::cond_result *cond_value)
Itemremove_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)
ORDERsimple_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)
Itemst_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_infopointer 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_infopointer 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:
tabthe JOIN_TAB object to attach created Filesort object to
orderList 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.

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

Return values:
0ok
1Error
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]e1Pointer to condition that will be extended with e2
e2Condition that will extend e1
Return values:
trueif there was a memory allocation error, in which case e1 remains unchanged
falseotherwise
bool JOIN_TAB::and_with_condition ( Item add_cond,
uint  line 
)

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

Parameters:
add_condThe condition to AND with the existing cond for this JOIN_TAB
lineCode line this method was called from
Return values:
trueif there was a memory allocation error
falseotherwise
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_condThe condition to AND with the existing conditions
lineCode line this method was called from
Return values:
trueif there was a memory allocation error
falseotherwise
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:
thdThread handler
condcondition to build the multiple equalities for
inheritedpath to all inherited multiple equality items
do_inheritwhether or not to inherit equalities from other parts of the condition
join_listlist of join tables to which the condition refers to
[out]cond_equal_refpointer to the structure to place built equalities in
Returns:
pointer to the transformed condition containing multiple equalities

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:
resnew select_result object
Return values:
FALSEOK
TRUEerror
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:
filltrue 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.

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:
condWHERE clause expression
comp_itemItem to find in WHERE expression (if comp_field != NULL)
comp_fieldField to find in WHERE expression (if comp_item != NULL)
[out]const_itemintermediate 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:
thdTHD pointer, for memory allocation
tableTable object representing table
keypartsNumber of key parts in the primary key
outer_exprsList 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:
joinThe join object being handled
jThe join_tab which will have the ref access populated
first_keyuseFirst key part of (possibly multi-part) key
used_tablesBitmap 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.

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

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:
joinJoin condition
Return values:
0ok
1Error (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_equalmultiple equalities to search in
fieldfield to look for
[out]inherited_flset 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:
tableTable to scan
usable_keysAllowed 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:
thdTHD pointer
selectpointer to st_select_lex which subselects joins we will free

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

Parameters:
select_lexgenerate 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

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_fieldThe field that we are seeking a substitution for.
cond_equalmultiple 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:
orderLinked list of ORDER BY arguments
tableTable to find a key
selectPointer to access/update select->quick (if any)
limitLIMIT clause parameter
[out]need_sortTRUE if filesort needed
[out]reverseTRUE 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:
jointhe join to check
[out]out_argsCollect the arguments of the aggregate functions to a list. We don't worry about duplicates as these will be sorted out later in get_best_group_min_max.
Returns:
does the query qualify for indexed AGGFN(DISTINCT)
Return values:
trueit does
falseAGGFN(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:
trueJT_REF_OR_NULL will be used
falseno 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_partFirst key parts
ref_key_partSecond key parts
ref_key_part_endLast+1 part of the second key
Note:
Second key MUST be shorter than the first one.
Return values:
1is a subkey
0no 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:
condCondition to analyze
tablesTables for which "current field values" are available
used_tableTable(s) that we are extracting the condition for (may also include PSEUDO_TABLE_BITS, and may be zero)
exclude_expensive_condDo not push expensive conditions
Return values:
<>NULLGenerated condition
=NULL Already checked, OR error

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

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

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

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

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

Note:
make_cond_for_info_schema() uses an algorithm similar to make_cond_for_table().
bool make_join_readinfo ( JOIN join,
ulonglong  options,
uint  no_jbuf_after 
)

Plan refinement stage: do various setup things for the executor

Parameters:
joinJoin being processed
optionsJoin's options (checking for SELECT_DESCRIBE, SELECT_NO_JOIN_CACHE)
no_jbuf_afterDon'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_listAll items
send_result_set_metadataItems in select list
before_group_bySet to 1 if this is called before GROUP BY handling
recomputeSet to TRUE if sum_funcs must be recomputed
Return values:
0ok
1error
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:
thdthread handler
tableslist of all tables used in this query. The tables have been pre-opened.
wild_numnumber 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.
fieldslist 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.
condstop level item of an expression representing WHERE clause of the top level select
orderlinked list of ORDER BY agruments
grouplinked list of GROUP BY arguments
havingtop level item of HAVING expression
select_optionsselect options (BIG_RESULT, etc)
resultan instance of result set handling class. This object is responsible for send result set rows to the client or inserting them into a table.
unittop-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_lexthe only SELECT_LEX of this query
Return values:
falsesuccess
truean error
int JOIN::optimize ( )

global select optimisation.

Note:
error code saved in field 'error'
Return values:
0success
1error
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:
joinpointer to the structure providing all context info for the query
condsconditions to optimize
join_listlist of join tables to which the condition refers to
[out]cond_valueNot 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_ptrposition 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.

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

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_writingif 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_writingif 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_listList 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_argList of all fields (hidden and real ones)
sel_fieldsPointer to selected fields
funcStore here a pointer to all fields
Return values:
0if ok; In this case func is pointing to next not used element.
1on error

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:
0if ok
1on error

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:
orderLinked list of ORDER BY arguments
condWHERE expression
Returns:
pointer to new filtered ORDER list or NULL if whole list eliminated
Note:
This function overwrites input order list.
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:
rseqValue returned by bka_range_seq_init()
range_infoMRR 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:
falseThe record combination satisfies the index condition
trueOtherwise

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:
condcondition to process
cond_equalmultiple equalities to take into consideration
table_join_idxindex 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:
orderSort order
tableTable to sort
idxIndex 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:
1key is ok.
0Key can't be used
-1Reverse 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:
tabNULL or JOIN_TAB of the accessed table
orderLinked list of ORDER BY arguments
select_limitLIMIT value, or HA_POS_ERROR if no limit
no_changesNo changes will be made to the query plan.
mapkey_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:
0We have to use filesort to do the sorting
1We 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:
outerExpression from outer query
innerExpression from inner query
Return values:
TRUEIf subquery types allow materialization.
FALSEOtherwise.

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.

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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines