Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

18129 lines (16379 sloc) 592.835 kB
/* Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; version 2 of the License.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */
/**
@file
@brief
mysql_select and join optimization
@defgroup Query_Optimizer Query Optimizer
@{
*/
#ifdef USE_PRAGMA_IMPLEMENTATION
#pragma implementation // gcc: Class implementation
#endif
#include "sql_priv.h"
#include "unireg.h"
#include "sql_select.h"
#include "sql_cache.h" // query_cache_*
#include "sql_table.h" // primary_key_name
#include "probes_mysql.h"
#include "key.h" // key_copy, key_cmp, key_cmp_if_same
#include "lock.h" // mysql_unlock_some_tables,
// mysql_unlock_read_tables
#include "sql_show.h" // append_identifier
#include "sql_base.h" // setup_wild, setup_fields, fill_record
#include "sql_parse.h" // check_stack_overrun
#include "sql_partition.h" // make_used_partitions_str
#include "sql_acl.h" // *_ACL
#include "sql_test.h" // print_where, print_keyuse_array,
// print_sjm, print_plan, TEST_join
#include "records.h" // init_read_record, end_read_record
#include "filesort.h" // filesort_free_buffers
#include "sql_union.h" // mysql_union
#include "debug_sync.h" // DEBUG_SYNC
#include <m_ctype.h>
#include <my_bit.h>
#include <hash.h>
#include <ft_global.h>
#define PREV_BITS(type,A) ((type) (((type) 1 << (A)) -1))
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
"MAYBE_REF","ALL","range","index","fulltext",
"ref_or_null","unique_subquery","index_subquery",
"index_merge"
};
struct st_sargable_param;
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
static bool make_join_statistics(JOIN *join, TABLE_LIST *leaves, COND *conds,
DYNAMIC_ARRAY *keyuse);
static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,
JOIN_TAB *join_tab,
uint tables, COND *conds,
COND_EQUAL *cond_equal,
table_map table_map, SELECT_LEX *select_lex,
st_sargable_param **sargables);
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
static void set_position(JOIN *join,uint index,JOIN_TAB *table,KEYUSE *key);
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
table_map used_tables);
static bool choose_plan(JOIN *join,table_map join_tables);
static void best_access_path(JOIN *join, JOIN_TAB *s, THD *thd,
table_map remaining_tables, uint idx,
double record_count, double read_time);
static void optimize_straight_join(JOIN *join, table_map join_tables);
static bool greedy_search(JOIN *join, table_map remaining_tables,
uint depth, uint prune_level);
static bool best_extension_by_limited_search(JOIN *join,
table_map remaining_tables,
uint idx, double record_count,
double read_time, uint depth,
uint prune_level);
static uint determine_search_depth(JOIN* join);
C_MODE_START
static int join_tab_cmp(const void* ptr1, const void* ptr2);
static int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
C_MODE_END
/*
TODO: 'find_best' is here only temporarily until 'greedy_search' is
tested and approved.
*/
static bool find_best(JOIN *join,table_map rest_tables,uint index,
double record_count,double read_time);
static uint cache_record_length(JOIN *join,uint index);
static double prev_record_reads(JOIN *join, uint idx, table_map found_ref);
static bool get_best_combination(JOIN *join);
static store_key *get_store_key(THD *thd,
KEYUSE *keyuse, table_map used_tables,
KEY_PART_INFO *key_part, uchar *key_buff,
uint maybe_null);
static void make_outerjoin_info(JOIN *join);
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
static void make_join_readinfo(JOIN *join, ulonglong options);
static bool only_eq_ref_tables(JOIN *join, ORDER *order, table_map tables);
static void update_depend_map(JOIN *join);
static void update_depend_map(JOIN *join, ORDER *order);
static ORDER *remove_const(JOIN *join,ORDER *first_order,COND *cond,
bool change_list, bool *simple_order);
static int return_zero_rows(JOIN *join, select_result *res,TABLE_LIST *tables,
List<Item> &fields, bool send_row,
ulonglong select_options, const char *info,
Item *having);
static COND *build_equal_items(THD *thd, COND *cond,
COND_EQUAL *inherited,
List<TABLE_LIST> *join_list,
COND_EQUAL **cond_equal_ref);
static COND* substitute_for_best_equal_field(COND *cond,
COND_EQUAL *cond_equal,
void *table_join_idx);
static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list,
COND *conds, bool top);
static bool check_interleaving_with_nj(JOIN_TAB *next);
static void restore_prev_nj_state(JOIN_TAB *last);
static void reset_nj_counters(List<TABLE_LIST> *join_list);
static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
uint first_unused);
static COND *optimize_cond(JOIN *join, COND *conds,
List<TABLE_LIST> *join_list,
Item::cond_result *cond_value);
static bool open_tmp_table(TABLE *table);
static bool create_myisam_tmp_table(TABLE *,TMP_TABLE_PARAM *, ulonglong, my_bool);
static int do_select(JOIN *join,List<Item> *fields,TABLE *tmp_table,
Procedure *proc);
static enum_nested_loop_state
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
int error);
static enum_nested_loop_state
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
static enum_nested_loop_state
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
static enum_nested_loop_state
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_send_group(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_write_group(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static int test_if_group_changed(List<Cached_item> &list);
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
static int join_read_system(JOIN_TAB *tab);
static int join_read_const(JOIN_TAB *tab);
static int join_read_key(JOIN_TAB *tab);
static void join_read_key_unlock_row(st_join_table *tab);
static int join_read_always_key(JOIN_TAB *tab);
static int join_read_last_key(JOIN_TAB *tab);
static int join_no_more_records(READ_RECORD *info);
static int join_read_next(READ_RECORD *info);
static int join_init_quick_read_record(JOIN_TAB *tab);
static int test_if_quick_select(JOIN_TAB *tab);
static int join_init_read_record(JOIN_TAB *tab);
static int join_read_first(JOIN_TAB *tab);
static int join_read_next(READ_RECORD *info);
static int join_read_next_same(READ_RECORD *info);
static int join_read_last(JOIN_TAB *tab);
static int join_read_prev_same(READ_RECORD *info);
static int join_read_prev(READ_RECORD *info);
static int join_ft_read_first(JOIN_TAB *tab);
static int join_ft_read_next(READ_RECORD *info);
int join_read_always_key_or_null(JOIN_TAB *tab);
int join_read_next_same_or_null(READ_RECORD *info);
static COND *make_cond_for_table(COND *cond,table_map table,
table_map used_table);
static Item* part_of_refkey(TABLE *form,Field *field);
uint find_shortest_key(TABLE *table, const key_map *usable_keys);
static bool test_if_cheaper_ordering(const JOIN_TAB *tab,
ORDER *order, TABLE *table,
key_map usable_keys, int key,
ha_rows select_limit,
int *new_key, int *new_key_direction,
ha_rows *new_select_limit,
uint *new_used_key_parts= NULL,
uint *saved_best_key_parts= NULL);
static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,
ha_rows select_limit, bool no_changes,
key_map *map);
static bool list_contains_unique_index(TABLE *table,
bool (*find_func) (Field *, void *), void *data);
static bool find_field_in_item_list (Field *field, void *data);
static bool find_field_in_order_list (Field *field, void *data);
static int create_sort_index(THD *thd, JOIN *join, ORDER *order,
ha_rows filesort_limit, ha_rows select_limit,
bool is_order_by);
static int remove_duplicates(JOIN *join,TABLE *entry,List<Item> &fields,
Item *having);
static int remove_dup_with_compare(THD *thd, TABLE *entry, Field **field,
ulong offset,Item *having);
static int remove_dup_with_hash_index(THD *thd,TABLE *table,
uint field_count, Field **first_field,
ulong key_length,Item *having);
static int join_init_cache(THD *thd,JOIN_TAB *tables,uint table_count);
static ulong used_blob_length(CACHE_FIELD **ptr);
static bool store_record_in_cache(JOIN_CACHE *cache);
static void reset_cache_read(JOIN_CACHE *cache);
static void reset_cache_write(JOIN_CACHE *cache);
static void read_cached_record(JOIN_TAB *tab);
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
static bool setup_new_fields(THD *thd, List<Item> &fields,
List<Item> &all_fields, ORDER *new_order);
static ORDER *create_distinct_group(THD *thd, Item **ref_pointer_array,
ORDER *order, List<Item> &fields,
List<Item> &all_fields,
bool *all_order_by_fields_used);
static bool test_if_subpart(ORDER *a,ORDER *b);
static TABLE *get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables);
static void calc_group_buffer(JOIN *join,ORDER *group);
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
static bool alloc_group_fields(JOIN *join,ORDER *group);
// Create list for using with tempory table
static bool change_to_use_tmp_fields(THD *thd, Item **ref_pointer_array,
List<Item> &new_list1,
List<Item> &new_list2,
uint elements, List<Item> &items);
// Create list for using with tempory table
static bool change_refs_to_tmp_fields(THD *thd, Item **ref_pointer_array,
List<Item> &new_list1,
List<Item> &new_list2,
uint elements, List<Item> &items);
static void init_tmptable_sum_functions(Item_sum **func);
static void update_tmptable_sum_func(Item_sum **func,TABLE *tmp_table);
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
static bool add_ref_to_table_cond(THD *thd, JOIN_TAB *join_tab);
static bool setup_sum_funcs(THD *thd, Item_sum **func_ptr);
static bool prepare_sum_aggregators(Item_sum **func_ptr, bool need_distinct);
static bool init_sum_functions(Item_sum **func, Item_sum **end);
static bool update_sum_func(Item_sum **func);
static void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
bool distinct, const char *message=NullS);
static Item *remove_additional_cond(Item* conds);
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
static bool test_if_ref(Item_field *left_item,Item *right_item);
/**
This handles SELECT with and without UNION.
*/
bool handle_select(THD *thd, LEX *lex, select_result *result,
ulong setup_tables_done_option)
{
bool res;
register SELECT_LEX *select_lex = &lex->select_lex;
DBUG_ENTER("handle_select");
MYSQL_SELECT_START(thd->query());
if (select_lex->master_unit()->is_union() ||
select_lex->master_unit()->fake_select_lex)
res= mysql_union(thd, lex, result, &lex->unit, setup_tables_done_option);
else
{
SELECT_LEX_UNIT *unit= &lex->unit;
unit->set_limit(unit->global_parameters);
/*
'options' of mysql_select will be set in JOIN, as far as JOIN for
every PS/SP execution new, we will not need reset this flag if
setup_tables_done_option changed for next rexecution
*/
res= mysql_select(thd, &select_lex->ref_pointer_array,
select_lex->table_list.first,
select_lex->with_wild, select_lex->item_list,
select_lex->where,
select_lex->order_list.elements +
select_lex->group_list.elements,
select_lex->order_list.first,
select_lex->group_list.first,
select_lex->having,
lex->proc_list.first,
select_lex->options | thd->variables.option_bits |
setup_tables_done_option,
result, unit, select_lex);
}
DBUG_PRINT("info",("res: %d report_error: %d", res,
thd->is_error()));
res|= thd->is_error();
if (unlikely(res))
result->abort_result_set();
MYSQL_SELECT_DONE((int) res, (ulong) thd->limit_found_rows);
DBUG_RETURN(res);
}
/**
Fix fields referenced from inner selects.
@param thd Thread handle
@param all_fields List of all fields used in select
@param select Current select
@param ref_pointer_array Array of references to Items used in current select
@param group_list GROUP BY list (is NULL by default)
@details
The function serves 3 purposes
- adds fields referenced from inner query blocks to the current select list
- Decides which class to use to reference the items (Item_ref or
Item_direct_ref)
- fixes references (Item_ref objects) to these fields.
If a field isn't already on the select list and the ref_pointer_array
is provided then it is added to the all_fields list and the pointer to
it is saved in the ref_pointer_array.
The class to access the outer field is determined by the following rules:
-#. If the outer field isn't used under an aggregate function then the
Item_ref class should be used.
-#. If the outer field is used under an aggregate function and this
function is, in turn, aggregated in the query block where the outer
field was resolved or some query nested therein, then the
Item_direct_ref class should be used. Also it should be used if we are
grouping by a subquery containing the outer field.
The resolution is done here and not at the fix_fields() stage as
it can be done only after aggregate functions are fixed and pulled up to
selects where they are to be aggregated.
When the class is chosen it substitutes the original field in the
Item_outer_ref object.
After this we proceed with fixing references (Item_outer_ref objects) to
this field from inner subqueries.
@return Status
@retval true An error occured.
@retval false OK.
*/
bool
fix_inner_refs(THD *thd, List<Item> &all_fields, SELECT_LEX *select,
Item **ref_pointer_array, ORDER *group_list)
{
Item_outer_ref *ref;
List_iterator<Item_outer_ref> ref_it(select->inner_refs_list);
while ((ref= ref_it++))
{
bool direct_ref= false;
Item *item= ref->outer_ref;
Item **item_ref= ref->ref;
Item_ref *new_ref;
/*
TODO: this field item already might be present in the select list.
In this case instead of adding new field item we could use an
existing one. The change will lead to less operations for copying fields,
smaller temporary tables and less data passed through filesort.
*/
if (ref_pointer_array && !ref->found_in_select_list)
{
int el= all_fields.elements;
ref_pointer_array[el]= item;
/* Add the field item to the select list of the current select. */
all_fields.push_front(item);
/*
If it's needed reset each Item_ref item that refers this field with
a new reference taken from ref_pointer_array.
*/
item_ref= ref_pointer_array + el;
}
if (ref->in_sum_func)
{
Item_sum *sum_func;
if (ref->in_sum_func->nest_level > select->nest_level)
direct_ref= TRUE;
else
{
for (sum_func= ref->in_sum_func; sum_func &&
sum_func->aggr_level >= select->nest_level;
sum_func= sum_func->in_sum_func)
{
if (sum_func->aggr_level == select->nest_level)
{
direct_ref= TRUE;
break;
}
}
}
}
else
{
/*
Check if GROUP BY item trees contain the outer ref:
in this case we have to use Item_direct_ref instead of Item_ref.
*/
for (ORDER *group= group_list; group; group= group->next)
{
if ((*group->item)->walk(&Item::find_item_processor, TRUE,
(uchar *) ref))
{
direct_ref= TRUE;
break;
}
}
}
new_ref= direct_ref ?
new Item_direct_ref(ref->context, item_ref, ref->table_name,
ref->field_name, ref->alias_name_used) :
new Item_ref(ref->context, item_ref, ref->table_name,
ref->field_name, ref->alias_name_used);
if (!new_ref)
return TRUE;
ref->outer_ref= new_ref;
ref->ref= &ref->outer_ref;
if (!ref->fixed && ref->fix_fields(thd, 0))
return TRUE;
thd->lex->used_tables|= item->used_tables();
}
return false;
}
/**
Function to setup clauses without sum functions.
*/
inline int setup_without_group(THD *thd, Item **ref_pointer_array,
TABLE_LIST *tables,
TABLE_LIST *leaves,
List<Item> &fields,
List<Item> &all_fields,
COND **conds,
ORDER *order,
ORDER *group, bool *hidden_group_fields)
{
int res;
st_select_lex *const select= thd->lex->current_select;
nesting_map save_allow_sum_func= thd->lex->allow_sum_func;
/*
Need to save the value, so we can turn off only any new non_agg_field_used
additions coming from the WHERE
*/
const bool saved_non_agg_field_used= select->non_agg_field_used();
DBUG_ENTER("setup_without_group");
thd->lex->allow_sum_func&= ~((nesting_map)1 << select->nest_level);
res= setup_conds(thd, tables, leaves, conds);
/* it's not wrong to have non-aggregated columns in a WHERE */
select->set_non_agg_field_used(saved_non_agg_field_used);
thd->lex->allow_sum_func|= (nesting_map)1 << select->nest_level;
res= res || setup_order(thd, ref_pointer_array, tables, fields, all_fields,
order);
thd->lex->allow_sum_func&= ~((nesting_map)1 << select->nest_level);
res= res || setup_group(thd, ref_pointer_array, tables, fields, all_fields,
group, hidden_group_fields);
thd->lex->allow_sum_func= save_allow_sum_func;
DBUG_RETURN(res);
}
/*****************************************************************************
Check fields, find best join, do the select and output fields.
mysql_select assumes that all tables are already opened
*****************************************************************************/
/**
Prepare of whole select (including sub queries in future).
@todo
Add check of calculation of GROUP functions and fields:
SELECT COUNT(*)+table.col1 from table1;
@retval
-1 on error
@retval
0 on success
*/
int
JOIN::prepare(Item ***rref_pointer_array,
TABLE_LIST *tables_init,
uint wild_num, COND *conds_init, uint og_num,
ORDER *order_init, ORDER *group_init,
Item *having_init,
ORDER *proc_param_init, SELECT_LEX *select_lex_arg,
SELECT_LEX_UNIT *unit_arg)
{
DBUG_ENTER("JOIN::prepare");
// to prevent double initialization on EXPLAIN
if (optimized)
DBUG_RETURN(0);
conds= conds_init;
order= order_init;
group_list= group_init;
having= having_init;
proc_param= proc_param_init;
tables_list= tables_init;
select_lex= select_lex_arg;
select_lex->join= this;
join_list= &select_lex->top_join_list;
union_part= unit_arg->is_union();
thd->lex->current_select->is_item_list_lookup= 1;
/*
If we have already executed SELECT, then it have not sense to prevent
its table from update (see unique_table())
*/
if (thd->derived_tables_processing)
select_lex->exclude_from_table_unique_test= TRUE;
/* Check that all tables, fields, conds and order are ok */
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
setup_tables_and_check_access(thd, &select_lex->context, join_list,
tables_list, &select_lex->leaf_tables,
FALSE, SELECT_ACL, SELECT_ACL))
DBUG_RETURN(-1);
TABLE_LIST *table_ptr;
for (table_ptr= select_lex->leaf_tables;
table_ptr;
table_ptr= table_ptr->next_leaf)
tables++;
if (setup_wild(thd, tables_list, fields_list, &all_fields, wild_num) ||
select_lex->setup_ref_array(thd, og_num) ||
setup_fields(thd, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
&all_fields, 1) ||
setup_without_group(thd, (*rref_pointer_array), tables_list,
select_lex->leaf_tables, fields_list,
all_fields, &conds, order, group_list,
&hidden_group_fields))
DBUG_RETURN(-1); /* purecov: inspected */
ref_pointer_array= *rref_pointer_array;
if (having)
{
nesting_map save_allow_sum_func= thd->lex->allow_sum_func;
thd->where="having clause";
thd->lex->allow_sum_func|= (nesting_map)1 << select_lex_arg->nest_level;
select_lex->having_fix_field= 1;
bool having_fix_rc= (!having->fixed &&
(having->fix_fields(thd, &having) ||
having->check_cols(1)));
select_lex->having_fix_field= 0;
select_lex->having= having;
if (having_fix_rc || thd->is_error())
DBUG_RETURN(-1); /* purecov: inspected */
thd->lex->allow_sum_func= save_allow_sum_func;
}
if (!(thd->lex->context_analysis_only & CONTEXT_ANALYSIS_ONLY_VIEW) &&
!(select_options & SELECT_DESCRIBE))
{
Item_subselect *subselect;
/* Is it subselect? */
if ((subselect= select_lex->master_unit()->item))
{
Item_subselect::trans_res res;
if ((res= subselect->select_transformer(this)) !=
Item_subselect::RES_OK)
{
select_lex->fix_prepare_information(thd, &conds, &having);
DBUG_RETURN((res == Item_subselect::RES_ERROR));
}
}
}
select_lex->fix_prepare_information(thd, &conds, &having);
if (order)
{
bool real_order= FALSE;
ORDER *ord;
for (ord= order; ord; ord= ord->next)
{
Item *item= *ord->item;
/*
Disregard sort order if there's only
zero length NOT NULL fields (e.g. {VAR}CHAR(0) NOT NULL") or
zero length NOT NULL string functions there.
Such tuples don't contain any data to sort.
*/
if (!real_order &&
/* Not a zero length NOT NULL field */
((item->type() != Item::FIELD_ITEM ||
((Item_field *) item)->field->maybe_null() ||
((Item_field *) item)->field->sort_length()) &&
/* AND not a zero length NOT NULL string function. */
(item->type() != Item::FUNC_ITEM ||
item->maybe_null ||
item->result_type() != STRING_RESULT ||
item->max_length)))
real_order= TRUE;
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
item->split_sum_func(thd, ref_pointer_array, all_fields);
}
if (!real_order)
order= NULL;
}
if (having && having->with_sum_func)
having->split_sum_func2(thd, ref_pointer_array, all_fields,
&having, TRUE);
if (select_lex->inner_sum_func_list)
{
Item_sum *end=select_lex->inner_sum_func_list;
Item_sum *item_sum= end;
do
{
item_sum= item_sum->next;
item_sum->split_sum_func2(thd, ref_pointer_array,
all_fields, item_sum->ref_by, FALSE);
} while (item_sum != end);
}
if (select_lex->inner_refs_list.elements &&
fix_inner_refs(thd, all_fields, select_lex, ref_pointer_array,
group_list))
DBUG_RETURN(-1);
if (group_list)
{
/*
Because HEAP tables can't index BIT fields we need to use an
additional hidden field for grouping because later it will be
converted to a LONG field. Original field will remain of the
BIT type and will be returned to a client.
*/
for (ORDER *ord= group_list; ord; ord= ord->next)
{
if ((*ord->item)->type() == Item::FIELD_ITEM &&
(*ord->item)->field_type() == MYSQL_TYPE_BIT)
{
Item_field *field= new Item_field(thd, *(Item_field**)ord->item);
int el= all_fields.elements;
ref_pointer_array[el]= field;
all_fields.push_front(field);
ord->item= ref_pointer_array + el;
}
}
}
if (setup_ftfuncs(select_lex)) /* should be after having->fix_fields */
DBUG_RETURN(-1);
/*
Check if there are references to un-aggregated columns when computing
aggregate functions with implicit grouping (there is no GROUP BY).
*/
if (thd->variables.sql_mode & MODE_ONLY_FULL_GROUP_BY && !group_list &&
select_lex->non_agg_field_used() &&
select_lex->agg_func_used())
{
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
DBUG_RETURN(-1);
}
{
/* Caclulate the number of groups */
send_group_parts= 0;
for (ORDER *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
send_group_parts++;
}
procedure= setup_procedure(thd, proc_param, result, fields_list, &error);
if (error)
goto err; /* purecov: inspected */
if (procedure)
{
if (setup_new_fields(thd, fields_list, all_fields,
procedure->param_fields))
goto err; /* purecov: inspected */
if (procedure->group)
{
if (!test_if_subpart(procedure->group,group_list))
{ /* purecov: inspected */
my_message(ER_DIFF_GROUPS_PROC, ER(ER_DIFF_GROUPS_PROC),
MYF(0)); /* purecov: inspected */
goto err; /* purecov: inspected */
}
}
if (order && (procedure->flags & PROC_NO_SORT))
{ /* purecov: inspected */
my_message(ER_ORDER_WITH_PROC, ER(ER_ORDER_WITH_PROC),
MYF(0)); /* purecov: inspected */
goto err; /* purecov: inspected */
}
if (thd->lex->derived_tables)
{
my_error(ER_WRONG_USAGE, MYF(0), "PROCEDURE",
thd->lex->derived_tables & DERIVED_VIEW ?
"view" : "subquery");
goto err;
}
if (thd->lex->sql_command != SQLCOM_SELECT)
{
my_error(ER_WRONG_USAGE, MYF(0), "PROCEDURE", "non-SELECT");
goto err;
}
}
if (!procedure && result && result->prepare(fields_list, unit_arg))
goto err; /* purecov: inspected */
/* Init join struct */
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
this->group= group_list != 0;
unit= unit_arg;
if (tmp_table_param.sum_func_count && !group_list)
implicit_grouping= TRUE;
#ifdef RESTRICTED_GROUP
if (implicit_grouping)
{
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
goto err;
}
#endif
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
goto err;
if (alloc_func_list())
goto err;
DBUG_RETURN(0); // All OK
err:
delete procedure; /* purecov: inspected */
procedure= 0;
DBUG_RETURN(-1); /* purecov: inspected */
}
/*
Remove the predicates pushed down into the subquery
SYNOPSIS
JOIN::remove_subq_pushed_predicates()
where IN Must be NULL
OUT The remaining WHERE condition, or NULL
DESCRIPTION
Given that this join will be executed using (unique|index)_subquery,
without "checking NULL", remove the predicates that were pushed down
into the subquery.
If the subquery compares scalar values, we can remove the condition that
was wrapped into trig_cond (it will be checked when needed by the subquery
engine)
If the subquery compares row values, we need to keep the wrapped
equalities in the WHERE clause: when the left (outer) tuple has both NULL
and non-NULL values, we'll do a full table scan and will rely on the
equalities corresponding to non-NULL parts of left tuple to filter out
non-matching records.
TODO: We can remove the equalities that will be guaranteed to be true by the
fact that subquery engine will be using index lookup. This must be done only
for cases where there are no conversion errors of significance, e.g. 257
that is searched in a byte. But this requires homogenization of the return
codes of all Field*::store() methods.
*/
void JOIN::remove_subq_pushed_predicates(Item **where)
{
if (conds->type() == Item::FUNC_ITEM &&
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
((Item_func *)conds)->arguments()[0]))
{
*where= 0;
return;
}
}
/*
Index lookup-based subquery: save some flags for EXPLAIN output
SYNOPSIS
save_index_subquery_explain_info()
join_tab Subquery's join tab (there is only one as index lookup is
only used for subqueries that are single-table SELECTs)
where Subquery's WHERE clause
DESCRIPTION
For index lookup-based subquery (i.e. one executed with
subselect_uniquesubquery_engine or subselect_indexsubquery_engine),
check its EXPLAIN output row should contain
"Using index" (TAB_INFO_FULL_SCAN_ON_NULL)
"Using Where" (TAB_INFO_USING_WHERE)
"Full scan on NULL key" (TAB_INFO_FULL_SCAN_ON_NULL)
and set appropriate flags in join_tab->packed_info.
*/
static void save_index_subquery_explain_info(JOIN_TAB *join_tab, Item* where)
{
join_tab->packed_info= TAB_INFO_HAVE_VALUE;
if (join_tab->table->covering_keys.is_set(join_tab->ref.key))
join_tab->packed_info |= TAB_INFO_USING_INDEX;
if (where)
join_tab->packed_info |= TAB_INFO_USING_WHERE;
for (uint i = 0; i < join_tab->ref.key_parts; i++)
{
if (join_tab->ref.cond_guards[i])
{
join_tab->packed_info |= TAB_INFO_FULL_SCAN_ON_NULL;
break;
}
}
}
/**
global select optimisation.
@note
error code saved in field 'error'
@retval
0 success
@retval
1 error
*/
int
JOIN::optimize()
{
DBUG_ENTER("JOIN::optimize");
// to prevent double initialization on EXPLAIN
if (optimized)
DBUG_RETURN(0);
optimized= 1;
DEBUG_SYNC(thd, "before_join_optimize");
thd_proc_info(thd, "optimizing");
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
unit->select_limit_cnt);
/* select_limit is used to decide if we are likely to scan the whole table */
select_limit= unit->select_limit_cnt;
if (having || (select_options & OPTION_FOUND_ROWS))
select_limit= HA_POS_ERROR;
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
// Ignore errors of execution if option IGNORE present
if (thd->lex->ignore)
thd->lex->current_select->no_error= 1;
#ifdef HAVE_REF_TO_FIELDS // Not done yet
/* Add HAVING to WHERE if possible */
if (having && !group_list && !sum_func_count)
{
if (!conds)
{
conds= having;
having= 0;
}
else if ((conds=new Item_cond_and(conds,having)))
{
/*
Item_cond_and can't be fixed after creation, so we do not check
conds->fixed
*/
conds->fix_fields(thd, &conds);
conds->change_ref_to_fields(thd, tables_list);
conds->top_level_item();
having= 0;
}
}
#endif
SELECT_LEX *sel= thd->lex->current_select;
if (sel->first_cond_optimization)
{
/*
The following code will allocate the new items in a permanent
MEMROOT for prepared statements and stored procedures.
*/
Query_arena *arena= thd->stmt_arena, backup;
if (arena->is_conventional())
arena= 0; // For easier test
else
thd->set_n_backup_active_arena(arena, &backup);
sel->first_cond_optimization= 0;
/* Convert all outer joins to inner joins if possible */
conds= simplify_joins(this, join_list, conds, TRUE);
build_bitmap_for_nested_joins(join_list, 0);
sel->prep_where= conds ? conds->copy_andor_structure(thd) : 0;
if (arena)
thd->restore_active_arena(arena, &backup);
}
conds= optimize_cond(this, conds, join_list, &cond_value);
if (thd->is_error())
{
error= 1;
DBUG_PRINT("error",("Error from optimize_cond"));
DBUG_RETURN(1);
}
{
having= optimize_cond(this, having, join_list, &having_value);
if (thd->is_error())
{
error= 1;
DBUG_PRINT("error",("Error from optimize_cond"));
DBUG_RETURN(1);
}
if (select_lex->where)
select_lex->cond_value= cond_value;
if (select_lex->having)
select_lex->having_value= having_value;
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
{ /* Impossible cond */
DBUG_PRINT("info", (having_value == Item::COND_FALSE ?
"Impossible HAVING" : "Impossible WHERE"));
zero_result_cause= having_value == Item::COND_FALSE ?
"Impossible HAVING" : "Impossible WHERE";
tables= 0;
error= 0;
DBUG_RETURN(0);
}
}
#ifdef WITH_PARTITION_STORAGE_ENGINE
{
TABLE_LIST *tbl;
for (tbl= select_lex->leaf_tables; tbl; tbl= tbl->next_leaf)
{
/*
If tbl->embedding!=NULL that means that this table is in the inner
part of the nested outer join, and we can't do partition pruning
(TODO: check if this limitation can be lifted)
*/
if (!tbl->embedding)
{
Item *prune_cond= tbl->on_expr? tbl->on_expr : conds;
tbl->table->no_partitions_used= prune_partitions(thd, tbl->table,
prune_cond);
}
}
}
#endif
/*
Try to optimize count(*), min() and max() to const fields if
there is implicit grouping (aggregate functions but no
group_list). In this case, the result set shall only contain one
row.
*/
if (tables_list && implicit_grouping)
{
int res;
/*
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
to the WHERE conditions,
or 1 if all items were resolved (optimized away),
or 0, or an error number HA_ERR_...
If all items were resolved by opt_sum_query, there is no need to
open any tables.
*/
if ((res=opt_sum_query(thd, select_lex->leaf_tables, all_fields, conds)))
{
if (res == HA_ERR_KEY_NOT_FOUND)
{
DBUG_PRINT("info",("No matching min/max row"));
zero_result_cause= "No matching min/max row";
tables= 0;
error=0;
DBUG_RETURN(0);
}
if (res > 1)
{
error= res;
DBUG_PRINT("error",("Error from opt_sum_query"));
DBUG_RETURN(1);
}
if (res < 0)
{
DBUG_PRINT("info",("No matching min/max row"));
zero_result_cause= "No matching min/max row";
tables= 0;
error=0;
DBUG_RETURN(0);
}
DBUG_PRINT("info",("Select tables optimized away"));
zero_result_cause= "Select tables optimized away";
tables_list= 0; // All tables resolved
const_tables= tables;
/*
Extract all table-independent conditions and replace the WHERE
clause with them. All other conditions were computed by opt_sum_query
and the MIN/MAX/COUNT function(s) have been replaced by constants,
so there is no need to compute the whole WHERE clause again.
Notice that make_cond_for_table() will always succeed to remove all
computed conditions, because opt_sum_query() is applicable only to
conjunctions.
Preserve conditions for EXPLAIN.
*/
if (conds && !(thd->lex->describe & DESCRIBE_EXTENDED))
{
COND *table_independent_conds=
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0);
DBUG_EXECUTE("where",
print_where(table_independent_conds,
"where after opt_sum_query()",
QT_ORDINARY););
conds= table_independent_conds;
}
}
}
if (!tables_list)
{
DBUG_PRINT("info",("No tables"));
error= 0;
DBUG_RETURN(0);
}
error= -1; // Error is sent to client
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
/* Calculate how to do the join */
thd_proc_info(thd, "statistics");
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
thd->is_fatal_error)
{
DBUG_PRINT("error",("Error: make_join_statistics() failed"));
DBUG_RETURN(1);
}
if (rollup.state != ROLLUP::STATE_NONE)
{
if (rollup_process_const_fields())
{
DBUG_PRINT("error", ("Error: rollup_process_fields() failed"));
DBUG_RETURN(1);
}
}
else
{
/* Remove distinct if only const tables */
select_distinct= select_distinct && (const_tables != tables);
}
thd_proc_info(thd, "preparing");
if (result->initialize_tables(this))
{
DBUG_PRINT("error",("Error: initialize_tables() failed"));
DBUG_RETURN(1); // error == -1
}
if (const_table_map != found_const_table_map &&
!(select_options & SELECT_DESCRIBE) &&
(!conds ||
!(conds->used_tables() & RAND_TABLE_BIT) ||
select_lex->master_unit() == &thd->lex->unit)) // upper level SELECT
{
zero_result_cause= "no matching row in const table";
DBUG_PRINT("error",("Error: %s", zero_result_cause));
error= 0;
DBUG_RETURN(0);
}
if (!(thd->variables.option_bits & OPTION_BIG_SELECTS) &&
best_read > (double) thd->variables.max_join_size &&
!(select_options & SELECT_DESCRIBE))
{ /* purecov: inspected */
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
error= -1;
DBUG_RETURN(1);
}
if (const_tables && !thd->locked_tables_mode &&
!(select_options & SELECT_NO_UNLOCK))
mysql_unlock_some_tables(thd, all_tables, const_tables);
if (!conds && outer_join)
{
/* Handle the case where we have an OUTER JOIN without a WHERE */
conds=new Item_int((longlong) 1,1); // Always true
}
select= make_select(*all_tables, const_table_map,
const_table_map, conds, 1, &error);
if (error)
{ /* purecov: inspected */
error= -1; /* purecov: inspected */
DBUG_PRINT("error",("Error: make_select() failed"));
DBUG_RETURN(1);
}
reset_nj_counters(join_list);
make_outerjoin_info(this);
/*
Among the equal fields belonging to the same multiple equality
choose the one that is to be retrieved first and substitute
all references to these in where condition for a reference for
the selected field.
*/
if (conds)
{
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
conds->update_used_tables();
DBUG_EXECUTE("where",
print_where(conds,
"after substitute_best_equal",
QT_ORDINARY););
}
/*
Permorm the the optimization on fields evaluation mentioned above
for all on expressions.
*/
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
{
if (*tab->on_expr_ref)
{
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
tab->cond_equal,
map2table);
(*tab->on_expr_ref)->update_used_tables();
}
}
if (conds && const_table_map != found_const_table_map &&
(select_options & SELECT_DESCRIBE))
{
conds=new Item_int((longlong) 0,1); // Always false
}
/*
It's necessary to check const part of HAVING cond as
there is a chance that some cond parts may become
const items after make_join_statisctics(for example
when Item is a reference to cost table field from
outer join).
This check is performed only for those conditions
which do not use aggregate functions. In such case
temporary table may not be used and const condition
elements may be lost during further having
condition transformation in JOIN::exec.
*/
if (having && const_table_map && !having->with_sum_func)
{
having->update_used_tables();
having= remove_eq_conds(thd, having, &having_value);
if (having_value == Item::COND_FALSE)
{
having= new Item_int((longlong) 0,1);
zero_result_cause= "Impossible HAVING noticed after reading const tables";
error= 0;
DBUG_RETURN(0);
}
}
/* Cache constant expressions in WHERE, HAVING, ON clauses. */
cache_const_exprs();
if (make_join_select(this, select, conds))
{
zero_result_cause=
"Impossible WHERE noticed after reading const tables";
DBUG_RETURN(0); // error == 0
}
error= -1; /* if goto err */
/* Optimize distinct away if possible */
{
ORDER *org_order= order;
order=remove_const(this, order,conds,1, &simple_order);
if (thd->is_error())
{
error= 1;
DBUG_PRINT("error",("Error from remove_const"));
DBUG_RETURN(1);
}
/*
If we are using ORDER BY NULL or ORDER BY const_expression,
return result in any order (even if we are using a GROUP BY)
*/
if (!order && org_order)
skip_sort_order= 1;
}
/*
Check if we can optimize away GROUP BY/DISTINCT.
We can do that if there are no aggregate functions, the
fields in DISTINCT clause (if present) and/or columns in GROUP BY
(if present) contain direct references to all key parts of
an unique index (in whatever order) and if the key parts of the
unique index cannot contain NULLs.
Note that the unique keys for DISTINCT and GROUP BY should not
be the same (as long as they are unique).
The FROM clause must contain a single non-constant table.
*/
if (tables - const_tables == 1 && (group_list || select_distinct) &&
!tmp_table_param.sum_func_count &&
(!join_tab[const_tables].select ||
!join_tab[const_tables].select->quick ||
join_tab[const_tables].select->quick->get_type() !=
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
{
if (group_list && rollup.state == ROLLUP::STATE_NONE &&
list_contains_unique_index(join_tab[const_tables].table,
find_field_in_order_list,
(void *) group_list))
{
/*
We have found that grouping can be removed since groups correspond to
only one row anyway, but we still have to guarantee correct result
order. The line below effectively rewrites the query from GROUP BY
<fields> to ORDER BY <fields>. There are two exceptions:
- if skip_sort_order is set (see above), then we can simply skip
GROUP BY;
- we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
with the GROUP BY ones, i.e. either one is a prefix of another.
We only check if the ORDER BY is a prefix of GROUP BY. In this case
test_if_subpart() copies the ASC/DESC attributes from the original
ORDER BY fields.
If GROUP BY is a prefix of ORDER BY, then it is safe to leave
'order' as is.
*/
if (!order || test_if_subpart(group_list, order))
order= skip_sort_order ? 0 : group_list;
/*
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
rewritten to IGNORE INDEX FOR ORDER BY(fields).
*/
join_tab->table->keys_in_use_for_order_by=
join_tab->table->keys_in_use_for_group_by;
group_list= 0;
group= 0;
}
if (select_distinct &&
list_contains_unique_index(join_tab[const_tables].table,
find_field_in_item_list,
(void *) &fields_list))
{
select_distinct= 0;
}
}
if (group_list || tmp_table_param.sum_func_count)
{
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
select_distinct=0;
}
else if (select_distinct && tables - const_tables == 1 &&
rollup.state == ROLLUP::STATE_NONE)
{
/*
We are only using one table. In this case we change DISTINCT to a
GROUP BY query if:
- The GROUP BY can be done through indexes (no sort) and the ORDER
BY only uses selected fields.
(In this case we can later optimize away GROUP BY and ORDER BY)
- We are scanning the whole table without LIMIT
This can happen if:
- We are using CALC_FOUND_ROWS
- We are using an ORDER BY that can't be optimized away.
We don't want to use this optimization when we are using LIMIT
because in this case we can just create a temporary table that
holds LIMIT rows and stop when this table is full.
*/
JOIN_TAB *tab= &join_tab[const_tables];
bool all_order_fields_used;
if (order)
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
&tab->table->keys_in_use_for_order_by);
if ((group_list=create_distinct_group(thd, select_lex->ref_pointer_array,
order, fields_list, all_fields,
&all_order_fields_used)))
{
bool skip_group= (skip_sort_order &&
test_if_skip_sort_order(tab, group_list, select_limit, 1,
&tab->table->keys_in_use_for_group_by) != 0);
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
if ((skip_group && all_order_fields_used) ||
select_limit == HA_POS_ERROR ||
(order && !skip_sort_order))
{
/* Change DISTINCT to GROUP BY */
select_distinct= 0;
no_order= !order;
if (all_order_fields_used)
{
if (order && skip_sort_order)
{
/*
Force MySQL to read the table in sorted order to get result in
ORDER BY order.
*/
tmp_table_param.quick_group=0;
}
order=0;
}
group=1; // For end_write_group
}
else
group_list= 0;
}
else if (thd->is_fatal_error) // End of memory
DBUG_RETURN(1);
}
simple_group= 0;
{
ORDER *old_group_list;
group_list= remove_const(this, (old_group_list= group_list), conds,
rollup.state == ROLLUP::STATE_NONE,
&simple_group);
if (thd->is_error())
{
error= 1;
DBUG_PRINT("error",("Error from remove_const"));
DBUG_RETURN(1);
}
if (old_group_list && !group_list)
select_distinct= 0;
}
if (!group_list && group)
{
order=0; // The output has only one row
simple_order=1;
select_distinct= 0; // No need in distinct for 1 row
group_optimized_away= 1;
}
calc_group_buffer(this, group_list);
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
if (procedure && procedure->group)
{
group_list= procedure->group= remove_const(this, procedure->group, conds,
1, &simple_group);
if (thd->is_error())
{
error= 1;
DBUG_PRINT("error",("Error from remove_const"));
DBUG_RETURN(1);
}
calc_group_buffer(this, group_list);
}
if (test_if_subpart(group_list, order) ||
(!group_list && tmp_table_param.sum_func_count))
{
order=0;
if (is_indexed_agg_distinct(this, NULL))
sort_and_group= 0;
}
// Can't use sort on head table if using join buffering
if (full_join)
{
TABLE *stable= (sort_by_table == (TABLE *) 1 ?
join_tab[const_tables].table : sort_by_table);
/*
FORCE INDEX FOR ORDER BY can be used to prevent join buffering when
sorting on the first table.
*/
if (!stable || !stable->force_index_order)
{
if (group_list)
simple_group= 0;
if (order)
simple_order= 0;
}
}
/*
Check if we need to create a temporary table.
This has to be done if all tables are not already read (const tables)
and one of the following conditions holds:
- We are using DISTINCT (simple distinct's are already optimized away)
- We are using an ORDER BY or GROUP BY on fields not in the first table
- We are using different ORDER BY and GROUP BY orders
- The user wants us to buffer the result.
When the WITH ROLLUP modifier is present, we cannot skip temporary table
creation for the DISTINCT clause just because there are only const tables.
*/
need_tmp= ((const_tables != tables &&
((select_distinct || !simple_order || !simple_group) ||
(group_list && order) ||
test(select_options & OPTION_BUFFER_RESULT))) ||
(rollup.state != ROLLUP::STATE_NONE && select_distinct));
// No cache for MATCH
make_join_readinfo(this,
(select_options & (SELECT_DESCRIBE |
SELECT_NO_JOIN_CACHE)) |
(select_lex->ftfunc_list->elements ?
SELECT_NO_JOIN_CACHE : 0));
/* Perform FULLTEXT search before all regular searches */
if (!(select_options & SELECT_DESCRIBE))
init_ftfuncs(thd, select_lex, test(order));
/*
is this simple IN subquery?
*/
if (!group_list && !order &&
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
tables == 1 && conds &&
!unit->is_union())
{
if (!having)
{
Item *where= conds;
if (join_tab[0].type == JT_EQ_REF &&
join_tab[0].ref.items[0]->name == in_left_expr_name)
{
remove_subq_pushed_predicates(&where);
save_index_subquery_explain_info(join_tab, where);
join_tab[0].type= JT_UNIQUE_SUBQUERY;
error= 0;
DBUG_RETURN(unit->item->
change_engine(new
subselect_uniquesubquery_engine(thd,
join_tab,
unit->item,
where)));
}
else if (join_tab[0].type == JT_REF &&
join_tab[0].ref.items[0]->name == in_left_expr_name)
{
remove_subq_pushed_predicates(&where);
save_index_subquery_explain_info(join_tab, where);
join_tab[0].type= JT_INDEX_SUBQUERY;
error= 0;
DBUG_RETURN(unit->item->
change_engine(new
subselect_indexsubquery_engine(thd,
join_tab,
unit->item,
where,
NULL,
0)));
}
} else if (join_tab[0].type == JT_REF_OR_NULL &&
join_tab[0].ref.items[0]->name == in_left_expr_name &&
having->name == in_having_cond)
{
join_tab[0].type= JT_INDEX_SUBQUERY;
error= 0;
conds= remove_additional_cond(conds);
save_index_subquery_explain_info(join_tab, conds);
DBUG_RETURN(unit->item->
change_engine(new subselect_indexsubquery_engine(thd,
join_tab,
unit->item,
conds,
having,
1)));
}
}
/*
Need to tell handlers that to play it safe, it should fetch all
columns of the primary key of the tables: this is because MySQL may
build row pointers for the rows, and for all columns of the primary key
the read set has not necessarily been set by the server code.
*/
if (need_tmp || select_distinct || group_list || order)
{
for (uint i = const_tables; i < tables; i++)
join_tab[i].table->prepare_for_position();
}
DBUG_EXECUTE("info",TEST_join(this););
if (const_tables != tables)
{
/*
Because filesort always does a full table scan or a quick range scan
we must add the removed reference to the select for the table.
We only need to do this when we have a simple_order or simple_group
as in other cases the join is done before the sort.
*/
if ((order || group_list) &&
join_tab[const_tables].type != JT_ALL &&
join_tab[const_tables].type != JT_FT &&
join_tab[const_tables].type != JT_REF_OR_NULL &&
((order && simple_order) || (group_list && simple_group)))
{
if (add_ref_to_table_cond(thd,&join_tab[const_tables])) {
DBUG_RETURN(1);
}
}
/*
Calculate a possible 'limit' of table rows for 'GROUP BY': 'need_tmp'
implies that there will be more postprocessing so the specified
'limit' should not be enforced yet in the call to
'test_if_skip_sort_order'.
*/
const ha_rows limit = need_tmp ? HA_POS_ERROR : unit->select_limit_cnt;
if (!(select_options & SELECT_BIG_RESULT) &&
((group_list &&
(!simple_group ||
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
limit, 0,
&join_tab[const_tables].table->
keys_in_use_for_group_by))) ||
select_distinct) &&
tmp_table_param.quick_group && !procedure)
{
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
}
if (order)
{
/*
Do we need a temporary table due to the ORDER BY not being equal to
the GROUP BY? The call to test_if_skip_sort_order above tests for the
GROUP BY clause only and hence is not valid in this case. So the
estimated number of rows to be read from the first table is not valid.
We clear it here so that it doesn't show up in EXPLAIN.
*/
if (need_tmp && (select_options & SELECT_DESCRIBE) != 0)
join_tab[const_tables].limit= 0;
/*
Force using of tmp table if sorting by a SP or UDF function due to
their expensive and probably non-deterministic nature.
*/
for (ORDER *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
{
Item *item= *tmp_order->item;
if (item->walk(&Item::is_expensive_processor, 0, (uchar*)0))
{
/* Force tmp table without sort */
need_tmp=1; simple_order=simple_group=0;
break;
}
}
}
}
tmp_having= having;
if (select_options & SELECT_DESCRIBE)
{
error= 0;
DBUG_RETURN(0);
}
having= 0;
/*
The loose index scan access method guarantees that all grouping or
duplicate row elimination (for distinct) is already performed
during data retrieval, and that all MIN/MAX functions are already
computed for each group. Thus all MIN/MAX functions should be
treated as regular functions, and there is no need to perform
grouping in the main execution loop.
Notice that currently loose index scan is applicable only for
single table queries, thus it is sufficient to test only the first
join_tab element of the plan for its access method.
*/
bool need_distinct= TRUE;
if (join_tab->is_using_loose_index_scan())
{
tmp_table_param.precomputed_group_by= TRUE;
if (join_tab->is_using_agg_loose_index_scan())
{
need_distinct= FALSE;
tmp_table_param.precomputed_group_by= FALSE;
}
}
/* Create a tmp table if distinct or if the sort is too complicated */
if (need_tmp)
{
DBUG_PRINT("info",("Creating tmp table"));
thd_proc_info(thd, "Creating tmp table");
init_items_ref_array();
tmp_table_param.hidden_field_count= (all_fields.elements -
fields_list.elements);
ORDER *tmp_group= ((!simple_group && !procedure &&
!(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
(ORDER*) 0);
/*
Pushing LIMIT to the temporary table creation is not applicable
when there is ORDER BY or GROUP BY or there is no GROUP BY, but
there are aggregate functions, because in all these cases we need
all result rows.
*/
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
!tmp_group &&
!thd->lex->current_select->with_sum_func) ?
select_limit : HA_POS_ERROR;
if (!(exec_tmp_table1=
create_tmp_table(thd, &tmp_table_param, all_fields,
tmp_group, group_list ? 0 : select_distinct,
group_list && simple_group,
select_options, tmp_rows_limit, "")))
DBUG_RETURN(1);
/*
We don't have to store rows in temp table that doesn't match HAVING if:
- we are sorting the table and writing complete group rows to the
temp table.
- We are using DISTINCT without resolving the distinct as a GROUP BY
on all columns.
If having is not handled here, it will be checked before the row
is sent to the client.
*/
if (tmp_having &&
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
having= tmp_having;
/* if group or order on first table, sort first */
if (group_list && simple_group)
{
DBUG_PRINT("info",("Sorting for group"));
thd_proc_info(thd, "Sorting for group");
if (create_sort_index(thd, this, group_list,
HA_POS_ERROR, HA_POS_ERROR, FALSE) ||
alloc_group_fields(this, group_list) ||
make_sum_func_list(all_fields, fields_list, 1) ||
prepare_sum_aggregators(sum_funcs, need_distinct) ||
setup_sum_funcs(thd, sum_funcs))
{
DBUG_RETURN(1);
}
group_list=0;
}
else
{
if (make_sum_func_list(all_fields, fields_list, 0) ||
prepare_sum_aggregators(sum_funcs, need_distinct) ||
setup_sum_funcs(thd, sum_funcs))
{
DBUG_RETURN(1);
}
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
{
thd_proc_info(thd, "Sorting for order");
if (create_sort_index(thd, this, order,
HA_POS_ERROR, HA_POS_ERROR, TRUE))
{
DBUG_RETURN(1);
}
order=0;
}
}
/*
Optimize distinct when used on some of the tables
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
In this case we can stop scanning t2 when we have found one t1.a
*/
if (exec_tmp_table1->distinct)
{
table_map used_tables= thd->lex->used_tables;
JOIN_TAB *last_join_tab= join_tab+tables-1;
do
{
if (used_tables & last_join_tab->table->map)
break;
last_join_tab->not_used_in_distinct=1;
} while (last_join_tab-- != join_tab);
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
if (order && skip_sort_order)
{
/* Should always succeed */
if (test_if_skip_sort_order(&join_tab[const_tables],
order, unit->select_limit_cnt, 0,
&join_tab[const_tables].table->
keys_in_use_for_order_by))
order=0;
}
}
/* If this join belongs to an uncacheable query save the original join */
if (select_lex->uncacheable && init_save_join_tab())
DBUG_RETURN(-1); /* purecov: inspected */
}
error= 0;
DBUG_RETURN(0);
}
/**
Restore values in temporary join.
*/
void JOIN::restore_tmp()
{
DBUG_PRINT("info", ("restore_tmp this %p tmp_join %p", this, tmp_join));
DBUG_ASSERT(tmp_join != this);
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
}
int
JOIN::reinit()
{
DBUG_ENTER("JOIN::reinit");
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
select_lex->offset_limit->val_uint() :
ULL(0));
first_record= 0;
if (exec_tmp_table1)
{
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
exec_tmp_table1->file->ha_delete_all_rows();
free_io_cache(exec_tmp_table1);
filesort_free_buffers(exec_tmp_table1,0);
}
if (exec_tmp_table2)
{
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
exec_tmp_table2->file->ha_delete_all_rows();
free_io_cache(exec_tmp_table2);
filesort_free_buffers(exec_tmp_table2,0);
}
if (items0)
set_items_ref_array(items0);
if (join_tab_save)
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
/* need to reset ref access state (see join_read_key) */
if (join_tab)
for (uint i= 0; i < tables; i++)
join_tab[i].ref.key_err= TRUE;
if (tmp_join)
restore_tmp();
/* Reset of sum functions */
if (sum_funcs)
{
Item_sum *func, **func_ptr= sum_funcs;
while ((func= *(func_ptr++)))
func->clear();
}
if (!(select_options & SELECT_DESCRIBE))
init_ftfuncs(thd, select_lex, test(order));
DBUG_RETURN(0);
}
/**
@brief Save the original join layout
@details Saves the original join layout so it can be reused in
re-execution and for EXPLAIN.
@return Operation status
@retval 0 success.
@retval 1 error occurred.
*/
bool
JOIN::init_save_join_tab()
{
if (!(tmp_join= (JOIN*)thd->alloc(sizeof(JOIN))))
return 1; /* purecov: inspected */
error= 0; // Ensure that tmp_join.error= 0
restore_tmp();
return 0;
}
bool
JOIN::save_join_tab()
{
if (!join_tab_save && select_lex->master_unit()->uncacheable)
{
if (!(join_tab_save= (JOIN_TAB*)thd->memdup((uchar*) join_tab,
sizeof(JOIN_TAB) * tables)))
return 1;
}
return 0;
}
/**
Exec select.
@todo
Note, that create_sort_index calls test_if_skip_sort_order and may
finally replace sorting with index scan if there is a LIMIT clause in
the query. It's never shown in EXPLAIN!
@todo
When can we have here thd->net.report_error not zero?
*/
void
JOIN::exec()
{
List<Item> *columns_list= &fields_list;
int tmp_error;
bool sort_index_created= false;
DBUG_ENTER("JOIN::exec");
thd_proc_info(thd, "executing");
error= 0;
if (procedure)
{
procedure_fields_list= fields_list;
if (procedure->change_columns(procedure_fields_list) ||
result->prepare(procedure_fields_list, unit))
{
thd->limit_found_rows= thd->examined_row_count= 0;
DBUG_VOID_RETURN;
}
columns_list= &procedure_fields_list;
}
(void) result->prepare2(); // Currently, this cannot fail.
if (!tables_list && (tables || !select_lex->with_sum_func))
{ // Only test of functions
if (select_options & SELECT_DESCRIBE)
select_describe(this, FALSE, FALSE, FALSE,
(zero_result_cause?zero_result_cause:"No tables used"));
else
{
if (result->send_result_set_metadata(*columns_list,
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF))
{
DBUG_VOID_RETURN;
}
/*
We have to test for 'conds' here as the WHERE may not be constant
even if we don't have any tables for prepared statements or if
conds uses something like 'rand()'.
If the HAVING clause is either impossible or always true, then
JOIN::having is set to NULL by optimize_cond.
In this case JOIN::exec must check for JOIN::having_value, in the
same way it checks for JOIN::cond_value.
*/
if (cond_value != Item::COND_FALSE &&
having_value != Item::COND_FALSE &&
(!conds || conds->val_int()) &&
(!having || having->val_int()))
{
if (do_send_rows &&
(procedure ? (procedure->send_row(procedure_fields_list) ||
procedure->end_of_records()) : result->send_data(fields_list)))
error= 1;
else
{
error= (int) result->send_eof();
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 :
thd->sent_row_count);
}
}
else
{
error=(int) result->send_eof();
send_records= 0;
}
}
/* Single select (without union) always returns 0 or 1 row */
thd->limit_found_rows= send_records;
thd->examined_row_count= 0;
DBUG_VOID_RETURN;
}
/*
Don't reset the found rows count if there're no tables as
FOUND_ROWS() may be called. Never reset the examined row count here.
It must be accumulated from all join iterations of all join parts.
*/
if (tables)
thd->limit_found_rows= 0;
if (zero_result_cause)
{
(void) return_zero_rows(this, result, select_lex->leaf_tables,
*columns_list,
send_row_on_empty_set(),
select_options,
zero_result_cause,
having);
DBUG_VOID_RETURN;
}
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) &&
get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
DBUG_VOID_RETURN;
if (select_options & SELECT_DESCRIBE)
{
/*
Check if we managed to optimize ORDER BY away and don't use temporary
table to resolve ORDER BY: in that case, we only may need to do
filesort for GROUP BY.
*/
if (!order && !no_order && (!skip_sort_order || !need_tmp))
{
/*
Reset 'order' to 'group_list' and reinit variables describing
'order'
*/
order= group_list;
simple_order= simple_group;
skip_sort_order= 0;
}
if (order &&
(order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
(const_tables == tables ||
((simple_order || skip_sort_order) &&
test_if_skip_sort_order(&join_tab[const_tables], order,
select_limit, 0,
&join_tab[const_tables].table->
keys_in_use_for_query))))
order=0;
having= tmp_having;
select_describe(this, need_tmp,
order != 0 && !skip_sort_order,
select_distinct,
!tables ? "No tables used" : NullS);
DBUG_VOID_RETURN;
}
JOIN *curr_join= this;
List<Item> *curr_all_fields= &all_fields;
List<Item> *curr_fields_list= &fields_list;
TABLE *curr_tmp_table= 0;
/*
Initialize examined rows here because the values from all join parts
must be accumulated in examined_row_count. Hence every join
iteration must count from zero.
*/
curr_join->examined_rows= 0;
/* Create a tmp table if distinct or if the sort is too complicated */
if (need_tmp)
{
if (tmp_join)
{
/*
We are in a non cacheable sub query. Get the saved join structure
after optimization.
(curr_join may have been modified during last exection and we need
to reset it)
*/
curr_join= tmp_join;
}
curr_tmp_table= exec_tmp_table1;
/* Copy data to the temporary table */
thd_proc_info(thd, "Copying to tmp table");
DBUG_PRINT("info", ("%s", thd->proc_info));
if (!curr_join->sort_and_group &&
curr_join->const_tables != curr_join->tables)
curr_join->join_tab[curr_join->const_tables].sorted= 0;
Procedure *save_proc= curr_join->procedure;
tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table, 0);
curr_join->procedure= save_proc;
if (tmp_error)
{
error= tmp_error;
DBUG_VOID_RETURN;
}
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
if (curr_join->having)
curr_join->having= curr_join->tmp_having= 0; // Allready done
/* Change sum_fields reference to calculated fields in tmp_table */
if (curr_join != this)
curr_join->all_fields= *curr_all_fields;
if (!items1)
{
items1= items0 + all_fields.elements;
if (sort_and_group || curr_tmp_table->group ||
tmp_table_param.precomputed_group_by)
{
if (change_to_use_tmp_fields(thd, items1,
tmp_fields_list1, tmp_all_fields1,
fields_list.elements, all_fields))
DBUG_VOID_RETURN;
}
else
{
if (change_refs_to_tmp_fields(thd, items1,
tmp_fields_list1, tmp_all_fields1,
fields_list.elements, all_fields))
DBUG_VOID_RETURN;
}
if (curr_join != this)
{
curr_join->tmp_all_fields1= tmp_all_fields1;
curr_join->tmp_fields_list1= tmp_fields_list1;
}
curr_join->items1= items1;
}
curr_all_fields= &tmp_all_fields1;
curr_fields_list= &tmp_fields_list1;
curr_join->set_items_ref_array(items1);
if (sort_and_group || curr_tmp_table->group)
{
curr_join->tmp_table_param.field_count+=
curr_join->tmp_table_param.sum_func_count+
curr_join->tmp_table_param.func_count;
curr_join->tmp_table_param.sum_func_count=
curr_join->tmp_table_param.func_count= 0;
}
else
{
curr_join->tmp_table_param.field_count+=
curr_join->tmp_table_param.func_count;
curr_join->tmp_table_param.func_count= 0;
}
// procedure can't be used inside subselect => we do nothing special for it
if (procedure)
procedure->update_refs();
if (curr_tmp_table->group)
{ // Already grouped
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
curr_join->order= curr_join->group_list; /* order by group */
curr_join->group_list= 0;
}
/*
If we have different sort & group then we must sort the data by group
and copy it to another tmp table
This code is also used if we are using distinct something
we haven't been able to store in the temporary table yet
like SEC_TO_TIME(SUM(...)).
*/
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list,
curr_join->order) ||
curr_join->select_distinct)) ||
(curr_join->select_distinct &&
curr_join->tmp_table_param.using_indirect_summary_function))
{ /* Must copy to another table */
DBUG_PRINT("info",("Creating group table"));
/* Free first data from old join */
curr_join->join_free();
if (curr_join->make_simple_join(this, curr_tmp_table))
DBUG_VOID_RETURN;
calc_group_buffer(curr_join, group_list);
count_field_types(select_lex, &curr_join->tmp_table_param,
curr_join->tmp_all_fields1,
curr_join->select_distinct && !curr_join->group_list);
curr_join->tmp_table_param.hidden_field_count=
(curr_join->tmp_all_fields1.elements-
curr_join->tmp_fields_list1.elements);
if (exec_tmp_table2)
curr_tmp_table= exec_tmp_table2;
else
{
/* group data to new table */
/*
If the access method is loose index scan then all MIN/MAX
functions are precomputed, and should be treated as regular
functions. See extended comment in JOIN::exec.
*/
if (curr_join->join_tab->is_using_loose_index_scan())
curr_join->tmp_table_param.precomputed_group_by= TRUE;
if (!(curr_tmp_table=
exec_tmp_table2= create_tmp_table(thd,
&curr_join->tmp_table_param,
*curr_all_fields,
(ORDER*) 0,
curr_join->select_distinct &&
!curr_join->group_list,
1, curr_join->select_options,
HA_POS_ERROR, "")))
DBUG_VOID_RETURN;
curr_join->exec_tmp_table2= exec_tmp_table2;
}
if (curr_join->group_list)
{
thd_proc_info(thd, "Creating sort index");
if (curr_join->join_tab == join_tab && save_join_tab())
{
DBUG_VOID_RETURN;
}
if (create_sort_index(thd, curr_join, curr_join->group_list,
HA_POS_ERROR, HA_POS_ERROR, FALSE) ||
make_group_fields(this, curr_join))
{
DBUG_VOID_RETURN;
}
sort_index_created= true;
sortorder= curr_join->sortorder;
}
thd_proc_info(thd, "Copying to group table");
DBUG_PRINT("info", ("%s", thd->proc_info));
tmp_error= -1;
if (curr_join != this)
{
if (sum_funcs2)
{
curr_join->sum_funcs= sum_funcs2;
curr_join->sum_funcs_end= sum_funcs_end2;
}
else
{
curr_join->alloc_func_list();
sum_funcs2= curr_join->sum_funcs;
sum_funcs_end2= curr_join->sum_funcs_end;
}
}
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1, TRUE) ||
prepare_sum_aggregators(curr_join->sum_funcs,
!curr_join->join_tab->is_using_agg_loose_index_scan()))
DBUG_VOID_RETURN;
curr_join->group_list= 0;
if (!curr_join->sort_and_group &&
curr_join->const_tables != curr_join->tables)
curr_join->join_tab[curr_join->const_tables].sorted= 0;
if (setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
(tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table,
0)))
{
error= tmp_error;
DBUG_VOID_RETURN;
}
end_read_record(&curr_join->join_tab->read_record);
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
curr_join->join_tab[0].table= 0; // Table is freed
// No sum funcs anymore
if (!items2)
{
items2= items1 + all_fields.elements;
if (change_to_use_tmp_fields(thd, items2,
tmp_fields_list2, tmp_all_fields2,
fields_list.elements, tmp_all_fields1))
DBUG_VOID_RETURN;
if (curr_join != this)
{
curr_join->tmp_fields_list2= tmp_fields_list2;
curr_join->tmp_all_fields2= tmp_all_fields2;
}
}
curr_fields_list= &curr_join->tmp_fields_list2;
curr_all_fields= &curr_join->tmp_all_fields2;
curr_join->set_items_ref_array(items2);
curr_join->tmp_table_param.field_count+=
curr_join->tmp_table_param.sum_func_count;
curr_join->tmp_table_param.sum_func_count= 0;
}
if (curr_tmp_table->distinct)
curr_join->select_distinct=0; /* Each row is unique */
curr_join->join_free(); /* Free quick selects */
if (curr_join->select_distinct && ! curr_join->group_list)
{
thd_proc_info(thd, "Removing duplicates");
if (curr_join->tmp_having)
curr_join->tmp_having->update_used_tables();
if (remove_duplicates(curr_join, curr_tmp_table,
*curr_fields_list, curr_join->tmp_having))
DBUG_VOID_RETURN;
curr_join->tmp_having=0;
curr_join->select_distinct=0;
}
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
if (curr_join->make_simple_join(this, curr_tmp_table))
DBUG_VOID_RETURN;
calc_group_buffer(curr_join, curr_join->group_list);
count_field_types(select_lex, &curr_join->tmp_table_param,
*curr_all_fields, 0);
}
if (procedure)
count_field_types(select_lex, &curr_join->tmp_table_param,
*curr_all_fields, 0);
if (curr_join->group || curr_join->implicit_grouping ||
curr_join->tmp_table_param.sum_func_count ||
(procedure && (procedure->flags & PROC_GROUP)))
{
if (make_group_fields(this, curr_join))
{
DBUG_VOID_RETURN;
}
if (!items3)
{
if (!items0)
init_items_ref_array();
items3= ref_pointer_array + (all_fields.elements*4);
setup_copy_fields(thd, &curr_join->tmp_table_param,
items3, tmp_fields_list3, tmp_all_fields3,
curr_fields_list->elements, *curr_all_fields);
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
tmp_table_param.save_copy_field_end=
curr_join->tmp_table_param.copy_field_end;
if (curr_join != this)
{
curr_join->tmp_all_fields3= tmp_all_fields3;
curr_join->tmp_fields_list3= tmp_fields_list3;
}
}
else
{
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
curr_join->tmp_table_param.copy_field_end=
tmp_table_param.save_copy_field_end;
}
curr_fields_list= &tmp_fields_list3;
curr_all_fields= &tmp_all_fields3;
curr_join->set_items_ref_array(items3);
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1, TRUE) ||
prepare_sum_aggregators(curr_join->sum_funcs,
!curr_join->join_tab ||
!curr_join->join_tab->
is_using_agg_loose_index_scan()) ||
setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
thd->is_fatal_error)
DBUG_VOID_RETURN;
}
if (curr_join->group_list || curr_join->order)
{
DBUG_PRINT("info",("Sorting for send_result_set_metadata"));
thd_proc_info(thd, "Sorting result");
/* If we have already done the group, add HAVING to sorted table */
if (curr_join->tmp_having && ! curr_join->group_list &&
! curr_join->sort_and_group)
{
// Some tables may have been const
curr_join->tmp_having->update_used_tables();
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
table_map used_tables= (curr_join->const_table_map |
curr_table->table->map);
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
used_tables,
(table_map) 0);
if (sort_table_cond)
{
if (!curr_table->select)
if (!(curr_table->select= new SQL_SELECT))
DBUG_VOID_RETURN;
if (!curr_table->select->cond)
curr_table->select->cond= sort_table_cond;
else
{
if (!(curr_table->select->cond=
new Item_cond_and(curr_table->select->cond,
sort_table_cond)))
DBUG_VOID_RETURN;
curr_table->select->cond->fix_fields(thd, 0);
}
curr_table->select_cond= curr_table->select->cond;
curr_table->select_cond->top_level_item();
DBUG_EXECUTE("where",print_where(curr_table->select->cond,
"select and having",
QT_ORDINARY););
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
~ (table_map) 0,
~used_tables);
DBUG_EXECUTE("where",print_where(curr_join->tmp_having,
"having after sort",
QT_ORDINARY););
}
}
{
if (group)
curr_join->select_limit= HA_POS_ERROR;
else
{
/*
We can abort sorting after thd->select_limit rows if we there is no
WHERE clause for any tables after the sorted one.
*/
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
for (; curr_table < end_table ; curr_table++)
{
/*
table->keyuse is set in the case there was an original WHERE clause
on the table that was optimized away.
*/
if (curr_table->select_cond ||
(curr_table->keyuse && !curr_table->first_inner))
{
/* We have to sort all rows */
curr_join->select_limit= HA_POS_ERROR;
break;
}
}
}
if (curr_join->join_tab == join_tab && save_join_tab())
{
DBUG_VOID_RETURN;
}
/*
Here we sort rows for ORDER BY/GROUP BY clause, if the optimiser
chose FILESORT to be faster than INDEX SCAN or there is no
suitable index present.
Note, that create_sort_index calls test_if_skip_sort_order and may
finally replace sorting with index scan if there is a LIMIT clause in
the query. XXX: it's never shown in EXPLAIN!
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
*/
if (create_sort_index(thd, curr_join,
curr_join->group_list ?
curr_join->group_list : curr_join->order,
curr_join->select_limit,
(select_options & OPTION_FOUND_ROWS ?
HA_POS_ERROR : unit->select_limit_cnt),
curr_join->group_list ? TRUE : FALSE))
DBUG_VOID_RETURN;
sort_index_created= true;
sortorder= curr_join->sortorder;
if (curr_join->const_tables != curr_join->tables &&
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
{
/*
If no IO cache exists for the first table then we are using an
INDEX SCAN and no filesort. Thus we should not remove the sorted
attribute on the INDEX SCAN.
*/
skip_sort_order= 1;
}
}
}
/* XXX: When can we have here thd->is_error() not zero? */
if (thd->is_error())
{
error= thd->is_error();
DBUG_VOID_RETURN;
}
curr_join->having= curr_join->tmp_having;
curr_join->fields= curr_fields_list;
curr_join->procedure= procedure;
thd_proc_info(thd, "Sending data");
DBUG_PRINT("info", ("%s", thd->proc_info));
result->send_result_set_metadata((procedure ? curr_join->procedure_fields_list :
*curr_fields_list),
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
error= do_select(curr_join, curr_fields_list, NULL, procedure);
thd->limit_found_rows= curr_join->send_records;
if (sort_index_created && curr_join->tables != curr_join->const_tables )
{
// Restore the original "select" used by create_sort_index():
JOIN_TAB *const tab= curr_join->join_tab + curr_join->const_tables;
if (tab->saved_select)
{
tab->select= tab->saved_select;
tab->saved_select= NULL;
}
}
/* Accumulate the counts from all join iterations of all join parts. */
thd->examined_row_count+= curr_join->examined_rows;
DBUG_PRINT("counts", ("thd->examined_row_count: %lu",
(ulong) thd->examined_row_count));
/*
With EXPLAIN EXTENDED we have to restore original ref_array
for a derived table which is always materialized.
We also need to do this when we have temp table(s).
Otherwise we would not be able to print the query correctly.
*/
if (items0 && (thd->lex->describe & DESCRIBE_EXTENDED) &&
(select_lex->linkage == DERIVED_TABLE_TYPE ||
exec_tmp_table1 || exec_tmp_table2))
set_items_ref_array(items0);
DBUG_VOID_RETURN;
}
/**
Clean up join.
@return
Return error that hold JOIN.
*/
int
JOIN::destroy()
{
DBUG_ENTER("JOIN::destroy");
select_lex->join= 0;
if (tmp_join)
{
if (join_tab != tmp_join->join_tab)
{
JOIN_TAB *tab, *end;
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
tab->cleanup();
}
tmp_join->tmp_join= 0;
/*
We need to clean up tmp_table_param for reusable JOINs (having non-zero
and different from self tmp_join) because it's not being cleaned up
anywhere else (as we need to keep the join is reusable).
*/
tmp_table_param.cleanup();
tmp_table_param.copy_field= tmp_join->tmp_table_param.copy_field= 0;
DBUG_RETURN(tmp_join->destroy());
}
cond_equal= 0;
cleanup(1);
/* Cleanup items referencing temporary table columns */
cleanup_item_list(tmp_all_fields1);
cleanup_item_list(tmp_all_fields3);
if (exec_tmp_table1)
free_tmp_table(thd, exec_tmp_table1);
if (exec_tmp_table2)
free_tmp_table(thd, exec_tmp_table2);
delete select;
delete_dynamic(&keyuse);
delete procedure;
DBUG_RETURN(error);
}
void JOIN::cleanup_item_list(List<Item> &items) const
{
if (!items.is_empty())
{
List_iterator_fast<Item> it(items);
Item *item;
while ((item= it++))
item->cleanup();
}
}
/**
An entry point to single-unit select (a select without UNION).
@param thd thread handler
@param rref_pointer_array a reference to ref_pointer_array of
the top-level select_lex for this query
@param tables list of all tables used in this query.
The tables have been pre-opened.
@param 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.
@param 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.
@param conds top level item of an expression representing
WHERE clause of the top level select
@param og_num total number of ORDER BY and GROUP BY clauses
arguments
@param order linked list of ORDER BY agruments
@param group linked list of GROUP BY arguments
@param having top level item of HAVING expression
@param proc_param list of PROCEDUREs
@param select_options select options (BIG_RESULT, etc)
@param 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.
@param select_lex the only SELECT_LEX of this query
@param 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.
@retval
FALSE success
@retval
TRUE an error
*/
bool
mysql_select(THD *thd, Item ***rref_pointer_array,
TABLE_LIST *tables, uint wild_num, List<Item> &fields,
COND *conds, uint og_num, ORDER *order, ORDER *group,
Item *having, ORDER *proc_param, ulonglong select_options,
select_result *result, SELECT_LEX_UNIT *unit,
SELECT_LEX *select_lex)
{
bool err;
bool free_join= 1;
DBUG_ENTER("mysql_select");
select_lex->context.resolve_in_select_list= TRUE;
JOIN *join;
if (select_lex->join != 0)
{
join= select_lex->join;
/*
is it single SELECT in derived table, called in derived table
creation
*/
if (select_lex->linkage != DERIVED_TABLE_TYPE ||
(select_options & SELECT_DESCRIBE))
{
if (select_lex->linkage != GLOBAL_OPTIONS_TYPE)
{
//here is EXPLAIN of subselect or derived table
if (join->change_result(result))
{
DBUG_RETURN(TRUE);
}
/*
Original join tabs might be overwritten at first
subselect execution. So we need to restore them.
*/
Item_subselect *subselect= select_lex->master_unit()->item;
if (subselect && subselect->is_uncacheable() && join->reinit())
DBUG_RETURN(TRUE);
}
else
{
err= join->prepare(rref_pointer_array, tables, wild_num,
conds, og_num, order, group, having, proc_param,
select_lex, unit);
if (err)
{
goto err;
}
}
}
free_join= 0;
join->select_options= select_options;
}
else
{
if (!(join= new JOIN(thd, fields, select_options, result)))
DBUG_RETURN(TRUE);
thd_proc_info(thd, "init");
thd->lex->used_tables=0; // Updated by setup_fields
err= join->prepare(rref_pointer_array, tables, wild_num,
conds, og_num, order, group, having, proc_param,
select_lex, unit);
if (err)
{
goto err;
}
}
if ((err= join->optimize()))
{
goto err; // 1
}
if (thd->lex->describe & DESCRIBE_EXTENDED)
{
join->conds_history= join->conds;
join->having_history= (join->having?join->having:join->tmp_having);
}
if (thd->is_error())
goto err;
join->exec();
if (thd->lex->describe & DESCRIBE_EXTENDED)
{
select_lex->where= join->conds_history;
select_lex->having= join->having_history;
}
err:
if (free_join)
{
thd_proc_info(thd, "end");
err|= select_lex->cleanup();
DBUG_RETURN(err || thd->is_error());
}
DBUG_RETURN(join->error);
}
/*****************************************************************************
Create JOIN_TABS, make a guess about the table types,
Approximate how many records will be used in each table
*****************************************************************************/
static ha_rows get_quick_record_count(THD *thd, SQL_SELECT *select,
TABLE *table,
const key_map *keys,ha_rows limit)
{
int error;
DBUG_ENTER("get_quick_record_count");
uchar buff[STACK_BUFF_ALLOC];
if (check_stack_overrun(thd, STACK_MIN_SIZE, buff))
DBUG_RETURN(0); // Fatal error flag is set
if (select)
{
select->head=table;
if ((error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
limit, 0)) == 1)
DBUG_RETURN(select->quick->records);
if (error == -1)
{
table->reginfo.impossible_range=1;
DBUG_RETURN(0);
}
DBUG_PRINT("warning",("Couldn't use record count on const keypart"));
}
DBUG_RETURN(HA_POS_ERROR); /* This shouldn't happend */
}
/*
This structure is used to collect info on potentially sargable
predicates in order to check whether they become sargable after
reading const tables.
We form a bitmap of indexes that can be used for sargable predicates.
Only such indexes are involved in range analysis.
*/
typedef struct st_sargable_param
{
Field *field; /* field against which to check sargability */
Item **arg_value; /* values of potential keys for lookups */
uint num_values; /* number of values in the above array */
} SARGABLE_PARAM;
/**
Calculate the best possible join and initialize the join structure.
@retval
0 ok
@retval
1 Fatal error
*/
static bool
make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds,
DYNAMIC_ARRAY *keyuse_array)
{
int error;
TABLE *table;
TABLE_LIST *tables= tables_arg;
uint i,table_count,const_count,key;
table_map found_const_table_map, all_table_map, found_ref, refs;
key_map const_ref, eq_part;
TABLE **table_vector;
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
KEYUSE *keyuse,*start_keyuse;
table_map outer_join=0;
SARGABLE_PARAM *sargables= 0;
JOIN_TAB *stat_vector[MAX_TABLES+1];
DBUG_ENTER("make_join_statistics");
table_count=join->tables;
stat=(JOIN_TAB*) join->thd->calloc(sizeof(JOIN_TAB)*table_count);
stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
table_vector=(TABLE**) join->thd->alloc(sizeof(TABLE*)*(table_count*2));
if (!stat || !stat_ref || !table_vector)
DBUG_RETURN(1); // Eom /* purecov: inspected */
join->best_ref=stat_vector;
stat_end=stat+table_count;
found_const_table_map= all_table_map=0;
const_count=0;
for (s= stat, i= 0;
tables;
s++, tables= tables->next_leaf, i++)
{
TABLE_LIST *embedding= tables->embedding;
stat_vector[i]=s;
s->keys.init();
s->const_keys.init();
s->checked_keys.init();
s->needed_reg.init();
s->filesort_used_loose_index_scan= false;
s->filesort_used_loose_index_scan_agg_distinct= false;
table_vector[i]=s->table=table=tables->table;
table->pos_in_table_list= tables;
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
DBUG_EXECUTE_IF("bug11747970_raise_error",
{
if (!error)
{
my_error(ER_UNKNOWN_ERROR, MYF(0));
goto error;
}
});
if (error)
{
table->file->print_error(error, MYF(0));
goto error;
}
table->quick_keys.clear_all();
table->reginfo.join_tab=s;
table->reginfo.not_exists_optimize=0;
bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->s->keys);
all_table_map|= table->map;
s->join=join;
s->info=0; // For describe
s->dependent= tables->dep_tables;
s->key_dependent= 0;
if (tables->schema_table)
table->file->stats.records= 2;
table->quick_condition_rows= table->file->stats.records;
s->on_expr_ref= &tables->on_expr;
if (*s->on_expr_ref)
{
/* s is the only inner table of an outer join */
#ifdef WITH_PARTITION_STORAGE_ENGINE
if ((!table->file->stats.records || table->no_partitions_used) && !embedding)
#else
if (!table->file->stats.records && !embedding)
#endif
{ // Empty table
s->dependent= 0; // Ignore LEFT JOIN depend.
set_position(join,const_count++,s,(KEYUSE*) 0);
continue;
}
outer_join|= table->map;
s->embedding_map= 0;
for (;embedding; embedding= embedding->embedding)
s->embedding_map|= embedding->nested_join->nj_map;
continue;
}
if (embedding)
{
/* s belongs to a nested join, maybe to several embedded joins */
s->embedding_map= 0;
do
{
NESTED_JOIN *nested_join= embedding->nested_join;
s->embedding_map|=nested_join->nj_map;
s->dependent|= embedding->dep_tables;
embedding= embedding->embedding;
outer_join|= nested_join->used_tables;
}
while (embedding);
continue;
}
#ifdef WITH_PARTITION_STORAGE_ENGINE
const bool no_partitions_used= table->no_partitions_used;
#else
const bool no_partitions_used= FALSE;
#endif
if ((table->s->system || table->file->stats.records <= 1 ||
no_partitions_used) &&
!s->dependent &&
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
!table->fulltext_searched && !join->no_const_tables)
{
set_position(join,const_count++,s,(KEYUSE*) 0);
}
}
stat_vector[i]=0;
join->outer_join=outer_join;
if (join->outer_join)
{
/*
Build transitive closure for relation 'to be dependent on'.
This will speed up the plan search for many cases with outer joins,
as well as allow us to catch illegal cross references.
Warshall's algorithm is used to build the transitive closure.
As we may restart the outer loop upto 'table_count' times, the
complexity of the algorithm is O((number of tables)^3).
However, most of the iterations will be shortcircuited when
there are no pedendencies to propogate.
*/
for (i= 0 ; i < table_count ; i++)
{
uint j;
table= stat[i].table;
if (!table->reginfo.join_tab->dependent)
continue;
/* Add my dependencies to other tables depending on me */
for (j= 0, s= stat ; j < table_count ; j++, s++)
{
if (s->dependent & table->map)
{
table_map was_dependent= s->dependent;
s->dependent |= table->reginfo.join_tab->dependent;
/*
If we change dependencies for a table we already have
processed: Redo dependency propagation from this table.
*/
if (i > j && s->dependent != was_dependent)
{
i = j-1;
break;
}
}
}
}
for (i= 0, s= stat ; i < table_count ; i++, s++)
{
/* Catch illegal cross references for outer joins */
if (s->dependent & s->table->map)
{
join->tables=0; // Don't use join->table
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
goto error;
}
if (outer_join & s->table->map)
s->table->maybe_null= 1;
s->key_dependent= s->dependent;
}
}
if (conds || outer_join)
if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables,
conds, join->cond_equal,
~outer_join, join->select_lex, &sargables))
goto error;
/* Read tables with 0 or 1 rows (system tables) */
join->const_table_map= 0;
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
p_pos < p_end ;
p_pos++)
{
int tmp;
s= p_pos->table;
s->type=JT_SYSTEM;
join->const_table_map|=s->table->map;
if ((tmp=join_read_const_table(s, p_pos)))
{
if (tmp > 0)
goto error; // Fatal error
}
else
{
found_const_table_map|= s->table->map;
s->table->pos_in_table_list->optimized_away= TRUE;
}
}
/* loop until no more const tables are found */
int ref_changed;
do
{
more_const_tables_found:
ref_changed = 0;
found_ref=0;
/*
We only have to loop from stat_vector + const_count as
set_position() will move all const_tables first in stat_vector
*/
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
{
table=s->table;
/*
If equi-join condition by a key is null rejecting and after a
substitution of a const table the key value happens to be null
then we can state that there are no matches for this equi-join.
*/
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
{
/*
When performing an outer join operation if there are no matching rows
for the single row of the outer table all the inner tables are to be
null complemented and thus considered as constant tables.
Here we apply this consideration to the case of outer join operations
with a single inner table only because the case with nested tables
would require a more thorough analysis.
TODO. Apply single row substitution to null complemented inner tables
for nested outer join operations.
*/
while (keyuse->table == table)
{
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
keyuse->val->is_null() && keyuse->null_rejecting)
{
s->type= JT_CONST;
mark_as_null_row(table);
found_const_table_map|= table->map;
join->const_table_map|= table->map;
set_position(join,const_count++,s,(KEYUSE*) 0);
goto more_const_tables_found;
}
keyuse++;
}
}
if (s->dependent) // If dependent on some table
{
// All dep. must be constants
if (s->dependent & ~(found_const_table_map))
continue;
if (table->file->stats.records <= 1L &&
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
!table->pos_in_table_list->embedding)
{ // system table
int tmp= 0;
s->type=JT_SYSTEM;
join->const_table_map|=table->map;
set_position(join,const_count++,s,(KEYUSE*) 0);
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
{
if (tmp > 0)
goto error; // Fatal error
}
else
found_const_table_map|= table->map;
continue;
}
}
/* check if table can be read by key or table only uses const refs */
if ((keyuse=s->keyuse))
{
s->type= JT_REF;
while (keyuse->table == table)
{
start_keyuse=keyuse;
key=keyuse->key;
s->keys.set_bit(key); // QQ: remove this ?
refs=0;
const_ref.clear_all();
eq_part.clear_all();
do
{
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
{
if (!((~found_const_table_map) & keyuse->used_tables))
const_ref.set_bit(keyuse->keypart);
else
refs|=keyuse->used_tables;
eq_part.set_bit(keyuse->keypart);
}
keyuse++;
} while (keyuse->table == table && keyuse->key == key);
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
!table->fulltext_searched &&
!table->pos_in_table_list->embedding)
{
if (table->key_info[key].flags & HA_NOSAME)
{
if (const_ref == eq_part)
{ // Found everything for ref.
int tmp;
ref_changed = 1;
s->type= JT_CONST;
join->const_table_map|=table->map;
set_position(join,const_count++,s,start_keyuse);
if (create_ref_for_key(join, s, start_keyuse,
found_const_table_map))
goto error;
if ((tmp=join_read_const_table(s,
join->positions+const_count-1)))
{
if (tmp > 0)
goto error; // Fatal error
}
else
found_const_table_map|= table->map;
break;
}
else
found_ref|= refs; // Table is const if all refs are const
}
else if (const_ref == eq_part)
s->const_keys.set_bit(key);
}
}
}
}
} while (join->const_table_map & found_ref && ref_changed);
/*
Update info on indexes that can be used for search lookups as
reading const tables may has added new sargable predicates.
*/
if (const_count && sargables)
{
for( ; sargables->field ; sargables++)
{
Field *field= sargables->field;
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
key_map possible_keys= field->key_start;
possible_keys.intersect(field->table->keys_in_use_for_query);
bool is_const= 1;
for (uint j=0; j < sargables->num_values; j++)
is_const&= sargables->arg_value[j]->const_item();
if (is_const)
join_tab[0].const_keys.merge(possible_keys);
}
}
/* Calc how many (possible) matched records in each table */
for (s=stat ; s < stat_end ; s++)
{
if (s->type == JT_SYSTEM || s->type == JT_CONST)
{
/* Only one matching row */
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
continue;
}
/* Approximate found rows and time to read them */
s->found_records=s->records=s->table->file->stats.records;
s->read_time=(ha_rows) s->table->file->scan_time();
/*
Set a max range of how many seeks we can expect when using keys
This is can't be to high as otherwise we are likely to use
table scan.
*/
s->worst_seeks= min((double) s->found_records / 10,
(double) s->read_time*3);
if (s->worst_seeks < 2.0) // Fix for small tables
s->worst_seeks=2.0;
/*
Add to stat->const_keys those indexes for which all group fields or
all select distinct fields participate in one index.
*/
add_group_and_distinct_keys(join, s);
if (!s->const_keys.is_clear_all() &&
!s->table->pos_in_table_list->embedding)
{
ha_rows records;
SQL_SELECT *select;
select= make_select(s->table, found_const_table_map,
found_const_table_map,
*s->on_expr_ref ? *s->on_expr_ref : conds,
1, &error);
if (!select)
goto error;
records= get_quick_record_count(join->thd, select, s->table,
&s->const_keys, join->row_limit);
s->quick=select->quick;
s->needed_reg=select->needed_reg;
select->quick=0;
if (records == 0 && s->table->reginfo.impossible_range)
{
/*
Impossible WHERE or ON expression
In case of ON, we mark that the we match one empty NULL row.
In case of WHERE, don't set found_const_table_map to get the
caller to abort with a zero row result.
*/
join->const_table_map|= s->table->map;
set_position(join,const_count++,s,(KEYUSE*) 0);
s->type= JT_CONST;
if (*s->on_expr_ref)
{
/* Generate empty row */
s->info= "Impossible ON condition";
found_const_table_map|= s->table->map;
s->type= JT_CONST;
mark_as_null_row(s->table); // All fields are NULL
}
}
if (records != HA_POS_ERROR)
{
s->found_records=records;
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
}
delete select;
}
}
join->join_tab=stat;
join->map2table=stat_ref;
join->all_tables= table_vector;
join->const_tables=const_count;
join->found_const_table_map=found_const_table_map;
/* Find an optimal join order of the non-constant tables. */
if (join->const_tables != join->tables)
{
optimize_keyuse(join, keyuse_array);
if (choose_plan(join, all_table_map & ~join->const_table_map))
goto error;
}
else
{
memcpy((uchar*) join->best_positions,(uchar*) join->positions,
sizeof(POSITION)*join->const_tables);
join->best_read=1.0;
}
/* Generate an execution plan from the found optimal join order. */
DBUG_RETURN(join->thd->killed || get_best_combination(join));
error:
/*
Need to clean up join_tab from TABLEs in case of error.
They won't get cleaned up by JOIN::cleanup() because JOIN::join_tab
may not be assigned yet by this function (which is building join_tab).
Dangling TABLE::reginfo.join_tab may cause part_of_refkey to choke.
*/
for (tables= tables_arg; tables; tables= tables->next_leaf)
tables->table->reginfo.join_tab= NULL;
DBUG_RETURN (1);
}
/*****************************************************************************
Check with keys are used and with tables references with tables
Updates in stat:
keys Bitmap of all used keys
const_keys Bitmap of all keys with may be used with quick_select
keyuse Pointer to possible keys
*****************************************************************************/
/// Used when finding key fields
typedef struct key_field_t {
Field *field;
Item *val; ///< May be empty if diff constant
uint level;
uint optimize;
bool eq_func;
/**
If true, the condition this struct represents will not be satisfied
when val IS NULL.
*/
bool null_rejecting;
bool *cond_guard; /* See KEYUSE::cond_guard */
} KEY_FIELD;
/* Values in optimize */
#define KEY_OPTIMIZE_EXISTS 1
#define KEY_OPTIMIZE_REF_OR_NULL 2
/**
Merge new key definitions to old ones, remove those not used in both.
This is called for OR between different levels.
To be able to do 'ref_or_null' we merge a comparison of a column
and 'column IS NULL' to one test. This is useful for sub select queries
that are internally transformed to something like:.
@code
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
@endcode
KEY_FIELD::null_rejecting is processed as follows: @n
result has null_rejecting=true if it is set for both ORed references.
for example:
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
@todo
The result of this is that we're missing some 'ref' accesses.
OptimizerTeam: Fix this
*/
static KEY_FIELD *
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
uint and_level)
{
if (start == new_fields)
return start; // Impossible or
if (new_fields == end)
return start; // No new fields, skip all
KEY_FIELD *first_free=new_fields;
/* Mark all found fields in old array */
for (; new_fields != end ; new_fields++)
{
for (KEY_FIELD *old=start ; old != first_free ; old++)
{
if (old->field == new_fields->field)
{
/*
NOTE: below const_item() call really works as "!used_tables()", i.e.
it can return FALSE where it is feasible to make it return TRUE.
The cause is as follows: Some of the tables are already known to be
const tables (the detection code is in make_join_statistics(),
above the update_ref_and_keys() call), but we didn't propagate
information about this: TABLE::const_table is not set to TRUE, and
Item::update_used_tables() hasn't been called for each item.
The result of this is that we're missing some 'ref' accesses.
TODO: OptimizerTeam: Fix this
*/
if (!new_fields->val->const_item())
{
/*
If the value matches, we can use the key reference.
If not, we keep it until we have examined all new values
*/
if (old->val->eq(new_fields->val, old->field->binary()))
{
old->level= and_level;
old->optimize= ((old->optimize & new_fields->optimize &
KEY_OPTIMIZE_EXISTS) |
((old->optimize | new_fields->optimize) &
KEY_OPTIMIZE_REF_OR_NULL));
old->null_rejecting= (old->null_rejecting &&
new_fields->null_rejecting);
}
}
else if (old->eq_func && new_fields->eq_func &&
old->val->eq_by_collation(new_fields->val,
old->field->binary(),
old->field->charset()))
{
old->level= and_level;
old->optimize= ((old->optimize & new_fields->optimize &
KEY_OPTIMIZE_EXISTS) |
((old->optimize | new_fields->optimize) &
KEY_OPTIMIZE_REF_OR_NULL));
old->null_rejecting= (old->null_rejecting &&
new_fields->null_rejecting);
}
else if (old->eq_func && new_fields->eq_func &&
((old->val->const_item() && old->val->is_null()) ||
new_fields->val->is_null()))
{
/* field = expression OR field IS NULL */
old->level= and_level;
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
/*
Remember the NOT NULL value unless the value does not depend
on other tables.
*/
if (!old->val->used_tables() && old->val->is_null())
old->val= new_fields->val;
/* The referred expression can be NULL: */
old->null_rejecting= 0;
}
else
{
/*
We are comparing two different const. In this case we can't
use a key-lookup on this so it's better to remove the value
and let the range optimzier handle it
*/
if (old == --first_free) // If last item
break;
*old= *first_free; // Remove old value
old--; // Retry this value
}
}
}
}
/* Remove all not used items */
for (KEY_FIELD *old=start ; old != first_free ;)
{
if (old->level != and_level)
{ // Not used in all levels
if (old == --first_free)
break;
*old= *first_free; // Remove old value
continue;
}
old++;
}
return first_free;
}
/**
Add a possible key to array of possible keys if it's usable as a key
@param key_fields Pointer to add key, if usable
@param and_level And level, to be stored in KEY_FIELD
@param cond Condition predicate
@param field Field used in comparision
@param eq_func True if we used =, <=> or IS NULL
@param value Value used for comparison with field
@param usable_tables Tables which can be used for key optimization
@param sargables IN/OUT Array of found sargable candidates
@note
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
table, we store this to be able to do not exists optimization later.
@returns
*key_fields is incremented if we stored a key in the array
*/
static void
add_key_field(KEY_FIELD **key_fields,uint and_level, Item_func *cond,
Field *field, bool eq_func, Item **value, uint num_values,
table_map usable_tables, SARGABLE_PARAM **sargables)
{
uint exists_optimize= 0;
if (!(field->flags & PART_KEY_FLAG))
{
// Don't remove column IS NULL on a LEFT JOIN table
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
!field->table->maybe_null || field->null_ptr)
return; // Not a key. Skip it
exists_optimize= KEY_OPTIMIZE_EXISTS;
DBUG_ASSERT(num_values == 1);
}
else
{
table_map used_tables=0;
bool optimizable=0;
for (uint i=0; i<num_values; i++)
{
used_tables|=(value[i])->used_tables();
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
optimizable=1;
}
if (!optimizable)
return;
if (!(usable_tables & field->table->map))
{
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
!field->table->maybe_null || field->null_ptr)
return; // Can't use left join optimize
exists_optimize= KEY_OPTIMIZE_EXISTS;
}
else
{
JOIN_TAB *stat=field->table->reginfo.join_tab;
key_map possible_keys=field->key_start;
possible_keys.intersect(field->table->keys_in_use_for_query);
stat[0].keys.merge(possible_keys); // Add possible keys
/*
Save the following cases:
Field op constant
Field LIKE constant where constant doesn't start with a wildcard
Field = field2 where field2 is in a different table
Field op formula
Field IS NULL
Field IS NOT NULL
Field BETWEEN ...
Field IN ...
*/
stat[0].key_dependent|=used_tables;
bool is_const=1;
for (uint i=0; i<num_values; i++)
{
if (!(is_const&= value[i]->const_item()))
break;
}
if (is_const)
stat[0].const_keys.merge(possible_keys);
else if (!eq_func)
{
/*
Save info to be able check whether this predicate can be
considered as sargable for range analisis after reading const tables.
We do not save info about equalities as update_const_equal_items
will take care of updating info on keys from sargable equalities.
*/
(*sargables)--;
(*sargables)->field= field;
(*sargables)->arg_value= value;
(*sargables)->num_values= num_values;
}
/*
We can't always use indexes when comparing a string index to a
number. cmp_type() is checked to allow compare of dates to numbers.
eq_func is NEVER true when num_values > 1
*/
if (!eq_func)
return;
if (field->result_type() == STRING_RESULT)
{
if ((*value)->result_type() != STRING_RESULT)
{
if (field->cmp_type() != (*value)->result_type())
return;
}
else
{
/*
We can't use indexes if the effective collation
of the operation differ from the field collation.
*/
if (field->cmp_type() == STRING_RESULT &&
((Field_str*)field)->charset() != cond->compare_collation())
return;
}
}
}
}
/*
For the moment eq_func is always true. This slot is reserved for future
extensions where we want to remembers other things than just eq comparisons
*/
DBUG_ASSERT(eq_func);
/* Store possible eq field */
(*key_fields)->field= field;
(*key_fields)->eq_func= eq_func;
(*key_fields)->val= *value;
(*key_fields)->level= and_level;
(*key_fields)->optimize= exists_optimize;
/*
If the condition has form "tbl.keypart = othertbl.field" and
othertbl.field can be NULL, there will be no matches if othertbl.field
has NULL value.
We use null_rejecting in add_not_null_conds() to add
'othertbl.field IS NOT NULL' to tab->select_cond.
*/
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
((*value)->type() == Item::FIELD_ITEM) &&
((Item_field*)*value)->field->maybe_null());
(*key_fields)->cond_guard= NULL;
(*key_fields)++;
}
/**
Add possible keys to array of possible keys originated from a simple
predicate.
@param key_fields Pointer to add key, if usable
@param and_level And level, to be stored in KEY_FIELD
@param cond Condition predicate
@param field Field used in comparision
@param eq_func True if we used =, <=> or IS NULL
@param value Value used for comparison with field
Is NULL for BETWEEN and IN
@param usable_tables Tables which can be used for key optimization
@param sargables IN/OUT Array of found sargable candidates
@note
If field items f1 and f2 belong to the same multiple equality and
a key is added for f1, the the same key is added for f2.
@returns
*key_fields is incremented if we stored a key in the array
*/
static void
add_key_equal_fields(KEY_FIELD **key_fields, uint and_level,
Item_func *cond, Item_field *field_item,
bool eq_func, Item **val,
uint num_values, table_map usable_tables,
SARGABLE_PARAM **sargables)
{
Field *field= field_item->field;
add_key_field(key_fields, and_level, cond, field,
eq_func, val, num_values, usable_tables, sargables);
Item_equal *item_equal= field_item->item_equal;
if (item_equal)
{
/*
Add to the set of possible key values every substitution of
the field for an equal field included into item_equal
*/
Item_equal_iterator it(*item_equal);
Item_field *item;
while ((item= it++))
{
if (!field->eq(item->field))
{
add_key_field(key_fields, and_level, cond, item->field,
eq_func, val, num_values, usable_tables,
sargables);
}
}
}
}
/**
Check if an expression is a non-outer field.
Checks if an expression is a field and belongs to the current select.
@param field Item expression to check
@return boolean
@retval TRUE the expression is a local field
@retval FALSE it's something else
*/
static bool
is_local_field (Item *field)
{
return field->real_item()->type() == Item::FIELD_ITEM
&& !(field->used_tables() & OUTER_REF_TABLE_BIT)
&& !((Item_field *)field->real_item())->depended_from;
}
static void
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint *and_level,
COND *cond, table_map usable_tables,
SARGABLE_PARAM **sargables)
{
if (cond->type() == Item_func::COND_ITEM)
{
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
KEY_FIELD *org_key_fields= *key_fields;
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
{
Item *item;
while ((item=li++))
add_key_fields(join, key_fields, and_level, item, usable_tables,
sargables);
for (; org_key_fields != *key_fields ; org_key_fields++)
org_key_fields->level= *and_level;
}
else
{
(*and_level)++;
add_key_fields(join, key_fields, and_level, li++, usable_tables,
sargables);
Item *item;
while ((item=li++))
{
KEY_FIELD *start_key_fields= *key_fields;
(*and_level)++;
add_key_fields(join, key_fields, and_level, item, usable_tables,
sargables);
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
*key_fields,++(*and_level));
}
}
return;
}
/*
Subquery optimization: Conditions that are pushed down into subqueries
are wrapped into Item_func_trig_cond. We process the wrapped condition
but need to set cond_guard for KEYUSE elements generated from it.
*/
{
if (cond->type() == Item::FUNC_ITEM &&
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
{
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
if (!join->group_list && !join->order &&
join->unit->item &&
join->unit->item->substype() == Item_subselect::IN_SUBS &&
!join->unit->is_union())
{
KEY_FIELD *save= *key_fields;
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
sargables);
// Indicate that this ref access candidate is for subquery lookup:
for (; save != *key_fields; save++)
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
}
return;
}
}
/* If item is of type 'field op field/constant' add it to key_fields */
if (cond->type() != Item::FUNC_ITEM)
return;
Item_func *cond_func= (Item_func*) cond;
switch (cond_func->select_optimize()) {
case Item_func::OPTIMIZE_NONE:
break;
case Item_func::OPTIMIZE_KEY:
{
Item **values;
/*
Build list of possible keys for 'a BETWEEN low AND high'.
It is handled similar to the equivalent condition
'a >= low AND a <= high':
*/
if (cond_func->functype() == Item_func::BETWEEN)
{
Item_field *field_item;
bool equal_func= FALSE;
uint num_values= 2;
values= cond_func->arguments();
bool binary_cmp= (values[0]->real_item()->type() == Item::FIELD_ITEM)
? ((Item_field*)values[0]->real_item())->field->binary()
: TRUE;
/*
Additional optimization: If 'low = high':
Handle as if the condition was "t.key = low".
*/
if (!((Item_func_between*)cond_func)->negated &&
values[1]->eq(values[2], binary_cmp))
{
equal_func= TRUE;
num_values= 1;
}
/*
Append keys for 'field <cmp> value[]' if the
condition is of the form::
'<field> BETWEEN value[1] AND value[2]'
*/
if (is_local_field (values[0]))
{
field_item= (Item_field *) (values[0]->real_item());
add_key_equal_fields(key_fields, *and_level, cond_func,
field_item, equal_func, &values[1],
num_values, usable_tables, sargables);
}
/*
Append keys for 'value[0] <cmp> field' if the
condition is of the form:
'value[0] BETWEEN field1 AND field2'
*/
for (uint i= 1; i <= num_values; i++)
{
if (is_local_field (values[i]))
{
field_item= (Item_field *) (values[i]->real_item());
add_key_equal_fields(key_fields, *and_level, cond_func,
field_item, equal_func, values,
1, usable_tables, sargables);
}
}
} // if ( ... Item_func::BETWEEN)
// IN, NE
else if (is_local_field (cond_func->key_item()) &&
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
{
values= cond_func->arguments()+1;
if (cond_func->functype() == Item_func::NE_FUNC &&
is_local_field (cond_func->arguments()[1]))
values--;
DBUG_ASSERT(cond_func->functype() != Item_func::IN_FUNC ||
cond_func->argument_count() != 2);
add_key_equal_fields(key_fields, *and_level, cond_func,
(Item_field*) (cond_func->key_item()->real_item()),
0, values,
cond_func->argument_count()-1,
usable_tables, sargables);
}
break;
}
case Item_func::OPTIMIZE_OP:
{
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
cond_func->functype() == Item_func::EQUAL_FUNC);
if (is_local_field (cond_func->arguments()[0]))
{
add_key_equal_fields(key_fields, *and_level, cond_func,
(Item_field*) (cond_func->arguments()[0])->real_item(),
equal_func,
cond_func->arguments()+1, 1, usable_tables,
sargables);
}
if (is_local_field (cond_func->arguments()[1]) &&
cond_func->functype() != Item_func::LIKE_FUNC)
{
add_key_equal_fields(key_fields, *and_level, cond_func,
(Item_field*) (cond_func->arguments()[1])->real_item(),
equal_func,
cond_func->arguments(),1,usable_tables,
sargables);
}
break;
}
case Item_func::OPTIMIZE_NULL:
/* column_name IS [NOT] NULL */
if (is_local_field (cond_func->arguments()[0]) &&
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
{
Item *tmp=new Item_null;
if (unlikely(!tmp)) // Should never be true
return;
add_key_equal_fields(key_fields, *and_level, cond_func,
(Item_field*) (cond_func->arguments()[0])->real_item(),
cond_func->functype() == Item_func::ISNULL_FUNC,
&tmp, 1, usable_tables, sargables);
}
break;
case Item_func::OPTIMIZE_EQUAL:
Item_equal *item_equal= (Item_equal *) cond;
Item *const_item= item_equal->get_const();
Item_equal_iterator it(*item_equal);
Item_field *item;
if (const_item)
{
/*
For each field field1 from item_equal consider the equality
field1=const_item as a condition allowing an index access of the table
with field1 by the keys value of field1.
*/
while ((item= it++))
{
add_key_field(key_fields, *and_level, cond_func, item->field,
TRUE, &const_item, 1, usable_tables, sargables);
}
}
else
{
/*
Consider all pairs of different fields included into item_equal.
For each of them (field1, field1) consider the equality
field1=field2 as a condition allowing an index access of the table
with field1 by the keys value of field2.
*/
Item_equal_iterator fi(*item_equal);
while ((item= fi++))
{
Field *field= item->field;
while ((item= it++))
{
if (!field->eq(item->field))
{
add_key_field(key_fields, *and_level, cond_func, field,
TRUE, (Item **) &item, 1, usable_tables,
sargables);
}
}
it.rewind();
}
}
break;
}
}
static uint
max_part_bit(key_part_map bits)
{
uint found;
for (found=0; bits & 1 ; found++,bits>>=1) ;
return found;
}
/*
Add all keys with uses 'field' for some keypart
If field->and_level != and_level then only mark key_part as const_part
RETURN
0 - OK
1 - Out of memory.
*/
static bool
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
{
Field *field=key_field->field;
TABLE *form= field->table;
KEYUSE keyuse;
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
{
for (uint key=0 ; key < form->s->keys ; key++)
{
if (!(form->keys_in_use_for_query.is_set(key)))
continue;
if (form->key_info[key].flags & (HA_FULLTEXT | HA_SPATIAL))
continue; // ToDo: ft-keys in non-ft queries. SerG
uint key_parts= (uint) form->key_info[key].key_parts;
for (uint part=0 ; part < key_parts ; part++)
{
if (field->eq(form->key_info[key].key_part[part].field))
{
keyuse.table= field->table;
keyuse.val = key_field->val;
keyuse.key = key;
keyuse.keypart=part;
keyuse.keypart_map= (key_part_map) 1 << part;
keyuse.used_tables=key_field->val->used_tables();
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
keyuse.null_rejecting= key_field->null_rejecting;
keyuse.cond_guard= key_field->cond_guard;
if (insert_dynamic(keyuse_array,(uchar*) &keyuse))
return TRUE;
}
}
}
}
return FALSE;
}
#define FT_KEYPART (MAX_REF_PARTS+10)
static bool
add_ft_keys(DYNAMIC_ARRAY *keyuse_array,
JOIN_TAB *stat,COND *cond,table_map usable_tables)
{
Item_func_match *cond_func=NULL;
if (!cond)
return FALSE;
if (cond->type() == Item::FUNC_ITEM)
{
Item_func *func=(Item_func *)cond;
Item_func::Functype functype= func->functype();
if (functype == Item_func::FT_FUNC)
cond_func=(Item_func_match *)cond;
else if (func->arg_count == 2)
{
Item *arg0=(Item *)(func->arguments()[0]),
*arg1=(Item *)(func->arguments()[1]);
if (arg1->const_item() && arg1->cols() == 1 &&
arg0->type() == Item::FUNC_ITEM &&
((Item_func *) arg0)->functype() == Item_func::FT_FUNC &&
((functype == Item_func::GE_FUNC && arg1->val_real() > 0) ||
(functype == Item_func::GT_FUNC && arg1->val_real() >=0)))
cond_func= (Item_func_match *) arg0;
else if (arg0->const_item() &&
arg1->type() == Item::FUNC_ITEM &&
((Item_func *) arg1)->functype() == Item_func::FT_FUNC &&
((functype == Item_func::LE_FUNC && arg0->val_real() > 0) ||
(functype == Item_func::LT_FUNC && arg0->val_real() >=0)))
cond_func= (Item_func_match *) arg1;
}
}
else if (cond->type() == Item::COND_ITEM)
{
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
{
Item *item;
while ((item=li++))
{
if (add_ft_keys(keyuse_array,stat,item,usable_tables))
return TRUE;
}
}
}
if (!cond_func || cond_func->key == NO_SUCH_KEY ||
!(usable_tables & cond_func->table->map))
return FALSE;
KEYUSE keyuse;
keyuse.table= cond_func->table;
keyuse.val = cond_func;
keyuse.key = cond_func->key;
keyuse.keypart= FT_KEYPART;
keyuse.used_tables=cond_func->key_item()->used_tables();
keyuse.optimize= 0;
keyuse.keypart_map= 0;
return insert_dynamic(keyuse_array,(uchar*) &keyuse);
}
static int
sort_keyuse(KEYUSE *a,KEYUSE *b)
{
int res;
if (a->table->tablenr != b->table->tablenr)
return (int) (a->table->tablenr - b->table->tablenr);
if (a->key != b->key)
return (int) (a->key - b->key);
if (a->keypart != b->keypart)
return (int) (a->keypart - b->keypart);
// Place const values before other ones
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
return res;
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
}
/*
Add to KEY_FIELD array all 'ref' access candidates within nested join.
This function populates KEY_FIELD array with entries generated from the
ON condition of the given nested join, and does the same for nested joins
contained within this nested join.
@param[in] nested_join_table Nested join pseudo-table to process
@param[in,out] end End of the key field array
@param[in,out] and_level And-level
@param[in,out] sargables Array of found sargable candidates
@note
We can add accesses to the tables that are direct children of this nested
join (1), and are not inner tables w.r.t their neighbours (2).
Example for #1 (outer brackets pair denotes nested join this function is
invoked for):
@code
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
@endcode
Example for #2:
@code
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
@endcode
In examples 1-2 for condition cond, we can add 'ref' access candidates to
t1 only.
Example #3:
@code
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
@endcode
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
*/
static void add_key_fields_for_nj(JOIN *join, TABLE_LIST *nested_join_table,
KEY_FIELD **end, uint *and_level,
SARGABLE_PARAM **sargables)
{
List_iterator<TABLE_LIST> li(nested_join_table->nested_join->join_list);
table_map tables= 0;
TABLE_LIST *table;
DBUG_ASSERT(nested_join_table->nested_join);
while ((table= li++))
{
if (table->nested_join)
add_key_fields_for_nj(join, table, end, and_level, sargables);
else
if (!table->on_expr)
tables |= table->table->map;
}
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
sargables);
}
/**