1
/* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
4
* Copyright (C) 2008-2009 Sun Microsystems
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.
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.
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
24
* Implementation of the JOIN class
26
* @defgroup Query_Optimizer Query Optimizer
30
#include "drizzled/server_includes.h"
31
#include "drizzled/sj_tmp_table.h"
32
#include "drizzled/table_map_iterator.h"
33
#include "drizzled/item/cache.h"
34
#include "drizzled/item/cmpfunc.h"
35
#include "drizzled/item/copy_string.h"
36
#include "drizzled/item/uint.h"
37
#include "drizzled/cached_item.h"
38
#include "drizzled/sql_base.h"
39
#include "drizzled/sql_select.h" /* include join.h */
40
#include "drizzled/lock.h"
41
#include "drizzled/nested_join.h"
42
#include "drizzled/join.h"
43
#include "drizzled/join_cache.h"
44
#include "drizzled/show.h"
45
#include "drizzled/field/blob.h"
46
#include "mysys/my_bit.h"
48
/** Declarations of static functions used in this source file. */
49
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
50
static void calc_group_buffer(JOIN *join,order_st *group);
51
static bool alloc_group_fields(JOIN *join,order_st *group);
53
TODO: 'find_best' is here only temporarily until 'greedy_search' is
56
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index, double record_count,double read_time);
57
static uint32_t cache_record_length(JOIN *join, uint32_t index);
58
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
59
static bool get_best_combination(JOIN *join);
60
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
61
static bool choose_plan(JOIN *join,table_map join_tables);
62
static void best_access_path(JOIN *join, JOIN_TAB *s,
64
table_map remaining_tables,
68
static void optimize_straight_join(JOIN *join, table_map join_tables);
69
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
70
static bool best_extension_by_limited_search(JOIN *join,
71
table_map remaining_tables,
76
uint32_t prune_level);
77
static uint32_t determine_search_depth(JOIN* join);
78
static bool make_simple_join(JOIN *join,Table *tmp_table);
79
static void make_outerjoin_info(JOIN *join);
80
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
81
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
82
static void update_depend_map(JOIN *join);
83
static void update_depend_map(JOIN *join, order_st *order);
84
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
85
static int return_zero_rows(JOIN *join,
90
uint64_t select_options,
93
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top, bool in_sj);
94
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
95
static int setup_without_group(Session *session,
96
Item **ref_pointer_array,
100
List<Item> &all_fields,
104
bool *hidden_group_fields);
105
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
106
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
107
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
108
static void reset_nj_counters(List<TableList> *join_list);
109
static bool test_if_subpart(order_st *a,order_st *b);
110
static void restore_prev_nj_state(JOIN_TAB *last);
111
static uint32_t make_join_orderinfo(JOIN *join);
112
static int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
113
static void cleanup_sj_tmp_tables(JOIN *join);
114
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
115
static bool replace_where_subcondition(JOIN *join, Item *old_cond, Item *new_cond, bool fix_fields);
116
static int pull_out_semijoin_tables(JOIN *join);
117
static int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl);
118
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
119
static bool bitmap_covers(const table_map x, const table_map y);
120
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab);
123
Prepare of whole select (including sub queries in future).
126
Add check of calculation of GROUP functions and fields:
127
SELECT COUNT(*)+table.col1 from table1;
134
int JOIN::prepare(Item ***rref_pointer_array,
135
TableList *tables_init,
139
order_st *order_init,
140
order_st *group_init,
142
Select_Lex *select_lex_arg,
143
Select_Lex_Unit *unit_arg)
145
// to prevent double initialization on EXPLAIN
151
group_list= group_init;
153
tables_list= tables_init;
154
select_lex= select_lex_arg;
155
select_lex->join= this;
156
join_list= &select_lex->top_join_list;
157
union_part= unit_arg->is_union();
159
session->lex->current_select->is_item_list_lookup= 1;
161
If we have already executed SELECT, then it have not sense to prevent
162
its table from update (see unique_table())
164
if (session->derived_tables_processing)
165
select_lex->exclude_from_table_unique_test= true;
167
/* Check that all tables, fields, conds and order are ok */
169
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
170
setup_tables_and_check_access(session, &select_lex->context, join_list,
171
tables_list, &select_lex->leaf_tables,
175
TableList *table_ptr;
176
for (table_ptr= select_lex->leaf_tables;
178
table_ptr= table_ptr->next_leaf)
181
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
182
select_lex->setup_ref_array(session, og_num) ||
183
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
185
setup_without_group(session, (*rref_pointer_array), tables_list,
186
select_lex->leaf_tables, fields_list,
187
all_fields, &conds, order, group_list,
188
&hidden_group_fields))
189
return(-1); /* purecov: inspected */
191
ref_pointer_array= *rref_pointer_array;
195
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
196
session->where="having clause";
197
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
198
select_lex->having_fix_field= 1;
199
bool having_fix_rc= (!having->fixed &&
200
(having->fix_fields(session, &having) ||
201
having->check_cols(1)));
202
select_lex->having_fix_field= 0;
203
if (having_fix_rc || session->is_error())
204
return(-1); /* purecov: inspected */
205
session->lex->allow_sum_func= save_allow_sum_func;
209
Item_subselect *subselect;
210
Item_in_subselect *in_subs= NULL;
212
Are we in a subquery predicate?
213
TODO: the block below will be executed for every PS execution without need.
215
if ((subselect= select_lex->master_unit()->item))
217
bool do_semijoin= !test(session->variables.optimizer_switch &
218
OPTIMIZER_SWITCH_NO_SEMIJOIN);
219
if (subselect->substype() == Item_subselect::IN_SUBS)
220
in_subs= (Item_in_subselect*)subselect;
223
Check if we're in subquery that is a candidate for flattening into a
224
semi-join (which is done done in flatten_subqueries()). The
226
1. Subquery predicate is an IN/=ANY subq predicate
227
2. Subquery is a single SELECT (not a UNION)
228
3. Subquery does not have GROUP BY or order_st BY
229
4. Subquery does not use aggregate functions or HAVING
230
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
231
6. No execution method was already chosen (by a prepared statement).
233
(*). We are not in a subquery of a single table UPDATE/DELETE that
234
doesn't have a JOIN (TODO: We should handle this at some
235
point by switching to multi-table UPDATE/DELETE)
237
(**). We're not in a confluent table-less subquery, like
241
!select_lex->master_unit()->first_select()->next_select() && // 2
242
!select_lex->group_list.elements && !order && // 3
243
!having && !select_lex->with_sum_func && // 4
244
session->session_marker && // 5
245
select_lex->outer_select()->join && // (*)
246
select_lex->master_unit()->first_select()->leaf_tables && // (**)
248
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
251
if (!in_subs->left_expr->fixed &&
252
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
257
Check that the right part of the subselect contains no more than one
258
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
260
if (subselect->substype() == Item_subselect::IN_SUBS &&
261
(select_lex->item_list.elements !=
262
((Item_in_subselect*)subselect)->left_expr->cols()))
264
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
269
/* Register the subquery for further processing */
270
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
271
in_subs->expr_join_nest= (TableList*)session->session_marker;
275
bool do_materialize= !test(session->variables.optimizer_switch &
276
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
278
Check if the subquery predicate can be executed via materialization.
279
The required conditions are:
280
1. Subquery predicate is an IN/=ANY subq predicate
281
2. Subquery is a single SELECT (not a UNION)
282
3. Subquery is not a table-less query. In this case there is no
283
point in materializing.
284
4. Subquery predicate is a top-level predicate
285
(this implies it is not negated)
286
TODO: this is a limitation that should be lifeted once we
287
implement correct NULL semantics (WL#3830)
288
5. Subquery is non-correlated
290
This is an overly restrictive condition. It can be extended to:
291
(Subquery is non-correlated ||
292
Subquery is correlated to any query outer to IN predicate ||
293
(Subquery is correlated to the immediate outer query &&
294
Subquery !contains {GROUP BY, order_st BY [LIMIT],
295
aggregate functions) && subquery predicate is not under "NOT IN"))
296
6. No execution method was already chosen (by a prepared statement).
298
(*) The subquery must be part of a SELECT statement. The current
299
condition also excludes multi-table update statements.
301
We have to determine whether we will perform subquery materialization
302
before calling the IN=>EXISTS transformation, so that we know whether to
303
perform the whole transformation or only that part of it which wraps
304
Item_in_subselect in an Item_in_optimizer.
306
if (do_materialize &&
308
!select_lex->master_unit()->first_select()->next_select() && // 2
309
select_lex->master_unit()->first_select()->leaf_tables && // 3
310
session->lex->sql_command == SQLCOM_SELECT) // *
312
if (in_subs->is_top_level_item() && // 4
313
!in_subs->is_correlated && // 5
314
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
315
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
318
Item_subselect::trans_res trans_res;
319
if ((trans_res= subselect->select_transformer(this)) !=
320
Item_subselect::RES_OK)
322
return((trans_res == Item_subselect::RES_ERROR));
331
for (ord= order; ord; ord= ord->next)
333
Item *item= *ord->item;
334
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
335
item->split_sum_func(session, ref_pointer_array, all_fields);
339
if (having && having->with_sum_func)
340
having->split_sum_func(session, ref_pointer_array, all_fields,
342
if (select_lex->inner_sum_func_list)
344
Item_sum *end=select_lex->inner_sum_func_list;
345
Item_sum *item_sum= end;
348
item_sum= item_sum->next;
349
item_sum->split_sum_func(session, ref_pointer_array,
350
all_fields, item_sum->ref_by, false);
351
} while (item_sum != end);
354
if (select_lex->inner_refs_list.elements &&
355
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
359
Check if there are references to un-aggregated columns when computing
360
aggregate functions with implicit grouping (there is no GROUP BY).
362
MODE_ONLY_FULL_GROUP_BY is enabled here by default
364
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
366
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
367
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
371
/* Caclulate the number of groups */
373
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
378
goto err; /* purecov: inspected */
380
if (result && result->prepare(fields_list, unit_arg))
381
goto err; /* purecov: inspected */
383
/* Init join struct */
384
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
385
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
386
this->group= group_list != 0;
389
#ifdef RESTRICTED_GROUP
390
if (sum_func_count && !group_list && (func_count || field_count))
392
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
396
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
398
if (alloc_func_list())
404
return(-1); /* purecov: inspected */
408
Remove the predicates pushed down into the subquery
411
JOIN::remove_subq_pushed_predicates()
412
where IN Must be NULL
413
OUT The remaining WHERE condition, or NULL
416
Given that this join will be executed using (unique|index)_subquery,
417
without "checking NULL", remove the predicates that were pushed down
420
If the subquery compares scalar values, we can remove the condition that
421
was wrapped into trig_cond (it will be checked when needed by the subquery
424
If the subquery compares row values, we need to keep the wrapped
425
equalities in the WHERE clause: when the left (outer) tuple has both NULL
426
and non-NULL values, we'll do a full table scan and will rely on the
427
equalities corresponding to non-NULL parts of left tuple to filter out
428
non-matching records.
430
TODO: We can remove the equalities that will be guaranteed to be true by the
431
fact that subquery engine will be using index lookup. This must be done only
432
for cases where there are no conversion errors of significance, e.g. 257
433
that is searched in a byte. But this requires homogenization of the return
434
codes of all Field*::store() methods.
436
void JOIN::remove_subq_pushed_predicates(Item **where)
438
if (conds->type() == Item::FUNC_ITEM &&
439
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
440
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
441
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
442
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
443
((Item_func *)conds)->arguments()[0]))
451
global select optimisation.
454
error code saved in field 'error'
463
// to prevent double initialization on EXPLAIN
468
session->set_proc_info("optimizing");
469
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
470
unit->select_limit_cnt);
471
/* select_limit is used to decide if we are likely to scan the whole table */
472
select_limit= unit->select_limit_cnt;
473
if (having || (select_options & OPTION_FOUND_ROWS))
474
select_limit= HA_POS_ERROR;
475
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
476
// Ignore errors of execution if option IGNORE present
477
if (session->lex->ignore)
478
session->lex->current_select->no_error= 1;
480
#ifdef HAVE_REF_TO_FIELDS // Not done yet
481
/* Add HAVING to WHERE if possible */
482
if (having && !group_list && !sum_func_count)
489
else if ((conds=new Item_cond_and(conds,having)))
492
Item_cond_and can't be fixed after creation, so we do not check
495
conds->fix_fields(session, &conds);
496
conds->change_ref_to_fields(session, tables_list);
497
conds->top_level_item();
503
/* Convert all outer joins to inner joins if possible */
504
conds= simplify_joins(this, join_list, conds, true, false);
505
build_bitmap_for_nested_joins(join_list, 0);
507
conds= optimize_cond(this, conds, join_list, &cond_value);
508
if (session->is_error())
515
having= optimize_cond(this, having, join_list, &having_value);
516
if (session->is_error())
521
if (select_lex->where)
522
select_lex->cond_value= cond_value;
523
if (select_lex->having)
524
select_lex->having_value= having_value;
526
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
527
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
528
{ /* Impossible cond */
529
zero_result_cause= having_value == Item::COND_FALSE ?
530
"Impossible HAVING" : "Impossible WHERE";
536
/* Optimize count(*), cmin() and cmax() */
537
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
541
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
542
to the WHERE conditions,
543
or 1 if all items were resolved,
544
or 0, or an error number HA_ERR_...
546
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
548
if (res == HA_ERR_KEY_NOT_FOUND)
550
zero_result_cause= "No matching min/max row";
561
zero_result_cause= "No matching min/max row";
565
zero_result_cause= "Select tables optimized away";
566
tables_list= 0; // All tables resolved
568
Extract all table-independent conditions and replace the WHERE
569
clause with them. All other conditions were computed by opt_sum_query
570
and the MIN/MAX/COUNT function(s) have been replaced by constants,
571
so there is no need to compute the whole WHERE clause again.
572
Notice that make_cond_for_table() will always succeed to remove all
573
computed conditions, because opt_sum_query() is applicable only to
575
Preserve conditions for EXPLAIN.
577
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
579
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
580
conds= table_independent_conds;
589
error= -1; // Error is sent to client
590
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
592
/* Calculate how to do the join */
593
session->set_proc_info("statistics");
594
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
595
session->is_fatal_error)
600
/* Remove distinct if only const tables */
601
select_distinct= select_distinct && (const_tables != tables);
602
session->set_proc_info("preparing");
603
if (result->initialize_tables(this))
605
return(1); // error == -1
607
if (const_table_map != found_const_table_map &&
608
!(select_options & SELECT_DESCRIBE) &&
610
!(conds->used_tables() & RAND_TABLE_BIT) ||
611
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
613
zero_result_cause= "no matching row in const table";
617
if (!(session->options & OPTION_BIG_SELECTS) &&
618
best_read > (double) session->variables.max_join_size &&
619
!(select_options & SELECT_DESCRIBE))
620
{ /* purecov: inspected */
621
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
625
if (const_tables && !session->locked_tables &&
626
!(select_options & SELECT_NO_UNLOCK))
627
mysql_unlock_some_tables(session, table, const_tables);
628
if (!conds && outer_join)
630
/* Handle the case where we have an OUTER JOIN without a WHERE */
631
conds=new Item_int((int64_t) 1,1); // Always true
633
select= make_select(*table, const_table_map,
634
const_table_map, conds, 1, &error);
636
{ /* purecov: inspected */
637
error= -1; /* purecov: inspected */
641
reset_nj_counters(join_list);
642
make_outerjoin_info(this);
645
Among the equal fields belonging to the same multiple equality
646
choose the one that is to be retrieved first and substitute
647
all references to these in where condition for a reference for
652
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
653
conds->update_used_tables();
657
Permorm the the optimization on fields evaluation mentioned above
658
for all on expressions.
660
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
662
if (*tab->on_expr_ref)
664
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
667
(*tab->on_expr_ref)->update_used_tables();
671
if (conds &&!outer_join && const_table_map != found_const_table_map &&
672
(select_options & SELECT_DESCRIBE) &&
673
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
675
conds=new Item_int((int64_t) 0,1); // Always false
677
if (make_join_select(this, select, conds))
680
"Impossible WHERE noticed after reading const tables";
681
return(0); // error == 0
684
error= -1; /* if goto err */
686
/* Optimize distinct away if possible */
688
order_st *org_order= order;
689
order= remove_constants(this, order,conds,1, &simple_order);
690
if (session->is_error())
697
If we are using order_st BY NULL or order_st BY const_expression,
698
return result in any order (even if we are using a GROUP BY)
700
if (!order && org_order)
704
Check if we can optimize away GROUP BY/DISTINCT.
705
We can do that if there are no aggregate functions, the
706
fields in DISTINCT clause (if present) and/or columns in GROUP BY
707
(if present) contain direct references to all key parts of
708
an unique index (in whatever order) and if the key parts of the
709
unique index cannot contain NULLs.
710
Note that the unique keys for DISTINCT and GROUP BY should not
711
be the same (as long as they are unique).
713
The FROM clause must contain a single non-constant table.
715
if (tables - const_tables == 1 && (group_list || select_distinct) &&
716
!tmp_table_param.sum_func_count &&
717
(!join_tab[const_tables].select ||
718
!join_tab[const_tables].select->quick ||
719
join_tab[const_tables].select->quick->get_type() !=
720
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
722
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
725
We have found that grouping can be removed since groups correspond to
726
only one row anyway, but we still have to guarantee correct result
727
order. The line below effectively rewrites the query from GROUP BY
728
<fields> to order_st BY <fields>. There are two exceptions:
729
- if skip_sort_order is set (see above), then we can simply skip
731
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
732
with the GROUP BY ones, i.e. either one is a prefix of another.
733
We only check if the order_st BY is a prefix of GROUP BY. In this case
734
test_if_subpart() copies the ASC/DESC attributes from the original
736
If GROUP BY is a prefix of order_st BY, then it is safe to leave
739
if (!order || test_if_subpart(group_list, order))
740
order= skip_sort_order ? 0 : group_list;
742
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
743
rewritten to IGNORE INDEX FOR order_st BY(fields).
745
join_tab->table->keys_in_use_for_order_by=
746
join_tab->table->keys_in_use_for_group_by;
750
if (select_distinct &&
751
list_contains_unique_index(join_tab[const_tables].table,
752
find_field_in_item_list,
753
(void *) &fields_list))
758
if (group_list || tmp_table_param.sum_func_count)
760
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
763
else if (select_distinct && tables - const_tables == 1)
766
We are only using one table. In this case we change DISTINCT to a
768
- The GROUP BY can be done through indexes (no sort) and the order_st
769
BY only uses selected fields.
770
(In this case we can later optimize away GROUP BY and order_st BY)
771
- We are scanning the whole table without LIMIT
773
- We are using CALC_FOUND_ROWS
774
- We are using an order_st BY that can't be optimized away.
776
We don't want to use this optimization when we are using LIMIT
777
because in this case we can just create a temporary table that
778
holds LIMIT rows and stop when this table is full.
780
JOIN_TAB *tab= &join_tab[const_tables];
781
bool all_order_fields_used;
783
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
784
&tab->table->keys_in_use_for_order_by);
785
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
786
order, fields_list, all_fields,
787
&all_order_fields_used)))
789
bool skip_group= (skip_sort_order &&
790
test_if_skip_sort_order(tab, group_list, select_limit, 1,
791
&tab->table->keys_in_use_for_group_by) != 0);
792
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
793
if ((skip_group && all_order_fields_used) ||
794
select_limit == HA_POS_ERROR ||
795
(order && !skip_sort_order))
797
/* Change DISTINCT to GROUP BY */
800
if (all_order_fields_used)
802
if (order && skip_sort_order)
805
Force MySQL to read the table in sorted order to get result in
808
tmp_table_param.quick_group=0;
812
group=1; // For end_write_group
817
else if (session->is_fatal_error) // End of memory
822
order_st *old_group_list;
823
group_list= remove_constants(this, (old_group_list= group_list), conds,
824
rollup.state == ROLLUP::STATE_NONE,
826
if (session->is_error())
831
if (old_group_list && !group_list)
834
if (!group_list && group)
836
order=0; // The output has only one row
838
select_distinct= 0; // No need in distinct for 1 row
839
group_optimized_away= 1;
842
calc_group_buffer(this, group_list);
843
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
845
if (test_if_subpart(group_list, order) ||
846
(!group_list && tmp_table_param.sum_func_count))
849
// Can't use sort on head table if using row cache
859
Check if we need to create a temporary table.
860
This has to be done if all tables are not already read (const tables)
861
and one of the following conditions holds:
862
- We are using DISTINCT (simple distinct's are already optimized away)
863
- We are using an order_st BY or GROUP BY on fields not in the first table
864
- We are using different order_st BY and GROUP BY orders
865
- The user wants us to buffer the result.
867
need_tmp= (const_tables != tables &&
868
((select_distinct || !simple_order || !simple_group) ||
869
(group_list && order) ||
870
test(select_options & OPTION_BUFFER_RESULT)));
872
uint32_t no_jbuf_after= make_join_orderinfo(this);
873
uint64_t select_opts_for_readinfo=
874
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
877
if (!select_lex->sj_nests.is_empty())
878
setup_semijoin_dups_elimination(this, select_opts_for_readinfo, no_jbuf_after);
880
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
881
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
884
/* Create all structures needed for materialized subquery execution. */
885
if (setup_subquery_materialization())
889
is this simple IN subquery?
891
if (!group_list && !order &&
892
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
893
tables == 1 && conds &&
899
if (join_tab[0].type == JT_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
901
remove_subq_pushed_predicates(&where);
902
save_index_subquery_explain_info(join_tab, where);
903
join_tab[0].type= JT_UNIQUE_SUBQUERY;
907
subselect_uniquesubquery_engine(session,
912
else if (join_tab[0].type == JT_REF &&
913
join_tab[0].ref.items[0]->name == in_left_expr_name)
915
remove_subq_pushed_predicates(&where);
916
save_index_subquery_explain_info(join_tab, where);
917
join_tab[0].type= JT_INDEX_SUBQUERY;
921
subselect_indexsubquery_engine(session,
929
else if (join_tab[0].type == JT_REF_OR_NULL &&
930
join_tab[0].ref.items[0]->name == in_left_expr_name &&
931
having->name == in_having_cond)
933
join_tab[0].type= JT_INDEX_SUBQUERY;
935
conds= remove_additional_cond(conds);
936
save_index_subquery_explain_info(join_tab, conds);
938
change_engine(new subselect_indexsubquery_engine(session,
948
Need to tell handlers that to play it safe, it should fetch all
949
columns of the primary key of the tables: this is because MySQL may
950
build row pointers for the rows, and for all columns of the primary key
951
the read set has not necessarily been set by the server code.
953
if (need_tmp || select_distinct || group_list || order)
955
for (uint32_t i = const_tables; i < tables; i++)
956
join_tab[i].table->prepare_for_position();
959
if (const_tables != tables)
962
Because filesort always does a full table scan or a quick range scan
963
we must add the removed reference to the select for the table.
964
We only need to do this when we have a simple_order or simple_group
965
as in other cases the join is done before the sort.
967
if ((order || group_list) &&
968
(join_tab[const_tables].type != JT_ALL) &&
969
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
970
((order && simple_order) || (group_list && simple_group)))
972
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
977
if (!(select_options & SELECT_BIG_RESULT) &&
980
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
981
unit->select_limit_cnt, 0,
982
&join_tab[const_tables].table->
983
keys_in_use_for_group_by))) ||
985
tmp_table_param.quick_group)
987
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
992
Force using of tmp table if sorting by a SP or UDF function due to
993
their expensive and probably non-deterministic nature.
995
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
997
Item *item= *tmp_order->item;
998
if (item->is_expensive())
1000
/* Force tmp table without sort */
1001
need_tmp=1; simple_order=simple_group=0;
1009
if (select_options & SELECT_DESCRIBE)
1017
The loose index scan access method guarantees that all grouping or
1018
duplicate row elimination (for distinct) is already performed
1019
during data retrieval, and that all MIN/MAX functions are already
1020
computed for each group. Thus all MIN/MAX functions should be
1021
treated as regular functions, and there is no need to perform
1022
grouping in the main execution loop.
1023
Notice that currently loose index scan is applicable only for
1024
single table queries, thus it is sufficient to test only the first
1025
join_tab element of the plan for its access method.
1027
if (join_tab->is_using_loose_index_scan())
1028
tmp_table_param.precomputed_group_by= true;
1030
/* Create a tmp table if distinct or if the sort is too complicated */
1033
session->set_proc_info("Creating tmp table");
1035
init_items_ref_array();
1037
tmp_table_param.hidden_field_count= (all_fields.elements -
1038
fields_list.elements);
1039
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1042
Pushing LIMIT to the temporary table creation is not applicable
1043
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1044
there are aggregate functions, because in all these cases we need
1047
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1049
!session->lex->current_select->with_sum_func) ?
1050
select_limit : HA_POS_ERROR;
1052
if (!(exec_tmp_table1=
1053
create_tmp_table(session, &tmp_table_param, all_fields,
1055
group_list ? 0 : select_distinct,
1056
group_list && simple_group,
1065
We don't have to store rows in temp table that doesn't match HAVING if:
1066
- we are sorting the table and writing complete group rows to the
1068
- We are using DISTINCT without resolving the distinct as a GROUP BY
1071
If having is not handled here, it will be checked before the row
1072
is sent to the client.
1074
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1077
/* if group or order on first table, sort first */
1078
if (group_list && simple_group)
1080
session->set_proc_info("Sorting for group");
1081
if (create_sort_index(session, this, group_list,
1082
HA_POS_ERROR, HA_POS_ERROR, false) ||
1083
alloc_group_fields(this, group_list) ||
1084
make_sum_func_list(all_fields, fields_list, 1) ||
1085
setup_sum_funcs(session, sum_funcs))
1093
if (make_sum_func_list(all_fields, fields_list, 0) ||
1094
setup_sum_funcs(session, sum_funcs))
1099
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1101
session->set_proc_info("Sorting for order");
1102
if (create_sort_index(session, this, order,
1103
HA_POS_ERROR, HA_POS_ERROR, true))
1112
Optimize distinct when used on some of the tables
1113
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1114
In this case we can stop scanning t2 when we have found one t1.a
1117
if (exec_tmp_table1->distinct)
1119
table_map used_tables= session->used_tables;
1120
JOIN_TAB *last_join_tab= join_tab+tables-1;
1123
if (used_tables & last_join_tab->table->map)
1125
last_join_tab->not_used_in_distinct=1;
1126
} while (last_join_tab-- != join_tab);
1127
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1128
if (order && skip_sort_order)
1130
/* Should always succeed */
1131
if (test_if_skip_sort_order(&join_tab[const_tables],
1132
order, unit->select_limit_cnt, 0,
1133
&join_tab[const_tables].table->
1134
keys_in_use_for_order_by))
1140
If this join belongs to an uncacheable subquery save
1143
if (select_lex->uncacheable && !is_top_level_join() &&
1144
init_save_join_tab())
1145
return(-1); /* purecov: inspected */
1153
Restore values in temporary join.
1155
void JOIN::restore_tmp()
1157
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1162
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1163
select_lex->offset_limit->val_uint() :
1168
if (exec_tmp_table1)
1170
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1171
exec_tmp_table1->file->ha_delete_all_rows();
1172
free_io_cache(exec_tmp_table1);
1173
filesort_free_buffers(exec_tmp_table1,0);
1175
if (exec_tmp_table2)
1177
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1178
exec_tmp_table2->file->ha_delete_all_rows();
1179
free_io_cache(exec_tmp_table2);
1180
filesort_free_buffers(exec_tmp_table2,0);
1183
set_items_ref_array(items0);
1186
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1191
/* Reset of sum functions */
1194
Item_sum *func, **func_ptr= sum_funcs;
1195
while ((func= *(func_ptr++)))
1203
@brief Save the original join layout
1205
@details Saves the original join layout so it can be reused in
1206
re-execution and for EXPLAIN.
1208
@return Operation status
1210
@retval 1 error occurred.
1212
bool JOIN::init_save_join_tab()
1214
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
1215
return 1; /* purecov: inspected */
1216
error= 0; // Ensure that tmp_join.error= 0
1221
bool JOIN::save_join_tab()
1223
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1225
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
1226
sizeof(JOIN_TAB) * tables)))
1236
Note, that create_sort_index calls test_if_skip_sort_order and may
1237
finally replace sorting with index scan if there is a LIMIT clause in
1238
the query. It's never shown in EXPLAIN!
1241
When can we have here session->net.report_error not zero?
1245
List<Item> *columns_list= &fields_list;
1248
session->set_proc_info("executing");
1251
if (!tables_list && (tables || !select_lex->with_sum_func))
1253
/* Only test of functions */
1254
if (select_options & SELECT_DESCRIBE)
1255
select_describe(this, false, false, false, (zero_result_cause?zero_result_cause:"No tables used"));
1258
result->send_fields(*columns_list, Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
1260
We have to test for 'conds' here as the WHERE may not be constant
1261
even if we don't have any tables for prepared statements or if
1262
conds uses something like 'rand()'.
1264
if (cond_value != Item::COND_FALSE &&
1265
(!conds || conds->val_int()) &&
1266
(!having || having->val_int()))
1268
if (do_send_rows && result->send_data(fields_list))
1272
error= (int) result->send_eof();
1273
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1278
error= (int) result->send_eof();
1282
/* Single select (without union) always returns 0 or 1 row */
1283
session->limit_found_rows= send_records;
1284
session->examined_row_count= 0;
1288
Don't reset the found rows count if there're no tables as
1289
FOUND_ROWS() may be called. Never reset the examined row count here.
1290
It must be accumulated from all join iterations of all join parts.
1293
session->limit_found_rows= 0;
1295
if (zero_result_cause)
1297
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1299
send_row_on_empty_set(),
1306
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) && get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
1309
if (select_options & SELECT_DESCRIBE)
1312
Check if we managed to optimize order_st BY away and don't use temporary
1313
table to resolve order_st BY: in that case, we only may need to do
1314
filesort for GROUP BY.
1316
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1318
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1320
simple_order= simple_group;
1323
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1325
if (const_tables == tables
1326
|| ((simple_order || skip_sort_order)
1327
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1331
select_describe(this, need_tmp, order != 0 && !skip_sort_order, select_distinct, !tables ? "No tables used" : NULL);
1335
JOIN *curr_join= this;
1336
List<Item> *curr_all_fields= &all_fields;
1337
List<Item> *curr_fields_list= &fields_list;
1338
Table *curr_tmp_table= 0;
1340
Initialize examined rows here because the values from all join parts
1341
must be accumulated in examined_row_count. Hence every join
1342
iteration must count from zero.
1344
curr_join->examined_rows= 0;
1346
/* Create a tmp table if distinct or if the sort is too complicated */
1352
We are in a non cacheable sub query. Get the saved join structure
1354
(curr_join may have been modified during last exection and we need
1357
curr_join= tmp_join;
1359
curr_tmp_table= exec_tmp_table1;
1361
/* Copy data to the temporary table */
1362
session->set_proc_info("Copying to tmp table");
1363
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1364
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1365
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1370
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
1372
if (curr_join->having)
1373
curr_join->having= curr_join->tmp_having= 0; // Allready done
1375
/* Change sum_fields reference to calculated fields in tmp_table */
1376
curr_join->all_fields= *curr_all_fields;
1379
items1= items0 + all_fields.elements;
1380
if (sort_and_group || curr_tmp_table->group)
1382
if (change_to_use_tmp_fields(session, items1,
1383
tmp_fields_list1, tmp_all_fields1,
1384
fields_list.elements, all_fields))
1389
if (change_refs_to_tmp_fields(session, items1,
1390
tmp_fields_list1, tmp_all_fields1,
1391
fields_list.elements, all_fields))
1394
curr_join->tmp_all_fields1= tmp_all_fields1;
1395
curr_join->tmp_fields_list1= tmp_fields_list1;
1396
curr_join->items1= items1;
1398
curr_all_fields= &tmp_all_fields1;
1399
curr_fields_list= &tmp_fields_list1;
1400
curr_join->set_items_ref_array(items1);
1402
if (sort_and_group || curr_tmp_table->group)
1404
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1405
+ curr_join->tmp_table_param.func_count;
1406
curr_join->tmp_table_param.sum_func_count= 0;
1407
curr_join->tmp_table_param.func_count= 0;
1411
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1412
curr_join->tmp_table_param.func_count= 0;
1415
if (curr_tmp_table->group)
1416
{ // Already grouped
1417
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1418
curr_join->order= curr_join->group_list; /* order by group */
1419
curr_join->group_list= 0;
1423
If we have different sort & group then we must sort the data by group
1424
and copy it to another tmp table
1425
This code is also used if we are using distinct something
1426
we haven't been able to store in the temporary table yet
1427
like SEC_TO_TIME(SUM(...)).
1430
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1431
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1432
{ /* Must copy to another table */
1433
/* Free first data from old join */
1434
curr_join->join_free();
1435
if (make_simple_join(curr_join, curr_tmp_table))
1437
calc_group_buffer(curr_join, group_list);
1438
count_field_types(select_lex, &curr_join->tmp_table_param,
1439
curr_join->tmp_all_fields1,
1440
curr_join->select_distinct && !curr_join->group_list);
1441
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1442
- curr_join->tmp_fields_list1.elements;
1444
if (exec_tmp_table2)
1445
curr_tmp_table= exec_tmp_table2;
1448
/* group data to new table */
1451
If the access method is loose index scan then all MIN/MAX
1452
functions are precomputed, and should be treated as regular
1453
functions. See extended comment in JOIN::exec.
1455
if (curr_join->join_tab->is_using_loose_index_scan())
1456
curr_join->tmp_table_param.precomputed_group_by= true;
1458
if (!(curr_tmp_table=
1459
exec_tmp_table2= create_tmp_table(session,
1460
&curr_join->tmp_table_param,
1463
curr_join->select_distinct &&
1464
!curr_join->group_list,
1465
1, curr_join->select_options,
1469
curr_join->exec_tmp_table2= exec_tmp_table2;
1471
if (curr_join->group_list)
1473
session->set_proc_info("Creating sort index");
1474
if (curr_join->join_tab == join_tab && save_join_tab())
1478
if (create_sort_index(session, curr_join, curr_join->group_list,
1479
HA_POS_ERROR, HA_POS_ERROR, false) ||
1480
make_group_fields(this, curr_join))
1484
sortorder= curr_join->sortorder;
1487
session->set_proc_info("Copying to group table");
1489
if (curr_join != this)
1493
curr_join->sum_funcs= sum_funcs2;
1494
curr_join->sum_funcs_end= sum_funcs_end2;
1498
curr_join->alloc_func_list();
1499
sum_funcs2= curr_join->sum_funcs;
1500
sum_funcs_end2= curr_join->sum_funcs_end;
1503
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1505
curr_join->group_list= 0;
1507
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1508
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1510
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1511
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1516
end_read_record(&curr_join->join_tab->read_record);
1517
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1518
curr_join->join_tab[0].table= 0; // Table is freed
1520
// No sum funcs anymore
1523
items2= items1 + all_fields.elements;
1524
if (change_to_use_tmp_fields(session, items2,
1525
tmp_fields_list2, tmp_all_fields2,
1526
fields_list.elements, tmp_all_fields1))
1528
curr_join->tmp_fields_list2= tmp_fields_list2;
1529
curr_join->tmp_all_fields2= tmp_all_fields2;
1531
curr_fields_list= &curr_join->tmp_fields_list2;
1532
curr_all_fields= &curr_join->tmp_all_fields2;
1533
curr_join->set_items_ref_array(items2);
1534
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1535
curr_join->tmp_table_param.sum_func_count= 0;
1537
if (curr_tmp_table->distinct)
1538
curr_join->select_distinct=0; /* Each row is unique */
1540
curr_join->join_free(); /* Free quick selects */
1541
if (curr_join->select_distinct && ! curr_join->group_list)
1543
session->set_proc_info("Removing duplicates");
1544
if (curr_join->tmp_having)
1545
curr_join->tmp_having->update_used_tables();
1547
if (remove_duplicates(curr_join, curr_tmp_table,
1548
*curr_fields_list, curr_join->tmp_having))
1551
curr_join->tmp_having=0;
1552
curr_join->select_distinct=0;
1554
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1555
if (make_simple_join(curr_join, curr_tmp_table))
1557
calc_group_buffer(curr_join, curr_join->group_list);
1558
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1562
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1564
if (make_group_fields(this, curr_join))
1570
init_items_ref_array();
1571
items3= ref_pointer_array + (all_fields.elements*4);
1572
setup_copy_fields(session, &curr_join->tmp_table_param,
1573
items3, tmp_fields_list3, tmp_all_fields3,
1574
curr_fields_list->elements, *curr_all_fields);
1575
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1576
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1577
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1578
curr_join->tmp_all_fields3= tmp_all_fields3;
1579
curr_join->tmp_fields_list3= tmp_fields_list3;
1583
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1584
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1585
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1587
curr_fields_list= &tmp_fields_list3;
1588
curr_all_fields= &tmp_all_fields3;
1589
curr_join->set_items_ref_array(items3);
1591
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1593
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1594
session->is_fatal_error)
1597
if (curr_join->group_list || curr_join->order)
1599
session->set_proc_info("Sorting result");
1600
/* If we have already done the group, add HAVING to sorted table */
1601
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1603
// Some tables may have been const
1604
curr_join->tmp_having->update_used_tables();
1605
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
1606
table_map used_tables= (curr_join->const_table_map |
1607
curr_table->table->map);
1609
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1610
if (sort_table_cond)
1612
if (!curr_table->select)
1613
if (!(curr_table->select= new SQL_SELECT))
1615
if (!curr_table->select->cond)
1616
curr_table->select->cond= sort_table_cond;
1617
else // This should never happen
1619
if (!(curr_table->select->cond=
1620
new Item_cond_and(curr_table->select->cond,
1624
Item_cond_and do not need fix_fields for execution, its parameters
1625
are fixed or do not need fix_fields, too
1627
curr_table->select->cond->quick_fix_field();
1629
curr_table->select_cond= curr_table->select->cond;
1630
curr_table->select_cond->top_level_item();
1631
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1638
curr_join->select_limit= HA_POS_ERROR;
1642
We can abort sorting after session->select_limit rows if we there is no
1643
WHERE clause for any tables after the sorted one.
1645
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1646
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
1647
for (; curr_table < end_table ; curr_table++)
1650
table->keyuse is set in the case there was an original WHERE clause
1651
on the table that was optimized away.
1653
if (curr_table->select_cond ||
1654
(curr_table->keyuse && !curr_table->first_inner))
1656
/* We have to sort all rows */
1657
curr_join->select_limit= HA_POS_ERROR;
1662
if (curr_join->join_tab == join_tab && save_join_tab())
1665
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1666
chose FILESORT to be faster than INDEX SCAN or there is no
1667
suitable index present.
1668
Note, that create_sort_index calls test_if_skip_sort_order and may
1669
finally replace sorting with index scan if there is a LIMIT clause in
1670
the query. XXX: it's never shown in EXPLAIN!
1671
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1673
if (create_sort_index(session, curr_join,
1674
curr_join->group_list ?
1675
curr_join->group_list : curr_join->order,
1676
curr_join->select_limit,
1677
(select_options & OPTION_FOUND_ROWS ?
1678
HA_POS_ERROR : unit->select_limit_cnt),
1679
curr_join->group_list ? true : false))
1682
sortorder= curr_join->sortorder;
1683
if (curr_join->const_tables != curr_join->tables &&
1684
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1687
If no IO cache exists for the first table then we are using an
1688
INDEX SCAN and no filesort. Thus we should not remove the sorted
1689
attribute on the INDEX SCAN.
1695
/* XXX: When can we have here session->is_error() not zero? */
1696
if (session->is_error())
1698
error= session->is_error();
1701
curr_join->having= curr_join->tmp_having;
1702
curr_join->fields= curr_fields_list;
1704
session->set_proc_info("Sending data");
1705
result->send_fields(*curr_fields_list,
1706
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
1707
error= do_select(curr_join, curr_fields_list, NULL);
1708
session->limit_found_rows= curr_join->send_records;
1710
/* Accumulate the counts from all join iterations of all join parts. */
1711
session->examined_row_count+= curr_join->examined_rows;
1714
With EXPLAIN EXTENDED we have to restore original ref_array
1715
for a derived table which is always materialized.
1716
Otherwise we would not be able to print the query correctly.
1718
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1719
set_items_ref_array(items0);
1728
Return error that hold JOIN.
1732
select_lex->join= 0;
1736
if (join_tab != tmp_join->join_tab)
1738
JOIN_TAB *tab, *end;
1739
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1742
tmp_join->tmp_join= 0;
1743
tmp_table_param.copy_field=0;
1744
return(tmp_join->destroy());
1749
if (exec_tmp_table1)
1750
exec_tmp_table1->free_tmp_table(session);
1751
if (exec_tmp_table2)
1752
exec_tmp_table2->free_tmp_table(session);
1754
delete_dynamic(&keyuse);
1759
Convert candidate subquery predicates to semi-joins
1762
JOIN::flatten_subqueries()
1765
Convert candidate subquery predicates to semi-joins.
1771
bool JOIN::flatten_subqueries()
1773
Item_in_subselect **in_subq;
1774
Item_in_subselect **in_subq_end;
1776
if (sj_subselects.elements() == 0)
1779
/* 1. Fix children subqueries */
1780
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
1781
in_subq != in_subq_end; in_subq++)
1783
JOIN *child_join= (*in_subq)->unit->first_select()->join;
1784
child_join->outer_tables = child_join->tables;
1785
if (child_join->flatten_subqueries())
1787
(*in_subq)->sj_convert_priority=
1788
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
1791
bool outer_join_disable_semi_join= false;
1793
* Temporary measure: disable semi-joins when they are together with outer
1796
* @see LP Bug #314911
1798
for (TableList *tbl= select_lex->leaf_tables; tbl; tbl=tbl->next_leaf)
1800
TableList *embedding= tbl->embedding;
1801
if (tbl->on_expr || (tbl->embedding && !(embedding->sj_on_expr &&
1802
!embedding->embedding)))
1804
in_subq= sj_subselects.front();
1805
outer_join_disable_semi_join= true;
1809
if (! outer_join_disable_semi_join)
1812
2. Pick which subqueries to convert:
1813
sort the subquery array
1814
- prefer correlated subqueries over uncorrelated;
1815
- prefer subqueries that have greater number of outer tables;
1817
sj_subselects.sort(subq_sj_candidate_cmp);
1818
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
1819
/* Replace all subqueries to be flattened with Item_int(1) */
1820
for (in_subq= sj_subselects.front();
1821
in_subq != in_subq_end &&
1822
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
1825
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
1829
for (in_subq= sj_subselects.front();
1830
in_subq != in_subq_end &&
1831
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
1834
if (convert_subq_to_sj(this, *in_subq))
1839
/* 3. Finalize those we didn't convert */
1840
for (; in_subq!= in_subq_end; in_subq++)
1842
JOIN *child_join= (*in_subq)->unit->first_select()->join;
1843
Item_subselect::trans_res res;
1844
(*in_subq)->changed= 0;
1845
(*in_subq)->fixed= 0;
1846
res= (*in_subq)->select_transformer(child_join);
1847
if (res == Item_subselect::RES_ERROR)
1850
(*in_subq)->changed= 1;
1851
(*in_subq)->fixed= 1;
1853
Item *substitute= (*in_subq)->substitution;
1854
bool do_fix_fields= !(*in_subq)->substitution->fixed;
1855
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
1858
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
1861
sj_subselects.clear();
1866
Setup for execution all subqueries of a query, for which the optimizer
1867
chose hash semi-join.
1869
@details Iterate over all subqueries of the query, and if they are under an
1870
IN predicate, and the optimizer chose to compute it via hash semi-join:
1871
- try to initialize all data structures needed for the materialized execution
1872
of the IN predicate,
1873
- if this fails, then perform the IN=>EXISTS transformation which was
1874
previously blocked during JOIN::prepare.
1876
This method is part of the "code generation" query processing phase.
1878
This phase must be called after substitute_for_best_equal_field() because
1879
that function may replace items with other items from a multiple equality,
1880
and we need to reference the correct items in the index access method of the
1883
@return Operation status
1884
@retval false success.
1885
@retval true error occurred.
1887
bool JOIN::setup_subquery_materialization()
1889
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1890
un= un->next_unit())
1892
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1894
Item_subselect *subquery_predicate= sl->master_unit()->item;
1895
if (subquery_predicate &&
1896
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1898
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1899
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1900
in_subs->setup_engine())
1909
Partially cleanup JOIN after it has executed: close index or rnd read
1910
(table cursors), free quick selects.
1912
This function is called in the end of execution of a JOIN, before the used
1913
tables are unlocked and closed.
1915
For a join that is resolved using a temporary table, the first sweep is
1916
performed against actual tables and an intermediate result is inserted
1917
into the temprorary table.
1918
The last sweep is performed against the temporary table. Therefore,
1919
the base tables and associated buffers used to fill the temporary table
1920
are no longer needed, and this function is called to free them.
1922
For a join that is performed without a temporary table, this function
1923
is called after all rows are sent, but before EOF packet is sent.
1925
For a simple SELECT with no subqueries this function performs a full
1926
cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1929
If a JOIN is executed for a subquery or if it has a subquery, we can't
1930
do the full cleanup and need to do a partial cleanup only.
1931
- If a JOIN is not the top level join, we must not unlock the tables
1932
because the outer select may not have been evaluated yet, and we
1933
can't unlock only selected tables of a query.
1934
- Additionally, if this JOIN corresponds to a correlated subquery, we
1935
should not free quick selects and join buffers because they will be
1936
needed for the next execution of the correlated subquery.
1937
- However, if this is a JOIN for a [sub]select, which is not
1938
a correlated subquery itself, but has subqueries, we can free it
1939
fully and also free JOINs of all its subqueries. The exception
1940
is a subquery in SELECT list, e.g: @n
1941
SELECT a, (select cmax(b) from t1) group by c @n
1942
This subquery will not be evaluated at first sweep and its value will
1943
not be inserted into the temporary table. Instead, it's evaluated
1944
when selecting from the temporary table. Therefore, it can't be freed
1945
here even though it's not correlated.
1948
Unlock tables even if the join isn't top level select in the tree
1950
void JOIN::join_free()
1952
Select_Lex_Unit *tmp_unit;
1955
Optimization: if not EXPLAIN and we are done with the JOIN,
1958
bool full= (!select_lex->uncacheable && !session->lex->describe);
1959
bool can_unlock= full;
1963
for (tmp_unit= select_lex->first_inner_unit();
1965
tmp_unit= tmp_unit->next_unit())
1966
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1968
Item_subselect *subselect= sl->master_unit()->item;
1969
bool full_local= full && (!subselect || subselect->is_evaluated());
1971
If this join is evaluated, we can fully clean it up and clean up all
1972
its underlying joins even if they are correlated -- they will not be
1973
used any more anyway.
1974
If this join is not yet evaluated, we still must clean it up to
1975
close its table cursors -- it may never get evaluated, as in case of
1976
... HAVING false OR a IN (SELECT ...))
1977
but all table cursors must be closed before the unlock.
1979
sl->cleanup_all_joins(full_local);
1980
/* Can't unlock if at least one JOIN is still needed */
1981
can_unlock= can_unlock && full_local;
1985
We are not using tables anymore
1986
Unlock all tables. We may be in an INSERT .... SELECT statement.
1988
if (can_unlock && lock && session->lock &&
1989
!(select_options & SELECT_NO_UNLOCK) &&
1990
!select_lex->subquery_in_having &&
1991
(select_lex == (session->lex->unit.fake_select_lex ?
1992
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1995
TODO: unlock tables even if the join isn't top level select in the
1998
mysql_unlock_read_tables(session, lock); // Don't free join->lock
2007
Free resources of given join.
2009
@param fill true if we should free all resources, call with full==1
2010
should be last, before it this function can be called with
2014
With subquery this function definitely will be called several times,
2015
but even for simple query it can be called several times.
2017
void JOIN::cleanup(bool full)
2023
Only a sorted table may be cached. This sorted table is always the
2024
first non const table in join->table
2026
if (tables > const_tables) // Test for not-const tables
2028
free_io_cache(table[const_tables]);
2029
filesort_free_buffers(table[const_tables],full);
2034
for (tab= join_tab, end= tab+tables; tab != end; tab++)
2040
for (tab= join_tab, end= tab+tables; tab != end; tab++)
2043
tab->table->file->ha_index_or_rnd_end();
2046
cleanup_sj_tmp_tables(this);//
2049
We are not using tables anymore
2050
Unlock all tables. We may be in an INSERT .... SELECT statement.
2055
tmp_table_param.copy_field= 0;
2056
group_fields.delete_elements();
2058
We can't call delete_elements() on copy_funcs as this will cause
2059
problems in free_elements() as some of the elements are then deleted.
2061
tmp_table_param.copy_funcs.empty();
2063
If we have tmp_join and 'this' JOIN is not tmp_join and
2064
tmp_table_param.copy_field's of them are equal then we have to remove
2065
pointer to tmp_table_param.copy_field from tmp_join, because it qill
2066
be removed in tmp_table_param.cleanup().
2070
tmp_join->tmp_table_param.copy_field ==
2071
tmp_table_param.copy_field)
2073
tmp_join->tmp_table_param.copy_field=
2074
tmp_join->tmp_table_param.save_copy_field= 0;
2076
tmp_table_param.cleanup();
2082
used only in JOIN::clear
2084
static void clear_tables(JOIN *join)
2087
must clear only the non-const tables, as const tables
2088
are not re-calculated.
2090
for (uint32_t i= join->const_tables; i < join->tables; i++)
2091
join->table[i]->mark_as_null_row(); // All fields are NULL
2095
Make an array of pointers to sum_functions to speed up
2096
sum_func calculation.
2103
bool JOIN::alloc_func_list()
2105
uint32_t func_count, group_parts;
2107
func_count= tmp_table_param.sum_func_count;
2109
If we are using rollup, we need a copy of the summary functions for
2112
if (rollup.state != ROLLUP::STATE_NONE)
2113
func_count*= (send_group_parts+1);
2115
group_parts= send_group_parts;
2117
If distinct, reserve memory for possible
2118
disctinct->group_by optimization
2120
if (select_distinct)
2122
group_parts+= fields_list.elements;
2124
If the order_st clause is specified then it's possible that
2125
it also will be optimized, so reserve space for it too
2130
for (ord= order; ord; ord= ord->next)
2135
/* This must use calloc() as rollup_make_fields depends on this */
2136
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
2137
sizeof(Item_sum***) * (group_parts+1));
2138
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
2139
return(sum_funcs == 0);
2143
Initialize 'sum_funcs' array with all Item_sum objects.
2145
@param field_list All items
2146
@param send_fields Items in select list
2147
@param before_group_by Set to 1 if this is called before GROUP BY handling
2148
@param recompute Set to true if sum_funcs must be recomputed
2155
bool JOIN::make_sum_func_list(List<Item> &field_list,
2156
List<Item> &send_fields,
2157
bool before_group_by,
2160
List_iterator_fast<Item> it(field_list);
2164
if (*sum_funcs && !recompute)
2165
return(false); /* We have already initialized sum_funcs. */
2170
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2171
(!((Item_sum*) item)->depended_from() ||
2172
((Item_sum *)item)->depended_from() == select_lex))
2173
*func++= (Item_sum*) item;
2175
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2177
rollup.state= ROLLUP::STATE_READY;
2178
if (rollup_make_fields(field_list, send_fields, &func))
2179
return(true); // Should never happen
2181
else if (rollup.state == ROLLUP::STATE_NONE)
2183
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2184
sum_funcs_end[i]= func;
2186
else if (rollup.state == ROLLUP::STATE_READY)
2187
return(false); // Don't put end marker
2188
*func=0; // End marker
2192
/** Allocate memory needed for other rollup functions. */
2193
bool JOIN::rollup_init()
2198
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2199
rollup.state= ROLLUP::STATE_INITED;
2202
Create pointers to the different sum function groups
2203
These are updated by rollup_make_fields()
2205
tmp_table_param.group_parts= send_group_parts;
2207
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2209
sizeof(List<Item>) +
2210
ref_pointer_array_size)
2211
* send_group_parts )))
2214
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2215
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2216
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2219
Prepare space for field list for the different levels
2220
These will be filled up in rollup_make_fields()
2222
for (i= 0 ; i < send_group_parts ; i++)
2224
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2225
List<Item> *rollup_fields= &rollup.fields[i];
2226
rollup_fields->empty();
2227
rollup.ref_pointer_arrays[i]= ref_array;
2228
ref_array+= all_fields.elements;
2230
for (i= 0 ; i < send_group_parts; i++)
2232
for (j=0 ; j < fields_list.elements ; j++)
2233
rollup.fields[i].push_back(rollup.null_items[i]);
2235
List_iterator<Item> it(all_fields);
2237
while ((item= it++))
2239
order_st *group_tmp;
2240
bool found_in_group= 0;
2242
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2244
if (*group_tmp->item == item)
2246
item->maybe_null= 1;
2248
if (item->const_item())
2251
For ROLLUP queries each constant item referenced in GROUP BY list
2252
is wrapped up into an Item_func object yielding the same value
2253
as the constant item. The objects of the wrapper class are never
2254
considered as constant items and besides they inherit all
2255
properties of the Item_result_field class.
2256
This wrapping allows us to ensure writing constant items
2257
into temporary tables whenever the result of the ROLLUP
2258
operation has to be written into a temporary table, e.g. when
2259
ROLLUP is used together with DISTINCT in the SELECT list.
2260
Usually when creating temporary tables for a intermidiate
2261
result we do not include fields for constant expressions.
2263
Item* new_item= new Item_func_rollup_const(item);
2266
new_item->fix_fields(session, (Item **) 0);
2267
session->change_item_tree(it.ref(), new_item);
2268
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2270
if (*tmp->item == item)
2271
session->change_item_tree(tmp->item, new_item);
2276
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2278
bool changed= false;
2279
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2282
We have to prevent creation of a field in a temporary table for
2283
an expression that contains GROUP BY attributes.
2284
Marking the expression item as 'with_sum_func' will ensure this.
2287
item->with_sum_func= 1;
2294
Fill up rollup structures with pointers to fields to use.
2296
Creates copies of item_sum items for each sum level.
2298
@param fields_arg List of all fields (hidden and real ones)
2299
@param sel_fields Pointer to selected fields
2300
@param func Store here a pointer to all fields
2304
In this case func is pointing to next not used element.
2308
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2310
List_iterator_fast<Item> it(fields_arg);
2311
Item *first_field= sel_fields.head();
2315
Create field lists for the different levels
2317
The idea here is to have a separate field list for each rollup level to
2318
avoid all runtime checks of which columns should be NULL.
2320
The list is stored in reverse order to get sum function in such an order
2321
in func that it makes it easy to reset them with init_sum_functions()
2323
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2325
rollup.fields[0] will contain list where a,b,c is NULL
2326
rollup.fields[1] will contain list where b,c is NULL
2328
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2330
sum_funcs_end[0] points to all sum functions
2331
sum_funcs_end[1] points to all sum functions, except grand totals
2335
for (level=0 ; level < send_group_parts ; level++)
2338
uint32_t pos= send_group_parts - level -1;
2339
bool real_fields= 0;
2341
List_iterator<Item> new_it(rollup.fields[pos]);
2342
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2343
order_st *start_group;
2345
/* Point to first hidden field */
2346
Item **ref_array= ref_array_start + fields_arg.elements-1;
2348
/* Remember where the sum functions ends for the previous level */
2349
sum_funcs_end[pos+1]= *func;
2351
/* Find the start of the group for this level */
2352
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2356
while ((item= it++))
2358
if (item == first_field)
2360
real_fields= 1; // End of hidden fields
2361
ref_array= ref_array_start;
2364
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2365
(!((Item_sum*) item)->depended_from() ||
2366
((Item_sum *)item)->depended_from() == select_lex))
2370
This is a top level summary function that must be replaced with
2371
a sum function that is reset for this level.
2373
NOTE: This code creates an object which is not that nice in a
2374
sub select. Fortunately it's not common to have rollup in
2377
item= item->copy_or_same(session);
2378
((Item_sum*) item)->make_unique();
2379
*(*func)= (Item_sum*) item;
2384
/* Check if this is something that is part of this group by */
2385
order_st *group_tmp;
2386
for (group_tmp= start_group, i= pos ;
2387
group_tmp ; group_tmp= group_tmp->next, i++)
2389
if (*group_tmp->item == item)
2392
This is an element that is used by the GROUP BY and should be
2393
set to NULL in this level
2395
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2398
item->maybe_null= 1; // Value will be null sometimes
2399
null_item->result_field= item->get_tmp_table_field();
2408
(void) new_it++; // Point to next item
2409
new_it.replace(item); // Replace previous
2416
sum_funcs_end[0]= *func; // Point to last function
2421
Send all rollup levels higher than the current one to the client.
2425
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2428
@param idx Level we are on:
2429
- 0 = Total sum level
2430
- 1 = First group changed (a)
2431
- 2 = Second group changed (a,b)
2436
1 If send_data_failed()
2438
int JOIN::rollup_send_data(uint32_t idx)
2441
for (i= send_group_parts ; i-- > idx ; )
2443
/* Get reference pointers to sum functions in place */
2444
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2445
ref_pointer_array_size);
2446
if ((!having || having->val_int()))
2448
if (send_records < unit->select_limit_cnt && do_send_rows &&
2449
result->send_data(rollup.fields[i]))
2454
/* Restore ref_pointer_array */
2455
set_items_ref_array(current_ref_pointer_array);
2460
Write all rollup levels higher than the current one to a temp table.
2464
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2467
@param idx Level we are on:
2468
- 0 = Total sum level
2469
- 1 = First group changed (a)
2470
- 2 = Second group changed (a,b)
2471
@param table reference to temp table
2476
1 if write_data_failed()
2478
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2481
for (i= send_group_parts ; i-- > idx ; )
2483
/* Get reference pointers to sum functions in place */
2484
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2485
ref_pointer_array_size);
2486
if ((!having || having->val_int()))
2490
List_iterator_fast<Item> it(rollup.fields[i]);
2491
while ((item= it++))
2493
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2494
item->save_in_result_field(1);
2496
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2497
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
2499
if (create_myisam_from_heap(session, table_arg,
2500
tmp_table_param.start_recinfo,
2501
&tmp_table_param.recinfo,
2507
/* Restore ref_pointer_array */
2508
set_items_ref_array(current_ref_pointer_array);
2513
clear results if there are not rows found for group
2514
(end_send_group/end_write_group)
2519
copy_fields(&tmp_table_param);
2523
Item_sum *func, **func_ptr= sum_funcs;
2524
while ((func= *(func_ptr++)))
2530
change select_result object of JOIN.
2532
@param res new select_result object
2539
bool JOIN::change_result(select_result *res)
2542
if (result->prepare(fields_list, select_lex->master_unit()))
2550
Give error if we some tables are done with a full join.
2552
This is used by multi_table_update and multi_table_delete when running
2555
@param join Join condition
2560
1 Error (full join used)
2562
bool error_if_full_join(JOIN *join)
2564
for (JOIN_TAB *tab= join->join_tab, *end= join->join_tab+join->tables; tab < end; tab++)
2566
if (tab->type == JT_ALL && (!tab->select || !tab->select->quick))
2568
my_message(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE,
2569
ER(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE), MYF(0));
2579
Process one record of the nested loop join.
2583
This function will evaluate parts of WHERE/ON clauses that are
2584
applicable to the partial record on hand and in case of success
2585
submit this record to the next level of the nested loop.
2587
enum_nested_loop_state evaluate_join_record(JOIN *join, JOIN_TAB *join_tab, int error)
2589
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2590
ha_rows found_records= join->found_records;
2591
COND *select_cond= join_tab->select_cond;
2593
if (error > 0 || (join->session->is_error())) // Fatal error
2594
return NESTED_LOOP_ERROR;
2596
return NESTED_LOOP_NO_MORE_ROWS;
2597
if (join->session->killed) // Aborted by user
2599
join->session->send_kill_message();
2600
return NESTED_LOOP_KILLED; /* purecov: inspected */
2602
if (!select_cond || select_cond->val_int())
2605
There is no select condition or the attached pushed down
2606
condition is true => a match is found.
2609
while (join_tab->first_unmatched && found)
2612
The while condition is always false if join_tab is not
2613
the last inner join table of an outer join operation.
2615
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
2617
Mark that a match for current outer table is found.
2618
This activates push down conditional predicates attached
2619
to the all inner tables of the outer join.
2621
first_unmatched->found= 1;
2622
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
2624
if (tab->table->reginfo.not_exists_optimize)
2625
return NESTED_LOOP_NO_MORE_ROWS;
2626
/* Check all predicates that has just been activated. */
2628
Actually all predicates non-guarded by first_unmatched->found
2629
will be re-evaluated again. It could be fixed, but, probably,
2630
it's not worth doing now.
2632
if (tab->select_cond && !tab->select_cond->val_int())
2634
/* The condition attached to table tab is false */
2635
if (tab == join_tab)
2640
Set a return point if rejected predicate is attached
2641
not to the last table of the current nest level.
2643
join->return_tab= tab;
2644
return NESTED_LOOP_OK;
2649
Check whether join_tab is not the last inner table
2650
for another embedding outer join.
2652
if ((first_unmatched= first_unmatched->first_upper) &&
2653
first_unmatched->last_inner != join_tab)
2655
join_tab->first_unmatched= first_unmatched;
2658
JOIN_TAB *return_tab= join->return_tab;
2659
join_tab->found_match= true;
2660
if (join_tab->check_weed_out_table)
2662
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
2664
return NESTED_LOOP_ERROR;
2666
return NESTED_LOOP_OK;
2668
else if (join_tab->do_firstmatch)
2671
We should return to the join_tab->do_firstmatch after we have
2672
enumerated all the suffixes for current prefix row combination
2674
return_tab= join_tab->do_firstmatch;
2678
It was not just a return to lower loop level when one
2679
of the newly activated predicates is evaluated as false
2680
(See above join->return_tab= tab).
2682
join->examined_rows++;
2683
join->session->row_count++;
2687
enum enum_nested_loop_state rc;
2688
/* A match from join_tab is found for the current partial join. */
2689
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2690
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2692
if (return_tab < join->return_tab)
2693
join->return_tab= return_tab;
2695
if (join->return_tab < join_tab)
2696
return NESTED_LOOP_OK;
2698
Test if this was a SELECT DISTINCT query on a table that
2699
was not in the field list; In this case we can abort if
2700
we found a row, as no new rows can be added to the result.
2702
if (not_used_in_distinct && found_records != join->found_records)
2703
return NESTED_LOOP_NO_MORE_ROWS;
2706
join_tab->read_record.file->unlock_row();
2711
The condition pushed down to the table join_tab rejects all rows
2712
with the beginning coinciding with the current partial join.
2714
join->examined_rows++;
2715
join->session->row_count++;
2716
join_tab->read_record.file->unlock_row();
2718
return NESTED_LOOP_OK;
2723
Construct a NULL complimented partial join record and feed it to the next
2724
level of the nested loop. This function is used in case we have
2725
an OUTER join and no matching record was found.
2727
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
2730
The table join_tab is the first inner table of a outer join operation
2731
and no matches has been found for the current outer row.
2733
JOIN_TAB *last_inner_tab= join_tab->last_inner;
2734
/* Cache variables for faster loop */
2736
for ( ; join_tab <= last_inner_tab ; join_tab++)
2738
/* Change the the values of guard predicate variables. */
2740
join_tab->not_null_compl= 0;
2741
/* The outer row is complemented by nulls for each inner tables */
2742
join_tab->table->restoreRecordAsDefault(); // Make empty record
2743
join_tab->table->mark_as_null_row(); // For group by without error
2744
select_cond= join_tab->select_cond;
2745
/* Check all attached conditions for inner table rows. */
2746
if (select_cond && !select_cond->val_int())
2747
return NESTED_LOOP_OK;
2751
The row complemented by nulls might be the first row
2752
of embedding outer joins.
2753
If so, perform the same actions as in the code
2754
for the first regular outer join row above.
2758
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
2759
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2761
join_tab->first_unmatched= first_unmatched;
2762
if (! first_unmatched)
2764
first_unmatched->found= 1;
2765
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
2767
if (tab->select_cond && !tab->select_cond->val_int())
2769
join->return_tab= tab;
2770
return NESTED_LOOP_OK;
2775
The row complemented by nulls satisfies all conditions
2776
attached to inner tables.
2777
Send the row complemented by nulls to be joined with the
2780
return (*join_tab->next_select)(join, join_tab+1, 0);
2783
enum_nested_loop_state flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last)
2785
enum_nested_loop_state rc= NESTED_LOOP_OK;
2789
join_tab->table->null_row= 0;
2790
if (!join_tab->cache.records)
2791
return NESTED_LOOP_OK; /* Nothing to do */
2793
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
2794
if (join_tab->use_quick == 2)
2796
if (join_tab->select->quick)
2797
{ /* Used quick select last. reset it */
2798
delete join_tab->select->quick;
2799
join_tab->select->quick=0;
2802
/* read through all records */
2803
if ((error=join_init_read_record(join_tab)))
2805
reset_cache_write(&join_tab->cache);
2806
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2809
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
2811
tmp->status=tmp->table->status;
2812
tmp->table->status=0;
2815
info= &join_tab->read_record;
2818
if (join->session->killed)
2820
join->session->send_kill_message();
2821
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
2823
SQL_SELECT *select=join_tab->select;
2824
if (rc == NESTED_LOOP_OK &&
2825
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2828
reset_cache_read(&join_tab->cache);
2829
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2831
read_cached_record(join_tab);
2832
if (!select || !select->skip_record())
2835
if (!join_tab->check_weed_out_table ||
2836
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
2838
rc= (join_tab->next_select)(join,join_tab+1,0);
2839
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2841
reset_cache_write(&join_tab->cache);
2846
return NESTED_LOOP_ERROR;
2850
} while (!(error=info->read_record(info)));
2853
read_cached_record(join_tab); // Restore current record
2854
reset_cache_write(&join_tab->cache);
2855
if (error > 0) // Fatal error
2856
return NESTED_LOOP_ERROR; /* purecov: inspected */
2857
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2858
tmp2->table->status=tmp2->status;
2859
return NESTED_LOOP_OK;
2862
/*****************************************************************************
2864
Functions that end one nested loop iteration. Different functions
2865
are used to support GROUP BY clause and to redirect records
2866
to a table (e.g. in case of SELECT into a temporary table) or to the
2870
NESTED_LOOP_OK - the record has been successfully handled
2871
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2873
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2875
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2876
additionally, the nested loop produced the
2877
number of rows specified in the LIMIT clause
2879
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2880
additionally, there is a cursor and the nested
2881
loop algorithm produced the number of rows
2882
that is specified for current cursor fetch
2884
All return values except NESTED_LOOP_OK abort the nested loop.
2885
*****************************************************************************/
2886
enum_nested_loop_state end_send(JOIN *join, JOIN_TAB *, bool end_of_records)
2888
if (! end_of_records)
2891
if (join->having && join->having->val_int() == 0)
2892
return NESTED_LOOP_OK; // Didn't match having
2894
if (join->do_send_rows)
2895
error=join->result->send_data(*join->fields);
2897
return NESTED_LOOP_ERROR; /* purecov: inspected */
2898
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2900
if (join->select_options & OPTION_FOUND_ROWS)
2902
JOIN_TAB *jt=join->join_tab;
2903
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2904
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2905
!(jt->select && jt->select->quick) &&
2906
(jt->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
2909
/* Join over all rows in table; Return number of found rows */
2910
Table *table= jt->table;
2912
join->select_options^= OPTION_FOUND_ROWS;
2913
if (table->sort.record_pointers ||
2914
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2916
/* Using filesort */
2917
join->send_records= table->sort.found_records;
2921
table->file->info(HA_STATUS_VARIABLE);
2922
join->send_records= table->file->stats.records;
2927
join->do_send_rows= 0;
2928
if (join->unit->fake_select_lex)
2929
join->unit->fake_select_lex->select_limit= 0;
2930
return NESTED_LOOP_OK;
2933
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2935
else if (join->send_records >= join->fetch_limit)
2938
There is a server side cursor and all rows for
2939
this fetch request are sent.
2941
return NESTED_LOOP_CURSOR_LIMIT;
2945
return NESTED_LOOP_OK;
2948
enum_nested_loop_state end_write(JOIN *join, JOIN_TAB *, bool end_of_records)
2950
Table *table= join->tmp_table;
2952
if (join->session->killed) // Aborted by user
2954
join->session->send_kill_message();
2955
return NESTED_LOOP_KILLED; /* purecov: inspected */
2957
if (!end_of_records)
2959
copy_fields(&join->tmp_table_param);
2960
copy_funcs(join->tmp_table_param.items_to_copy);
2961
if (!join->having || join->having->val_int())
2964
join->found_records++;
2965
if ((error=table->file->ha_write_row(table->record[0])))
2967
if (!table->file->is_fatal_error(error, HA_CHECK_DUP))
2969
if (create_myisam_from_heap(join->session, table,
2970
join->tmp_table_param.start_recinfo,
2971
&join->tmp_table_param.recinfo,
2973
return NESTED_LOOP_ERROR; // Not a table_is_full error
2974
table->s->uniques= 0; // To ensure rows are the same
2976
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2978
if (!(join->select_options & OPTION_FOUND_ROWS))
2979
return NESTED_LOOP_QUERY_LIMIT;
2980
join->do_send_rows= 0;
2981
join->unit->select_limit_cnt= HA_POS_ERROR;
2982
return NESTED_LOOP_OK;
2987
return NESTED_LOOP_OK;
2990
/** Group by searching after group record and updating it if possible. */
2991
enum_nested_loop_state end_update(JOIN *join, JOIN_TAB *, bool end_of_records)
2993
Table *table= join->tmp_table;
2998
return NESTED_LOOP_OK;
2999
if (join->session->killed) // Aborted by user
3001
join->session->send_kill_message();
3002
return NESTED_LOOP_KILLED; /* purecov: inspected */
3005
join->found_records++;
3006
copy_fields(&join->tmp_table_param); // Groups are copied twice.
3007
/* Make a key of group index */
3008
for (group=table->group ; group ; group=group->next)
3010
Item *item= *group->item;
3011
item->save_org_in_field(group->field);
3012
/* Store in the used key if the field was 0 */
3013
if (item->maybe_null)
3014
group->buff[-1]= (char) group->field->is_null();
3016
if (!table->file->index_read_map(table->record[1],
3017
join->tmp_table_param.group_buff,
3020
{ /* Update old record */
3021
table->restoreRecord();
3022
update_tmptable_sum_func(join->sum_funcs,table);
3023
if ((error= table->file->ha_update_row(table->record[1],
3026
table->file->print_error(error,MYF(0)); /* purecov: inspected */
3027
return NESTED_LOOP_ERROR; /* purecov: inspected */
3029
return NESTED_LOOP_OK;
3033
Copy null bits from group key to table
3034
We can't copy all data as the key may have different format
3035
as the row data (for example as with VARCHAR keys)
3037
KEY_PART_INFO *key_part;
3038
for (group=table->group,key_part=table->key_info[0].key_part;
3040
group=group->next,key_part++)
3042
if (key_part->null_bit)
3043
memcpy(table->record[0]+key_part->offset, group->buff, 1);
3045
init_tmptable_sum_functions(join->sum_funcs);
3046
copy_funcs(join->tmp_table_param.items_to_copy);
3047
if ((error=table->file->ha_write_row(table->record[0])))
3049
if (create_myisam_from_heap(join->session, table,
3050
join->tmp_table_param.start_recinfo,
3051
&join->tmp_table_param.recinfo,
3053
return NESTED_LOOP_ERROR; // Not a table_is_full error
3054
/* Change method to update rows */
3055
table->file->ha_index_init(0, 0);
3056
join->join_tab[join->tables-1].next_select= end_unique_update;
3058
join->send_records++;
3059
return NESTED_LOOP_OK;
3062
/** Like end_update, but this is done with unique constraints instead of keys. */
3063
enum_nested_loop_state end_unique_update(JOIN *join, JOIN_TAB *, bool end_of_records)
3065
Table *table= join->tmp_table;
3069
return NESTED_LOOP_OK;
3070
if (join->session->killed) // Aborted by user
3072
join->session->send_kill_message();
3073
return NESTED_LOOP_KILLED; /* purecov: inspected */
3076
init_tmptable_sum_functions(join->sum_funcs);
3077
copy_fields(&join->tmp_table_param); // Groups are copied twice.
3078
copy_funcs(join->tmp_table_param.items_to_copy);
3080
if (!(error= table->file->ha_write_row(table->record[0])))
3081
join->send_records++; // New group
3084
if ((int) table->file->get_dup_key(error) < 0)
3086
table->file->print_error(error,MYF(0)); /* purecov: inspected */
3087
return NESTED_LOOP_ERROR; /* purecov: inspected */
3089
if (table->file->rnd_pos(table->record[1],table->file->dup_ref))
3091
table->file->print_error(error,MYF(0)); /* purecov: inspected */
3092
return NESTED_LOOP_ERROR; /* purecov: inspected */
3094
table->restoreRecord();
3095
update_tmptable_sum_func(join->sum_funcs,table);
3096
if ((error= table->file->ha_update_row(table->record[1],
3099
table->file->print_error(error,MYF(0)); /* purecov: inspected */
3100
return NESTED_LOOP_ERROR; /* purecov: inspected */
3103
return NESTED_LOOP_OK;
3107
allocate group fields or take prepared (cached).
3109
@param main_join join of current select
3110
@param curr_join current join (join of current select or temporary copy
3118
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
3120
if (main_join->group_fields_cache.elements)
3122
curr_join->group_fields= main_join->group_fields_cache;
3123
curr_join->sort_and_group= 1;
3127
if (alloc_group_fields(curr_join, curr_join->group_list))
3129
main_join->group_fields_cache= curr_join->group_fields;
3135
calc how big buffer we need for comparing group entries.
3137
static void calc_group_buffer(JOIN *join,order_st *group)
3139
uint32_t key_length=0, parts=0, null_parts=0;
3143
for (; group ; group=group->next)
3145
Item *group_item= *group->item;
3146
Field *field= group_item->get_tmp_table_field();
3149
enum_field_types type;
3150
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
3151
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
3152
else if (type == DRIZZLE_TYPE_VARCHAR)
3153
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3155
key_length+= field->pack_length();
3159
switch (group_item->result_type()) {
3161
key_length+= sizeof(double);
3164
key_length+= sizeof(int64_t);
3166
case DECIMAL_RESULT:
3167
key_length+= my_decimal_get_binary_size(group_item->max_length -
3168
(group_item->decimals ? 1 : 0),
3169
group_item->decimals);
3173
enum enum_field_types type= group_item->field_type();
3175
As items represented as DATE/TIME fields in the group buffer
3176
have STRING_RESULT result type, we increase the length
3177
by 8 as maximum pack length of such fields.
3179
if (type == DRIZZLE_TYPE_DATE ||
3180
type == DRIZZLE_TYPE_DATETIME ||
3181
type == DRIZZLE_TYPE_TIMESTAMP)
3188
Group strings are taken as varstrings and require an length field.
3189
A field is not yet created by create_tmp_field()
3190
and the sizes should match up.
3192
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3197
/* This case should never be choosen */
3199
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3203
if (group_item->maybe_null)
3206
join->tmp_table_param.group_length=key_length+null_parts;
3207
join->tmp_table_param.group_parts=parts;
3208
join->tmp_table_param.group_null_parts=null_parts;
3212
Get a list of buffers for saveing last group.
3214
Groups are saved in reverse order for easyer check loop.
3216
static bool alloc_group_fields(JOIN *join,order_st *group)
3220
for (; group ; group=group->next)
3222
Cached_item *tmp=new_Cached_item(join->session, *group->item, false);
3223
if (!tmp || join->group_fields.push_front(tmp))
3227
join->sort_and_group=1; /* Mark for do_select */
3233
- TODO: this function is here only temporarily until 'greedy_search' is
3234
tested and accepted.
3240
static bool find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count, double read_time)
3242
Session *session= join->session;
3243
if (session->killed)
3247
read_time+=record_count/(double) TIME_FOR_COMPARE;
3248
if (join->sort_by_table &&
3249
join->sort_by_table !=
3250
join->positions[join->const_tables].table->table)
3251
read_time+=record_count; // We have to make a temp table
3252
if (read_time < join->best_read)
3254
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
3255
join->best_read= read_time - 0.001;
3259
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
3260
return(false); /* Found better before */
3263
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
3264
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
3266
table_map real_table_bit=s->table->map;
3267
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
3268
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
3270
double records, best;
3271
advance_sj_state(rest_tables, s);
3272
best_access_path(join, s, session, rest_tables, idx, record_count,
3274
records= join->positions[idx].records_read;
3275
best= join->positions[idx].read_time;
3277
Go to the next level only if there hasn't been a better key on
3278
this level! This will cut down the search for a lot simple cases!
3280
double current_record_count=record_count*records;
3281
double current_read_time=read_time+best;
3282
if (best_record_count > current_record_count ||
3283
best_read_time > current_read_time ||
3284
(idx == join->const_tables && s->table == join->sort_by_table))
3286
if (best_record_count >= current_record_count &&
3287
best_read_time >= current_read_time &&
3288
(!(s->key_dependent & rest_tables) || records < 2.0))
3290
best_record_count=current_record_count;
3291
best_read_time=current_read_time;
3293
std::swap(join->best_ref[idx], *pos);
3294
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
3295
current_record_count,current_read_time))
3297
std::swap(join->best_ref[idx], *pos);
3299
restore_prev_nj_state(s);
3300
restore_prev_sj_state(rest_tables, s);
3301
if (join->select_options & SELECT_STRAIGHT_JOIN)
3302
break; // Don't test all combinations
3308
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3311
JOIN_TAB **pos,**end;
3312
Session *session=join->session;
3314
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3318
JOIN_TAB *join_tab= *pos;
3319
if (!join_tab->used_fieldlength) /* Not calced yet */
3320
calc_used_field_length(session, join_tab);
3321
length+=join_tab->used_fieldlength;
3327
Get the number of different row combinations for subset of partial join
3331
join The join structure
3332
idx Number of tables in the partial join order (i.e. the
3333
partial join order is in join->positions[0..idx-1])
3334
found_ref Bitmap of tables for which we need to find # of distinct
3338
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3339
tables within that join order (specified in found_ref), find out how many
3340
distinct row combinations of subset tables will be in the result of the
3343
This is used as follows: Suppose we have a table accessed with a ref-based
3344
method. The ref access depends on current rows of tables in found_ref.
3345
We want to count # of different ref accesses. We assume two ref accesses
3346
will be different if at least one of access parameters is different.
3347
Example: consider a query
3349
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3352
t1, ref access on t1.key=c1
3353
t2, ref access on t2.key=c2
3354
t3, ref access on t3.key=t1.field
3356
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3357
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3358
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3359
n_distinct_ref_scans = #records_read(t1)
3361
The reason for having this function (at least the latest version of it)
3362
is that we need to account for buffering in join execution.
3364
An edge-case example: if we have a non-first table in join accessed via
3365
ref(const) or ref(param) where there is a small number of different
3366
values of param, then the access will likely hit the disk cache and will
3367
not require any disk seeks.
3369
The proper solution would be to assume an LRU disk cache of some size,
3370
calculate probability of cache hits, etc. For now we just count
3371
identical ref accesses as one.
3374
Expected number of row combinations
3376
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3379
POSITION *pos_end= join->positions - 1;
3380
for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--)
3382
if (pos->table->table->map & found_ref)
3384
found_ref|= pos->ref_depend_map;
3386
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3387
with no matching row we will get position[t2].records_read==0.
3388
Actually the size of output is one null-complemented row, therefore
3389
we will use value of 1 whenever we get records_read==0.
3392
- the above case can't occur if inner part of outer join has more
3393
than one table: table with no matches will not be marked as const.
3395
- Ideally we should add 1 to records_read for every possible null-
3396
complemented row. We're not doing it because: 1. it will require
3397
non-trivial code and add overhead. 2. The value of records_read
3398
is an inprecise estimate and adding 1 (or, in the worst case,
3399
#max_nested_outer_joins=64-1) will not make it any more precise.
3401
if (pos->records_read > DBL_EPSILON)
3402
found*= pos->records_read;
3409
Set up join struct according to best position.
3411
static bool get_best_combination(JOIN *join)
3414
table_map used_tables;
3415
JOIN_TAB *join_tab,*j;
3417
uint32_t table_count;
3418
Session *session=join->session;
3420
table_count=join->tables;
3421
if (!(join->join_tab=join_tab=
3422
(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))
3427
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3428
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3431
*j= *join->best_positions[tablenr].table;
3432
form=join->table[tablenr]=j->table;
3433
used_tables|= form->map;
3434
form->reginfo.join_tab=j;
3435
if (!*j->on_expr_ref)
3436
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
3437
if (j->type == JT_CONST)
3438
continue; // Handled in make_join_stat..
3443
if (j->type == JT_SYSTEM)
3445
if (j->keys.none() || !(keyuse= join->best_positions[tablenr].key))
3448
if (tablenr != join->const_tables)
3451
else if (create_ref_for_key(join, j, keyuse, used_tables))
3452
return(true); // Something went wrong
3455
for (i=0 ; i < table_count ; i++)
3456
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3457
update_depend_map(join);
3461
/** Save const tables first as used tables. */
3462
static void set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
3464
join->positions[idx].table= table;
3465
join->positions[idx].key=key;
3466
join->positions[idx].records_read=1.0; /* This is a const table */
3467
join->positions[idx].ref_depend_map= 0;
3469
/* Move the const table as down as possible in best_ref */
3470
JOIN_TAB **pos=join->best_ref+idx+1;
3471
JOIN_TAB *next=join->best_ref[idx];
3472
for (;next != table ; pos++)
3474
JOIN_TAB *tmp=pos[0];
3478
join->best_ref[idx]=table;
3482
Selects and invokes a search strategy for an optimal query plan.
3484
The function checks user-configurable parameters that control the search
3485
strategy for an optimal plan, selects the search method and then invokes
3486
it. Each specific optimization procedure stores the final optimal plan in
3487
the array 'join->best_positions', and the cost of the plan in
3490
@param join pointer to the structure providing all context info for
3492
@param join_tables set of the tables in the query
3495
'MAX_TABLES+2' denotes the old implementation of find_best before
3496
the greedy version. Will be removed when greedy_search is approved.
3503
static bool choose_plan(JOIN *join, table_map join_tables)
3505
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3506
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3507
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3509
join->cur_embedding_map= 0;
3510
reset_nj_counters(join->join_list);
3512
if (SELECT_STRAIGHT_JOIN option is set)
3513
reorder tables so dependent tables come after tables they depend
3514
on, otherwise keep tables in the order they were specified in the query
3516
Apply heuristic: pre-sort all access plans with respect to the number of
3519
my_qsort(join->best_ref + join->const_tables,
3520
join->tables - join->const_tables, sizeof(JOIN_TAB*),
3521
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3522
join->cur_emb_sj_nests= 0;
3525
optimize_straight_join(join, join_tables);
3529
if (search_depth == MAX_TABLES+2)
3531
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
3532
the greedy version. Will be removed when greedy_search is approved.
3534
join->best_read= DBL_MAX;
3535
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
3540
if (search_depth == 0)
3541
/* Automatically determine a reasonable value for 'search_depth' */
3542
search_depth= determine_search_depth(join);
3543
if (greedy_search(join, join_tables, search_depth, prune_level))
3549
Store the cost of this query into a user variable
3550
Don't update last_query_cost for statements that are not "flat joins" :
3551
i.e. they have subqueries, unions or call stored procedures.
3552
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3554
if (join->session->lex->is_single_level_stmt())
3555
join->session->status_var.last_query_cost= join->best_read;
3560
Find the best access path for an extension of a partial execution
3561
plan and add this path to the plan.
3563
The function finds the best access path to table 's' from the passed
3564
partial plan where an access path is the general term for any means to
3565
access the data in 's'. An access path may use either an index or a scan,
3566
whichever is cheaper. The input partial plan is passed via the array
3567
'join->positions' of length 'idx'. The chosen access method for 's' and its
3568
cost are stored in 'join->positions[idx]'.
3570
@param join pointer to the structure providing all context info
3572
@param s the table to be joined by the function
3573
@param session thread for the connection that submitted the query
3574
@param remaining_tables set of tables not included into the partial plan yet
3575
@param idx the length of the partial plan
3576
@param record_count estimate for the number of records returned by the
3578
@param read_time the cost of the partial plan
3583
static void best_access_path(JOIN *join,
3586
table_map remaining_tables,
3588
double record_count,
3591
KEYUSE *best_key= 0;
3592
uint32_t best_max_key_part= 0;
3593
bool found_constraint= 0;
3594
double best= DBL_MAX;
3595
double best_time= DBL_MAX;
3596
double records= DBL_MAX;
3597
table_map best_ref_depends_map= 0;
3600
uint32_t best_is_sj_inside_out= 0;
3603
{ /* Use key if possible */
3604
Table *table= s->table;
3605
KEYUSE *keyuse,*start_key=0;
3606
double best_records= DBL_MAX;
3607
uint32_t max_key_part=0;
3608
uint64_t bound_sj_equalities= 0;
3609
bool try_sj_inside_out= false;
3611
Discover the bound equalites. We need to do this, if
3612
1. The next table is an SJ-inner table, and
3613
2. It is the first table from that semijoin, and
3614
3. We're not within a semi-join range (i.e. all semi-joins either have
3615
all or none of their tables in join_table_map), except
3616
s->emb_sj_nest (which we've just entered).
3617
3. All correlation references from this sj-nest are bound
3619
if (s->emb_sj_nest && // (1)
3620
s->emb_sj_nest->sj_in_exprs < 64 &&
3621
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
3622
s->emb_sj_nest->sj_inner_tables) && // (2)
3623
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
3624
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
3626
/* This table is an InsideOut scan candidate */
3627
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
3629
try_sj_inside_out= true;
3632
/* Test how we can use keys */
3633
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3634
for (keyuse=s->keyuse ; keyuse->table == table ;)
3636
key_part_map found_part= 0;
3637
table_map found_ref= 0;
3638
uint32_t key= keyuse->key;
3639
KEY *keyinfo= table->key_info+key;
3640
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3641
key_part_map const_part= 0;
3642
/* The or-null keypart in ref-or-null access: */
3643
key_part_map ref_or_null_part= 0;
3645
/* Calculate how many key segments of the current key we can use */
3647
uint64_t handled_sj_equalities=0;
3648
key_part_map sj_insideout_map= 0;
3650
do /* For each keypart */
3652
uint32_t keypart= keyuse->keypart;
3653
table_map best_part_found_ref= 0;
3654
double best_prev_record_reads= DBL_MAX;
3656
do /* For each way to access the keypart */
3660
if 1. expression doesn't refer to forward tables
3661
2. we won't get two ref-or-null's
3663
if (!(remaining_tables & keyuse->used_tables) &&
3664
!(ref_or_null_part && (keyuse->optimize &
3665
KEY_OPTIMIZE_REF_OR_NULL)))
3667
found_part|= keyuse->keypart_map;
3668
if (!(keyuse->used_tables & ~join->const_table_map))
3669
const_part|= keyuse->keypart_map;
3671
double tmp2= prev_record_reads(join, idx, (found_ref |
3672
keyuse->used_tables));
3673
if (tmp2 < best_prev_record_reads)
3675
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
3676
best_prev_record_reads= tmp2;
3678
if (rec > keyuse->ref_table_rows)
3679
rec= keyuse->ref_table_rows;
3681
If there is one 'key_column IS NULL' expression, we can
3682
use this ref_or_null optimisation of this field
3684
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
3685
ref_or_null_part |= keyuse->keypart_map;
3688
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
3690
if (!(remaining_tables & keyuse->used_tables))
3691
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
3694
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
3695
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
3700
} while (keyuse->table == table && keyuse->key == key &&
3701
keyuse->keypart == keypart);
3702
found_ref|= best_part_found_ref;
3703
} while (keyuse->table == table && keyuse->key == key);
3706
Assume that that each key matches a proportional part of table.
3708
if (!found_part && !handled_sj_equalities)
3709
continue; // Nothing usable found
3711
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3712
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3714
bool sj_inside_out_scan= false;
3716
found_constraint= 1;
3718
Check if InsideOut scan is applicable:
3719
1. All IN-equalities are either "bound" or "handled"
3720
2. Index keyparts are
3723
if (try_sj_inside_out &&
3724
table->covering_keys.test(key) &&
3725
(handled_sj_equalities | bound_sj_equalities) == // (1)
3726
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
3728
uint32_t n_fixed_parts= max_part_bit(found_part);
3729
if (n_fixed_parts != keyinfo->key_parts &&
3730
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
3731
PREV_BITS(uint, keyinfo->key_parts))
3734
Not all parts are fixed. Produce bitmap of remaining bits and
3735
check if all of them are covered.
3737
sj_inside_out_scan= true;
3741
It's a confluent ref scan.
3743
That is, all found KEYUSE elements refer to IN-equalities,
3744
and there is really no ref access because there is no
3745
t.keypart0 = {bound expression}
3747
Calculate the cost of complete loose index scan.
3749
records= (double)s->table->file->stats.records;
3751
/* The cost is entire index scan cost (divided by 2) */
3752
best_time= s->table->file->index_only_read_time(key, records);
3754
/* Now figure how many different keys we will get */
3756
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
3757
records= records / rpc;
3764
Check if we found full key
3766
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3769
max_key_part= UINT32_MAX;
3770
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3772
tmp = prev_record_reads(join, idx, found_ref);
3778
{ /* We found a const key */
3780
ReuseRangeEstimateForRef-1:
3781
We get here if we've found a ref(const) (c_i are constants):
3782
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3784
If range optimizer was able to construct a "range"
3785
access on this index, then its condition "quick_cond" was
3786
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3787
from the range optimizer.
3789
Proof of (*): By properties of range and ref optimizers
3790
quick_cond will be equal or tighther than ref_const_cond.
3791
ref_const_cond already covers "smallest" possible interval -
3792
a singlepoint interval over all keyparts. Therefore,
3793
quick_cond is equivalent to ref_const_cond (if it was an
3794
empty interval we wouldn't have got here).
3796
if (table->quick_keys.test(key))
3797
records= (double) table->quick_rows[key];
3800
/* quick_range couldn't use key! */
3801
records= (double) s->records/rec;
3806
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3807
{ /* Prefer longer keys */
3809
((double) s->records / (double) rec *
3811
((double) (table->s->max_key_length-keyinfo->key_length) /
3812
(double) table->s->max_key_length)));
3814
records=2.0; /* Can't be as good as a unique */
3817
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3818
E(#rows) from range optimizer. Make another try:
3820
If range optimizer produced E(#rows) for a prefix of the ref
3821
access we're considering, and that E(#rows) is lower then our
3822
current estimate, make an adjustment. The criteria of when we
3823
can make an adjustment is a special case of the criteria used
3824
in ReuseRangeEstimateForRef-3.
3826
if (table->quick_keys.test(key) &&
3827
const_part & (1 << table->quick_key_parts[key]) &&
3828
table->quick_n_ranges[key] == 1 &&
3829
records > (double) table->quick_rows[key])
3831
records= (double) table->quick_rows[key];
3834
/* Limit the number of matched rows */
3836
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3837
if (table->covering_keys.test(key))
3839
/* we can use only index tree */
3840
tmp= record_count * table->file->index_only_read_time(key, tmp);
3843
tmp= record_count*cmin(tmp,s->worst_seeks);
3849
Use as much key-parts as possible and a uniq key is better
3850
than a not unique key
3851
Set tmp to (previous record count) * (records / combination)
3853
if ((found_part & 1) &&
3854
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
3855
found_part == PREV_BITS(uint,keyinfo->key_parts)))
3857
max_key_part= max_part_bit(found_part);
3859
ReuseRangeEstimateForRef-3:
3860
We're now considering a ref[or_null] access via
3861
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3862
(same-as-above but with one cond replaced
3863
with "t.keypart_i IS NULL")] (**)
3865
Try re-using E(#rows) from "range" optimizer:
3866
We can do so if "range" optimizer used the same intervals as
3867
in (**). The intervals used by range optimizer may be not
3868
available at this point (as "range" access might have choosen to
3869
create quick select over another index), so we can't compare
3870
them to (**). We'll make indirect judgements instead.
3871
The sufficient conditions for re-use are:
3872
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3873
this is not satisfied we have no way to know which ranges
3874
will be actually scanned by 'ref' until we execute the
3876
(C2) max #key parts in 'range' access == K == max_key_part (this
3877
is apparently a necessary requirement)
3879
We also have a property that "range optimizer produces equal or
3880
tighter set of scan intervals than ref(const) optimizer". Each
3881
of the intervals in (**) are "tightest possible" intervals when
3882
one limits itself to using keyparts 1..K (which we do in #2).
3883
From here it follows that range access used either one, or
3884
both of the (I1) and (I2) intervals:
3886
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3887
(same-as-above but with one cond replaced
3888
with "t.keypart_i IS NULL") (I2)
3890
The remaining part is to exclude the situation where range
3891
optimizer used one interval while we're considering
3892
ref-or-null and looking for estimate for two intervals. This
3893
is done by last limitation:
3895
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3897
if (table->quick_keys.test(key) && !found_ref && //(C1)
3898
table->quick_key_parts[key] == max_key_part && //(C2)
3899
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3901
tmp= records= (double) table->quick_rows[key];
3905
/* Check if we have statistic about the distribution */
3906
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3909
Fix for the case where the index statistics is too
3911
(1) We're considering ref(const) and there is quick select
3913
(2) and that quick select uses more keyparts (i.e. it will
3914
scan equal/smaller interval then this ref(const))
3915
(3) and E(#rows) for quick select is higher then our
3918
We'll use E(#rows) from quick select.
3920
Q: Why do we choose to use 'ref'? Won't quick select be
3921
cheaper in some cases ?
3922
TODO: figure this out and adjust the plan choice if needed.
3924
if (!found_ref && table->quick_keys.test(key) && // (1)
3925
table->quick_key_parts[key] > max_key_part && // (2)
3926
records < (double)table->quick_rows[key]) // (3)
3927
records= (double)table->quick_rows[key];
3934
Assume that the first key part matches 1% of the file
3935
and that the whole key matches 10 (duplicates) or 1
3937
Assume also that more key matches proportionally more
3939
This gives the formula:
3940
records = (x * (b-a) + a*c-b)/(c-1)
3942
b = records matched by whole key
3943
a = records matched by first key part (1% of all records?)
3944
c = number of key parts in key
3945
x = used key parts (1 <= x <= c)
3948
if (!(rec_per_key=(double)
3949
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3950
rec_per_key=(double) s->records/rec+1;
3954
else if (rec_per_key/(double) s->records >= 0.01)
3958
double a=s->records*0.01;
3959
if (keyinfo->key_parts > 1)
3960
tmp= (max_key_part * (rec_per_key - a) +
3961
a*keyinfo->key_parts - rec_per_key)/
3962
(keyinfo->key_parts-1);
3965
set_if_bigger(tmp,1.0);
3967
records = (uint32_t) tmp;
3970
if (ref_or_null_part)
3972
/* We need to do two key searches to find key */
3978
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3979
E(#rows) from range optimizer. Make another try:
3981
If range optimizer produced E(#rows) for a prefix of the ref
3982
access we're considering, and that E(#rows) is lower then our
3983
current estimate, make the adjustment.
3985
The decision whether we can re-use the estimate from the range
3986
optimizer is the same as in ReuseRangeEstimateForRef-3,
3987
applied to first table->quick_key_parts[key] key parts.
3989
if (table->quick_keys.test(key) &&
3990
table->quick_key_parts[key] <= max_key_part &&
3991
const_part & (1 << table->quick_key_parts[key]) &&
3992
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3993
const_part) ? 1 : 0) &&
3994
records > (double) table->quick_rows[key])
3996
tmp= records= (double) table->quick_rows[key];
4000
/* Limit the number of matched rows */
4001
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
4002
if (table->covering_keys.test(key))
4004
/* we can use only index tree */
4005
tmp= record_count * table->file->index_only_read_time(key, tmp);
4008
tmp= record_count * cmin(tmp,s->worst_seeks);
4011
tmp= best_time; // Do nothing
4014
if (sj_inside_out_scan && !start_key)
4022
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
4024
best_time= tmp + records/(double) TIME_FOR_COMPARE;
4026
best_records= records;
4027
best_key= start_key;
4028
best_max_key_part= max_key_part;
4029
best_ref_depends_map= found_ref;
4030
best_is_sj_inside_out= sj_inside_out_scan;
4033
records= best_records;
4037
Don't test table scan if it can't be better.
4038
Prefer key lookup if we would use the same key for scanning.
4040
Don't do a table scan on InnoDB tables, if we can read the used
4041
parts of the row from any of the used index.
4042
This is because table scans uses index and we would not win
4043
anything by using a table scan.
4045
A word for word translation of the below if-statement in sergefp's
4046
understanding: we check if we should use table scan if:
4047
(1) The found 'ref' access produces more records than a table scan
4048
(or index scan, or quick select), or 'ref' is more expensive than
4050
(2) This doesn't hold: the best way to perform table scan is to to perform
4051
'range' access using index IDX, and the best way to perform 'ref'
4052
access is to use the same index IDX, with the same or more key parts.
4053
(note: it is not clear how this rule is/should be extended to
4054
index_merge quick selects)
4055
(3) See above note about InnoDB.
4056
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
4057
path, but there is no quick select)
4058
If the condition in the above brackets holds, then the only possible
4059
"table scan" access method is ALL/index (there is no quick select).
4060
Since we have a 'ref' access path, and FORCE INDEX instructs us to
4061
choose it over ALL/index, there is no need to consider a full table
4064
if ((records >= s->found_records || best > s->read_time) && // (1)
4065
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
4066
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
4067
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
4068
! s->table->covering_keys.none() && best_key && !s->quick) &&// (3)
4069
!(s->table->force_index && best_key && !s->quick)) // (4)
4070
{ // Check full join
4071
ha_rows rnd_records= s->found_records;
4073
If there is a filtering condition on the table (i.e. ref analyzer found
4074
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
4075
preceding this table in the join order we're now considering), then
4076
assume that 25% of the rows will be filtered out by this condition.
4078
This heuristic is supposed to force tables used in exprZ to be before
4079
this table in join order.
4081
if (found_constraint)
4082
rnd_records-= rnd_records/4;
4085
If applicable, get a more accurate estimate. Don't use the two
4088
if (s->table->quick_condition_rows != s->found_records)
4089
rnd_records= s->table->quick_condition_rows;
4092
Range optimizer never proposes a RANGE if it isn't better
4093
than FULL: so if RANGE is present, it's always preferred to FULL.
4094
Here we estimate its cost.
4100
- read record range through 'quick'
4101
- skip rows which does not satisfy WHERE constraints
4103
We take into account possible use of join cache for ALL/index
4104
access (see first else-branch below), but we don't take it into
4105
account here for range/index_merge access. Find out why this is so.
4108
(s->quick->read_time +
4109
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
4113
/* Estimate cost of reading table. */
4114
tmp= s->table->file->scan_time();
4115
if (s->table->map & join->outer_join) // Can't use join cache
4118
For each record we have to:
4119
- read the whole table record
4120
- skip rows which does not satisfy join condition
4124
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
4128
/* We read the table as many times as join buffer becomes full. */
4129
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
4131
(double) session->variables.join_buff_size));
4133
We don't make full cartesian product between rows in the scanned
4134
table and existing records because we skip all rows from the
4135
scanned table, which does not satisfy join condition when
4136
we read the table (see flush_cached_records for details). Here we
4137
take into account cost to read and skip these records.
4139
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
4144
We estimate the cost of evaluating WHERE clause for found records
4145
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
4146
tmp give us total cost of using Table SCAN
4148
if (best == DBL_MAX ||
4149
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
4150
best + record_count/(double) TIME_FOR_COMPARE*records))
4153
If the table has a range (s->quick is set) make_join_select()
4154
will ensure that this will be used
4157
records= rows2double(rnd_records);
4159
/* range/index_merge/ALL/index access method are "independent", so: */
4160
best_ref_depends_map= 0;
4161
best_is_sj_inside_out= false;
4165
/* Update the cost information for the current partial plan */
4166
join->positions[idx].records_read= records;
4167
join->positions[idx].read_time= best;
4168
join->positions[idx].key= best_key;
4169
join->positions[idx].table= s;
4170
join->positions[idx].ref_depend_map= best_ref_depends_map;
4171
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
4174
idx == join->const_tables &&
4175
s->table == join->sort_by_table &&
4176
join->unit->select_limit_cnt >= records)
4177
join->sort_by_table= (Table*) 1; // Must use temporary table
4183
Select the best ways to access the tables in a query without reordering them.
4185
Find the best access paths for each query table and compute their costs
4186
according to their order in the array 'join->best_ref' (thus without
4187
reordering the join tables). The function calls sequentially
4188
'best_access_path' for each table in the query to select the best table
4189
access method. The final optimal plan is stored in the array
4190
'join->best_positions', and the corresponding cost in 'join->best_read'.
4192
@param join pointer to the structure providing all context info for
4194
@param join_tables set of the tables in the query
4197
This function can be applied to:
4198
- queries with STRAIGHT_JOIN
4199
- internally to compute the cost of an arbitrary QEP
4201
Thus 'optimize_straight_join' can be used at any stage of the query
4202
optimization process to finalize a QEP as it is.
4204
static void optimize_straight_join(JOIN *join, table_map join_tables)
4207
uint32_t idx= join->const_tables;
4208
double record_count= 1.0;
4209
double read_time= 0.0;
4211
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4213
/* Find the best access method from 's' to the current partial plan */
4214
advance_sj_state(join_tables, s);
4215
best_access_path(join, s, join->session, join_tables, idx,
4216
record_count, read_time);
4217
/* compute the cost of the new plan extended with 's' */
4218
record_count*= join->positions[idx].records_read;
4219
read_time+= join->positions[idx].read_time;
4220
join_tables&= ~(s->table->map);
4224
read_time+= record_count / (double) TIME_FOR_COMPARE;
4225
if (join->sort_by_table &&
4226
join->sort_by_table != join->positions[join->const_tables].table->table)
4227
read_time+= record_count; // We have to make a temp table
4228
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
4229
join->best_read= read_time;
4233
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
4235
The search procedure uses a hybrid greedy/exhaustive search with controlled
4236
exhaustiveness. The search is performed in N = card(remaining_tables)
4237
steps. Each step evaluates how promising is each of the unoptimized tables,
4238
selects the most promising table, and extends the current partial QEP with
4239
that table. Currenly the most 'promising' table is the one with least
4240
expensive extension.\
4242
There are two extreme cases:
4243
-# When (card(remaining_tables) < search_depth), the estimate finds the
4244
best complete continuation of the partial QEP. This continuation can be
4245
used directly as a result of the search.
4246
-# When (search_depth == 1) the 'best_extension_by_limited_search'
4247
consideres the extension of the current QEP with each of the remaining
4250
All other cases are in-between these two extremes. Thus the parameter
4251
'search_depth' controlls the exhaustiveness of the search. The higher the
4252
value, the longer the optimizaton time and possibly the better the
4253
resulting plan. The lower the value, the fewer alternative plans are
4254
estimated, but the more likely to get a bad QEP.
4256
All intermediate and final results of the procedure are stored in 'join':
4257
- join->positions : modified for every partial QEP that is explored
4258
- join->best_positions: modified for the current best complete QEP
4259
- join->best_read : modified for the current best complete QEP
4260
- join->best_ref : might be partially reordered
4262
The final optimal plan is stored in 'join->best_positions', and its
4263
corresponding cost in 'join->best_read'.
4266
The following pseudocode describes the algorithm of 'greedy_search':
4269
procedure greedy_search
4270
input: remaining_tables
4275
(t, a) = best_extension(pplan, remaining_tables);
4276
pplan = concat(pplan, (t, a));
4277
remaining_tables = remaining_tables - t;
4278
} while (remaining_tables != {})
4283
where 'best_extension' is a placeholder for a procedure that selects the
4284
most "promising" of all tables in 'remaining_tables'.
4285
Currently this estimate is performed by calling
4286
'best_extension_by_limited_search' to evaluate all extensions of the
4287
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
4288
mainly depends on that of 'best_extension_by_limited_search'.
4291
If 'best_extension()' == 'best_extension_by_limited_search()', then the
4292
worst-case complexity of this algorithm is <=
4293
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
4294
complexity of greedy_search is O(N!).
4297
In the future, 'greedy_search' might be extended to support other
4298
implementations of 'best_extension', e.g. some simpler quadratic procedure.
4300
@param join pointer to the structure providing all context info
4302
@param remaining_tables set of tables not included into the partial plan yet
4303
@param search_depth controlls the exhaustiveness of the search
4304
@param prune_level the pruning heuristics that should be applied during
4312
static bool greedy_search(JOIN *join,
4313
table_map remaining_tables,
4314
uint32_t search_depth,
4315
uint32_t prune_level)
4317
double record_count= 1.0;
4318
double read_time= 0.0;
4319
uint32_t idx= join->const_tables; // index into 'join->best_ref'
4321
uint32_t size_remain; // cardinality of remaining_tables
4323
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
4325
/* number of tables that remain to be optimized */
4326
size_remain= my_count_bits(remaining_tables);
4329
/* Find the extension of the current QEP with the lowest cost */
4330
join->best_read= DBL_MAX;
4331
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
4332
read_time, search_depth, prune_level))
4335
if (size_remain <= search_depth)
4338
'join->best_positions' contains a complete optimal extension of the
4339
current partial QEP.
4344
/* select the first table in the optimal extension as most promising */
4345
best_pos= join->best_positions[idx];
4346
best_table= best_pos.table;
4348
Each subsequent loop of 'best_extension_by_limited_search' uses
4349
'join->positions' for cost estimates, therefore we have to update its
4352
join->positions[idx]= best_pos;
4354
/* find the position of 'best_table' in 'join->best_ref' */
4356
JOIN_TAB *pos= join->best_ref[best_idx];
4357
while (pos && best_table != pos)
4358
pos= join->best_ref[++best_idx];
4359
assert((pos != NULL)); // should always find 'best_table'
4360
/* move 'best_table' at the first free position in the array of joins */
4361
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4363
/* compute the cost of the new plan extended with 'best_table' */
4364
record_count*= join->positions[idx].records_read;
4365
read_time+= join->positions[idx].read_time;
4367
remaining_tables&= ~(best_table->table->map);
4375
Find a good, possibly optimal, query execution plan (QEP) by a possibly
4378
The procedure searches for the optimal ordering of the query tables in set
4379
'remaining_tables' of size N, and the corresponding optimal access paths to
4380
each table. The choice of a table order and an access path for each table
4381
constitutes a query execution plan (QEP) that fully specifies how to
4384
The maximal size of the found plan is controlled by the parameter
4385
'search_depth'. When search_depth == N, the resulting plan is complete and
4386
can be used directly as a QEP. If search_depth < N, the found plan consists
4387
of only some of the query tables. Such "partial" optimal plans are useful
4388
only as input to query optimization procedures, and cannot be used directly
4391
The algorithm begins with an empty partial plan stored in 'join->positions'
4392
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4393
evaluates the cost of the partial plan extended by all access plans for
4394
each of the relations in 'remaining_tables', expands the current partial
4395
plan with the access plan that results in lowest cost of the expanded
4396
partial plan, and removes the corresponding relation from
4397
'remaining_tables'. The algorithm continues until it either constructs a
4398
complete optimal plan, or constructs an optimal plartial plan with size =
4401
The final optimal plan is stored in 'join->best_positions'. The
4402
corresponding cost of the optimal plan is in 'join->best_read'.
4405
The procedure uses a recursive depth-first search where the depth of the
4406
recursion (and thus the exhaustiveness of the search) is controlled by the
4407
parameter 'search_depth'.
4410
The pseudocode below describes the algorithm of
4411
'best_extension_by_limited_search'. The worst-case complexity of this
4412
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4413
the complexity of greedy_search is O(N!).
4416
procedure best_extension_by_limited_search(
4417
pplan in, // in, partial plan of tables-joined-so-far
4418
pplan_cost, // in, cost of pplan
4419
remaining_tables, // in, set of tables not referenced in pplan
4420
best_plan_so_far, // in/out, best plan found so far
4421
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4422
search_depth) // in, maximum size of the plans being considered
4424
for each table T from remaining_tables
4426
// Calculate the cost of using table T as above
4427
cost = complex-series-of-calculations;
4429
// Add the cost to the cost so far.
4432
if (pplan_cost >= best_plan_so_far_cost)
4433
// pplan_cost already too great, stop search
4436
pplan= expand pplan by best_access_method;
4437
remaining_tables= remaining_tables - table T;
4438
if (remaining_tables is not an empty set
4442
best_extension_by_limited_search(pplan, pplan_cost,
4445
best_plan_so_far_cost,
4450
best_plan_so_far_cost= pplan_cost;
4451
best_plan_so_far= pplan;
4458
When 'best_extension_by_limited_search' is called for the first time,
4459
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4460
The actual implementation provides a way to optionally use pruning
4461
heuristic (controlled by the parameter 'prune_level') to reduce the search
4462
space by skipping some partial plans.
4465
The parameter 'search_depth' provides control over the recursion
4466
depth, and thus the size of the resulting optimal plan.
4468
@param join pointer to the structure providing all context info
4470
@param remaining_tables set of tables not included into the partial plan yet
4471
@param idx length of the partial QEP in 'join->positions';
4472
since a depth-first search is used, also corresponds
4473
to the current depth of the search tree;
4474
also an index in the array 'join->best_ref';
4475
@param record_count estimate for the number of records returned by the
4477
@param read_time the cost of the best partial plan
4478
@param search_depth maximum depth of the recursion and thus size of the
4480
(0 < search_depth <= join->tables+1).
4481
@param prune_level pruning heuristics that should be applied during
4483
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4490
static bool best_extension_by_limited_search(JOIN *join,
4491
table_map remaining_tables,
4493
double record_count,
4495
uint32_t search_depth,
4496
uint32_t prune_level)
4498
Session *session= join->session;
4499
if (session->killed) // Abort
4503
'join' is a partial plan with lower cost than the best plan so far,
4504
so continue expanding it further with the tables in 'remaining_tables'.
4507
double best_record_count= DBL_MAX;
4508
double best_read_time= DBL_MAX;
4510
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4512
table_map real_table_bit= s->table->map;
4513
if ((remaining_tables & real_table_bit) &&
4514
!(remaining_tables & s->dependent) &&
4515
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
4517
double current_record_count, current_read_time;
4518
advance_sj_state(remaining_tables, s);
4521
psergey-insideout-todo:
4522
when best_access_path() detects it could do an InsideOut scan or
4523
some other scan, have it return an insideout scan and a flag that
4524
requests to "fork" this loop iteration. (Q: how does that behave
4525
when the depth is insufficient??)
4527
/* Find the best access method from 's' to the current partial plan */
4528
best_access_path(join, s, session, remaining_tables, idx,
4529
record_count, read_time);
4530
/* Compute the cost of extending the plan with 's' */
4531
current_record_count= record_count * join->positions[idx].records_read;
4532
current_read_time= read_time + join->positions[idx].read_time;
4534
/* Expand only partial plans with lower cost than the best QEP so far */
4535
if ((current_read_time +
4536
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4538
restore_prev_nj_state(s);
4539
restore_prev_sj_state(remaining_tables, s);
4544
Prune some less promising partial plans. This heuristic may miss
4545
the optimal QEPs, thus it results in a non-exhaustive search.
4547
if (prune_level == 1)
4549
if (best_record_count > current_record_count ||
4550
best_read_time > current_read_time ||
4551
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4553
if (best_record_count >= current_record_count &&
4554
best_read_time >= current_read_time &&
4555
/* TODO: What is the reasoning behind this condition? */
4556
(!(s->key_dependent & remaining_tables) ||
4557
join->positions[idx].records_read < 2.0))
4559
best_record_count= current_record_count;
4560
best_read_time= current_read_time;
4565
restore_prev_nj_state(s);
4566
restore_prev_sj_state(remaining_tables, s);
4571
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4572
{ /* Recursively expand the current partial plan */
4573
std::swap(join->best_ref[idx], *pos);
4574
if (best_extension_by_limited_search(join,
4575
remaining_tables & ~real_table_bit,
4577
current_record_count,
4582
std::swap(join->best_ref[idx], *pos);
4586
'join' is either the best partial QEP with 'search_depth' relations,
4587
or the best complete QEP so far, whichever is smaller.
4589
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4590
if (join->sort_by_table &&
4591
join->sort_by_table !=
4592
join->positions[join->const_tables].table->table)
4593
/* We have to make a temp table */
4594
current_read_time+= current_record_count;
4595
if ((search_depth == 1) || (current_read_time < join->best_read))
4597
memcpy(join->best_positions, join->positions,
4598
sizeof(POSITION) * (idx + 1));
4599
join->best_read= current_read_time - 0.001;
4602
restore_prev_nj_state(s);
4603
restore_prev_sj_state(remaining_tables, s);
4610
Heuristic procedure to automatically guess a reasonable degree of
4611
exhaustiveness for the greedy search procedure.
4613
The procedure estimates the optimization time and selects a search depth
4614
big enough to result in a near-optimal QEP, that doesn't take too long to
4615
find. If the number of tables in the query exceeds some constant, then
4616
search_depth is set to this constant.
4618
@param join pointer to the structure providing all context info for
4622
This is an extremely simplistic implementation that serves as a stub for a
4623
more advanced analysis of the join. Ideally the search depth should be
4624
determined by learning from previous query optimizations, because it will
4625
depend on the CPU power (and other factors).
4628
this value should be determined dynamically, based on statistics:
4629
uint32_t max_tables_for_exhaustive_opt= 7;
4632
this value could be determined by some mapping of the form:
4633
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4636
A positive integer that specifies the search depth (and thus the
4637
exhaustiveness) of the depth-first search algorithm used by
4640
static uint32_t determine_search_depth(JOIN *join)
4642
uint32_t table_count= join->tables - join->const_tables;
4643
uint32_t search_depth;
4644
/* TODO: this value should be determined dynamically, based on statistics: */
4645
uint32_t max_tables_for_exhaustive_opt= 7;
4647
if (table_count <= max_tables_for_exhaustive_opt)
4648
search_depth= table_count+1; // use exhaustive for small number of tables
4651
TODO: this value could be determined by some mapping of the form:
4652
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4654
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4656
return search_depth;
4659
static bool make_simple_join(JOIN *join,Table *tmp_table)
4665
Reuse Table * and JOIN_TAB if already allocated by a previous call
4666
to this function through JOIN::exec (may happen for sub-queries).
4668
if (!join->table_reexec)
4670
if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
4671
return(true); /* purecov: inspected */
4673
join->tmp_join->table_reexec= join->table_reexec;
4675
if (!join->join_tab_reexec)
4677
if (!(join->join_tab_reexec=
4678
(JOIN_TAB*) join->session->alloc(sizeof(JOIN_TAB))))
4679
return(true); /* purecov: inspected */
4681
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4683
tableptr= join->table_reexec;
4684
join_tab= join->join_tab_reexec;
4686
join->join_tab=join_tab;
4687
join->table=tableptr; tableptr[0]=tmp_table;
4689
join->const_tables=0;
4690
join->const_table_map=0;
4691
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4692
join->tmp_table_param.func_count=0;
4693
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4694
join->first_record=join->sort_and_group=0;
4695
join->send_records=(ha_rows) 0;
4697
join->row_limit=join->unit->select_limit_cnt;
4698
join->do_send_rows = (join->row_limit) ? 1 : 0;
4700
join_tab->cache.buff=0; /* No caching */
4701
join_tab->table=tmp_table;
4703
join_tab->select_cond=0;
4705
join_tab->type= JT_ALL; /* Map through all records */
4706
join_tab->keys.set(); /* test everything in quick */
4708
join_tab->on_expr_ref=0;
4709
join_tab->last_inner= 0;
4710
join_tab->first_unmatched= 0;
4711
join_tab->ref.key = -1;
4712
join_tab->not_used_in_distinct=0;
4713
join_tab->read_first_record= join_init_read_record;
4714
join_tab->join=join;
4715
join_tab->ref.key_parts= 0;
4716
join_tab->flush_weedout_table= join_tab->check_weed_out_table= NULL;
4717
join_tab->do_firstmatch= NULL;
4718
memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4719
tmp_table->status=0;
4720
tmp_table->null_row=0;
4725
Fill in outer join related info for the execution plan structure.
4727
For each outer join operation left after simplification of the
4728
original query the function set up the following pointers in the linear
4729
structure join->join_tab representing the selected execution plan.
4730
The first inner table t0 for the operation is set to refer to the last
4731
inner table tk through the field t0->last_inner.
4732
Any inner table ti for the operation are set to refer to the first
4733
inner table ti->first_inner.
4734
The first inner table t0 for the operation is set to refer to the
4735
first inner table of the embedding outer join operation, if there is any,
4736
through the field t0->first_upper.
4737
The on expression for the outer join operation is attached to the
4738
corresponding first inner table through the field t0->on_expr_ref.
4739
Here ti are structures of the JOIN_TAB type.
4741
EXAMPLE. For the query:
4745
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4746
ON (t1.a=t2.a AND t1.b=t3.b)
4750
given the execution plan with the table order t1,t2,t3,t4
4751
is selected, the following references will be set;
4752
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4753
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4754
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4755
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4757
@param join reference to the info fully describing the query
4760
The function assumes that the simplification procedure has been
4761
already applied to the join query (see simplify_joins).
4762
This function can be called only after the execution plan
4765
static void make_outerjoin_info(JOIN *join)
4767
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4769
JOIN_TAB *tab=join->join_tab+i;
4770
Table *table=tab->table;
4771
TableList *tbl= table->pos_in_table_list;
4772
TableList *embedding= tbl->embedding;
4774
if (tbl->outer_join)
4777
Table tab is the only one inner table for outer join.
4778
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4779
is in the query above.)
4781
tab->last_inner= tab->first_inner= tab;
4782
tab->on_expr_ref= &tbl->on_expr;
4783
tab->cond_equal= tbl->cond_equal;
4785
tab->first_upper= embedding->nested_join->first_nested;
4787
for ( ; embedding ; embedding= embedding->embedding)
4789
/* Ignore sj-nests: */
4790
if (!embedding->on_expr)
4792
nested_join_st *nested_join= embedding->nested_join;
4793
if (!nested_join->counter_)
4796
Table tab is the first inner table for nested_join.
4797
Save reference to it in the nested join structure.
4799
nested_join->first_nested= tab;
4800
tab->on_expr_ref= &embedding->on_expr;
4801
tab->cond_equal= tbl->cond_equal;
4802
if (embedding->embedding)
4803
tab->first_upper= embedding->embedding->nested_join->first_nested;
4805
if (!tab->first_inner)
4806
tab->first_inner= nested_join->first_nested;
4807
if (++nested_join->counter_ < nested_join->join_list.elements)
4809
/* Table tab is the last inner table for nested join. */
4810
nested_join->first_nested->last_inner= tab;
4816
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
4818
Session *session= join->session;
4821
add_not_null_conds(join);
4822
table_map used_tables;
4823
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4824
{ /* there may be a select without a cond. */
4825
if (join->tables > 1)
4826
cond->update_used_tables(); // Tablenr may have changed
4827
if (join->const_tables == join->tables &&
4828
session->lex->current_select->master_unit() ==
4829
&session->lex->unit) // not upper level SELECT
4830
join->const_table_map|=RAND_TABLE_BIT;
4831
{ // Check const tables
4833
make_cond_for_table(cond,
4834
join->const_table_map,
4836
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
4837
tab < join->join_tab+join->tables ; tab++)
4839
if (*tab->on_expr_ref)
4841
JOIN_TAB *cond_tab= tab->first_inner;
4842
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4843
join->const_table_map,
4847
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4850
tmp->quick_fix_field();
4851
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4852
new Item_cond_and(cond_tab->select_cond,
4854
if (!cond_tab->select_cond)
4856
cond_tab->select_cond->quick_fix_field();
4859
if (const_cond && !const_cond->val_int())
4861
return(1); // Impossible const condition
4865
used_tables=((select->const_tables=join->const_table_map) |
4866
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4867
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4869
JOIN_TAB *tab=join->join_tab+i;
4871
first_inner is the X in queries like:
4872
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4874
JOIN_TAB *first_inner_tab= tab->first_inner;
4875
table_map current_map= tab->table->map;
4876
bool use_quick_range=0;
4880
Following force including random expression in last table condition.
4881
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4883
if (i == join->tables-1)
4884
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4885
used_tables|=current_map;
4887
if (tab->type == JT_REF && tab->quick &&
4888
(uint32_t) tab->ref.key == tab->quick->index &&
4889
tab->ref.key_length < tab->quick->max_used_key_length)
4891
/* Range uses longer key; Use this instead of ref on key */
4896
tab->ref.key_parts=0; // Don't use ref key.
4897
join->best_positions[i].records_read= rows2double(tab->quick->records);
4899
We will use join cache here : prevent sorting of the first
4900
table only and sort at the end.
4902
if (i != join->const_tables && join->tables > join->const_tables + 1)
4908
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4909
if (cond && !tmp && tab->quick)
4911
if (tab->type != JT_ALL)
4914
Don't use the quick method
4915
We come here in the case where we have 'key=constant' and
4916
the test is removed by make_cond_for_table()
4924
Hack to handle the case where we only refer to a table
4925
in the ON part of an OUTER JOIN. In this case we want the code
4926
below to check if we should use 'quick' instead.
4928
tmp= new Item_int((int64_t) 1,1); // Always true
4932
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
4933
tab->type == JT_EQ_REF)
4935
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
4936
session->memdup((unsigned char*) select,
4939
return(1); // End of memory
4941
If tab is an inner table of an outer join operation,
4942
add a match guard to the pushed down predicate.
4943
The guard will turn the predicate on only after
4944
the first match for outer tables is encountered.
4949
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4950
a cond, so neutralize the hack above.
4952
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4954
tab->select_cond=sel->cond=tmp;
4955
/* Push condition to storage engine if this is enabled
4956
and the condition is not guarded */
4957
tab->table->file->pushed_cond= NULL;
4958
if (session->variables.engine_condition_pushdown)
4961
make_cond_for_table(tmp, current_map, current_map, 0);
4964
/* Push condition to handler */
4965
if (!tab->table->file->cond_push(push_cond))
4966
tab->table->file->pushed_cond= push_cond;
4971
tab->select_cond= sel->cond= NULL;
4973
sel->head=tab->table;
4976
/* Use quick key read if it's a constant and it's not used
4978
if (tab->needed_reg.none() && tab->type != JT_EQ_REF
4979
&& (tab->type != JT_REF || (uint32_t) tab->ref.key == tab->quick->index))
4981
sel->quick=tab->quick; // Use value from get_quick_...
4982
sel->quick_keys.reset();
4983
sel->needed_reg.reset();
4991
uint32_t ref_key=(uint32_t) sel->head->reginfo.join_tab->ref.key+1;
4992
if (i == join->const_tables && ref_key)
4994
if (tab->const_keys.any() &&
4995
tab->table->reginfo.impossible_range)
4998
else if (tab->type == JT_ALL && ! use_quick_range)
5000
if (tab->const_keys.any() &&
5001
tab->table->reginfo.impossible_range)
5002
return(1); // Impossible range
5004
We plan to scan all rows.
5005
Check again if we should use an index.
5006
We could have used an column from a previous table in
5007
the index if we are using limit and this is the first table
5010
if ((cond && (!((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
5011
(!tab->const_keys.none() && (i == join->const_tables) && (join->unit->select_limit_cnt < join->best_positions[i].records_read) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
5013
/* Join with outer join condition */
5014
COND *orig_cond=sel->cond;
5015
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
5018
We can't call sel->cond->fix_fields,
5019
as it will break tab->on_expr if it's AND condition
5020
(fix_fields currently removes extra AND/OR levels).
5021
Yet attributes of the just built condition are not needed.
5022
Thus we call sel->cond->quick_fix_field for safety.
5024
if (sel->cond && !sel->cond->fixed)
5025
sel->cond->quick_fix_field();
5027
if (sel->test_quick_select(session, tab->keys,
5028
used_tables & ~ current_map,
5029
(join->select_options &
5032
join->unit->select_limit_cnt), 0,
5036
Before reporting "Impossible WHERE" for the whole query
5037
we have to check isn't it only "impossible ON" instead
5039
sel->cond=orig_cond;
5040
if (!*tab->on_expr_ref ||
5041
sel->test_quick_select(session, tab->keys,
5042
used_tables & ~ current_map,
5043
(join->select_options &
5046
join->unit->select_limit_cnt),0,
5048
return(1); // Impossible WHERE
5051
sel->cond=orig_cond;
5053
/* Fix for EXPLAIN */
5055
join->best_positions[i].records_read= (double)sel->quick->records;
5059
sel->needed_reg=tab->needed_reg;
5060
sel->quick_keys.reset();
5062
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
5063
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
5065
tab->keys= sel->quick_keys;
5066
tab->keys|= sel->needed_reg;
5067
tab->use_quick= (!sel->needed_reg.none() &&
5068
(select->quick_keys.none() ||
5070
(select->quick->records >= 100L)))) ?
5072
sel->read_tables= used_tables & ~current_map;
5074
if (i != join->const_tables && tab->use_quick != 2)
5075
{ /* Read with cache */
5077
(tmp=make_cond_for_table(cond,
5078
join->const_table_map |
5082
tab->cache.select=(SQL_SELECT*)
5083
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
5084
tab->cache.select->cond=tmp;
5085
tab->cache.select->read_tables=join->const_table_map;
5092
Push down conditions from all on expressions.
5093
Each of these conditions are guarded by a variable
5094
that turns if off just before null complemented row for
5095
outer joins is formed. Thus, the condition from an
5096
'on expression' are guaranteed not to be checked for
5097
the null complemented row.
5100
/* First push down constant conditions from on expressions */
5101
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
5102
join_tab < join->join_tab+join->tables ; join_tab++)
5104
if (*join_tab->on_expr_ref)
5106
JOIN_TAB *cond_tab= join_tab->first_inner;
5107
tmp= make_cond_for_table(*join_tab->on_expr_ref,
5108
join->const_table_map,
5112
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
5115
tmp->quick_fix_field();
5116
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
5117
new Item_cond_and(cond_tab->select_cond,tmp);
5118
if (!cond_tab->select_cond)
5120
cond_tab->select_cond->quick_fix_field();
5124
/* Push down non-constant conditions from on expressions */
5125
JOIN_TAB *last_tab= tab;
5126
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
5129
Table tab is the last inner table of an outer join.
5130
An on expression is always attached to it.
5132
COND *on_expr= *first_inner_tab->on_expr_ref;
5134
table_map used_tables2= (join->const_table_map |
5135
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
5136
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
5138
current_map= tab->table->map;
5139
used_tables2|= current_map;
5140
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
5144
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
5146
First add the guards for match variables of
5147
all embedding outer join operations.
5149
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
5154
Now add the guard turning the predicate off for
5155
the null complemented row.
5157
tmp_cond= new Item_func_trig_cond(tmp_cond,
5161
tmp_cond->quick_fix_field();
5162
/* Add the predicate to other pushed down predicates */
5163
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
5164
new Item_cond_and(cond_tab->select_cond,
5166
if (!cond_tab->select_cond)
5168
cond_tab->select_cond->quick_fix_field();
5171
first_inner_tab= first_inner_tab->first_upper;
5179
Plan refinement stage: do various set ups for the executioner
5182
make_join_readinfo()
5183
join Join being processed
5184
options Join's options (checking for SELECT_DESCRIBE,
5185
SELECT_NO_JOIN_CACHE)
5186
no_jbuf_after Don't use join buffering after table with this number.
5189
Plan refinement stage: do various set ups for the executioner
5190
- set up use of join buffering
5191
- push index conditions
5192
- increment counters
5197
true - Out of memory
5199
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
5202
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
5205
for (i=join->const_tables ; i < join->tables ; i++)
5207
JOIN_TAB *tab=join->join_tab+i;
5208
Table *table=tab->table;
5209
bool using_join_cache;
5210
tab->read_record.table= table;
5211
tab->read_record.file=table->file;
5212
tab->next_select=sub_select; /* normal select */
5214
TODO: don't always instruct first table's ref/range access method to
5215
produce sorted output.
5217
tab->sorted= sorted;
5218
sorted= 0; // only first must be sorted
5219
if (tab->insideout_match_tab)
5221
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
5226
switch (tab->type) {
5227
case JT_SYSTEM: // Only happens with left join
5228
table->status=STATUS_NO_RECORD;
5229
tab->read_first_record= join_read_system;
5230
tab->read_record.read_record= join_no_more_records;
5232
case JT_CONST: // Only happens with left join
5233
table->status=STATUS_NO_RECORD;
5234
tab->read_first_record= join_read_const;
5235
tab->read_record.read_record= join_no_more_records;
5236
if (table->covering_keys.test(tab->ref.key) &&
5240
table->file->extra(HA_EXTRA_KEYREAD);
5244
table->status=STATUS_NO_RECORD;
5247
delete tab->select->quick;
5248
tab->select->quick=0;
5252
tab->read_first_record= join_read_key;
5253
tab->read_record.read_record= join_no_more_records;
5254
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
5257
table->file->extra(HA_EXTRA_KEYREAD);
5260
push_index_cond(tab, tab->ref.key, true);
5262
case JT_REF_OR_NULL:
5264
table->status=STATUS_NO_RECORD;
5267
delete tab->select->quick;
5268
tab->select->quick=0;
5272
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
5275
table->file->extra(HA_EXTRA_KEYREAD);
5278
push_index_cond(tab, tab->ref.key, true);
5279
if (tab->type == JT_REF)
5281
tab->read_first_record= join_read_always_key;
5282
tab->read_record.read_record= tab->insideout_match_tab?
5283
join_read_next_same_diff : join_read_next_same;
5287
tab->read_first_record= join_read_always_key_or_null;
5288
tab->read_record.read_record= join_read_next_same_or_null;
5293
If previous table use cache
5294
If the incoming data set is already sorted don't use cache.
5296
table->status=STATUS_NO_RECORD;
5297
using_join_cache= false;
5298
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
5299
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
5300
!tab->insideout_match_tab)
5302
if ((options & SELECT_DESCRIBE) ||
5303
!join_init_cache(join->session,join->join_tab+join->const_tables,
5304
i-join->const_tables))
5306
using_join_cache= true;
5307
tab[-1].next_select=sub_select_cache; /* Patch previous */
5310
/* These init changes read_record */
5311
if (tab->use_quick == 2)
5313
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
5314
tab->read_first_record= join_init_quick_read_record;
5316
status_var_increment(join->session->status_var.select_range_check_count);
5320
tab->read_first_record= join_init_read_record;
5321
if (i == join->const_tables)
5323
if (tab->select && tab->select->quick)
5326
status_var_increment(join->session->status_var.select_range_count);
5330
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
5332
status_var_increment(join->session->status_var.select_scan_count);
5337
if (tab->select && tab->select->quick)
5340
status_var_increment(join->session->status_var.select_full_range_join_count);
5344
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
5346
status_var_increment(join->session->status_var.select_full_join_count);
5349
if (!table->no_keyread)
5351
if (tab->select && tab->select->quick &&
5352
tab->select->quick->index != MAX_KEY && //not index_merge
5353
table->covering_keys.test(tab->select->quick->index))
5356
table->file->extra(HA_EXTRA_KEYREAD);
5358
else if (!table->covering_keys.none() &&
5359
!(tab->select && tab->select->quick))
5360
{ // Only read index tree
5361
if (!tab->insideout_match_tab)
5364
See bug #26447: "Using the clustered index for a table scan
5365
is always faster than using a secondary index".
5367
if (table->s->primary_key != MAX_KEY &&
5368
table->file->primary_key_is_clustered())
5369
tab->index= table->s->primary_key;
5371
tab->index= table->find_shortest_key(&table->covering_keys);
5373
tab->read_first_record= join_read_first;
5374
tab->type=JT_NEXT; // Read with index_first / index_next
5377
if (tab->select && tab->select->quick &&
5378
tab->select->quick->index != MAX_KEY && ! tab->table->key_read)
5379
push_index_cond(tab, tab->select->quick->index, !using_join_cache);
5383
break; /* purecov: deadcode */
5386
abort(); /* purecov: deadcode */
5389
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
5393
/** Update the dependency map for the tables. */
5394
static void update_depend_map(JOIN *join)
5396
JOIN_TAB *join_tab=join->join_tab, *end=join_tab+join->tables;
5398
for (; join_tab != end ; join_tab++)
5400
TABLE_REF *ref= &join_tab->ref;
5401
table_map depend_map=0;
5402
Item **item=ref->items;
5404
for (i=0 ; i < ref->key_parts ; i++,item++)
5405
depend_map|=(*item)->used_tables();
5406
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
5407
depend_map&= ~OUTER_REF_TABLE_BIT;
5408
for (JOIN_TAB **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5411
ref->depend_map|=(*tab)->ref.depend_map;
5416
/** Update the dependency map for the sort order. */
5417
static void update_depend_map(JOIN *join, order_st *order)
5419
for (; order ; order=order->next)
5421
table_map depend_map;
5422
order->item[0]->update_used_tables();
5423
order->depend_map=depend_map=order->item[0]->used_tables();
5424
// Not item_sum(), RAND() and no reference to table outside of sub select
5425
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5426
&& !order->item[0]->with_sum_func)
5428
for (JOIN_TAB **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5431
order->depend_map|=(*tab)->ref.depend_map;
5438
Remove all constants and check if order_st only contains simple
5441
simple_order is set to 1 if sort_order only uses fields from head table
5442
and the head table is not a LEFT JOIN table.
5444
@param join Join handler
5445
@param first_order List of SORT or GROUP order
5446
@param cond WHERE statement
5447
@param change_list Set to 1 if we should remove things from list.
5448
If this is not set, then only simple_order is
5450
@param simple_order Set to 1 if we are only using simple expressions
5453
Returns new sort order
5455
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5457
if (join->tables == join->const_tables)
5458
return change_list ? 0 : first_order; // No need to sort
5460
order_st *order,**prev_ptr;
5461
table_map first_table= join->join_tab[join->const_tables].table->map;
5462
table_map not_const_tables= ~join->const_table_map;
5465
prev_ptr= &first_order;
5466
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5468
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5470
update_depend_map(join, first_order);
5471
for (order=first_order; order ; order=order->next)
5473
table_map order_tables=order->item[0]->used_tables();
5474
if (order->item[0]->with_sum_func)
5475
*simple_order=0; // Must do a temp table to sort
5476
else if (!(order_tables & not_const_tables))
5478
if (order->item[0]->with_subselect)
5479
order->item[0]->val_str(&order->item[0]->str_value);
5480
continue; // skip const item
5484
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5489
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5493
if ((ref=order_tables & (not_const_tables ^ first_table)))
5495
if (!(order_tables & first_table) &&
5496
only_eq_ref_tables(join,first_order, ref))
5500
*simple_order=0; // Must do a temp table to sort
5505
*prev_ptr= order; // use this entry
5506
prev_ptr= &order->next;
5510
if (prev_ptr == &first_order) // Nothing to sort/group
5512
return(first_order);
5515
static int return_zero_rows(JOIN *join,
5516
select_result *result,
5520
uint64_t select_options,
5524
if (select_options & SELECT_DESCRIBE)
5526
select_describe(join, false, false, false, info);
5534
for (TableList *table= tables; table; table= table->next_leaf)
5535
table->table->mark_as_null_row(); // All fields are NULL
5536
if (having && having->val_int() == 0)
5539
if (!(result->send_fields(fields, Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF)))
5543
List_iterator_fast<Item> it(fields);
5545
while ((item= it++))
5546
item->no_rows_in_result();
5547
result->send_data(fields);
5549
result->send_eof(); // Should be safe
5551
/* Update results for FOUND_ROWS */
5552
join->session->limit_found_rows= join->session->examined_row_count= 0;
5557
Simplify joins replacing outer joins by inner joins whenever it's
5560
The function, during a retrieval of join_list, eliminates those
5561
outer joins that can be converted into inner join, possibly nested.
5562
It also moves the on expressions for the converted outer joins
5563
and from inner joins to conds.
5564
The function also calculates some attributes for nested joins:
5568
- on_expr_dep_tables
5569
The first two attributes are used to test whether an outer join can
5570
be substituted for an inner join. The third attribute represents the
5571
relation 'to be dependent on' for tables. If table t2 is dependent
5572
on table t1, then in any evaluated execution plan table access to
5573
table t2 must precede access to table t2. This relation is used also
5574
to check whether the query contains invalid cross-references.
5575
The forth attribute is an auxiliary one and is used to calculate
5577
As the attribute dep_tables qualifies possibles orders of tables in the
5578
execution plan, the dependencies required by the straight join
5579
modifiers are reflected in this attribute as well.
5580
The function also removes all braces that can be removed from the join
5581
expression without changing its meaning.
5584
An outer join can be replaced by an inner join if the where condition
5585
or the on expression for an embedding nested join contains a conjunctive
5586
predicate rejecting null values for some attribute of the inner tables.
5590
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5592
the predicate t2.b < 5 rejects nulls.
5593
The query is converted first to:
5595
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5597
then to the equivalent form:
5599
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5603
Similarly the following query:
5605
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5610
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5614
One conversion might trigger another:
5616
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5617
LEFT JOIN t3 ON t3.b=t2.b
5618
WHERE t3 IS NOT NULL =>
5619
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5620
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5621
SELECT * FROM t1, t2, t3
5622
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5625
The function removes all unnecessary braces from the expression
5626
produced by the conversions.
5629
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5631
finally is converted to:
5633
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5638
It also will remove braces from the following queries:
5640
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5641
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5644
The benefit of this simplification procedure is that it might return
5645
a query for which the optimizer can evaluate execution plan with more
5646
join orders. With a left join operation the optimizer does not
5647
consider any plan where one of the inner tables is before some of outer
5651
The function is implemented by a recursive procedure. On the recursive
5652
ascent all attributes are calculated, all outer joins that can be
5653
converted are replaced and then all unnecessary braces are removed.
5654
As join list contains join tables in the reverse order sequential
5655
elimination of outer joins does not require extra recursive calls.
5658
Remove all semi-joins that have are within another semi-join (i.e. have
5659
an "ancestor" semi-join nest)
5662
Here is an example of a join query with invalid cross references:
5664
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5667
@param join reference to the query info
5668
@param join_list list representation of the join to be converted
5669
@param conds conditions to add on expressions for converted joins
5670
@param top true <=> conds is the where condition
5673
- The new condition, if success
5676
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top, bool in_sj)
5679
nested_join_st *nested_join;
5680
TableList *prev_table= 0;
5681
List_iterator<TableList> li(*join_list);
5684
Try to simplify join operations from join_list.
5685
The most outer join operation is checked for conversion first.
5687
while ((table= li++))
5689
table_map used_tables;
5690
table_map not_null_tables= (table_map) 0;
5692
if ((nested_join= table->nested_join))
5695
If the element of join_list is a nested join apply
5696
the procedure to its nested join list first.
5700
Item *expr= table->on_expr;
5702
If an on expression E is attached to the table,
5703
check all null rejected predicates in this expression.
5704
If such a predicate over an attribute belonging to
5705
an inner table of an embedded outer join is found,
5706
the outer join is converted to an inner join and
5707
the corresponding on expression is added to E.
5709
expr= simplify_joins(join, &nested_join->join_list,
5710
expr, false, in_sj || table->sj_on_expr);
5712
if (!table->prep_on_expr || expr != table->on_expr)
5716
table->on_expr= expr;
5717
table->prep_on_expr= expr->copy_andor_structure(join->session);
5720
nested_join->used_tables= (table_map) 0;
5721
nested_join->not_null_tables=(table_map) 0;
5722
conds= simplify_joins(join, &nested_join->join_list, conds, top, in_sj || table->sj_on_expr);
5723
used_tables= nested_join->used_tables;
5724
not_null_tables= nested_join->not_null_tables;
5728
if (!table->prep_on_expr)
5729
table->prep_on_expr= table->on_expr;
5730
used_tables= table->table->map;
5732
not_null_tables= conds->not_null_tables();
5735
if (table->embedding)
5737
table->embedding->nested_join->used_tables|= used_tables;
5738
table->embedding->nested_join->not_null_tables|= not_null_tables;
5741
if (!table->outer_join || (used_tables & not_null_tables))
5744
For some of the inner tables there are conjunctive predicates
5745
that reject nulls => the outer join can be replaced by an inner join.
5747
table->outer_join= 0;
5750
/* Add ON expression to the WHERE or upper-level ON condition. */
5753
conds= and_conds(conds, table->on_expr);
5754
conds->top_level_item();
5755
/* conds is always a new item as both cond and on_expr existed */
5756
assert(!conds->fixed);
5757
conds->fix_fields(join->session, &conds);
5760
conds= table->on_expr;
5761
table->prep_on_expr= table->on_expr= 0;
5769
Only inner tables of non-convertible outer joins
5770
remain with on_expr.
5774
table->dep_tables|= table->on_expr->used_tables();
5775
if (table->embedding)
5777
table->dep_tables&= ~table->embedding->nested_join->used_tables;
5779
Embedding table depends on tables used
5780
in embedded on expressions.
5782
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5785
table->dep_tables&= ~table->table->map;
5790
/* The order of tables is reverse: prev_table follows table */
5791
if (prev_table->straight)
5792
prev_table->dep_tables|= used_tables;
5793
if (prev_table->on_expr)
5795
prev_table->dep_tables|= table->on_expr_dep_tables;
5796
table_map prev_used_tables= prev_table->nested_join ?
5797
prev_table->nested_join->used_tables :
5798
prev_table->table->map;
5800
If on expression contains only references to inner tables
5801
we still make the inner tables dependent on the outer tables.
5802
It would be enough to set dependency only on one outer table
5803
for them. Yet this is really a rare case.
5805
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5806
prev_table->dep_tables|= used_tables;
5813
Flatten nested joins that can be flattened.
5814
no ON expression and not a semi-join => can be flattened.
5817
while ((table= li++))
5819
nested_join= table->nested_join;
5820
if (table->sj_on_expr && !in_sj)
5823
If this is a semi-join that is not contained within another semi-join,
5824
leave it intact (otherwise it is flattened)
5826
join->select_lex->sj_nests.push_back(table);
5828
else if (nested_join && !table->on_expr)
5831
List_iterator<TableList> it(nested_join->join_list);
5834
tbl->embedding= table->embedding;
5835
tbl->join_list= table->join_list;
5837
li.replace(nested_join->join_list);
5843
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5846
uint32_t reclength,offset;
5847
uint32_t field_count;
5848
Session *session= join->session;
5850
entry->reginfo.lock_type=TL_WRITE;
5852
/* Calculate how many saved fields there is in list */
5854
List_iterator<Item> it(fields);
5858
if (item->get_tmp_table_field() && ! item->const_item())
5862
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5863
{ // only const items with no OPTION_FOUND_ROWS
5864
join->unit->select_limit_cnt= 1; // Only send first row
5867
Field **first_field=entry->field+entry->s->fields - field_count;
5868
offset= (field_count ?
5869
entry->field[entry->s->fields - field_count]->
5870
offset(entry->record[0]) : 0);
5871
reclength= entry->s->reclength-offset;
5873
free_io_cache(entry); // Safety
5874
entry->file->info(HA_STATUS_VARIABLE);
5875
if (entry->s->db_type() == heap_engine ||
5876
(!entry->s->blob_fields &&
5877
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->file->stats.records <
5878
session->variables.sortbuff_size)))
5879
error= remove_dup_with_hash_index(join->session, entry,
5880
field_count, first_field,
5883
error= remove_dup_with_compare(join->session, entry, first_field, offset,
5886
free_blobs(first_field);
5891
Function to setup clauses without sum functions.
5893
static int setup_without_group(Session *session,
5894
Item **ref_pointer_array,
5898
List<Item> &all_fields,
5902
bool *hidden_group_fields)
5905
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
5907
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5908
res= setup_conds(session, tables, conds);
5910
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
5911
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5913
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5914
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5915
group, hidden_group_fields);
5916
session->lex->allow_sum_func= save_allow_sum_func;
5921
Calculate the best possible join and initialize the join structure.
5928
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5932
uint32_t i,table_count,const_count,key;
5933
table_map found_const_table_map, all_table_map, found_ref, refs;
5934
key_map const_ref, eq_part;
5935
Table **table_vector;
5936
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
5937
KEYUSE *keyuse,*start_keyuse;
5938
table_map outer_join=0;
5939
SARGABLE_PARAM *sargables= 0;
5940
JOIN_TAB *stat_vector[MAX_TABLES+1];
5942
table_count=join->tables;
5943
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
5944
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
5945
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5946
if (!stat || !stat_ref || !table_vector)
5947
return(1); // Eom /* purecov: inspected */
5949
join->best_ref=stat_vector;
5951
stat_end=stat+table_count;
5952
found_const_table_map= all_table_map=0;
5957
s++, tables= tables->next_leaf, i++)
5959
TableList *embedding= tables->embedding;
5962
s->const_keys.reset();
5963
s->checked_keys.reset();
5964
s->needed_reg.reset();
5965
table_vector[i]=s->table=table=tables->table;
5966
table->pos_in_table_list= tables;
5967
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5970
table->file->print_error(error, MYF(0));
5973
table->quick_keys.reset();
5974
table->reginfo.join_tab=s;
5975
table->reginfo.not_exists_optimize=0;
5976
memset(table->const_key_parts, 0,
5977
sizeof(key_part_map)*table->s->keys);
5978
all_table_map|= table->map;
5980
s->info=0; // For describe
5982
s->dependent= tables->dep_tables;
5983
s->key_dependent= 0;
5984
if (tables->schema_table)
5985
table->file->stats.records= 2;
5986
table->quick_condition_rows= table->file->stats.records;
5988
s->on_expr_ref= &tables->on_expr;
5989
if (*s->on_expr_ref)
5991
/* s is the only inner table of an outer join */
5992
if (!table->file->stats.records && !embedding)
5994
s->dependent= 0; // Ignore LEFT JOIN depend.
5995
set_position(join,const_count++,s,(KEYUSE*) 0);
5998
outer_join|= table->map;
5999
s->embedding_map= 0;
6000
for (;embedding; embedding= embedding->embedding)
6001
s->embedding_map|= embedding->nested_join->nj_map;
6004
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
6006
/* s belongs to a nested join, maybe to several embedded joins */
6007
s->embedding_map= 0;
6010
nested_join_st *nested_join= embedding->nested_join;
6011
s->embedding_map|=nested_join->nj_map;
6012
s->dependent|= embedding->dep_tables;
6013
embedding= embedding->embedding;
6014
outer_join|= nested_join->used_tables;
6019
if ((table->file->stats.records <= 1) && !s->dependent &&
6020
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
6021
!join->no_const_tables)
6023
set_position(join,const_count++,s,(KEYUSE*) 0);
6027
join->outer_join=outer_join;
6029
if (join->outer_join)
6032
Build transitive closure for relation 'to be dependent on'.
6033
This will speed up the plan search for many cases with outer joins,
6034
as well as allow us to catch illegal cross references/
6035
Warshall's algorithm is used to build the transitive closure.
6036
As we use bitmaps to represent the relation the complexity
6037
of the algorithm is O((number of tables)^2).
6039
for (i= 0, s= stat ; i < table_count ; i++, s++)
6041
for (uint32_t j= 0 ; j < table_count ; j++)
6043
table= stat[j].table;
6044
if (s->dependent & table->map)
6045
s->dependent |= table->reginfo.join_tab->dependent;
6048
s->table->maybe_null= 1;
6050
/* Catch illegal cross references for outer joins */
6051
for (i= 0, s= stat ; i < table_count ; i++, s++)
6053
if (s->dependent & s->table->map)
6055
join->tables=0; // Don't use join->table
6056
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
6059
s->key_dependent= s->dependent;
6063
if (conds || outer_join)
6064
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
6065
conds, join->cond_equal,
6066
~outer_join, join->select_lex, &sargables))
6069
/* Read tables with 0 or 1 rows (system tables) */
6070
join->const_table_map= 0;
6072
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
6079
join->const_table_map|=s->table->map;
6080
if ((tmp=join_read_const_table(s, p_pos)))
6083
return(1); // Fatal error
6086
found_const_table_map|= s->table->map;
6089
/* loop until no more const tables are found */
6093
more_const_tables_found:
6098
We only have to loop from stat_vector + const_count as
6099
set_position() will move all const_tables first in stat_vector
6102
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
6107
If equi-join condition by a key is null rejecting and after a
6108
substitution of a const table the key value happens to be null
6109
then we can state that there are no matches for this equi-join.
6111
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
6114
When performing an outer join operation if there are no matching rows
6115
for the single row of the outer table all the inner tables are to be
6116
null complemented and thus considered as constant tables.
6117
Here we apply this consideration to the case of outer join operations
6118
with a single inner table only because the case with nested tables
6119
would require a more thorough analysis.
6120
TODO. Apply single row substitution to null complemented inner tables
6121
for nested outer join operations.
6123
while (keyuse->table == table)
6125
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
6126
keyuse->val->is_null() && keyuse->null_rejecting)
6129
table->mark_as_null_row();
6130
found_const_table_map|= table->map;
6131
join->const_table_map|= table->map;
6132
set_position(join,const_count++,s,(KEYUSE*) 0);
6133
goto more_const_tables_found;
6139
if (s->dependent) // If dependent on some table
6141
// All dep. must be constants
6142
if (s->dependent & ~(found_const_table_map))
6144
if (table->file->stats.records <= 1L &&
6145
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
6146
!table->pos_in_table_list->embedding)
6150
join->const_table_map|=table->map;
6151
set_position(join,const_count++,s,(KEYUSE*) 0);
6152
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
6155
return(1); // Fatal error
6158
found_const_table_map|= table->map;
6162
/* check if table can be read by key or table only uses const refs */
6163
if ((keyuse=s->keyuse))
6166
while (keyuse->table == table)
6168
start_keyuse=keyuse;
6170
s->keys.set(key); // QQ: remove this ?
6177
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
6179
if (!((~found_const_table_map) & keyuse->used_tables))
6180
const_ref.set(keyuse->keypart);
6182
refs|=keyuse->used_tables;
6183
eq_part.set(keyuse->keypart);
6186
} while (keyuse->table == table && keyuse->key == key);
6188
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
6189
!table->pos_in_table_list->embedding)
6191
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
6193
if (const_ref == eq_part)
6194
{ // Found everything for ref.
6198
join->const_table_map|= table->map;
6199
set_position(join,const_count++,s,start_keyuse);
6200
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
6202
if ((tmp=join_read_const_table(s, join->positions+const_count-1)))
6205
return(1); // Fatal error
6208
found_const_table_map|= table->map;
6212
found_ref|= refs; // Table is const if all refs are const
6214
else if (const_ref == eq_part)
6215
s->const_keys.set(key);
6220
} while (join->const_table_map & found_ref && ref_changed);
6223
Update info on indexes that can be used for search lookups as
6224
reading const tables may has added new sargable predicates.
6226
if (const_count && sargables)
6228
for( ; sargables->field ; sargables++)
6230
Field *field= sargables->field;
6231
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
6232
key_map possible_keys= field->key_start;
6233
possible_keys&= field->table->keys_in_use_for_query;
6235
for (uint32_t j=0; j < sargables->num_values; j++)
6236
is_const&= sargables->arg_value[j]->const_item();
6238
join_tab[0].const_keys|= possible_keys;
6242
if (pull_out_semijoin_tables(join))
6245
/* Calc how many (possible) matched records in each table */
6247
for (s=stat ; s < stat_end ; s++)
6249
if (s->type == JT_SYSTEM || s->type == JT_CONST)
6251
/* Only one matching row */
6252
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
6255
/* Approximate found rows and time to read them */
6256
s->found_records=s->records=s->table->file->stats.records;
6257
s->read_time=(ha_rows) s->table->file->scan_time();
6260
Set a max range of how many seeks we can expect when using keys
6261
This is can't be to high as otherwise we are likely to use
6264
s->worst_seeks= cmin((double) s->found_records / 10,
6265
(double) s->read_time*3);
6266
if (s->worst_seeks < 2.0) // Fix for small tables
6270
Add to stat->const_keys those indexes for which all group fields or
6271
all select distinct fields participate in one index.
6273
add_group_and_distinct_keys(join, s);
6275
if (s->const_keys.any() &&
6276
!s->table->pos_in_table_list->embedding)
6280
select= make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
6283
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
6284
s->quick=select->quick;
6285
s->needed_reg=select->needed_reg;
6287
if (records == 0 && s->table->reginfo.impossible_range)
6290
Impossible WHERE or ON expression
6291
In case of ON, we mark that the we match one empty NULL row.
6292
In case of WHERE, don't set found_const_table_map to get the
6293
caller to abort with a zero row result.
6295
join->const_table_map|= s->table->map;
6296
set_position(join,const_count++,s,(KEYUSE*) 0);
6298
if (*s->on_expr_ref)
6300
/* Generate empty row */
6301
s->info= "Impossible ON condition";
6302
found_const_table_map|= s->table->map;
6304
s->table->mark_as_null_row(); // All fields are NULL
6307
if (records != HA_POS_ERROR)
6309
s->found_records=records;
6310
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
6316
join->join_tab=stat;
6317
join->map2table=stat_ref;
6318
join->table= join->all_tables=table_vector;
6319
join->const_tables=const_count;
6320
join->found_const_table_map=found_const_table_map;
6322
/* Find an optimal join order of the non-constant tables. */
6323
if (join->const_tables != join->tables)
6325
optimize_keyuse(join, keyuse_array);
6326
if (choose_plan(join, all_table_map & ~join->const_table_map))
6331
memcpy(join->best_positions, join->positions, sizeof(POSITION)*join->const_tables);
6332
join->best_read= 1.0;
6334
/* Generate an execution plan from the found optimal join order. */
6335
return (join->session->killed || get_best_combination(join));
6339
Assign each nested join structure a bit in nested_join_map.
6341
Assign each nested join structure (except "confluent" ones - those that
6342
embed only one element) a bit in nested_join_map.
6344
@param join Join being processed
6345
@param join_list List of tables
6346
@param first_unused Number of first unused bit in nested_join_map before the
6350
This function is called after simplify_joins(), when there are no
6351
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
6352
we will not run out of bits in nested_join_map.
6355
First unused bit in nested_join_map after the call.
6357
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
6359
List_iterator<TableList> li(*join_list);
6361
while ((table= li++))
6363
nested_join_st *nested_join;
6364
if ((nested_join= table->nested_join))
6367
It is guaranteed by simplify_joins() function that a nested join
6368
that has only one child is either
6369
- a single-table view (the child is the underlying table), or
6370
- a single-table semi-join nest
6372
We don't assign bits to such sj-nests because
6373
1. it is redundant (a "sequence" of one table cannot be interleaved
6375
2. we could run out bits in nested_join_map otherwise.
6377
if (nested_join->join_list.elements != 1)
6379
/* Don't assign bits to sj-nests */
6381
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
6382
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
6387
return(first_unused);
6392
Return table number if there is only one table in sort order
6393
and group and order is compatible, else return 0.
6395
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
6397
table_map map= (table_map) 0;
6400
a= b; // Only one need to be given
6404
for (; a && b; a=a->next,b=b->next)
6406
if (!(*a->item)->eq(*b->item,1))
6407
return (Table *) NULL;
6408
map|= a->item[0]->used_tables();
6410
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
6411
return (Table *) NULL;
6413
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6414
if (map != tables->table->map)
6415
return (Table *) NULL; // More than one table
6416
return tables->table;
6420
Set nested_join_st::counter=0 in all nested joins in passed list.
6422
Recursively set nested_join_st::counter=0 for all nested joins contained in
6423
the passed join_list.
6425
@param join_list List of nested joins to process. It may also contain base
6426
tables which will be ignored.
6428
static void reset_nj_counters(List<TableList> *join_list)
6430
List_iterator<TableList> li(*join_list);
6432
while ((table= li++))
6434
nested_join_st *nested_join;
6435
if ((nested_join= table->nested_join))
6437
nested_join->counter_= 0;
6438
reset_nj_counters(&nested_join->join_list);
6445
Return 1 if second is a subpart of first argument.
6447
If first parts has different direction, change it to second part
6448
(group is sorted like order)
6450
static bool test_if_subpart(order_st *a,order_st *b)
6452
for (; a && b; a=a->next,b=b->next)
6454
if ((*a->item)->eq(*b->item,1))
6463
Nested joins perspective: Remove the last table from the join order.
6465
Remove the last table from the partial join order and update the nested
6466
joins counters and join->cur_embedding_map. It is ok to call this
6467
function for the first table in join order (for which
6468
check_interleaving_with_nj has not been called)
6470
@param last join table to remove, it is assumed to be the last in current
6473
static void restore_prev_nj_state(JOIN_TAB *last)
6475
TableList *last_emb= last->table->pos_in_table_list->embedding;
6476
JOIN *join= last->join;
6479
if (last_emb->on_expr)
6481
if (!(--last_emb->nested_join->counter_))
6482
join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
6483
else if (last_emb->nested_join->join_list.elements-1 ==
6484
last_emb->nested_join->counter_)
6485
join->cur_embedding_map|= last_emb->nested_join->nj_map;
6489
last_emb= last_emb->embedding;
6494
Determine if the set is already ordered for order_st BY, so it can
6495
disable join cache because it will change the ordering of the results.
6496
Code handles sort table that is at any location (not only first after
6497
the const tables) despite the fact that it's currently prohibited.
6498
We must disable join cache if the first non-const table alone is
6499
ordered. If there is a temp table the ordering is done as a last
6500
operation and doesn't prevent join cache usage.
6502
static uint32_t make_join_orderinfo(JOIN *join)
6506
return join->tables;
6508
for (i=join->const_tables ; i < join->tables ; i++)
6510
JOIN_TAB *tab= join->join_tab+i;
6511
Table *table= tab->table;
6512
if ((table == join->sort_by_table &&
6513
(!join->order || join->skip_sort_order)) ||
6514
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
6523
Setup the strategies to eliminate semi-join duplicates.
6526
setup_semijoin_dups_elimination()
6527
join Join to process
6528
options Join options (needed to see if join buffering will be
6530
no_jbuf_after Another bit of information re where join buffering will
6534
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
6537
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
6538
of row combinations)
6539
2. FirstMatch (pick only the 1st matching row combination of inner tables)
6540
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
6541
together and picking the 1st one)
6543
The join order has "duplicate-generating ranges", and every range is
6544
served by one strategy or a combination of FirstMatch with with some
6547
"Duplicate-generating range" is defined as a range within the join order
6548
that contains all of the inner tables of a semi-join. All ranges must be
6549
disjoint, if tables of several semi-joins are interleaved, then the ranges
6550
are joined together, which is equivalent to converting
6551
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
6553
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
6556
Applicability conditions are as follows:
6558
DuplicateWeedout strategy
6559
~~~~~~~~~~~~~~~~~~~~~~~~~
6561
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
6562
+------+ +=========================+ +---+
6565
(1) - Prefix of OuterTables (those that participate in
6566
IN-equality and/or are correlated with subquery) and outer
6567
Noncorrelated Tables.
6568
(2) - The handled range. The range starts with the first sj-inner
6569
table, and covers all sj-inner and outer tables
6570
Within the range, Inner, Outer, outer Noncorrelated tables
6571
may follow in any order.
6572
(3) - The suffix of outer Noncorrelated tables.
6577
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
6578
+------+ +==================+ +---+
6581
(1) - Prefix of outer and non-correlated tables
6582
(2) - The handled range, which may contain only inner and
6583
non-correlated tables.
6584
(3) - The suffix of outer Noncorrelated tables.
6589
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
6590
+--------+ +===========+ +=============+ +------+
6593
(1) - Prefix that may contain any outer tables. The prefix must contain
6594
all the non-trivially correlated outer tables. (non-trivially means
6595
that the correlation is not just through the IN-equality).
6597
(2) - Inner table for which the InsideOut scan is performed.
6599
(3) - The remainder of the duplicate-generating range. It is served by
6600
application of FirstMatch strategy, with the exception that
6601
outer IN-correlated tables are considered to be non-correlated.
6603
(4) - THe suffix of outer and outer non-correlated tables.
6605
If several strategies are applicable, their relative priorities are:
6610
This function walks over the join order and sets up the strategies by
6611
setting appropriate members in join_tab structures.
6615
true Out of memory error
6617
static int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
6619
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
6622
0 - invalid (EOF marker),
6624
2 - Temptable (maybe confluent),
6625
3 - Temptable with join buffering
6628
uint32_t start_idx; /* Left range bound */
6629
uint32_t end_idx; /* Right range bound */
6631
For Temptable strategy: Bitmap of all outer and correlated tables from
6632
all involved join nests.
6634
table_map outer_tables;
6635
} dups_ranges [MAX_TABLES];
6637
TableList *emb_insideout_nest= NULL;
6638
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
6639
tables) whose ranges we're in */
6640
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
6641
table_map range_start_map= 0; /* table_map at current range start */
6642
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
6647
First pass: locate the duplicate-generating ranges and pick the strategies.
6649
for (i=join->const_tables ; i < join->tables ; i++)
6651
JOIN_TAB *tab=join->join_tab+i;
6652
Table *table=tab->table;
6653
cur_map |= table->map;
6655
if (tab->emb_sj_nest) // Encountered an sj-inner table
6659
dups_ranges[cur_range].start_idx= i;
6660
range_start_map= cur_map & ~table->map;
6662
Remember if this is a possible start of range that is covered by
6663
the InsideOut strategy (the reason that it is not covered could
6664
be that it overlaps with anther semi-join's range. we don't
6665
support InsideOut for joined ranges)
6667
if (join->best_positions[i].use_insideout_scan)
6668
emb_insideout_nest= tab->emb_sj_nest;
6671
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
6672
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
6674
if (tab->emb_sj_nest != emb_insideout_nest)
6677
Two different semi-joins interleave. This cannot be handled by
6680
emb_insideout_nest= NULL;
6684
if (emb_sj_map) /* We're in duplicate-generating range */
6686
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
6687
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
6688
i <= no_jbuf_after && !dealing_with_jbuf)
6691
This table uses join buffering, which makes use of FirstMatch or
6692
InsideOut strategies impossible for the current and (we assume)
6693
preceding duplicate-producing ranges.
6694
That is, for the join order:
6696
x x [ x x] x [x x x] x [x x X* x] x
6698
+-----+ +-----+ | join buffering use
6701
we'll have to remove r1 and r2 and use duplicate-elimination
6702
strategy that spans all the tables, starting from the very 1st
6705
dealing_with_jbuf= true;
6706
emb_insideout_nest= false;
6709
Absorb all preceding duplicate-eliminating ranges. Their strategies
6712
for (int prev_range= 0; prev_range < cur_range; prev_range++)
6714
dups_ranges[cur_range].outer_tables |=
6715
dups_ranges[prev_range].outer_tables;
6717
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
6718
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
6723
Check if we are at the end of duplicate-producing range. We are if
6725
1. It's an InsideOut range (which presumes all correlated tables are
6726
in the prefix), and all inner tables are in the join order prefix,
6728
2. It's a DuplicateElimination range (possibly covering several
6729
SJ-nests), and all inner, outer, and correlated tables of all
6730
sj-nests are in the join order prefix.
6732
bool end_of_range= false;
6733
if (emb_insideout_nest &&
6734
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
6736
/* Save that this range is handled with InsideOut: */
6737
dups_ranges[cur_range].strategy= 1;
6740
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
6743
This is a complete range to be handled with either DuplicateWeedout
6746
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
6748
This will hold tables from within the range that need to be put
6749
into the join buffer before we can use the FirstMatch on its tail.
6751
dups_ranges[cur_range].outer_tables= emb_outer_tables &
6758
dups_ranges[cur_range].end_idx= i+1;
6759
emb_sj_map= emb_outer_tables= 0;
6760
emb_insideout_nest= NULL;
6761
dealing_with_jbuf= false;
6762
dups_ranges[++cur_range].strategy= 0;
6767
Session *session= join->session;
6768
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
6770
Second pass: setup the chosen strategies
6772
for (int j= 0; j < cur_range; j++)
6774
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
6776
if (dups_ranges[j].strategy == 1) // InsideOut strategy
6778
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
6781
else // DuplicateWeedout strategy
6783
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
6784
table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
6785
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
6786
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
6787
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
6788
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
6789
JOIN_TAB *last_outer_tab= tab - 1;
6791
Walk through the range and remember
6792
- tables that need their rowids to be put into temptable
6793
- the last outer table
6795
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
6797
if (sj_table_is_included(join, tab))
6799
last_tab->join_tab= tab;
6800
last_tab->rowid_offset= jt_rowid_offset;
6801
jt_rowid_offset += tab->table->file->ref_length;
6802
if (tab->table->maybe_null)
6804
last_tab->null_byte= jt_null_bits / 8;
6805
last_tab->null_bit= jt_null_bits++;
6808
tab->table->prepare_for_position();
6809
tab->rowid_keep_flags= rowid_keep_flags;
6811
weed_cur_map |= tab->table->map;
6812
if (!tab->emb_sj_nest && bitmap_covers(weed_cur_map,
6813
dups_ranges[j].outer_tables))
6814
last_outer_tab= tab;
6817
if (jt_rowid_offset) /* Temptable has at least one rowid */
6819
SJ_TMP_TABLE *sjtbl;
6820
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
6821
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
6822
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
6824
memcpy(sjtbl->tabs, sjtabs, tabs_size);
6825
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
6826
sjtbl->rowid_len= jt_rowid_offset;
6827
sjtbl->null_bits= jt_null_bits;
6828
sjtbl->null_bytes= (jt_null_bits + 7)/8;
6830
*next_sjtbl_ptr= sjtbl;
6831
next_sjtbl_ptr= &(sjtbl->next);
6835
create_duplicate_weedout_tmp_table(session,
6840
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
6841
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
6843
tab= last_outer_tab + 1;
6844
jump_to= last_outer_tab;
6847
/* Create the FirstMatch tail */
6848
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
6850
if (tab->emb_sj_nest)
6851
tab->do_firstmatch= jump_to;
6859
static void cleanup_sj_tmp_tables(JOIN *join)
6861
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
6862
sj_tbl= sj_tbl->next)
6864
if (sj_tbl->tmp_table)
6866
sj_tbl->tmp_table->free_tmp_table(join->session);
6869
join->sj_tmp_tables= NULL;
6873
Create a condition for a const reference and add this to the
6874
currenct select for the table.
6876
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab)
6878
if (!join_tab->ref.key_parts)
6881
Item_cond_and *cond=new Item_cond_and();
6882
Table *table=join_tab->table;
6887
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6889
Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
6891
Item *value=join_tab->ref.items[i];
6892
cond->add(new Item_func_equal(new Item_field(field), value));
6894
if (session->is_fatal_error)
6898
cond->fix_fields(session, (Item**)&cond);
6899
if (join_tab->select)
6901
error=(int) cond->add(join_tab->select->cond);
6902
join_tab->select_cond=join_tab->select->cond=cond;
6904
else if ((join_tab->select= make_select(join_tab->table, 0, 0, cond, 0,
6906
join_tab->select_cond=cond;
6908
return(error ? true : false);
6912
@brief Replaces an expression destructively inside the expression tree of
6915
@note Because of current requirements for semijoin flattening, we do not
6916
need to recurse here, hence this function will only examine the top-level
6917
AND conditions. (see JOIN::prepare, comment above the line
6918
'if (do_materialize)'
6920
@param join The top-level query.
6921
@param old_cond The expression to be replaced.
6922
@param new_cond The expression to be substituted.
6923
@param do_fix_fields If true, Item::fix_fields(Session*, Item**) is called for
6925
@return <code>true</code> if there was an error, <code>false</code> if
6928
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
6929
Item *new_cond, bool do_fix_fields)
6931
if (join->conds == old_cond) {
6932
join->conds= new_cond;
6934
new_cond->fix_fields(join->session, &join->conds);
6938
if (join->conds->type() == Item::COND_ITEM) {
6939
List_iterator<Item> li(*((Item_cond*)join->conds)->argument_list());
6941
while ((item= li++))
6942
if (item == old_cond)
6944
li.replace(new_cond);
6946
new_cond->fix_fields(join->session, li.ref());
6955
Pull tables out of semi-join nests, if possible
6958
pull_out_semijoin_tables()
6959
join The join where to do the semi-join flattening
6962
Try to pull tables out of semi-join nests.
6965
When this function is called, the join may have several semi-join nests
6966
(possibly within different semi-join nests), but it is guaranteed that
6967
one semi-join nest does not contain another.
6970
A table can be pulled out of the semi-join nest if
6971
- It is a constant table
6975
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
6977
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
6978
* Semi-join nests TableList::sj_inner_tables
6980
This operation is (and should be) performed at each PS execution since
6981
tables may become/cease to be constant across PS reexecutions.
6985
1 - Out of memory error
6987
static int pull_out_semijoin_tables(JOIN *join)
6990
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
6992
/* Try pulling out of the each of the semi-joins */
6993
while ((sj_nest= sj_list_it++))
6995
/* Action #1: Mark the constant tables to be pulled out */
6996
table_map pulled_tables= 0;
6998
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
7000
while ((tbl= child_li++))
7004
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
7005
if (tbl->table->map & join->const_table_map)
7007
pulled_tables |= tbl->table->map;
7013
Action #2: Find which tables we can pull out based on
7014
update_ref_and_keys() data. Note that pulling one table out can allow
7015
us to pull out some other tables too.
7017
bool pulled_a_table;
7020
pulled_a_table= false;
7022
while ((tbl= child_li++))
7024
if (tbl->table && !(pulled_tables & tbl->table->map))
7026
if (find_eq_ref_candidate(tbl->table,
7027
sj_nest->nested_join->used_tables &
7030
pulled_a_table= true;
7031
pulled_tables |= tbl->table->map;
7035
} while (pulled_a_table);
7038
if ((sj_nest)->nested_join->used_tables == pulled_tables)
7040
(sj_nest)->sj_inner_tables= 0;
7041
while ((tbl= child_li++))
7044
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
7049
/* Record the bitmap of inner tables, mark the inner tables */
7050
table_map inner_tables=(sj_nest)->nested_join->used_tables &
7052
(sj_nest)->sj_inner_tables= inner_tables;
7053
while ((tbl= child_li++))
7057
if (inner_tables & tbl->table->map)
7058
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
7060
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
7069
SemiJoinDuplicateElimination: Weed out duplicate row combinations
7072
do_sj_dups_weedout()
7076
1 The row combination is a duplicate (discard it)
7077
0 The row combination is not a duplicate (continue)
7079
static int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)
7082
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
7083
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
7084
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
7085
unsigned char *nulls_ptr= ptr;
7087
/* Put the the rowids tuple into table->record[0]: */
7089
// 1. Store the length
7090
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
7092
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
7097
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
7101
// 2. Zero the null bytes
7102
if (sjtbl->null_bytes)
7104
memset(ptr, 0, sjtbl->null_bytes);
7105
ptr += sjtbl->null_bytes;
7108
// 3. Put the rowids
7109
for (uint32_t i=0; tab != tab_end; tab++, i++)
7111
handler *h= tab->join_tab->table->file;
7112
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
7114
/* It's a NULL-complemented row */
7115
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
7116
memset(ptr + tab->rowid_offset, 0, h->ref_length);
7120
/* Copy the rowid value */
7121
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
7122
h->position(tab->join_tab->table->record[0]);
7123
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
7127
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
7130
/* create_myisam_from_heap will generate error if needed */
7131
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
7132
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
7133
&sjtbl->recinfo, error, 1))
7135
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
7141
static void free_blobs(Field **ptr)
7143
for (; *ptr ; ptr++)
7145
if ((*ptr)->flags & BLOB_FLAG)
7146
((Field_blob *) (*ptr))->free();
7150
static bool bitmap_covers(const table_map x, const table_map y)
7152
return !test(y & ~x);
7156
Check if the table's rowid is included in the temptable
7159
sj_table_is_included()
7161
join_tab The table to be checked
7164
SemiJoinDuplicateElimination: check the table's rowid should be included
7165
in the temptable. This is so if
7167
1. The table is not embedded within some semi-join nest
7168
2. The has been pulled out of a semi-join nest, or
7170
3. The table is functionally dependent on some previous table
7172
[4. This is also true for constant tables that can't be
7173
NULL-complemented but this function is not called for such tables]
7176
true - Include table's rowid
7179
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
7181
if (join_tab->emb_sj_nest)
7184
/* Check if this table is functionally dependent on the tables that
7185
are within the same outer join nest
7187
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
7188
if (join_tab->type == JT_EQ_REF)
7190
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
7192
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
7194
JOIN_TAB *ref_tab= join->join_tab + idx;
7195
if (embedding == ref_tab->table->pos_in_table_list->embedding)
7198
/* Ok, functionally dependent */
7201
/* Not functionally dependent => need to include*/
7206
@} (end of group Query_Optimizer)
added
removed
drizzled/join.cc
