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