Recommended Servers for MySQLThe world's most popular open source database
The world's most popular open source database
mysql/src/5.1-dbg/sql/sql_select.cc
Go to the documentation of this file.00001 /* Copyright (C) 2000-2004 MySQL AB & MySQL Finland AB & TCX DataKonsult AB 00002 00003 This program is free software; you can redistribute it and/or modify 00004 it under the terms of the GNU General Public License as published by 00005 the Free Software Foundation; either version 2 of the License, or 00006 (at your option) any later version. 00007 00008 This program is distributed in the hope that it will be useful, 00009 but WITHOUT ANY WARRANTY; without even the implied warranty of 00010 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00011 GNU General Public License for more details. 00012 00013 You should have received a copy of the GNU General Public License 00014 along with this program; if not, write to the Free Software 00015 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ 00016 00017 00018 /* mysql_select and join optimization */ 00019 00020 #ifdef USE_PRAGMA_IMPLEMENTATION 00021 #pragma implementation // gcc: Class implementation 00022 #endif 00023 00024 #include "mysql_priv.h" 00025 #include "sql_select.h" 00026 #include "sql_cursor.h" 00027 00028 #include <m_ctype.h> 00029 #include <hash.h> 00030 #include <ft_global.h> 00031 00032 const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref", 00033 "MAYBE_REF","ALL","range","index","fulltext", 00034 "ref_or_null","unique_subquery","index_subquery", 00035 "index_merge" 00036 }; 00037 00038 static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array); 00039 static bool make_join_statistics(JOIN *join, TABLE_LIST *leaves, COND *conds, 00040 DYNAMIC_ARRAY *keyuse); 00041 static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse, 00042 JOIN_TAB *join_tab, 00043 uint tables, COND *conds, 00044 COND_EQUAL *cond_equal, 00045 table_map table_map, SELECT_LEX *select_lex); 00046 static int sort_keyuse(KEYUSE *a,KEYUSE *b); 00047 static void set_position(JOIN *join,uint index,JOIN_TAB *table,KEYUSE *key); 00048 static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse, 00049 table_map used_tables); 00050 static void choose_plan(JOIN *join,table_map join_tables); 00051 00052 static void best_access_path(JOIN *join, JOIN_TAB *s, THD *thd, 00053 table_map remaining_tables, uint idx, 00054 double record_count, double read_time); 00055 static void optimize_straight_join(JOIN *join, table_map join_tables); 00056 static void greedy_search(JOIN *join, table_map remaining_tables, 00057 uint depth, uint prune_level); 00058 static void best_extension_by_limited_search(JOIN *join, 00059 table_map remaining_tables, 00060 uint idx, double record_count, 00061 double read_time, uint depth, 00062 uint prune_level); 00063 static uint determine_search_depth(JOIN* join); 00064 static int join_tab_cmp(const void* ptr1, const void* ptr2); 00065 static int join_tab_cmp_straight(const void* ptr1, const void* ptr2); 00066 /* 00067 TODO: 'find_best' is here only temporarily until 'greedy_search' is 00068 tested and approved. 00069 */ 00070 static void find_best(JOIN *join,table_map rest_tables,uint index, 00071 double record_count,double read_time); 00072 static uint cache_record_length(JOIN *join,uint index); 00073 static double prev_record_reads(JOIN *join,table_map found_ref); 00074 static bool get_best_combination(JOIN *join); 00075 static store_key *get_store_key(THD *thd, 00076 KEYUSE *keyuse, table_map used_tables, 00077 KEY_PART_INFO *key_part, char *key_buff, 00078 uint maybe_null); 00079 static bool make_simple_join(JOIN *join,TABLE *tmp_table); 00080 static void make_outerjoin_info(JOIN *join); 00081 static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item); 00082 static void make_join_readinfo(JOIN *join,uint options); 00083 static bool only_eq_ref_tables(JOIN *join, ORDER *order, table_map tables); 00084 static void update_depend_map(JOIN *join); 00085 static void update_depend_map(JOIN *join, ORDER *order); 00086 static ORDER *remove_const(JOIN *join,ORDER *first_order,COND *cond, 00087 bool change_list, bool *simple_order); 00088 static int return_zero_rows(JOIN *join, select_result *res,TABLE_LIST *tables, 00089 List<Item> &fields, bool send_row, 00090 uint select_options, const char *info, 00091 Item *having); 00092 static COND *build_equal_items(THD *thd, COND *cond, 00093 COND_EQUAL *inherited, 00094 List<TABLE_LIST> *join_list, 00095 COND_EQUAL **cond_equal_ref); 00096 static COND* substitute_for_best_equal_field(COND *cond, 00097 COND_EQUAL *cond_equal, 00098 void *table_join_idx); 00099 static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list, 00100 COND *conds, bool top); 00101 static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next); 00102 static void restore_prev_nj_state(JOIN_TAB *last); 00103 static void reset_nj_counters(List<TABLE_LIST> *join_list); 00104 static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list, 00105 uint first_unused); 00106 00107 static COND *optimize_cond(JOIN *join, COND *conds, 00108 List<TABLE_LIST> *join_list, 00109 Item::cond_result *cond_value); 00110 static bool resolve_nested_join (TABLE_LIST *table); 00111 static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item); 00112 static bool open_tmp_table(TABLE *table); 00113 static bool create_myisam_tmp_table(TABLE *table,TMP_TABLE_PARAM *param, 00114 ulong options); 00115 static int do_select(JOIN *join,List<Item> *fields,TABLE *tmp_table, 00116 Procedure *proc); 00117 00118 static enum_nested_loop_state 00119 evaluate_join_record(JOIN *join, JOIN_TAB *join_tab, 00120 int error, my_bool *report_error); 00121 static enum_nested_loop_state 00122 evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab); 00123 static enum_nested_loop_state 00124 flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last); 00125 static enum_nested_loop_state 00126 end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); 00127 static enum_nested_loop_state 00128 end_send_group(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); 00129 static enum_nested_loop_state 00130 end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); 00131 static enum_nested_loop_state 00132 end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); 00133 static enum_nested_loop_state 00134 end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); 00135 static enum_nested_loop_state 00136 end_write_group(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); 00137 00138 static int test_if_group_changed(List<Cached_item> &list); 00139 static int join_read_const_table(JOIN_TAB *tab, POSITION *pos); 00140 static int join_read_system(JOIN_TAB *tab); 00141 static int join_read_const(JOIN_TAB *tab); 00142 static int join_read_key(JOIN_TAB *tab); 00143 static int join_read_always_key(JOIN_TAB *tab); 00144 static int join_read_last_key(JOIN_TAB *tab); 00145 static int join_no_more_records(READ_RECORD *info); 00146 static int join_read_next(READ_RECORD *info); 00147 static int join_init_quick_read_record(JOIN_TAB *tab); 00148 static int test_if_quick_select(JOIN_TAB *tab); 00149 static int join_init_read_record(JOIN_TAB *tab); 00150 static int join_read_first(JOIN_TAB *tab); 00151 static int join_read_next(READ_RECORD *info); 00152 static int join_read_next_same(READ_RECORD *info); 00153 static int join_read_last(JOIN_TAB *tab); 00154 static int join_read_prev_same(READ_RECORD *info); 00155 static int join_read_prev(READ_RECORD *info); 00156 static int join_ft_read_first(JOIN_TAB *tab); 00157 static int join_ft_read_next(READ_RECORD *info); 00158 static int join_read_always_key_or_null(JOIN_TAB *tab); 00159 static int join_read_next_same_or_null(READ_RECORD *info); 00160 static COND *make_cond_for_table(COND *cond,table_map table, 00161 table_map used_table); 00162 static Item* part_of_refkey(TABLE *form,Field *field); 00163 uint find_shortest_key(TABLE *table, const key_map *usable_keys); 00164 static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order, 00165 ha_rows select_limit, bool no_changes); 00166 static bool list_contains_unique_index(TABLE *table, 00167 bool (*find_func) (Field *, void *), void *data); 00168 static bool find_field_in_item_list (Field *field, void *data); 00169 static bool find_field_in_order_list (Field *field, void *data); 00170 static int create_sort_index(THD *thd, JOIN *join, ORDER *order, 00171 ha_rows filesort_limit, ha_rows select_limit); 00172 static int remove_duplicates(JOIN *join,TABLE *entry,List<Item> &fields, 00173 Item *having); 00174 static int remove_dup_with_compare(THD *thd, TABLE *entry, Field **field, 00175 ulong offset,Item *having); 00176 static int remove_dup_with_hash_index(THD *thd,TABLE *table, 00177 uint field_count, Field **first_field, 00178 00179 ulong key_length,Item *having); 00180 static int join_init_cache(THD *thd,JOIN_TAB *tables,uint table_count); 00181 static ulong used_blob_length(CACHE_FIELD **ptr); 00182 static bool store_record_in_cache(JOIN_CACHE *cache); 00183 static void reset_cache_read(JOIN_CACHE *cache); 00184 static void reset_cache_write(JOIN_CACHE *cache); 00185 static void read_cached_record(JOIN_TAB *tab); 00186 static bool cmp_buffer_with_ref(JOIN_TAB *tab); 00187 static bool setup_new_fields(THD *thd, List<Item> &fields, 00188 List<Item> &all_fields, ORDER *new_order); 00189 static ORDER *create_distinct_group(THD *thd, Item **ref_pointer_array, 00190 ORDER *order, List<Item> &fields, 00191 bool *all_order_by_fields_used); 00192 static bool test_if_subpart(ORDER *a,ORDER *b); 00193 static TABLE *get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables); 00194 static void calc_group_buffer(JOIN *join,ORDER *group); 00195 static bool make_group_fields(JOIN *main_join, JOIN *curr_join); 00196 static bool alloc_group_fields(JOIN *join,ORDER *group); 00197 // Create list for using with tempory table 00198 static bool change_to_use_tmp_fields(THD *thd, Item **ref_pointer_array, 00199 List<Item> &new_list1, 00200 List<Item> &new_list2, 00201 uint elements, List<Item> &items); 00202 // Create list for using with tempory table 00203 static bool change_refs_to_tmp_fields(THD *thd, Item **ref_pointer_array, 00204 List<Item> &new_list1, 00205 List<Item> &new_list2, 00206 uint elements, List<Item> &items); 00207 static void init_tmptable_sum_functions(Item_sum **func); 00208 static void update_tmptable_sum_func(Item_sum **func,TABLE *tmp_table); 00209 static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end); 00210 static bool add_ref_to_table_cond(THD *thd, JOIN_TAB *join_tab); 00211 static bool setup_sum_funcs(THD *thd, Item_sum **func_ptr); 00212 static bool init_sum_functions(Item_sum **func, Item_sum **end); 00213 static bool update_sum_func(Item_sum **func); 00214 static void select_describe(JOIN *join, bool need_tmp_table,bool need_order, 00215 bool distinct, const char *message=NullS); 00216 static Item *remove_additional_cond(Item* conds); 00217 static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab); 00218 00219 00220 /* 00221 This handles SELECT with and without UNION 00222 */ 00223 00224 bool handle_select(THD *thd, LEX *lex, select_result *result, 00225 ulong setup_tables_done_option) 00226 { 00227 bool res; 00228 register SELECT_LEX *select_lex = &lex->select_lex; 00229 DBUG_ENTER("handle_select"); 00230 00231 if (select_lex->next_select() || select_lex->master_unit()->fake_select_lex) 00232 res= mysql_union(thd, lex, result, &lex->unit, setup_tables_done_option); 00233 else 00234 { 00235 SELECT_LEX_UNIT *unit= &lex->unit; 00236 unit->set_limit(unit->global_parameters); 00237 /* 00238 'options' of mysql_select will be set in JOIN, as far as JOIN for 00239 every PS/SP execution new, we will not need reset this flag if 00240 setup_tables_done_option changed for next rexecution 00241 */ 00242 res= mysql_select(thd, &select_lex->ref_pointer_array, 00243 (TABLE_LIST*) select_lex->table_list.first, 00244 select_lex->with_wild, select_lex->item_list, 00245 select_lex->where, 00246 select_lex->order_list.elements + 00247 select_lex->group_list.elements, 00248 (ORDER*) select_lex->order_list.first, 00249 (ORDER*) select_lex->group_list.first, 00250 select_lex->having, 00251 (ORDER*) lex->proc_list.first, 00252 select_lex->options | thd->options | 00253 setup_tables_done_option, 00254 result, unit, select_lex); 00255 } 00256 DBUG_PRINT("info",("res: %d report_error: %d", res, 00257 thd->net.report_error)); 00258 res|= thd->net.report_error; 00259 if (unlikely(res)) 00260 { 00261 /* If we had a another error reported earlier then this will be ignored */ 00262 result->send_error(ER_UNKNOWN_ERROR, ER(ER_UNKNOWN_ERROR)); 00263 result->abort(); 00264 } 00265 DBUG_RETURN(res); 00266 } 00267 00268 00269 /* 00270 Function to setup clauses without sum functions 00271 */ 00272 inline int setup_without_group(THD *thd, Item **ref_pointer_array, 00273 TABLE_LIST *tables, 00274 TABLE_LIST *leaves, 00275 List<Item> &fields, 00276 List<Item> &all_fields, 00277 COND **conds, 00278 ORDER *order, 00279 ORDER *group, bool *hidden_group_fields) 00280 { 00281 int res; 00282 nesting_map save_allow_sum_func=thd->lex->allow_sum_func ; 00283 DBUG_ENTER("setup_without_group"); 00284 00285 thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level); 00286 res= setup_conds(thd, tables, leaves, conds); 00287 00288 thd->lex->allow_sum_func|= 1 << thd->lex->current_select->nest_level; 00289 res= res || setup_order(thd, ref_pointer_array, tables, fields, all_fields, 00290 order); 00291 thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level); 00292 res= res || setup_group(thd, ref_pointer_array, tables, fields, all_fields, 00293 group, hidden_group_fields); 00294 thd->lex->allow_sum_func= save_allow_sum_func; 00295 DBUG_RETURN(res); 00296 } 00297 00298 /***************************************************************************** 00299 Check fields, find best join, do the select and output fields. 00300 mysql_select assumes that all tables are already opened 00301 *****************************************************************************/ 00302 00303 /* 00304 Prepare of whole select (including sub queries in future). 00305 return -1 on error 00306 0 on success 00307 */ 00308 int 00309 JOIN::prepare(Item ***rref_pointer_array, 00310 TABLE_LIST *tables_init, 00311 uint wild_num, COND *conds_init, uint og_num, 00312 ORDER *order_init, ORDER *group_init, 00313 Item *having_init, 00314 ORDER *proc_param_init, SELECT_LEX *select_lex_arg, 00315 SELECT_LEX_UNIT *unit_arg) 00316 { 00317 DBUG_ENTER("JOIN::prepare"); 00318 00319 // to prevent double initialization on EXPLAIN 00320 if (optimized) 00321 DBUG_RETURN(0); 00322 00323 conds= conds_init; 00324 order= order_init; 00325 group_list= group_init; 00326 having= having_init; 00327 proc_param= proc_param_init; 00328 tables_list= tables_init; 00329 select_lex= select_lex_arg; 00330 select_lex->join= this; 00331 join_list= &select_lex->top_join_list; 00332 union_part= (unit_arg->first_select()->next_select() != 0); 00333 00334 /* 00335 If we have already executed SELECT, then it have not sense to prevent 00336 its table from update (see unique_table()) 00337 */ 00338 if (thd->derived_tables_processing) 00339 select_lex->exclude_from_table_unique_test= TRUE; 00340 00341 /* Check that all tables, fields, conds and order are ok */ 00342 00343 if ((!(select_options & OPTION_SETUP_TABLES_DONE) && 00344 setup_tables_and_check_access(thd, &select_lex->context, join_list, 00345 tables_list, 00346 &select_lex->leaf_tables, FALSE, 00347 SELECT_ACL)) || 00348 setup_wild(thd, tables_list, fields_list, &all_fields, wild_num) || 00349 select_lex->setup_ref_array(thd, og_num) || 00350 setup_fields(thd, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ, 00351 &all_fields, 1) || 00352 setup_without_group(thd, (*rref_pointer_array), tables_list, 00353 select_lex->leaf_tables, fields_list, 00354 all_fields, &conds, order, group_list, 00355 &hidden_group_fields)) 00356 DBUG_RETURN(-1); /* purecov: inspected */ 00357 00358 ref_pointer_array= *rref_pointer_array; 00359 00360 if (having) 00361 { 00362 nesting_map save_allow_sum_func= thd->lex->allow_sum_func; 00363 thd->where="having clause"; 00364 thd->lex->allow_sum_func|= 1 << select_lex_arg->nest_level; 00365 select_lex->having_fix_field= 1; 00366 bool having_fix_rc= (!having->fixed && 00367 (having->fix_fields(thd, &having) || 00368 having->check_cols(1))); 00369 select_lex->having_fix_field= 0; 00370 if (having_fix_rc || thd->net.report_error) 00371 DBUG_RETURN(-1); /* purecov: inspected */ 00372 thd->lex->allow_sum_func= save_allow_sum_func; 00373 } 00374 00375 if (!thd->lex->view_prepare_mode) 00376 { 00377 Item_subselect *subselect; 00378 /* Is it subselect? */ 00379 if ((subselect= select_lex->master_unit()->item)) 00380 { 00381 Item_subselect::trans_res res; 00382 if ((res= subselect->select_transformer(this)) != 00383 Item_subselect::RES_OK) 00384 { 00385 select_lex->fix_prepare_information(thd, &conds); 00386 DBUG_RETURN((res == Item_subselect::RES_ERROR)); 00387 } 00388 } 00389 } 00390 00391 if (having && having->with_sum_func) 00392 having->split_sum_func2(thd, ref_pointer_array, all_fields, 00393 &having, TRUE); 00394 if (select_lex->inner_sum_func_list) 00395 { 00396 Item_sum *end=select_lex->inner_sum_func_list; 00397 Item_sum *item_sum= end; 00398 do 00399 { 00400 item_sum= item_sum->next; 00401 item_sum->split_sum_func2(thd, ref_pointer_array, 00402 all_fields, item_sum->ref_by, FALSE); 00403 } while (item_sum != end); 00404 } 00405 00406 if (setup_ftfuncs(select_lex)) /* should be after having->fix_fields */ 00407 DBUG_RETURN(-1); 00408 00409 00410 /* 00411 Check if one one uses a not constant column with group functions 00412 and no GROUP BY. 00413 TODO: Add check of calculation of GROUP functions and fields: 00414 SELECT COUNT(*)+table.col1 from table1; 00415 */ 00416 { 00417 if (!group_list) 00418 { 00419 uint flag=0; 00420 List_iterator_fast<Item> it(fields_list); 00421 Item *item; 00422 while ((item= it++)) 00423 { 00424 if (item->with_sum_func) 00425 flag|=1; 00426 else if (!(flag & 2) && !item->const_during_execution()) 00427 flag|=2; 00428 } 00429 if (flag == 3) 00430 { 00431 my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS, 00432 ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0)); 00433 DBUG_RETURN(-1); 00434 } 00435 } 00436 TABLE_LIST *table_ptr; 00437 for (table_ptr= select_lex->leaf_tables; 00438 table_ptr; 00439 table_ptr= table_ptr->next_leaf) 00440 tables++; 00441 } 00442 { 00443 /* Caclulate the number of groups */ 00444 send_group_parts= 0; 00445 for (ORDER *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next) 00446 send_group_parts++; 00447 } 00448 00449 procedure= setup_procedure(thd, proc_param, result, fields_list, &error); 00450 if (error) 00451 goto err; /* purecov: inspected */ 00452 if (procedure) 00453 { 00454 if (setup_new_fields(thd, fields_list, all_fields, 00455 procedure->param_fields)) 00456 goto err; /* purecov: inspected */ 00457 if (procedure->group) 00458 { 00459 if (!test_if_subpart(procedure->group,group_list)) 00460 { /* purecov: inspected */ 00461 my_message(ER_DIFF_GROUPS_PROC, ER(ER_DIFF_GROUPS_PROC), 00462 MYF(0)); /* purecov: inspected */ 00463 goto err; /* purecov: inspected */ 00464 } 00465 } 00466 if (order && (procedure->flags & PROC_NO_SORT)) 00467 { /* purecov: inspected */ 00468 my_message(ER_ORDER_WITH_PROC, ER(ER_ORDER_WITH_PROC), 00469 MYF(0)); /* purecov: inspected */ 00470 goto err; /* purecov: inspected */ 00471 } 00472 } 00473 00474 /* Init join struct */ 00475 count_field_types(&tmp_table_param, all_fields, 0); 00476 ref_pointer_array_size= all_fields.elements*sizeof(Item*); 00477 this->group= group_list != 0; 00478 unit= unit_arg; 00479 00480 #ifdef RESTRICTED_GROUP 00481 if (sum_func_count && !group_list && (func_count || field_count)) 00482 { 00483 my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0)); 00484 goto err; 00485 } 00486 #endif 00487 if (!procedure && result && result->prepare(fields_list, unit_arg)) 00488 goto err; /* purecov: inspected */ 00489 00490 if (select_lex->olap == ROLLUP_TYPE && rollup_init()) 00491 goto err; 00492 if (alloc_func_list()) 00493 goto err; 00494 00495 select_lex->fix_prepare_information(thd, &conds); 00496 DBUG_RETURN(0); // All OK 00497 00498 err: 00499 delete procedure; /* purecov: inspected */ 00500 procedure= 0; 00501 DBUG_RETURN(-1); /* purecov: inspected */ 00502 } 00503 00504 /* 00505 test if it is known for optimisation IN subquery 00506 00507 SYNOPSYS 00508 JOIN::test_in_subselect 00509 where - pointer for variable in which conditions should be 00510 stored if subquery is known 00511 00512 RETURN 00513 1 - known 00514 0 - unknown 00515 */ 00516 00517 bool JOIN::test_in_subselect(Item **where) 00518 { 00519 if (conds->type() == Item::FUNC_ITEM && 00520 ((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC && 00521 ((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM && 00522 ((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM) 00523 { 00524 join_tab->info= "Using index"; 00525 *where= 0; 00526 return 1; 00527 } 00528 if (conds->type() == Item::COND_ITEM && 00529 ((class Item_func *)this->conds)->functype() == 00530 Item_func::COND_AND_FUNC) 00531 { 00532 if ((*where= remove_additional_cond(conds))) 00533 join_tab->info= "Using index; Using where"; 00534 else 00535 join_tab->info= "Using index"; 00536 return 1; 00537 } 00538 return 0; 00539 } 00540 00541 00542 /* 00543 global select optimisation. 00544 return 0 - success 00545 1 - error 00546 error code saved in field 'error' 00547 */ 00548 00549 int 00550 JOIN::optimize() 00551 { 00552 DBUG_ENTER("JOIN::optimize"); 00553 // to prevent double initialization on EXPLAIN 00554 if (optimized) 00555 DBUG_RETURN(0); 00556 optimized= 1; 00557 00558 row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR : 00559 unit->select_limit_cnt); 00560 /* select_limit is used to decide if we are likely to scan the whole table */ 00561 select_limit= unit->select_limit_cnt; 00562 if (having || (select_options & OPTION_FOUND_ROWS)) 00563 select_limit= HA_POS_ERROR; 00564 do_send_rows = (unit->select_limit_cnt) ? 1 : 0; 00565 // Ignore errors of execution if option IGNORE present 00566 if (thd->lex->ignore) 00567 thd->lex->current_select->no_error= 1; 00568 #ifdef HAVE_REF_TO_FIELDS // Not done yet 00569 /* Add HAVING to WHERE if possible */ 00570 if (having && !group_list && !sum_func_count) 00571 { 00572 if (!conds) 00573 { 00574 conds= having; 00575 having= 0; 00576 } 00577 else if ((conds=new Item_cond_and(conds,having))) 00578 { 00579 /* 00580 Item_cond_and can't be fixed after creation, so we do not check 00581 conds->fixed 00582 */ 00583 conds->fix_fields(thd, &conds); 00584 conds->change_ref_to_fields(thd, tables_list); 00585 conds->top_level_item(); 00586 having= 0; 00587 } 00588 } 00589 #endif 00590 SELECT_LEX *sel= thd->lex->current_select; 00591 if (sel->first_cond_optimization) 00592 { 00593 /* 00594 The following code will allocate the new items in a permanent 00595 MEMROOT for prepared statements and stored procedures. 00596 */ 00597 00598 Query_arena *arena= thd->stmt_arena, backup; 00599 if (arena->is_conventional()) 00600 arena= 0; // For easier test 00601 else 00602 thd->set_n_backup_active_arena(arena, &backup); 00603 00604 sel->first_cond_optimization= 0; 00605 00606 /* Convert all outer joins to inner joins if possible */ 00607 conds= simplify_joins(this, join_list, conds, TRUE); 00608 build_bitmap_for_nested_joins(join_list, 0); 00609 00610 sel->prep_where= conds ? conds->copy_andor_structure(thd) : 0; 00611 sel->prep_having= having ? having->copy_andor_structure(thd) : 0; 00612 00613 if (arena) 00614 thd->restore_active_arena(arena, &backup); 00615 } 00616 00617 conds= optimize_cond(this, conds, join_list, &cond_value); 00618 if (thd->net.report_error) 00619 { 00620 error= 1; 00621 DBUG_PRINT("error",("Error from optimize_cond")); 00622 DBUG_RETURN(1); 00623 } 00624 00625 { 00626 Item::cond_result having_value; 00627 having= optimize_cond(this, having, join_list, &having_value); 00628 if (thd->net.report_error) 00629 { 00630 error= 1; 00631 DBUG_PRINT("error",("Error from optimize_cond")); 00632 DBUG_RETURN(1); 00633 } 00634 00635 if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE || 00636 (!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS))) 00637 { /* Impossible cond */ 00638 DBUG_PRINT("info", (having_value == Item::COND_FALSE ? 00639 "Impossible HAVING" : "Impossible WHERE")); 00640 zero_result_cause= having_value == Item::COND_FALSE ? 00641 "Impossible HAVING" : "Impossible WHERE"; 00642 error= 0; 00643 DBUG_RETURN(0); 00644 } 00645 } 00646 00647 #ifdef WITH_PARTITION_STORAGE_ENGINE 00648 { 00649 TABLE_LIST *tbl; 00650 for (tbl= select_lex->leaf_tables; tbl; tbl= tbl->next_leaf) 00651 { 00652 /* 00653 If tbl->embedding!=NULL that means that this table is in the inner 00654 part of the nested outer join, and we can't do partition pruning 00655 (TODO: check if this limitation can be lifted) 00656 */ 00657 if (!tbl->embedding) 00658 { 00659 Item *prune_cond= tbl->on_expr? tbl->on_expr : conds; 00660 tbl->table->no_partitions_used= prune_partitions(thd, tbl->table, 00661 prune_cond); 00662 } 00663 } 00664 } 00665 #endif 00666 00667 /* Optimize count(*), min() and max() */ 00668 if (tables_list && tmp_table_param.sum_func_count && ! group_list) 00669 { 00670 int res; 00671 /* 00672 opt_sum_query() returns -1 if no rows match to the WHERE conditions, 00673 or 1 if all items were resolved, or 0, or an error number HA_ERR_... 00674 */ 00675 if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds))) 00676 { 00677 if (res > 1) 00678 { 00679 DBUG_PRINT("error",("Error from opt_sum_query")); 00680 DBUG_RETURN(1); 00681 } 00682 if (res < 0) 00683 { 00684 DBUG_PRINT("info",("No matching min/max row")); 00685 zero_result_cause= "No matching min/max row"; 00686 error=0; 00687 DBUG_RETURN(0); 00688 } 00689 DBUG_PRINT("info",("Select tables optimized away")); 00690 zero_result_cause= "Select tables optimized away"; 00691 tables_list= 0; // All tables resolved 00692 /* 00693 Extract all table-independent conditions and replace the WHERE 00694 clause with them. All other conditions were computed by opt_sum_query 00695 and the MIN/MAX/COUNT function(s) have been replaced by constants, 00696 so there is no need to compute the whole WHERE clause again. 00697 Notice that make_cond_for_table() will always succeed to remove all 00698 computed conditions, because opt_sum_query() is applicable only to 00699 conjunctions. 00700 Preserve conditions for EXPLAIN. 00701 */ 00702 if (conds && !(thd->lex->describe & DESCRIBE_EXTENDED)) 00703 { 00704 COND *table_independent_conds= 00705 make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0); 00706 DBUG_EXECUTE("where", 00707 print_where(table_independent_conds, 00708 "where after opt_sum_query()");); 00709 conds= table_independent_conds; 00710 } 00711 } 00712 } 00713 if (!tables_list) 00714 { 00715 DBUG_PRINT("info",("No tables")); 00716 error= 0; 00717 DBUG_RETURN(0); 00718 } 00719 error= -1; // Error is sent to client 00720 sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables); 00721 00722 /* Calculate how to do the join */ 00723 thd->proc_info= "statistics"; 00724 if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) || 00725 thd->is_fatal_error) 00726 { 00727 DBUG_PRINT("error",("Error: make_join_statistics() failed")); 00728 DBUG_RETURN(1); 00729 } 00730 00731 /* Remove distinct if only const tables */ 00732 select_distinct= select_distinct && (const_tables != tables); 00733 thd->proc_info= "preparing"; 00734 if (result->initialize_tables(this)) 00735 { 00736 DBUG_PRINT("error",("Error: initialize_tables() failed")); 00737 DBUG_RETURN(1); // error == -1 00738 } 00739 if (const_table_map != found_const_table_map && 00740 !(select_options & SELECT_DESCRIBE) && 00741 (!conds || 00742 !(conds->used_tables() & RAND_TABLE_BIT) || 00743 select_lex->master_unit() == &thd->lex->unit)) // upper level SELECT 00744 { 00745 zero_result_cause= "no matching row in const table"; 00746 DBUG_PRINT("error",("Error: %s", zero_result_cause)); 00747 error= 0; 00748 DBUG_RETURN(0); 00749 } 00750 if (!(thd->options & OPTION_BIG_SELECTS) && 00751 best_read > (double) thd->variables.max_join_size && 00752 !(select_options & SELECT_DESCRIBE)) 00753 { /* purecov: inspected */ 00754 my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0)); 00755 error= -1; 00756 DBUG_RETURN(1); 00757 } 00758 if (const_tables && !thd->locked_tables && 00759 !(select_options & SELECT_NO_UNLOCK)) 00760 mysql_unlock_some_tables(thd, table, const_tables); 00761 if (!conds && outer_join) 00762 { 00763 /* Handle the case where we have an OUTER JOIN without a WHERE */ 00764 conds=new Item_int((longlong) 1,1); // Always true 00765 } 00766 select= make_select(*table, const_table_map, 00767 const_table_map, conds, 1, &error); 00768 if (error) 00769 { /* purecov: inspected */ 00770 error= -1; /* purecov: inspected */ 00771 DBUG_PRINT("error",("Error: make_select() failed")); 00772 DBUG_RETURN(1); 00773 } 00774 00775 reset_nj_counters(join_list); 00776 make_outerjoin_info(this); 00777 00778 /* 00779 Among the equal fields belonging to the same multiple equality 00780 choose the one that is to be retrieved first and substitute 00781 all references to these in where condition for a reference for 00782 the selected field. 00783 */ 00784 if (conds) 00785 { 00786 conds= substitute_for_best_equal_field(conds, cond_equal, map2table); 00787 conds->update_used_tables(); 00788 DBUG_EXECUTE("where", print_where(conds, "after substitute_best_equal");); 00789 } 00790 /* 00791 Permorm the the optimization on fields evaluation mentioned above 00792 for all on expressions. 00793 */ 00794 for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++) 00795 { 00796 if (*tab->on_expr_ref) 00797 { 00798 *tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref, 00799 tab->cond_equal, 00800 map2table); 00801 (*tab->on_expr_ref)->update_used_tables(); 00802 } 00803 } 00804 00805 if (make_join_select(this, select, conds)) 00806 { 00807 zero_result_cause= 00808 "Impossible WHERE noticed after reading const tables"; 00809 DBUG_RETURN(0); // error == 0 00810 } 00811 00812 error= -1; /* if goto err */ 00813 00814 /* Optimize distinct away if possible */ 00815 { 00816 ORDER *org_order= order; 00817 order=remove_const(this, order,conds,1, &simple_order); 00818 /* 00819 If we are using ORDER BY NULL or ORDER BY const_expression, 00820 return result in any order (even if we are using a GROUP BY) 00821 */ 00822 if (!order && org_order) 00823 skip_sort_order= 1; 00824 } 00825 if (group_list || tmp_table_param.sum_func_count) 00826 { 00827 if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE) 00828 select_distinct=0; 00829 } 00830 else if (select_distinct && tables - const_tables == 1) 00831 { 00832 /* 00833 We are only using one table. In this case we change DISTINCT to a 00834 GROUP BY query if: 00835 - The GROUP BY can be done through indexes (no sort) and the ORDER 00836 BY only uses selected fields. 00837 (In this case we can later optimize away GROUP BY and ORDER BY) 00838 - We are scanning the whole table without LIMIT 00839 This can happen if: 00840 - We are using CALC_FOUND_ROWS 00841 - We are using an ORDER BY that can't be optimized away. 00842 00843 We don't want to use this optimization when we are using LIMIT 00844 because in this case we can just create a temporary table that 00845 holds LIMIT rows and stop when this table is full. 00846 */ 00847 JOIN_TAB *tab= &join_tab[const_tables]; 00848 bool all_order_fields_used; 00849 if (order) 00850 skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1); 00851 if ((group_list=create_distinct_group(thd, select_lex->ref_pointer_array, 00852 order, fields_list, 00853 &all_order_fields_used))) 00854 { 00855 bool skip_group= (skip_sort_order && 00856 test_if_skip_sort_order(tab, group_list, select_limit, 00857 1) != 0); 00858 if ((skip_group && all_order_fields_used) || 00859 select_limit == HA_POS_ERROR || 00860 (order && !skip_sort_order)) 00861 { 00862 /* Change DISTINCT to GROUP BY */ 00863 select_distinct= 0; 00864 no_order= !order; 00865 if (all_order_fields_used) 00866 { 00867 if (order && skip_sort_order) 00868 { 00869 /* 00870 Force MySQL to read the table in sorted order to get result in 00871 ORDER BY order. 00872 */ 00873 tmp_table_param.quick_group=0; 00874 } 00875 order=0; 00876 } 00877 group=1; // For end_write_group 00878 } 00879 else 00880 group_list= 0; 00881 } 00882 else if (thd->is_fatal_error) // End of memory 00883 DBUG_RETURN(1); 00884 } 00885 simple_group= 0; 00886 { 00887 ORDER *old_group_list; 00888 group_list= remove_const(this, (old_group_list= group_list), conds, 00889 rollup.state == ROLLUP::STATE_NONE, 00890 &simple_group); 00891 if (old_group_list && !group_list) 00892 select_distinct= 0; 00893 } 00894 /* 00895 Check if we can optimize away GROUP BY/DISTINCT. 00896 We can do that if there are no aggregate functions and the 00897 fields in DISTINCT clause (if present) and/or columns in GROUP BY 00898 (if present) contain direct references to all key parts of 00899 an unique index (in whatever order). 00900 Note that the unique keys for DISTINCT and GROUP BY should not 00901 be the same (as long as they are unique). 00902 00903 The FROM clause must contain a single non-constant table. 00904 */ 00905 if (tables - const_tables == 1 && (group_list || select_distinct) && 00906 !tmp_table_param.sum_func_count && 00907 (!join_tab[const_tables].select || 00908 !join_tab[const_tables].select->quick || 00909 join_tab[const_tables].select->quick->get_type() != 00910 QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)) 00911 { 00912 if (group_list && 00913 list_contains_unique_index(join_tab[const_tables].table, 00914 find_field_in_order_list, 00915 (void *) group_list)) 00916 { 00917 group_list= 0; 00918 group= 0; 00919 } 00920 if (select_distinct && 00921 list_contains_unique_index(join_tab[const_tables].table, 00922 find_field_in_item_list, 00923 (void *) &fields_list)) 00924 { 00925 select_distinct= 0; 00926 } 00927 } 00928 if (!group_list && group) 00929 { 00930 order=0; // The output has only one row 00931 simple_order=1; 00932 select_distinct= 0; // No need in distinct for 1 row 00933 } 00934 00935 calc_group_buffer(this, group_list); 00936 send_group_parts= tmp_table_param.group_parts; /* Save org parts */ 00937 if (procedure && procedure->group) 00938 { 00939 group_list= procedure->group= remove_const(this, procedure->group, conds, 00940 1, &simple_group); 00941 calc_group_buffer(this, group_list); 00942 } 00943 00944 if (test_if_subpart(group_list, order) || 00945 (!group_list && tmp_table_param.sum_func_count)) 00946 order=0; 00947 00948 // Can't use sort on head table if using row cache 00949 if (full_join) 00950 { 00951 if (group_list) 00952 simple_group=0; 00953 if (order) 00954 simple_order=0; 00955 } 00956 00957 /* 00958 Check if we need to create a temporary table. 00959 This has to be done if all tables are not already read (const tables) 00960 and one of the following conditions holds: 00961 - We are using DISTINCT (simple distinct's are already optimized away) 00962 - We are using an ORDER BY or GROUP BY on fields not in the first table 00963 - We are using different ORDER BY and GROUP BY orders 00964 - The user wants us to buffer the result. 00965 */ 00966 need_tmp= (const_tables != tables && 00967 ((select_distinct || !simple_order || !simple_group) || 00968 (group_list && order) || 00969 test(select_options & OPTION_BUFFER_RESULT))); 00970 00971 // No cache for MATCH 00972 make_join_readinfo(this, 00973 (select_options & (SELECT_DESCRIBE | 00974 SELECT_NO_JOIN_CACHE)) | 00975 (select_lex->ftfunc_list->elements ? 00976 SELECT_NO_JOIN_CACHE : 0)); 00977 00978 /* Perform FULLTEXT search before all regular searches */ 00979 if (!(select_options & SELECT_DESCRIBE)) 00980 init_ftfuncs(thd, select_lex, test(order)); 00981 00982 /* 00983 is this simple IN subquery? 00984 */ 00985 if (!group_list && !order && 00986 unit->item && unit->item->substype() == Item_subselect::IN_SUBS && 00987 tables == 1 && conds && 00988 !unit->first_select()->next_select()) 00989 { 00990 if (!having) 00991 { 00992 Item *where= 0; 00993 if (join_tab[0].type == JT_EQ_REF && 00994 join_tab[0].ref.items[0]->name == in_left_expr_name) 00995 { 00996 if (test_in_subselect(&where)) 00997 { 00998 join_tab[0].type= JT_UNIQUE_SUBQUERY; 00999 error= 0; 01000 DBUG_RETURN(unit->item-> 01001 change_engine(new 01002 subselect_uniquesubquery_engine(thd, 01003 join_tab, 01004 unit->item, 01005 where))); 01006 } 01007 } 01008 else if (join_tab[0].type == JT_REF && 01009 join_tab[0].ref.items[0]->name == in_left_expr_name) 01010 { 01011 if (test_in_subselect(&where)) 01012 { 01013 join_tab[0].type= JT_INDEX_SUBQUERY; 01014 error= 0; 01015 DBUG_RETURN(unit->item-> 01016 change_engine(new 01017 subselect_indexsubquery_engine(thd, 01018 join_tab, 01019 unit->item, 01020 where, 01021 0))); 01022 } 01023 } 01024 } else if (join_tab[0].type == JT_REF_OR_NULL && 01025 join_tab[0].ref.items[0]->name == in_left_expr_name && 01026 having->type() == Item::FUNC_ITEM && 01027 ((Item_func *) having)->functype() == 01028 Item_func::ISNOTNULLTEST_FUNC) 01029 { 01030 join_tab[0].type= JT_INDEX_SUBQUERY; 01031 error= 0; 01032 01033 if ((conds= remove_additional_cond(conds))) 01034 join_tab->info= "Using index; Using where"; 01035 else 01036 join_tab->info= "Using index"; 01037 01038 DBUG_RETURN(unit->item-> 01039 change_engine(new subselect_indexsubquery_engine(thd, 01040 join_tab, 01041 unit->item, 01042 conds, 01043 1))); 01044 } 01045 01046 } 01047 /* 01048 Need to tell handlers that to play it safe, it should fetch all 01049 columns of the primary key of the tables: this is because MySQL may 01050 build row pointers for the rows, and for all columns of the primary key 01051 the read set has not necessarily been set by the server code. 01052 */ 01053 if (need_tmp || select_distinct || group_list || order) 01054 { 01055 for (uint i = const_tables; i < tables; i++) 01056 join_tab[i].table->prepare_for_position(); 01057 } 01058 01059 DBUG_EXECUTE("info",TEST_join(this);); 01060 01061 if (const_tables != tables) 01062 { 01063 /* 01064 Because filesort always does a full table scan or a quick range scan 01065 we must add the removed reference to the select for the table. 01066 We only need to do this when we have a simple_order or simple_group 01067 as in other cases the join is done before the sort. 01068 */ 01069 if ((order || group_list) && 01070 join_tab[const_tables].type != JT_ALL && 01071 join_tab[const_tables].type != JT_FT && 01072 join_tab[const_tables].type != JT_REF_OR_NULL && 01073 (order && simple_order || group_list && simple_group)) 01074 { 01075 if (add_ref_to_table_cond(thd,&join_tab[const_tables])) 01076 DBUG_RETURN(1); 01077 } 01078 01079 if (!(select_options & SELECT_BIG_RESULT) && 01080 ((group_list && 01081 (!simple_group || 01082 !test_if_skip_sort_order(&join_tab[const_tables], group_list, 01083 unit->select_limit_cnt, 0))) || 01084 select_distinct) && 01085 tmp_table_param.quick_group && !procedure) 01086 { 01087 need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort 01088 } 01089 if (order) 01090 { 01091 /* 01092 Force using of tmp table if sorting by a SP or UDF function due to 01093 their expensive and probably non-deterministic nature. 01094 */ 01095 for (ORDER *tmp_order= order; tmp_order ; tmp_order=tmp_order->next) 01096 { 01097 Item *item= *tmp_order->item; 01098 if (item->walk(&Item::is_expensive_processor, 0, (byte*)0)) 01099 { 01100 /* Force tmp table without sort */ 01101 need_tmp=1; simple_order=simple_group=0; 01102 break; 01103 } 01104 } 01105 } 01106 } 01107 01108 tmp_having= having; 01109 if (select_options & SELECT_DESCRIBE) 01110 { 01111 error= 0; 01112 DBUG_RETURN(0); 01113 } 01114 having= 0; 01115 01116 /* 01117 The loose index scan access method guarantees that all grouping or 01118 duplicate row elimination (for distinct) is already performed 01119 during data retrieval, and that all MIN/MAX functions are already 01120 computed for each group. Thus all MIN/MAX functions should be 01121 treated as regular functions, and there is no need to perform 01122 grouping in the main execution loop. 01123 Notice that currently loose index scan is applicable only for 01124 single table queries, thus it is sufficient to test only the first 01125 join_tab element of the plan for its access method. 01126 */ 01127 if (join_tab->is_using_loose_index_scan()) 01128 tmp_table_param.precomputed_group_by= TRUE; 01129 01130 /* Create a tmp table if distinct or if the sort is too complicated */ 01131 if (need_tmp) 01132 { 01133 DBUG_PRINT("info",("Creating tmp table")); 01134 thd->proc_info="Creating tmp table"; 01135 01136 init_items_ref_array(); 01137 01138 tmp_table_param.hidden_field_count= (all_fields.elements - 01139 fields_list.elements); 01140 if (!(exec_tmp_table1= 01141 create_tmp_table(thd, &tmp_table_param, all_fields, 01142 ((!simple_group && !procedure && 01143 !(test_flags & TEST_NO_KEY_GROUP)) ? 01144 group_list : (ORDER*) 0), 01145 group_list ? 0 : select_distinct, 01146 group_list && simple_group, 01147 select_options, 01148 (order == 0 || skip_sort_order || 01149 test(select_options & OPTION_BUFFER_RESULT)) ? 01150 select_limit : HA_POS_ERROR, 01151 (char *) ""))) 01152 DBUG_RETURN(1); 01153 01154 /* 01155 We don't have to store rows in temp table that doesn't match HAVING if: 01156 - we are sorting the table and writing complete group rows to the 01157 temp table. 01158 - We are using DISTINCT without resolving the distinct as a GROUP BY 01159 on all columns. 01160 01161 If having is not handled here, it will be checked before the row 01162 is sent to the client. 01163 */ 01164 if (tmp_having && 01165 (sort_and_group || (exec_tmp_table1->distinct && !group_list))) 01166 having= tmp_having; 01167 01168 /* if group or order on first table, sort first */ 01169 if (group_list && simple_group) 01170 { 01171 DBUG_PRINT("info",("Sorting for group")); 01172 thd->proc_info="Sorting for group"; 01173 if (create_sort_index(thd, this, group_list, 01174 HA_POS_ERROR, HA_POS_ERROR) || 01175 alloc_group_fields(this, group_list) || 01176 make_sum_func_list(all_fields, fields_list, 1) || 01177 setup_sum_funcs(thd, sum_funcs)) 01178 DBUG_RETURN(1); 01179 group_list=0; 01180 } 01181 else 01182 { 01183 if (make_sum_func_list(all_fields, fields_list, 0) || 01184 setup_sum_funcs(thd, sum_funcs)) 01185 DBUG_RETURN(1); 01186 if (!group_list && ! exec_tmp_table1->distinct && order && simple_order) 01187 { 01188 DBUG_PRINT("info",("Sorting for order")); 01189 thd->proc_info="Sorting for order"; 01190 if (create_sort_index(thd, this, order, 01191 HA_POS_ERROR, HA_POS_ERROR)) 01192 DBUG_RETURN(1); 01193 order=0; 01194 } 01195 } 01196 01197 /* 01198 Optimize distinct when used on some of the tables 01199 SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b 01200 In this case we can stop scanning t2 when we have found one t1.a 01201 */ 01202 01203 if (exec_tmp_table1->distinct) 01204 { 01205 table_map used_tables= thd->used_tables; 01206 JOIN_TAB *last_join_tab= join_tab+tables-1; 01207 do 01208 { 01209 if (used_tables & last_join_tab->table->map) 01210 break; 01211 last_join_tab->not_used_in_distinct=1; 01212 } while (last_join_tab-- != join_tab); 01213 /* Optimize "select distinct b from t1 order by key_part_1 limit #" */ 01214 if (order && skip_sort_order) 01215 { 01216 /* Should always succeed */ 01217 if (test_if_skip_sort_order(&join_tab[const_tables], 01218 order, unit->select_limit_cnt, 0)) 01219 order=0; 01220 } 01221 } 01222 01223 if (select_lex->uncacheable && !is_top_level_join()) 01224 { 01225 /* If this join belongs to an uncacheable subquery */ 01226 if (!(tmp_join= (JOIN*)thd->alloc(sizeof(JOIN)))) 01227 DBUG_RETURN(-1); 01228 error= 0; // Ensure that tmp_join.error= 0 01229 restore_tmp(); 01230 } 01231 } 01232 01233 error= 0; 01234 DBUG_RETURN(0); 01235 } 01236 01237 01238 /* 01239 Restore values in temporary join 01240 */ 01241 void JOIN::restore_tmp() 01242 { 01243 memcpy(tmp_join, this, (size_t) sizeof(JOIN)); 01244 } 01245 01246 01247 int 01248 JOIN::reinit() 01249 { 01250 DBUG_ENTER("JOIN::reinit"); 01251 01252 unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ? 01253 select_lex->offset_limit->val_uint() : 01254 ULL(0)); 01255 01256 first_record= 0; 01257 01258 if (exec_tmp_table1) 01259 { 01260 exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE); 01261 exec_tmp_table1->file->delete_all_rows(); 01262 free_io_cache(exec_tmp_table1); 01263 filesort_free_buffers(exec_tmp_table1); 01264 } 01265 if (exec_tmp_table2) 01266 { 01267 exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE); 01268 exec_tmp_table2->file->delete_all_rows(); 01269 free_io_cache(exec_tmp_table2); 01270 filesort_free_buffers(exec_tmp_table2); 01271 } 01272 if (items0) 01273 set_items_ref_array(items0); 01274 01275 if (join_tab_save) 01276 memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables); 01277 01278 if (tmp_join) 01279 restore_tmp(); 01280 01281 /* Reset of sum functions */ 01282 if (sum_funcs) 01283 { 01284 Item_sum *func, **func_ptr= sum_funcs; 01285 while ((func= *(func_ptr++))) 01286 func->clear(); 01287 } 01288 01289 DBUG_RETURN(0); 01290 } 01291 01292 01293 bool 01294 JOIN::save_join_tab() 01295 { 01296 if (!join_tab_save && select_lex->master_unit()->uncacheable) 01297 { 01298 if (!(join_tab_save= (JOIN_TAB*)thd->memdup((gptr) join_tab, 01299 sizeof(JOIN_TAB) * tables))) 01300 return 1; 01301 } 01302 return 0; 01303 } 01304 01305 01306 /* 01307 Exec select 01308 */ 01309 void 01310 JOIN::exec() 01311 { 01312 List<Item> *columns_list= &fields_list; 01313 int tmp_error; 01314 DBUG_ENTER("JOIN::exec"); 01315 01316 error= 0; 01317 if (procedure) 01318 { 01319 procedure_fields_list= fields_list; 01320 if (procedure->change_columns(procedure_fields_list) || 01321 result->prepare(procedure_fields_list, unit)) 01322 { 01323 thd->limit_found_rows= thd->examined_row_count= 0; 01324 DBUG_VOID_RETURN; 01325 } 01326 columns_list= &procedure_fields_list; 01327 } 01328 (void) result->prepare2(); // Currently, this cannot fail. 01329 01330 if (!tables_list) 01331 { // Only test of functions 01332 if (select_options & SELECT_DESCRIBE) 01333 select_describe(this, FALSE, FALSE, FALSE, 01334 (zero_result_cause?zero_result_cause:"No tables used")); 01335 else 01336 { 01337 result->send_fields(*columns_list, 01338 Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF); 01339 /* 01340 We have to test for 'conds' here as the WHERE may not be constant 01341 even if we don't have any tables for prepared statements or if 01342 conds uses something like 'rand()'. 01343 */ 01344 if (cond_value != Item::COND_FALSE && 01345 (!conds || conds->val_int()) && 01346 (!having || having->val_int())) 01347 { 01348 if (do_send_rows && 01349 (procedure ? (procedure->send_row(procedure_fields_list) || 01350 procedure->end_of_records()) : result->send_data(fields_list))) 01351 error= 1; 01352 else 01353 { 01354 error= (int) result->send_eof(); 01355 send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : 01356 thd->sent_row_count); 01357 } 01358 } 01359 else 01360 { 01361 error=(int) result->send_eof(); 01362 send_records= 0; 01363 } 01364 } 01365 /* Single select (without union) always returns 0 or 1 row */ 01366 thd->limit_found_rows= send_records; 01367 thd->examined_row_count= 0; 01368 DBUG_VOID_RETURN; 01369 } 01370 thd->limit_found_rows= thd->examined_row_count= 0; 01371 01372 if (zero_result_cause) 01373 { 01374 (void) return_zero_rows(this, result, select_lex->leaf_tables, 01375 *columns_list, 01376 send_row_on_empty_set(), 01377 select_options, 01378 zero_result_cause, 01379 having); 01380 DBUG_VOID_RETURN; 01381 } 01382 01383 if (select_options & SELECT_DESCRIBE) 01384 { 01385 /* 01386 Check if we managed to optimize ORDER BY away and don't use temporary 01387 table to resolve ORDER BY: in that case, we only may need to do 01388 filesort for GROUP BY. 01389 */ 01390 if (!order && !no_order && (!skip_sort_order || !need_tmp)) 01391 { 01392 /* 01393 Reset 'order' to 'group_list' and reinit variables describing 01394 'order' 01395 */ 01396 order= group_list; 01397 simple_order= simple_group; 01398 skip_sort_order= 0; 01399 } 01400 if (order && 01401 (const_tables == tables || 01402 ((simple_order || skip_sort_order) && 01403 test_if_skip_sort_order(&join_tab[const_tables], order, 01404 select_limit, 0)))) 01405 order=0; 01406 having= tmp_having; 01407 select_describe(this, need_tmp, 01408 order != 0 && !skip_sort_order, 01409 select_distinct); 01410 DBUG_VOID_RETURN; 01411 } 01412 01413 JOIN *curr_join= this; 01414 List<Item> *curr_all_fields= &all_fields; 01415 List<Item> *curr_fields_list= &fields_list; 01416 TABLE *curr_tmp_table= 0; 01417 01418 if ((curr_join->select_lex->options & OPTION_SCHEMA_TABLE) && 01419 get_schema_tables_result(curr_join)) 01420 { 01421 DBUG_VOID_RETURN; 01422 } 01423 01424 /* Create a tmp table if distinct or if the sort is too complicated */ 01425 if (need_tmp) 01426 { 01427 if (tmp_join) 01428 { 01429 /* 01430 We are in a non cacheable sub query. Get the saved join structure 01431 after optimization. 01432 (curr_join may have been modified during last exection and we need 01433 to reset it) 01434 */ 01435 curr_join= tmp_join; 01436 } 01437 curr_tmp_table= exec_tmp_table1; 01438 01439 /* Copy data to the temporary table */ 01440 thd->proc_info= "Copying to tmp table"; 01441 DBUG_PRINT("info", ("%s", thd->proc_info)); 01442 if (!curr_join->sort_and_group && 01443 curr_join->const_tables != curr_join->tables) 01444 curr_join->join_tab[curr_join->const_tables].sorted= 0; 01445 if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table, 0))) 01446 { 01447 error= tmp_error; 01448 DBUG_VOID_RETURN; 01449 } 01450 curr_tmp_table->file->info(HA_STATUS_VARIABLE); 01451 01452 if (curr_join->having) 01453 curr_join->having= curr_join->tmp_having= 0; // Allready done 01454 01455 /* Change sum_fields reference to calculated fields in tmp_table */ 01456 curr_join->all_fields= *curr_all_fields; 01457 if (!items1) 01458 { 01459 items1= items0 + all_fields.elements; 01460 if (sort_and_group || curr_tmp_table->group) 01461 { 01462 if (change_to_use_tmp_fields(thd, items1, 01463 tmp_fields_list1, tmp_all_fields1, 01464 fields_list.elements, all_fields)) 01465 DBUG_VOID_RETURN; 01466 } 01467 else 01468 { 01469 if (change_refs_to_tmp_fields(thd, items1, 01470 tmp_fields_list1, tmp_all_fields1, 01471 fields_list.elements, all_fields)) 01472 DBUG_VOID_RETURN; 01473 } 01474 curr_join->tmp_all_fields1= tmp_all_fields1; 01475 curr_join->tmp_fields_list1= tmp_fields_list1; 01476 curr_join->items1= items1; 01477 } 01478 curr_all_fields= &tmp_all_fields1; 01479 curr_fields_list= &tmp_fields_list1; 01480 curr_join->set_items_ref_array(items1); 01481 01482 if (sort_and_group || curr_tmp_table->group) 01483 { 01484 curr_join->tmp_table_param.field_count+= 01485 curr_join->tmp_table_param.sum_func_count+ 01486 curr_join->tmp_table_param.func_count; 01487 curr_join->tmp_table_param.sum_func_count= 01488 curr_join->tmp_table_param.func_count= 0; 01489 } 01490 else 01491 { 01492 curr_join->tmp_table_param.field_count+= 01493 curr_join->tmp_table_param.func_count; 01494 curr_join->tmp_table_param.func_count= 0; 01495 } 01496 01497 // procedure can't be used inside subselect => we do nothing special for it 01498 if (procedure) 01499 procedure->update_refs(); 01500 01501 if (curr_tmp_table->group) 01502 { // Already grouped 01503 if (!curr_join->order && !curr_join->no_order && !skip_sort_order) 01504 curr_join->order= curr_join->group_list; /* order by group */ 01505 curr_join->group_list= 0; 01506 } 01507 01508 /* 01509 If we have different sort & group then we must sort the data by group 01510 and copy it to another tmp table 01511 This code is also used if we are using distinct something 01512 we haven't been able to store in the temporary table yet 01513 like SEC_TO_TIME(SUM(...)). 01514 */ 01515 01516 if (curr_join->group_list && (!test_if_subpart(curr_join->group_list, 01517 curr_join->order) || 01518 curr_join->select_distinct) || 01519 (curr_join->select_distinct && 01520 curr_join->tmp_table_param.using_indirect_summary_function)) 01521 { /* Must copy to another table */ 01522 DBUG_PRINT("info",("Creating group table")); 01523 01524 /* Free first data from old join */ 01525 curr_join->join_free(); 01526 if (make_simple_join(curr_join, curr_tmp_table)) 01527 DBUG_VOID_RETURN; 01528 calc_group_buffer(curr_join, group_list); 01529 count_field_types(&curr_join->tmp_table_param, 01530 curr_join->tmp_all_fields1, 01531 curr_join->select_distinct && !curr_join->group_list); 01532 curr_join->tmp_table_param.hidden_field_count= 01533 (curr_join->tmp_all_fields1.elements- 01534 curr_join->tmp_fields_list1.elements); 01535 01536 01537 if (exec_tmp_table2) 01538 curr_tmp_table= exec_tmp_table2; 01539 else 01540 { 01541 /* group data to new table */ 01542 01543 /* 01544 If the access method is loose index scan then all MIN/MAX 01545 functions are precomputed, and should be treated as regular 01546 functions. See extended comment in JOIN::exec. 01547 */ 01548 if (curr_join->join_tab->is_using_loose_index_scan()) 01549 curr_join->tmp_table_param.precomputed_group_by= TRUE; 01550 01551 if (!(curr_tmp_table= 01552 exec_tmp_table2= create_tmp_table(thd, 01553 &curr_join->tmp_table_param, 01554 *curr_all_fields, 01555 (ORDER*) 0, 01556 curr_join->select_distinct && 01557 !curr_join->group_list, 01558 1, curr_join->select_options, 01559 HA_POS_ERROR, 01560 (char *) ""))) 01561 DBUG_VOID_RETURN; 01562 curr_join->exec_tmp_table2= exec_tmp_table2; 01563 } 01564 if (curr_join->group_list) 01565 { 01566 thd->proc_info= "Creating sort index"; 01567 if (curr_join->join_tab == join_tab && save_join_tab()) 01568 { 01569 DBUG_VOID_RETURN; 01570 } 01571 if (create_sort_index(thd, curr_join, curr_join->group_list, 01572 HA_POS_ERROR, HA_POS_ERROR) || 01573 make_group_fields(this, curr_join)) 01574 { 01575 DBUG_VOID_RETURN; 01576 } 01577 } 01578 01579 thd->proc_info="Copying to group table"; 01580 DBUG_PRINT("info", ("%s", thd->proc_info)); 01581 tmp_error= -1; 01582 if (curr_join != this) 01583 { 01584 if (sum_funcs2) 01585 { 01586 curr_join->sum_funcs= sum_funcs2; 01587 curr_join->sum_funcs_end= sum_funcs_end2; 01588 } 01589 else 01590 { 01591 curr_join->alloc_func_list(); 01592 sum_funcs2= curr_join->sum_funcs; 01593 sum_funcs_end2= curr_join->sum_funcs_end; 01594 } 01595 } 01596 if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 01597 1, TRUE)) 01598 DBUG_VOID_RETURN; 01599 curr_join->group_list= 0; 01600 if (!curr_join->sort_and_group && 01601 curr_join->const_tables != curr_join->tables) 01602 curr_join->join_tab[curr_join->const_tables].sorted= 0; 01603 if (setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) || 01604 (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table, 01605 0))) 01606 { 01607 error= tmp_error; 01608 DBUG_VOID_RETURN; 01609 } 01610 end_read_record(&curr_join->join_tab->read_record); 01611 curr_join->const_tables= curr_join->tables; // Mark free for cleanup() 01612 curr_join->join_tab[0].table= 0; // Table is freed 01613 01614 // No sum funcs anymore 01615 if (!items2) 01616 { 01617 items2= items1 + all_fields.elements; 01618 if (change_to_use_tmp_fields(thd, items2, 01619 tmp_fields_list2, tmp_all_fields2, 01620 fields_list.elements, tmp_all_fields1)) 01621 DBUG_VOID_RETURN; 01622 curr_join->tmp_fields_list2= tmp_fields_list2; 01623 curr_join->tmp_all_fields2= tmp_all_fields2; 01624 } 01625 curr_fields_list= &curr_join->tmp_fields_list2; 01626 curr_all_fields= &curr_join->tmp_all_fields2; 01627 curr_join->set_items_ref_array(items2); 01628 curr_join->tmp_table_param.field_count+= 01629 curr_join->tmp_table_param.sum_func_count; 01630 curr_join->tmp_table_param.sum_func_count= 0; 01631 } 01632 if (curr_tmp_table->distinct) 01633 curr_join->select_distinct=0; /* Each row is unique */ 01634 01635 curr_join->join_free(); /* Free quick selects */ 01636 if (curr_join->select_distinct && ! curr_join->group_list) 01637 { 01638 thd->proc_info="Removing duplicates"; 01639 if (curr_join->tmp_having) 01640 curr_join->tmp_having->update_used_tables(); 01641 if (remove_duplicates(curr_join, curr_tmp_table, 01642 *curr_fields_list, curr_join->tmp_having)) 01643 DBUG_VOID_RETURN; 01644 curr_join->tmp_having=0; 01645 curr_join->select_distinct=0; 01646 } 01647 curr_tmp_table->reginfo.lock_type= TL_UNLOCK; 01648 if (make_simple_join(curr_join, curr_tmp_table)) 01649 DBUG_VOID_RETURN; 01650 calc_group_buffer(curr_join, curr_join->group_list); 01651 count_field_types(&curr_join->tmp_table_param, *curr_all_fields, 0); 01652 01653 } 01654 if (procedure) 01655 count_field_types(&curr_join->tmp_table_param, *curr_all_fields, 0); 01656 01657 if (curr_join->group || curr_join->tmp_table_param.sum_func_count || 01658 (procedure && (procedure->flags & PROC_GROUP))) 01659 { 01660 if (make_group_fields(this, curr_join)) 01661 { 01662 DBUG_VOID_RETURN; 01663 } 01664 if (!items3) 01665 { 01666 if (!items0) 01667 init_items_ref_array(); 01668 items3= ref_pointer_array + (all_fields.elements*4); 01669 setup_copy_fields(thd, &curr_join->tmp_table_param, 01670 items3, tmp_fields_list3, tmp_all_fields3, 01671 curr_fields_list->elements, *curr_all_fields); 01672 tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs; 01673 tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field; 01674 tmp_table_param.save_copy_field_end= 01675 curr_join->tmp_table_param.copy_field_end; 01676 curr_join->tmp_all_fields3= tmp_all_fields3; 01677 curr_join->tmp_fields_list3= tmp_fields_list3; 01678 } 01679 else 01680 { 01681 curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs; 01682 curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field; 01683 curr_join->tmp_table_param.copy_field_end= 01684 tmp_table_param.save_copy_field_end; 01685 } 01686 curr_fields_list= &tmp_fields_list3; 01687 curr_all_fields= &tmp_all_fields3; 01688 curr_join->set_items_ref_array(items3); 01689 01690 if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 01691 1, TRUE) || 01692 setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) || 01693 thd->is_fatal_error) 01694 DBUG_VOID_RETURN; 01695 } 01696 if (curr_join->group_list || curr_join->order) 01697 { 01698 DBUG_PRINT("info",("Sorting for send_fields")); 01699 thd->proc_info="Sorting result"; 01700 /* If we have already done the group, add HAVING to sorted table */ 01701 if (curr_join->tmp_having && ! curr_join->group_list && 01702 ! curr_join->sort_and_group) 01703 { 01704 // Some tables may have been const 01705 curr_join->tmp_having->update_used_tables(); 01706 JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables]; 01707 table_map used_tables= (curr_join->const_table_map | 01708 curr_table->table->map); 01709 01710 Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, 01711 used_tables, 01712 used_tables); 01713 if (sort_table_cond) 01714 { 01715 if (!curr_table->select) 01716 if (!(curr_table->select= new SQL_SELECT)) 01717 DBUG_VOID_RETURN; 01718 if (!curr_table->select->cond) 01719 curr_table->select->cond= sort_table_cond; 01720 else // This should never happen 01721 { 01722 if (!(curr_table->select->cond= 01723 new Item_cond_and(curr_table->select->cond, 01724 sort_table_cond))) 01725 DBUG_VOID_RETURN; 01726 /* 01727 Item_cond_and do not need fix_fields for execution, its parameters 01728 are fixed or do not need fix_fields, too 01729 */ 01730 curr_table->select->cond->quick_fix_field(); 01731 } 01732 curr_table->select_cond= curr_table->select->cond; 01733 curr_table->select_cond->top_level_item(); 01734 DBUG_EXECUTE("where",print_where(curr_table->select->cond, 01735 "select and having");); 01736 curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having, 01737 ~ (table_map) 0, 01738 ~used_tables); 01739 DBUG_EXECUTE("where",print_where(curr_join->tmp_having, 01740 "having after sort");); 01741 } 01742 } 01743 { 01744 if (group) 01745 curr_join->select_limit= HA_POS_ERROR; 01746 else 01747 { 01748 /* 01749 We can abort sorting after thd->select_limit rows if we there is no 01750 WHERE clause for any tables after the sorted one. 01751 */ 01752 JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1]; 01753 JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables]; 01754 for (; curr_table < end_table ; curr_table++) 01755 { 01756 /* 01757 table->keyuse is set in the case there was an original WHERE clause 01758 on the table that was optimized away. 01759 */ 01760 if (curr_table->select_cond || 01761 (curr_table->keyuse && !curr_table->first_inner)) 01762 { 01763 /* We have to sort all rows */ 01764 curr_join->select_limit= HA_POS_ERROR; 01765 break; 01766 } 01767 } 01768 } 01769 if (curr_join->join_tab == join_tab && save_join_tab()) 01770 { 01771 DBUG_VOID_RETURN; 01772 } 01773 /* 01774 Here we sort rows for ORDER BY/GROUP BY clause, if the optimiser 01775 chose FILESORT to be faster than INDEX SCAN or there is no 01776 suitable index present. 01777 Note, that create_sort_index calls test_if_skip_sort_order and may 01778 finally replace sorting with index scan if there is a LIMIT clause in 01779 the query. XXX: it's never shown in EXPLAIN! 01780 OPTION_FOUND_ROWS supersedes LIMIT and is taken into account. 01781 */ 01782 if (create_sort_index(thd, curr_join, 01783 curr_join->group_list ? 01784 curr_join->group_list : curr_join->order, 01785 curr_join->select_limit, 01786 (select_options & OPTION_FOUND_ROWS ? 01787 HA_POS_ERROR : unit->select_limit_cnt))) 01788 DBUG_VOID_RETURN; 01789 if (curr_join->const_tables != curr_join->tables && 01790 !curr_join->join_tab[curr_join->const_tables].table->sort.io_cache) 01791 { 01792 /* 01793 If no IO cache exists for the first table then we are using an 01794 INDEX SCAN and no filesort. Thus we should not remove the sorted 01795 attribute on the INDEX SCAN. 01796 */ 01797 skip_sort_order= 1; 01798 } 01799 } 01800 } 01801 /* XXX: When can we have here thd->net.report_error not zero? */ 01802 if (thd->net.report_error) 01803 { 01804 error= thd->net.report_error; 01805 DBUG_VOID_RETURN; 01806 } 01807 curr_join->having= curr_join->tmp_having; 01808 curr_join->fields= curr_fields_list; 01809 curr_join->procedure= procedure; 01810 01811 if (is_top_level_join() && thd->cursor && tables != const_tables) 01812 { 01813 /* 01814 We are here if this is JOIN::exec for the last select of the main unit 01815 and the client requested to open a cursor. 01816 We check that not all tables are constant because this case is not 01817 handled by do_select() separately, and this case is not implemented 01818 for cursors yet. 01819 */ 01820 DBUG_ASSERT(error == 0); 01821 /* 01822 curr_join is used only for reusable joins - that is, 01823 to perform SELECT for each outer row (like in subselects). 01824 This join is main, so we know for sure that curr_join == join. 01825 */ 01826 DBUG_ASSERT(curr_join == this); 01827 /* Open cursor for the last join sweep */ 01828 error= thd->cursor->open(this); 01829 } 01830 else 01831 { 01832 thd->proc_info="Sending data"; 01833 DBUG_PRINT("info", ("%s", thd->proc_info)); 01834 result->send_fields((procedure ? curr_join->procedure_fields_list : 01835 *curr_fields_list), 01836 Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF); 01837 error= do_select(curr_join, curr_fields_list, NULL, procedure); 01838 thd->limit_found_rows= curr_join->send_records; 01839 thd->examined_row_count= curr_join->examined_rows; 01840 } 01841 01842 DBUG_VOID_RETURN; 01843 } 01844 01845 01846 /* 01847 Clean up join. Return error that hold JOIN. 01848 */ 01849 01850 int 01851 JOIN::destroy() 01852 { 01853 DBUG_ENTER("JOIN::destroy"); 01854 select_lex->join= 0; 01855 01856 if (tmp_join) 01857 { 01858 if (join_tab != tmp_join->join_tab) 01859 { 01860 JOIN_TAB *tab, *end; 01861 for (tab= join_tab, end= tab+tables ; tab != end ; tab++) 01862 tab->cleanup(); 01863 } 01864 tmp_join->tmp_join= 0; 01865 tmp_table_param.copy_field=0; 01866 DBUG_RETURN(tmp_join->destroy()); 01867 } 01868 cond_equal= 0; 01869 01870 cleanup(1); 01871 if (exec_tmp_table1) 01872 free_tmp_table(thd, exec_tmp_table1); 01873 if (exec_tmp_table2) 01874 free_tmp_table(thd, exec_tmp_table2); 01875 delete select; 01876 delete_dynamic(&keyuse); 01877 delete procedure; 01878 DBUG_RETURN(error); 01879 } 01880 01881 /* 01882 An entry point to single-unit select (a select without UNION). 01883 01884 SYNOPSIS 01885 mysql_select() 01886 01887 thd thread handler 01888 rref_pointer_array a reference to ref_pointer_array of 01889 the top-level select_lex for this query 01890 tables list of all tables used in this query. 01891 The tables have been pre-opened. 01892 wild_num number of wildcards used in the top level 01893 select of this query. 01894 For example statement 01895 SELECT *, t1.*, catalog.t2.* FROM t0, t1, t2; 01896 has 3 wildcards. 01897 fields list of items in SELECT list of the top-level 01898 select 01899 e.g. SELECT a, b, c FROM t1 will have Item_field 01900 for a, b and c in this list. 01901 conds top level item of an expression representing 01902 WHERE clause of the top level select 01903 og_num total number of ORDER BY and GROUP BY clauses 01904 arguments 01905 order linked list of ORDER BY agruments 01906 group linked list of GROUP BY arguments 01907 having top level item of HAVING expression 01908 proc_param list of PROCEDUREs 01909 select_options select options (BIG_RESULT, etc) 01910 result an instance of result set handling class. 01911 This object is responsible for send result 01912 set rows to the client or inserting them 01913 into a table. 01914 select_lex the only SELECT_LEX of this query 01915 unit top-level UNIT of this query 01916 UNIT is an artificial object created by the parser 01917 for every SELECT clause. 01918 e.g. SELECT * FROM t1 WHERE a1 IN (SELECT * FROM t2) 01919 has 2 unions. 01920 01921 RETURN VALUE 01922 FALSE success 01923 TRUE an error 01924 */ 01925 01926 bool 01927 mysql_select(THD *thd, Item ***rref_pointer_array, 01928 TABLE_LIST *tables, uint wild_num, List<Item> &fields, 01929 COND *conds, uint og_num, ORDER *order, ORDER *group, 01930 Item *having, ORDER *proc_param, ulong select_options, 01931 select_result *result, SELECT_LEX_UNIT *unit, 01932 SELECT_LEX *select_lex) 01933 { 01934 bool err; 01935 bool free_join= 1; 01936 DBUG_ENTER("mysql_select"); 01937 01938 select_lex->context.resolve_in_select_list= TRUE; 01939 JOIN *join; 01940 if (select_lex->join != 0) 01941 { 01942 join= select_lex->join; 01943 /* 01944 is it single SELECT in derived table, called in derived table 01945 creation 01946 */ 01947 if (select_lex->linkage != DERIVED_TABLE_TYPE || 01948 (select_options & SELECT_DESCRIBE)) 01949 { 01950 if (select_lex->linkage != GLOBAL_OPTIONS_TYPE) 01951 { 01952 //here is EXPLAIN of subselect or derived table 01953 if (join->change_result(result)) 01954 { 01955 DBUG_RETURN(TRUE); 01956 } 01957 } 01958 else 01959 { 01960 if (err= join->prepare(rref_pointer_array, tables, wild_num, 01961 conds, og_num, order, group, having, proc_param, 01962 select_lex, unit)) 01963 { 01964 goto err; 01965 } 01966 } 01967 } 01968 free_join= 0; 01969 join->select_options= select_options; 01970 } 01971 else 01972 { 01973 if (!(join= new JOIN(thd, fields, select_options, result))) 01974 DBUG_RETURN(TRUE); 01975 thd->proc_info="init"; 01976 thd->used_tables=0; // Updated by setup_fields 01977 if (err= join->prepare(rref_pointer_array, tables, wild_num, 01978 conds, og_num, order, group, having, proc_param, 01979 select_lex, unit)) 01980 { 01981 goto err; 01982 } 01983 } 01984 01985 if ((err= join->optimize())) 01986 { 01987 goto err; // 1 01988 } 01989 01990 if (thd->lex->describe & DESCRIBE_EXTENDED) 01991 { 01992 join->conds_history= join->conds; 01993 join->having_history= (join->having?join->having:join->tmp_having); 01994 } 01995 01996 if (thd->net.report_error) 01997 goto err; 01998 01999 join->exec(); 02000 02001 if (thd->cursor && thd->cursor->is_open()) 02002 { 02003 /* 02004 A cursor was opened for the last sweep in exec(). 02005 We are here only if this is mysql_select for top-level SELECT_LEX_UNIT 02006 and there were no error. 02007 */ 02008 free_join= 0; 02009 } 02010 02011 if (thd->lex->describe & DESCRIBE_EXTENDED) 02012 { 02013 select_lex->where= join->conds_history; 02014 select_lex->having= join->having_history; 02015 } 02016 02017 err: 02018 if (free_join) 02019 { 02020 thd->proc_info="end"; 02021 err|= select_lex->cleanup(); 02022 DBUG_RETURN(err || thd->net.report_error); 02023 } 02024 DBUG_RETURN(join->error); 02025 } 02026 02027 /***************************************************************************** 02028 Create JOIN_TABS, make a guess about the table types, 02029 Approximate how many records will be used in each table 02030 *****************************************************************************/ 02031 02032 static ha_rows get_quick_record_count(THD *thd, SQL_SELECT *select, 02033 TABLE *table, 02034 const key_map *keys,ha_rows limit) 02035 { 02036 int error; 02037 DBUG_ENTER("get_quick_record_count"); 02038 if (select) 02039 { 02040 select->head=table; 02041 table->reginfo.impossible_range=0; 02042 if ((error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0, 02043 limit, 0)) == 1) 02044 DBUG_RETURN(select->quick->records); 02045 if (error == -1) 02046 { 02047 table->reginfo.impossible_range=1; 02048 DBUG_RETURN(0); 02049 } 02050 DBUG_PRINT("warning",("Couldn't use record count on const keypart")); 02051 } 02052 DBUG_RETURN(HA_POS_ERROR); /* This shouldn't happend */ 02053 } 02054 02055 02056 /* 02057 Calculate the best possible join and initialize the join structure 02058 02059 RETURN VALUES 02060 0 ok 02061 1 Fatal error 02062 */ 02063 02064 static bool 02065 make_join_statistics(JOIN *join, TABLE_LIST *tables, COND *conds, 02066 DYNAMIC_ARRAY *keyuse_array) 02067 { 02068 int error; 02069 TABLE *table; 02070 uint i,table_count,const_count,key; 02071 table_map found_const_table_map, all_table_map, found_ref, refs; 02072 key_map const_ref, eq_part; 02073 TABLE **table_vector; 02074 JOIN_TAB *stat,*stat_end,*s,**stat_ref; 02075 KEYUSE *keyuse,*start_keyuse; 02076 table_map outer_join=0; 02077 JOIN_TAB *stat_vector[MAX_TABLES+1]; 02078 DBUG_ENTER("make_join_statistics"); 02079 02080 table_count=join->tables; 02081 stat=(JOIN_TAB*) join->thd->calloc(sizeof(JOIN_TAB)*table_count); 02082 stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES); 02083 table_vector=(TABLE**) join->thd->alloc(sizeof(TABLE*)*(table_count*2)); 02084 if (!stat || !stat_ref || !table_vector) 02085 DBUG_RETURN(1); // Eom /* purecov: inspected */ 02086 02087 join->best_ref=stat_vector; 02088 02089 stat_end=stat+table_count; 02090 found_const_table_map= all_table_map=0; 02091 const_count=0; 02092 02093 for (s= stat, i= 0; 02094 tables; 02095 s++, tables= tables->next_leaf, i++) 02096 { 02097 TABLE_LIST *embedding= tables->embedding; 02098 stat_vector[i]=s; 02099 s->keys.init(); 02100 s->const_keys.init(); 02101 s->checked_keys.init(); 02102 s->needed_reg.init(); 02103 table_vector[i]=s->table=table=tables->table; 02104 table->pos_in_table_list= tables; 02105 table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);// record count 02106 table->quick_keys.clear_all(); 02107 table->reginfo.join_tab=s; 02108 table->reginfo.not_exists_optimize=0; 02109 bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->s->keys); 02110 all_table_map|= table->map; 02111 s->join=join; 02112 s->info=0; // For describe 02113 02114 s->dependent= tables->dep_tables; 02115 s->key_dependent= 0; 02116 if (tables->schema_table) 02117 table->file->stats.records= 2; 02118 table->quick_condition_rows= table->file->records(); 02119 02120 s->on_expr_ref= &tables->on_expr; 02121 if (*s->on_expr_ref) 02122 { 02123 /* s is the only inner table of an outer join */ 02124 #ifdef WITH_PARTITION_STORAGE_ENGINE 02125 if ((!table->file->stats.records || table->no_partitions_used) && !embedding) 02126 #else 02127 if (!table->file->stats.records && !embedding) 02128 #endif 02129 { // Empty table 02130 s->dependent= 0; // Ignore LEFT JOIN depend. 02131 set_position(join,const_count++,s,(KEYUSE*) 0); 02132 continue; 02133 } 02134 outer_join|= table->map; 02135 s->embedding_map= 0; 02136 for (;embedding; embedding= embedding->embedding) 02137 s->embedding_map|= embedding->nested_join->nj_map; 02138 continue; 02139 } 02140 if (embedding) 02141 { 02142 /* s belongs to a nested join, maybe to several embedded joins */ 02143 s->embedding_map= 0; 02144 do 02145 { 02146 NESTED_JOIN *nested_join= embedding->nested_join; 02147 s->embedding_map|=nested_join->nj_map; 02148 s->dependent|= embedding->dep_tables; 02149 embedding= embedding->embedding; 02150 outer_join|= nested_join->used_tables; 02151 } 02152 while (embedding); 02153 continue; 02154 } 02155 #ifdef WITH_PARTITION_STORAGE_ENGINE 02156 bool no_partitions_used= table->no_partitions_used; 02157 #else 02158 const bool no_partitions_used= FALSE; 02159 #endif 02160 if ((table->s->system || table->file->stats.records <= 1 || 02161 no_partitions_used) && 02162 !s->dependent && 02163 (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && 02164 !table->fulltext_searched) 02165 { 02166 set_position(join,const_count++,s,(KEYUSE*) 0); 02167 } 02168 } 02169 stat_vector[i]=0; 02170 join->outer_join=outer_join; 02171 02172 if (join->outer_join) 02173 { 02174 /* 02175 Build transitive closure for relation 'to be dependent on'. 02176 This will speed up the plan search for many cases with outer joins, 02177 as well as allow us to catch illegal cross references/ 02178 Warshall's algorithm is used to build the transitive closure. 02179 As we use bitmaps to represent the relation the complexity 02180 of the algorithm is O((number of tables)^2). 02181 */ 02182 for (i= 0, s= stat ; i < table_count ; i++, s++) 02183 { 02184 for (uint j= 0 ; j < table_count ; j++) 02185 { 02186 table= stat[j].table; 02187 if (s->dependent & table->map) 02188 s->dependent |= table->reginfo.join_tab->dependent; 02189 } 02190 if (s->dependent) 02191 s->table->maybe_null= 1; 02192 } 02193 /* Catch illegal cross references for outer joins */ 02194 for (i= 0, s= stat ; i < table_count ; i++, s++) 02195 { 02196 if (s->dependent & s->table->map) 02197 { 02198 join->tables=0; // Don't use join->table 02199 my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0)); 02200 DBUG_RETURN(1); 02201 } 02202 s->key_dependent= s->dependent; 02203 } 02204 } 02205 02206 if (conds || outer_join) 02207 if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables, 02208 conds, join->cond_equal, 02209 ~outer_join, join->select_lex)) 02210 DBUG_RETURN(1); 02211 02212 /* Read tables with 0 or 1 rows (system tables) */ 02213 join->const_table_map= 0; 02214 02215 for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count; 02216 p_pos < p_end ; 02217 p_pos++) 02218 { 02219 int tmp; 02220 s= p_pos->table; 02221 s->type=JT_SYSTEM; 02222 join->const_table_map|=s->table->map; 02223 if ((tmp=join_read_const_table(s, p_pos))) 02224 { 02225 if (tmp > 0) 02226 DBUG_RETURN(1); // Fatal error 02227 } 02228 else 02229 found_const_table_map|= s->table->map; 02230 } 02231 02232 /* loop until no more const tables are found */ 02233 int ref_changed; 02234 do 02235 { 02236 ref_changed = 0; 02237 found_ref=0; 02238 02239 /* 02240 We only have to loop from stat_vector + const_count as 02241 set_position() will move all const_tables first in stat_vector 02242 */ 02243 02244 for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++) 02245 { 02246 table=s->table; 02247 if (s->dependent) // If dependent on some table 02248 { 02249 // All dep. must be constants 02250 if (s->dependent & ~(found_const_table_map)) 02251 continue; 02252 if (table->file->stats.records <= 1L && 02253 (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && 02254 !table->pos_in_table_list->embedding) 02255 { // system table 02256 int tmp= 0; 02257 s->type=JT_SYSTEM; 02258 join->const_table_map|=table->map; 02259 set_position(join,const_count++,s,(KEYUSE*) 0); 02260 if ((tmp= join_read_const_table(s, join->positions+const_count-1))) 02261 { 02262 if (tmp > 0) 02263 DBUG_RETURN(1); // Fatal error 02264 } 02265 else 02266 found_const_table_map|= table->map; 02267 continue; 02268 } 02269 } 02270 /* check if table can be read by key or table only uses const refs */ 02271 if ((keyuse=s->keyuse)) 02272 { 02273 s->type= JT_REF; 02274 while (keyuse->table == table) 02275 { 02276 start_keyuse=keyuse; 02277 key=keyuse->key; 02278 s->keys.set_bit(key); // QQ: remove this ? 02279 02280 refs=0; 02281 const_ref.clear_all(); 02282 eq_part.clear_all(); 02283 do 02284 { 02285 if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize) 02286 { 02287 if (!((~found_const_table_map) & keyuse->used_tables)) 02288 const_ref.set_bit(keyuse->keypart); 02289 else 02290 refs|=keyuse->used_tables; 02291 eq_part.set_bit(keyuse->keypart); 02292 } 02293 keyuse++; 02294 } while (keyuse->table == table && keyuse->key == key); 02295 02296 if (eq_part.is_prefix(table->key_info[key].key_parts) && 02297 ((table->key_info[key].flags & (HA_NOSAME | HA_END_SPACE_KEY)) == 02298 HA_NOSAME) && 02299 !table->fulltext_searched && 02300 !table->pos_in_table_list->embedding) 02301 { 02302 if (const_ref == eq_part) 02303 { // Found everything for ref. 02304 int tmp; 02305 ref_changed = 1; 02306 s->type= JT_CONST; 02307 join->const_table_map|=table->map; 02308 set_position(join,const_count++,s,start_keyuse); 02309 if (create_ref_for_key(join, s, start_keyuse, 02310 found_const_table_map)) 02311 DBUG_RETURN(1); 02312 if ((tmp=join_read_const_table(s, 02313 join->positions+const_count-1))) 02314 { 02315 if (tmp > 0) 02316 DBUG_RETURN(1); // Fatal error 02317 } 02318 else 02319 found_const_table_map|= table->map; 02320 break; 02321 } 02322 else 02323 found_ref|= refs; // Table is const if all refs are const 02324 } 02325 } 02326 } 02327 } 02328 } while (join->const_table_map & found_ref && ref_changed); 02329 02330 /* Calc how many (possible) matched records in each table */ 02331 02332 for (s=stat ; s < stat_end ; s++) 02333 { 02334 if (s->type == JT_SYSTEM || s->type == JT_CONST) 02335 { 02336 /* Only one matching row */ 02337 s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0; 02338 continue; 02339 } 02340 /* Approximate found rows and time to read them */ 02341 s->found_records=s->records=s->table->file->stats.records; 02342 s->read_time=(ha_rows) s->table->file->scan_time(); 02343 02344 /* 02345 Set a max range of how many seeks we can expect when using keys 02346 This is can't be to high as otherwise we are likely to use 02347 table scan. 02348 */ 02349 s->worst_seeks= min((double) s->found_records / 10, 02350 (double) s->read_time*3); 02351 if (s->worst_seeks < 2.0) // Fix for small tables 02352 s->worst_seeks=2.0; 02353 02354 /* 02355 Add to stat->const_keys those indexes for which all group fields or 02356 all select distinct fields participate in one index. 02357 */ 02358 add_group_and_distinct_keys(join, s); 02359 02360 if (!s->const_keys.is_clear_all() && 02361 !s->table->pos_in_table_list->embedding) 02362 { 02363 ha_rows records; 02364 SQL_SELECT *select; 02365 select= make_select(s->table, found_const_table_map, 02366 found_const_table_map, 02367 *s->on_expr_ref ? *s->on_expr_ref : conds, 02368 1, &error); 02369 if (!select) 02370 DBUG_RETURN(1); 02371 records= get_quick_record_count(join->thd, select, s->table, 02372 &s->const_keys, join->row_limit); 02373 s->quick=select->quick; 02374 s->needed_reg=select->needed_reg; 02375 select->quick=0; 02376 if (records == 0 && s->table->reginfo.impossible_range) 02377 { 02378 /* 02379 Impossible WHERE or ON expression 02380 In case of ON, we mark that the we match one empty NULL row. 02381 In case of WHERE, don't set found_const_table_map to get the 02382 caller to abort with a zero row result. 02383 */ 02384 join->const_table_map|= s->table->map; 02385 set_position(join,const_count++,s,(KEYUSE*) 0); 02386 s->type= JT_CONST; 02387 if (*s->on_expr_ref) 02388 { 02389 /* Generate empty row */ 02390 s->info= "Impossible ON condition"; 02391 found_const_table_map|= s->table->map; 02392 s->type= JT_CONST; 02393 mark_as_null_row(s->table); // All fields are NULL 02394 } 02395 } 02396 if (records != HA_POS_ERROR) 02397 { 02398 s->found_records=records; 02399 s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0); 02400 } 02401 delete select; 02402 } 02403 } 02404 02405 join->join_tab=stat; 02406 join->map2table=stat_ref; 02407 join->table= join->all_tables=table_vector; 02408 join->const_tables=const_count; 02409 join->found_const_table_map=found_const_table_map; 02410 02411 /* Find an optimal join order of the non-constant tables. */ 02412 if (join->const_tables != join->tables) 02413 { 02414 optimize_keyuse(join, keyuse_array); 02415 choose_plan(join, all_table_map & ~join->const_table_map); 02416 } 02417 else 02418 { 02419 memcpy((gptr) join->best_positions,(gptr) join->positions, 02420 sizeof(POSITION)*join->const_tables); 02421 join->best_read=1.0; 02422 } 02423 /* Generate an execution plan from the found optimal join order. */ 02424 DBUG_RETURN(join->thd->killed || get_best_combination(join)); 02425 } 02426 02427 02428 /***************************************************************************** 02429 Check with keys are used and with tables references with tables 02430 Updates in stat: 02431 keys Bitmap of all used keys 02432 const_keys Bitmap of all keys with may be used with quick_select 02433 keyuse Pointer to possible keys 02434 *****************************************************************************/ 02435 02436 typedef struct key_field_t { // Used when finding key fields 02437 Field *field; 02438 Item *val; // May be empty if diff constant 02439 uint level; 02440 uint optimize; 02441 bool eq_func; 02442 /* 02443 If true, the condition this struct represents will not be satisfied 02444 when val IS NULL. 02445 */ 02446 bool null_rejecting; 02447 } KEY_FIELD; 02448 02449 /* Values in optimize */ 02450 #define KEY_OPTIMIZE_EXISTS 1 02451 #define KEY_OPTIMIZE_REF_OR_NULL 2 02452 02453 /* 02454 Merge new key definitions to old ones, remove those not used in both 02455 02456 This is called for OR between different levels 02457 02458 To be able to do 'ref_or_null' we merge a comparison of a column 02459 and 'column IS NULL' to one test. This is useful for sub select queries 02460 that are internally transformed to something like: 02461 02462 SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL 02463 02464 KEY_FIELD::null_rejecting is processed as follows: 02465 result has null_rejecting=true if it is set for both ORed references. 02466 for example: 02467 (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true 02468 (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false 02469 */ 02470 02471 static KEY_FIELD * 02472 merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end, 02473 uint and_level) 02474 { 02475 if (start == new_fields) 02476 return start; // Impossible or 02477 if (new_fields == end) 02478 return start; // No new fields, skip all 02479 02480 KEY_FIELD *first_free=new_fields; 02481 02482 /* Mark all found fields in old array */ 02483 for (; new_fields != end ; new_fields++) 02484 { 02485 for (KEY_FIELD *old=start ; old != first_free ; old++) 02486 { 02487 if (old->field == new_fields->field) 02488 { 02489 /* 02490 NOTE: below const_item() call really works as "!used_tables()", i.e. 02491 it can return FALSE where it is feasible to make it return TRUE. 02492 02493 The cause is as follows: Some of the tables are already known to be 02494 const tables (the detection code is in make_join_statistics(), 02495 above the update_ref_and_keys() call), but we didn't propagate 02496 information about this: TABLE::const_table is not set to TRUE, and 02497 Item::update_used_tables() hasn't been called for each item. 02498 The result of this is that we're missing some 'ref' accesses. 02499 TODO: OptimizerTeam: Fix this 02500 */ 02501 if (!new_fields->val->const_item()) 02502 { 02503 /* 02504 If the value matches, we can use the key reference. 02505 If not, we keep it until we have examined all new values 02506 */ 02507 if (old->val->eq(new_fields->val, old->field->binary())) 02508 { 02509 old->level= and_level; 02510 old->optimize= ((old->optimize & new_fields->optimize & 02511 KEY_OPTIMIZE_EXISTS) | 02512 ((old->optimize | new_fields->optimize) & 02513 KEY_OPTIMIZE_REF_OR_NULL)); 02514 old->null_rejecting= (old->null_rejecting && 02515 new_fields->null_rejecting); 02516 } 02517 } 02518 else if (old->eq_func && new_fields->eq_func && 02519 old->val->eq(new_fields->val, old->field->binary())) 02520 02521 { 02522 old->level= and_level; 02523 old->optimize= ((old->optimize & new_fields->optimize & 02524 KEY_OPTIMIZE_EXISTS) | 02525 ((old->optimize | new_fields->optimize) & 02526 KEY_OPTIMIZE_REF_OR_NULL)); 02527 old->null_rejecting= (old->null_rejecting && 02528 new_fields->null_rejecting); 02529 } 02530 else if (old->eq_func && new_fields->eq_func && 02531 ((old->val->const_item() && old->val->is_null()) || 02532 new_fields->val->is_null())) 02533 { 02534 /* field = expression OR field IS NULL */ 02535 old->level= and_level; 02536 old->optimize= KEY_OPTIMIZE_REF_OR_NULL; 02537 /* 02538 Remember the NOT NULL value unless the value does not depend 02539 on other tables. 02540 */ 02541 if (!old->val->used_tables() && old->val->is_null()) 02542 old->val= new_fields->val; 02543 /* The referred expression can be NULL: */ 02544 old->null_rejecting= 0; 02545 } 02546 else 02547 { 02548 /* 02549 We are comparing two different const. In this case we can't 02550 use a key-lookup on this so it's better to remove the value 02551 and let the range optimzier handle it 02552 */ 02553 if (old == --first_free) // If last item 02554 break; 02555 *old= *first_free; // Remove old value 02556 old--; // Retry this value 02557 } 02558 } 02559 } 02560 } 02561 /* Remove all not used items */ 02562 for (KEY_FIELD *old=start ; old != first_free ;) 02563 { 02564 if (old->level != and_level) 02565 { // Not used in all levels 02566 if (old == --first_free) 02567 break; 02568 *old= *first_free; // Remove old value 02569 continue; 02570 } 02571 old++; 02572 } 02573 return first_free; 02574 } 02575 02576 02577 /* 02578 Add a possible key to array of possible keys if it's usable as a key 02579 02580 SYNPOSIS 02581 add_key_field() 02582 key_fields Pointer to add key, if usable 02583 and_level And level, to be stored in KEY_FIELD 02584 cond Condition predicate 02585 field Field used in comparision 02586 eq_func True if we used =, <=> or IS NULL 02587 value Value used for comparison with field 02588 usable_tables Tables which can be used for key optimization 02589 02590 NOTES 02591 If we are doing a NOT NULL comparison on a NOT NULL field in a outer join 02592 table, we store this to be able to do not exists optimization later. 02593 02594 RETURN 02595 *key_fields is incremented if we stored a key in the array 02596 */ 02597 02598 static void 02599 add_key_field(KEY_FIELD **key_fields,uint and_level, Item_func *cond, 02600 Field *field, bool eq_func, Item **value, uint num_values, 02601 table_map usable_tables) 02602 { 02603 uint exists_optimize= 0; 02604 if (!(field->flags & PART_KEY_FLAG)) 02605 { 02606 // Don't remove column IS NULL on a LEFT JOIN table 02607 if (!eq_func || (*value)->type() != Item::NULL_ITEM || 02608 !field->table->maybe_null || field->null_ptr) 02609 return; // Not a key. Skip it 02610 exists_optimize= KEY_OPTIMIZE_EXISTS; 02611 DBUG_ASSERT(num_values == 1); 02612 } 02613 else 02614 { 02615 table_map used_tables=0; 02616 bool optimizable=0; 02617 for (uint i=0; i<num_values; i++) 02618 { 02619 used_tables|=(value[i])->used_tables(); 02620 if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT))) 02621 optimizable=1; 02622 } 02623 if (!optimizable) 02624 return; 02625 if (!(usable_tables & field->table->map)) 02626 { 02627 if (!eq_func || (*value)->type() != Item::NULL_ITEM || 02628 !field->table->maybe_null || field->null_ptr) 02629 return; // Can't use left join optimize 02630 exists_optimize= KEY_OPTIMIZE_EXISTS; 02631 } 02632 else 02633 { 02634 JOIN_TAB *stat=field->table->reginfo.join_tab; 02635 key_map possible_keys=field->key_start; 02636 possible_keys.intersect(field->table->keys_in_use_for_query); 02637 stat[0].keys.merge(possible_keys); // Add possible keys 02638 02639 /* 02640 Save the following cases: 02641 Field op constant 02642 Field LIKE constant where constant doesn't start with a wildcard 02643 Field = field2 where field2 is in a different table 02644 Field op formula 02645 Field IS NULL 02646 Field IS NOT NULL 02647 Field BETWEEN ... 02648 Field IN ... 02649 */ 02650 stat[0].key_dependent|=used_tables; 02651 02652 bool is_const=1; 02653 for (uint i=0; i<num_values; i++) 02654 { 02655 if (!(is_const&= value[i]->const_item())) 02656 break; 02657 } 02658 if (is_const) 02659 stat[0].const_keys.merge(possible_keys); 02660 /* 02661 We can't always use indexes when comparing a string index to a 02662 number. cmp_type() is checked to allow compare of dates to numbers. 02663 eq_func is NEVER true when num_values > 1 02664 */ 02665 if (!eq_func) 02666 { 02667 /* 02668 Additional optimization: if we're processing 02669 "t.key BETWEEN c1 AND c1" then proceed as if we were processing 02670 "t.key = c1". 02671 TODO: This is a very limited fix. A more generic fix is possible. 02672 There are 2 options: 02673 A) Make equality propagation code be able to handle BETWEEN 02674 (including cases like t1.key BETWEEN t2.key AND t3.key) 02675 B) Make range optimizer to infer additional "t.key = c" equalities 02676 and use them in equality propagation process (see details in 02677 OptimizerKBAndTodo) 02678 */ 02679 if ((cond->functype() != Item_func::BETWEEN) || 02680 ((Item_func_between*) cond)->negated || 02681 !value[0]->eq(value[1], field->binary())) 02682 return; 02683 eq_func= TRUE; 02684 } 02685 02686 if (field->result_type() == STRING_RESULT) 02687 { 02688 if ((*value)->result_type() != STRING_RESULT) 02689 { 02690 if (field->cmp_type() != (*value)->result_type()) 02691 return; 02692 } 02693 else 02694 { 02695 /* 02696 We can't use indexes if the effective collation 02697 of the operation differ from the field collation. 02698 02699 We also cannot use index on a text column, as the column may 02700 contain 'x' 'x\t' 'x ' and 'read_next_same' will stop after 02701 'x' when searching for WHERE col='x ' 02702 */ 02703 if (field->cmp_type() == STRING_RESULT && 02704 (((Field_str*)field)->charset() != cond->compare_collation() || 02705 ((*value)->type() != Item::NULL_ITEM && 02706 (field->flags & BLOB_FLAG) && !field->binary()))) 02707 return; 02708 } 02709 } 02710 } 02711 } 02712 /* 02713 For the moment eq_func is always true. This slot is reserved for future 02714 extensions where we want to remembers other things than just eq comparisons 02715 */ 02716 DBUG_ASSERT(eq_func); 02717 /* Store possible eq field */ 02718 (*key_fields)->field= field; 02719 (*key_fields)->eq_func= eq_func; 02720 (*key_fields)->val= *value; 02721 (*key_fields)->level= and_level; 02722 (*key_fields)->optimize= exists_optimize; 02723 /* 02724 If the condition has form "tbl.keypart = othertbl.field" and 02725 othertbl.field can be NULL, there will be no matches if othertbl.field 02726 has NULL value. 02727 We use null_rejecting in add_not_null_conds() to add 02728 'othertbl.field IS NOT NULL' to tab->select_cond. 02729 */ 02730 (*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC) && 02731 ((*value)->type() == Item::FIELD_ITEM) && 02732 ((Item_field*)*value)->field->maybe_null()); 02733 (*key_fields)++; 02734 } 02735 02736 /* 02737 Add possible keys to array of possible keys originated from a simple predicate 02738 02739 SYNPOSIS 02740 add_key_equal_fields() 02741 key_fields Pointer to add key, if usable 02742 and_level And level, to be stored in KEY_FIELD 02743 cond Condition predicate 02744 field Field used in comparision 02745 eq_func True if we used =, <=> or IS NULL 02746 value Value used for comparison with field 02747 Is NULL for BETWEEN and IN 02748 usable_tables Tables which can be used for key optimization 02749 02750 NOTES 02751 If field items f1 and f2 belong to the same multiple equality and 02752 a key is added for f1, the the same key is added for f2. 02753 02754 RETURN 02755 *key_fields is incremented if we stored a key in the array 02756 */ 02757 02758 static void 02759 add_key_equal_fields(KEY_FIELD **key_fields, uint and_level, 02760 Item_func *cond, Item_field *field_item, 02761 bool eq_func, Item **val, 02762 uint num_values, table_map usable_tables) 02763 { 02764 Field *field= field_item->field; 02765 add_key_field(key_fields, and_level, cond, field, 02766 eq_func, val, num_values, usable_tables); 02767 Item_equal *item_equal= field_item->item_equal; 02768 if (item_equal) 02769 { 02770 /* 02771 Add to the set of possible key values every substitution of 02772 the field for an equal field included into item_equal 02773 */ 02774 Item_equal_iterator it(*item_equal); 02775 Item_field *item; 02776 while ((item= it++)) 02777 { 02778 if (!field->eq(item->field)) 02779 { 02780 add_key_field(key_fields, and_level, cond, item->field, 02781 eq_func, val, num_values, usable_tables); 02782 } 02783 } 02784 } 02785 } 02786 02787 static void 02788 add_key_fields(KEY_FIELD **key_fields,uint *and_level, 02789 COND *cond, table_map usable_tables) 02790 { 02791 if (cond->type() == Item_func::COND_ITEM) 02792 { 02793 List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list()); 02794 KEY_FIELD *org_key_fields= *key_fields; 02795 02796 if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC) 02797 { 02798 Item *item; 02799 while ((item=li++)) 02800 add_key_fields(key_fields,and_level,item,usable_tables); 02801 for (; org_key_fields != *key_fields ; org_key_fields++) 02802 org_key_fields->level= *and_level; 02803 } 02804 else 02805 { 02806 (*and_level)++; 02807 add_key_fields(key_fields,and_level,li++,usable_tables); 02808 Item *item; 02809 while ((item=li++)) 02810 { 02811 KEY_FIELD *start_key_fields= *key_fields; 02812 (*and_level)++; 02813 add_key_fields(key_fields,and_level,item,usable_tables); 02814 *key_fields=merge_key_fields(org_key_fields,start_key_fields, 02815 *key_fields,++(*and_level)); 02816 } 02817 } 02818 return; 02819 } 02820 /* If item is of type 'field op field/constant' add it to key_fields */ 02821 02822 if (cond->type() != Item::FUNC_ITEM) 02823 return; 02824 Item_func *cond_func= (Item_func*) cond; 02825 switch (cond_func->select_optimize()) { 02826 case Item_func::OPTIMIZE_NONE: 02827 break; 02828 case Item_func::OPTIMIZE_KEY: 02829 { 02830 // BETWEEN, IN, NE 02831 if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM && 02832 !(cond_func->used_tables() & OUTER_REF_TABLE_BIT)) 02833 { 02834 Item **values= cond_func->arguments()+1; 02835 if (cond_func->functype() == Item_func::NE_FUNC && 02836 cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM && 02837 !(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT)) 02838 values--; 02839 DBUG_ASSERT(cond_func->functype() != Item_func::IN_FUNC || 02840 cond_func->argument_count() != 2); 02841 add_key_equal_fields(key_fields, *and_level, cond_func, 02842 (Item_field*) (cond_func->key_item()->real_item()), 02843 0, values, 02844 cond_func->argument_count()-1, 02845 usable_tables); 02846 } 02847 break; 02848 } 02849 case Item_func::OPTIMIZE_OP: 02850 { 02851 bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC || 02852 cond_func->functype() == Item_func::EQUAL_FUNC); 02853 02854 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM && 02855 !(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT)) 02856 { 02857 add_key_equal_fields(key_fields, *and_level, cond_func, 02858 (Item_field*) (cond_func->arguments()[0])->real_item(), 02859 equal_func, 02860 cond_func->arguments()+1, 1, usable_tables); 02861 } 02862 if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM && 02863 cond_func->functype() != Item_func::LIKE_FUNC && 02864 !(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT)) 02865 { 02866 add_key_equal_fields(key_fields, *and_level, cond_func, 02867 (Item_field*) (cond_func->arguments()[1])->real_item(), 02868 equal_func, 02869 cond_func->arguments(),1,usable_tables); 02870 } 02871 break; 02872 } 02873 case Item_func::OPTIMIZE_NULL: 02874 /* column_name IS [NOT] NULL */ 02875 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM && 02876 !(cond_func->used_tables() & OUTER_REF_TABLE_BIT)) 02877 { 02878 Item *tmp=new Item_null; 02879 if (unlikely(!tmp)) // Should never be true 02880 return; 02881 add_key_equal_fields(key_fields, *and_level, cond_func, 02882 (Item_field*) (cond_func->arguments()[0])->real_item(), 02883 cond_func->functype() == Item_func::ISNULL_FUNC, 02884 &tmp, 1, usable_tables); 02885 } 02886 break; 02887 case Item_func::OPTIMIZE_EQUAL: 02888 Item_equal *item_equal= (Item_equal *) cond; 02889 Item *const_item= item_equal->get_const(); 02890 Item_equal_iterator it(*item_equal); 02891 Item_field *item; 02892 if (const_item) 02893 { 02894 /* 02895 For each field field1 from item_equal consider the equality 02896 field1=const_item as a condition allowing an index access of the table 02897 with field1 by the keys value of field1. 02898 */ 02899 while ((item= it++)) 02900 { 02901 add_key_field(key_fields, *and_level, cond_func, item->field, 02902 TRUE, &const_item, 1, usable_tables); 02903 } 02904 } 02905 else 02906 { 02907 /* 02908 Consider all pairs of different fields included into item_equal. 02909 For each of them (field1, field1) consider the equality 02910 field1=field2 as a condition allowing an index access of the table 02911 with field1 by the keys value of field2. 02912 */ 02913 Item_equal_iterator fi(*item_equal); 02914 while ((item= fi++)) 02915 { 02916 Field *field= item->field; 02917 while ((item= it++)) 02918 { 02919 if (!field->eq(item->field)) 02920 { 02921 add_key_field(key_fields, *and_level, cond_func, field, 02922 TRUE, (Item **) &item, 1, usable_tables); 02923 } 02924 } 02925 it.rewind(); 02926 } 02927 } 02928 break; 02929 } 02930 } 02931 02932 /* 02933 Add all keys with uses 'field' for some keypart 02934 If field->and_level != and_level then only mark key_part as const_part 02935 */ 02936 02937 static uint 02938 max_part_bit(key_part_map bits) 02939 { 02940 uint found; 02941 for (found=0; bits & 1 ; found++,bits>>=1) ; 02942 return found; 02943 } 02944 02945 static void 02946 add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field) 02947 { 02948 Field *field=key_field->field; 02949 TABLE *form= field->table; 02950 KEYUSE keyuse; 02951 02952 if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS)) 02953 { 02954 for (uint key=0 ; key < form->s->keys ; key++) 02955 { 02956 if (!(form->keys_in_use_for_query.is_set(key))) 02957 continue; 02958 if (form->key_info[key].flags & HA_FULLTEXT) 02959 continue; // ToDo: ft-keys in non-ft queries. SerG 02960 02961 uint key_parts= (uint) form->key_info[key].key_parts; 02962 for (uint part=0 ; part < key_parts ; part++) 02963 { 02964 if (field->eq(form->key_info[key].key_part[part].field)) 02965 { 02966 keyuse.table= field->table; 02967 keyuse.val = key_field->val; 02968 keyuse.key = key; 02969 keyuse.keypart=part; 02970 keyuse.keypart_map= (key_part_map) 1 << part; 02971 keyuse.used_tables=key_field->val->used_tables(); 02972 keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL; 02973 keyuse.null_rejecting= key_field->null_rejecting; 02974 VOID(insert_dynamic(keyuse_array,(gptr) &keyuse)); 02975 } 02976 } 02977 } 02978 } 02979 } 02980 02981 02982 #define FT_KEYPART (MAX_REF_PARTS+10) 02983 02984 static void 02985 add_ft_keys(DYNAMIC_ARRAY *keyuse_array, 02986 JOIN_TAB *stat,COND *cond,table_map usable_tables) 02987 { 02988 Item_func_match *cond_func=NULL; 02989 02990 if (!cond) 02991 return; 02992 02993 if (cond->type() == Item::FUNC_ITEM) 02994 { 02995 Item_func *func=(Item_func *)cond; 02996 Item_func::Functype functype= func->functype(); 02997 if (functype == Item_func::FT_FUNC) 02998 cond_func=(Item_func_match *)cond; 02999 else if (func->arg_count == 2) 03000 { 03001 Item_func *arg0=(Item_func *)(func->arguments()[0]), 03002 *arg1=(Item_func *)(func->arguments()[1]); 03003 if (arg1->const_item() && 03004 ((functype == Item_func::GE_FUNC && arg1->val_real() > 0) || 03005 (functype == Item_func::GT_FUNC && arg1->val_real() >=0)) && 03006 arg0->type() == Item::FUNC_ITEM && 03007 arg0->functype() == Item_func::FT_FUNC) 03008 cond_func=(Item_func_match *) arg0; 03009 else if (arg0->const_item() && 03010 ((functype == Item_func::LE_FUNC && arg0->val_real() > 0) || 03011 (functype == Item_func::LT_FUNC && arg0->val_real() >=0)) && 03012 arg1->type() == Item::FUNC_ITEM && 03013 arg1->functype() == Item_func::FT_FUNC) 03014 cond_func=(Item_func_match *) arg1; 03015 } 03016 } 03017 else if (cond->type() == Item::COND_ITEM) 03018 { 03019 List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list()); 03020 03021 if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC) 03022 { 03023 Item *item; 03024 while ((item=li++)) 03025 add_ft_keys(keyuse_array,stat,item,usable_tables); 03026 } 03027 } 03028 03029 if (!cond_func || cond_func->key == NO_SUCH_KEY || 03030 !(usable_tables & cond_func->table->map)) 03031 return; 03032 03033 KEYUSE keyuse; 03034 keyuse.table= cond_func->table; 03035 keyuse.val = cond_func; 03036 keyuse.key = cond_func->key; 03037 keyuse.keypart= FT_KEYPART; 03038 keyuse.used_tables=cond_func->key_item()->used_tables(); 03039 keyuse.optimize= 0; 03040 keyuse.keypart_map= 0; 03041 VOID(insert_dynamic(keyuse_array,(gptr) &keyuse)); 03042 } 03043 03044 03045 static int 03046 sort_keyuse(KEYUSE *a,KEYUSE *b) 03047 { 03048 int res; 03049 if (a->table->tablenr != b->table->tablenr) 03050 return (int) (a->table->tablenr - b->table->tablenr); 03051 if (a->key != b->key) 03052 return (int) (a->key - b->key); 03053 if (a->keypart != b->keypart) 03054 return (int) (a->keypart - b->keypart); 03055 // Place const values before other ones 03056 if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) - 03057 test((b->used_tables & ~OUTER_REF_TABLE_BIT)))) 03058 return res; 03059 /* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */ 03060 return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) - 03061 (b->optimize & KEY_OPTIMIZE_REF_OR_NULL)); 03062 } 03063 03064 03065 /* 03066 Add to KEY_FIELD array all 'ref' access candidates within nested join 03067 03068 SYNPOSIS 03069 add_key_fields_for_nj() 03070 nested_join_table IN Nested join pseudo-table to process 03071 end INOUT End of the key field array 03072 and_level INOUT And-level 03073 03074 DESCRIPTION 03075 This function populates KEY_FIELD array with entries generated from the 03076 ON condition of the given nested join, and does the same for nested joins 03077 contained within this nested join. 03078 03079 NOTES 03080 We can add accesses to the tables that are direct children of this nested 03081 join (1), and are not inner tables w.r.t their neighbours (2). 03082 03083 Example for #1 (outer brackets pair denotes nested join this function is 03084 invoked for): 03085 ... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond 03086 Example for #2: 03087 ... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond 03088 In examples 1-2 for condition cond, we can add 'ref' access candidates to 03089 t1 only. 03090 Example #3: 03091 ... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond 03092 Here we can add 'ref' access candidates for t1 and t2, but not for t3. 03093 */ 03094 03095 static void add_key_fields_for_nj(TABLE_LIST *nested_join_table, 03096 KEY_FIELD **end, uint *and_level) 03097 { 03098 List_iterator<TABLE_LIST> li(nested_join_table->nested_join->join_list); 03099 table_map tables= 0; 03100 TABLE_LIST *table; 03101 DBUG_ASSERT(nested_join_table->nested_join); 03102 03103 while ((table= li++)) 03104 { 03105 if (table->nested_join) 03106 add_key_fields_for_nj(table, end, and_level); 03107 else 03108 if (!table->on_expr) 03109 tables |= table->table->map; 03110 } 03111 add_key_fields(end, and_level, nested_join_table->on_expr, tables); 03112 } 03113 03114 03115 /* 03116 Update keyuse array with all possible keys we can use to fetch rows 03117 03118 SYNOPSIS 03119 update_ref_and_keys() 03120 thd 03121 keyuse OUT Put here ordered array of KEYUSE structures 03122 join_tab Array in tablenr_order 03123 tables Number of tables in join 03124 cond WHERE condition (note that the function analyzes 03125 join_tab[i]->on_expr too) 03126 normal_tables tables not inner w.r.t some outer join (ones for which 03127 we can make ref access based the WHERE clause) 03128 select_lex current SELECT 03129 03130 RETURN 03131 0 - OK 03132 1 - Out of memory. 03133 */ 03134 03135 static bool 03136 update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab, 03137 uint tables, COND *cond, COND_EQUAL *cond_equal, 03138 table_map normal_tables, SELECT_LEX *select_lex) 03139 { 03140 uint and_level,i,found_eq_constant; 03141 KEY_FIELD *key_fields, *end, *field; 03142 uint m= 1; 03143 03144 if (cond_equal && cond_equal->max_members) 03145 m= cond_equal->max_members; 03146 03147 if (!(key_fields=(KEY_FIELD*) 03148 thd->alloc(sizeof(key_fields[0])* 03149 (thd->lex->current_select->cond_count+1)*2*m))) 03150 return TRUE; /* purecov: inspected */ 03151 and_level= 0; 03152 field= end= key_fields; 03153 if (my_init_dynamic_array(keyuse,sizeof(KEYUSE),20,64)) 03154 return TRUE; 03155 if (cond) 03156 { 03157 add_key_fields(&end,&and_level,cond,normal_tables); 03158 for (; field != end ; field++) 03159 { 03160 add_key_part(keyuse,field); 03161 /* Mark that we can optimize LEFT JOIN */ 03162 if (field->val->type() == Item::NULL_ITEM && 03163 !field->field->real_maybe_null()) 03164 field->field->table->reginfo.not_exists_optimize=1; 03165 } 03166 } 03167 for (i=0 ; i < tables ; i++) 03168 { 03169 /* 03170 Block the creation of keys for inner tables of outer joins. 03171 Here only the outer joins that can not be converted to 03172 inner joins are left and all nests that can be eliminated 03173 are flattened. 03174 In the future when we introduce conditional accesses 03175 for inner tables in outer joins these keys will be taken 03176 into account as well. 03177 */ 03178 if (*join_tab[i].on_expr_ref) 03179 add_key_fields(&end,&and_level,*join_tab[i].on_expr_ref, 03180 join_tab[i].table->map); 03181 } 03182 03183 /* Process ON conditions for the nested joins */ 03184 { 03185 List_iterator<TABLE_LIST> li(*join_tab->join->join_list); 03186 TABLE_LIST *table; 03187 while ((table= li++)) 03188 { 03189 if (table->nested_join) 03190 add_key_fields_for_nj(table, &end, &and_level); 03191 } 03192 } 03193 03194 /* fill keyuse with found key parts */ 03195 for ( ; field != end ; field++) 03196 add_key_part(keyuse,field); 03197 03198 if (select_lex->ftfunc_list->elements) 03199 { 03200 add_ft_keys(keyuse,join_tab,cond,normal_tables); 03201 } 03202 03203 /* 03204 Sort the array of possible keys and remove the following key parts: 03205 - ref if there is a keypart which is a ref and a const. 03206 (e.g. if there is a key(a,b) and the clause is a=3 and b=7 and b=t2.d, 03207 then we skip the key part corresponding to b=t2.d) 03208 - keyparts without previous keyparts 03209 (e.g. if there is a key(a,b,c) but only b < 5 (or a=2 and c < 3) is 03210 used in the query, we drop the partial key parts from consideration). 03211 Special treatment for ft-keys. 03212 */ 03213 if (keyuse->elements) 03214 { 03215 KEYUSE end,*prev,*save_pos,*use; 03216 03217 qsort(keyuse->buffer,keyuse->elements,sizeof(KEYUSE), 03218 (qsort_cmp) sort_keyuse); 03219 03220 bzero((char*) &end,sizeof(end)); /* Add for easy testing */ 03221 VOID(insert_dynamic(keyuse,(gptr) &end)); 03222 03223 use=save_pos=dynamic_element(keyuse,0,KEYUSE*); 03224 prev=&end; 03225 found_eq_constant=0; 03226 for (i=0 ; i < keyuse->elements-1 ; i++,use++) 03227 { 03228 if (!use->used_tables) 03229 use->table->const_key_parts[use->key]|= use->keypart_map; 03230 if (use->keypart != FT_KEYPART) 03231 { 03232 if (use->key == prev->key && use->table == prev->table) 03233 { 03234 if (prev->keypart+1 < use->keypart || 03235 prev->keypart == use->keypart && found_eq_constant) 03236 continue; /* remove */ 03237 } 03238 else if (use->keypart != 0) // First found must be 0 03239 continue; 03240 } 03241 03242 *save_pos= *use; 03243 prev=use; 03244 found_eq_constant= !use->used_tables; 03245 /* Save ptr to first use */ 03246 if (!use->table->reginfo.join_tab->keyuse) 03247 use->table->reginfo.join_tab->keyuse=save_pos; 03248 use->table->reginfo.join_tab->checked_keys.set_bit(use->key); 03249 save_pos++; 03250 } 03251 i=(uint) (save_pos-(KEYUSE*) keyuse->buffer); 03252 VOID(set_dynamic(keyuse,(gptr) &end,i)); 03253 keyuse->elements=i; 03254 } 03255 return FALSE; 03256 } 03257 03258 /* 03259 Update some values in keyuse for faster choose_plan() loop 03260 */ 03261 03262 static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array) 03263 { 03264 KEYUSE *end,*keyuse= dynamic_element(keyuse_array, 0, KEYUSE*); 03265 03266 for (end= keyuse+ keyuse_array->elements ; keyuse < end ; keyuse++) 03267 { 03268 table_map map; 03269 /* 03270 If we find a ref, assume this table matches a proportional 03271 part of this table. 03272 For example 100 records matching a table with 5000 records 03273 gives 5000/100 = 50 records per key 03274 Constant tables are ignored. 03275 To avoid bad matches, we don't make ref_table_rows less than 100. 03276 */ 03277 keyuse->ref_table_rows= ~(ha_rows) 0; // If no ref 03278 if (keyuse->used_tables & 03279 (map= (keyuse->used_tables & ~join->const_table_map & 03280 ~OUTER_REF_TABLE_BIT))) 03281 { 03282 uint tablenr; 03283 for (tablenr=0 ; ! (map & 1) ; map>>=1, tablenr++) ; 03284 if (map == 1) // Only one table 03285 { 03286 TABLE *tmp_table=join->all_tables[tablenr]; 03287 keyuse->ref_table_rows= max(tmp_table->file->stats.records, 100); 03288 } 03289 } 03290 /* 03291 Outer reference (external field) is constant for single executing 03292 of subquery 03293 */ 03294 if (keyuse->used_tables == OUTER_REF_TABLE_BIT) 03295 keyuse->ref_table_rows= 1; 03296 } 03297 } 03298 03299 03300 /* 03301 Discover the indexes that can be used for GROUP BY or DISTINCT queries. 03302 03303 SYNOPSIS 03304 add_group_and_distinct_keys() 03305 join 03306 join_tab 03307 03308 DESCRIPTION 03309 If the query has a GROUP BY clause, find all indexes that contain all 03310 GROUP BY fields, and add those indexes to join->const_keys. 03311 If the query has a DISTINCT clause, find all indexes that contain all 03312 SELECT fields, and add those indexes to join->const_keys. 03313 This allows later on such queries to be processed by a 03314 QUICK_GROUP_MIN_MAX_SELECT. 03315 03316 RETURN 03317 None 03318 */ 03319 03320 static void 03321 add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab) 03322 { 03323 List<Item_field> indexed_fields; 03324 List_iterator<Item_field> indexed_fields_it(indexed_fields); 03325 ORDER *cur_group; 03326 Item_field *cur_item; 03327 key_map possible_keys(0); 03328 03329 if (join->group_list) 03330 { /* Collect all query fields referenced in the GROUP clause. */ 03331 for (cur_group= join->group_list; cur_group; cur_group= cur_group->next) 03332 (*cur_group->item)->walk(&Item::collect_item_field_processor, 0, 03333 (byte*) &indexed_fields); 03334 } 03335 else if (join->select_distinct) 03336 { /* Collect all query fields referenced in the SELECT clause. */ 03337 List<Item> &select_items= join->fields_list; 03338 List_iterator<Item> select_items_it(select_items); 03339 Item *item; 03340 while ((item= select_items_it++)) 03341 item->walk(&Item::collect_item_field_processor, 0, 03342 (byte*) &indexed_fields); 03343 } 03344 else 03345 return; 03346 03347 if (indexed_fields.elements == 0) 03348 return; 03349 03350 /* Intersect the keys of all group fields. */ 03351 cur_item= indexed_fields_it++; 03352 possible_keys.merge(cur_item->field->part_of_key); 03353 while ((cur_item= indexed_fields_it++)) 03354 { 03355 possible_keys.intersect(cur_item->field->part_of_key); 03356 } 03357 03358 if (!possible_keys.is_clear_all()) 03359 join_tab->const_keys.merge(possible_keys); 03360 } 03361 03362 03363 /***************************************************************************** 03364 Go through all combinations of not marked tables and find the one 03365 which uses least records 03366 *****************************************************************************/ 03367 03368 /* Save const tables first as used tables */ 03369 03370 static void 03371 set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key) 03372 { 03373 join->positions[idx].table= table; 03374 join->positions[idx].key=key; 03375 join->positions[idx].records_read=1.0; /* This is a const table */ 03376 03377 /* Move the const table as down as possible in best_ref */ 03378 JOIN_TAB **pos=join->best_ref+idx+1; 03379 JOIN_TAB *next=join->best_ref[idx]; 03380 for (;next != table ; pos++) 03381 { 03382 JOIN_TAB *tmp=pos[0]; 03383 pos[0]=next; 03384 next=tmp; 03385 } 03386 join->best_ref[idx]=table; 03387 } 03388 03389 03390 /* 03391 Find the best access path for an extension of a partial execution plan and 03392 add this path to the plan. 03393 03394 SYNOPSIS 03395 best_access_path() 03396 join pointer to the structure providing all context info 03397 for the query 03398 s the table to be joined by the function 03399 thd thread for the connection that submitted the query 03400 remaining_tables set of tables not included into the partial plan yet 03401 idx the length of the partial plan 03402 record_count estimate for the number of records returned by the partial 03403 plan 03404 read_time the cost of the partial plan 03405 03406 DESCRIPTION 03407 The function finds the best access path to table 's' from the passed 03408 partial plan where an access path is the general term for any means to 03409 access the data in 's'. An access path may use either an index or a scan, 03410 whichever is cheaper. The input partial plan is passed via the array 03411 'join->positions' of length 'idx'. The chosen access method for 's' and its 03412 cost are stored in 'join->positions[idx]'. 03413 03414 RETURN 03415 None 03416 */ 03417 03418 static void 03419 best_access_path(JOIN *join, 03420 JOIN_TAB *s, 03421 THD *thd, 03422 table_map remaining_tables, 03423 uint idx, 03424 double record_count, 03425 double read_time) 03426 { 03427 KEYUSE *best_key= 0; 03428 uint best_max_key_part= 0; 03429 my_bool found_constraint= 0; 03430 double best= DBL_MAX; 03431 double best_time= DBL_MAX; 03432 double records= DBL_MAX; 03433 double tmp; 03434 ha_rows rec; 03435 03436 DBUG_ENTER("best_access_path"); 03437 03438 if (s->keyuse) 03439 { /* Use key if possible */ 03440 TABLE *table= s->table; 03441 KEYUSE *keyuse,*start_key=0; 03442 double best_records= DBL_MAX; 03443 uint max_key_part=0; 03444 03445 /* Test how we can use keys */ 03446 rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key 03447 for (keyuse=s->keyuse ; keyuse->table == table ;) 03448 { 03449 key_part_map found_part= 0; 03450 table_map found_ref= 0; 03451 uint key= keyuse->key; 03452 KEY *keyinfo= table->key_info+key; 03453 bool ft_key= (keyuse->keypart == FT_KEYPART); 03454 /* Bitmap of keyparts where the ref access is over 'keypart=const': */ 03455 key_part_map const_part= 0; 03456 /* The or-null keypart in ref-or-null access: */ 03457 key_part_map ref_or_null_part= 0; 03458 03459 /* Calculate how many key segments of the current key we can use */ 03460 start_key= keyuse; 03461 do 03462 { /* for each keypart */ 03463 uint keypart= keyuse->keypart; 03464 table_map best_part_found_ref= 0; 03465 double best_prev_record_reads= DBL_MAX; 03466 do 03467 { 03468 if (!(remaining_tables & keyuse->used_tables) && 03469 !(ref_or_null_part && (keyuse->optimize & 03470 KEY_OPTIMIZE_REF_OR_NULL))) 03471 { 03472 found_part|= keyuse->keypart_map; 03473 if (!(keyuse->used_tables & ~join->const_table_map)) 03474 const_part|= keyuse->keypart_map; 03475 double tmp= prev_record_reads(join, (found_ref | 03476 keyuse->used_tables)); 03477 if (tmp < best_prev_record_reads) 03478 { 03479 best_part_found_ref= keyuse->used_tables; 03480 best_prev_record_reads= tmp; 03481 } 03482 if (rec > keyuse->ref_table_rows) 03483 rec= keyuse->ref_table_rows; 03484 /* 03485 If there is one 'key_column IS NULL' expression, we can 03486 use this ref_or_null optimisation of this field 03487 */ 03488 if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) 03489 ref_or_null_part |= keyuse->keypart_map; 03490 } 03491 keyuse++; 03492 } while (keyuse->table == table && keyuse->key == key && 03493 keyuse->keypart == keypart); 03494 found_ref|= best_part_found_ref; 03495 } while (keyuse->table == table && keyuse->key == key); 03496 03497 /* 03498 Assume that that each key matches a proportional part of table. 03499 */ 03500 if (!found_part && !ft_key) 03501 continue; // Nothing usable found 03502 03503 if (rec < MATCHING_ROWS_IN_OTHER_TABLE) 03504 rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables 03505 03506 /* 03507 ft-keys require special treatment 03508 */ 03509 if (ft_key) 03510 { 03511 /* 03512 Really, there should be records=0.0 (yes!) 03513 but 1.0 would be probably safer 03514 */ 03515 tmp= prev_record_reads(join, found_ref); 03516 records= 1.0; 03517 } 03518 else 03519 { 03520 found_constraint= 1; 03521 /* 03522 Check if we found full key 03523 */ 03524 if (found_part == PREV_BITS(uint,keyinfo->key_parts) && 03525 !ref_or_null_part) 03526 { /* use eq key */ 03527 max_key_part= (uint) ~0; 03528 if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME) 03529 { 03530 tmp = prev_record_reads(join, found_ref); 03531 records=1.0; 03532 } 03533 else 03534 { 03535 if (!found_ref) 03536 { /* We found a const key */ 03537 /* 03538 ReuseRangeEstimateForRef-1: 03539 We get here if we've found a ref(const) (c_i are constants): 03540 "(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond] 03541 03542 If range optimizer was able to construct a "range" 03543 access on this index, then its condition "quick_cond" was 03544 eqivalent to ref_const_cond (*), and we can re-use E(#rows) 03545 from the range optimizer. 03546 03547 Proof of (*): By properties of range and ref optimizers 03548 quick_cond will be equal or tighther than ref_const_cond. 03549 ref_const_cond already covers "smallest" possible interval - 03550 a singlepoint interval over all keyparts. Therefore, 03551 quick_cond is equivalent to ref_const_cond (if it was an 03552 empty interval we wouldn't have got here). 03553 */ 03554 if (table->quick_keys.is_set(key)) 03555 records= (double) table->quick_rows[key]; 03556 else 03557 { 03558 /* quick_range couldn't use key! */ 03559 records= (double) s->records/rec; 03560 } 03561 } 03562 else 03563 { 03564 if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1])) 03565 { /* Prefer longer keys */ 03566 records= 03567 ((double) s->records / (double) rec * 03568 (1.0 + 03569 ((double) (table->s->max_key_length-keyinfo->key_length) / 03570 (double) table->s->max_key_length))); 03571 if (records < 2.0) 03572 records=2.0; /* Can't be as good as a unique */ 03573 } 03574 /* 03575 ReuseRangeEstimateForRef-2: We get here if we could not reuse 03576 E(#rows) from range optimizer. Make another try: 03577 03578 If range optimizer produced E(#rows) for a prefix of the ref 03579 access we're considering, and that E(#rows) is lower then our 03580 current estimate, make an adjustment. The criteria of when we 03581 can make an adjustment is a special case of the criteria used 03582 in ReuseRangeEstimateForRef-3. 03583 */ 03584 if (table->quick_keys.is_set(key) && 03585 const_part & (1 << table->quick_key_parts[key]) && 03586 table->quick_n_ranges[key] == 1 && 03587 records > (double) table->quick_rows[key]) 03588 { 03589 records= (double) table->quick_rows[key]; 03590 } 03591 } 03592 /* Limit the number of matched rows */ 03593 tmp= records; 03594 set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key); 03595 if (table->used_keys.is_set(key)) 03596 { 03597 /* we can use only index tree */ 03598 uint keys_per_block= table->file->stats.block_size/2/ 03599 (keyinfo->key_length+table->file->ref_length)+1; 03600 tmp= record_count*(tmp+keys_per_block-1)/keys_per_block; 03601 } 03602 else 03603 tmp= record_count*min(tmp,s->worst_seeks); 03604 } 03605 } 03606 else 03607 { 03608 /* 03609 Use as much key-parts as possible and a uniq key is better 03610 than a not unique key 03611 Set tmp to (previous record count) * (records / combination) 03612 */ 03613 if ((found_part & 1) && 03614 (!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) || 03615 found_part == PREV_BITS(uint,keyinfo->key_parts))) 03616 { 03617 max_key_part= max_part_bit(found_part); 03618 /* 03619 ReuseRangeEstimateForRef-3: 03620 We're now considering a ref[or_null] access via 03621 (t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR 03622 (same-as-above but with one cond replaced 03623 with "t.keypart_i IS NULL")] (**) 03624 03625 Try re-using E(#rows) from "range" optimizer: 03626 We can do so if "range" optimizer used the same intervals as 03627 in (**). The intervals used by range optimizer may be not 03628 available at this point (as "range" access might have choosen to 03629 create quick select over another index), so we can't compare 03630 them to (**). We'll make indirect judgements instead. 03631 The sufficient conditions for re-use are: 03632 (C1) All e_i in (**) are constants, i.e. found_ref==FALSE. (if 03633 this is not satisfied we have no way to know which ranges 03634 will be actually scanned by 'ref' until we execute the 03635 join) 03636 (C2) max #key parts in 'range' access == K == max_key_part (this 03637 is apparently a necessary requirement) 03638 03639 We also have a property that "range optimizer produces equal or 03640 tighter set of scan intervals than ref(const) optimizer". Each 03641 of the intervals in (**) are "tightest possible" intervals when 03642 one limits itself to using keyparts 1..K (which we do in #2). 03643 From here it follows that range access used either one, or 03644 both of the (I1) and (I2) intervals: 03645 03646 (t.keypart1=c1 AND ... AND t.keypartK=eK) (I1) 03647 (same-as-above but with one cond replaced 03648 with "t.keypart_i IS NULL") (I2) 03649 03650 The remaining part is to exclude the situation where range 03651 optimizer used one interval while we're considering 03652 ref-or-null and looking for estimate for two intervals. This 03653 is done by last limitation: 03654 03655 (C3) "range optimizer used (have ref_or_null?2:1) intervals" 03656 */ 03657 if (table->quick_keys.is_set(key) && !found_ref && //(C1) 03658 table->quick_key_parts[key] == max_key_part && //(C2) 03659 table->quick_n_ranges[key] == 1+test(ref_or_null_part)) //(C3) 03660 { 03661 tmp= records= (double) table->quick_rows[key]; 03662 } 03663 else 03664 { 03665 /* Check if we have statistic about the distribution */ 03666 if ((records= keyinfo->rec_per_key[max_key_part-1])) 03667 tmp= records; 03668 else 03669 { 03670 /* 03671 Assume that the first key part matches 1% of the file 03672 and that the whole key matches 10 (duplicates) or 1 03673 (unique) records. 03674 Assume also that more key matches proportionally more 03675 records 03676 This gives the formula: 03677 records = (x * (b-a) + a*c-b)/(c-1) 03678 03679 b = records matched by whole key 03680 a = records matched by first key part (1% of all records?) 03681 c = number of key parts in key 03682 x = used key parts (1 <= x <= c) 03683 */ 03684 double rec_per_key; 03685 if (!(rec_per_key=(double) 03686 keyinfo->rec_per_key[keyinfo->key_parts-1])) 03687 rec_per_key=(double) s->records/rec+1; 03688 03689 if (!s->records) 03690 tmp = 0; 03691 else if (rec_per_key/(double) s->records >= 0.01) 03692 tmp = rec_per_key; 03693 else 03694 { 03695 double a=s->records*0.01; 03696 if (keyinfo->key_parts > 1) 03697 tmp= (max_key_part * (rec_per_key - a) + 03698 a*keyinfo->key_parts - rec_per_key)/ 03699 (keyinfo->key_parts-1); 03700 else 03701 tmp= a; 03702 set_if_bigger(tmp,1.0); 03703 } 03704 records = (ulong) tmp; 03705 } 03706 03707 if (ref_or_null_part) 03708 { 03709 /* We need to do two key searches to find key */ 03710 tmp *= 2.0; 03711 records *= 2.0; 03712 } 03713 03714 /* 03715 ReuseRangeEstimateForRef-4: We get here if we could not reuse 03716 E(#rows) from range optimizer. Make another try: 03717 03718 If range optimizer produced E(#rows) for a prefix of the ref 03719 access we're considering, and that E(#rows) is lower then our 03720 current estimate, make the adjustment. 03721 03722 The decision whether we can re-use the estimate from the range 03723 optimizer is the same as in ReuseRangeEstimateForRef-3, 03724 applied to first table->quick_key_parts[key] key parts. 03725 */ 03726 if (table->quick_keys.is_set(key) && 03727 table->quick_key_parts[key] <= max_key_part && 03728 const_part & (1 << table->quick_key_parts[key]) && 03729 table->quick_n_ranges[key] == 1 + test(ref_or_null_part & 03730 const_part) && 03731 records > (double) table->quick_rows[key]) 03732 { 03733 tmp= records= (double) table->quick_rows[key]; 03734 } 03735 } 03736 03737 /* Limit the number of matched rows */ 03738 set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key); 03739 if (table->used_keys.is_set(key)) 03740 { 03741 /* we can use only index tree */ 03742 uint keys_per_block= table->file->stats.block_size/2/ 03743 (keyinfo->key_length+table->file->ref_length)+1; 03744 tmp= record_count*(tmp+keys_per_block-1)/keys_per_block; 03745 } 03746 else 03747 tmp= record_count*min(tmp,s->worst_seeks); 03748 } 03749 else 03750 tmp= best_time; // Do nothing 03751 } 03752 } /* not ft_key */ 03753 if (tmp < best_time - records/(double) TIME_FOR_COMPARE) 03754 { 03755 best_time= tmp + records/(double) TIME_FOR_COMPARE; 03756 best= tmp; 03757 best_records= records; 03758 best_key= start_key; 03759 best_max_key_part= max_key_part; 03760 } 03761 } 03762 records= best_records; 03763 } 03764 03765 /* 03766 Don't test table scan if it can't be better. 03767 Prefer key lookup if we would use the same key for scanning. 03768 03769 Don't do a table scan on InnoDB tables, if we can read the used 03770 parts of the row from any of the used index. 03771 This is because table scans uses index and we would not win 03772 anything by using a table scan. 03773 03774 A word for word translation of the below if-statement in psergey's 03775 understanding: we check if we should use table scan if: 03776 (1) The found 'ref' access produces more records than a table scan 03777 (or index scan, or quick select), or 'ref' is more expensive than 03778 any of them. 03779 (2) This doesn't hold: the best way to perform table scan is to to perform 03780 'range' access using index IDX, and the best way to perform 'ref' 03781 access is to use the same index IDX, with the same or more key parts. 03782 (note: it is not clear how this rule is/should be extended to 03783 index_merge quick selects) 03784 (3) See above note about InnoDB. 03785 (4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access 03786 path, but there is no quick select) 03787 If the condition in the above brackets holds, then the only possible 03788 "table scan" access method is ALL/index (there is no quick select). 03789 Since we have a 'ref' access path, and FORCE INDEX instructs us to 03790 choose it over ALL/index, there is no need to consider a full table 03791 scan. 03792 */ 03793 if ((records >= s->found_records || best > s->read_time) && // (1) 03794 !(s->quick && best_key && s->quick->index == best_key->key && // (2) 03795 best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2) 03796 !((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3) 03797 ! s->table->used_keys.is_clear_all() && best_key) && // (3) 03798 !(s->table->force_index && best_key && !s->quick)) // (4) 03799 { // Check full join 03800 ha_rows rnd_records= s->found_records; 03801 /* 03802 If there is a filtering condition on the table (i.e. ref analyzer found 03803 at least one "table.keyXpartY= exprZ", where exprZ refers only to tables 03804 preceding this table in the join order we're now considering), then 03805 assume that 25% of the rows will be filtered out by this condition. 03806 03807 This heuristic is supposed to force tables used in exprZ to be before 03808 this table in join order. 03809 */ 03810 if (found_constraint) 03811 rnd_records-= rnd_records/4; 03812 03813 /* 03814 If applicable, get a more accurate estimate. Don't use the two 03815 heuristics at once. 03816 */ 03817 if (s->table->quick_condition_rows != s->found_records) 03818 rnd_records= s->table->quick_condition_rows; 03819 03820 /* 03821 Range optimizer never proposes a RANGE if it isn't better 03822 than FULL: so if RANGE is present, it's always preferred to FULL. 03823 Here we estimate its cost. 03824 */ 03825 if (s->quick) 03826 { 03827 /* 03828 For each record we: 03829 - read record range through 'quick' 03830 - skip rows which does not satisfy WHERE constraints 03831 TODO: 03832 We take into account possible use of join cache for ALL/index 03833 access (see first else-branch below), but we don't take it into 03834 account here for range/index_merge access. Find out why this is so. 03835 */ 03836 tmp= record_count * 03837 (s->quick->read_time + 03838 (s->found_records - rnd_records)/(double) TIME_FOR_COMPARE); 03839 } 03840 else 03841 { 03842 /* Estimate cost of reading table. */ 03843 tmp= s->table->file->scan_time(); 03844 if (s->table->map & join->outer_join) // Can't use join cache 03845 { 03846 /* 03847 For each record we have to: 03848 - read the whole table record 03849 - skip rows which does not satisfy join condition 03850 */ 03851 tmp= record_count * 03852 (tmp + 03853 (s->records - rnd_records)/(double) TIME_FOR_COMPARE); 03854 } 03855 else 03856 { 03857 /* We read the table as many times as join buffer becomes full. */ 03858 tmp*= (1.0 + floor((double) cache_record_length(join,idx) * 03859 record_count / 03860 (double) thd->variables.join_buff_size)); 03861 /* 03862 We don't make full cartesian product between rows in the scanned 03863 table and existing records because we skip all rows from the 03864 scanned table, which does not satisfy join condition when 03865 we read the table (see flush_cached_records for details). Here we 03866 take into account cost to read and skip these records. 03867 */ 03868 tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE; 03869 } 03870 } 03871 03872 /* 03873 We estimate the cost of evaluating WHERE clause for found records 03874 as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus 03875 tmp give us total cost of using TABLE SCAN 03876 */ 03877 if (best == DBL_MAX || 03878 (tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records < 03879 best + record_count/(double) TIME_FOR_COMPARE*records)) 03880 { 03881 /* 03882 If the table has a range (s->quick is set) make_join_select() 03883 will ensure that this will be used 03884 */ 03885 best= tmp; 03886 records= rows2double(rnd_records); 03887 best_key= 0; 03888 } 03889 } 03890 03891 /* Update the cost information for the current partial plan */ 03892 join->positions[idx].records_read= records; 03893 join->positions[idx].read_time= best; 03894 join->positions[idx].key= best_key; 03895 join->positions[idx].table= s; 03896 03897 if (!best_key && 03898 idx == join->const_tables && 03899 s->table == join->sort_by_table && 03900 join->unit->select_limit_cnt >= records) 03901 join->sort_by_table= (TABLE*) 1; // Must use temporary table 03902 03903 DBUG_VOID_RETURN; 03904 } 03905 03906 03907 /* 03908 Selects and invokes a search strategy for an optimal query plan. 03909 03910 SYNOPSIS 03911 choose_plan() 03912 join pointer to the structure providing all context info for 03913 the query 03914 join_tables set of the tables in the query 03915 03916 DESCRIPTION 03917 The function checks user-configurable parameters that control the search 03918 strategy for an optimal plan, selects the search method and then invokes 03919 it. Each specific optimization procedure stores the final optimal plan in 03920 the array 'join->best_positions', and the cost of the plan in 03921 'join->best_read'. 03922 03923 RETURN 03924 None 03925 */ 03926 03927 static void 03928 choose_plan(JOIN *join, table_map join_tables) 03929 { 03930 uint search_depth= join->thd->variables.optimizer_search_depth; 03931 uint prune_level= join->thd->variables.optimizer_prune_level; 03932 bool straight_join= join->select_options & SELECT_STRAIGHT_JOIN; 03933 DBUG_ENTER("choose_plan"); 03934 03935 join->cur_embedding_map= 0; 03936 reset_nj_counters(join->join_list); 03937 /* 03938 if (S