Drizzled Public API Documentation

join.cc
Go to the documentation of this file.
1 /* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2  * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3  *
4  * Copyright (C) 2008-2009 Sun Microsystems, Inc.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20 
30 #include <config.h>
31 
32 #include <float.h>
33 #include <math.h>
34 
35 #include <drizzled/item/cache.h>
36 #include <drizzled/item/cmpfunc.h>
37 #include <drizzled/item/copy_string.h>
38 #include <drizzled/item/uint.h>
39 #include <drizzled/cached_item.h>
40 #include <drizzled/sql_base.h>
41 #include <drizzled/sql_select.h> /* include join.h */
42 #include <drizzled/lock.h>
43 #include <drizzled/nested_join.h>
44 #include <drizzled/join.h>
45 #include <drizzled/join_cache.h>
46 #include <drizzled/show.h>
47 #include <drizzled/field/blob.h>
48 #include <drizzled/open_tables_state.h>
49 #include <drizzled/optimizer/position.h>
50 #include <drizzled/optimizer/sargable_param.h>
51 #include <drizzled/optimizer/key_use.h>
52 #include <drizzled/optimizer/range.h>
53 #include <drizzled/optimizer/sum.h>
54 #include <drizzled/optimizer/explain_plan.h>
55 #include <drizzled/optimizer/access_method_factory.h>
56 #include <drizzled/optimizer/access_method.h>
57 #include <drizzled/records.h>
58 #include <drizzled/probes.h>
59 #include <drizzled/internal/my_bit.h>
60 #include <drizzled/internal/my_sys.h>
61 #include <drizzled/internal/iocache.h>
62 #include <drizzled/plugin/storage_engine.h>
63 #include <drizzled/session.h>
64 #include <drizzled/select_result.h>
65 #include <drizzled/debug.h>
66 #include <drizzled/item/subselect.h>
67 #include <drizzled/my_hash.h>
68 #include <drizzled/sql_lex.h>
69 #include <drizzled/statistics_variables.h>
70 #include <drizzled/system_variables.h>
71 #include <algorithm>
72 
73 using namespace std;
74 
75 namespace drizzled {
76 
77 extern plugin::StorageEngine *heap_engine;
78 
80 static bool make_group_fields(Join *main_join, Join *curr_join);
81 static void calc_group_buffer(Join *join, Order *group);
82 static bool alloc_group_fields(Join *join, Order *group);
83 static uint32_t cache_record_length(Join *join, uint32_t index);
84 static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref);
85 static bool get_best_combination(Join *join);
86 static void set_position(Join *join,
87  uint32_t index,
88  JoinTable *table,
89  optimizer::KeyUse *key);
90 static bool choose_plan(Join *join,table_map join_tables);
91 static void best_access_path(Join *join, JoinTable *s,
92  Session *session,
93  table_map remaining_tables,
94  uint32_t idx,
95  double record_count,
96  double read_time);
97 static void optimize_straight_join(Join *join, table_map join_tables);
98 static bool greedy_search(Join *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
99 static bool best_extension_by_limited_search(Join *join,
100  table_map remaining_tables,
101  uint32_t idx,
102  double record_count,
103  double read_time,
104  uint32_t depth,
105  uint32_t prune_level);
106 static uint32_t determine_search_depth(Join* join);
107 static void make_simple_join(Join*, Table*);
108 static void make_outerjoin_info(Join *join);
109 static bool make_join_select(Join *join, optimizer::SqlSelect *select,COND *item);
110 static void make_join_readinfo(Join&);
111 static void update_depend_map(Join *join);
112 static void update_depend_map(Join *join, Order *order);
113 static Order *remove_constants(Join *join,Order *first_order,COND *cond, bool change_list, bool *simple_order);
114 static void return_zero_rows(Join *join,
115  select_result *res,
116  TableList *tables,
117  List<Item> &fields,
118  bool send_row,
119  uint64_t select_options,
120  const char *info,
121  Item *having);
122 static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top);
123 static int remove_duplicates(Join *join,Table *entry,List<Item> &fields, Item *having);
124 static int setup_without_group(Session *session,
125  Item **ref_pointer_array,
126  TableList *tables,
127  TableList *,
128  List<Item> &fields,
129  List<Item> &all_fields,
130  COND **conds,
131  Order *order,
132  Order *group,
133  bool *hidden_group_fields);
134 static bool make_join_statistics(Join *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
135 static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
136 static Table *get_sort_by_table(Order *a, Order *b,TableList *tables);
137 static void reset_nj_counters(List<TableList> *join_list);
138 static bool test_if_subpart(Order *a,Order *b);
139 static void restore_prev_nj_state(JoinTable *last);
140 static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
141 static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
142 
143 Join::Join(Session *session_arg,
144  List<Item> &fields_arg,
145  uint64_t select_options_arg,
146  select_result *result_arg) :
147  join_tab(NULL),
148  best_ref(NULL),
149  map2table(NULL),
150  join_tab_save(NULL),
151  table(NULL),
152  all_tables(NULL),
153  sort_by_table(NULL),
154  tables(0),
155  outer_tables(0),
156  const_tables(0),
157  send_group_parts(0),
158  sort_and_group(false),
159  first_record(false),
160  full_join(false),
161  group(false),
162  no_field_update(false),
163  do_send_rows(true),
164  resume_nested_loop(false),
165  no_const_tables(false),
166  select_distinct(false),
167  group_optimized_away(false),
168  simple_order(false),
169  simple_group(false),
170  no_order(false),
171  skip_sort_order(false),
172  union_part(false),
173  optimized(false),
174  need_tmp(false),
175  hidden_group_fields(false),
176  const_table_map(0),
177  found_const_table_map(0),
178  outer_join(0),
179  send_records(0),
180  found_records(0),
181  examined_rows(0),
182  row_limit(0),
183  select_limit(0),
184  fetch_limit(HA_POS_ERROR),
185  session(session_arg),
186  fields_list(fields_arg),
187  join_list(NULL),
188  unit(NULL),
189  select_lex(NULL),
190  select(NULL),
191  exec_tmp_table1(NULL),
192  exec_tmp_table2(NULL),
193  sum_funcs(NULL),
194  sum_funcs2(NULL),
195  having(NULL),
196  tmp_having(NULL),
197  having_history(NULL),
198  select_options(select_options_arg),
199  result(result_arg),
200  lock(session_arg->open_tables.lock),
201  tmp_join(NULL),
202  all_fields(fields_arg),
203  error(0),
204  cond_equal(NULL),
205  return_tab(NULL),
206  ref_pointer_array(NULL),
207  items0(NULL),
208  items1(NULL),
209  items2(NULL),
210  items3(NULL),
211  ref_pointer_array_size(0),
212  zero_result_cause(NULL),
213  sortorder(NULL),
214  table_reexec(NULL),
215  join_tab_reexec(NULL)
216 {
217  select_distinct= test(select_options & SELECT_DISTINCT);
218  if (&fields_list != &fields_arg) /* only copy if not same*/
219  fields_list= fields_arg;
220  memset(&keyuse, 0, sizeof(keyuse));
221  tmp_table_param.init();
222  tmp_table_param.end_write_records= HA_POS_ERROR;
223  rollup.setState(Rollup::STATE_NONE);
224 }
225 
232 void Join::reset(Session *session_arg,
233  List<Item> &fields_arg,
234  uint64_t select_options_arg,
235  select_result *result_arg)
236 {
237  join_tab= NULL;
238  best_ref= NULL;
239  map2table= NULL;
240  join_tab_save= NULL;
241  table= NULL;
242  all_tables= NULL;
243  sort_by_table= NULL;
244  tables= 0;
245  outer_tables= 0;
246  const_tables= 0;
247  send_group_parts= 0;
248  sort_and_group= false;
249  first_record= false;
250  full_join= false;
251  group= false;
252  no_field_update= false;
253  do_send_rows= true;
254  resume_nested_loop= false;
255  no_const_tables= false;
256  select_distinct= false;
257  group_optimized_away= false;
258  simple_order= false;
259  simple_group= false;
260  no_order= false;
261  skip_sort_order= false;
262  union_part= false;
263  optimized= false;
264  need_tmp= false;
265  hidden_group_fields= false;
266  const_table_map= 0;
267  found_const_table_map= 0;
268  outer_join= 0;
269  send_records= 0;
270  found_records= 0;
271  examined_rows= 0;
272  row_limit= 0;
273  select_limit= 0;
274  fetch_limit= HA_POS_ERROR;
275  session= session_arg;
276  fields_list= fields_arg;
277  join_list= NULL;
278  unit= NULL;
279  select_lex= NULL;
280  select= NULL;
281  exec_tmp_table1= NULL;
282  exec_tmp_table2= NULL;
283  sum_funcs= NULL;
284  sum_funcs2= NULL;
285  having= NULL;
286  tmp_having= NULL;
287  having_history= NULL;
288  select_options= select_options_arg;
289  result= result_arg;
290  lock= session_arg->open_tables.lock;
291  tmp_join= NULL;
292  all_fields= fields_arg;
293  error= 0;
294  cond_equal= NULL;
295  return_tab= NULL;
296  ref_pointer_array= NULL;
297  items0= NULL;
298  items1= NULL;
299  items2= NULL;
300  items3= NULL;
302  zero_result_cause= NULL;
303  sortorder= NULL;
304  table_reexec= NULL;
305  join_tab_reexec= NULL;
306  select_distinct= test(select_options & SELECT_DISTINCT);
307  if (&fields_list != &fields_arg) /* only copy if not same*/
308  fields_list= fields_arg;
309  memset(&keyuse, 0, sizeof(keyuse));
310  tmp_table_param.init();
311  tmp_table_param.end_write_records= HA_POS_ERROR;
312  rollup.setState(Rollup::STATE_NONE);
313 }
314 
315 bool Join::is_top_level_join() const
316 {
317  return unit == &session->lex().unit && (unit->fake_select_lex == 0 || select_lex == unit->fake_select_lex);
318 }
319 
332 int Join::prepare(Item ***rref_pointer_array,
333  TableList *tables_init,
334  uint32_t wild_num,
335  COND *conds_init,
336  uint32_t og_num,
337  Order *order_init,
338  Order *group_init,
339  Item *having_init,
340  Select_Lex *select_lex_arg,
341  Select_Lex_Unit *unit_arg)
342 {
343  // to prevent double initialization on EXPLAIN
344  if (optimized)
345  return 0;
346 
347  conds= conds_init;
348  order= order_init;
349  group_list= group_init;
350  having= having_init;
351  tables_list= tables_init;
352  select_lex= select_lex_arg;
353  select_lex->join= this;
354  join_list= &select_lex->top_join_list;
355  union_part= unit_arg->is_union();
356 
357  session->lex().current_select->is_item_list_lookup= 1;
358  /*
359  If we have already executed SELECT, then it have not sense to prevent
360  its table from update (see unique_table())
361  */
362  if (session->derived_tables_processing)
363  select_lex->exclude_from_table_unique_test= true;
364 
365  /* Check that all tables, fields, conds and order are ok */
366 
367  if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
368  setup_tables_and_check_access(session, &select_lex->context, join_list, tables_list, &select_lex->leaf_tables, false))
369  {
370  return(-1);
371  }
372 
373  TableList *table_ptr;
374  for (table_ptr= select_lex->leaf_tables; table_ptr; table_ptr= table_ptr->next_leaf)
375  {
376  tables++;
377  }
378 
379 
380  if (setup_wild(session, fields_list, &all_fields, wild_num))
381  return -1;
382  select_lex->setup_ref_array(session, og_num);
383  if (setup_fields(session, *rref_pointer_array, fields_list, MARK_COLUMNS_READ, &all_fields, 1) ||
384  setup_without_group(session, *rref_pointer_array, tables_list, select_lex->leaf_tables, fields_list,
385  all_fields, &conds, order, group_list, &hidden_group_fields))
386  return -1;
387 
388  ref_pointer_array= *rref_pointer_array;
389 
390  if (having)
391  {
392  nesting_map save_allow_sum_func= session->lex().allow_sum_func;
393  session->setWhere("having clause");
394  session->lex().allow_sum_func|= 1 << select_lex_arg->nest_level;
395  select_lex->having_fix_field= 1;
396  bool having_fix_rc= (!having->fixed &&
397  (having->fix_fields(session, &having) ||
398  having->check_cols(1)));
399  select_lex->having_fix_field= 0;
400  if (having_fix_rc || session->is_error())
401  return(-1);
402  session->lex().allow_sum_func= save_allow_sum_func;
403  }
404 
405  {
406  Item_subselect *subselect;
407  Item_in_subselect *in_subs= NULL;
408  /*
409  Are we in a subquery predicate?
410  TODO: the block below will be executed for every PS execution without need.
411  */
412  if ((subselect= select_lex->master_unit()->item))
413  {
414  if (subselect->substype() == Item_subselect::IN_SUBS)
415  in_subs= (Item_in_subselect*)subselect;
416 
417  {
418  bool do_materialize= true;
419  /*
420  Check if the subquery predicate can be executed via materialization.
421  The required conditions are:
422  1. Subquery predicate is an IN/=ANY subq predicate
423  2. Subquery is a single SELECT (not a UNION)
424  3. Subquery is not a table-less query. In this case there is no
425  point in materializing.
426  4. Subquery predicate is a top-level predicate
427  (this implies it is not negated)
428  TODO: this is a limitation that should be lifeted once we
429  implement correct NULL semantics (WL#3830)
430  5. Subquery is non-correlated
431  TODO:
432  This is an overly restrictive condition. It can be extended to:
433  (Subquery is non-correlated ||
434  Subquery is correlated to any query outer to IN predicate ||
435  (Subquery is correlated to the immediate outer query &&
436  Subquery !contains {GROUP BY, ORDER BY [LIMIT],
437  aggregate functions) && subquery predicate is not under "NOT IN"))
438  6. No execution method was already chosen (by a prepared statement).
439 
440  (*) The subquery must be part of a SELECT statement. The current
441  condition also excludes multi-table update statements.
442 
443  We have to determine whether we will perform subquery materialization
444  before calling the IN=>EXISTS transformation, so that we know whether to
445  perform the whole transformation or only that part of it which wraps
446  Item_in_subselect in an Item_in_optimizer.
447  */
448  if (do_materialize &&
449  in_subs && // 1
450  !select_lex->master_unit()->first_select()->next_select() && // 2
451  select_lex->master_unit()->first_select()->leaf_tables && // 3
452  session->lex().sql_command == SQLCOM_SELECT) // *
453  {
454  if (in_subs->is_top_level_item() && // 4
455  !in_subs->is_correlated && // 5
456  in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
457  in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
458  }
459 
460  Item_subselect::trans_res trans_res;
461  if ((trans_res= subselect->select_transformer(this)) !=
462  Item_subselect::RES_OK)
463  {
464  return((trans_res == Item_subselect::RES_ERROR));
465  }
466  }
467  }
468  }
469 
470  if (order)
471  {
472  Order *ord;
473  for (ord= order; ord; ord= ord->next)
474  {
475  Item *item= *ord->item;
476  if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
477  item->split_sum_func(session, ref_pointer_array, all_fields);
478  }
479  }
480 
481  if (having && having->with_sum_func)
482  having->split_sum_func(session, ref_pointer_array, all_fields,
483  &having, true);
484  if (select_lex->inner_sum_func_list)
485  {
486  Item_sum *end=select_lex->inner_sum_func_list;
487  Item_sum *item_sum= end;
488  do
489  {
490  item_sum= item_sum->next;
491  item_sum->split_sum_func(session, ref_pointer_array,
492  all_fields, item_sum->ref_by, false);
493  } while (item_sum != end);
494  }
495 
496  if (select_lex->inner_refs_list.size() &&
497  fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
498  return(-1);
499 
500  /*
501  Check if there are references to un-aggregated columns when computing
502  aggregate functions with implicit grouping (there is no GROUP BY).
503 
504  MODE_ONLY_FULL_GROUP_BY is enabled here by default
505  */
506  if (! group_list &&
507  select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
508  select_lex->full_group_by_flag.test(SUM_FUNC_USED))
509  {
510  my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
511  ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
512  return(-1);
513  }
514  {
515  /* Caclulate the number of groups */
516  send_group_parts= 0;
517  for (Order *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
518  send_group_parts++;
519  }
520 
521  if (error)
522  return(-1);
523 
524  /*
525  * The below will create the new table for
526  * CREATE TABLE ... SELECT
527  *
528  * @see create_table_from_items() in drizzled/sql_insert.cc
529  */
530  if (result && result->prepare(fields_list, unit_arg))
531  return(-1);
532 
533  /* Init join struct */
534  count_field_types(select_lex, &tmp_table_param, all_fields, 0);
535  ref_pointer_array_size= all_fields.size() * sizeof(Item*);
536  this->group= group_list != 0;
537  unit= unit_arg;
538 
539 #ifdef RESTRICTED_GROUP
540  if (sum_func_count && !group_list && (func_count || field_count))
541  {
542  my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
543  return(-1);
544  }
545 #endif
546  if (select_lex->olap == ROLLUP_TYPE && rollup_init())
547  return(-1);
548 
549  if (alloc_func_list())
550  return(-1);
551 
552  return 0; // All OK
553 }
554 
555 /*
556  Remove the predicates pushed down into the subquery
557 
558  SYNOPSIS
559  Join::remove_subq_pushed_predicates()
560  where IN Must be NULL
561  OUT The remaining WHERE condition, or NULL
562 
563  DESCRIPTION
564  Given that this join will be executed using (unique|index)_subquery,
565  without "checking NULL", remove the predicates that were pushed down
566  into the subquery.
567 
568  If the subquery compares scalar values, we can remove the condition that
569  was wrapped into trig_cond (it will be checked when needed by the subquery
570  engine)
571 
572  If the subquery compares row values, we need to keep the wrapped
573  equalities in the WHERE clause: when the left (outer) tuple has both NULL
574  and non-NULL values, we'll do a full table scan and will rely on the
575  equalities corresponding to non-NULL parts of left tuple to filter out
576  non-matching records.
577 
578  TODO: We can remove the equalities that will be guaranteed to be true by the
579  fact that subquery engine will be using index lookup. This must be done only
580  for cases where there are no conversion errors of significance, e.g. 257
581  that is searched in a byte. But this requires homogenization of the return
582  codes of all Field*::store() methods.
583 */
584 void Join::remove_subq_pushed_predicates(Item **where)
585 {
586  if (conds->type() == Item::FUNC_ITEM &&
587  ((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
588  ((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
589  ((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
590  test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
591  ((Item_func *)conds)->arguments()[0]))
592  {
593  *where= 0;
594  return;
595  }
596 }
597 
610 {
611  // to prevent double initialization on EXPLAIN
612  if (optimized)
613  return 0;
614  optimized= 1;
615 
616  session->set_proc_info("optimizing");
617  row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
618  unit->select_limit_cnt);
619  /* select_limit is used to decide if we are likely to scan the whole table */
620  select_limit= unit->select_limit_cnt;
621  if (having || (select_options & OPTION_FOUND_ROWS))
622  select_limit= HA_POS_ERROR;
623  do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
624  // Ignore errors of execution if option IGNORE present
625  if (session->lex().ignore)
626  session->lex().current_select->no_error= 1;
627 
628 #ifdef HAVE_REF_TO_FIELDS // Not done yet
629  /* Add HAVING to WHERE if possible */
630  if (having && !group_list && !sum_func_count)
631  {
632  if (!conds)
633  {
634  conds= having;
635  having= 0;
636  }
637  else
638  {
639  conds= new Item_cond_and(conds,having);
640 
641  /*
642  Item_cond_and can't be fixed after creation, so we do not check
643  conds->fixed
644  */
645  conds->fix_fields(session, &conds);
646  conds->change_ref_to_fields(session, tables_list);
647  conds->top_level_item();
648  having= 0;
649  }
650  }
651 #endif
652 
653  /* Convert all outer joins to inner joins if possible */
654  conds= simplify_joins(this, join_list, conds, true);
656 
657  conds= optimize_cond(this, conds, join_list, &cond_value);
658  if (session->is_error())
659  {
660  error= 1;
661  return 1;
662  }
663 
664  {
665  having= optimize_cond(this, having, join_list, &having_value);
666  if (session->is_error())
667  {
668  error= 1;
669  return 1;
670  }
671  if (select_lex->where)
672  select_lex->cond_value= cond_value;
673  if (select_lex->having)
674  select_lex->having_value= having_value;
675 
676  if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
677  (!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
678  { /* Impossible cond */
679  zero_result_cause= having_value == Item::COND_FALSE ?
680  "Impossible HAVING" : "Impossible WHERE";
681  tables = 0;
682  goto setup_subq_exit;
683  }
684  }
685 
686  /* Optimize count(*), cmin() and cmax() */
687  if (tables_list && tmp_table_param.sum_func_count && ! group_list)
688  {
689  int res;
690  /*
691  optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
692  to the WHERE conditions,
693  or 1 if all items were resolved,
694  or 0, or an error number HA_ERR_...
695  */
696  if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
697  {
698  if (res == HA_ERR_KEY_NOT_FOUND)
699  {
700  zero_result_cause= "No matching min/max row";
701  tables = 0;
702  goto setup_subq_exit;
703  }
704  if (res > 1)
705  {
706  error= res;
707  return 1;
708  }
709  if (res < 0)
710  {
711  zero_result_cause= "No matching min/max row";
712  tables = 0;
713  goto setup_subq_exit;
714  }
715  zero_result_cause= "Select tables optimized away";
716  tables_list= 0; // All tables resolved
717  const_tables= tables;
718  /*
719  Extract all table-independent conditions and replace the WHERE
720  clause with them. All other conditions were computed by optimizer::sum_query
721  and the MIN/MAX/COUNT function(s) have been replaced by constants,
722  so there is no need to compute the whole WHERE clause again.
723  Notice that make_cond_for_table() will always succeed to remove all
724  computed conditions, because optimizer::sum_query() is applicable only to
725  conjunctions.
726  Preserve conditions for EXPLAIN.
727  */
728  if (conds && !(session->lex().describe & DESCRIBE_EXTENDED))
729  {
730  COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
731  conds= table_independent_conds;
732  }
733  goto setup_subq_exit;
734  }
735  }
736  if (!tables_list)
737  {
738  error= 0;
739  return 0;
740  }
741  error= -1; // Error is sent to client
742  sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
743 
744  /* Calculate how to do the join */
745  session->set_proc_info("statistics");
746  if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
747  session->is_fatal_error)
748  {
749  return 1;
750  }
751 
752  /* Remove distinct if only const tables */
753  select_distinct= select_distinct && (const_tables != tables);
754  session->set_proc_info("preparing");
755  if (result->initialize_tables(this))
756  {
757  return 1; // error == -1
758  }
759  if (const_table_map != found_const_table_map &&
760  !(select_options & SELECT_DESCRIBE) &&
761  (!conds ||
762  !(conds->used_tables() & RAND_TABLE_BIT) ||
763  select_lex->master_unit() == &session->lex().unit)) // upper level SELECT
764  {
765  zero_result_cause= "no matching row in const table";
766  goto setup_subq_exit;
767  }
768  if (!(session->options & OPTION_BIG_SELECTS) &&
769  best_read > (double) session->variables.max_join_size &&
770  !(select_options & SELECT_DESCRIBE))
771  {
772  my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
773  error= -1;
774  return 1;
775  }
776  if (const_tables && !(select_options & SELECT_NO_UNLOCK))
777  session->unlockSomeTables(table, const_tables);
778  if (!conds && outer_join)
779  {
780  /* Handle the case where we have an OUTER JOIN without a WHERE */
781  conds=new Item_int((int64_t) 1,1); // Always true
782  }
783  select= optimizer::make_select(*table, const_table_map,
784  const_table_map, conds, 1, &error);
785  if (error)
786  {
787  error= -1;
788  return 1;
789  }
790 
792  make_outerjoin_info(this);
793 
794  /*
795  Among the equal fields belonging to the same multiple equality
796  choose the one that is to be retrieved first and substitute
797  all references to these in where condition for a reference for
798  the selected field.
799  */
800  if (conds)
801  {
802  conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
803  conds->update_used_tables();
804  }
805 
806  /*
807  Permorm the the optimization on fields evaluation mentioned above
808  for all on expressions.
809  */
810  for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
811  {
812  if (*tab->on_expr_ref)
813  {
814  *tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
815  tab->cond_equal,
816  map2table);
817  (*tab->on_expr_ref)->update_used_tables();
818  }
819  }
820 
821  if (conds &&!outer_join && const_table_map != found_const_table_map &&
822  (select_options & SELECT_DESCRIBE) &&
823  select_lex->master_unit() == &session->lex().unit) // upper level SELECT
824  {
825  conds=new Item_int(0, 1); // Always false
826  }
827 
828  if (make_join_select(this, select, conds))
829  {
831  "Impossible WHERE noticed after reading const tables";
832  goto setup_subq_exit;
833  }
834 
835  error= -1; /* if goto err */
836 
837  /* Optimize distinct away if possible */
838  {
839  Order *org_order= order;
840  order= remove_constants(this, order,conds,1, &simple_order);
841  if (session->is_error())
842  {
843  error= 1;
844  return 1;
845  }
846 
847  /*
848  If we are using ORDER BY NULL or ORDER BY const_expression,
849  return result in any order (even if we are using a GROUP BY)
850  */
851  if (!order && org_order)
852  skip_sort_order= 1;
853  }
854  /*
855  Check if we can optimize away GROUP BY/DISTINCT.
856  We can do that if there are no aggregate functions, the
857  fields in DISTINCT clause (if present) and/or columns in GROUP BY
858  (if present) contain direct references to all key parts of
859  an unique index (in whatever order) and if the key parts of the
860  unique index cannot contain NULLs.
861  Note that the unique keys for DISTINCT and GROUP BY should not
862  be the same (as long as they are unique).
863 
864  The FROM clause must contain a single non-constant table.
865  */
866  if (tables - const_tables == 1 && (group_list || select_distinct) &&
867  ! tmp_table_param.sum_func_count &&
868  (! join_tab[const_tables].select ||
869  ! join_tab[const_tables].select->quick ||
870  join_tab[const_tables].select->quick->get_type() !=
871  optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
872  {
873  if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
874  {
875  /*
876  We have found that grouping can be removed since groups correspond to
877  only one row anyway, but we still have to guarantee correct result
878  order. The line below effectively rewrites the query from GROUP BY
879  <fields> to ORDER BY <fields>. There are two exceptions:
880  - if skip_sort_order is set (see above), then we can simply skip
881  GROUP BY;
882  - we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
883  with the GROUP BY ones, i.e. either one is a prefix of another.
884  We only check if the ORDER BY is a prefix of GROUP BY. In this case
885  test_if_subpart() copies the ASC/DESC attributes from the original
886  ORDER BY fields.
887  If GROUP BY is a prefix of order_st BY, then it is safe to leave
888  'order' as is.
889  */
890  if (! order || test_if_subpart(group_list, order))
891  order= skip_sort_order ? 0 : group_list;
892  /*
893  If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
894  rewritten to IGNORE INDEX FOR order_st BY(fields).
895  */
896  join_tab->table->keys_in_use_for_order_by=
897  join_tab->table->keys_in_use_for_group_by;
898  group_list= 0;
899  group= 0;
900  }
901  if (select_distinct &&
902  list_contains_unique_index(join_tab[const_tables].table,
904  (void *) &fields_list))
905  {
906  select_distinct= 0;
907  }
908  }
909  if (group_list || tmp_table_param.sum_func_count)
910  {
911  if (! hidden_group_fields && rollup.getState() == Rollup::STATE_NONE)
912  select_distinct=0;
913  }
914  else if (select_distinct && tables - const_tables == 1)
915  {
916  /*
917  We are only using one table. In this case we change DISTINCT to a
918  GROUP BY query if:
919  - The GROUP BY can be done through indexes (no sort) and the order_st
920  BY only uses selected fields.
921  (In this case we can later optimize away GROUP BY and order_st BY)
922  - We are scanning the whole table without LIMIT
923  This can happen if:
924  - We are using CALC_FOUND_ROWS
925  - We are using an ORDER BY that can't be optimized away.
926 
927  We don't want to use this optimization when we are using LIMIT
928  because in this case we can just create a temporary table that
929  holds LIMIT rows and stop when this table is full.
930  */
931  JoinTable *tab= &join_tab[const_tables];
932  bool all_order_fields_used;
933  if (order)
934  skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
935  &tab->table->keys_in_use_for_order_by);
936  if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
937  order, fields_list, all_fields,
938  &all_order_fields_used)))
939  {
940  bool skip_group= (skip_sort_order &&
941  test_if_skip_sort_order(tab, group_list, select_limit, 1,
942  &tab->table->keys_in_use_for_group_by) != 0);
943  count_field_types(select_lex, &tmp_table_param, all_fields, 0);
944  if ((skip_group && all_order_fields_used) ||
945  select_limit == HA_POS_ERROR ||
946  (order && !skip_sort_order))
947  {
948  /* Change DISTINCT to GROUP BY */
949  select_distinct= 0;
950  no_order= !order;
951  if (all_order_fields_used)
952  {
953  if (order && skip_sort_order)
954  {
955  /*
956  Force MySQL to read the table in sorted order to get result in
957  ORDER BY order.
958  */
959  tmp_table_param.quick_group=0;
960  }
961  order=0;
962  }
963  group=1; // For end_write_group
964  }
965  else
966  group_list= 0;
967  }
968  else if (session->is_fatal_error) // End of memory
969  return 1;
970  }
971  simple_group= 0;
972  {
973  Order *old_group_list;
974  group_list= remove_constants(this, (old_group_list= group_list), conds,
975  rollup.getState() == Rollup::STATE_NONE,
976  &simple_group);
977  if (session->is_error())
978  {
979  error= 1;
980  return 1;
981  }
982  if (old_group_list && !group_list)
983  select_distinct= 0;
984  }
985  if (!group_list && group)
986  {
987  order=0; // The output has only one row
988  simple_order=1;
989  select_distinct= 0; // No need in distinct for 1 row
991  }
992 
994  send_group_parts= tmp_table_param.group_parts; /* Save org parts */
995 
996  if (test_if_subpart(group_list, order) ||
997  (!group_list && tmp_table_param.sum_func_count))
998  order=0;
999 
1000  // Can't use sort on head table if using row cache
1001  if (full_join)
1002  {
1003  if (group_list)
1004  simple_group=0;
1005  if (order)
1006  simple_order=0;
1007  }
1008 
1009  /*
1010  Check if we need to create a temporary table.
1011  This has to be done if all tables are not already read (const tables)
1012  and one of the following conditions holds:
1013  - We are using DISTINCT (simple distinct's are already optimized away)
1014  - We are using an ORDER BY or GROUP BY on fields not in the first table
1015  - We are using different ORDER BY and GROUP BY orders
1016  - The user wants us to buffer the result.
1017  */
1018  need_tmp= (const_tables != tables &&
1019  ((select_distinct || !simple_order || !simple_group) ||
1020  (group_list && order) ||
1021  test(select_options & OPTION_BUFFER_RESULT)));
1022 
1023  // No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1024  make_join_readinfo(*this);
1025 
1026  /* Create all structures needed for materialized subquery execution. */
1028  return 1;
1029 
1030  /* Cache constant expressions in WHERE, HAVING, ON clauses. */
1032 
1033  /*
1034  is this simple IN subquery?
1035  */
1036  if (!group_list && !order &&
1037  unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1038  tables == 1 && conds &&
1039  !unit->is_union())
1040  {
1041  if (!having)
1042  {
1043  Item *where= conds;
1044  if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
1045  {
1046  remove_subq_pushed_predicates(&where);
1047  save_index_subquery_explain_info(join_tab, where);
1048  join_tab[0].type= AM_UNIQUE_SUBQUERY;
1049  error= 0;
1050  return(unit->item->change_engine(new subselect_uniquesubquery_engine(session, join_tab, unit->item, where)));
1051  }
1052  else if (join_tab[0].type == AM_REF &&
1053  join_tab[0].ref.items[0]->name == in_left_expr_name)
1054  {
1055  remove_subq_pushed_predicates(&where);
1056  save_index_subquery_explain_info(join_tab, where);
1057  join_tab[0].type= AM_INDEX_SUBQUERY;
1058  error= 0;
1059  return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, where, NULL, 0)));
1060  }
1061  }
1062  else if (join_tab[0].type == AM_REF_OR_NULL &&
1063  join_tab[0].ref.items[0]->name == in_left_expr_name &&
1064  having->name == in_having_cond)
1065  {
1066  join_tab[0].type= AM_INDEX_SUBQUERY;
1067  error= 0;
1068  conds= remove_additional_cond(conds);
1069  save_index_subquery_explain_info(join_tab, conds);
1070  return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, conds, having, 1)));
1071  }
1072 
1073  }
1074  /*
1075  Need to tell handlers that to play it safe, it should fetch all
1076  columns of the primary key of the tables: this is because MySQL may
1077  build row pointers for the rows, and for all columns of the primary key
1078  the read set has not necessarily been set by the server code.
1079  */
1080  if (need_tmp || select_distinct || group_list || order)
1081  {
1082  for (uint32_t i = const_tables; i < tables; i++)
1083  join_tab[i].table->prepare_for_position();
1084  }
1085 
1086  if (const_tables != tables)
1087  {
1088  /*
1089  Because filesort always does a full table scan or a quick range scan
1090  we must add the removed reference to the select for the table.
1091  We only need to do this when we have a simple_order or simple_group
1092  as in other cases the join is done before the sort.
1093  */
1094  if ((order || group_list) &&
1095  (join_tab[const_tables].type != AM_ALL) &&
1096  (join_tab[const_tables].type != AM_REF_OR_NULL) &&
1097  ((order && simple_order) || (group_list && simple_group)))
1098  {
1099  if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1100  return 1;
1101  }
1102  }
1103 
1104  if (!(select_options & SELECT_BIG_RESULT) &&
1105  ((group_list &&
1106  (!simple_group ||
1107  !test_if_skip_sort_order(&join_tab[const_tables], group_list,
1108  unit->select_limit_cnt, 0,
1109  &join_tab[const_tables].table->
1110  keys_in_use_for_group_by))) ||
1111  select_distinct) &&
1112  tmp_table_param.quick_group)
1113  {
1114  need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1115  }
1116  if (order)
1117  {
1118  /*
1119  Force using of tmp table if sorting by a SP or UDF function due to
1120  their expensive and probably non-deterministic nature.
1121  */
1122  for (Order *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1123  {
1124  Item *item= *tmp_order->item;
1125  if (item->is_expensive())
1126  {
1127  /* Force tmp table without sort */
1128  need_tmp=1; simple_order=simple_group=0;
1129  break;
1130  }
1131  }
1132  }
1133  }
1134 
1135  tmp_having= having;
1136  if (select_options & SELECT_DESCRIBE)
1137  {
1138  error= 0;
1139  return 0;
1140  }
1141  having= 0;
1142 
1143  /*
1144  The loose index scan access method guarantees that all grouping or
1145  duplicate row elimination (for distinct) is already performed
1146  during data retrieval, and that all MIN/MAX functions are already
1147  computed for each group. Thus all MIN/MAX functions should be
1148  treated as regular functions, and there is no need to perform
1149  grouping in the main execution loop.
1150  Notice that currently loose index scan is applicable only for
1151  single table queries, thus it is sufficient to test only the first
1152  join_tab element of the plan for its access method.
1153  */
1154  if (join_tab->is_using_loose_index_scan())
1155  tmp_table_param.precomputed_group_by= true;
1156 
1157  /* Create a tmp table if distinct or if the sort is too complicated */
1158  if (need_tmp)
1159  {
1160  session->set_proc_info("Creating tmp table");
1161 
1162  init_items_ref_array();
1163 
1164  tmp_table_param.hidden_field_count= all_fields.size() - fields_list.size();
1165  Order *tmp_group= (((not simple_group) or not (getDebug().test(debug::NO_KEY_GROUP))) ? group_list : NULL);
1166 
1167  /*
1168  Pushing LIMIT to the temporary table creation is not applicable
1169  when there is ORDER BY or GROUP BY or there is no GROUP BY, but
1170  there are aggregate functions, because in all these cases we need
1171  all result rows.
1172  */
1173  ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1174  !tmp_group &&
1175  !session->lex().current_select->with_sum_func) ?
1176  select_limit : HA_POS_ERROR;
1177 
1178  if (!(exec_tmp_table1=
1179  create_tmp_table(session, &tmp_table_param, all_fields,
1180  tmp_group,
1182  group_list && simple_group,
1183  select_options,
1184  tmp_rows_limit,
1185  (char *) "")))
1186  {
1187  return 1;
1188  }
1189 
1190  /*
1191  We don't have to store rows in temp table that doesn't match HAVING if:
1192  - we are sorting the table and writing complete group rows to the
1193  temp table.
1194  - We are using DISTINCT without resolving the distinct as a GROUP BY
1195  on all columns.
1196 
1197  If having is not handled here, it will be checked before the row
1198  is sent to the client.
1199  */
1200  if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1201  having= tmp_having;
1202 
1203  /* if group or order on first table, sort first */
1204  if (group_list && simple_group)
1205  {
1206  session->set_proc_info("Sorting for group");
1207  if (create_sort_index(session, this, group_list,
1208  HA_POS_ERROR, HA_POS_ERROR, false) ||
1209  alloc_group_fields(this, group_list) ||
1211  setup_sum_funcs(session, sum_funcs))
1212  {
1213  return 1;
1214  }
1215  group_list=0;
1216  }
1217  else
1218  {
1220  setup_sum_funcs(session, sum_funcs))
1221  {
1222  return 1;
1223  }
1224 
1225  if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1226  {
1227  session->set_proc_info("Sorting for order");
1228  if (create_sort_index(session, this, order, HA_POS_ERROR, HA_POS_ERROR, true))
1229  {
1230  return 1;
1231  }
1232  order=0;
1233  }
1234  }
1235 
1236  /*
1237  Optimize distinct when used on some of the tables
1238  SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1239  In this case we can stop scanning t2 when we have found one t1.a
1240  */
1241 
1242  if (exec_tmp_table1->distinct)
1243  {
1244  table_map used_tables= session->used_tables;
1245  JoinTable *last_join_tab= join_tab+tables-1;
1246  do
1247  {
1248  if (used_tables & last_join_tab->table->map)
1249  break;
1250  last_join_tab->not_used_in_distinct=1;
1251  } while (last_join_tab-- != join_tab);
1252  /* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1253  if (order && skip_sort_order)
1254  {
1255  /* Should always succeed */
1256  if (test_if_skip_sort_order(&join_tab[const_tables],
1257  order, unit->select_limit_cnt, 0,
1258  &join_tab[const_tables].table->
1259  keys_in_use_for_order_by))
1260  order= 0;
1261  }
1262  }
1263 
1264  /*
1265  If this join belongs to an uncacheable subquery save
1266  the original join
1267  */
1268  if (select_lex->uncacheable.any() && not is_top_level_join())
1270  }
1271 
1272  error= 0;
1273  return 0;
1274 
1275 setup_subq_exit:
1276  /* Even with zero matching rows, subqueries in the HAVING clause
1277  may need to be evaluated if there are aggregate functions in the query.
1278  */
1280  return 1;
1281  error= 0;
1282  return 0;
1283 }
1284 
1289 {
1290  memcpy(tmp_join, this, (size_t) sizeof(Join));
1291 }
1292 
1293 int Join::reinit()
1294 {
1295  unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1296  select_lex->offset_limit->val_uint() :
1297  0UL);
1298 
1299  first_record= 0;
1300 
1301  if (exec_tmp_table1)
1302  {
1303  exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1305  exec_tmp_table1->free_io_cache();
1306  exec_tmp_table1->filesort_free_buffers();
1307  }
1308  if (exec_tmp_table2)
1309  {
1310  exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1311  exec_tmp_table2->cursor->ha_delete_all_rows();
1312  exec_tmp_table2->free_io_cache();
1313  exec_tmp_table2->filesort_free_buffers();
1314  }
1315  if (items0)
1316  set_items_ref_array(items0);
1317 
1318  if (join_tab_save)
1319  memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1320 
1321  if (tmp_join)
1322  restore_tmp();
1323 
1324  /* Reset of sum functions */
1325  if (sum_funcs)
1326  {
1327  Item_sum *func, **func_ptr= sum_funcs;
1328  while ((func= *(func_ptr++)))
1329  func->clear();
1330  }
1331 
1332  return 0;
1333 }
1334 
1346 {
1347  tmp_join= (Join*)session->mem.alloc(sizeof(Join));
1348 
1349  error= 0; // Ensure that tmp_join.error= 0
1350  restore_tmp();
1351 }
1352 
1353 void Join::save_join_tab()
1354 {
1355  if (! join_tab_save && select_lex->master_unit()->uncacheable.any())
1356  {
1357  join_tab_save= (JoinTable*)session->mem.memdup(join_tab, sizeof(JoinTable) * tables);
1358  }
1359 }
1360 
1373 {
1374  List<Item> *columns_list= &fields_list;
1375  int tmp_error;
1376 
1377  session->set_proc_info("executing");
1378  error= 0;
1379 
1380  if (!tables_list && (tables || !select_lex->with_sum_func))
1381  {
1382  /* Only test of functions */
1383  if (select_options & SELECT_DESCRIBE)
1384  {
1385  optimizer::ExplainPlan planner(this,
1386  false,
1387  false,
1388  false,
1389  (zero_result_cause ? zero_result_cause : "No tables used"));
1390  planner.printPlan();
1391  }
1392  else
1393  {
1394  result->send_fields(*columns_list);
1395  /*
1396  We have to test for 'conds' here as the WHERE may not be constant
1397  even if we don't have any tables for prepared statements or if
1398  conds uses something like 'rand()'.
1399  */
1400  if (cond_value != Item::COND_FALSE &&
1401  (!conds || conds->val_int()) &&
1402  (!having || having->val_int()))
1403  {
1404  if (do_send_rows && result->send_data(fields_list))
1405  error= 1;
1406  else
1407  {
1408  error= (int) result->send_eof();
1409  send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1410  }
1411  }
1412  else
1413  {
1414  error= (int) result->send_eof();
1415  send_records= 0;
1416  }
1417  }
1418  /* Single select (without union) always returns 0 or 1 row */
1419  session->limit_found_rows= send_records;
1420  session->examined_row_count= 0;
1421  return;
1422  }
1423  /*
1424  Don't reset the found rows count if there're no tables as
1425  FOUND_ROWS() may be called. Never reset the examined row count here.
1426  It must be accumulated from all join iterations of all join parts.
1427  */
1428  if (tables)
1429  session->limit_found_rows= 0;
1430 
1431  if (zero_result_cause)
1432  {
1433  return_zero_rows(this, result, select_lex->leaf_tables, *columns_list, send_row_on_empty_set(), select_options, zero_result_cause, having);
1434  return;
1435  }
1436 
1437  if (select_options & SELECT_DESCRIBE)
1438  {
1439  /*
1440  Check if we managed to optimize ORDER BY away and don't use temporary
1441  table to resolve order_st BY: in that case, we only may need to do
1442  filesort for GROUP BY.
1443  */
1444  if (!order && !no_order && (!skip_sort_order || !need_tmp))
1445  {
1446  /* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1447  order= group_list;
1448  simple_order= simple_group;
1449  skip_sort_order= 0;
1450  }
1451  if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1452  {
1453  if (const_tables == tables
1454  || ((simple_order || skip_sort_order)
1455  && test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1456  order= 0;
1457  }
1458  having= tmp_having;
1459  optimizer::ExplainPlan planner(this,
1460  need_tmp,
1461  order != 0 && ! skip_sort_order,
1463  ! tables ? "No tables used" : NULL);
1464  planner.printPlan();
1465  return;
1466  }
1467 
1468  Join *curr_join= this;
1469  List<Item> *curr_all_fields= &all_fields;
1470  List<Item> *curr_fields_list= &fields_list;
1471  Table *curr_tmp_table= 0;
1472  /*
1473  Initialize examined rows here because the values from all join parts
1474  must be accumulated in examined_row_count. Hence every join
1475  iteration must count from zero.
1476  */
1477  curr_join->examined_rows= 0;
1478 
1479  /* Create a tmp table if distinct or if the sort is too complicated */
1480  if (need_tmp)
1481  {
1482  if (tmp_join)
1483  {
1484  /*
1485  We are in a non cacheable sub query. Get the saved join structure
1486  after optimization.
1487  (curr_join may have been modified during last exection and we need
1488  to reset it)
1489  */
1490  curr_join= tmp_join;
1491  }
1492  curr_tmp_table= exec_tmp_table1;
1493 
1494  /* Copy data to the temporary table */
1495  session->set_proc_info("Copying to tmp table");
1496  if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1497  curr_join->join_tab[curr_join->const_tables].sorted= 0;
1498  if ((tmp_error= do_select(curr_join, NULL, curr_tmp_table)))
1499  {
1500  error= tmp_error;
1501  return;
1502  }
1503  curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
1504 
1505  if (curr_join->having)
1506  curr_join->having= curr_join->tmp_having= 0; // Allready done
1507 
1508  /* Change sum_fields reference to calculated fields in tmp_table */
1509  curr_join->all_fields= *curr_all_fields;
1510  if (!items1)
1511  {
1512  items1= items0 + all_fields.size();
1513  if (sort_and_group || curr_tmp_table->group)
1514  {
1515  if (change_to_use_tmp_fields(session, items1,
1517  fields_list.size(), all_fields))
1518  return;
1519  }
1520  else
1521  {
1522  if (change_refs_to_tmp_fields(session, items1,
1524  fields_list.size(), all_fields))
1525  return;
1526  }
1527  curr_join->tmp_all_fields1= tmp_all_fields1;
1528  curr_join->tmp_fields_list1= tmp_fields_list1;
1529  curr_join->items1= items1;
1530  }
1531  curr_all_fields= &tmp_all_fields1;
1532  curr_fields_list= &tmp_fields_list1;
1533  curr_join->set_items_ref_array(items1);
1534 
1535  if (sort_and_group || curr_tmp_table->group)
1536  {
1537  curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1538  + curr_join->tmp_table_param.func_count;
1539  curr_join->tmp_table_param.sum_func_count= 0;
1540  curr_join->tmp_table_param.func_count= 0;
1541  }
1542  else
1543  {
1544  curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1545  curr_join->tmp_table_param.func_count= 0;
1546  }
1547 
1548  if (curr_tmp_table->group)
1549  { // Already grouped
1550  if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1551  curr_join->order= curr_join->group_list; /* order by group */
1552  curr_join->group_list= 0;
1553  }
1554 
1555  /*
1556  If we have different sort & group then we must sort the data by group
1557  and copy it to another tmp table
1558  This code is also used if we are using distinct something
1559  we haven't been able to store in the temporary table yet
1560  like SEC_TO_TIME(SUM(...)).
1561  */
1562 
1563  if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1564  || (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1565  { /* Must copy to another table */
1566  /* Free first data from old join */
1567  curr_join->join_free();
1568  make_simple_join(curr_join, curr_tmp_table);
1569  calc_group_buffer(curr_join, group_list);
1570  count_field_types(select_lex, &curr_join->tmp_table_param,
1571  curr_join->tmp_all_fields1,
1572  curr_join->select_distinct && !curr_join->group_list);
1573  curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.size()
1574  - curr_join->tmp_fields_list1.size();
1575 
1576  if (exec_tmp_table2)
1577  {
1578  curr_tmp_table= exec_tmp_table2;
1579  }
1580  else
1581  {
1582  /* group data to new table */
1583 
1584  /*
1585  If the access method is loose index scan then all MIN/MAX
1586  functions are precomputed, and should be treated as regular
1587  functions. See extended comment in Join::exec.
1588  */
1589  if (curr_join->join_tab->is_using_loose_index_scan())
1590  curr_join->tmp_table_param.precomputed_group_by= true;
1591 
1592  if (!(curr_tmp_table=
1593  exec_tmp_table2= create_tmp_table(session,
1594  &curr_join->tmp_table_param,
1595  *curr_all_fields,
1596  NULL,
1597  curr_join->select_distinct &&
1598  !curr_join->group_list,
1599  1, curr_join->select_options,
1600  HA_POS_ERROR,
1601  (char *) "")))
1602  {
1603  return;
1604  }
1605 
1606  curr_join->exec_tmp_table2= exec_tmp_table2;
1607  }
1608  if (curr_join->group_list)
1609  {
1610  session->set_proc_info("Creating sort index");
1611  if (curr_join->join_tab == join_tab)
1612  save_join_tab();
1613  if (create_sort_index(session, curr_join, curr_join->group_list, HA_POS_ERROR, HA_POS_ERROR, false) ||
1614  make_group_fields(this, curr_join))
1615  {
1616  return;
1617  }
1618  sortorder= curr_join->sortorder;
1619  }
1620 
1621  session->set_proc_info("Copying to group table");
1622  tmp_error= -1;
1623  if (curr_join != this)
1624  {
1625  if (sum_funcs2)
1626  {
1627  curr_join->sum_funcs= sum_funcs2;
1628  curr_join->sum_funcs_end= sum_funcs_end2;
1629  }
1630  else
1631  {
1632  curr_join->alloc_func_list();
1633  sum_funcs2= curr_join->sum_funcs;
1634  sum_funcs_end2= curr_join->sum_funcs_end;
1635  }
1636  }
1637  if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1638  return;
1639  curr_join->group_list= 0;
1640 
1641  if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1642  curr_join->join_tab[curr_join->const_tables].sorted= 0;
1643 
1644  if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1645  || (tmp_error= do_select(curr_join, NULL, curr_tmp_table)))
1646  {
1647  error= tmp_error;
1648  return;
1649  }
1650  curr_join->join_tab->read_record.end_read_record();
1651  curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1652  curr_join->join_tab[0].table= 0; // Table is freed
1653 
1654  // No sum funcs anymore
1655  if (!items2)
1656  {
1657  items2= items1 + all_fields.size();
1658  if (change_to_use_tmp_fields(session, items2,
1659  tmp_fields_list2, tmp_all_fields2,
1660  fields_list.size(), tmp_all_fields1))
1661  return;
1662  curr_join->tmp_fields_list2= tmp_fields_list2;
1663  curr_join->tmp_all_fields2= tmp_all_fields2;
1664  }
1665  curr_fields_list= &curr_join->tmp_fields_list2;
1666  curr_all_fields= &curr_join->tmp_all_fields2;
1667  curr_join->set_items_ref_array(items2);
1668  curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1669  curr_join->tmp_table_param.sum_func_count= 0;
1670  }
1671  if (curr_tmp_table->distinct)
1672  curr_join->select_distinct=0; /* Each row is unique */
1673 
1674  curr_join->join_free(); /* Free quick selects */
1675  if (curr_join->select_distinct && ! curr_join->group_list)
1676  {
1677  session->set_proc_info("Removing duplicates");
1678  if (curr_join->tmp_having)
1679  curr_join->tmp_having->update_used_tables();
1680 
1681  if (remove_duplicates(curr_join, curr_tmp_table,
1682  *curr_fields_list, curr_join->tmp_having))
1683  return;
1684 
1685  curr_join->tmp_having=0;
1686  curr_join->select_distinct=0;
1687  }
1688  curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1689  make_simple_join(curr_join, curr_tmp_table);
1690  calc_group_buffer(curr_join, curr_join->group_list);
1691  count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1692 
1693  }
1694 
1695  if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1696  {
1697  if (make_group_fields(this, curr_join))
1698  return;
1699 
1700  if (! items3)
1701  {
1702  if (! items0)
1703  init_items_ref_array();
1704  items3= ref_pointer_array + (all_fields.size() * 4);
1705  setup_copy_fields(session, &curr_join->tmp_table_param,
1706  items3, tmp_fields_list3, tmp_all_fields3,
1707  curr_fields_list->size(), *curr_all_fields);
1708  tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1709  tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1710  tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1711  curr_join->tmp_all_fields3= tmp_all_fields3;
1712  curr_join->tmp_fields_list3= tmp_fields_list3;
1713  }
1714  else
1715  {
1716  curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1717  curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1718  curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1719  }
1720  curr_fields_list= &tmp_fields_list3;
1721  curr_all_fields= &tmp_all_fields3;
1722  curr_join->set_items_ref_array(items3);
1723 
1724  if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1725  1, true) ||
1726  setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1727  session->is_fatal_error)
1728  return;
1729  }
1730  if (curr_join->group_list || curr_join->order)
1731  {
1732  session->set_proc_info("Sorting result");
1733  /* If we have already done the group, add HAVING to sorted table */
1734  if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1735  {
1736  // Some tables may have been const
1737  curr_join->tmp_having->update_used_tables();
1738  JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1739  table_map used_tables= (curr_join->const_table_map |
1740  curr_table->table->map);
1741 
1742  Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1743  if (sort_table_cond)
1744  {
1745  if (!curr_table->select)
1746  curr_table->select= new optimizer::SqlSelect;
1747  if (!curr_table->select->cond)
1748  curr_table->select->cond= sort_table_cond;
1749  else // This should never happen
1750  {
1751  curr_table->select->cond= new Item_cond_and(curr_table->select->cond, sort_table_cond);
1752  /*
1753  Item_cond_and do not need fix_fields for execution, its parameters
1754  are fixed or do not need fix_fields, too
1755  */
1756  curr_table->select->cond->quick_fix_field();
1757  }
1758  curr_table->select_cond= curr_table->select->cond;
1759  curr_table->select_cond->top_level_item();
1760  curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having, ~ (table_map) 0, ~used_tables, 0);
1761  }
1762  }
1763  {
1764  if (group)
1765  curr_join->select_limit= HA_POS_ERROR;
1766  else
1767  {
1768  /*
1769  We can abort sorting after session->select_limit rows if we there is no
1770  WHERE clause for any tables after the sorted one.
1771  */
1772  JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1773  JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1774  for (; curr_table < end_table ; curr_table++)
1775  {
1776  /*
1777  table->keyuse is set in the case there was an original WHERE clause
1778  on the table that was optimized away.
1779  */
1780  if (curr_table->select_cond ||
1781  (curr_table->keyuse && !curr_table->first_inner))
1782  {
1783  /* We have to sort all rows */
1784  curr_join->select_limit= HA_POS_ERROR;
1785  break;
1786  }
1787  }
1788  }
1789  if (curr_join->join_tab == join_tab)
1790  save_join_tab();
1791  /*
1792  Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1793  chose FILESORT to be faster than INDEX SCAN or there is no
1794  suitable index present.
1795  Note, that create_sort_index calls test_if_skip_sort_order and may
1796  finally replace sorting with index scan if there is a LIMIT clause in
1797  the query. XXX: it's never shown in EXPLAIN!
1798  OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1799  */
1800  if (create_sort_index(session, curr_join,
1801  curr_join->group_list ?
1802  curr_join->group_list : curr_join->order,
1803  curr_join->select_limit,
1804  (select_options & OPTION_FOUND_ROWS ?
1805  HA_POS_ERROR : unit->select_limit_cnt),
1806  curr_join->group_list ? true : false))
1807  return;
1808 
1809  sortorder= curr_join->sortorder;
1810  if (curr_join->const_tables != curr_join->tables &&
1811  !curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1812  {
1813  /*
1814  If no IO cache exists for the first table then we are using an
1815  INDEX SCAN and no filesort. Thus we should not remove the sorted
1816  attribute on the INDEX SCAN.
1817  */
1818  skip_sort_order= 1;
1819  }
1820  }
1821  }
1822  /* XXX: When can we have here session->is_error() not zero? */
1823  if (session->is_error())
1824  {
1825  error= session->is_error();
1826  return;
1827  }
1828  curr_join->having= curr_join->tmp_having;
1829  curr_join->fields= curr_fields_list;
1830 
1831  session->set_proc_info("Sending data");
1832  result->send_fields(*curr_fields_list);
1833  error= do_select(curr_join, curr_fields_list, NULL);
1834  session->limit_found_rows= curr_join->send_records;
1835 
1836  /* Accumulate the counts from all join iterations of all join parts. */
1837  session->examined_row_count+= curr_join->examined_rows;
1838 
1839  /*
1840  With EXPLAIN EXTENDED we have to restore original ref_array
1841  for a derived table which is always materialized.
1842  Otherwise we would not be able to print the query correctly.
1843  */
1844  if (items0 && (session->lex().describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1845  set_items_ref_array(items0);
1846 
1847  return;
1848 }
1849 
1857 {
1858  select_lex->join= 0;
1859 
1860  if (tmp_join)
1861  {
1862  if (join_tab != tmp_join->join_tab)
1863  {
1864  JoinTable *tab, *end;
1865  for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1866  tab->cleanup();
1867  }
1868  tmp_join->tmp_join= 0;
1869  tmp_table_param.copy_field=0;
1870  return(tmp_join->destroy());
1871  }
1872  cond_equal= 0;
1873 
1874  cleanup(1);
1875  exec_tmp_table1= NULL;
1876  exec_tmp_table2= NULL;
1877  delete select;
1878  keyuse.free();
1879  return error;
1880 }
1881 
1905 {
1906  for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1907  un= un->next_unit())
1908  {
1909  for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1910  {
1911  Item_subselect *subquery_predicate= sl->master_unit()->item;
1912  if (subquery_predicate &&
1913  subquery_predicate->substype() == Item_subselect::IN_SUBS)
1914  {
1915  Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1916  if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1917  in_subs->setup_engine())
1918  return true;
1919  }
1920  }
1921  }
1922  return false;
1923 }
1924 
1968 {
1969  Select_Lex_Unit *tmp_unit;
1970  Select_Lex *sl;
1971  /*
1972  Optimization: if not EXPLAIN and we are done with the Join,
1973  free all tables.
1974  */
1975  bool full= (select_lex->uncacheable.none() && ! session->lex().describe);
1976  bool can_unlock= full;
1977 
1978  cleanup(full);
1979 
1980  for (tmp_unit= select_lex->first_inner_unit();
1981  tmp_unit;
1982  tmp_unit= tmp_unit->next_unit())
1983  for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1984  {
1985  Item_subselect *subselect= sl->master_unit()->item;
1986  bool full_local= full && (!subselect ||
1987  (subselect->is_evaluated() &&
1988  !subselect->is_uncacheable()));
1989  /*
1990  If this join is evaluated, we can fully clean it up and clean up all
1991  its underlying joins even if they are correlated -- they will not be
1992  used any more anyway.
1993  If this join is not yet evaluated, we still must clean it up to
1994  close its table cursors -- it may never get evaluated, as in case of
1995  ... HAVING false OR a IN (SELECT ...))
1996  but all table cursors must be closed before the unlock.
1997  */
1998  sl->cleanup_all_joins(full_local);
1999  /* Can't unlock if at least one Join is still needed */
2000  can_unlock= can_unlock && full_local;
2001  }
2002 
2003  /*
2004  We are not using tables anymore
2005  Unlock all tables. We may be in an INSERT .... SELECT statement.
2006  */
2007  if (can_unlock && lock && session->open_tables.lock &&
2008  !(select_options & SELECT_NO_UNLOCK) &&
2009  !select_lex->subquery_in_having &&
2010  (select_lex == (session->lex().unit.fake_select_lex ?
2011  session->lex().unit.fake_select_lex : &session->lex().select_lex)))
2012  {
2013  /*
2014  TODO: unlock tables even if the join isn't top level select in the
2015  tree.
2016  */
2017  session->unlockReadTables(lock); // Don't free join->lock
2018  lock= 0;
2019  }
2020 
2021  return;
2022 }
2023 
2024 
2036 void Join::cleanup(bool full)
2037 {
2038  if (table)
2039  {
2040  /*
2041  Only a sorted table may be cached. This sorted table is always the
2042  first non const table in join->table
2043  */
2044  if (tables > const_tables) // Test for not-const tables
2045  {
2046  table[const_tables]->free_io_cache();
2047  table[const_tables]->filesort_free_buffers(full);
2048  }
2049  }
2050 
2051  if (join_tab)
2052  {
2053  JoinTable *tab,*end;
2054 
2055  if (full)
2056  {
2057  for (tab= join_tab, end= tab+tables; tab != end; tab++)
2058  tab->cleanup();
2059  table= 0;
2060  }
2061  else
2062  {
2063  for (tab= join_tab, end= tab+tables; tab != end; tab++)
2064  {
2065  if (tab->table)
2066  tab->table->cursor->ha_index_or_rnd_end();
2067  }
2068  }
2069  }
2070 
2071  /*
2072  We are not using tables anymore
2073  Unlock all tables. We may be in an INSERT .... SELECT statement.
2074  */
2075  if (full)
2076  {
2077  if (tmp_join)
2078  tmp_table_param.copy_field= 0;
2079  group_fields.delete_elements();
2080  /*
2081  We can't call delete_elements() on copy_funcs as this will cause
2082  problems in free_elements() as some of the elements are then deleted.
2083  */
2084  tmp_table_param.copy_funcs.clear();
2085  /*
2086  If we have tmp_join and 'this' Join is not tmp_join and
2087  tmp_table_param.copy_field's of them are equal then we have to remove
2088  pointer to tmp_table_param.copy_field from tmp_join, because it qill
2089  be removed in tmp_table_param.cleanup().
2090  */
2091  if (tmp_join &&
2092  tmp_join != this &&
2093  tmp_join->tmp_table_param.copy_field ==
2094  tmp_table_param.copy_field)
2095  {
2096  tmp_join->tmp_table_param.copy_field=
2097  tmp_join->tmp_table_param.save_copy_field= 0;
2098  }
2099  tmp_table_param.cleanup();
2100  }
2101  return;
2102 }
2103 
2104 /*
2105  used only in Join::clear
2106 */
2107 static void clear_tables(Join *join)
2108 {
2109  /*
2110  must clear only the non-const tables, as const tables
2111  are not re-calculated.
2112  */
2113  for (uint32_t i= join->const_tables; i < join->tables; i++)
2114  {
2115  join->table[i]->mark_as_null_row(); // All fields are NULL
2116  }
2117 }
2118 
2129 {
2130  uint32_t func_count, group_parts;
2131 
2132  func_count= tmp_table_param.sum_func_count;
2133  /*
2134  If we are using rollup, we need a copy of the summary functions for
2135  each level
2136  */
2137  if (rollup.getState() != Rollup::STATE_NONE)
2138  func_count*= (send_group_parts+1);
2139 
2140  group_parts= send_group_parts;
2141  /*
2142  If distinct, reserve memory for possible
2143  disctinct->group_by optimization
2144  */
2145  if (select_distinct)
2146  {
2147  group_parts+= fields_list.size();
2148  /*
2149  If the order_st clause is specified then it's possible that
2150  it also will be optimized, so reserve space for it too
2151  */
2152  if (order)
2153  {
2154  Order *ord;
2155  for (ord= order; ord; ord= ord->next)
2156  group_parts++;
2157  }
2158  }
2159 
2160  /* This must use calloc() as rollup_make_fields depends on this */
2161  sum_funcs= (Item_sum**) session->mem.calloc(sizeof(Item_sum**) * (func_count+1) +
2162  sizeof(Item_sum***) * (group_parts+1));
2163  sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
2164  return(sum_funcs == 0);
2165 }
2166 
2181  List<Item> &send_fields,
2182  bool before_group_by,
2183  bool recompute)
2184 {
2185  List<Item>::iterator it(field_list.begin());
2186  Item_sum **func;
2187  Item *item;
2188 
2189  if (*sum_funcs && !recompute)
2190  return false; /* We have already initialized sum_funcs. */
2191 
2192  func= sum_funcs;
2193  while ((item=it++))
2194  {
2195  if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2196  (!((Item_sum*) item)->depended_from() ||
2197  ((Item_sum *)item)->depended_from() == select_lex))
2198  *func++= (Item_sum*) item;
2199  }
2200  if (before_group_by && rollup.getState() == Rollup::STATE_INITED)
2201  {
2202  rollup.setState(Rollup::STATE_READY);
2203  if (rollup_make_fields(field_list, send_fields, &func))
2204  return true; // Should never happen
2205  }
2206  else if (rollup.getState() == Rollup::STATE_NONE)
2207  {
2208  for (uint32_t i=0 ; i <= send_group_parts ;i++)
2209  sum_funcs_end[i]= func;
2210  }
2211  else if (rollup.getState() == Rollup::STATE_READY)
2212  return false; // Don't put end marker
2213  *func=0; // End marker
2214  return false;
2215 }
2216 
2219 {
2220 
2221  tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2222  rollup.setState(Rollup::STATE_INITED);
2223 
2224  /*
2225  Create pointers to the different sum function groups
2226  These are updated by rollup_make_fields()
2227  */
2228  tmp_table_param.group_parts= send_group_parts;
2229 
2230  rollup.setNullItems((Item_null_result**) session->mem.alloc((sizeof(Item*) + sizeof(Item**) + sizeof(List<Item>) + ref_pointer_array_size) * send_group_parts));
2231  rollup.setFields((List<Item>*) (rollup.getNullItems() + send_group_parts));
2232  rollup.setRefPointerArrays((Item***) (rollup.getFields() + send_group_parts));
2233  Item** ref_array= (Item**) (rollup.getRefPointerArrays()+send_group_parts);
2234 
2235  /*
2236  Prepare space for field list for the different levels
2237  These will be filled up in rollup_make_fields()
2238  */
2239  for (uint32_t i= 0 ; i < send_group_parts ; i++)
2240  {
2241  rollup.getNullItems()[i]= new (session->mem) Item_null_result();
2242  List<Item> *rollup_fields= &rollup.getFields()[i];
2243  rollup_fields->clear();
2244  rollup.getRefPointerArrays()[i]= ref_array;
2245  ref_array+= all_fields.size();
2246  }
2247 
2248  for (uint32_t i= 0 ; i < send_group_parts; i++)
2249  {
2250  for (uint32_t j= 0 ; j < fields_list.size() ; j++)
2251  {
2252  rollup.getFields()[i].push_back(rollup.getNullItems()[i]);
2253  }
2254  }
2255 
2256  List<Item>::iterator it(all_fields.begin());
2257  while (Item* item= it++)
2258  {
2259  Order *group_tmp;
2260  bool found_in_group= 0;
2261 
2262  for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2263  {
2264  if (*group_tmp->item == item)
2265  {
2266  item->maybe_null= 1;
2267  found_in_group= 1;
2268  if (item->const_item())
2269  {
2270  /*
2271  For ROLLUP queries each constant item referenced in GROUP BY list
2272  is wrapped up into an Item_func object yielding the same value
2273  as the constant item. The objects of the wrapper class are never
2274  considered as constant items and besides they inherit all
2275  properties of the Item_result_field class.
2276  This wrapping allows us to ensure writing constant items
2277  into temporary tables whenever the result of the ROLLUP
2278  operation has to be written into a temporary table, e.g. when
2279  ROLLUP is used together with DISTINCT in the SELECT list.
2280  Usually when creating temporary tables for a intermidiate
2281  result we do not include fields for constant expressions.
2282  */
2283  Item* new_item= new Item_func_rollup_const(item);
2284  new_item->fix_fields(session, NULL);
2285  *it.ref()= new_item;
2286  for (Order *tmp= group_tmp; tmp; tmp= tmp->next)
2287  {
2288  if (*tmp->item == item)
2289  *tmp->item= new_item;
2290  }
2291  }
2292  }
2293  }
2294  if (item->type() == Item::FUNC_ITEM && !found_in_group)
2295  {
2296  bool changed= false;
2297  if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2298  return 1;
2299  /*
2300  We have to prevent creation of a field in a temporary table for
2301  an expression that contains GROUP BY attributes.
2302  Marking the expression item as 'with_sum_func' will ensure this.
2303  */
2304  if (changed)
2305  item->with_sum_func= 1;
2306  }
2307  }
2308  return 0;
2309 }
2310 
2326 bool Join::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2327 {
2328  List<Item>::iterator it(fields_arg.begin());
2329  Item *first_field= &sel_fields.front();
2330  uint32_t level;
2331 
2332  /*
2333  Create field lists for the different levels
2334 
2335  The idea here is to have a separate field list for each rollup level to
2336  avoid all runtime checks of which columns should be NULL.
2337 
2338  The list is stored in reverse order to get sum function in such an order
2339  in func that it makes it easy to reset them with init_sum_functions()
2340 
2341  Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2342 
2343  rollup.fields[0] will contain list where a,b,c is NULL
2344  rollup.fields[1] will contain list where b,c is NULL
2345  ...
2346  rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2347  ...
2348  sum_funcs_end[0] points to all sum functions
2349  sum_funcs_end[1] points to all sum functions, except grand totals
2350  ...
2351  */
2352 
2353  for (level=0 ; level < send_group_parts ; level++)
2354  {
2355  uint32_t i;
2356  uint32_t pos= send_group_parts - level -1;
2357  bool real_fields= 0;
2358  Item *item;
2359  List<Item>::iterator new_it(rollup.getFields()[pos].begin());
2360  Item **ref_array_start= rollup.getRefPointerArrays()[pos];
2361  Order *start_group;
2362 
2363  /* Point to first hidden field */
2364  Item **ref_array= ref_array_start + fields_arg.size()-1;
2365 
2366  /* Remember where the sum functions ends for the previous level */
2367  sum_funcs_end[pos+1]= *func;
2368 
2369  /* Find the start of the group for this level */
2370  for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2371  {}
2372 
2373  it= fields_arg.begin();
2374  while ((item= it++))
2375  {
2376  if (item == first_field)
2377  {
2378  real_fields= 1; // End of hidden fields
2379  ref_array= ref_array_start;
2380  }
2381 
2382  if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2383  (!((Item_sum*) item)->depended_from() ||
2384  ((Item_sum *)item)->depended_from() == select_lex))
2385 
2386  {
2387  /*
2388  This is a top level summary function that must be replaced with
2389  a sum function that is reset for this level.
2390 
2391  NOTE: This code creates an object which is not that nice in a
2392  sub select. Fortunately it's not common to have rollup in
2393  sub selects.
2394  */
2395  item= item->copy_or_same(session);
2396  ((Item_sum*) item)->make_unique();
2397  *(*func)= (Item_sum*) item;
2398  (*func)++;
2399  }
2400  else
2401  {
2402  /* Check if this is something that is part of this group by */
2403  Order *group_tmp;
2404  for (group_tmp= start_group, i= pos ;
2405  group_tmp ; group_tmp= group_tmp->next, i++)
2406  {
2407  if (*group_tmp->item == item)
2408  {
2409  /*
2410  This is an element that is used by the GROUP BY and should be
2411  set to NULL in this level
2412  */
2413  Item_null_result *null_item= new (session->mem) Item_null_result();
2414  item->maybe_null= 1; // Value will be null sometimes
2415  null_item->result_field= item->get_tmp_table_field();
2416  item= null_item;
2417  break;
2418  }
2419  }
2420  }
2421  *ref_array= item;
2422  if (real_fields)
2423  {
2424  (void) new_it++; // Point to next item
2425  new_it.replace(item); // Replace previous
2426  ref_array++;
2427  }
2428  else
2429  ref_array--;
2430  }
2431  }
2432  sum_funcs_end[0]= *func; // Point to last function
2433  return 0;
2434 }
2435 
2454 int Join::rollup_send_data(uint32_t idx)
2455 {
2456  for (uint32_t i= send_group_parts ; i-- > idx ; )
2457  {
2458  /* Get reference pointers to sum functions in place */
2459  memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i], ref_pointer_array_size);
2460 
2461  if ((!having || having->val_int()))
2462  {
2463  if (send_records < unit->select_limit_cnt && do_send_rows && result->send_data(rollup.getFields()[i]))
2464  {
2465  return 1;
2466  }
2467  send_records++;
2468  }
2469  }
2470  /* Restore ref_pointer_array */
2471  set_items_ref_array(current_ref_pointer_array);
2472 
2473  return 0;
2474 }
2475 
2495 int Join::rollup_write_data(uint32_t idx, Table *table_arg)
2496 {
2497  for (uint32_t i= send_group_parts ; i-- > idx ; )
2498  {
2499  /* Get reference pointers to sum functions in place */
2500  memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i],
2502  if ((!having || having->val_int()))
2503  {
2504  List<Item>::iterator it(rollup.getFields()[i].begin());
2505  while (Item* item= it++)
2506  {
2507  if (item->type() == Item::NULL_ITEM && item->is_result_field())
2508  item->save_in_result_field(1);
2509  }
2510  copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2511  if (table_arg->cursor->insertRecord(table_arg->getInsertRecord()))
2512  {
2513  my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2514  return 1;
2515  }
2516  }
2517  }
2518  /* Restore ref_pointer_array */
2519  set_items_ref_array(current_ref_pointer_array);
2520 
2521  return 0;
2522 }
2523 
2529 {
2530  clear_tables(this);
2531  copy_fields(&tmp_table_param);
2532 
2533  if (sum_funcs)
2534  {
2535  Item_sum *func, **func_ptr= sum_funcs;
2536  while ((func= *(func_ptr++)))
2537  func->clear();
2538  }
2539 }
2540 
2552 {
2553  result= res;
2554  if (result->prepare(fields_list, select_lex->master_unit()))
2555  {
2556  return true;
2557  }
2558  return false;
2559 }
2560 
2566 {
2567  bool cache_flag= false;
2568  bool *analyzer_arg= &cache_flag;
2569 
2570  /* No need in cache if all tables are constant. */
2571  if (const_tables == tables)
2572  return;
2573 
2574  if (conds)
2575  conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2576  &Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2577  cache_flag= false;
2578  if (having)
2579  having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2580  &Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2581 
2582  for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2583  {
2584  if (*tab->on_expr_ref)
2585  {
2586  cache_flag= false;
2587  (*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2588  (unsigned char **)&analyzer_arg,
2590  (unsigned char *)&cache_flag);
2591  }
2592  }
2593 }
2594 
2607 {
2608  bool not_used_in_distinct= join_tab->not_used_in_distinct;
2609  ha_rows found_records= join->found_records;
2610  COND *select_cond= join_tab->select_cond;
2611 
2612  if (error > 0 || (join->session->is_error())) // Fatal error
2613  return NESTED_LOOP_ERROR;
2614  if (error < 0)
2615  return NESTED_LOOP_NO_MORE_ROWS;
2616  if (join->session->getKilled()) // Aborted by user
2617  {
2618  join->session->send_kill_message();
2619  return NESTED_LOOP_KILLED;
2620  }
2621  if (!select_cond || select_cond->val_int())
2622  {
2623  /*
2624  There is no select condition or the attached pushed down
2625  condition is true => a match is found.
2626  */
2627  bool found= 1;
2628  while (join_tab->first_unmatched && found)
2629  {
2630  /*
2631  The while condition is always false if join_tab is not
2632  the last inner join table of an outer join operation.
2633  */
2634  JoinTable *first_unmatched= join_tab->first_unmatched;
2635  /*
2636  Mark that a match for current outer table is found.
2637  This activates push down conditional predicates attached
2638  to the all inner tables of the outer join.
2639  */
2640  first_unmatched->found= 1;
2641  for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2642  {
2643  if (tab->table->reginfo.not_exists_optimize)
2644  return NESTED_LOOP_NO_MORE_ROWS;
2645  /* Check all predicates that has just been activated. */
2646  /*
2647  Actually all predicates non-guarded by first_unmatched->found
2648  will be re-evaluated again. It could be fixed, but, probably,
2649  it's not worth doing now.
2650  */
2651  if (tab->select_cond && !tab->select_cond->val_int())
2652  {
2653  /* The condition attached to table tab is false */
2654  if (tab == join_tab)
2655  found= 0;
2656  else
2657  {
2658  /*
2659  Set a return point if rejected predicate is attached
2660  not to the last table of the current nest level.
2661  */
2662  join->return_tab= tab;
2663  return NESTED_LOOP_OK;
2664  }
2665  }
2666  }
2667  /*
2668  Check whether join_tab is not the last inner table
2669  for another embedding outer join.
2670  */
2671  if ((first_unmatched= first_unmatched->first_upper) &&
2672  first_unmatched->last_inner != join_tab)
2673  first_unmatched= 0;
2674  join_tab->first_unmatched= first_unmatched;
2675  }
2676 
2677  JoinTable *return_tab= join->return_tab;
2678  join_tab->found_match= true;
2679 
2680  /*
2681  It was not just a return to lower loop level when one
2682  of the newly activated predicates is evaluated as false
2683  (See above join->return_tab= tab).
2684  */
2685  join->examined_rows++;
2686  join->session->row_count++;
2687 
2688  if (found)
2689  {
2690  enum enum_nested_loop_state rc;
2691  /* A match from join_tab is found for the current partial join. */
2692  rc= (*join_tab->next_select)(join, join_tab+1, 0);
2693  if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2694  return rc;
2695  if (return_tab < join->return_tab)
2696  join->return_tab= return_tab;
2697 
2698  if (join->return_tab < join_tab)
2699  return NESTED_LOOP_OK;
2700  /*
2701  Test if this was a SELECT DISTINCT query on a table that
2702  was not in the field list; In this case we can abort if
2703  we found a row, as no new rows can be added to the result.
2704  */
2705  if (not_used_in_distinct && found_records != join->found_records)
2706  return NESTED_LOOP_NO_MORE_ROWS;
2707  }
2708  else
2709  join_tab->read_record.cursor->unlock_row();
2710  }
2711  else
2712  {
2713  /*
2714  The condition pushed down to the table join_tab rejects all rows
2715  with the beginning coinciding with the current partial join.
2716  */
2717  join->examined_rows++;
2718  join->session->row_count++;
2719  join_tab->read_record.cursor->unlock_row();
2720  }
2721  return NESTED_LOOP_OK;
2722 }
2723 
2731 {
2732  /*
2733  The table join_tab is the first inner table of a outer join operation
2734  and no matches has been found for the current outer row.
2735  */
2736  JoinTable *last_inner_tab= join_tab->last_inner;
2737  /* Cache variables for faster loop */
2738  COND *select_cond;
2739  for ( ; join_tab <= last_inner_tab ; join_tab++)
2740  {
2741  /* Change the the values of guard predicate variables. */
2742  join_tab->found= 1;
2743  join_tab->not_null_compl= 0;
2744  /* The outer row is complemented by nulls for each inner tables */
2745  join_tab->table->restoreRecordAsDefault(); // Make empty record
2746  join_tab->table->mark_as_null_row(); // For group by without error
2747  select_cond= join_tab->select_cond;
2748  /* Check all attached conditions for inner table rows. */
2749  if (select_cond && !select_cond->val_int())
2750  return NESTED_LOOP_OK;
2751  }
2752  join_tab--;
2753  /*
2754  The row complemented by nulls might be the first row
2755  of embedding outer joins.
2756  If so, perform the same actions as in the code
2757  for the first regular outer join row above.
2758  */
2759  for ( ; ; )
2760  {
2761  JoinTable *first_unmatched= join_tab->first_unmatched;
2762  if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2763  first_unmatched= 0;
2764  join_tab->first_unmatched= first_unmatched;
2765  if (! first_unmatched)
2766  break;
2767  first_unmatched->found= 1;
2768  for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2769  {
2770  if (tab->select_cond && !tab->select_cond->val_int())
2771  {
2772  join->return_tab= tab;
2773  return NESTED_LOOP_OK;
2774  }
2775  }
2776  }
2777  /*
2778  The row complemented by nulls satisfies all conditions
2779  attached to inner tables.
2780  Send the row complemented by nulls to be joined with the
2781  remaining tables.
2782  */
2783  return (*join_tab->next_select)(join, join_tab+1, 0);
2784 }
2785 
2786 enum_nested_loop_state flush_cached_records(Join *join, JoinTable *join_tab, bool skip_last)
2787 {
2788  enum_nested_loop_state rc= NESTED_LOOP_OK;
2789  int error;
2790  ReadRecord *info;
2791 
2792  join_tab->table->null_row= 0;
2793  if (!join_tab->cache.records)
2794  {
2795  return NESTED_LOOP_OK; /* Nothing to do */
2796  }
2797 
2798  if (skip_last)
2799  {
2800  (void) join_tab->cache.store_record_in_cache(); // Must save this for later
2801  }
2802 
2803 
2804  if (join_tab->use_quick == 2)
2805  {
2806  delete join_tab->select->quick;
2807  join_tab->select->quick= 0;
2808  }
2809  /* read through all records */
2810  if ((error=join_init_read_record(join_tab)))
2811  {
2812  join_tab->cache.reset_cache_write();
2813  return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2814  }
2815 
2816  for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2817  {
2818  tmp->status=tmp->table->status;
2819  tmp->table->status=0;
2820  }
2821 
2822  info= &join_tab->read_record;
2823  do
2824  {
2825  if (join->session->getKilled())
2826  {
2827  join->session->send_kill_message();
2828  return NESTED_LOOP_KILLED;
2829  }
2830  optimizer::SqlSelect *select= join_tab->select;
2831  if (rc == NESTED_LOOP_OK &&
2832  (!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2833  {
2834  uint32_t i;
2835  join_tab->cache.reset_cache_read();
2836  for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2837  {
2838  join_tab->readCachedRecord();
2839  if (!select || !select->skip_record())
2840  {
2841  int res= 0;
2842 
2843  rc= (join_tab->next_select)(join,join_tab+1,0);
2844  if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2845  {
2846  join_tab->cache.reset_cache_write();
2847  return rc;
2848  }
2849 
2850  if (res == -1)
2851  return NESTED_LOOP_ERROR;
2852  }
2853  }
2854  }
2855  } while (!(error=info->read_record(info)));
2856 
2857  if (skip_last)
2858  join_tab->readCachedRecord(); // Restore current record
2859  join_tab->cache.reset_cache_write();
2860  if (error > 0) // Fatal error
2861  return NESTED_LOOP_ERROR;
2862  for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2863  tmp2->table->status=tmp2->status;
2864  return NESTED_LOOP_OK;
2865 }
2866 
2867 /*****************************************************************************
2868  DESCRIPTION
2869  Functions that end one nested loop iteration. Different functions
2870  are used to support GROUP BY clause and to redirect records
2871  to a table (e.g. in case of SELECT into a temporary table) or to the
2872  network client.
2873 
2874  RETURN VALUES
2875  NESTED_LOOP_OK - the record has been successfully handled
2876  NESTED_LOOP_ERROR - a fatal error (like table corruption)
2877  was detected
2878  NESTED_LOOP_KILLED - thread shutdown was requested while processing
2879  the record
2880  NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2881  additionally, the nested loop produced the
2882  number of rows specified in the LIMIT clause
2883  for the query
2884  NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2885  additionally, there is a cursor and the nested
2886  loop algorithm produced the number of rows
2887  that is specified for current cursor fetch
2888  operation.
2889  All return values except NESTED_LOOP_OK abort the nested loop.
2890 *****************************************************************************/
2891 enum_nested_loop_state end_send(Join *join, JoinTable *, bool end_of_records)
2892 {
2893  if (! end_of_records)
2894  {
2895  int error;
2896  if (join->having && join->having->val_int() == 0)
2897  return NESTED_LOOP_OK; // Didn't match having
2898  error= 0;
2899  if (join->do_send_rows)
2900  error=join->result->send_data(*join->fields);
2901  if (error)
2902  return NESTED_LOOP_ERROR;
2903  if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2904  {
2905  if (join->select_options & OPTION_FOUND_ROWS)
2906  {
2907  JoinTable *jt=join->join_tab;
2908  if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2909  && !join->send_group_parts && !join->having && !jt->select_cond &&
2910  !(jt->select && jt->select->quick) &&
2911  (jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
2912  (jt->ref.key < 0))
2913  {
2914  /* Join over all rows in table; Return number of found rows */
2915  Table *table= jt->table;
2916 
2917  join->select_options^= OPTION_FOUND_ROWS;
2918  if (table->sort.record_pointers ||
2919  (table->sort.io_cache && table->sort.io_cache->inited()))
2920  {
2921  /* Using filesort */
2922  join->send_records= table->sort.found_records;
2923  }
2924  else
2925  {
2926  table->cursor->info(HA_STATUS_VARIABLE);
2927  join->send_records= table->cursor->stats.records;
2928  }
2929  }
2930  else
2931  {
2932  join->do_send_rows= 0;
2933  if (join->unit->fake_select_lex)
2934  join->unit->fake_select_lex->select_limit= 0;
2935  return NESTED_LOOP_OK;
2936  }
2937  }
2938  return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2939  }
2940  else if (join->send_records >= join->fetch_limit)
2941  {
2942  /*
2943  There is a server side cursor and all rows for
2944  this fetch request are sent.
2945  */
2946  return NESTED_LOOP_CURSOR_LIMIT;
2947  }
2948  }
2949 
2950  return NESTED_LOOP_OK;
2951 }
2952 
2953 enum_nested_loop_state end_write(Join *join, JoinTable *, bool end_of_records)
2954 {
2955  Table *table= join->tmp_table;
2956 
2957  if (join->session->getKilled()) // Aborted by user
2958  {
2959  join->session->send_kill_message();
2960  return NESTED_LOOP_KILLED;
2961  }
2962  if (!end_of_records)
2963  {
2964  copy_fields(&join->tmp_table_param);
2965  if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
2966  return NESTED_LOOP_ERROR;
2967  if (!join->having || join->having->val_int())
2968  {
2969  int error;
2970  join->found_records++;
2971  if ((error=table->cursor->insertRecord(table->getInsertRecord())))
2972  {
2973  if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
2974  {
2975  return NESTED_LOOP_OK;
2976  }
2977 
2978  my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2979  return NESTED_LOOP_ERROR; // Table is_full error
2980  }
2981  if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2982  {
2983  if (!(join->select_options & OPTION_FOUND_ROWS))
2984  return NESTED_LOOP_QUERY_LIMIT;
2985  join->do_send_rows= 0;
2986  join->unit->select_limit_cnt= HA_POS_ERROR;
2987  return NESTED_LOOP_OK;
2988  }
2989  }
2990  }
2991 
2992  return NESTED_LOOP_OK;
2993 }
2994 
2996 enum_nested_loop_state end_update(Join *join, JoinTable *, bool end_of_records)
2997 {
2998  Table *table= join->tmp_table;
2999  Order *group;
3000  int error;
3001 
3002  if (end_of_records)
3003  return NESTED_LOOP_OK;
3004  if (join->session->getKilled()) // Aborted by user
3005  {
3006  join->session->send_kill_message();
3007  return NESTED_LOOP_KILLED;
3008  }
3009 
3010  join->found_records++;
3011  copy_fields(&join->tmp_table_param); // Groups are copied twice.
3012  /* Make a key of group index */
3013  for (group=table->group ; group ; group=group->next)
3014  {
3015  Item *item= *group->item;
3016  item->save_org_in_field(group->field);
3017  /* Store in the used key if the field was 0 */
3018  if (item->maybe_null)
3019  group->buff[-1]= (char) group->field->is_null();
3020  }
3021  if (!table->cursor->index_read_map(table->getUpdateRecord(),
3022  join->tmp_table_param.group_buff,
3023  HA_WHOLE_KEY,
3024  HA_READ_KEY_EXACT))
3025  { /* Update old record */
3026  table->restoreRecord();
3027  update_tmptable_sum_func(join->sum_funcs,table);
3028  if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
3029  table->getInsertRecord())))
3030  {
3031  table->print_error(error,MYF(0));
3032  return NESTED_LOOP_ERROR;
3033  }
3034  return NESTED_LOOP_OK;
3035  }
3036 
3037  /*
3038  Copy null bits from group key to table
3039  We can't copy all data as the key may have different format
3040  as the row data (for example as with VARCHAR keys)
3041  */
3042  KeyPartInfo *key_part;
3043  for (group=table->group,key_part=table->key_info[0].key_part;
3044  group ;
3045  group=group->next,key_part++)
3046  {
3047  if (key_part->null_bit)
3048  memcpy(table->getInsertRecord()+key_part->offset, group->buff, 1);
3049  }
3050  init_tmptable_sum_functions(join->sum_funcs);
3051  if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
3052  return NESTED_LOOP_ERROR;
3053  if ((error=table->cursor->insertRecord(table->getInsertRecord())))
3054  {
3055  my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
3056  return NESTED_LOOP_ERROR; // Table is_full error
3057  }
3058  join->send_records++;
3059  return NESTED_LOOP_OK;
3060 }
3061 
3064 {
3065  Table *table= join->tmp_table;
3066  int error;
3067 
3068  if (end_of_records)
3069  return NESTED_LOOP_OK;
3070  if (join->session->getKilled()) // Aborted by user
3071  {
3072  join->session->send_kill_message();
3073  return NESTED_LOOP_KILLED;
3074  }
3075 
3076  init_tmptable_sum_functions(join->sum_funcs);
3077  copy_fields(&join->tmp_table_param); // Groups are copied twice.
3078  if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
3079  return NESTED_LOOP_ERROR;
3080 
3081  if (!(error= table->cursor->insertRecord(table->getInsertRecord())))
3082  join->send_records++; // New group
3083  else
3084  {
3085  if ((int) table->get_dup_key(error) < 0)
3086  {
3087  table->print_error(error,MYF(0));
3088  return NESTED_LOOP_ERROR;
3089  }
3090  if (table->cursor->rnd_pos(table->getUpdateRecord(),table->cursor->dup_ref))
3091  {
3092  table->print_error(error,MYF(0));
3093  return NESTED_LOOP_ERROR;
3094  }
3095  table->restoreRecord();
3096  update_tmptable_sum_func(join->sum_funcs,table);
3097  if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
3098  table->getInsertRecord())))
3099  {
3100  table->print_error(error,MYF(0));
3101  return NESTED_LOOP_ERROR;
3102  }
3103  }
3104  return NESTED_LOOP_OK;
3105 }
3106 
3119 static bool make_group_fields(Join *main_join, Join *curr_join)
3120 {
3121  if (main_join->group_fields_cache.size())
3122  {
3123  curr_join->group_fields= main_join->group_fields_cache;
3124  curr_join->sort_and_group= 1;
3125  }
3126  else
3127  {
3128  if (alloc_group_fields(curr_join, curr_join->group_list))
3129  return 1;
3130  main_join->group_fields_cache= curr_join->group_fields;
3131  }
3132  return (0);
3133 }
3134 
3138 static void calc_group_buffer(Join *join, Order *group)
3139 {
3140  uint32_t key_length=0, parts=0, null_parts=0;
3141 
3142  if (group)
3143  join->group= 1;
3144  for (; group ; group=group->next)
3145  {
3146  Item *group_item= *group->item;
3147  Field *field= group_item->get_tmp_table_field();
3148  if (field)
3149  {
3150  enum_field_types type;
3151  if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
3152  key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
3153  else if (type == DRIZZLE_TYPE_VARCHAR)
3154  key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3155  else
3156  key_length+= field->pack_length();
3157  }
3158  else
3159  {
3160  switch (group_item->result_type()) {
3161  case REAL_RESULT:
3162  key_length+= sizeof(double);
3163  break;
3164 
3165  case INT_RESULT:
3166  key_length+= sizeof(int64_t);
3167  break;
3168 
3169  case DECIMAL_RESULT:
3170  key_length+= class_decimal_get_binary_size(group_item->max_length -
3171  (group_item->decimals ? 1 : 0),
3172  group_item->decimals);
3173  break;
3174 
3175  case STRING_RESULT:
3176  {
3177  enum enum_field_types type= group_item->field_type();
3178  /*
3179  As items represented as DATE/TIME fields in the group buffer
3180  have STRING_RESULT result type, we increase the length
3181  by 8 as maximum pack length of such fields.
3182  */
3183  if (field::isDateTime(type))
3184  {
3185  key_length+= 8;
3186  }
3187  else
3188  {
3189  /*
3190  Group strings are taken as varstrings and require an length field.
3191  A field is not yet created by create_tmp_field()
3192  and the sizes should match up.
3193  */
3194  key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3195  }
3196 
3197  break;
3198  }
3199 
3200  case ROW_RESULT:
3201  /* This case should never be choosen */
3202  assert(0);
3203  my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3204  }
3205  }
3206 
3207  parts++;
3208 
3209  if (group_item->maybe_null)
3210  null_parts++;
3211  }
3212 
3213  join->tmp_table_param.group_length=key_length+null_parts;
3214  join->tmp_table_param.group_parts=parts;
3215  join->tmp_table_param.group_null_parts=null_parts;
3216 }
3217 
3223 static bool alloc_group_fields(Join *join, Order *group)
3224 {
3225  if (group)
3226  {
3227  for (; group ; group=group->next)
3228  {
3229  Cached_item *tmp= new_Cached_item(join->session, *group->item);
3230  if (!tmp)
3231  return true;
3232  join->group_fields.push_front(tmp);
3233  }
3234  }
3235  join->sort_and_group=1; /* Mark for do_select */
3236  return false;
3237 }
3238 
3239 static uint32_t cache_record_length(Join *join,uint32_t idx)
3240 {
3241  uint32_t length=0;
3242  JoinTable **pos,**end;
3243  Session *session=join->session;
3244 
3245  for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3246  pos != end ;
3247  pos++)
3248  {
3249  JoinTable *join_tab= *pos;
3250  if (!join_tab->used_fieldlength) /* Not calced yet */
3251  calc_used_field_length(session, join_tab);
3252  length+=join_tab->used_fieldlength;
3253  }
3254  return length;
3255 }
3256 
3257 /*
3258  Get the number of different row combinations for subset of partial join
3259 
3260  SYNOPSIS
3261  prev_record_reads()
3262  join The join structure
3263  idx Number of tables in the partial join order (i.e. the
3264  partial join order is in join->positions[0..idx-1])
3265  found_ref Bitmap of tables for which we need to find # of distinct
3266  row combinations.
3267 
3268  DESCRIPTION
3269  Given a partial join order (in join->positions[0..idx-1]) and a subset of
3270  tables within that join order (specified in found_ref), find out how many
3271  distinct row combinations of subset tables will be in the result of the
3272  partial join order.
3273 
3274  This is used as follows: Suppose we have a table accessed with a ref-based
3275  method. The ref access depends on current rows of tables in found_ref.
3276  We want to count # of different ref accesses. We assume two ref accesses
3277  will be different if at least one of access parameters is different.
3278  Example: consider a query
3279 
3280  SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3281 
3282  and a join order:
3283  t1, ref access on t1.key=c1
3284  t2, ref access on t2.key=c2
3285  t3, ref access on t3.key=t1.field
3286 
3287  For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3288  For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3289  For t3: n_ref_scans = records_read(t1)*records_read(t2)
3290  n_distinct_ref_scans = #records_read(t1)
3291 
3292  The reason for having this function (at least the latest version of it)
3293  is that we need to account for buffering in join execution.
3294 
3295  An edge-case example: if we have a non-first table in join accessed via
3296  ref(const) or ref(param) where there is a small number of different
3297  values of param, then the access will likely hit the disk cache and will
3298  not require any disk seeks.
3299 
3300  The proper solution would be to assume an LRU disk cache of some size,
3301  calculate probability of cache hits, etc. For now we just count
3302  identical ref accesses as one.
3303 
3304  RETURN
3305  Expected number of row combinations
3306 */
3307 static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref)
3308 {
3309  double found=1.0;
3310  optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3311  for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3312  pos != pos_end;
3313  pos--)
3314  {
3315  if (pos->examinePosition(found_ref))
3316  {
3317  found_ref|= pos->getRefDependMap();
3318  /*
3319  For the case of "t1 LEFT Join t2 ON ..." where t2 is a const table
3320  with no matching row we will get position[t2].records_read==0.
3321  Actually the size of output is one null-complemented row, therefore
3322  we will use value of 1 whenever we get records_read==0.
3323 
3324  Note
3325  - the above case can't occur if inner part of outer join has more
3326  than one table: table with no matches will not be marked as const.
3327 
3328  - Ideally we should add 1 to records_read for every possible null-
3329  complemented row. We're not doing it because: 1. it will require
3330  non-trivial code and add overhead. 2. The value of records_read
3331  is an inprecise estimate and adding 1 (or, in the worst case,
3332  #max_nested_outer_joins=64-1) will not make it any more precise.
3333  */
3334  if (pos->getFanout() > DBL_EPSILON)
3335  found*= pos->getFanout();
3336  }
3337  }
3338  return found;
3339 }
3340 
3344 static bool get_best_combination(Join *join)
3345 {
3346  uint32_t i,tablenr;
3347  table_map used_tables;
3348  JoinTable *join_tab,*j;
3349  optimizer::KeyUse *keyuse;
3350  uint32_t table_count;
3351  Session *session=join->session;
3352  optimizer::Position cur_pos;
3353 
3354  table_count=join->tables;
3355  join->join_tab=join_tab= new (session->mem) JoinTable[table_count];
3356  join->full_join=0;
3357 
3358  used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3359  for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3360  {
3361  Table *form;
3362  cur_pos= join->getPosFromOptimalPlan(tablenr);
3363  *j= *cur_pos.getJoinTable();
3364  form=join->table[tablenr]=j->table;
3365  used_tables|= form->map;
3366  form->reginfo.join_tab=j;
3367  if (!*j->on_expr_ref)
3368  form->reginfo.not_exists_optimize=0; // Only with LEFT Join
3369  if (j->type == AM_CONST)
3370  continue; // Handled in make_join_stat..
3371 
3372  j->ref.key = -1;
3373  j->ref.key_parts=0;
3374 
3375  if (j->type == AM_SYSTEM)
3376  continue;
3377  if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3378  {
3379  j->type= AM_ALL;
3380  if (tablenr != join->const_tables)
3381  join->full_join=1;
3382  }
3383  else if (create_ref_for_key(join, j, keyuse, used_tables))
3384  return true; // Something went wrong
3385  }
3386 
3387  for (i=0 ; i < table_count ; i++)
3388  join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3389  update_depend_map(join);
3390  return 0;
3391 }
3392 
3394 static void set_position(Join *join,
3395  uint32_t idx,
3396  JoinTable *table,
3397  optimizer::KeyUse *key)
3398 {
3399  optimizer::Position tmp_pos(1.0, /* This is a const table */
3400  0.0,
3401  table,
3402  key,
3403  0);
3404  join->setPosInPartialPlan(idx, tmp_pos);
3405 
3406  /* Move the const table as down as possible in best_ref */
3407  JoinTable **pos=join->best_ref+idx+1;
3408  JoinTable *next=join->best_ref[idx];
3409  for (;next != table ; pos++)
3410  {
3411  JoinTable *tmp=pos[0];
3412  pos[0]=next;
3413  next=tmp;
3414  }
3415  join->best_ref[idx]=table;
3416 }
3417 
3436 static bool choose_plan(Join *join, table_map join_tables)
3437 {
3438  uint32_t search_depth= join->session->variables.optimizer_search_depth;
3439  uint32_t prune_level= join->session->variables.optimizer_prune_level;
3440  bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3441 
3442  join->cur_embedding_map.reset();
3444  /*
3445  if (SELECT_STRAIGHT_JOIN option is set)
3446  reorder tables so dependent tables come after tables they depend
3447  on, otherwise keep tables in the order they were specified in the query
3448  else
3449  Apply heuristic: pre-sort all access plans with respect to the number of
3450  records accessed.
3451  */
3452  internal::my_qsort(join->best_ref + join->const_tables,
3453  join->tables - join->const_tables, sizeof(JoinTable*),
3454  straight_join ? join_tab_cmp_straight : join_tab_cmp);
3455  if (straight_join)
3456  {
3457  optimize_straight_join(join, join_tables);
3458  }
3459  else
3460  {
3461  if (search_depth == 0)
3462  /* Automatically determine a reasonable value for 'search_depth' */
3463  search_depth= determine_search_depth(join);
3464  if (greedy_search(join, join_tables, search_depth, prune_level))
3465  return true;
3466  }
3467 
3468  /*
3469  Store the cost of this query into a user variable
3470  Don't update last_query_cost for statements that are not "flat joins" :
3471  i.e. they have subqueries, unions or call stored procedures.
3472  TODO: calculate a correct cost for a query with subqueries and UNIONs.
3473  */
3474  if (join->session->lex().is_single_level_stmt())
3475  join->session->status_var.last_query_cost= join->best_read;
3476  return false;
3477 }
3478 
3503 static void best_access_path(Join *join,
3504  JoinTable *s,
3505  Session *session,
3506  table_map remaining_tables,
3507  uint32_t idx,
3508  double record_count,
3509  double)
3510 {
3511  optimizer::KeyUse *best_key= NULL;
3512  uint32_t best_max_key_part= 0;
3513  bool found_constraint= 0;
3514  double best= DBL_MAX;
3515  double best_time= DBL_MAX;
3516  double records= DBL_MAX;
3517  table_map best_ref_depends_map= 0;
3518  double tmp;
3519  ha_rows rec;
3520 
3521  if (s->keyuse)
3522  { /* Use key if possible */
3523  Table *table= s->table;
3524  optimizer::KeyUse *keyuse= NULL;
3525  optimizer::KeyUse *start_key= NULL;
3526  double best_records= DBL_MAX;
3527  uint32_t max_key_part=0;
3528 
3529  /* Test how we can use keys */
3530  rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3531  for (keyuse= s->keyuse; keyuse->getTable() == table; )
3532  {
3533  key_part_map found_part= 0;
3534  table_map found_ref= 0;
3535  uint32_t key= keyuse->getKey();
3536  KeyInfo *keyinfo= table->key_info + key;
3537  /* Bitmap of keyparts where the ref access is over 'keypart=const': */
3538  key_part_map const_part= 0;
3539  /* The or-null keypart in ref-or-null access: */
3540  key_part_map ref_or_null_part= 0;
3541 
3542  /* Calculate how many key segments of the current key we can use */
3543  start_key= keyuse;
3544 
3545  do /* For each keypart */
3546  {
3547  uint32_t keypart= keyuse->getKeypart();
3548  table_map best_part_found_ref= 0;
3549  double best_prev_record_reads= DBL_MAX;
3550 
3551  do /* For each way to access the keypart */
3552  {
3553 
3554  /*
3555  if 1. expression doesn't refer to forward tables
3556  2. we won't get two ref-or-null's
3557  */
3558  if (! (remaining_tables & keyuse->getUsedTables()) &&
3559  ! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3560  KEY_OPTIMIZE_REF_OR_NULL)))
3561  {
3562  found_part|= keyuse->getKeypartMap();
3563  if (! (keyuse->getUsedTables() & ~join->const_table_map))
3564  const_part|= keyuse->getKeypartMap();
3565 
3566  double tmp2= prev_record_reads(join, idx, (found_ref |
3567  keyuse->getUsedTables()));
3568  if (tmp2 < best_prev_record_reads)
3569  {
3570  best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
3571  best_prev_record_reads= tmp2;
3572  }
3573  if (rec > keyuse->getTableRows())
3574  rec= keyuse->getTableRows();
3575  /*
3576  If there is one 'key_column IS NULL' expression, we can
3577  use this ref_or_null optimisation of this field
3578  */
3579  if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3580  ref_or_null_part|= keyuse->getKeypartMap();
3581  }
3582 
3583  keyuse++;
3584  } while (keyuse->getTable() == table && keyuse->getKey() == key &&
3585  keyuse->getKeypart() == keypart);
3586  found_ref|= best_part_found_ref;
3587  } while (keyuse->getTable() == table && keyuse->getKey() == key);
3588 
3589  /*
3590  Assume that that each key matches a proportional part of table.
3591  */
3592  if (!found_part)
3593  continue; // Nothing usable found
3594 
3595  if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3596  rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3597 
3598  {
3599  found_constraint= 1;
3600 
3601  /*
3602  Check if we found full key
3603  */
3604  if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3605  !ref_or_null_part)
3606  { /* use eq key */
3607  max_key_part= UINT32_MAX;
3608  if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3609  {
3610  tmp = prev_record_reads(join, idx, found_ref);
3611  records=1.0;
3612  }
3613  else
3614  {
3615  if (!found_ref)
3616  { /* We found a const key */
3617  /*
3618  ReuseRangeEstimateForRef-1:
3619  We get here if we've found a ref(const) (c_i are constants):
3620  "(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3621 
3622  If range optimizer was able to construct a "range"
3623  access on this index, then its condition "quick_cond" was
3624  eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3625  from the range optimizer.
3626 
3627  Proof of (*): By properties of range and ref optimizers
3628  quick_cond will be equal or tighther than ref_const_cond.
3629  ref_const_cond already covers "smallest" possible interval -
3630  a singlepoint interval over all keyparts. Therefore,
3631  quick_cond is equivalent to ref_const_cond (if it was an
3632  empty interval we wouldn't have got here).
3633  */
3634  if (table->quick_keys.test(key))
3635  records= (double) table->quick_rows[key];
3636  else
3637  {
3638  /* quick_range couldn't use key! */
3639  records= (double) s->records/rec;
3640  }
3641  }
3642  else
3643  {
3644  if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3645  { /* Prefer longer keys */
3646  records=
3647  ((double) s->records / (double) rec *
3648  (1.0 +
3649  ((double) (table->getShare()->max_key_length-keyinfo->key_length) /
3650  (double) table->getShare()->max_key_length)));
3651  if (records < 2.0)
3652  records=2.0; /* Can't be as good as a unique */
3653  }
3654  /*
3655  ReuseRangeEstimateForRef-2: We get here if we could not reuse
3656  E(#rows) from range optimizer. Make another try:
3657 
3658  If range optimizer produced E(#rows) for a prefix of the ref
3659  access we're considering, and that E(#rows) is lower then our
3660  current estimate, make an adjustment. The criteria of when we
3661  can make an adjustment is a special case of the criteria used
3662  in ReuseRangeEstimateForRef-3.
3663  */
3664  if (table->quick_keys.test(key) &&
3665  const_part & (1 << table->quick_key_parts[key]) &&
3666  table->quick_n_ranges[key] == 1 &&
3667  records > (double) table->quick_rows[key])
3668  {
3669  records= (double) table->quick_rows[key];
3670  }
3671  }
3672  /* Limit the number of matched rows */
3673  tmp= records;
3674  set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3675  if (table->covering_keys.test(key))
3676  {
3677  /* we can use only index tree */
3678  tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3679  }
3680  else
3681  tmp= record_count * min(tmp,s->worst_seeks);
3682  }
3683  }
3684  else
3685  {
3686  /*
3687  Use as much key-parts as possible and a uniq key is better
3688  than a not unique key
3689  Set tmp to (previous record count) * (records / combination)
3690  */
3691  if ((found_part & 1) &&
3692  (!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
3693  found_part == PREV_BITS(uint, keyinfo->key_parts)))
3694  {
3695  max_key_part= max_part_bit(found_part);
3696  /*
3697  ReuseRangeEstimateForRef-3:
3698  We're now considering a ref[or_null] access via
3699  (t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3700  (same-as-above but with one cond replaced
3701  with "t.keypart_i IS NULL")] (**)
3702 
3703  Try re-using E(#rows) from "range" optimizer:
3704  We can do so if "range" optimizer used the same intervals as
3705  in (**). The intervals used by range optimizer may be not
3706  available at this point (as "range" access might have choosen to
3707  create quick select over another index), so we can't compare
3708  them to (**). We'll make indirect judgements instead.
3709  The sufficient conditions for re-use are:
3710  (C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3711  this is not satisfied we have no way to know which ranges
3712  will be actually scanned by 'ref' until we execute the
3713  join)
3714  (C2) max #key parts in 'range' access == K == max_key_part (this
3715  is apparently a necessary requirement)
3716 
3717  We also have a property that "range optimizer produces equal or
3718  tighter set of scan intervals than ref(const) optimizer". Each
3719  of the intervals in (**) are "tightest possible" intervals when
3720  one limits itself to using keyparts 1..K (which we do in #2).
3721  From here it follows that range access used either one, or
3722  both of the (I1) and (I2) intervals:
3723 
3724  (t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3725  (same-as-above but with one cond replaced
3726  with "t.keypart_i IS NULL") (I2)
3727 
3728  The remaining part is to exclude the situation where range
3729  optimizer used one interval while we're considering
3730  ref-or-null and looking for estimate for two intervals. This
3731  is done by last limitation:
3732 
3733  (C3) "range optimizer used (have ref_or_null?2:1) intervals"
3734  */
3735  if (table->quick_keys.test(key) && !found_ref && //(C1)
3736  table->quick_key_parts[key] == max_key_part && //(C2)
3737  table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3738  {
3739  tmp= records= (double) table->quick_rows[key];
3740  }
3741  else
3742  {
3743  /* Check if we have statistic about the distribution */
3744  if ((records= keyinfo->rec_per_key[max_key_part-1]))
3745  {
3746  /*
3747  Fix for the case where the index statistics is too
3748  optimistic: If
3749  (1) We're considering ref(const) and there is quick select
3750  on the same index,
3751  (2) and that quick select uses more keyparts (i.e. it will
3752  scan equal/smaller interval then this ref(const))
3753  (3) and E(#rows) for quick select is higher then our
3754  estimate,
3755  Then
3756  We'll use E(#rows) from quick select.
3757 
3758  Q: Why do we choose to use 'ref'? Won't quick select be
3759  cheaper in some cases ?
3760  TODO: figure this out and adjust the plan choice if needed.
3761  */
3762  if (!found_ref && table->quick_keys.test(key) && // (1)
3763  table->quick_key_parts[key] > max_key_part && // (2)
3764  records < (double)table->quick_rows[key]) // (3)
3765  records= (double)table->quick_rows[key];
3766 
3767  tmp= records;
3768  }
3769  else
3770  {
3771  /*
3772  Assume that the first key part matches 1% of the cursor
3773  and that the whole key matches 10 (duplicates) or 1
3774  (unique) records.
3775  Assume also that more key matches proportionally more
3776  records
3777  This gives the formula:
3778  records = (x * (b-a) + a*c-b)/(c-1)
3779 
3780  b = records matched by whole key
3781  a = records matched by first key part (1% of all records?)
3782  c = number of key parts in key
3783  x = used key parts (1 <= x <= c)
3784  */
3785  double rec_per_key;
3786  if (!(rec_per_key=(double)
3787  keyinfo->rec_per_key[keyinfo->key_parts-1]))
3788  rec_per_key=(double) s->records/rec+1;
3789 
3790  if (!s->records)
3791  tmp = 0;
3792  else if (rec_per_key/(double) s->records >= 0.01)
3793  tmp = rec_per_key;
3794  else
3795  {
3796  double a=s->records*0.01;
3797  if (keyinfo->key_parts > 1)
3798  tmp= (max_key_part * (rec_per_key - a) +
3799  a*keyinfo->key_parts - rec_per_key)/
3800  (keyinfo->key_parts-1);
3801  else
3802  tmp= a;
3803  set_if_bigger(tmp,1.0);
3804  }
3805  records = (uint32_t) tmp;
3806  }
3807 
3808  if (ref_or_null_part)
3809  {
3810  /* We need to do two key searches to find key */
3811  tmp *= 2.0;
3812  records *= 2.0;
3813  }
3814 
3815  /*
3816  ReuseRangeEstimateForRef-4: We get here if we could not reuse
3817  E(#rows) from range optimizer. Make another try:
3818 
3819  If range optimizer produced E(#rows) for a prefix of the ref
3820  access we're considering, and that E(#rows) is lower then our
3821  current estimate, make the adjustment.
3822 
3823  The decision whether we can re-use the estimate from the range
3824  optimizer is the same as in ReuseRangeEstimateForRef-3,
3825  applied to first table->quick_key_parts[key] key parts.
3826  */
3827  if (table->quick_keys.test(key) &&
3828  table->quick_key_parts[key] <= max_key_part &&
3829  const_part & (1 << table->quick_key_parts[key]) &&
3830  table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3831  const_part) ? 1 : 0) &&
3832  records > (double) table->quick_rows[key])
3833  {
3834  tmp= records= (double) table->quick_rows[key];
3835  }
3836  }
3837 
3838  /* Limit the number of matched rows */
3839  set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3840  if (table->covering_keys.test(key))
3841  {
3842  /* we can use only index tree */
3843  tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3844  }
3845  else
3846  tmp= record_count * min(tmp,s->worst_seeks);
3847  }
3848  else
3849  tmp= best_time; // Do nothing
3850  }
3851 
3852  }
3853  if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3854  {
3855  best_time= tmp + records/(double) TIME_FOR_COMPARE;
3856  best= tmp;
3857  best_records= records;
3858  best_key= start_key;
3859  best_max_key_part= max_key_part;
3860  best_ref_depends_map= found_ref;
3861  }
3862  }
3863  records= best_records;
3864  }
3865 
3866  /*
3867  Don't test table scan if it can't be better.
3868  Prefer key lookup if we would use the same key for scanning.
3869 
3870  Don't do a table scan on InnoDB tables, if we can read the used
3871  parts of the row from any of the used index.
3872  This is because table scans uses index and we would not win
3873  anything by using a table scan.
3874 
3875  A word for word translation of the below if-statement in sergefp's
3876  understanding: we check if we should use table scan if:
3877  (1) The found 'ref' access produces more records than a table scan
3878  (or index scan, or quick select), or 'ref' is more expensive than
3879  any of them.
3880  (2) This doesn't hold: the best way to perform table scan is to to perform
3881  'range' access using index IDX, and the best way to perform 'ref'
3882  access is to use the same index IDX, with the same or more key parts.
3883  (note: it is not clear how this rule is/should be extended to
3884  index_merge quick selects)
3885  (3) See above note about InnoDB.
3886  (4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3887  path, but there is no quick select)
3888  If the condition in the above brackets holds, then the only possible
3889  "table scan" access method is ALL/index (there is no quick select).
3890  Since we have a 'ref' access path, and FORCE INDEX instructs us to
3891  choose it over ALL/index, there is no need to consider a full table
3892  scan.
3893  */
3894  if ((records >= s->found_records || best > s->read_time) && // (1)
3895  ! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)
3896  best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3897  ! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) && // (3)
3898  ! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3899  ! (s->table->force_index && best_key && !s->quick)) // (4)
3900  { // Check full join
3901  ha_rows rnd_records= s->found_records;
3902  /*
3903  If there is a filtering condition on the table (i.e. ref analyzer found
3904  at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3905  preceding this table in the join order we're now considering), then
3906  assume that 25% of the rows will be filtered out by this condition.
3907 
3908  This heuristic is supposed to force tables used in exprZ to be before
3909  this table in join order.
3910  */
3911  if (found_constraint)
3912  rnd_records-= rnd_records/4;
3913 
3914  /*
3915  If applicable, get a more accurate estimate. Don't use the two
3916  heuristics at once.
3917  */
3918  if (s->table->quick_condition_rows != s->found_records)
3919  rnd_records= s->table->quick_condition_rows;
3920 
3921  /*
3922  Range optimizer never proposes a RANGE if it isn't better
3923  than FULL: so if RANGE is present, it's always preferred to FULL.
3924  Here we estimate its cost.
3925  */
3926  if (s->quick)
3927  {
3928  /*
3929  For each record we:
3930  - read record range through 'quick'
3931  - skip rows which does not satisfy WHERE constraints
3932  TODO:
3933  We take into account possible use of join cache for ALL/index
3934  access (see first else-branch below), but we don't take it into
3935  account here for range/index_merge access. Find out why this is so.
3936  */
3937  tmp= record_count *
3938  (s->quick->read_time +
3939  (s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3940  }
3941  else
3942  {
3943  /* Estimate cost of reading table. */
3944  tmp= s->table->cursor->scan_time();
3945  if (s->table->map & join->outer_join) // Can't use join cache
3946  {
3947  /*
3948  For each record we have to:
3949  - read the whole table record
3950  - skip rows which does not satisfy join condition
3951  */
3952  tmp= record_count *
3953  (tmp +
3954  (s->records - rnd_records)/(double) TIME_FOR_COMPARE);
3955  }
3956  else
3957  {
3958  /* We read the table as many times as join buffer becomes full. */
3959  tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
3960  record_count /
3961  (double) session->variables.join_buff_size));
3962  /*
3963  We don't make full cartesian product between rows in the scanned
3964  table and existing records because we skip all rows from the
3965  scanned table, which does not satisfy join condition when
3966  we read the table (see flush_cached_records for details). Here we
3967  take into account cost to read and skip these records.
3968  */
3969  tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
3970  }
3971  }
3972 
3973  /*
3974  We estimate the cost of evaluating WHERE clause for found records
3975  as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
3976  tmp give us total cost of using Table SCAN
3977  */
3978  if (best == DBL_MAX ||
3979  (tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
3980  best + record_count/(double) TIME_FOR_COMPARE*records))
3981  {
3982  /*
3983  If the table has a range (s->quick is set) make_join_select()
3984  will ensure that this will be used
3985  */
3986  best= tmp;
3987  records= rnd_records;
3988  best_key= 0;
3989  /* range/index_merge/ALL/index access method are "independent", so: */
3990  best_ref_depends_map= 0;
3991  }
3992  }
3993 
3994  /* Update the cost information for the current partial plan */
3995  optimizer::Position tmp_pos(records,
3996  best,
3997  s,
3998  best_key,
3999  best_ref_depends_map);
4000  join->setPosInPartialPlan(idx, tmp_pos);
4001 
4002  if (!best_key &&
4003  idx == join->const_tables &&
4004  s->table == join->sort_by_table &&
4005  join->unit->select_limit_cnt >= records)
4006  join->sort_by_table= (Table*) 1; // Must use temporary table
4007 
4008  return;
4009 }
4010 
4033 static void optimize_straight_join(Join *join, table_map join_tables)
4034 {
4035  JoinTable *s;
4036  optimizer::Position partial_pos;
4037  uint32_t idx= join->const_tables;
4038  double record_count= 1.0;
4039  double read_time= 0.0;
4040 
4041  for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4042  {
4043  /* Find the best access method from 's' to the current partial plan */
4044  best_access_path(join, s, join->session, join_tables, idx,
4045  record_count, read_time);
4046  /* compute the cost of the new plan extended with 's' */
4047  partial_pos= join->getPosFromPartialPlan(idx);
4048  record_count*= partial_pos.getFanout();
4049  read_time+= partial_pos.getCost();
4050  join_tables&= ~(s->table->map);
4051  ++idx;
4052  }
4053 
4054  read_time+= record_count / (double) TIME_FOR_COMPARE;
4055  partial_pos= join->getPosFromPartialPlan(join->const_tables);
4056  if (join->sort_by_table &&
4057  partial_pos.hasTableForSorting(join->sort_by_table))
4058  read_time+= record_count; // We have to make a temp table
4059  join->copyPartialPlanIntoOptimalPlan(idx);
4060  join->best_read= read_time;
4061 }
4062 
4143 static bool greedy_search(Join *join,
4144  table_map remaining_tables,
4145  uint32_t search_depth,
4146  uint32_t prune_level)
4147 {
4148  double record_count= 1.0;
4149  double read_time= 0.0;
4150  uint32_t idx= join->const_tables; // index into 'join->best_ref'
4151  uint32_t best_idx;
4152  uint32_t size_remain; // cardinality of remaining_tables
4153  optimizer::Position best_pos;
4154  JoinTable *best_table; // the next plan node to be added to the curr QEP
4155 
4156  /* number of tables that remain to be optimized */
4157  size_remain= internal::my_count_bits(remaining_tables);
4158 
4159  do {
4160  /* Find the extension of the current QEP with the lowest cost */
4161  join->best_read= DBL_MAX;
4162  if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
4163  read_time, search_depth, prune_level))
4164  return true;
4165 
4166  if (size_remain <= search_depth)
4167  {
4168  /*
4169  'join->best_positions' contains a complete optimal extension of the
4170  current partial QEP.
4171  */
4172  return false;
4173  }
4174 
4175  /* select the first table in the optimal extension as most promising */
4176  best_pos= join->getPosFromOptimalPlan(idx);
4177  best_table= best_pos.getJoinTable();
4178  /*
4179  Each subsequent loop of 'best_extension_by_limited_search' uses
4180  'join->positions' for cost estimates, therefore we have to update its
4181  value.
4182  */
4183  join->setPosInPartialPlan(idx, best_pos);
4184 
4185  /*
4186  We need to make best_extension_by_limited_search aware of the fact
4187  that it's not starting from top level, but from a rather specific
4188  position in the list of nested joins.
4189  */
4190  check_interleaving_with_nj (best_table);
4191 
4192 
4193 
4194  /* find the position of 'best_table' in 'join->best_ref' */
4195  best_idx= idx;
4196  JoinTable *pos= join->best_ref[best_idx];
4197  while (pos && best_table != pos)
4198  pos= join->best_ref[++best_idx];
4199  assert((pos != NULL)); // should always find 'best_table'
4200  /* move 'best_table' at the first free position in the array of joins */
4201  std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4202 
4203  /* compute the cost of the new plan extended with 'best_table' */
4204  optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
4205  record_count*= partial_pos.getFanout();
4206  read_time+= partial_pos.getCost();
4207 
4208  remaining_tables&= ~(best_table->table->map);
4209  --size_remain;
4210  ++idx;
4211  } while (true);
4212 }
4213 
4214 
4332  table_map remaining_tables,
4333  uint32_t idx,
4334  double record_count,
4335  double read_time,
4336  uint32_t search_depth,
4337  uint32_t prune_level)
4338 {
4339  Session *session= join->session;
4340  if (session->getKilled()) // Abort
4341  return true;
4342 
4343  /*
4344  'join' is a partial plan with lower cost than the best plan so far,
4345  so continue expanding it further with the tables in 'remaining_tables'.
4346  */
4347  JoinTable *s;
4348  double best_record_count= DBL_MAX;
4349  double best_read_time= DBL_MAX;
4350  optimizer::Position partial_pos;
4351 
4352  for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4353  {
4354  table_map real_table_bit= s->table->map;
4355  if ((remaining_tables & real_table_bit) &&
4356  ! (remaining_tables & s->dependent) &&
4357  (! idx || ! check_interleaving_with_nj(s)))
4358  {
4359  double current_record_count, current_read_time;
4360 
4361  /*
4362  psergey-insideout-todo:
4363  when best_access_path() detects it could do an InsideOut scan or
4364  some other scan, have it return an insideout scan and a flag that
4365  requests to "fork" this loop iteration. (Q: how does that behave
4366  when the depth is insufficient??)
4367  */
4368  /* Find the best access method from 's' to the current partial plan */
4369  best_access_path(join, s, session, remaining_tables, idx,
4370  record_count, read_time);
4371  /* Compute the cost of extending the plan with 's' */
4372  partial_pos= join->getPosFromPartialPlan(idx);
4373  current_record_count= record_count * partial_pos.getFanout();
4374  current_read_time= read_time + partial_pos.getCost();
4375 
4376  /* Expand only partial plans with lower cost than the best QEP so far */
4377  if ((current_read_time +
4378  current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4379  {
4381  continue;
4382  }
4383 
4384  /*
4385  Prune some less promising partial plans. This heuristic may miss
4386  the optimal QEPs, thus it results in a non-exhaustive search.
4387  */
4388  if (prune_level == 1)
4389  {
4390  if (best_record_count > current_record_count ||
4391  best_read_time > current_read_time ||
4392  (idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4393  {
4394  if (best_record_count >= current_record_count &&
4395  best_read_time >= current_read_time &&
4396  /* TODO: What is the reasoning behind this condition? */
4397  (! (s->key_dependent & remaining_tables) ||
4398  partial_pos.isConstTable()))
4399  {
4400  best_record_count= current_record_count;
4401  best_read_time= current_read_time;
4402  }
4403  }
4404  else
4405  {
4407  continue;
4408  }
4409  }
4410 
4411  if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4412  { /* Recursively expand the current partial plan */
4413  std::swap(join->best_ref[idx], *pos);
4415  remaining_tables & ~real_table_bit,
4416  idx + 1,
4417  current_record_count,
4418  current_read_time,
4419  search_depth - 1,
4420  prune_level))
4421  return true;
4422  std::swap(join->best_ref[idx], *pos);
4423  }
4424  else
4425  { /*
4426  'join' is either the best partial QEP with 'search_depth' relations,
4427  or the best complete QEP so far, whichever is smaller.
4428  */
4429  partial_pos= join->getPosFromPartialPlan(join->const_tables);
4430  current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4431  if (join->sort_by_table &&
4432  partial_pos.hasTableForSorting(join->sort_by_table))
4433  /* We have to make a temp table */
4434  current_read_time+= current_record_count;
4435  if ((search_depth == 1) || (current_read_time < join->best_read))
4436  {
4437  join->copyPartialPlanIntoOptimalPlan(idx + 1);
4438  join->best_read= current_read_time - 0.001;
4439  }
4440  }
4442  }
4443  }
4444  return false;
4445 }
4446 
4478 static uint32_t determine_search_depth(Join *join)
4479 {
4480  uint32_t table_count= join->tables - join->const_tables;
4481  uint32_t search_depth;
4482  /* TODO: this value should be determined dynamically, based on statistics: */
4483  uint32_t max_tables_for_exhaustive_opt= 7;
4484 
4485  if (table_count <= max_tables_for_exhaustive_opt)
4486  search_depth= table_count+1; // use exhaustive for small number of tables
4487  else
4488  /*
4489  TODO: this value could be determined by some mapping of the form:
4490  depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4491  */
4492  search_depth= max_tables_for_exhaustive_opt; // use greedy search
4493 
4494  return search_depth;
4495 }
4496 
4497 static void make_simple_join(Join *join,Table *tmp_table)
4498 {
4499  /*
4500  Reuse Table * and JoinTable if already allocated by a previous call
4501  to this function through Join::exec (may happen for sub-queries).
4502  */
4503  if (!join->table_reexec)
4504  {
4505  join->table_reexec= new (join->session->mem) Table*;
4506  if (join->tmp_join)
4507  join->tmp_join->table_reexec= join->table_reexec;
4508  }
4509  if (!join->join_tab_reexec)
4510  {
4511  join->join_tab_reexec= new (join->session->mem) JoinTable;
4512  if (join->tmp_join)
4513  join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4514  }
4515  Table** tableptr= join->table_reexec;
4516  JoinTable* join_tab= join->join_tab_reexec;
4517 
4518  join->join_tab=join_tab;
4519  join->table=tableptr; tableptr[0]=tmp_table;
4520  join->tables=1;
4521  join->const_tables=0;
4522  join->const_table_map=0;
4523  join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4524  join->tmp_table_param.func_count=0;
4525  join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4526  join->first_record=join->sort_and_group=0;
4527  join->send_records=(ha_rows) 0;
4528  join->group=0;
4529  join->row_limit=join->unit->select_limit_cnt;
4530  join->do_send_rows = (join->row_limit) ? 1 : 0;
4531 
4532  join_tab->table=tmp_table;
4533  join_tab->select=0;
4534  join_tab->select_cond=0;
4535  join_tab->quick=0;
4536  join_tab->type= AM_ALL; /* Map through all records */
4537  join_tab->keys.set(); /* test everything in quick */
4538  join_tab->info=0;
4539  join_tab->on_expr_ref=0;
4540  join_tab->last_inner= 0;
4541  join_tab->first_unmatched= 0;
4542  join_tab->ref.key = -1;
4543  join_tab->not_used_in_distinct=0;
4544  join_tab->read_first_record= join_init_read_record;
4545  join_tab->join=join;
4546  join_tab->ref.key_parts= 0;
4547  join_tab->read_record.init();
4548  tmp_table->status=0;
4549  tmp_table->null_row=0;
4550 }
4551 
4593 static void make_outerjoin_info(Join *join)
4594 {
4595  for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4596  {
4597  JoinTable *tab=join->join_tab+i;
4598  Table *table=tab->table;
4599  TableList *tbl= table->pos_in_table_list;
4600  TableList *embedding= tbl->getEmbedding();
4601 
4602  if (tbl->outer_join)
4603  {
4604  /*
4605  Table tab is the only one inner table for outer join.
4606  (Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4607  is in the query above.)
4608  */
4609  tab->last_inner= tab->first_inner= tab;
4610  tab->on_expr_ref= &tbl->on_expr;
4611  tab->cond_equal= tbl->cond_equal;
4612  if (embedding)
4613  tab->first_upper= embedding->getNestedJoin()->first_nested;
4614  }
4615  for ( ; embedding ; embedding= embedding->getEmbedding())
4616  {
4617  /* Ignore sj-nests: */
4618  if (!embedding->on_expr)
4619  continue;
4620  NestedJoin *nested_join= embedding->getNestedJoin();
4621  if (!nested_join->counter_)
4622  {
4623  /*
4624  Table tab is the first inner table for nested_join.
4625  Save reference to it in the nested join structure.
4626  */
4627  nested_join->first_nested= tab;
4628  tab->on_expr_ref= &embedding->on_expr;
4629  tab->cond_equal= tbl->cond_equal;
4630  if (embedding->getEmbedding())
4631  tab->first_upper= embedding->getEmbedding()->getNestedJoin()->first_nested;
4632  }
4633  if (!tab->first_inner)
4634  tab->first_inner= nested_join->first_nested;
4635  if (++nested_join->counter_ < nested_join->join_list.size())
4636  break;
4637  /* Table tab is the last inner table for nested join. */
4638  nested_join->first_nested->last_inner= tab;
4639  }
4640  }
4641  return;
4642 }
4643 
4644 static bool make_join_select(Join *join,
4645  optimizer::SqlSelect *select,
4646  COND *cond)
4647 {
4648  Session *session= join->session;
4649  optimizer::Position cur_pos;
4650  if (select)
4651  {
4652  add_not_null_conds(join);
4653  table_map used_tables;
4654  if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4655  { /* there may be a select without a cond. */
4656  if (join->tables > 1)
4657  cond->update_used_tables(); // Tablenr may have changed
4658  if (join->const_tables == join->tables &&
4659  session->lex().current_select->master_unit() ==
4660  &session->lex().unit) // not upper level SELECT
4661  join->const_table_map|=RAND_TABLE_BIT;
4662  { // Check const tables
4663  COND *const_cond=
4664  make_cond_for_table(cond,
4665  join->const_table_map,
4666  0, 1);
4667  for (JoinTable *tab= join->join_tab+join->const_tables;
4668  tab < join->join_tab+join->tables ; tab++)
4669  {
4670  if (*tab->on_expr_ref)
4671  {
4672  JoinTable *cond_tab= tab->first_inner;
4673  COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4674  join->const_table_map,
4675  ( table_map) 0, 0);
4676  if (!tmp)
4677  continue;
4678  tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4679  if (! tmp)
4680  return 1;
4681  tmp->quick_fix_field();
4682  cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4683  new Item_cond_and(cond_tab->select_cond,
4684  tmp);
4685  if (! cond_tab->select_cond)
4686  return 1;
4687  cond_tab->select_cond->quick_fix_field();
4688  }
4689  }
4690  if (const_cond && ! const_cond->val_int())
4691  {
4692  return 1; // Impossible const condition
4693  }
4694  }
4695  }
4696  used_tables=((select->const_tables=join->const_table_map) |
4697  OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4698  for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4699  {
4700  JoinTable *tab=join->join_tab+i;
4701  /*
4702  first_inner is the X in queries like:
4703  SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4704  */
4705  JoinTable *first_inner_tab= tab->first_inner;
4706  table_map current_map= tab->table->map;
4707  bool use_quick_range=0;
4708  COND *tmp;
4709 
4710  /*
4711  Following force including random expression in last table condition.
4712  It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4713  */
4714  if (i == join->tables-1)
4715  current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4716  used_tables|=current_map;
4717 
4718  if (tab->type == AM_REF && tab->quick &&
4719  (uint32_t) tab->ref.key == tab->quick->index &&
4720  tab->ref.key_length < tab->quick->max_used_key_length)
4721  {
4722  /* Range uses longer key; Use this instead of ref on key */
4723  tab->type= AM_ALL;
4724  use_quick_range= 1;
4725  tab->use_quick= 1;
4726  tab->ref.key= -1;
4727  tab->ref.key_parts= 0; // Don't use ref key.
4728  cur_pos= join->getPosFromOptimalPlan(i);
4729  cur_pos.setFanout(tab->quick->records);
4730  /*
4731  We will use join cache here : prevent sorting of the first
4732  table only and sort at the end.
4733  */
4734  if (i != join->const_tables && join->tables > join->const_tables + 1)
4735  join->full_join= 1;
4736  }
4737 
4738  if (join->full_join and not session->lex().current_select->is_cross and not cond)
4739  {
4740  my_error(ER_CARTESIAN_JOIN_ATTEMPTED, MYF(0));
4741  return 1;
4742  }
4743 
4744  tmp= NULL;
4745  if (cond)
4746  tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4747  if (cond && !tmp && tab->quick)
4748  { // Outer join
4749  if (tab->type != AM_ALL)
4750  {
4751  /*
4752  Don't use the quick method
4753  We come here in the case where we have 'key=constant' and
4754  the test is removed by make_cond_for_table()
4755  */
4756  delete tab->quick;
4757  tab->quick= 0;
4758  }
4759  else
4760  {
4761  /*
4762  Hack to handle the case where we only refer to a table
4763  in the ON part of an OUTER JOIN. In this case we want the code
4764  below to check if we should use 'quick' instead.
4765  */
4766  tmp= new Item_int((int64_t) 1,1); // Always true
4767  }
4768 
4769  }
4770  if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4771  tab->type == AM_EQ_REF)
4772  {
4773  optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)session->mem.memdup(select, sizeof(*select)));
4774  /*
4775  If tab is an inner table of an outer join operation,
4776  add a match guard to the pushed down predicate.
4777  The guard will turn the predicate on only after
4778  the first match for outer tables is encountered.
4779  */
4780  if (cond && tmp)
4781  {
4782  /*
4783  Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4784  a cond, so neutralize the hack above.
4785  */
4786  if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4787  return 1;
4788  tab->select_cond=sel->cond=tmp;
4789  }
4790  else
4791  tab->select_cond= sel->cond= NULL;
4792 
4793  sel->head=tab->table;
4794  if (tab->quick)
4795  {
4796  /* Use quick key read if it's a constant and it's not used
4797  with key reading */
4798  if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4799  && (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4800  {
4801  sel->quick=tab->quick; // Use value from get_quick_...
4802  sel->quick_keys.reset();
4803  sel->needed_reg.reset();
4804  }
4805  else
4806  {
4807  delete tab->quick;
4808  }
4809  tab->quick= 0;
4810  }
4811  uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4812  if (i == join->const_tables && ref_key)
4813  {
4814  if (tab->const_keys.any() &&
4815  tab->table->reginfo.impossible_range)
4816  return 1;
4817  }
4818  else if (tab->type == AM_ALL && ! use_quick_range)
4819  {
4820  if (tab->const_keys.any() &&
4821  tab->table->reginfo.impossible_range)
4822  return 1; // Impossible range
4823  /*
4824  We plan to scan all rows.
4825  Check again if we should use an index.
4826  We could have used an column from a previous table in
4827  the index if we are using limit and this is the first table
4828  */
4829 
4830  cur_pos= join->getPosFromOptimalPlan(i);
4831  if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4832  (! tab->const_keys.none() && (i == join->const_tables) &&
4833  (join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4834  {
4835  /* Join with outer join condition */
4836  COND *orig_cond= sel->cond;
4837  sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4838 
4839  /*
4840  We can't call sel->cond->fix_fields,
4841  as it will break tab->on_expr if it's AND condition
4842  (fix_fields currently removes extra AND/OR levels).
4843  Yet attributes of the just built condition are not needed.
4844  Thus we call sel->cond->quick_fix_field for safety.
4845  */
4846  if (sel->cond && ! sel->cond->fixed)
4847  sel->cond->quick_fix_field();
4848 
4849  if (sel->test_quick_select(session, tab->keys,
4850  used_tables & ~ current_map,
4851  (join->select_options &
4852  OPTION_FOUND_ROWS ?
4853  HA_POS_ERROR :
4854  join->unit->select_limit_cnt), 0,
4855  false) < 0)
4856  {
4857  /*
4858  Before reporting "Impossible WHERE" for the whole query
4859  we have to check isn't it only "impossible ON" instead
4860  */
4861  sel->cond=orig_cond;
4862  if (! *tab->on_expr_ref ||
4863  sel->test_quick_select(session, tab->keys,
4864  used_tables & ~ current_map,
4865  (join->select_options &
4866  OPTION_FOUND_ROWS ?
4867  HA_POS_ERROR :
4868  join->unit->select_limit_cnt),0,
4869  false) < 0)
4870  return 1; // Impossible WHERE
4871  }
4872  else
4873  sel->cond=orig_cond;
4874 
4875  /* Fix for EXPLAIN */
4876  if (sel->quick)
4877  {
4878  cur_pos= join->getPosFromOptimalPlan(i);
4879  cur_pos.setFanout(static_cast<double>(sel->quick->records));
4880  }
4881  }
4882  else
4883  {
4884  sel->needed_reg= tab->needed_reg;
4885  sel->quick_keys.reset();
4886  }
4887  if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4888  !((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4889  {
4890  tab->keys= sel->quick_keys;
4891  tab->keys|= sel->needed_reg;
4892  tab->use_quick= (!sel->needed_reg.none() &&
4893  (select->quick_keys.none() ||
4894  (select->quick &&
4895  (select->quick->records >= 100L)))) ?
4896  2 : 1;
4897  sel->read_tables= used_tables & ~current_map;
4898  }
4899  if (i != join->const_tables && tab->use_quick != 2)
4900  { /* Read with cache */
4901  if (cond &&
4902  (tmp=make_cond_for_table(cond,
4903  join->const_table_map |
4904  current_map,
4905  current_map, 0)))
4906  {
4907  tab->cache.select= (optimizer::SqlSelect*)session->mem.memdup(sel, sizeof(optimizer::SqlSelect));
4908  tab->cache.select->cond= tmp;
4909  tab->cache.select->read_tables= join->const_table_map;
4910  }
4911  }
4912  }
4913  }
4914 
4915  /*
4916  Push down conditions from all on expressions.
4917  Each of these conditions are guarded by a variable
4918  that turns if off just before null complemented row for
4919  outer joins is formed. Thus, the condition from an
4920  'on expression' are guaranteed not to be checked for
4921  the null complemented row.
4922  */
4923 
4924  /* First push down constant conditions from on expressions */
4925  for (JoinTable *join_tab= join->join_tab+join->const_tables;
4926  join_tab < join->join_tab+join->tables ; join_tab++)
4927  {
4928  if (*join_tab->on_expr_ref)
4929  {
4930  JoinTable *cond_tab= join_tab->first_inner;
4931  tmp= make_cond_for_table(*join_tab->on_expr_ref,
4932  join->const_table_map,
4933  (table_map) 0, 0);
4934  if (!tmp)
4935  continue;
4936  tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4937  if (! tmp)
4938  return 1;
4939  tmp->quick_fix_field();
4940  cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4941  new Item_cond_and(cond_tab->select_cond,tmp);
4942  if (! cond_tab->select_cond)
4943  return 1;
4944  cond_tab->select_cond->quick_fix_field();
4945  }
4946  }
4947 
4948  /* Push down non-constant conditions from on expressions */
4949  JoinTable *last_tab= tab;
4950  while (first_inner_tab && first_inner_tab->last_inner == last_tab)
4951  {
4952  /*
4953  Table tab is the last inner table of an outer join.
4954  An on expression is always attached to it.
4955  */
4956  COND *on_expr= *first_inner_tab->on_expr_ref;
4957 
4958  table_map used_tables2= (join->const_table_map |
4959  OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4960  for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
4961  {
4962  current_map= tab->table->map;
4963  used_tables2|= current_map;
4964  COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
4965  current_map, 0);
4966  if (tmp_cond)
4967  {
4968  JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
4969  /*
4970  First add the guards for match variables of
4971  all embedding outer join operations.
4972  */
4973  if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
4974  tmp_cond,
4975  first_inner_tab)))
4976  return 1;
4977  /*
4978  Now add the guard turning the predicate off for
4979  the null complemented row.
4980  */
4981  tmp_cond= new Item_func_trig_cond(tmp_cond,
4982  &first_inner_tab->
4983  not_null_compl);
4984  if (tmp_cond)
4985  tmp_cond->quick_fix_field();
4986  /* Add the predicate to other pushed down predicates */
4987  cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
4988  new Item_cond_and(cond_tab->select_cond,
4989  tmp_cond);
4990  if (! cond_tab->select_cond)
4991  return 1;
4992  cond_tab->select_cond->quick_fix_field();
4993  }
4994  }
4995  first_inner_tab= first_inner_tab->first_upper;
4996  }
4997  }
4998  }
4999  return 0;
5000 }
5001 
5002 /*
5003  Plan refinement stage: do various set ups for the executioner
5004 
5005  SYNOPSIS
5006  make_join_readinfo()
5007  join Join being processed
5008  options Join's options (checking for SELECT_DESCRIBE,
5009  SELECT_NO_JOIN_CACHE)
5010  no_jbuf_after Don't use join buffering after table with this number.
5011 
5012  DESCRIPTION
5013  Plan refinement stage: do various set ups for the executioner
5014  - set up use of join buffering
5015  - push index conditions
5016  - increment counters
5017  - etc
5018 
5019  RETURN
5020  false - OK
5021  true - Out of memory
5022 */
5023 static void make_join_readinfo(Join& join)
5024 {
5025  bool sorted= true;
5026 
5027  for (uint32_t i= join.const_tables; i < join.tables; i++)
5028  {
5029  JoinTable *tab=join.join_tab+i;
5030  Table *table=tab->table;
5031  tab->read_record.table= table;
5032  tab->read_record.cursor= table->cursor;
5033  tab->next_select=sub_select; /* normal select */
5034  /*
5035  TODO: don't always instruct first table's ref/range access method to
5036  produce sorted output.
5037  */
5038  tab->sorted= sorted;
5039  sorted= false; // only first must be sorted
5040 
5041  if (tab->insideout_match_tab)
5042  {
5043  tab->insideout_buf= join.session->mem.alloc(tab->table->key_info[tab->index].key_length);
5044  }
5045 
5046  optimizer::AccessMethodFactory::create(tab->type)->getStats(*table, *tab);
5047  }
5048 
5049  join.join_tab[join.tables-1].next_select= NULL; /* Set by do_select */
5050 }
5051 
5053 static void update_depend_map(Join *join)
5054 {
5055  JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
5056 
5057  for (; join_tab != end ; join_tab++)
5058  {
5059  table_reference_st *ref= &join_tab->ref;
5060  table_map depend_map= 0;
5061  Item **item=ref->items;
5062  uint32_t i;
5063  for (i=0 ; i < ref->key_parts ; i++,item++)
5064  depend_map|=(*item)->used_tables();
5065  ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
5066  depend_map&= ~OUTER_REF_TABLE_BIT;
5067  for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5068  {
5069  if (depend_map & 1)
5070  ref->depend_map|=(*tab)->ref.depend_map;
5071  }
5072  }
5073 }
5074 
5076 static void update_depend_map(Join *join, Order *order)
5077 {
5078  for (; order ; order=order->next)
5079  {
5080  table_map depend_map;
5081  order->item[0]->update_used_tables();
5082  order->depend_map=depend_map=order->item[0]->used_tables();
5083  // Not item_sum(), RAND() and no reference to table outside of sub select
5084  if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5085  && !order->item[0]->with_sum_func)
5086  {
5087  for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5088  {
5089  if (depend_map & 1)
5090  order->depend_map|=(*tab)->ref.depend_map;
5091  }
5092  }
5093  }
5094 }
5095 
5114 static Order *remove_constants(Join *join,Order *first_order, COND *cond, bool change_list, bool *simple_order)
5115 {
5116  if (join->tables == join->const_tables)
5117  return change_list ? 0 : first_order; // No need to sort
5118 
5119  Order *order,**prev_ptr;
5120  table_map first_table= join->join_tab[join->const_tables].table->map;
5121  table_map not_const_tables= ~join->const_table_map;
5122  table_map ref;
5123 
5124  prev_ptr= &first_order;
5125  *simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5126 
5127  /* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5128 
5129  update_depend_map(join, first_order);
5130  for (order=first_order; order ; order=order->next)
5131  {
5132  table_map order_tables=order->item[0]->used_tables();
5133  if (order->item[0]->with_sum_func)
5134  *simple_order=0; // Must do a temp table to sort
5135  else if (!(order_tables & not_const_tables))
5136  {
5137  if (order->item[0]->with_subselect)
5138  order->item[0]->val_str(&order->item[0]->str_value);
5139  continue; // skip const item
5140  }
5141  else
5142  {
5143  if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5144  *simple_order=0;
5145  else
5146  {
5147  Item *comp_item=0;
5148  if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5149  {
5150  continue;
5151  }
5152  if ((ref=order_tables & (not_const_tables ^ first_table)))
5153  {
5154  if (!(order_tables & first_table) &&
5155  only_eq_ref_tables(join,first_order, ref))
5156  {
5157  continue;
5158  }
5159  *simple_order=0; // Must do a temp table to sort
5160  }
5161  }
5162  }
5163  if (change_list)
5164  *prev_ptr= order; // use this entry
5165  prev_ptr= &order->next;
5166  }
5167  if (change_list)
5168  *prev_ptr=0;
5169  if (prev_ptr == &first_order) // Nothing to sort/group
5170  *simple_order=1;
5171  return(first_order);
5172 }
5173 
5174 static void return_zero_rows(Join *join, select_result *result, TableList *tables, List<Item> &fields, bool send_row, uint64_t select_options, const char *info, Item *having)
5175 {
5176  if (select_options & SELECT_DESCRIBE)
5177  {
5178  optimizer::ExplainPlan planner(join, false, false, false, info);
5179  planner.printPlan();
5180  return;
5181  }
5182 
5183  join->join_free();
5184 
5185  if (send_row)
5186  {
5187  for (TableList *table= tables; table; table= table->next_leaf)
5188  table->table->mark_as_null_row(); // All fields are NULL
5189  if (having && having->val_int() == 0)
5190  send_row=0;
5191  }
5192  result->send_fields(fields);
5193  if (send_row)
5194  {
5195  List<Item>::iterator it(fields.begin());
5196  while (Item* item= it++)
5197  item->no_rows_in_result();
5198  result->send_data(fields);
5199  }
5200  result->send_eof(); // Should be safe
5201  /* Update results for FOUND_ROWS */
5202  join->session->limit_found_rows= join->session->examined_row_count= 0;
5203 }
5204 
5325 static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top)
5326 {
5327  NestedJoin *nested_join;
5328  TableList *prev_table= 0;
5329  List<TableList>::iterator li(join_list->begin());
5330 
5331  /*
5332  Try to simplify join operations from join_list.
5333  The most outer join operation is checked for conversion first.
5334  */
5335  while (TableList* table= li++)
5336  {
5337  table_map used_tables;
5338  table_map not_null_tables= (table_map) 0;
5339 
5340  if ((nested_join= table->getNestedJoin()))
5341  {
5342  /*
5343  If the element of join_list is a nested join apply
5344  the procedure to its nested join list first.
5345  */
5346  if (table->on_expr)
5347  {
5348  Item *expr= table->on_expr;
5349  /*
5350  If an on expression E is attached to the table,
5351  check all null rejected predicates in this expression.
5352  If such a predicate over an attribute belonging to
5353  an inner table of an embedded outer join is found,
5354  the outer join is converted to an inner join and
5355  the corresponding on expression is added to E.
5356  */
5357  expr= simplify_joins(join, &nested_join->join_list, expr, false);
5358 
5359  if (!table->prep_on_expr || expr != table->on_expr)
5360  {
5361  assert(expr);
5362 
5363  table->on_expr= expr;
5364  table->prep_on_expr= expr->copy_andor_structure(join->session);
5365  }
5366  }
5367  nested_join->used_tables= (table_map) 0;
5368  nested_join->not_null_tables=(table_map) 0;
5369  conds= simplify_joins(join, &nested_join->join_list, conds, top);
5370  used_tables= nested_join->used_tables;
5371  not_null_tables= nested_join->not_null_tables;
5372  }
5373  else
5374  {
5375  if (!table->prep_on_expr)
5376  table->prep_on_expr= table->on_expr;
5377  used_tables= table->table->map;
5378  if (conds)
5379  not_null_tables= conds->not_null_tables();
5380  }
5381 
5382  if (table->getEmbedding())
5383  {
5384  table->getEmbedding()->getNestedJoin()->used_tables|= used_tables;
5385  table->getEmbedding()->getNestedJoin()->not_null_tables|= not_null_tables;
5386  }
5387 
5388  if (!table->outer_join || (used_tables & not_null_tables))
5389  {
5390  /*
5391  For some of the inner tables there are conjunctive predicates
5392  that reject nulls => the outer join can be replaced by an inner join.
5393  */
5394  table->outer_join= 0;
5395  if (table->on_expr)
5396  {
5397  /* Add ON expression to the WHERE or upper-level ON condition. */
5398  if (conds)
5399  {
5400  conds= and_conds(conds, table->on_expr);
5401  conds->top_level_item();
5402  /* conds is always a new item as both cond and on_expr existed */
5403  assert(!conds->fixed);
5404  conds->fix_fields(join->session, &conds);
5405  }
5406  else
5407  conds= table->on_expr;
5408  table->prep_on_expr= table->on_expr= 0;
5409  }
5410  }
5411 
5412  if (!top)
5413  continue;
5414 
5415  /*
5416  Only inner tables of non-convertible outer joins
5417  remain with on_expr.
5418  */
5419  if (table->on_expr)
5420  {
5421  table->setDepTables(table->getDepTables() | table->on_expr->used_tables());
5422  if (table->getEmbedding())
5423  {
5424  table->setDepTables(table->getDepTables() & ~table->getEmbedding()->getNestedJoin()->used_tables);
5425  /*
5426  Embedding table depends on tables used
5427  in embedded on expressions.
5428  */
5429  table->getEmbedding()->setOnExprDepTables(table->getEmbedding()->getOnExprDepTables() & table->on_expr->used_tables());
5430  }
5431  else
5432  table->setDepTables(table->getDepTables() & ~table->table->map);
5433  }
5434 
5435  if (prev_table)
5436  {
5437  //If this is straight join, set prev table to be dependent on all tables
5438  //from this nested join, so that correct join order is selected.
5439  if ((test(join->select_options & SELECT_STRAIGHT_JOIN)) ||
5440  prev_table->straight)
5441  prev_table->setDepTables(prev_table->getDepTables() | used_tables);
5442  if (prev_table->on_expr)
5443  {
5444  prev_table->setDepTables(prev_table->getDepTables() | table->getOnExprDepTables());
5445  table_map prev_used_tables= prev_table->getNestedJoin() ?
5446  prev_table->getNestedJoin()->used_tables :
5447  prev_table->table->map;
5448  /*
5449  If on expression contains only references to inner tables
5450  we still make the inner tables dependent on the outer tables.
5451  It would be enough to set dependency only on one outer table
5452  for them. Yet this is really a rare case.
5453  */
5454  if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5455  prev_table->setDepTables(prev_table->getDepTables() | used_tables);
5456  }
5457  }
5458  prev_table= table;
5459  }
5460 
5461  /*
5462  Flatten nested joins that can be flattened.
5463  no ON expression and not a semi-join => can be flattened.
5464  */
5465  li= join_list->begin();
5466  while (TableList* table= li++)
5467  {
5468  nested_join= table->getNestedJoin();
5469  if (nested_join && !table->on_expr)
5470  {
5471  List<TableList>::iterator it(nested_join->join_list.begin());
5472  while (TableList* tbl= it++)
5473  {
5474  tbl->setEmbedding(table->getEmbedding());
5475  tbl->setJoinList(table->getJoinList());
5476  }
5477  li.replace(nested_join->join_list);
5478  }
5479  }
5480  return(conds);
5481 }
5482 
5483 static int remove_duplicates(Join *join, Table *entry,List<Item> &fields, Item *having)
5484 {
5485  entry->reginfo.lock_type=TL_WRITE;
5486 
5487  /* Calculate how many saved fields there is in list */
5488  uint32_t field_count= 0;
5489  List<Item>::iterator it(fields.begin());
5490  while (Item* item=it++)
5491  {
5492  if (item->get_tmp_table_field() && ! item->const_item())
5493  field_count++;
5494  }
5495 
5496  if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5497  { // only const items with no OPTION_FOUND_ROWS
5498  join->unit->select_limit_cnt= 1; // Only send first row
5499  return 0;
5500  }
5501  Field **first_field=entry->getFields() + entry->getShare()->sizeFields() - field_count;
5502  uint32_t offset= field_count ? entry->getField(entry->getShare()->sizeFields() - field_count)->offset(entry->getInsertRecord()) : 0;
5503  uint32_t reclength= entry->getShare()->getRecordLength() - offset;
5504 
5505  entry->free_io_cache(); // Safety
5506  entry->cursor->info(HA_STATUS_VARIABLE);
5507  int error;
5508  if (entry->getShare()->db_type() == heap_engine ||
5509  (!entry->getShare()->blob_fields &&
5510  ((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records < join->session->variables.sortbuff_size)))
5511  {
5512  error= remove_dup_with_hash_index(join->session, entry, field_count, first_field, reclength, having);
5513  }
5514  else
5515  {
5516  error= remove_dup_with_compare(join->session, entry, first_field, offset, having);
5517  }
5518  free_blobs(first_field);
5519  return error;
5520 }
5521 
5525 static int setup_without_group(Session *session,
5526  Item **ref_pointer_array,
5527  TableList *tables,
5528  TableList *,
5529  List<Item> &fields,
5530  List<Item> &all_fields,
5531  COND **conds,
5532  Order *order,
5533  Order *group,
5534  bool *hidden_group_fields)
5535 {
5536  int res;
5537  nesting_map save_allow_sum_func=session->lex().allow_sum_func;
5538 
5539  session->lex().allow_sum_func&= ~(1 << session->lex().current_select->nest_level);
5540  res= session->setup_conds(tables, conds);
5541 
5542  session->lex().allow_sum_func|= 1 << session->lex().current_select->nest_level;
5543  res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields, order);
5544  session->lex().allow_sum_func&= ~(1 << session->lex().current_select->nest_level);
5545  res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields, group, hidden_group_fields);
5546  session->lex().allow_sum_func= save_allow_sum_func;
5547  return res;
5548 }
5549 
5558 static bool make_join_statistics(Join *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5559 {
5560  int error;
5561  Table *table;
5562  uint32_t i;
5563  uint32_t table_count;
5564  uint32_t const_count;
5565  uint32_t key;
5566  table_map found_const_table_map;
5567  table_map all_table_map;
5568  table_map found_ref;
5569  table_map refs;
5570  key_map const_ref;
5571  key_map eq_part;
5572  Table **table_vector= NULL;
5573  JoinTable *stat= NULL;
5574  JoinTable *stat_end= NULL;
5575  JoinTable *s= NULL;
5576  JoinTable **stat_ref= NULL;
5577  optimizer::KeyUse *keyuse= NULL;
5578  optimizer::KeyUse *start_keyuse= NULL;
5579  table_map outer_join= 0;
5580  vector<optimizer::SargableParam> sargables;
5581  JoinTable *stat_vector[MAX_TABLES+1];
5582  optimizer::Position *partial_pos;
5583 
5584  table_count= join->tables;
5585  stat= (JoinTable*) join->session->mem.calloc(sizeof(JoinTable)*table_count);
5586  stat_ref= new (join->session->mem) JoinTable*[MAX_TABLES];
5587  table_vector= new (join->session->mem) Table*[2 * table_count];
5588 
5589  join->best_ref=stat_vector;
5590 
5591  stat_end=stat+table_count;
5592  found_const_table_map= all_table_map=0;
5593  const_count=0;
5594 
5595  for (s= stat, i= 0;
5596  tables;
5597  s++, tables= tables->next_leaf, i++)
5598  {
5599  TableList *embedding= tables->getEmbedding();
5600  stat_vector[i]=s;
5601  s->keys.reset();
5602  s->const_keys.reset();
5603  s->checked_keys.reset();
5604  s->needed_reg.reset();
5605  table_vector[i]=s->table=table=tables->table;
5606  table->pos_in_table_list= tables;
5607  assert(table->cursor);
5608  error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5609  if (error)
5610  {
5611  table->print_error(error, MYF(0));
5612  return 1;
5613  }
5614  table->quick_keys.reset();
5615  table->reginfo.join_tab=s;
5616  table->reginfo.not_exists_optimize=0;
5617  memset(table->const_key_parts, 0, sizeof(key_part_map)*table->getShare()->sizeKeys());
5618  all_table_map|= table->map;
5619  s->join=join;
5620  s->info=0; // For describe
5621 
5622  s->dependent= tables->getDepTables();
5623  s->key_dependent= 0;
5624  table->quick_condition_rows= table->cursor->stats.records;
5625 
5626  s->on_expr_ref= &tables->on_expr;
5627  if (*s->on_expr_ref)
5628  {
5629  /* s is the only inner table of an outer join */
5630  if (!table->cursor->stats.records && !embedding)
5631  { // Empty table
5632  s->dependent= 0; // Ignore LEFT JOIN depend.
5633  set_position(join, const_count++, s, NULL);
5634  continue;
5635  }
5636  outer_join|= table->map;
5637  s->embedding_map.reset();
5638  for (;embedding; embedding= embedding->getEmbedding())
5639  s->embedding_map|= embedding->getNestedJoin()->nj_map;
5640  continue;
5641  }
5642  if (embedding && !(false && ! embedding->getEmbedding()))
5643  {
5644  /* s belongs to a nested join, maybe to several embedded joins */
5645  s->embedding_map.reset();
5646  do
5647  {
5648  NestedJoin *nested_join= embedding->getNestedJoin();
5649  s->embedding_map|= nested_join->nj_map;
5650  s->dependent|= embedding->getDepTables();
5651  embedding= embedding->getEmbedding();
5652  outer_join|= nested_join->used_tables;
5653  }
5654  while (embedding);
5655  continue;
5656  }
5657  if ((table->cursor->stats.records <= 1) && !s->dependent &&
5658  (table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5659  !join->no_const_tables)
5660  {
5661  set_position(join, const_count++, s, NULL);
5662  }
5663  }
5664  stat_vector[i]=0;
5665  join->outer_join=outer_join;
5666 
5667  if (join->outer_join)
5668  {
5669  /*
5670  Build transitive closure for relation 'to be dependent on'.
5671  This will speed up the plan search for many cases with outer joins,
5672  as well as allow us to catch illegal cross references/
5673  Warshall's algorithm is used to build the transitive closure.
5674  As we use bitmaps to represent the relation the complexity
5675  of the algorithm is O((number of tables)^2).
5676  */
5677  for (i= 0; i < table_count; i++)
5678  {
5679  uint32_t j;
5680  table= stat[i].table;
5681 
5682  if (!table->reginfo.join_tab->dependent)
5683  continue;
5684 
5685  for (j= 0, s= stat; j < table_count; j++, s++)
5686  {
5687  if (s->dependent & table->map)
5688  {
5689  table_map was_dependent= s->dependent;
5690  s->dependent |= table->reginfo.join_tab->dependent;
5691  if (i > j && s->dependent != was_dependent)
5692  {
5693  i= j= 1;
5694  break;
5695  }
5696  }
5697  }
5698  }
5699  /* Catch illegal cross references for outer joins */
5700  for (i= 0, s= stat ; i < table_count ; i++, s++)
5701  {
5702  if (s->dependent & s->table->map)
5703  {
5704  join->tables=0; // Don't use join->table
5705  my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5706  return 1;
5707  }
5708  if (outer_join & s->table->map)
5709  s->table->maybe_null= 1;
5710 
5711  s->key_dependent= s->dependent;
5712  }
5713  }
5714 
5715  if (conds || outer_join)
5716  update_ref_and_keys(join->session, keyuse_array, stat, join->tables, conds, join->cond_equal, ~outer_join, join->select_lex, sargables);
5717 
5718  /* Read tables with 0 or 1 rows (system tables) */
5719  join->const_table_map= 0;
5720 
5722  optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5723  while (p_pos < p_end)
5724  {
5725  int tmp;
5726  s= p_pos->getJoinTable();
5727  s->type= AM_SYSTEM;
5728  join->const_table_map|=s->table->map;
5729  if ((tmp= s->joinReadConstTable(p_pos)))
5730  {
5731  if (tmp > 0)
5732  return 1; // Fatal error
5733  }
5734  else
5735  found_const_table_map|= s->table->map;
5736  p_pos++;
5737  }
5738 
5739  /* loop until no more const tables are found */
5740  int ref_changed;
5741  do
5742  {
5743  more_const_tables_found:
5744  ref_changed = 0;
5745  found_ref=0;
5746 
5747  /*
5748  We only have to loop from stat_vector + const_count as
5749  set_position() will move all const_tables first in stat_vector
5750  */
5751 
5752  for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
5753  {
5754  table= s->table;
5755 
5756  /*
5757  If equi-join condition by a key is null rejecting and after a
5758  substitution of a const table the key value happens to be null
5759  then we can state that there are no matches for this equi-join.
5760  */
5761  if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5762  {
5763  /*
5764  When performing an outer join operation if there are no matching rows
5765  for the single row of the outer table all the inner tables are to be
5766  null complemented and thus considered as constant tables.
5767  Here we apply this consideration to the case of outer join operations
5768  with a single inner table only because the case with nested tables
5769  would require a more thorough analysis.
5770  TODO. Apply single row substitution to null complemented inner tables
5771  for nested outer join operations.
5772  */
5773  while (keyuse->getTable() == table)
5774  {
5775  if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5776  keyuse->getVal()->is_null() && keyuse->isNullRejected())
5777  {
5778  s->type= AM_CONST;
5779  table->mark_as_null_row();
5780  found_const_table_map|= table->map;
5781  join->const_table_map|= table->map;
5782  set_position(join, const_count++, s, NULL);
5783  goto more_const_tables_found;
5784  }
5785  keyuse++;
5786  }
5787  }
5788 
5789  if (s->dependent) // If dependent on some table
5790  {
5791  // All dep. must be constants
5792  if (s->dependent & ~(found_const_table_map))
5793  continue;
5794  if (table->cursor->stats.records <= 1L &&
5795  (table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5796  !table->pos_in_table_list->getEmbedding())
5797  { // system table
5798  int tmp= 0;
5799  s->type= AM_SYSTEM;
5800  join->const_table_map|=table->map;
5801  set_position(join, const_count++, s, NULL);
5802  partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5803  if ((tmp= s->joinReadConstTable(partial_pos)))
5804  {
5805  if (tmp > 0)
5806  return 1; // Fatal error
5807  }
5808  else
5809  found_const_table_map|= table->map;
5810  continue;
5811  }
5812  }
5813  /* check if table can be read by key or table only uses const refs */
5814  if ((keyuse=s->keyuse))
5815  {
5816  s->type= AM_REF;
5817  while (keyuse->getTable() == table)
5818  {
5819  start_keyuse= keyuse;
5820  key= keyuse->getKey();
5821  s->keys.set(key); // QQ: remove this ?
5822 
5823  refs= 0;
5824  const_ref.reset();
5825  eq_part.reset();
5826  do
5827  {
5828  if (keyuse->getVal()->type() != Item::NULL_ITEM &&
5829  ! keyuse->getOptimizeFlags())
5830  {
5831  if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5832  const_ref.set(keyuse->getKeypart());
5833  else
5834  refs|= keyuse->getUsedTables();
5835  eq_part.set(keyuse->getKeypart());
5836  }
5837  keyuse++;
5838  } while (keyuse->getTable() == table && keyuse->getKey() == key);
5839 
5840  if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5841  ! table->pos_in_table_list->getEmbedding())
5842  {
5843  if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5844  {
5845  if (const_ref == eq_part)
5846  { // Found everything for ref.
5847  int tmp;
5848  ref_changed = 1;
5849  s->type= AM_CONST;
5850  join->const_table_map|= table->map;
5851  set_position(join, const_count++, s, start_keyuse);
5852  if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5853  return 1;
5854  partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5855  if ((tmp=s->joinReadConstTable(partial_pos)))
5856  {
5857  if (tmp > 0)
5858  return 1; // Fatal error
5859  }
5860  else
5861  found_const_table_map|= table->map;
5862  break;
5863  }
5864  else
5865  found_ref|= refs; // Table is const if all refs are const
5866  }
5867  else if (const_ref == eq_part)
5868  s->const_keys.set(key);
5869  }
5870  }
5871  }
5872  }
5873  } while (join->const_table_map & found_ref && ref_changed);
5874 
5875  /*
5876  Update info on indexes that can be used for search lookups as
5877  reading const tables may has added new sargable predicates.
5878  */
5879  if (const_count && ! sargables.empty())
5880  {
5881  BOOST_FOREACH(vector<optimizer::SargableParam>::reference iter, sargables)
5882  {
5883  Field& field= *iter.getField();
5884  JoinTable *join_tab= field.getTable()->reginfo.join_tab;
5885  key_map possible_keys= field.key_start & field.getTable()->keys_in_use_for_query;
5886  bool is_const= true;
5887  for (uint32_t j= 0; j < iter.getNumValues(); j++)
5888  is_const&= iter.isConstItem(j);
5889  if (is_const)
5890  join_tab[0].const_keys|= possible_keys;
5891  }
5892  }
5893 
5894  /* Calc how many (possible) matched records in each table */
5895 
5896  for (s=stat ; s < stat_end ; s++)
5897  {
5898  if (s->type == AM_SYSTEM || s->type == AM_CONST)
5899  {
5900  /* Only one matching row */
5901  s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
5902  continue;
5903  }
5904  /* Approximate found rows and time to read them */
5905  s->found_records=s->records=s->table->cursor->stats.records;
5906  s->read_time=(ha_rows) s->table->cursor->scan_time();
5907 
5908  /*
5909  Set a max range of how many seeks we can expect when using keys
5910  This is can't be to high as otherwise we are likely to use
5911  table scan.
5912  */
5913  s->worst_seeks= min((double) s->found_records / 10,
5914  (double) s->read_time*3);
5915  if (s->worst_seeks < 2.0) // Fix for small tables
5916  s->worst_seeks=2.0;
5917 
5918  /*
5919  Add to stat->const_keys those indexes for which all group fields or
5920  all select distinct fields participate in one index.
5921  */
5922  add_group_and_distinct_keys(join, s);
5923 
5924  if (s->const_keys.any() &&
5925  !s->table->pos_in_table_list->getEmbedding())
5926  {
5927  ha_rows records;
5928  optimizer::SqlSelect *select= NULL;
5929  select= optimizer::make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
5930  if (! select)
5931  return 1;
5932  records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
5933  s->quick=select->quick;
5934  s->needed_reg=select->needed_reg;
5935  select->quick=0;
5936 
5937  if (records == 0 && s->table->reginfo.impossible_range)
5938  {
5939  /*
5940  Impossible WHERE or ON expression
5941  In case of ON, we mark that the we match one empty NULL row.
5942  In case of WHERE, don't set found_const_table_map to get the
5943  caller to abort with a zero row result.
5944  */
5945  join->const_table_map|= s->table->map;
5946  set_position(join, const_count++, s, NULL);
5947  s->type= AM_CONST;
5948  if (*s->on_expr_ref)
5949  {
5950  /* Generate empty row */
5951  s->info= "Impossible ON condition";
5952  found_const_table_map|= s->table->map;
5953  s->type= AM_CONST;
5954  s->table->mark_as_null_row(); // All fields are NULL
5955  }
5956  }
5957  if (records != HA_POS_ERROR)
5958  {
5959  s->found_records=records;
5960  s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
5961  }
5962  delete select;
5963  }
5964  }
5965 
5966  join->join_tab=stat;
5967  join->map2table=stat_ref;
5968  join->table= join->all_tables=table_vector;
5969  join->const_tables=const_count;
5970  join->found_const_table_map=found_const_table_map;
5971 
5972  /* Find an optimal join order of the non-constant tables. */
5973  if (join->const_tables != join->tables)
5974  {
5975  optimize_keyuse(join, keyuse_array);
5976  // @note c_str() is not likely to be valid here if dtrace expects it to
5977  // exist for any period of time.
5978  DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->getQueryString()->c_str(), join->session->thread_id);
5979  bool res= choose_plan(join, all_table_map & ~join->const_table_map);
5980  DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
5981  if (res)
5982  return true;
5983  }
5984  else
5985  {
5986  join->copyPartialPlanIntoOptimalPlan(join->const_tables);
5987  join->best_read= 1.0;
5988  }
5989  /* Generate an execution plan from the found optimal join order. */
5990  return join->session->getKilled() || get_best_combination(join);
5991 }
5992 
6012 static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
6013 {
6014  List<TableList>::iterator li(join_list->begin());
6015  while (TableList* table= li++)
6016  {
6017  if (NestedJoin* nested_join= table->getNestedJoin())
6018  {
6019  /*
6020  It is guaranteed by simplify_joins() function that a nested join
6021  that has only one child is either
6022  - a single-table view (the child is the underlying table), or
6023  - a single-table semi-join nest
6024 
6025  We don't assign bits to such sj-nests because
6026  1. it is redundant (a "sequence" of one table cannot be interleaved
6027  with anything)
6028  2. we could run out of bits in the nested join bitset otherwise.
6029  */
6030  if (nested_join->join_list.size() != 1)
6031  {
6032  /* Don't assign bits to sj-nests */
6033  if (table->on_expr)
6034  nested_join->nj_map.set(first_unused++);
6035  first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
6036  first_unused);
6037  }
6038  }
6039  }
6040  return(first_unused);
6041 }
6042 
6043 
6049 {
6050  table_map map= 0;
6051 
6052  if (!a)
6053  a= b; // Only one need to be given
6054  else if (!b)
6055  b= a;
6056 
6057  for (; a && b; a=a->next,b=b->next)
6058  {
6059  if (!(*a->item)->eq(*b->item,1))
6060  return NULL;
6061  map|= a->item[0]->used_tables();
6062  }
6063  if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
6064  return NULL;
6065 
6066  for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6067  if (map != tables->table->map)
6068  return NULL; // More than one table
6069  return tables->table;
6070 }
6071 
6081 static void reset_nj_counters(List<TableList> *join_list)
6082 {
6083  List<TableList>::iterator li(join_list->begin());
6084  while (TableList* table= li++)
6085  {
6086  NestedJoin *nested_join;
6087  if ((nested_join= table->getNestedJoin()))
6088  {
6089  nested_join->counter_= 0;
6090  reset_nj_counters(&nested_join->join_list);
6091  }
6092  }
6093 }
6094 
6101 static bool test_if_subpart(Order *a, Order *b)
6102 {
6103  for (; a && b; a=a->next,b=b->next)
6104  {
6105  if ((*a->item)->eq(*b->item,1))
6106  a->asc=b->asc;
6107  else
6108  return 0;
6109  }
6110  return test(!b);
6111 }
6112 
6166 {
6167  TableList *last_emb= last->table->pos_in_table_list->getEmbedding();
6168  Join *join= last->join;
6169  for (;last_emb != NULL; last_emb= last_emb->getEmbedding())
6170  {
6171  NestedJoin *nest= last_emb->getNestedJoin();
6172 
6173  bool was_fully_covered= nest->is_fully_covered();
6174 
6175  if (--nest->counter_ == 0)
6176  join->cur_embedding_map&= ~nest->nj_map;
6177 
6178  if (!was_fully_covered)
6179  break;
6180 
6181  join->cur_embedding_map|= nest->nj_map;
6182  }
6183 }
6184 
6189 static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6190 {
6191  if (!join_tab->ref.key_parts)
6192  return false;
6193 
6194  Item_cond_and *cond=new Item_cond_and();
6195  Table *table=join_tab->table;
6196 
6197  for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6198  {
6199  Field *field=table->getField(table->key_info[join_tab->ref.key].key_part[i].fieldnr - 1);
6200  Item *value=join_tab->ref.items[i];
6201  cond->add(new Item_func_equal(new Item_field(field), value));
6202  }
6203  if (session->is_fatal_error)
6204  return true;
6205 
6206  if (!cond->fixed)
6207  cond->fix_fields(session, (Item**)&cond);
6208  int error = 0;
6209  if (join_tab->select)
6210  {
6211  cond->add(join_tab->select->cond);
6212  join_tab->select_cond=join_tab->select->cond=cond;
6213  }
6214  else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0, &error)))
6215  join_tab->select_cond=cond;
6216 
6217  return error;
6218 }
6219 
6220 static void free_blobs(Field **ptr)
6221 {
6222  for (; *ptr ; ptr++)
6223  {
6224  if ((*ptr)->flags & BLOB_FLAG)
6225  ((Field_blob *) (*ptr))->free();
6226  }
6227 }
6228 
6233 } /* namespace drizzled */