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/table_map_iterator.h"
32
#include "drizzled/item/cache.h"
33
#include "drizzled/item/cmpfunc.h"
34
#include "drizzled/item/copy_string.h"
35
#include "drizzled/item/uint.h"
36
#include "drizzled/cached_item.h"
37
#include "drizzled/sql_base.h"
38
#include "drizzled/sql_select.h" /* include join.h */
39
#include "drizzled/lock.h"
40
#include "drizzled/nested_join.h"
41
#include "drizzled/join.h"
42
#include "drizzled/join_cache.h"
43
#include "drizzled/show.h"
44
#include "drizzled/field/blob.h"
45
#include "drizzled/optimizer/position.h"
46
#include "drizzled/optimizer/sargable_param.h"
47
#include "mysys/my_bit.h"
52
using namespace drizzled;
54
/** Declarations of static functions used in this source file. */
55
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
56
static void calc_group_buffer(JOIN *join,order_st *group);
57
static bool alloc_group_fields(JOIN *join,order_st *group);
58
static uint32_t cache_record_length(JOIN *join, uint32_t index);
59
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
60
static bool get_best_combination(JOIN *join);
61
static void set_position(JOIN *join,uint32_t index,JoinTable *table,KeyUse *key);
62
static bool choose_plan(JOIN *join,table_map join_tables);
63
static void best_access_path(JOIN *join, JoinTable *s,
65
table_map remaining_tables,
69
static void optimize_straight_join(JOIN *join, table_map join_tables);
70
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
71
static bool best_extension_by_limited_search(JOIN *join,
72
table_map remaining_tables,
77
uint32_t prune_level);
78
static uint32_t determine_search_depth(JOIN* join);
79
static bool make_simple_join(JOIN *join,Table *tmp_table);
80
static void make_outerjoin_info(JOIN *join);
81
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
82
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
83
static void update_depend_map(JOIN *join);
84
static void update_depend_map(JOIN *join, order_st *order);
85
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
86
static int return_zero_rows(JOIN *join,
91
uint64_t select_options,
94
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
95
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
96
static int setup_without_group(Session *session,
97
Item **ref_pointer_array,
101
List<Item> &all_fields,
105
bool *hidden_group_fields);
106
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
107
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
108
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
109
static void reset_nj_counters(List<TableList> *join_list);
110
static bool test_if_subpart(order_st *a,order_st *b);
111
static void restore_prev_nj_state(JoinTable *last);
112
static uint32_t make_join_orderinfo(JOIN *join);
113
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
114
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
117
Prepare of whole select (including sub queries in future).
120
Add check of calculation of GROUP functions and fields:
121
SELECT COUNT(*)+table.col1 from table1;
128
int JOIN::prepare(Item ***rref_pointer_array,
129
TableList *tables_init,
133
order_st *order_init,
134
order_st *group_init,
136
Select_Lex *select_lex_arg,
137
Select_Lex_Unit *unit_arg)
139
// to prevent double initialization on EXPLAIN
145
group_list= group_init;
147
tables_list= tables_init;
148
select_lex= select_lex_arg;
149
select_lex->join= this;
150
join_list= &select_lex->top_join_list;
151
union_part= unit_arg->is_union();
153
session->lex->current_select->is_item_list_lookup= 1;
155
If we have already executed SELECT, then it have not sense to prevent
156
its table from update (see unique_table())
158
if (session->derived_tables_processing)
159
select_lex->exclude_from_table_unique_test= true;
161
/* Check that all tables, fields, conds and order are ok */
163
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
164
setup_tables_and_check_access(session, &select_lex->context, join_list,
165
tables_list, &select_lex->leaf_tables,
169
TableList *table_ptr;
170
for (table_ptr= select_lex->leaf_tables;
172
table_ptr= table_ptr->next_leaf)
175
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
176
select_lex->setup_ref_array(session, og_num) ||
177
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
179
setup_without_group(session, (*rref_pointer_array), tables_list,
180
select_lex->leaf_tables, fields_list,
181
all_fields, &conds, order, group_list,
182
&hidden_group_fields))
183
return(-1); /* purecov: inspected */
185
ref_pointer_array= *rref_pointer_array;
189
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
190
session->where="having clause";
191
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
192
select_lex->having_fix_field= 1;
193
bool having_fix_rc= (!having->fixed &&
194
(having->fix_fields(session, &having) ||
195
having->check_cols(1)));
196
select_lex->having_fix_field= 0;
197
if (having_fix_rc || session->is_error())
198
return(-1); /* purecov: inspected */
199
session->lex->allow_sum_func= save_allow_sum_func;
203
Item_subselect *subselect;
204
Item_in_subselect *in_subs= NULL;
206
Are we in a subquery predicate?
207
TODO: the block below will be executed for every PS execution without need.
209
if ((subselect= select_lex->master_unit()->item))
211
if (subselect->substype() == Item_subselect::IN_SUBS)
212
in_subs= (Item_in_subselect*)subselect;
215
bool do_materialize= !test(session->variables.optimizer_switch &
216
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
218
Check if the subquery predicate can be executed via materialization.
219
The required conditions are:
220
1. Subquery predicate is an IN/=ANY subq predicate
221
2. Subquery is a single SELECT (not a UNION)
222
3. Subquery is not a table-less query. In this case there is no
223
point in materializing.
224
4. Subquery predicate is a top-level predicate
225
(this implies it is not negated)
226
TODO: this is a limitation that should be lifeted once we
227
implement correct NULL semantics (WL#3830)
228
5. Subquery is non-correlated
230
This is an overly restrictive condition. It can be extended to:
231
(Subquery is non-correlated ||
232
Subquery is correlated to any query outer to IN predicate ||
233
(Subquery is correlated to the immediate outer query &&
234
Subquery !contains {GROUP BY, order_st BY [LIMIT],
235
aggregate functions) && subquery predicate is not under "NOT IN"))
236
6. No execution method was already chosen (by a prepared statement).
238
(*) The subquery must be part of a SELECT statement. The current
239
condition also excludes multi-table update statements.
241
We have to determine whether we will perform subquery materialization
242
before calling the IN=>EXISTS transformation, so that we know whether to
243
perform the whole transformation or only that part of it which wraps
244
Item_in_subselect in an Item_in_optimizer.
246
if (do_materialize &&
248
!select_lex->master_unit()->first_select()->next_select() && // 2
249
select_lex->master_unit()->first_select()->leaf_tables && // 3
250
session->lex->sql_command == SQLCOM_SELECT) // *
252
if (in_subs->is_top_level_item() && // 4
253
!in_subs->is_correlated && // 5
254
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
255
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
258
Item_subselect::trans_res trans_res;
259
if ((trans_res= subselect->select_transformer(this)) !=
260
Item_subselect::RES_OK)
262
return((trans_res == Item_subselect::RES_ERROR));
271
for (ord= order; ord; ord= ord->next)
273
Item *item= *ord->item;
274
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
275
item->split_sum_func(session, ref_pointer_array, all_fields);
279
if (having && having->with_sum_func)
280
having->split_sum_func(session, ref_pointer_array, all_fields,
282
if (select_lex->inner_sum_func_list)
284
Item_sum *end=select_lex->inner_sum_func_list;
285
Item_sum *item_sum= end;
288
item_sum= item_sum->next;
289
item_sum->split_sum_func(session, ref_pointer_array,
290
all_fields, item_sum->ref_by, false);
291
} while (item_sum != end);
294
if (select_lex->inner_refs_list.elements &&
295
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
299
Check if there are references to un-aggregated columns when computing
300
aggregate functions with implicit grouping (there is no GROUP BY).
302
MODE_ONLY_FULL_GROUP_BY is enabled here by default
305
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
306
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
308
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
309
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
313
/* Caclulate the number of groups */
315
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
320
goto err; /* purecov: inspected */
322
if (result && result->prepare(fields_list, unit_arg))
323
goto err; /* purecov: inspected */
325
/* Init join struct */
326
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
327
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
328
this->group= group_list != 0;
331
#ifdef RESTRICTED_GROUP
332
if (sum_func_count && !group_list && (func_count || field_count))
334
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
338
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
340
if (alloc_func_list())
346
return(-1); /* purecov: inspected */
350
Remove the predicates pushed down into the subquery
353
JOIN::remove_subq_pushed_predicates()
354
where IN Must be NULL
355
OUT The remaining WHERE condition, or NULL
358
Given that this join will be executed using (unique|index)_subquery,
359
without "checking NULL", remove the predicates that were pushed down
362
If the subquery compares scalar values, we can remove the condition that
363
was wrapped into trig_cond (it will be checked when needed by the subquery
366
If the subquery compares row values, we need to keep the wrapped
367
equalities in the WHERE clause: when the left (outer) tuple has both NULL
368
and non-NULL values, we'll do a full table scan and will rely on the
369
equalities corresponding to non-NULL parts of left tuple to filter out
370
non-matching records.
372
TODO: We can remove the equalities that will be guaranteed to be true by the
373
fact that subquery engine will be using index lookup. This must be done only
374
for cases where there are no conversion errors of significance, e.g. 257
375
that is searched in a byte. But this requires homogenization of the return
376
codes of all Field*::store() methods.
378
void JOIN::remove_subq_pushed_predicates(Item **where)
380
if (conds->type() == Item::FUNC_ITEM &&
381
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
382
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
383
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
384
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
385
((Item_func *)conds)->arguments()[0]))
393
global select optimisation.
396
error code saved in field 'error'
405
// to prevent double initialization on EXPLAIN
410
session->set_proc_info("optimizing");
411
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
412
unit->select_limit_cnt);
413
/* select_limit is used to decide if we are likely to scan the whole table */
414
select_limit= unit->select_limit_cnt;
415
if (having || (select_options & OPTION_FOUND_ROWS))
416
select_limit= HA_POS_ERROR;
417
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
418
// Ignore errors of execution if option IGNORE present
419
if (session->lex->ignore)
420
session->lex->current_select->no_error= 1;
422
#ifdef HAVE_REF_TO_FIELDS // Not done yet
423
/* Add HAVING to WHERE if possible */
424
if (having && !group_list && !sum_func_count)
431
else if ((conds=new Item_cond_and(conds,having)))
434
Item_cond_and can't be fixed after creation, so we do not check
437
conds->fix_fields(session, &conds);
438
conds->change_ref_to_fields(session, tables_list);
439
conds->top_level_item();
445
/* Convert all outer joins to inner joins if possible */
446
conds= simplify_joins(this, join_list, conds, true);
447
build_bitmap_for_nested_joins(join_list, 0);
449
conds= optimize_cond(this, conds, join_list, &cond_value);
450
if (session->is_error())
457
having= optimize_cond(this, having, join_list, &having_value);
458
if (session->is_error())
463
if (select_lex->where)
464
select_lex->cond_value= cond_value;
465
if (select_lex->having)
466
select_lex->having_value= having_value;
468
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
469
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
470
{ /* Impossible cond */
471
zero_result_cause= having_value == Item::COND_FALSE ?
472
"Impossible HAVING" : "Impossible WHERE";
478
/* Optimize count(*), cmin() and cmax() */
479
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
483
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
484
to the WHERE conditions,
485
or 1 if all items were resolved,
486
or 0, or an error number HA_ERR_...
488
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
490
if (res == HA_ERR_KEY_NOT_FOUND)
492
zero_result_cause= "No matching min/max row";
503
zero_result_cause= "No matching min/max row";
507
zero_result_cause= "Select tables optimized away";
508
tables_list= 0; // All tables resolved
510
Extract all table-independent conditions and replace the WHERE
511
clause with them. All other conditions were computed by opt_sum_query
512
and the MIN/MAX/COUNT function(s) have been replaced by constants,
513
so there is no need to compute the whole WHERE clause again.
514
Notice that make_cond_for_table() will always succeed to remove all
515
computed conditions, because opt_sum_query() is applicable only to
517
Preserve conditions for EXPLAIN.
519
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
521
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
522
conds= table_independent_conds;
531
error= -1; // Error is sent to client
532
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
534
/* Calculate how to do the join */
535
session->set_proc_info("statistics");
536
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
537
session->is_fatal_error)
542
/* Remove distinct if only const tables */
543
select_distinct= select_distinct && (const_tables != tables);
544
session->set_proc_info("preparing");
545
if (result->initialize_tables(this))
547
return 1; // error == -1
549
if (const_table_map != found_const_table_map &&
550
!(select_options & SELECT_DESCRIBE) &&
552
!(conds->used_tables() & RAND_TABLE_BIT) ||
553
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
555
zero_result_cause= "no matching row in const table";
559
if (!(session->options & OPTION_BIG_SELECTS) &&
560
best_read > (double) session->variables.max_join_size &&
561
!(select_options & SELECT_DESCRIBE))
562
{ /* purecov: inspected */
563
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
567
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
568
mysql_unlock_some_tables(session, table, const_tables);
569
if (!conds && outer_join)
571
/* Handle the case where we have an OUTER JOIN without a WHERE */
572
conds=new Item_int((int64_t) 1,1); // Always true
574
select= make_select(*table, const_table_map,
575
const_table_map, conds, 1, &error);
577
{ /* purecov: inspected */
578
error= -1; /* purecov: inspected */
582
reset_nj_counters(join_list);
583
make_outerjoin_info(this);
586
Among the equal fields belonging to the same multiple equality
587
choose the one that is to be retrieved first and substitute
588
all references to these in where condition for a reference for
593
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
594
conds->update_used_tables();
598
Permorm the the optimization on fields evaluation mentioned above
599
for all on expressions.
601
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
603
if (*tab->on_expr_ref)
605
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
608
(*tab->on_expr_ref)->update_used_tables();
612
if (conds &&!outer_join && const_table_map != found_const_table_map &&
613
(select_options & SELECT_DESCRIBE) &&
614
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
616
conds=new Item_int((int64_t) 0,1); // Always false
618
if (make_join_select(this, select, conds))
621
"Impossible WHERE noticed after reading const tables";
622
return(0); // error == 0
625
error= -1; /* if goto err */
627
/* Optimize distinct away if possible */
629
order_st *org_order= order;
630
order= remove_constants(this, order,conds,1, &simple_order);
631
if (session->is_error())
638
If we are using order_st BY NULL or order_st BY const_expression,
639
return result in any order (even if we are using a GROUP BY)
641
if (!order && org_order)
645
Check if we can optimize away GROUP BY/DISTINCT.
646
We can do that if there are no aggregate functions, the
647
fields in DISTINCT clause (if present) and/or columns in GROUP BY
648
(if present) contain direct references to all key parts of
649
an unique index (in whatever order) and if the key parts of the
650
unique index cannot contain NULLs.
651
Note that the unique keys for DISTINCT and GROUP BY should not
652
be the same (as long as they are unique).
654
The FROM clause must contain a single non-constant table.
656
if (tables - const_tables == 1 && (group_list || select_distinct) &&
657
!tmp_table_param.sum_func_count &&
658
(!join_tab[const_tables].select ||
659
!join_tab[const_tables].select->quick ||
660
join_tab[const_tables].select->quick->get_type() !=
661
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
663
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
666
We have found that grouping can be removed since groups correspond to
667
only one row anyway, but we still have to guarantee correct result
668
order. The line below effectively rewrites the query from GROUP BY
669
<fields> to order_st BY <fields>. There are two exceptions:
670
- if skip_sort_order is set (see above), then we can simply skip
672
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
673
with the GROUP BY ones, i.e. either one is a prefix of another.
674
We only check if the order_st BY is a prefix of GROUP BY. In this case
675
test_if_subpart() copies the ASC/DESC attributes from the original
677
If GROUP BY is a prefix of order_st BY, then it is safe to leave
680
if (!order || test_if_subpart(group_list, order))
681
order= skip_sort_order ? 0 : group_list;
683
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
684
rewritten to IGNORE INDEX FOR order_st BY(fields).
686
join_tab->table->keys_in_use_for_order_by=
687
join_tab->table->keys_in_use_for_group_by;
691
if (select_distinct &&
692
list_contains_unique_index(join_tab[const_tables].table,
693
find_field_in_item_list,
694
(void *) &fields_list))
699
if (group_list || tmp_table_param.sum_func_count)
701
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
704
else if (select_distinct && tables - const_tables == 1)
707
We are only using one table. In this case we change DISTINCT to a
709
- The GROUP BY can be done through indexes (no sort) and the order_st
710
BY only uses selected fields.
711
(In this case we can later optimize away GROUP BY and order_st BY)
712
- We are scanning the whole table without LIMIT
714
- We are using CALC_FOUND_ROWS
715
- We are using an order_st BY that can't be optimized away.
717
We don't want to use this optimization when we are using LIMIT
718
because in this case we can just create a temporary table that
719
holds LIMIT rows and stop when this table is full.
721
JoinTable *tab= &join_tab[const_tables];
722
bool all_order_fields_used;
724
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
725
&tab->table->keys_in_use_for_order_by);
726
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
727
order, fields_list, all_fields,
728
&all_order_fields_used)))
730
bool skip_group= (skip_sort_order &&
731
test_if_skip_sort_order(tab, group_list, select_limit, 1,
732
&tab->table->keys_in_use_for_group_by) != 0);
733
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
734
if ((skip_group && all_order_fields_used) ||
735
select_limit == HA_POS_ERROR ||
736
(order && !skip_sort_order))
738
/* Change DISTINCT to GROUP BY */
741
if (all_order_fields_used)
743
if (order && skip_sort_order)
746
Force MySQL to read the table in sorted order to get result in
749
tmp_table_param.quick_group=0;
753
group=1; // For end_write_group
758
else if (session->is_fatal_error) // End of memory
763
order_st *old_group_list;
764
group_list= remove_constants(this, (old_group_list= group_list), conds,
765
rollup.state == ROLLUP::STATE_NONE,
767
if (session->is_error())
772
if (old_group_list && !group_list)
775
if (!group_list && group)
777
order=0; // The output has only one row
779
select_distinct= 0; // No need in distinct for 1 row
780
group_optimized_away= 1;
783
calc_group_buffer(this, group_list);
784
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
786
if (test_if_subpart(group_list, order) ||
787
(!group_list && tmp_table_param.sum_func_count))
790
// Can't use sort on head table if using row cache
800
Check if we need to create a temporary table.
801
This has to be done if all tables are not already read (const tables)
802
and one of the following conditions holds:
803
- We are using DISTINCT (simple distinct's are already optimized away)
804
- We are using an order_st BY or GROUP BY on fields not in the first table
805
- We are using different order_st BY and GROUP BY orders
806
- The user wants us to buffer the result.
808
need_tmp= (const_tables != tables &&
809
((select_distinct || !simple_order || !simple_group) ||
810
(group_list && order) ||
811
test(select_options & OPTION_BUFFER_RESULT)));
813
uint32_t no_jbuf_after= make_join_orderinfo(this);
814
uint64_t select_opts_for_readinfo=
815
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
817
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
818
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
821
/* Create all structures needed for materialized subquery execution. */
822
if (setup_subquery_materialization())
826
is this simple IN subquery?
828
if (!group_list && !order &&
829
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
830
tables == 1 && conds &&
836
if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
838
remove_subq_pushed_predicates(&where);
839
save_index_subquery_explain_info(join_tab, where);
840
join_tab[0].type= AM_UNIQUE_SUBQUERY;
844
subselect_uniquesubquery_engine(session,
849
else if (join_tab[0].type == AM_REF &&
850
join_tab[0].ref.items[0]->name == in_left_expr_name)
852
remove_subq_pushed_predicates(&where);
853
save_index_subquery_explain_info(join_tab, where);
854
join_tab[0].type= AM_INDEX_SUBQUERY;
858
subselect_indexsubquery_engine(session,
866
else if (join_tab[0].type == AM_REF_OR_NULL &&
867
join_tab[0].ref.items[0]->name == in_left_expr_name &&
868
having->name == in_having_cond)
870
join_tab[0].type= AM_INDEX_SUBQUERY;
872
conds= remove_additional_cond(conds);
873
save_index_subquery_explain_info(join_tab, conds);
875
change_engine(new subselect_indexsubquery_engine(session,
885
Need to tell handlers that to play it safe, it should fetch all
886
columns of the primary key of the tables: this is because MySQL may
887
build row pointers for the rows, and for all columns of the primary key
888
the read set has not necessarily been set by the server code.
890
if (need_tmp || select_distinct || group_list || order)
892
for (uint32_t i = const_tables; i < tables; i++)
893
join_tab[i].table->prepare_for_position();
896
if (const_tables != tables)
899
Because filesort always does a full table scan or a quick range scan
900
we must add the removed reference to the select for the table.
901
We only need to do this when we have a simple_order or simple_group
902
as in other cases the join is done before the sort.
904
if ((order || group_list) &&
905
(join_tab[const_tables].type != AM_ALL) &&
906
(join_tab[const_tables].type != AM_REF_OR_NULL) &&
907
((order && simple_order) || (group_list && simple_group)))
909
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
914
if (!(select_options & SELECT_BIG_RESULT) &&
917
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
918
unit->select_limit_cnt, 0,
919
&join_tab[const_tables].table->
920
keys_in_use_for_group_by))) ||
922
tmp_table_param.quick_group)
924
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
929
Force using of tmp table if sorting by a SP or UDF function due to
930
their expensive and probably non-deterministic nature.
932
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
934
Item *item= *tmp_order->item;
935
if (item->is_expensive())
937
/* Force tmp table without sort */
938
need_tmp=1; simple_order=simple_group=0;
946
if (select_options & SELECT_DESCRIBE)
954
The loose index scan access method guarantees that all grouping or
955
duplicate row elimination (for distinct) is already performed
956
during data retrieval, and that all MIN/MAX functions are already
957
computed for each group. Thus all MIN/MAX functions should be
958
treated as regular functions, and there is no need to perform
959
grouping in the main execution loop.
960
Notice that currently loose index scan is applicable only for
961
single table queries, thus it is sufficient to test only the first
962
join_tab element of the plan for its access method.
964
if (join_tab->is_using_loose_index_scan())
965
tmp_table_param.precomputed_group_by= true;
967
/* Create a tmp table if distinct or if the sort is too complicated */
970
session->set_proc_info("Creating tmp table");
972
init_items_ref_array();
974
tmp_table_param.hidden_field_count= (all_fields.elements -
975
fields_list.elements);
976
order_st *tmp_group= ((!simple_group &&
977
! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
980
Pushing LIMIT to the temporary table creation is not applicable
981
when there is order_st BY or GROUP BY or there is no GROUP BY, but
982
there are aggregate functions, because in all these cases we need
985
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
987
!session->lex->current_select->with_sum_func) ?
988
select_limit : HA_POS_ERROR;
990
if (!(exec_tmp_table1=
991
create_tmp_table(session, &tmp_table_param, all_fields,
993
group_list ? 0 : select_distinct,
994
group_list && simple_group,
1003
We don't have to store rows in temp table that doesn't match HAVING if:
1004
- we are sorting the table and writing complete group rows to the
1006
- We are using DISTINCT without resolving the distinct as a GROUP BY
1009
If having is not handled here, it will be checked before the row
1010
is sent to the client.
1012
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1015
/* if group or order on first table, sort first */
1016
if (group_list && simple_group)
1018
session->set_proc_info("Sorting for group");
1019
if (create_sort_index(session, this, group_list,
1020
HA_POS_ERROR, HA_POS_ERROR, false) ||
1021
alloc_group_fields(this, group_list) ||
1022
make_sum_func_list(all_fields, fields_list, 1) ||
1023
setup_sum_funcs(session, sum_funcs))
1031
if (make_sum_func_list(all_fields, fields_list, 0) ||
1032
setup_sum_funcs(session, sum_funcs))
1037
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1039
session->set_proc_info("Sorting for order");
1040
if (create_sort_index(session, this, order,
1041
HA_POS_ERROR, HA_POS_ERROR, true))
1050
Optimize distinct when used on some of the tables
1051
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1052
In this case we can stop scanning t2 when we have found one t1.a
1055
if (exec_tmp_table1->distinct)
1057
table_map used_tables= session->used_tables;
1058
JoinTable *last_join_tab= join_tab+tables-1;
1061
if (used_tables & last_join_tab->table->map)
1063
last_join_tab->not_used_in_distinct=1;
1064
} while (last_join_tab-- != join_tab);
1065
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1066
if (order && skip_sort_order)
1068
/* Should always succeed */
1069
if (test_if_skip_sort_order(&join_tab[const_tables],
1070
order, unit->select_limit_cnt, 0,
1071
&join_tab[const_tables].table->
1072
keys_in_use_for_order_by))
1078
If this join belongs to an uncacheable subquery save
1081
if (select_lex->uncacheable && !is_top_level_join() &&
1082
init_save_join_tab())
1083
return(-1); /* purecov: inspected */
1091
Restore values in temporary join.
1093
void JOIN::restore_tmp()
1095
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1100
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1101
select_lex->offset_limit->val_uint() :
1106
if (exec_tmp_table1)
1108
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1109
exec_tmp_table1->file->ha_delete_all_rows();
1110
exec_tmp_table1->free_io_cache();
1111
exec_tmp_table1->filesort_free_buffers();
1113
if (exec_tmp_table2)
1115
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1116
exec_tmp_table2->file->ha_delete_all_rows();
1117
exec_tmp_table2->free_io_cache();
1118
exec_tmp_table2->filesort_free_buffers();
1121
set_items_ref_array(items0);
1124
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1129
/* Reset of sum functions */
1132
Item_sum *func, **func_ptr= sum_funcs;
1133
while ((func= *(func_ptr++)))
1141
@brief Save the original join layout
1143
@details Saves the original join layout so it can be reused in
1144
re-execution and for EXPLAIN.
1146
@return Operation status
1148
@retval 1 error occurred.
1150
bool JOIN::init_save_join_tab()
1152
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
1153
return 1; /* purecov: inspected */
1154
error= 0; // Ensure that tmp_join.error= 0
1159
bool JOIN::save_join_tab()
1161
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1163
if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1164
sizeof(JoinTable) * tables)))
1174
Note, that create_sort_index calls test_if_skip_sort_order and may
1175
finally replace sorting with index scan if there is a LIMIT clause in
1176
the query. It's never shown in EXPLAIN!
1179
When can we have here session->net.report_error not zero?
1183
List<Item> *columns_list= &fields_list;
1186
session->set_proc_info("executing");
1189
if (!tables_list && (tables || !select_lex->with_sum_func))
1191
/* Only test of functions */
1192
if (select_options & SELECT_DESCRIBE)
1193
select_describe(this, false, false, false, (zero_result_cause?zero_result_cause:"No tables used"));
1196
result->send_fields(*columns_list);
1198
We have to test for 'conds' here as the WHERE may not be constant
1199
even if we don't have any tables for prepared statements or if
1200
conds uses something like 'rand()'.
1202
if (cond_value != Item::COND_FALSE &&
1203
(!conds || conds->val_int()) &&
1204
(!having || having->val_int()))
1206
if (do_send_rows && result->send_data(fields_list))
1210
error= (int) result->send_eof();
1211
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1216
error= (int) result->send_eof();
1220
/* Single select (without union) always returns 0 or 1 row */
1221
session->limit_found_rows= send_records;
1222
session->examined_row_count= 0;
1226
Don't reset the found rows count if there're no tables as
1227
FOUND_ROWS() may be called. Never reset the examined row count here.
1228
It must be accumulated from all join iterations of all join parts.
1231
session->limit_found_rows= 0;
1233
if (zero_result_cause)
1235
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1237
send_row_on_empty_set(),
1244
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) && get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
1247
if (select_options & SELECT_DESCRIBE)
1250
Check if we managed to optimize order_st BY away and don't use temporary
1251
table to resolve order_st BY: in that case, we only may need to do
1252
filesort for GROUP BY.
1254
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1256
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1258
simple_order= simple_group;
1261
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1263
if (const_tables == tables
1264
|| ((simple_order || skip_sort_order)
1265
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1269
select_describe(this, need_tmp, order != 0 && !skip_sort_order, select_distinct, !tables ? "No tables used" : NULL);
1273
JOIN *curr_join= this;
1274
List<Item> *curr_all_fields= &all_fields;
1275
List<Item> *curr_fields_list= &fields_list;
1276
Table *curr_tmp_table= 0;
1278
Initialize examined rows here because the values from all join parts
1279
must be accumulated in examined_row_count. Hence every join
1280
iteration must count from zero.
1282
curr_join->examined_rows= 0;
1284
/* Create a tmp table if distinct or if the sort is too complicated */
1290
We are in a non cacheable sub query. Get the saved join structure
1292
(curr_join may have been modified during last exection and we need
1295
curr_join= tmp_join;
1297
curr_tmp_table= exec_tmp_table1;
1299
/* Copy data to the temporary table */
1300
session->set_proc_info("Copying to tmp table");
1301
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1302
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1303
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1308
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
1310
if (curr_join->having)
1311
curr_join->having= curr_join->tmp_having= 0; // Allready done
1313
/* Change sum_fields reference to calculated fields in tmp_table */
1314
curr_join->all_fields= *curr_all_fields;
1317
items1= items0 + all_fields.elements;
1318
if (sort_and_group || curr_tmp_table->group)
1320
if (change_to_use_tmp_fields(session, items1,
1321
tmp_fields_list1, tmp_all_fields1,
1322
fields_list.elements, all_fields))
1327
if (change_refs_to_tmp_fields(session, items1,
1328
tmp_fields_list1, tmp_all_fields1,
1329
fields_list.elements, all_fields))
1332
curr_join->tmp_all_fields1= tmp_all_fields1;
1333
curr_join->tmp_fields_list1= tmp_fields_list1;
1334
curr_join->items1= items1;
1336
curr_all_fields= &tmp_all_fields1;
1337
curr_fields_list= &tmp_fields_list1;
1338
curr_join->set_items_ref_array(items1);
1340
if (sort_and_group || curr_tmp_table->group)
1342
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1343
+ curr_join->tmp_table_param.func_count;
1344
curr_join->tmp_table_param.sum_func_count= 0;
1345
curr_join->tmp_table_param.func_count= 0;
1349
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1350
curr_join->tmp_table_param.func_count= 0;
1353
if (curr_tmp_table->group)
1354
{ // Already grouped
1355
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1356
curr_join->order= curr_join->group_list; /* order by group */
1357
curr_join->group_list= 0;
1361
If we have different sort & group then we must sort the data by group
1362
and copy it to another tmp table
1363
This code is also used if we are using distinct something
1364
we haven't been able to store in the temporary table yet
1365
like SEC_TO_TIME(SUM(...)).
1368
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1369
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1370
{ /* Must copy to another table */
1371
/* Free first data from old join */
1372
curr_join->join_free();
1373
if (make_simple_join(curr_join, curr_tmp_table))
1375
calc_group_buffer(curr_join, group_list);
1376
count_field_types(select_lex, &curr_join->tmp_table_param,
1377
curr_join->tmp_all_fields1,
1378
curr_join->select_distinct && !curr_join->group_list);
1379
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1380
- curr_join->tmp_fields_list1.elements;
1382
if (exec_tmp_table2)
1383
curr_tmp_table= exec_tmp_table2;
1386
/* group data to new table */
1389
If the access method is loose index scan then all MIN/MAX
1390
functions are precomputed, and should be treated as regular
1391
functions. See extended comment in JOIN::exec.
1393
if (curr_join->join_tab->is_using_loose_index_scan())
1394
curr_join->tmp_table_param.precomputed_group_by= true;
1396
if (!(curr_tmp_table=
1397
exec_tmp_table2= create_tmp_table(session,
1398
&curr_join->tmp_table_param,
1401
curr_join->select_distinct &&
1402
!curr_join->group_list,
1403
1, curr_join->select_options,
1407
curr_join->exec_tmp_table2= exec_tmp_table2;
1409
if (curr_join->group_list)
1411
session->set_proc_info("Creating sort index");
1412
if (curr_join->join_tab == join_tab && save_join_tab())
1416
if (create_sort_index(session, curr_join, curr_join->group_list,
1417
HA_POS_ERROR, HA_POS_ERROR, false) ||
1418
make_group_fields(this, curr_join))
1422
sortorder= curr_join->sortorder;
1425
session->set_proc_info("Copying to group table");
1427
if (curr_join != this)
1431
curr_join->sum_funcs= sum_funcs2;
1432
curr_join->sum_funcs_end= sum_funcs_end2;
1436
curr_join->alloc_func_list();
1437
sum_funcs2= curr_join->sum_funcs;
1438
sum_funcs_end2= curr_join->sum_funcs_end;
1441
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1443
curr_join->group_list= 0;
1445
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1446
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1448
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1449
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1454
end_read_record(&curr_join->join_tab->read_record);
1455
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1456
curr_join->join_tab[0].table= 0; // Table is freed
1458
// No sum funcs anymore
1461
items2= items1 + all_fields.elements;
1462
if (change_to_use_tmp_fields(session, items2,
1463
tmp_fields_list2, tmp_all_fields2,
1464
fields_list.elements, tmp_all_fields1))
1466
curr_join->tmp_fields_list2= tmp_fields_list2;
1467
curr_join->tmp_all_fields2= tmp_all_fields2;
1469
curr_fields_list= &curr_join->tmp_fields_list2;
1470
curr_all_fields= &curr_join->tmp_all_fields2;
1471
curr_join->set_items_ref_array(items2);
1472
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1473
curr_join->tmp_table_param.sum_func_count= 0;
1475
if (curr_tmp_table->distinct)
1476
curr_join->select_distinct=0; /* Each row is unique */
1478
curr_join->join_free(); /* Free quick selects */
1479
if (curr_join->select_distinct && ! curr_join->group_list)
1481
session->set_proc_info("Removing duplicates");
1482
if (curr_join->tmp_having)
1483
curr_join->tmp_having->update_used_tables();
1485
if (remove_duplicates(curr_join, curr_tmp_table,
1486
*curr_fields_list, curr_join->tmp_having))
1489
curr_join->tmp_having=0;
1490
curr_join->select_distinct=0;
1492
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1493
if (make_simple_join(curr_join, curr_tmp_table))
1495
calc_group_buffer(curr_join, curr_join->group_list);
1496
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1500
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1502
if (make_group_fields(this, curr_join))
1508
init_items_ref_array();
1509
items3= ref_pointer_array + (all_fields.elements*4);
1510
setup_copy_fields(session, &curr_join->tmp_table_param,
1511
items3, tmp_fields_list3, tmp_all_fields3,
1512
curr_fields_list->elements, *curr_all_fields);
1513
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1514
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1515
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1516
curr_join->tmp_all_fields3= tmp_all_fields3;
1517
curr_join->tmp_fields_list3= tmp_fields_list3;
1521
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1522
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1523
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1525
curr_fields_list= &tmp_fields_list3;
1526
curr_all_fields= &tmp_all_fields3;
1527
curr_join->set_items_ref_array(items3);
1529
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1531
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1532
session->is_fatal_error)
1535
if (curr_join->group_list || curr_join->order)
1537
session->set_proc_info("Sorting result");
1538
/* If we have already done the group, add HAVING to sorted table */
1539
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1541
// Some tables may have been const
1542
curr_join->tmp_having->update_used_tables();
1543
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1544
table_map used_tables= (curr_join->const_table_map |
1545
curr_table->table->map);
1547
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1548
if (sort_table_cond)
1550
if (!curr_table->select)
1551
if (!(curr_table->select= new SQL_SELECT))
1553
if (!curr_table->select->cond)
1554
curr_table->select->cond= sort_table_cond;
1555
else // This should never happen
1557
if (!(curr_table->select->cond=
1558
new Item_cond_and(curr_table->select->cond,
1562
Item_cond_and do not need fix_fields for execution, its parameters
1563
are fixed or do not need fix_fields, too
1565
curr_table->select->cond->quick_fix_field();
1567
curr_table->select_cond= curr_table->select->cond;
1568
curr_table->select_cond->top_level_item();
1569
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1576
curr_join->select_limit= HA_POS_ERROR;
1580
We can abort sorting after session->select_limit rows if we there is no
1581
WHERE clause for any tables after the sorted one.
1583
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1584
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1585
for (; curr_table < end_table ; curr_table++)
1588
table->keyuse is set in the case there was an original WHERE clause
1589
on the table that was optimized away.
1591
if (curr_table->select_cond ||
1592
(curr_table->keyuse && !curr_table->first_inner))
1594
/* We have to sort all rows */
1595
curr_join->select_limit= HA_POS_ERROR;
1600
if (curr_join->join_tab == join_tab && save_join_tab())
1603
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1604
chose FILESORT to be faster than INDEX SCAN or there is no
1605
suitable index present.
1606
Note, that create_sort_index calls test_if_skip_sort_order and may
1607
finally replace sorting with index scan if there is a LIMIT clause in
1608
the query. XXX: it's never shown in EXPLAIN!
1609
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1611
if (create_sort_index(session, curr_join,
1612
curr_join->group_list ?
1613
curr_join->group_list : curr_join->order,
1614
curr_join->select_limit,
1615
(select_options & OPTION_FOUND_ROWS ?
1616
HA_POS_ERROR : unit->select_limit_cnt),
1617
curr_join->group_list ? true : false))
1620
sortorder= curr_join->sortorder;
1621
if (curr_join->const_tables != curr_join->tables &&
1622
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1625
If no IO cache exists for the first table then we are using an
1626
INDEX SCAN and no filesort. Thus we should not remove the sorted
1627
attribute on the INDEX SCAN.
1633
/* XXX: When can we have here session->is_error() not zero? */
1634
if (session->is_error())
1636
error= session->is_error();
1639
curr_join->having= curr_join->tmp_having;
1640
curr_join->fields= curr_fields_list;
1642
session->set_proc_info("Sending data");
1643
result->send_fields(*curr_fields_list);
1644
error= do_select(curr_join, curr_fields_list, NULL);
1645
session->limit_found_rows= curr_join->send_records;
1647
/* Accumulate the counts from all join iterations of all join parts. */
1648
session->examined_row_count+= curr_join->examined_rows;
1651
With EXPLAIN EXTENDED we have to restore original ref_array
1652
for a derived table which is always materialized.
1653
Otherwise we would not be able to print the query correctly.
1655
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1656
set_items_ref_array(items0);
1665
Return error that hold JOIN.
1669
select_lex->join= 0;
1673
if (join_tab != tmp_join->join_tab)
1675
JoinTable *tab, *end;
1676
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1679
tmp_join->tmp_join= 0;
1680
tmp_table_param.copy_field=0;
1681
return(tmp_join->destroy());
1686
if (exec_tmp_table1)
1687
exec_tmp_table1->free_tmp_table(session);
1688
if (exec_tmp_table2)
1689
exec_tmp_table2->free_tmp_table(session);
1691
delete_dynamic(&keyuse);
1696
Setup for execution all subqueries of a query, for which the optimizer
1697
chose hash semi-join.
1699
@details Iterate over all subqueries of the query, and if they are under an
1700
IN predicate, and the optimizer chose to compute it via hash semi-join:
1701
- try to initialize all data structures needed for the materialized execution
1702
of the IN predicate,
1703
- if this fails, then perform the IN=>EXISTS transformation which was
1704
previously blocked during JOIN::prepare.
1706
This method is part of the "code generation" query processing phase.
1708
This phase must be called after substitute_for_best_equal_field() because
1709
that function may replace items with other items from a multiple equality,
1710
and we need to reference the correct items in the index access method of the
1713
@return Operation status
1714
@retval false success.
1715
@retval true error occurred.
1717
bool JOIN::setup_subquery_materialization()
1719
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1720
un= un->next_unit())
1722
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1724
Item_subselect *subquery_predicate= sl->master_unit()->item;
1725
if (subquery_predicate &&
1726
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1728
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1729
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1730
in_subs->setup_engine())
1739
Partially cleanup JOIN after it has executed: close index or rnd read
1740
(table cursors), free quick selects.
1742
This function is called in the end of execution of a JOIN, before the used
1743
tables are unlocked and closed.
1745
For a join that is resolved using a temporary table, the first sweep is
1746
performed against actual tables and an intermediate result is inserted
1747
into the temprorary table.
1748
The last sweep is performed against the temporary table. Therefore,
1749
the base tables and associated buffers used to fill the temporary table
1750
are no longer needed, and this function is called to free them.
1752
For a join that is performed without a temporary table, this function
1753
is called after all rows are sent, but before EOF packet is sent.
1755
For a simple SELECT with no subqueries this function performs a full
1756
cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1759
If a JOIN is executed for a subquery or if it has a subquery, we can't
1760
do the full cleanup and need to do a partial cleanup only.
1761
- If a JOIN is not the top level join, we must not unlock the tables
1762
because the outer select may not have been evaluated yet, and we
1763
can't unlock only selected tables of a query.
1764
- Additionally, if this JOIN corresponds to a correlated subquery, we
1765
should not free quick selects and join buffers because they will be
1766
needed for the next execution of the correlated subquery.
1767
- However, if this is a JOIN for a [sub]select, which is not
1768
a correlated subquery itself, but has subqueries, we can free it
1769
fully and also free JOINs of all its subqueries. The exception
1770
is a subquery in SELECT list, e.g: @n
1771
SELECT a, (select cmax(b) from t1) group by c @n
1772
This subquery will not be evaluated at first sweep and its value will
1773
not be inserted into the temporary table. Instead, it's evaluated
1774
when selecting from the temporary table. Therefore, it can't be freed
1775
here even though it's not correlated.
1778
Unlock tables even if the join isn't top level select in the tree
1780
void JOIN::join_free()
1782
Select_Lex_Unit *tmp_unit;
1785
Optimization: if not EXPLAIN and we are done with the JOIN,
1788
bool full= (!select_lex->uncacheable && !session->lex->describe);
1789
bool can_unlock= full;
1793
for (tmp_unit= select_lex->first_inner_unit();
1795
tmp_unit= tmp_unit->next_unit())
1796
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1798
Item_subselect *subselect= sl->master_unit()->item;
1799
bool full_local= full && (!subselect || subselect->is_evaluated());
1801
If this join is evaluated, we can fully clean it up and clean up all
1802
its underlying joins even if they are correlated -- they will not be
1803
used any more anyway.
1804
If this join is not yet evaluated, we still must clean it up to
1805
close its table cursors -- it may never get evaluated, as in case of
1806
... HAVING false OR a IN (SELECT ...))
1807
but all table cursors must be closed before the unlock.
1809
sl->cleanup_all_joins(full_local);
1810
/* Can't unlock if at least one JOIN is still needed */
1811
can_unlock= can_unlock && full_local;
1815
We are not using tables anymore
1816
Unlock all tables. We may be in an INSERT .... SELECT statement.
1818
if (can_unlock && lock && session->lock &&
1819
!(select_options & SELECT_NO_UNLOCK) &&
1820
!select_lex->subquery_in_having &&
1821
(select_lex == (session->lex->unit.fake_select_lex ?
1822
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1825
TODO: unlock tables even if the join isn't top level select in the
1828
mysql_unlock_read_tables(session, lock); // Don't free join->lock
1837
Free resources of given join.
1839
@param fill true if we should free all resources, call with full==1
1840
should be last, before it this function can be called with
1844
With subquery this function definitely will be called several times,
1845
but even for simple query it can be called several times.
1847
void JOIN::cleanup(bool full)
1851
JoinTable *tab,*end;
1853
Only a sorted table may be cached. This sorted table is always the
1854
first non const table in join->table
1856
if (tables > const_tables) // Test for not-const tables
1858
table[const_tables]->free_io_cache();
1859
table[const_tables]->filesort_free_buffers(full);
1864
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1870
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1873
tab->table->file->ha_index_or_rnd_end();
1878
We are not using tables anymore
1879
Unlock all tables. We may be in an INSERT .... SELECT statement.
1884
tmp_table_param.copy_field= 0;
1885
group_fields.delete_elements();
1887
We can't call delete_elements() on copy_funcs as this will cause
1888
problems in free_elements() as some of the elements are then deleted.
1890
tmp_table_param.copy_funcs.empty();
1892
If we have tmp_join and 'this' JOIN is not tmp_join and
1893
tmp_table_param.copy_field's of them are equal then we have to remove
1894
pointer to tmp_table_param.copy_field from tmp_join, because it qill
1895
be removed in tmp_table_param.cleanup().
1899
tmp_join->tmp_table_param.copy_field ==
1900
tmp_table_param.copy_field)
1902
tmp_join->tmp_table_param.copy_field=
1903
tmp_join->tmp_table_param.save_copy_field= 0;
1905
tmp_table_param.cleanup();
1911
used only in JOIN::clear
1913
static void clear_tables(JOIN *join)
1916
must clear only the non-const tables, as const tables
1917
are not re-calculated.
1919
for (uint32_t i= join->const_tables; i < join->tables; i++)
1920
join->table[i]->mark_as_null_row(); // All fields are NULL
1924
Make an array of pointers to sum_functions to speed up
1925
sum_func calculation.
1932
bool JOIN::alloc_func_list()
1934
uint32_t func_count, group_parts;
1936
func_count= tmp_table_param.sum_func_count;
1938
If we are using rollup, we need a copy of the summary functions for
1941
if (rollup.state != ROLLUP::STATE_NONE)
1942
func_count*= (send_group_parts+1);
1944
group_parts= send_group_parts;
1946
If distinct, reserve memory for possible
1947
disctinct->group_by optimization
1949
if (select_distinct)
1951
group_parts+= fields_list.elements;
1953
If the order_st clause is specified then it's possible that
1954
it also will be optimized, so reserve space for it too
1959
for (ord= order; ord; ord= ord->next)
1964
/* This must use calloc() as rollup_make_fields depends on this */
1965
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
1966
sizeof(Item_sum***) * (group_parts+1));
1967
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
1968
return(sum_funcs == 0);
1972
Initialize 'sum_funcs' array with all Item_sum objects.
1974
@param field_list All items
1975
@param send_fields Items in select list
1976
@param before_group_by Set to 1 if this is called before GROUP BY handling
1977
@param recompute Set to true if sum_funcs must be recomputed
1984
bool JOIN::make_sum_func_list(List<Item> &field_list,
1985
List<Item> &send_fields,
1986
bool before_group_by,
1989
List_iterator_fast<Item> it(field_list);
1993
if (*sum_funcs && !recompute)
1994
return(false); /* We have already initialized sum_funcs. */
1999
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2000
(!((Item_sum*) item)->depended_from() ||
2001
((Item_sum *)item)->depended_from() == select_lex))
2002
*func++= (Item_sum*) item;
2004
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2006
rollup.state= ROLLUP::STATE_READY;
2007
if (rollup_make_fields(field_list, send_fields, &func))
2008
return(true); // Should never happen
2010
else if (rollup.state == ROLLUP::STATE_NONE)
2012
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2013
sum_funcs_end[i]= func;
2015
else if (rollup.state == ROLLUP::STATE_READY)
2016
return(false); // Don't put end marker
2017
*func=0; // End marker
2021
/** Allocate memory needed for other rollup functions. */
2022
bool JOIN::rollup_init()
2027
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2028
rollup.state= ROLLUP::STATE_INITED;
2031
Create pointers to the different sum function groups
2032
These are updated by rollup_make_fields()
2034
tmp_table_param.group_parts= send_group_parts;
2036
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2038
sizeof(List<Item>) +
2039
ref_pointer_array_size)
2040
* send_group_parts )))
2043
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2044
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2045
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2048
Prepare space for field list for the different levels
2049
These will be filled up in rollup_make_fields()
2051
for (i= 0 ; i < send_group_parts ; i++)
2053
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2054
List<Item> *rollup_fields= &rollup.fields[i];
2055
rollup_fields->empty();
2056
rollup.ref_pointer_arrays[i]= ref_array;
2057
ref_array+= all_fields.elements;
2059
for (i= 0 ; i < send_group_parts; i++)
2061
for (j=0 ; j < fields_list.elements ; j++)
2062
rollup.fields[i].push_back(rollup.null_items[i]);
2064
List_iterator<Item> it(all_fields);
2066
while ((item= it++))
2068
order_st *group_tmp;
2069
bool found_in_group= 0;
2071
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2073
if (*group_tmp->item == item)
2075
item->maybe_null= 1;
2077
if (item->const_item())
2080
For ROLLUP queries each constant item referenced in GROUP BY list
2081
is wrapped up into an Item_func object yielding the same value
2082
as the constant item. The objects of the wrapper class are never
2083
considered as constant items and besides they inherit all
2084
properties of the Item_result_field class.
2085
This wrapping allows us to ensure writing constant items
2086
into temporary tables whenever the result of the ROLLUP
2087
operation has to be written into a temporary table, e.g. when
2088
ROLLUP is used together with DISTINCT in the SELECT list.
2089
Usually when creating temporary tables for a intermidiate
2090
result we do not include fields for constant expressions.
2092
Item* new_item= new Item_func_rollup_const(item);
2095
new_item->fix_fields(session, (Item **) 0);
2096
session->change_item_tree(it.ref(), new_item);
2097
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2099
if (*tmp->item == item)
2100
session->change_item_tree(tmp->item, new_item);
2105
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2107
bool changed= false;
2108
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2111
We have to prevent creation of a field in a temporary table for
2112
an expression that contains GROUP BY attributes.
2113
Marking the expression item as 'with_sum_func' will ensure this.
2116
item->with_sum_func= 1;
2123
Fill up rollup structures with pointers to fields to use.
2125
Creates copies of item_sum items for each sum level.
2127
@param fields_arg List of all fields (hidden and real ones)
2128
@param sel_fields Pointer to selected fields
2129
@param func Store here a pointer to all fields
2133
In this case func is pointing to next not used element.
2137
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2139
List_iterator_fast<Item> it(fields_arg);
2140
Item *first_field= sel_fields.head();
2144
Create field lists for the different levels
2146
The idea here is to have a separate field list for each rollup level to
2147
avoid all runtime checks of which columns should be NULL.
2149
The list is stored in reverse order to get sum function in such an order
2150
in func that it makes it easy to reset them with init_sum_functions()
2152
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2154
rollup.fields[0] will contain list where a,b,c is NULL
2155
rollup.fields[1] will contain list where b,c is NULL
2157
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2159
sum_funcs_end[0] points to all sum functions
2160
sum_funcs_end[1] points to all sum functions, except grand totals
2164
for (level=0 ; level < send_group_parts ; level++)
2167
uint32_t pos= send_group_parts - level -1;
2168
bool real_fields= 0;
2170
List_iterator<Item> new_it(rollup.fields[pos]);
2171
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2172
order_st *start_group;
2174
/* Point to first hidden field */
2175
Item **ref_array= ref_array_start + fields_arg.elements-1;
2177
/* Remember where the sum functions ends for the previous level */
2178
sum_funcs_end[pos+1]= *func;
2180
/* Find the start of the group for this level */
2181
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2185
while ((item= it++))
2187
if (item == first_field)
2189
real_fields= 1; // End of hidden fields
2190
ref_array= ref_array_start;
2193
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2194
(!((Item_sum*) item)->depended_from() ||
2195
((Item_sum *)item)->depended_from() == select_lex))
2199
This is a top level summary function that must be replaced with
2200
a sum function that is reset for this level.
2202
NOTE: This code creates an object which is not that nice in a
2203
sub select. Fortunately it's not common to have rollup in
2206
item= item->copy_or_same(session);
2207
((Item_sum*) item)->make_unique();
2208
*(*func)= (Item_sum*) item;
2213
/* Check if this is something that is part of this group by */
2214
order_st *group_tmp;
2215
for (group_tmp= start_group, i= pos ;
2216
group_tmp ; group_tmp= group_tmp->next, i++)
2218
if (*group_tmp->item == item)
2221
This is an element that is used by the GROUP BY and should be
2222
set to NULL in this level
2224
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2227
item->maybe_null= 1; // Value will be null sometimes
2228
null_item->result_field= item->get_tmp_table_field();
2237
(void) new_it++; // Point to next item
2238
new_it.replace(item); // Replace previous
2245
sum_funcs_end[0]= *func; // Point to last function
2250
Send all rollup levels higher than the current one to the client.
2254
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2257
@param idx Level we are on:
2258
- 0 = Total sum level
2259
- 1 = First group changed (a)
2260
- 2 = Second group changed (a,b)
2265
1 If send_data_failed()
2267
int JOIN::rollup_send_data(uint32_t idx)
2270
for (i= send_group_parts ; i-- > idx ; )
2272
/* Get reference pointers to sum functions in place */
2273
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2274
ref_pointer_array_size);
2275
if ((!having || having->val_int()))
2277
if (send_records < unit->select_limit_cnt && do_send_rows &&
2278
result->send_data(rollup.fields[i]))
2283
/* Restore ref_pointer_array */
2284
set_items_ref_array(current_ref_pointer_array);
2289
Write all rollup levels higher than the current one to a temp table.
2293
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2296
@param idx Level we are on:
2297
- 0 = Total sum level
2298
- 1 = First group changed (a)
2299
- 2 = Second group changed (a,b)
2300
@param table reference to temp table
2305
1 if write_data_failed()
2307
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2310
for (i= send_group_parts ; i-- > idx ; )
2312
/* Get reference pointers to sum functions in place */
2313
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2314
ref_pointer_array_size);
2315
if ((!having || having->val_int()))
2319
List_iterator_fast<Item> it(rollup.fields[i]);
2320
while ((item= it++))
2322
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2323
item->save_in_result_field(1);
2325
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2326
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
2328
if (create_myisam_from_heap(session, table_arg,
2329
tmp_table_param.start_recinfo,
2330
&tmp_table_param.recinfo,
2336
/* Restore ref_pointer_array */
2337
set_items_ref_array(current_ref_pointer_array);
2342
clear results if there are not rows found for group
2343
(end_send_group/end_write_group)
2348
copy_fields(&tmp_table_param);
2352
Item_sum *func, **func_ptr= sum_funcs;
2353
while ((func= *(func_ptr++)))
2359
change select_result object of JOIN.
2361
@param res new select_result object
2368
bool JOIN::change_result(select_result *res)
2371
if (result->prepare(fields_list, select_lex->master_unit()))
2381
Process one record of the nested loop join.
2385
This function will evaluate parts of WHERE/ON clauses that are
2386
applicable to the partial record on hand and in case of success
2387
submit this record to the next level of the nested loop.
2389
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error)
2391
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2392
ha_rows found_records= join->found_records;
2393
COND *select_cond= join_tab->select_cond;
2395
if (error > 0 || (join->session->is_error())) // Fatal error
2396
return NESTED_LOOP_ERROR;
2398
return NESTED_LOOP_NO_MORE_ROWS;
2399
if (join->session->killed) // Aborted by user
2401
join->session->send_kill_message();
2402
return NESTED_LOOP_KILLED; /* purecov: inspected */
2404
if (!select_cond || select_cond->val_int())
2407
There is no select condition or the attached pushed down
2408
condition is true => a match is found.
2411
while (join_tab->first_unmatched && found)
2414
The while condition is always false if join_tab is not
2415
the last inner join table of an outer join operation.
2417
JoinTable *first_unmatched= join_tab->first_unmatched;
2419
Mark that a match for current outer table is found.
2420
This activates push down conditional predicates attached
2421
to the all inner tables of the outer join.
2423
first_unmatched->found= 1;
2424
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2426
if (tab->table->reginfo.not_exists_optimize)
2427
return NESTED_LOOP_NO_MORE_ROWS;
2428
/* Check all predicates that has just been activated. */
2430
Actually all predicates non-guarded by first_unmatched->found
2431
will be re-evaluated again. It could be fixed, but, probably,
2432
it's not worth doing now.
2434
if (tab->select_cond && !tab->select_cond->val_int())
2436
/* The condition attached to table tab is false */
2437
if (tab == join_tab)
2442
Set a return point if rejected predicate is attached
2443
not to the last table of the current nest level.
2445
join->return_tab= tab;
2446
return NESTED_LOOP_OK;
2451
Check whether join_tab is not the last inner table
2452
for another embedding outer join.
2454
if ((first_unmatched= first_unmatched->first_upper) &&
2455
first_unmatched->last_inner != join_tab)
2457
join_tab->first_unmatched= first_unmatched;
2460
JoinTable *return_tab= join->return_tab;
2461
join_tab->found_match= true;
2464
It was not just a return to lower loop level when one
2465
of the newly activated predicates is evaluated as false
2466
(See above join->return_tab= tab).
2468
join->examined_rows++;
2469
join->session->row_count++;
2473
enum enum_nested_loop_state rc;
2474
/* A match from join_tab is found for the current partial join. */
2475
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2476
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2478
if (return_tab < join->return_tab)
2479
join->return_tab= return_tab;
2481
if (join->return_tab < join_tab)
2482
return NESTED_LOOP_OK;
2484
Test if this was a SELECT DISTINCT query on a table that
2485
was not in the field list; In this case we can abort if
2486
we found a row, as no new rows can be added to the result.
2488
if (not_used_in_distinct && found_records != join->found_records)
2489
return NESTED_LOOP_NO_MORE_ROWS;
2492
join_tab->read_record.file->unlock_row();
2497
The condition pushed down to the table join_tab rejects all rows
2498
with the beginning coinciding with the current partial join.
2500
join->examined_rows++;
2501
join->session->row_count++;
2502
join_tab->read_record.file->unlock_row();
2504
return NESTED_LOOP_OK;
2509
Construct a NULL complimented partial join record and feed it to the next
2510
level of the nested loop. This function is used in case we have
2511
an OUTER join and no matching record was found.
2513
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab)
2516
The table join_tab is the first inner table of a outer join operation
2517
and no matches has been found for the current outer row.
2519
JoinTable *last_inner_tab= join_tab->last_inner;
2520
/* Cache variables for faster loop */
2522
for ( ; join_tab <= last_inner_tab ; join_tab++)
2524
/* Change the the values of guard predicate variables. */
2526
join_tab->not_null_compl= 0;
2527
/* The outer row is complemented by nulls for each inner tables */
2528
join_tab->table->restoreRecordAsDefault(); // Make empty record
2529
join_tab->table->mark_as_null_row(); // For group by without error
2530
select_cond= join_tab->select_cond;
2531
/* Check all attached conditions for inner table rows. */
2532
if (select_cond && !select_cond->val_int())
2533
return NESTED_LOOP_OK;
2537
The row complemented by nulls might be the first row
2538
of embedding outer joins.
2539
If so, perform the same actions as in the code
2540
for the first regular outer join row above.
2544
JoinTable *first_unmatched= join_tab->first_unmatched;
2545
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2547
join_tab->first_unmatched= first_unmatched;
2548
if (! first_unmatched)
2550
first_unmatched->found= 1;
2551
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2553
if (tab->select_cond && !tab->select_cond->val_int())
2555
join->return_tab= tab;
2556
return NESTED_LOOP_OK;
2561
The row complemented by nulls satisfies all conditions
2562
attached to inner tables.
2563
Send the row complemented by nulls to be joined with the
2566
return (*join_tab->next_select)(join, join_tab+1, 0);
2569
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last)
2571
enum_nested_loop_state rc= NESTED_LOOP_OK;
2575
join_tab->table->null_row= 0;
2576
if (!join_tab->cache.records)
2577
return NESTED_LOOP_OK; /* Nothing to do */
2579
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
2580
if (join_tab->use_quick == 2)
2582
if (join_tab->select->quick)
2583
{ /* Used quick select last. reset it */
2584
delete join_tab->select->quick;
2585
join_tab->select->quick=0;
2588
/* read through all records */
2589
if ((error=join_init_read_record(join_tab)))
2591
reset_cache_write(&join_tab->cache);
2592
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2595
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2597
tmp->status=tmp->table->status;
2598
tmp->table->status=0;
2601
info= &join_tab->read_record;
2604
if (join->session->killed)
2606
join->session->send_kill_message();
2607
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
2609
SQL_SELECT *select=join_tab->select;
2610
if (rc == NESTED_LOOP_OK &&
2611
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2614
reset_cache_read(&join_tab->cache);
2615
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2617
join_tab->readCachedRecord();
2618
if (!select || !select->skip_record())
2622
rc= (join_tab->next_select)(join,join_tab+1,0);
2623
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2625
reset_cache_write(&join_tab->cache);
2630
return NESTED_LOOP_ERROR;
2634
} while (!(error=info->read_record(info)));
2637
join_tab->readCachedRecord(); // Restore current record
2638
reset_cache_write(&join_tab->cache);
2639
if (error > 0) // Fatal error
2640
return NESTED_LOOP_ERROR; /* purecov: inspected */
2641
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2642
tmp2->table->status=tmp2->status;
2643
return NESTED_LOOP_OK;
2646
/*****************************************************************************
2648
Functions that end one nested loop iteration. Different functions
2649
are used to support GROUP BY clause and to redirect records
2650
to a table (e.g. in case of SELECT into a temporary table) or to the
2654
NESTED_LOOP_OK - the record has been successfully handled
2655
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2657
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2659
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2660
additionally, the nested loop produced the
2661
number of rows specified in the LIMIT clause
2663
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2664
additionally, there is a cursor and the nested
2665
loop algorithm produced the number of rows
2666
that is specified for current cursor fetch
2668
All return values except NESTED_LOOP_OK abort the nested loop.
2669
*****************************************************************************/
2670
enum_nested_loop_state end_send(JOIN *join, JoinTable *, bool end_of_records)
2672
if (! end_of_records)
2675
if (join->having && join->having->val_int() == 0)
2676
return NESTED_LOOP_OK; // Didn't match having
2678
if (join->do_send_rows)
2679
error=join->result->send_data(*join->fields);
2681
return NESTED_LOOP_ERROR; /* purecov: inspected */
2682
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2684
if (join->select_options & OPTION_FOUND_ROWS)
2686
JoinTable *jt=join->join_tab;
2687
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2688
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2689
!(jt->select && jt->select->quick) &&
2690
(jt->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
2693
/* Join over all rows in table; Return number of found rows */
2694
Table *table= jt->table;
2696
join->select_options^= OPTION_FOUND_ROWS;
2697
if (table->sort.record_pointers ||
2698
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2700
/* Using filesort */
2701
join->send_records= table->sort.found_records;
2705
table->file->info(HA_STATUS_VARIABLE);
2706
join->send_records= table->file->stats.records;
2711
join->do_send_rows= 0;
2712
if (join->unit->fake_select_lex)
2713
join->unit->fake_select_lex->select_limit= 0;
2714
return NESTED_LOOP_OK;
2717
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2719
else if (join->send_records >= join->fetch_limit)
2722
There is a server side cursor and all rows for
2723
this fetch request are sent.
2725
return NESTED_LOOP_CURSOR_LIMIT;
2729
return NESTED_LOOP_OK;
2732
enum_nested_loop_state end_write(JOIN *join, JoinTable *, bool end_of_records)
2734
Table *table= join->tmp_table;
2736
if (join->session->killed) // Aborted by user
2738
join->session->send_kill_message();
2739
return NESTED_LOOP_KILLED; /* purecov: inspected */
2741
if (!end_of_records)
2743
copy_fields(&join->tmp_table_param);
2744
copy_funcs(join->tmp_table_param.items_to_copy);
2745
if (!join->having || join->having->val_int())
2748
join->found_records++;
2749
if ((error=table->file->ha_write_row(table->record[0])))
2751
if (!table->file->is_fatal_error(error, HA_CHECK_DUP))
2753
if (create_myisam_from_heap(join->session, table,
2754
join->tmp_table_param.start_recinfo,
2755
&join->tmp_table_param.recinfo,
2757
return NESTED_LOOP_ERROR; // Not a table_is_full error
2758
table->s->uniques= 0; // To ensure rows are the same
2760
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2762
if (!(join->select_options & OPTION_FOUND_ROWS))
2763
return NESTED_LOOP_QUERY_LIMIT;
2764
join->do_send_rows= 0;
2765
join->unit->select_limit_cnt= HA_POS_ERROR;
2766
return NESTED_LOOP_OK;
2771
return NESTED_LOOP_OK;
2774
/** Group by searching after group record and updating it if possible. */
2775
enum_nested_loop_state end_update(JOIN *join, JoinTable *, bool end_of_records)
2777
Table *table= join->tmp_table;
2782
return NESTED_LOOP_OK;
2783
if (join->session->killed) // Aborted by user
2785
join->session->send_kill_message();
2786
return NESTED_LOOP_KILLED; /* purecov: inspected */
2789
join->found_records++;
2790
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2791
/* Make a key of group index */
2792
for (group=table->group ; group ; group=group->next)
2794
Item *item= *group->item;
2795
item->save_org_in_field(group->field);
2796
/* Store in the used key if the field was 0 */
2797
if (item->maybe_null)
2798
group->buff[-1]= (char) group->field->is_null();
2800
if (!table->file->index_read_map(table->record[1],
2801
join->tmp_table_param.group_buff,
2804
{ /* Update old record */
2805
table->restoreRecord();
2806
update_tmptable_sum_func(join->sum_funcs,table);
2807
if ((error= table->file->ha_update_row(table->record[1],
2810
table->file->print_error(error,MYF(0)); /* purecov: inspected */
2811
return NESTED_LOOP_ERROR; /* purecov: inspected */
2813
return NESTED_LOOP_OK;
2817
Copy null bits from group key to table
2818
We can't copy all data as the key may have different format
2819
as the row data (for example as with VARCHAR keys)
2821
KEY_PART_INFO *key_part;
2822
for (group=table->group,key_part=table->key_info[0].key_part;
2824
group=group->next,key_part++)
2826
if (key_part->null_bit)
2827
memcpy(table->record[0]+key_part->offset, group->buff, 1);
2829
init_tmptable_sum_functions(join->sum_funcs);
2830
copy_funcs(join->tmp_table_param.items_to_copy);
2831
if ((error=table->file->ha_write_row(table->record[0])))
2833
if (create_myisam_from_heap(join->session, table,
2834
join->tmp_table_param.start_recinfo,
2835
&join->tmp_table_param.recinfo,
2837
return NESTED_LOOP_ERROR; // Not a table_is_full error
2838
/* Change method to update rows */
2839
table->file->ha_index_init(0, 0);
2840
join->join_tab[join->tables-1].next_select= end_unique_update;
2842
join->send_records++;
2843
return NESTED_LOOP_OK;
2846
/** Like end_update, but this is done with unique constraints instead of keys. */
2847
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *, bool end_of_records)
2849
Table *table= join->tmp_table;
2853
return NESTED_LOOP_OK;
2854
if (join->session->killed) // Aborted by user
2856
join->session->send_kill_message();
2857
return NESTED_LOOP_KILLED; /* purecov: inspected */
2860
init_tmptable_sum_functions(join->sum_funcs);
2861
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2862
copy_funcs(join->tmp_table_param.items_to_copy);
2864
if (!(error= table->file->ha_write_row(table->record[0])))
2865
join->send_records++; // New group
2868
if ((int) table->file->get_dup_key(error) < 0)
2870
table->file->print_error(error,MYF(0)); /* purecov: inspected */
2871
return NESTED_LOOP_ERROR; /* purecov: inspected */
2873
if (table->file->rnd_pos(table->record[1],table->file->dup_ref))
2875
table->file->print_error(error,MYF(0)); /* purecov: inspected */
2876
return NESTED_LOOP_ERROR; /* purecov: inspected */
2878
table->restoreRecord();
2879
update_tmptable_sum_func(join->sum_funcs,table);
2880
if ((error= table->file->ha_update_row(table->record[1],
2883
table->file->print_error(error,MYF(0)); /* purecov: inspected */
2884
return NESTED_LOOP_ERROR; /* purecov: inspected */
2887
return NESTED_LOOP_OK;
2891
allocate group fields or take prepared (cached).
2893
@param main_join join of current select
2894
@param curr_join current join (join of current select or temporary copy
2902
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
2904
if (main_join->group_fields_cache.elements)
2906
curr_join->group_fields= main_join->group_fields_cache;
2907
curr_join->sort_and_group= 1;
2911
if (alloc_group_fields(curr_join, curr_join->group_list))
2913
main_join->group_fields_cache= curr_join->group_fields;
2919
calc how big buffer we need for comparing group entries.
2921
static void calc_group_buffer(JOIN *join,order_st *group)
2923
uint32_t key_length=0, parts=0, null_parts=0;
2927
for (; group ; group=group->next)
2929
Item *group_item= *group->item;
2930
Field *field= group_item->get_tmp_table_field();
2933
enum_field_types type;
2934
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
2935
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
2936
else if (type == DRIZZLE_TYPE_VARCHAR)
2937
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
2939
key_length+= field->pack_length();
2943
switch (group_item->result_type()) {
2945
key_length+= sizeof(double);
2948
key_length+= sizeof(int64_t);
2950
case DECIMAL_RESULT:
2951
key_length+= my_decimal_get_binary_size(group_item->max_length -
2952
(group_item->decimals ? 1 : 0),
2953
group_item->decimals);
2957
enum enum_field_types type= group_item->field_type();
2959
As items represented as DATE/TIME fields in the group buffer
2960
have STRING_RESULT result type, we increase the length
2961
by 8 as maximum pack length of such fields.
2963
if (type == DRIZZLE_TYPE_DATE ||
2964
type == DRIZZLE_TYPE_DATETIME ||
2965
type == DRIZZLE_TYPE_TIMESTAMP)
2972
Group strings are taken as varstrings and require an length field.
2973
A field is not yet created by create_tmp_field()
2974
and the sizes should match up.
2976
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
2981
/* This case should never be choosen */
2983
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
2987
if (group_item->maybe_null)
2990
join->tmp_table_param.group_length=key_length+null_parts;
2991
join->tmp_table_param.group_parts=parts;
2992
join->tmp_table_param.group_null_parts=null_parts;
2996
Get a list of buffers for saveing last group.
2998
Groups are saved in reverse order for easyer check loop.
3000
static bool alloc_group_fields(JOIN *join,order_st *group)
3004
for (; group ; group=group->next)
3006
Cached_item *tmp=new_Cached_item(join->session, *group->item, false);
3007
if (!tmp || join->group_fields.push_front(tmp))
3011
join->sort_and_group=1; /* Mark for do_select */
3015
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3018
JoinTable **pos,**end;
3019
Session *session=join->session;
3021
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3025
JoinTable *join_tab= *pos;
3026
if (!join_tab->used_fieldlength) /* Not calced yet */
3027
calc_used_field_length(session, join_tab);
3028
length+=join_tab->used_fieldlength;
3034
Get the number of different row combinations for subset of partial join
3038
join The join structure
3039
idx Number of tables in the partial join order (i.e. the
3040
partial join order is in join->positions[0..idx-1])
3041
found_ref Bitmap of tables for which we need to find # of distinct
3045
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3046
tables within that join order (specified in found_ref), find out how many
3047
distinct row combinations of subset tables will be in the result of the
3050
This is used as follows: Suppose we have a table accessed with a ref-based
3051
method. The ref access depends on current rows of tables in found_ref.
3052
We want to count # of different ref accesses. We assume two ref accesses
3053
will be different if at least one of access parameters is different.
3054
Example: consider a query
3056
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3059
t1, ref access on t1.key=c1
3060
t2, ref access on t2.key=c2
3061
t3, ref access on t3.key=t1.field
3063
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3064
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3065
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3066
n_distinct_ref_scans = #records_read(t1)
3068
The reason for having this function (at least the latest version of it)
3069
is that we need to account for buffering in join execution.
3071
An edge-case example: if we have a non-first table in join accessed via
3072
ref(const) or ref(param) where there is a small number of different
3073
values of param, then the access will likely hit the disk cache and will
3074
not require any disk seeks.
3076
The proper solution would be to assume an LRU disk cache of some size,
3077
calculate probability of cache hits, etc. For now we just count
3078
identical ref accesses as one.
3081
Expected number of row combinations
3083
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3086
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3087
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3091
if (pos->examinePosition(found_ref))
3093
found_ref|= pos->getRefDependMap();
3095
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3096
with no matching row we will get position[t2].records_read==0.
3097
Actually the size of output is one null-complemented row, therefore
3098
we will use value of 1 whenever we get records_read==0.
3101
- the above case can't occur if inner part of outer join has more
3102
than one table: table with no matches will not be marked as const.
3104
- Ideally we should add 1 to records_read for every possible null-
3105
complemented row. We're not doing it because: 1. it will require
3106
non-trivial code and add overhead. 2. The value of records_read
3107
is an inprecise estimate and adding 1 (or, in the worst case,
3108
#max_nested_outer_joins=64-1) will not make it any more precise.
3110
if (pos->getFanout() > DBL_EPSILON)
3111
found*= pos->getFanout();
3118
Set up join struct according to best position.
3120
static bool get_best_combination(JOIN *join)
3123
table_map used_tables;
3124
JoinTable *join_tab,*j;
3126
uint32_t table_count;
3127
Session *session=join->session;
3128
optimizer::Position cur_pos;
3130
table_count=join->tables;
3131
if (!(join->join_tab=join_tab=
3132
(JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))
3137
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3138
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3141
cur_pos= join->getPosFromOptimalPlan(tablenr);
3142
*j= *cur_pos.getJoinTable();
3143
form=join->table[tablenr]=j->table;
3144
used_tables|= form->map;
3145
form->reginfo.join_tab=j;
3146
if (!*j->on_expr_ref)
3147
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
3148
if (j->type == AM_CONST)
3149
continue; // Handled in make_join_stat..
3154
if (j->type == AM_SYSTEM)
3156
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3159
if (tablenr != join->const_tables)
3162
else if (create_ref_for_key(join, j, keyuse, used_tables))
3163
return(true); // Something went wrong
3166
for (i=0 ; i < table_count ; i++)
3167
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3168
update_depend_map(join);
3172
/** Save const tables first as used tables. */
3173
static void set_position(JOIN *join,uint32_t idx,JoinTable *table,KeyUse *key)
3175
optimizer::Position tmp_pos(1.0, /* This is a const table */
3180
join->setPosInPartialPlan(idx, tmp_pos);
3182
/* Move the const table as down as possible in best_ref */
3183
JoinTable **pos=join->best_ref+idx+1;
3184
JoinTable *next=join->best_ref[idx];
3185
for (;next != table ; pos++)
3187
JoinTable *tmp=pos[0];
3191
join->best_ref[idx]=table;
3195
Selects and invokes a search strategy for an optimal query plan.
3197
The function checks user-configurable parameters that control the search
3198
strategy for an optimal plan, selects the search method and then invokes
3199
it. Each specific optimization procedure stores the final optimal plan in
3200
the array 'join->best_positions', and the cost of the plan in
3203
@param join pointer to the structure providing all context info for
3205
@param join_tables set of the tables in the query
3212
static bool choose_plan(JOIN *join, table_map join_tables)
3214
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3215
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3216
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3218
join->cur_embedding_map.reset();
3219
reset_nj_counters(join->join_list);
3221
if (SELECT_STRAIGHT_JOIN option is set)
3222
reorder tables so dependent tables come after tables they depend
3223
on, otherwise keep tables in the order they were specified in the query
3225
Apply heuristic: pre-sort all access plans with respect to the number of
3228
my_qsort(join->best_ref + join->const_tables,
3229
join->tables - join->const_tables, sizeof(JoinTable*),
3230
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3233
optimize_straight_join(join, join_tables);
3237
if (search_depth == 0)
3238
/* Automatically determine a reasonable value for 'search_depth' */
3239
search_depth= determine_search_depth(join);
3240
if (greedy_search(join, join_tables, search_depth, prune_level))
3245
Store the cost of this query into a user variable
3246
Don't update last_query_cost for statements that are not "flat joins" :
3247
i.e. they have subqueries, unions or call stored procedures.
3248
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3250
if (join->session->lex->is_single_level_stmt())
3251
join->session->status_var.last_query_cost= join->best_read;
3256
Find the best access path for an extension of a partial execution
3257
plan and add this path to the plan.
3259
The function finds the best access path to table 's' from the passed
3260
partial plan where an access path is the general term for any means to
3261
access the data in 's'. An access path may use either an index or a scan,
3262
whichever is cheaper. The input partial plan is passed via the array
3263
'join->positions' of length 'idx'. The chosen access method for 's' and its
3264
cost are stored in 'join->positions[idx]'.
3266
@param join pointer to the structure providing all context info
3268
@param s the table to be joined by the function
3269
@param session thread for the connection that submitted the query
3270
@param remaining_tables set of tables not included into the partial plan yet
3271
@param idx the length of the partial plan
3272
@param record_count estimate for the number of records returned by the
3274
@param read_time the cost of the partial plan
3279
static void best_access_path(JOIN *join,
3282
table_map remaining_tables,
3284
double record_count,
3287
KeyUse *best_key= 0;
3288
uint32_t best_max_key_part= 0;
3289
bool found_constraint= 0;
3290
double best= DBL_MAX;
3291
double best_time= DBL_MAX;
3292
double records= DBL_MAX;
3293
table_map best_ref_depends_map= 0;
3298
{ /* Use key if possible */
3299
Table *table= s->table;
3300
KeyUse *keyuse,*start_key=0;
3301
double best_records= DBL_MAX;
3302
uint32_t max_key_part=0;
3304
/* Test how we can use keys */
3305
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3306
for (keyuse=s->keyuse ; keyuse->table == table ;)
3308
key_part_map found_part= 0;
3309
table_map found_ref= 0;
3310
uint32_t key= keyuse->key;
3311
KEY *keyinfo= table->key_info+key;
3312
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3313
key_part_map const_part= 0;
3314
/* The or-null keypart in ref-or-null access: */
3315
key_part_map ref_or_null_part= 0;
3317
/* Calculate how many key segments of the current key we can use */
3320
do /* For each keypart */
3322
uint32_t keypart= keyuse->keypart;
3323
table_map best_part_found_ref= 0;
3324
double best_prev_record_reads= DBL_MAX;
3326
do /* For each way to access the keypart */
3330
if 1. expression doesn't refer to forward tables
3331
2. we won't get two ref-or-null's
3333
if (!(remaining_tables & keyuse->used_tables) &&
3334
!(ref_or_null_part && (keyuse->optimize &
3335
KEY_OPTIMIZE_REF_OR_NULL)))
3337
found_part|= keyuse->keypart_map;
3338
if (!(keyuse->used_tables & ~join->const_table_map))
3339
const_part|= keyuse->keypart_map;
3341
double tmp2= prev_record_reads(join, idx, (found_ref |
3342
keyuse->used_tables));
3343
if (tmp2 < best_prev_record_reads)
3345
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
3346
best_prev_record_reads= tmp2;
3348
if (rec > keyuse->ref_table_rows)
3349
rec= keyuse->ref_table_rows;
3351
If there is one 'key_column IS NULL' expression, we can
3352
use this ref_or_null optimisation of this field
3354
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
3355
ref_or_null_part |= keyuse->keypart_map;
3359
} while (keyuse->table == table && keyuse->key == key &&
3360
keyuse->keypart == keypart);
3361
found_ref|= best_part_found_ref;
3362
} while (keyuse->table == table && keyuse->key == key);
3365
Assume that that each key matches a proportional part of table.
3368
continue; // Nothing usable found
3370
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3371
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3374
found_constraint= 1;
3377
Check if we found full key
3379
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3382
max_key_part= UINT32_MAX;
3383
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3385
tmp = prev_record_reads(join, idx, found_ref);
3391
{ /* We found a const key */
3393
ReuseRangeEstimateForRef-1:
3394
We get here if we've found a ref(const) (c_i are constants):
3395
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3397
If range optimizer was able to construct a "range"
3398
access on this index, then its condition "quick_cond" was
3399
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3400
from the range optimizer.
3402
Proof of (*): By properties of range and ref optimizers
3403
quick_cond will be equal or tighther than ref_const_cond.
3404
ref_const_cond already covers "smallest" possible interval -
3405
a singlepoint interval over all keyparts. Therefore,
3406
quick_cond is equivalent to ref_const_cond (if it was an
3407
empty interval we wouldn't have got here).
3409
if (table->quick_keys.test(key))
3410
records= (double) table->quick_rows[key];
3413
/* quick_range couldn't use key! */
3414
records= (double) s->records/rec;
3419
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3420
{ /* Prefer longer keys */
3422
((double) s->records / (double) rec *
3424
((double) (table->s->max_key_length-keyinfo->key_length) /
3425
(double) table->s->max_key_length)));
3427
records=2.0; /* Can't be as good as a unique */
3430
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3431
E(#rows) from range optimizer. Make another try:
3433
If range optimizer produced E(#rows) for a prefix of the ref
3434
access we're considering, and that E(#rows) is lower then our
3435
current estimate, make an adjustment. The criteria of when we
3436
can make an adjustment is a special case of the criteria used
3437
in ReuseRangeEstimateForRef-3.
3439
if (table->quick_keys.test(key) &&
3440
const_part & (1 << table->quick_key_parts[key]) &&
3441
table->quick_n_ranges[key] == 1 &&
3442
records > (double) table->quick_rows[key])
3444
records= (double) table->quick_rows[key];
3447
/* Limit the number of matched rows */
3449
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3450
if (table->covering_keys.test(key))
3452
/* we can use only index tree */
3453
tmp= record_count * table->file->index_only_read_time(key, tmp);
3456
tmp= record_count * min(tmp,s->worst_seeks);
3462
Use as much key-parts as possible and a uniq key is better
3463
than a not unique key
3464
Set tmp to (previous record count) * (records / combination)
3466
if ((found_part & 1) &&
3467
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
3468
found_part == PREV_BITS(uint,keyinfo->key_parts)))
3470
max_key_part= max_part_bit(found_part);
3472
ReuseRangeEstimateForRef-3:
3473
We're now considering a ref[or_null] access via
3474
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3475
(same-as-above but with one cond replaced
3476
with "t.keypart_i IS NULL")] (**)
3478
Try re-using E(#rows) from "range" optimizer:
3479
We can do so if "range" optimizer used the same intervals as
3480
in (**). The intervals used by range optimizer may be not
3481
available at this point (as "range" access might have choosen to
3482
create quick select over another index), so we can't compare
3483
them to (**). We'll make indirect judgements instead.
3484
The sufficient conditions for re-use are:
3485
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3486
this is not satisfied we have no way to know which ranges
3487
will be actually scanned by 'ref' until we execute the
3489
(C2) max #key parts in 'range' access == K == max_key_part (this
3490
is apparently a necessary requirement)
3492
We also have a property that "range optimizer produces equal or
3493
tighter set of scan intervals than ref(const) optimizer". Each
3494
of the intervals in (**) are "tightest possible" intervals when
3495
one limits itself to using keyparts 1..K (which we do in #2).
3496
From here it follows that range access used either one, or
3497
both of the (I1) and (I2) intervals:
3499
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3500
(same-as-above but with one cond replaced
3501
with "t.keypart_i IS NULL") (I2)
3503
The remaining part is to exclude the situation where range
3504
optimizer used one interval while we're considering
3505
ref-or-null and looking for estimate for two intervals. This
3506
is done by last limitation:
3508
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3510
if (table->quick_keys.test(key) && !found_ref && //(C1)
3511
table->quick_key_parts[key] == max_key_part && //(C2)
3512
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3514
tmp= records= (double) table->quick_rows[key];
3518
/* Check if we have statistic about the distribution */
3519
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3522
Fix for the case where the index statistics is too
3524
(1) We're considering ref(const) and there is quick select
3526
(2) and that quick select uses more keyparts (i.e. it will
3527
scan equal/smaller interval then this ref(const))
3528
(3) and E(#rows) for quick select is higher then our
3531
We'll use E(#rows) from quick select.
3533
Q: Why do we choose to use 'ref'? Won't quick select be
3534
cheaper in some cases ?
3535
TODO: figure this out and adjust the plan choice if needed.
3537
if (!found_ref && table->quick_keys.test(key) && // (1)
3538
table->quick_key_parts[key] > max_key_part && // (2)
3539
records < (double)table->quick_rows[key]) // (3)
3540
records= (double)table->quick_rows[key];
3547
Assume that the first key part matches 1% of the file
3548
and that the whole key matches 10 (duplicates) or 1
3550
Assume also that more key matches proportionally more
3552
This gives the formula:
3553
records = (x * (b-a) + a*c-b)/(c-1)
3555
b = records matched by whole key
3556
a = records matched by first key part (1% of all records?)
3557
c = number of key parts in key
3558
x = used key parts (1 <= x <= c)
3561
if (!(rec_per_key=(double)
3562
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3563
rec_per_key=(double) s->records/rec+1;
3567
else if (rec_per_key/(double) s->records >= 0.01)
3571
double a=s->records*0.01;
3572
if (keyinfo->key_parts > 1)
3573
tmp= (max_key_part * (rec_per_key - a) +
3574
a*keyinfo->key_parts - rec_per_key)/
3575
(keyinfo->key_parts-1);
3578
set_if_bigger(tmp,1.0);
3580
records = (uint32_t) tmp;
3583
if (ref_or_null_part)
3585
/* We need to do two key searches to find key */
3591
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3592
E(#rows) from range optimizer. Make another try:
3594
If range optimizer produced E(#rows) for a prefix of the ref
3595
access we're considering, and that E(#rows) is lower then our
3596
current estimate, make the adjustment.
3598
The decision whether we can re-use the estimate from the range
3599
optimizer is the same as in ReuseRangeEstimateForRef-3,
3600
applied to first table->quick_key_parts[key] key parts.
3602
if (table->quick_keys.test(key) &&
3603
table->quick_key_parts[key] <= max_key_part &&
3604
const_part & (1 << table->quick_key_parts[key]) &&
3605
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3606
const_part) ? 1 : 0) &&
3607
records > (double) table->quick_rows[key])
3609
tmp= records= (double) table->quick_rows[key];
3613
/* Limit the number of matched rows */
3614
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3615
if (table->covering_keys.test(key))
3617
/* we can use only index tree */
3618
tmp= record_count * table->file->index_only_read_time(key, tmp);
3621
tmp= record_count * min(tmp,s->worst_seeks);
3624
tmp= best_time; // Do nothing
3628
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3630
best_time= tmp + records/(double) TIME_FOR_COMPARE;
3632
best_records= records;
3633
best_key= start_key;
3634
best_max_key_part= max_key_part;
3635
best_ref_depends_map= found_ref;
3638
records= best_records;
3642
Don't test table scan if it can't be better.
3643
Prefer key lookup if we would use the same key for scanning.
3645
Don't do a table scan on InnoDB tables, if we can read the used
3646
parts of the row from any of the used index.
3647
This is because table scans uses index and we would not win
3648
anything by using a table scan.
3650
A word for word translation of the below if-statement in sergefp's
3651
understanding: we check if we should use table scan if:
3652
(1) The found 'ref' access produces more records than a table scan
3653
(or index scan, or quick select), or 'ref' is more expensive than
3655
(2) This doesn't hold: the best way to perform table scan is to to perform
3656
'range' access using index IDX, and the best way to perform 'ref'
3657
access is to use the same index IDX, with the same or more key parts.
3658
(note: it is not clear how this rule is/should be extended to
3659
index_merge quick selects)
3660
(3) See above note about InnoDB.
3661
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3662
path, but there is no quick select)
3663
If the condition in the above brackets holds, then the only possible
3664
"table scan" access method is ALL/index (there is no quick select).
3665
Since we have a 'ref' access path, and FORCE INDEX instructs us to
3666
choose it over ALL/index, there is no need to consider a full table
3669
if ((records >= s->found_records || best > s->read_time) && // (1)
3670
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
3671
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
3672
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
3673
! s->table->covering_keys.none() && best_key && !s->quick) &&// (3)
3674
!(s->table->force_index && best_key && !s->quick)) // (4)
3675
{ // Check full join
3676
ha_rows rnd_records= s->found_records;
3678
If there is a filtering condition on the table (i.e. ref analyzer found
3679
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3680
preceding this table in the join order we're now considering), then
3681
assume that 25% of the rows will be filtered out by this condition.
3683
This heuristic is supposed to force tables used in exprZ to be before
3684
this table in join order.
3686
if (found_constraint)
3687
rnd_records-= rnd_records/4;
3690
If applicable, get a more accurate estimate. Don't use the two
3693
if (s->table->quick_condition_rows != s->found_records)
3694
rnd_records= s->table->quick_condition_rows;
3697
Range optimizer never proposes a RANGE if it isn't better
3698
than FULL: so if RANGE is present, it's always preferred to FULL.
3699
Here we estimate its cost.
3705
- read record range through 'quick'
3706
- skip rows which does not satisfy WHERE constraints
3708
We take into account possible use of join cache for ALL/index
3709
access (see first else-branch below), but we don't take it into
3710
account here for range/index_merge access. Find out why this is so.
3713
(s->quick->read_time +
3714
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3718
/* Estimate cost of reading table. */
3719
tmp= s->table->file->scan_time();
3720
if (s->table->map & join->outer_join) // Can't use join cache
3723
For each record we have to:
3724
- read the whole table record
3725
- skip rows which does not satisfy join condition
3729
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
3733
/* We read the table as many times as join buffer becomes full. */
3734
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
3736
(double) session->variables.join_buff_size));
3738
We don't make full cartesian product between rows in the scanned
3739
table and existing records because we skip all rows from the
3740
scanned table, which does not satisfy join condition when
3741
we read the table (see flush_cached_records for details). Here we
3742
take into account cost to read and skip these records.
3744
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
3749
We estimate the cost of evaluating WHERE clause for found records
3750
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
3751
tmp give us total cost of using Table SCAN
3753
if (best == DBL_MAX ||
3754
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
3755
best + record_count/(double) TIME_FOR_COMPARE*records))
3758
If the table has a range (s->quick is set) make_join_select()
3759
will ensure that this will be used
3762
records= rows2double(rnd_records);
3764
/* range/index_merge/ALL/index access method are "independent", so: */
3765
best_ref_depends_map= 0;
3769
/* Update the cost information for the current partial plan */
3770
optimizer::Position tmp_pos(records,
3774
best_ref_depends_map);
3775
join->setPosInPartialPlan(idx, tmp_pos);
3778
idx == join->const_tables &&
3779
s->table == join->sort_by_table &&
3780
join->unit->select_limit_cnt >= records)
3781
join->sort_by_table= (Table*) 1; // Must use temporary table
3787
Select the best ways to access the tables in a query without reordering them.
3789
Find the best access paths for each query table and compute their costs
3790
according to their order in the array 'join->best_ref' (thus without
3791
reordering the join tables). The function calls sequentially
3792
'best_access_path' for each table in the query to select the best table
3793
access method. The final optimal plan is stored in the array
3794
'join->best_positions', and the corresponding cost in 'join->best_read'.
3796
@param join pointer to the structure providing all context info for
3798
@param join_tables set of the tables in the query
3801
This function can be applied to:
3802
- queries with STRAIGHT_JOIN
3803
- internally to compute the cost of an arbitrary QEP
3805
Thus 'optimize_straight_join' can be used at any stage of the query
3806
optimization process to finalize a QEP as it is.
3808
static void optimize_straight_join(JOIN *join, table_map join_tables)
3811
optimizer::Position partial_pos;
3812
uint32_t idx= join->const_tables;
3813
double record_count= 1.0;
3814
double read_time= 0.0;
3816
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
3818
/* Find the best access method from 's' to the current partial plan */
3819
best_access_path(join, s, join->session, join_tables, idx,
3820
record_count, read_time);
3821
/* compute the cost of the new plan extended with 's' */
3822
partial_pos= join->getPosFromPartialPlan(idx);
3823
record_count*= partial_pos.getFanout();
3824
read_time+= partial_pos.getCost();
3825
join_tables&= ~(s->table->map);
3829
read_time+= record_count / (double) TIME_FOR_COMPARE;
3830
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3831
if (join->sort_by_table &&
3832
partial_pos.hasTableForSorting(join->sort_by_table))
3833
read_time+= record_count; // We have to make a temp table
3834
join->copyPartialPlanIntoOptimalPlan(idx);
3835
join->best_read= read_time;
3839
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
3841
The search procedure uses a hybrid greedy/exhaustive search with controlled
3842
exhaustiveness. The search is performed in N = card(remaining_tables)
3843
steps. Each step evaluates how promising is each of the unoptimized tables,
3844
selects the most promising table, and extends the current partial QEP with
3845
that table. Currenly the most 'promising' table is the one with least
3846
expensive extension.\
3848
There are two extreme cases:
3849
-# When (card(remaining_tables) < search_depth), the estimate finds the
3850
best complete continuation of the partial QEP. This continuation can be
3851
used directly as a result of the search.
3852
-# When (search_depth == 1) the 'best_extension_by_limited_search'
3853
consideres the extension of the current QEP with each of the remaining
3856
All other cases are in-between these two extremes. Thus the parameter
3857
'search_depth' controlls the exhaustiveness of the search. The higher the
3858
value, the longer the optimizaton time and possibly the better the
3859
resulting plan. The lower the value, the fewer alternative plans are
3860
estimated, but the more likely to get a bad QEP.
3862
All intermediate and final results of the procedure are stored in 'join':
3863
- join->positions : modified for every partial QEP that is explored
3864
- join->best_positions: modified for the current best complete QEP
3865
- join->best_read : modified for the current best complete QEP
3866
- join->best_ref : might be partially reordered
3868
The final optimal plan is stored in 'join->best_positions', and its
3869
corresponding cost in 'join->best_read'.
3872
The following pseudocode describes the algorithm of 'greedy_search':
3875
procedure greedy_search
3876
input: remaining_tables
3881
(t, a) = best_extension(pplan, remaining_tables);
3882
pplan = concat(pplan, (t, a));
3883
remaining_tables = remaining_tables - t;
3884
} while (remaining_tables != {})
3889
where 'best_extension' is a placeholder for a procedure that selects the
3890
most "promising" of all tables in 'remaining_tables'.
3891
Currently this estimate is performed by calling
3892
'best_extension_by_limited_search' to evaluate all extensions of the
3893
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
3894
mainly depends on that of 'best_extension_by_limited_search'.
3897
If 'best_extension()' == 'best_extension_by_limited_search()', then the
3898
worst-case complexity of this algorithm is <=
3899
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
3900
complexity of greedy_search is O(N!).
3903
In the future, 'greedy_search' might be extended to support other
3904
implementations of 'best_extension', e.g. some simpler quadratic procedure.
3906
@param join pointer to the structure providing all context info
3908
@param remaining_tables set of tables not included into the partial plan yet
3909
@param search_depth controlls the exhaustiveness of the search
3910
@param prune_level the pruning heuristics that should be applied during
3918
static bool greedy_search(JOIN *join,
3919
table_map remaining_tables,
3920
uint32_t search_depth,
3921
uint32_t prune_level)
3923
double record_count= 1.0;
3924
double read_time= 0.0;
3925
uint32_t idx= join->const_tables; // index into 'join->best_ref'
3927
uint32_t size_remain; // cardinality of remaining_tables
3928
optimizer::Position best_pos;
3929
JoinTable *best_table; // the next plan node to be added to the curr QEP
3931
/* number of tables that remain to be optimized */
3932
size_remain= my_count_bits(remaining_tables);
3935
/* Find the extension of the current QEP with the lowest cost */
3936
join->best_read= DBL_MAX;
3937
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
3938
read_time, search_depth, prune_level))
3941
if (size_remain <= search_depth)
3944
'join->best_positions' contains a complete optimal extension of the
3945
current partial QEP.
3950
/* select the first table in the optimal extension as most promising */
3951
best_pos= join->getPosFromOptimalPlan(idx);
3952
best_table= best_pos.getJoinTable();
3954
Each subsequent loop of 'best_extension_by_limited_search' uses
3955
'join->positions' for cost estimates, therefore we have to update its
3958
join->setPosInPartialPlan(idx, best_pos);
3960
/* find the position of 'best_table' in 'join->best_ref' */
3962
JoinTable *pos= join->best_ref[best_idx];
3963
while (pos && best_table != pos)
3964
pos= join->best_ref[++best_idx];
3965
assert((pos != NULL)); // should always find 'best_table'
3966
/* move 'best_table' at the first free position in the array of joins */
3967
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
3969
/* compute the cost of the new plan extended with 'best_table' */
3970
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
3971
record_count*= partial_pos.getFanout();
3972
read_time+= partial_pos.getCost();
3974
remaining_tables&= ~(best_table->table->map);
3982
Find a good, possibly optimal, query execution plan (QEP) by a possibly
3985
The procedure searches for the optimal ordering of the query tables in set
3986
'remaining_tables' of size N, and the corresponding optimal access paths to
3987
each table. The choice of a table order and an access path for each table
3988
constitutes a query execution plan (QEP) that fully specifies how to
3991
The maximal size of the found plan is controlled by the parameter
3992
'search_depth'. When search_depth == N, the resulting plan is complete and
3993
can be used directly as a QEP. If search_depth < N, the found plan consists
3994
of only some of the query tables. Such "partial" optimal plans are useful
3995
only as input to query optimization procedures, and cannot be used directly
3998
The algorithm begins with an empty partial plan stored in 'join->positions'
3999
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4000
evaluates the cost of the partial plan extended by all access plans for
4001
each of the relations in 'remaining_tables', expands the current partial
4002
plan with the access plan that results in lowest cost of the expanded
4003
partial plan, and removes the corresponding relation from
4004
'remaining_tables'. The algorithm continues until it either constructs a
4005
complete optimal plan, or constructs an optimal plartial plan with size =
4008
The final optimal plan is stored in 'join->best_positions'. The
4009
corresponding cost of the optimal plan is in 'join->best_read'.
4012
The procedure uses a recursive depth-first search where the depth of the
4013
recursion (and thus the exhaustiveness of the search) is controlled by the
4014
parameter 'search_depth'.
4017
The pseudocode below describes the algorithm of
4018
'best_extension_by_limited_search'. The worst-case complexity of this
4019
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4020
the complexity of greedy_search is O(N!).
4023
procedure best_extension_by_limited_search(
4024
pplan in, // in, partial plan of tables-joined-so-far
4025
pplan_cost, // in, cost of pplan
4026
remaining_tables, // in, set of tables not referenced in pplan
4027
best_plan_so_far, // in/out, best plan found so far
4028
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4029
search_depth) // in, maximum size of the plans being considered
4031
for each table T from remaining_tables
4033
// Calculate the cost of using table T as above
4034
cost = complex-series-of-calculations;
4036
// Add the cost to the cost so far.
4039
if (pplan_cost >= best_plan_so_far_cost)
4040
// pplan_cost already too great, stop search
4043
pplan= expand pplan by best_access_method;
4044
remaining_tables= remaining_tables - table T;
4045
if (remaining_tables is not an empty set
4049
best_extension_by_limited_search(pplan, pplan_cost,
4052
best_plan_so_far_cost,
4057
best_plan_so_far_cost= pplan_cost;
4058
best_plan_so_far= pplan;
4065
When 'best_extension_by_limited_search' is called for the first time,
4066
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4067
The actual implementation provides a way to optionally use pruning
4068
heuristic (controlled by the parameter 'prune_level') to reduce the search
4069
space by skipping some partial plans.
4072
The parameter 'search_depth' provides control over the recursion
4073
depth, and thus the size of the resulting optimal plan.
4075
@param join pointer to the structure providing all context info
4077
@param remaining_tables set of tables not included into the partial plan yet
4078
@param idx length of the partial QEP in 'join->positions';
4079
since a depth-first search is used, also corresponds
4080
to the current depth of the search tree;
4081
also an index in the array 'join->best_ref';
4082
@param record_count estimate for the number of records returned by the
4084
@param read_time the cost of the best partial plan
4085
@param search_depth maximum depth of the recursion and thus size of the
4087
(0 < search_depth <= join->tables+1).
4088
@param prune_level pruning heuristics that should be applied during
4090
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4097
static bool best_extension_by_limited_search(JOIN *join,
4098
table_map remaining_tables,
4100
double record_count,
4102
uint32_t search_depth,
4103
uint32_t prune_level)
4105
Session *session= join->session;
4106
if (session->killed) // Abort
4110
'join' is a partial plan with lower cost than the best plan so far,
4111
so continue expanding it further with the tables in 'remaining_tables'.
4114
double best_record_count= DBL_MAX;
4115
double best_read_time= DBL_MAX;
4116
optimizer::Position partial_pos;
4118
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4120
table_map real_table_bit= s->table->map;
4123
partial_pos= join->getPosFromPartialPlan(idx - 1);
4125
if ((remaining_tables & real_table_bit) &&
4126
! (remaining_tables & s->dependent) &&
4127
(! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
4129
double current_record_count, current_read_time;
4132
psergey-insideout-todo:
4133
when best_access_path() detects it could do an InsideOut scan or
4134
some other scan, have it return an insideout scan and a flag that
4135
requests to "fork" this loop iteration. (Q: how does that behave
4136
when the depth is insufficient??)
4138
/* Find the best access method from 's' to the current partial plan */
4139
best_access_path(join, s, session, remaining_tables, idx,
4140
record_count, read_time);
4141
/* Compute the cost of extending the plan with 's' */
4142
partial_pos= join->getPosFromPartialPlan(idx);
4143
current_record_count= record_count * partial_pos.getFanout();
4144
current_read_time= read_time + partial_pos.getCost();
4146
/* Expand only partial plans with lower cost than the best QEP so far */
4147
if ((current_read_time +
4148
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4150
restore_prev_nj_state(s);
4155
Prune some less promising partial plans. This heuristic may miss
4156
the optimal QEPs, thus it results in a non-exhaustive search.
4158
if (prune_level == 1)
4160
if (best_record_count > current_record_count ||
4161
best_read_time > current_read_time ||
4162
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4164
if (best_record_count >= current_record_count &&
4165
best_read_time >= current_read_time &&
4166
/* TODO: What is the reasoning behind this condition? */
4167
(! (s->key_dependent & remaining_tables) ||
4168
partial_pos.isConstTable()))
4170
best_record_count= current_record_count;
4171
best_read_time= current_read_time;
4176
restore_prev_nj_state(s);
4181
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4182
{ /* Recursively expand the current partial plan */
4183
std::swap(join->best_ref[idx], *pos);
4184
if (best_extension_by_limited_search(join,
4185
remaining_tables & ~real_table_bit,
4187
current_record_count,
4192
std::swap(join->best_ref[idx], *pos);
4196
'join' is either the best partial QEP with 'search_depth' relations,
4197
or the best complete QEP so far, whichever is smaller.
4199
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4200
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4201
if (join->sort_by_table &&
4202
partial_pos.hasTableForSorting(join->sort_by_table))
4203
/* We have to make a temp table */
4204
current_read_time+= current_record_count;
4205
if ((search_depth == 1) || (current_read_time < join->best_read))
4207
join->copyPartialPlanIntoOptimalPlan(idx + 1);
4208
join->best_read= current_read_time - 0.001;
4211
restore_prev_nj_state(s);
4218
Heuristic procedure to automatically guess a reasonable degree of
4219
exhaustiveness for the greedy search procedure.
4221
The procedure estimates the optimization time and selects a search depth
4222
big enough to result in a near-optimal QEP, that doesn't take too long to
4223
find. If the number of tables in the query exceeds some constant, then
4224
search_depth is set to this constant.
4226
@param join pointer to the structure providing all context info for
4230
This is an extremely simplistic implementation that serves as a stub for a
4231
more advanced analysis of the join. Ideally the search depth should be
4232
determined by learning from previous query optimizations, because it will
4233
depend on the CPU power (and other factors).
4236
this value should be determined dynamically, based on statistics:
4237
uint32_t max_tables_for_exhaustive_opt= 7;
4240
this value could be determined by some mapping of the form:
4241
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4244
A positive integer that specifies the search depth (and thus the
4245
exhaustiveness) of the depth-first search algorithm used by
4248
static uint32_t determine_search_depth(JOIN *join)
4250
uint32_t table_count= join->tables - join->const_tables;
4251
uint32_t search_depth;
4252
/* TODO: this value should be determined dynamically, based on statistics: */
4253
uint32_t max_tables_for_exhaustive_opt= 7;
4255
if (table_count <= max_tables_for_exhaustive_opt)
4256
search_depth= table_count+1; // use exhaustive for small number of tables
4259
TODO: this value could be determined by some mapping of the form:
4260
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4262
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4264
return search_depth;
4267
static bool make_simple_join(JOIN *join,Table *tmp_table)
4270
JoinTable *join_tab;
4273
Reuse Table * and JoinTable if already allocated by a previous call
4274
to this function through JOIN::exec (may happen for sub-queries).
4276
if (!join->table_reexec)
4278
if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
4279
return(true); /* purecov: inspected */
4281
join->tmp_join->table_reexec= join->table_reexec;
4283
if (!join->join_tab_reexec)
4285
if (!(join->join_tab_reexec=
4286
(JoinTable*) join->session->alloc(sizeof(JoinTable))))
4287
return(true); /* purecov: inspected */
4289
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4291
tableptr= join->table_reexec;
4292
join_tab= join->join_tab_reexec;
4294
join->join_tab=join_tab;
4295
join->table=tableptr; tableptr[0]=tmp_table;
4297
join->const_tables=0;
4298
join->const_table_map=0;
4299
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4300
join->tmp_table_param.func_count=0;
4301
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4302
join->first_record=join->sort_and_group=0;
4303
join->send_records=(ha_rows) 0;
4305
join->row_limit=join->unit->select_limit_cnt;
4306
join->do_send_rows = (join->row_limit) ? 1 : 0;
4308
join_tab->cache.buff=0; /* No caching */
4309
join_tab->table=tmp_table;
4311
join_tab->select_cond=0;
4313
join_tab->type= AM_ALL; /* Map through all records */
4314
join_tab->keys.set(); /* test everything in quick */
4316
join_tab->on_expr_ref=0;
4317
join_tab->last_inner= 0;
4318
join_tab->first_unmatched= 0;
4319
join_tab->ref.key = -1;
4320
join_tab->not_used_in_distinct=0;
4321
join_tab->read_first_record= join_init_read_record;
4322
join_tab->join=join;
4323
join_tab->ref.key_parts= 0;
4324
memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4325
tmp_table->status=0;
4326
tmp_table->null_row=0;
4331
Fill in outer join related info for the execution plan structure.
4333
For each outer join operation left after simplification of the
4334
original query the function set up the following pointers in the linear
4335
structure join->join_tab representing the selected execution plan.
4336
The first inner table t0 for the operation is set to refer to the last
4337
inner table tk through the field t0->last_inner.
4338
Any inner table ti for the operation are set to refer to the first
4339
inner table ti->first_inner.
4340
The first inner table t0 for the operation is set to refer to the
4341
first inner table of the embedding outer join operation, if there is any,
4342
through the field t0->first_upper.
4343
The on expression for the outer join operation is attached to the
4344
corresponding first inner table through the field t0->on_expr_ref.
4345
Here ti are structures of the JoinTable type.
4347
EXAMPLE. For the query:
4351
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4352
ON (t1.a=t2.a AND t1.b=t3.b)
4356
given the execution plan with the table order t1,t2,t3,t4
4357
is selected, the following references will be set;
4358
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4359
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4360
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4361
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4363
@param join reference to the info fully describing the query
4366
The function assumes that the simplification procedure has been
4367
already applied to the join query (see simplify_joins).
4368
This function can be called only after the execution plan
4371
static void make_outerjoin_info(JOIN *join)
4373
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4375
JoinTable *tab=join->join_tab+i;
4376
Table *table=tab->table;
4377
TableList *tbl= table->pos_in_table_list;
4378
TableList *embedding= tbl->embedding;
4380
if (tbl->outer_join)
4383
Table tab is the only one inner table for outer join.
4384
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4385
is in the query above.)
4387
tab->last_inner= tab->first_inner= tab;
4388
tab->on_expr_ref= &tbl->on_expr;
4389
tab->cond_equal= tbl->cond_equal;
4391
tab->first_upper= embedding->nested_join->first_nested;
4393
for ( ; embedding ; embedding= embedding->embedding)
4395
/* Ignore sj-nests: */
4396
if (!embedding->on_expr)
4398
nested_join_st *nested_join= embedding->nested_join;
4399
if (!nested_join->counter_)
4402
Table tab is the first inner table for nested_join.
4403
Save reference to it in the nested join structure.
4405
nested_join->first_nested= tab;
4406
tab->on_expr_ref= &embedding->on_expr;
4407
tab->cond_equal= tbl->cond_equal;
4408
if (embedding->embedding)
4409
tab->first_upper= embedding->embedding->nested_join->first_nested;
4411
if (!tab->first_inner)
4412
tab->first_inner= nested_join->first_nested;
4413
if (++nested_join->counter_ < nested_join->join_list.elements)
4415
/* Table tab is the last inner table for nested join. */
4416
nested_join->first_nested->last_inner= tab;
4422
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
4424
Session *session= join->session;
4425
optimizer::Position cur_pos;
4428
add_not_null_conds(join);
4429
table_map used_tables;
4430
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4431
{ /* there may be a select without a cond. */
4432
if (join->tables > 1)
4433
cond->update_used_tables(); // Tablenr may have changed
4434
if (join->const_tables == join->tables &&
4435
session->lex->current_select->master_unit() ==
4436
&session->lex->unit) // not upper level SELECT
4437
join->const_table_map|=RAND_TABLE_BIT;
4438
{ // Check const tables
4440
make_cond_for_table(cond,
4441
join->const_table_map,
4443
for (JoinTable *tab= join->join_tab+join->const_tables;
4444
tab < join->join_tab+join->tables ; tab++)
4446
if (*tab->on_expr_ref)
4448
JoinTable *cond_tab= tab->first_inner;
4449
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4450
join->const_table_map,
4454
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4457
tmp->quick_fix_field();
4458
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4459
new Item_cond_and(cond_tab->select_cond,
4461
if (! cond_tab->select_cond)
4463
cond_tab->select_cond->quick_fix_field();
4466
if (const_cond && ! const_cond->val_int())
4468
return 1; // Impossible const condition
4472
used_tables=((select->const_tables=join->const_table_map) |
4473
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4474
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4476
JoinTable *tab=join->join_tab+i;
4478
first_inner is the X in queries like:
4479
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4481
JoinTable *first_inner_tab= tab->first_inner;
4482
table_map current_map= tab->table->map;
4483
bool use_quick_range=0;
4487
Following force including random expression in last table condition.
4488
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4490
if (i == join->tables-1)
4491
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4492
used_tables|=current_map;
4494
if (tab->type == AM_REF && tab->quick &&
4495
(uint32_t) tab->ref.key == tab->quick->index &&
4496
tab->ref.key_length < tab->quick->max_used_key_length)
4498
/* Range uses longer key; Use this instead of ref on key */
4503
tab->ref.key_parts= 0; // Don't use ref key.
4504
cur_pos= join->getPosFromOptimalPlan(i);
4505
cur_pos.setFanout(rows2double(tab->quick->records));
4507
We will use join cache here : prevent sorting of the first
4508
table only and sort at the end.
4510
if (i != join->const_tables && join->tables > join->const_tables + 1)
4516
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4517
if (cond && !tmp && tab->quick)
4519
if (tab->type != AM_ALL)
4522
Don't use the quick method
4523
We come here in the case where we have 'key=constant' and
4524
the test is removed by make_cond_for_table()
4532
Hack to handle the case where we only refer to a table
4533
in the ON part of an OUTER JOIN. In this case we want the code
4534
below to check if we should use 'quick' instead.
4536
tmp= new Item_int((int64_t) 1,1); // Always true
4540
if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4541
tab->type == AM_EQ_REF)
4543
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
4544
session->memdup((unsigned char*) select,
4547
return 1; // End of memory
4549
If tab is an inner table of an outer join operation,
4550
add a match guard to the pushed down predicate.
4551
The guard will turn the predicate on only after
4552
the first match for outer tables is encountered.
4557
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4558
a cond, so neutralize the hack above.
4560
if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4562
tab->select_cond=sel->cond=tmp;
4565
tab->select_cond= sel->cond= NULL;
4567
sel->head=tab->table;
4570
/* Use quick key read if it's a constant and it's not used
4572
if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4573
&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4575
sel->quick=tab->quick; // Use value from get_quick_...
4576
sel->quick_keys.reset();
4577
sel->needed_reg.reset();
4585
uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4586
if (i == join->const_tables && ref_key)
4588
if (tab->const_keys.any() &&
4589
tab->table->reginfo.impossible_range)
4592
else if (tab->type == AM_ALL && ! use_quick_range)
4594
if (tab->const_keys.any() &&
4595
tab->table->reginfo.impossible_range)
4596
return 1; // Impossible range
4598
We plan to scan all rows.
4599
Check again if we should use an index.
4600
We could have used an column from a previous table in
4601
the index if we are using limit and this is the first table
4604
cur_pos= join->getPosFromOptimalPlan(i);
4605
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4606
(! tab->const_keys.none() && (i == join->const_tables) &&
4607
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4609
/* Join with outer join condition */
4610
COND *orig_cond= sel->cond;
4611
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4614
We can't call sel->cond->fix_fields,
4615
as it will break tab->on_expr if it's AND condition
4616
(fix_fields currently removes extra AND/OR levels).
4617
Yet attributes of the just built condition are not needed.
4618
Thus we call sel->cond->quick_fix_field for safety.
4620
if (sel->cond && ! sel->cond->fixed)
4621
sel->cond->quick_fix_field();
4623
if (sel->test_quick_select(session, tab->keys,
4624
used_tables & ~ current_map,
4625
(join->select_options &
4628
join->unit->select_limit_cnt), 0,
4632
Before reporting "Impossible WHERE" for the whole query
4633
we have to check isn't it only "impossible ON" instead
4635
sel->cond=orig_cond;
4636
if (! *tab->on_expr_ref ||
4637
sel->test_quick_select(session, tab->keys,
4638
used_tables & ~ current_map,
4639
(join->select_options &
4642
join->unit->select_limit_cnt),0,
4644
return 1; // Impossible WHERE
4647
sel->cond=orig_cond;
4649
/* Fix for EXPLAIN */
4652
cur_pos= join->getPosFromOptimalPlan(i);
4653
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4658
sel->needed_reg= tab->needed_reg;
4659
sel->quick_keys.reset();
4661
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4662
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4664
tab->keys= sel->quick_keys;
4665
tab->keys|= sel->needed_reg;
4666
tab->use_quick= (!sel->needed_reg.none() &&
4667
(select->quick_keys.none() ||
4669
(select->quick->records >= 100L)))) ?
4671
sel->read_tables= used_tables & ~current_map;
4673
if (i != join->const_tables && tab->use_quick != 2)
4674
{ /* Read with cache */
4676
(tmp=make_cond_for_table(cond,
4677
join->const_table_map |
4681
tab->cache.select= (SQL_SELECT*)
4682
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
4683
tab->cache.select->cond= tmp;
4684
tab->cache.select->read_tables= join->const_table_map;
4691
Push down conditions from all on expressions.
4692
Each of these conditions are guarded by a variable
4693
that turns if off just before null complemented row for
4694
outer joins is formed. Thus, the condition from an
4695
'on expression' are guaranteed not to be checked for
4696
the null complemented row.
4699
/* First push down constant conditions from on expressions */
4700
for (JoinTable *join_tab= join->join_tab+join->const_tables;
4701
join_tab < join->join_tab+join->tables ; join_tab++)
4703
if (*join_tab->on_expr_ref)
4705
JoinTable *cond_tab= join_tab->first_inner;
4706
tmp= make_cond_for_table(*join_tab->on_expr_ref,
4707
join->const_table_map,
4711
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4714
tmp->quick_fix_field();
4715
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4716
new Item_cond_and(cond_tab->select_cond,tmp);
4717
if (! cond_tab->select_cond)
4719
cond_tab->select_cond->quick_fix_field();
4723
/* Push down non-constant conditions from on expressions */
4724
JoinTable *last_tab= tab;
4725
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
4728
Table tab is the last inner table of an outer join.
4729
An on expression is always attached to it.
4731
COND *on_expr= *first_inner_tab->on_expr_ref;
4733
table_map used_tables2= (join->const_table_map |
4734
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4735
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
4737
current_map= tab->table->map;
4738
used_tables2|= current_map;
4739
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
4743
JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
4745
First add the guards for match variables of
4746
all embedding outer join operations.
4748
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
4753
Now add the guard turning the predicate off for
4754
the null complemented row.
4756
tmp_cond= new Item_func_trig_cond(tmp_cond,
4760
tmp_cond->quick_fix_field();
4761
/* Add the predicate to other pushed down predicates */
4762
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
4763
new Item_cond_and(cond_tab->select_cond,
4765
if (! cond_tab->select_cond)
4767
cond_tab->select_cond->quick_fix_field();
4770
first_inner_tab= first_inner_tab->first_upper;
4778
Plan refinement stage: do various set ups for the executioner
4781
make_join_readinfo()
4782
join Join being processed
4783
options Join's options (checking for SELECT_DESCRIBE,
4784
SELECT_NO_JOIN_CACHE)
4785
no_jbuf_after Don't use join buffering after table with this number.
4788
Plan refinement stage: do various set ups for the executioner
4789
- set up use of join buffering
4790
- push index conditions
4791
- increment counters
4796
true - Out of memory
4798
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
4801
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
4804
for (i=join->const_tables ; i < join->tables ; i++)
4806
JoinTable *tab=join->join_tab+i;
4807
Table *table=tab->table;
4808
bool using_join_cache;
4809
tab->read_record.table= table;
4810
tab->read_record.file=table->file;
4811
tab->next_select=sub_select; /* normal select */
4813
TODO: don't always instruct first table's ref/range access method to
4814
produce sorted output.
4816
tab->sorted= sorted;
4817
sorted= 0; // only first must be sorted
4818
if (tab->insideout_match_tab)
4820
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
4825
switch (tab->type) {
4826
case AM_SYSTEM: // Only happens with left join
4827
table->status=STATUS_NO_RECORD;
4828
tab->read_first_record= join_read_system;
4829
tab->read_record.read_record= join_no_more_records;
4831
case AM_CONST: // Only happens with left join
4832
table->status=STATUS_NO_RECORD;
4833
tab->read_first_record= join_read_const;
4834
tab->read_record.read_record= join_no_more_records;
4835
if (table->covering_keys.test(tab->ref.key) &&
4839
table->file->extra(HA_EXTRA_KEYREAD);
4843
table->status=STATUS_NO_RECORD;
4846
delete tab->select->quick;
4847
tab->select->quick=0;
4851
tab->read_first_record= join_read_key;
4852
tab->read_record.read_record= join_no_more_records;
4853
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4856
table->file->extra(HA_EXTRA_KEYREAD);
4859
case AM_REF_OR_NULL:
4861
table->status=STATUS_NO_RECORD;
4864
delete tab->select->quick;
4865
tab->select->quick=0;
4869
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4872
table->file->extra(HA_EXTRA_KEYREAD);
4874
if (tab->type == AM_REF)
4876
tab->read_first_record= join_read_always_key;
4877
tab->read_record.read_record= tab->insideout_match_tab?
4878
join_read_next_same_diff : join_read_next_same;
4882
tab->read_first_record= join_read_always_key_or_null;
4883
tab->read_record.read_record= join_read_next_same_or_null;
4888
If previous table use cache
4889
If the incoming data set is already sorted don't use cache.
4891
table->status=STATUS_NO_RECORD;
4892
using_join_cache= false;
4893
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
4894
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
4895
!tab->insideout_match_tab)
4897
if ((options & SELECT_DESCRIBE) ||
4898
!join_init_cache(join->session,join->join_tab+join->const_tables,
4899
i-join->const_tables))
4901
using_join_cache= true;
4902
tab[-1].next_select=sub_select_cache; /* Patch previous */
4905
/* These init changes read_record */
4906
if (tab->use_quick == 2)
4908
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
4909
tab->read_first_record= join_init_quick_read_record;
4911
status_var_increment(join->session->status_var.select_range_check_count);
4915
tab->read_first_record= join_init_read_record;
4916
if (i == join->const_tables)
4918
if (tab->select && tab->select->quick)
4921
status_var_increment(join->session->status_var.select_range_count);
4925
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
4927
status_var_increment(join->session->status_var.select_scan_count);
4932
if (tab->select && tab->select->quick)
4935
status_var_increment(join->session->status_var.select_full_range_join_count);
4939
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
4941
status_var_increment(join->session->status_var.select_full_join_count);
4944
if (!table->no_keyread)
4946
if (tab->select && tab->select->quick &&
4947
tab->select->quick->index != MAX_KEY && //not index_merge
4948
table->covering_keys.test(tab->select->quick->index))
4951
table->file->extra(HA_EXTRA_KEYREAD);
4953
else if (!table->covering_keys.none() &&
4954
!(tab->select && tab->select->quick))
4955
{ // Only read index tree
4956
if (!tab->insideout_match_tab)
4959
See bug #26447: "Using the clustered index for a table scan
4960
is always faster than using a secondary index".
4962
if (table->s->primary_key != MAX_KEY &&
4963
table->file->primary_key_is_clustered())
4964
tab->index= table->s->primary_key;
4966
tab->index= table->find_shortest_key(&table->covering_keys);
4968
tab->read_first_record= join_read_first;
4969
tab->type= AM_NEXT; // Read with index_first / index_next
4975
break; /* purecov: deadcode */
4978
abort(); /* purecov: deadcode */
4981
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
4985
/** Update the dependency map for the tables. */
4986
static void update_depend_map(JOIN *join)
4988
JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
4990
for (; join_tab != end ; join_tab++)
4992
table_reference_st *ref= &join_tab->ref;
4993
table_map depend_map= 0;
4994
Item **item=ref->items;
4996
for (i=0 ; i < ref->key_parts ; i++,item++)
4997
depend_map|=(*item)->used_tables();
4998
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
4999
depend_map&= ~OUTER_REF_TABLE_BIT;
5000
for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5003
ref->depend_map|=(*tab)->ref.depend_map;
5008
/** Update the dependency map for the sort order. */
5009
static void update_depend_map(JOIN *join, order_st *order)
5011
for (; order ; order=order->next)
5013
table_map depend_map;
5014
order->item[0]->update_used_tables();
5015
order->depend_map=depend_map=order->item[0]->used_tables();
5016
// Not item_sum(), RAND() and no reference to table outside of sub select
5017
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5018
&& !order->item[0]->with_sum_func)
5020
for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5023
order->depend_map|=(*tab)->ref.depend_map;
5030
Remove all constants and check if order_st only contains simple
5033
simple_order is set to 1 if sort_order only uses fields from head table
5034
and the head table is not a LEFT JOIN table.
5036
@param join Join handler
5037
@param first_order List of SORT or GROUP order
5038
@param cond WHERE statement
5039
@param change_list Set to 1 if we should remove things from list.
5040
If this is not set, then only simple_order is
5042
@param simple_order Set to 1 if we are only using simple expressions
5045
Returns new sort order
5047
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5049
if (join->tables == join->const_tables)
5050
return change_list ? 0 : first_order; // No need to sort
5052
order_st *order,**prev_ptr;
5053
table_map first_table= join->join_tab[join->const_tables].table->map;
5054
table_map not_const_tables= ~join->const_table_map;
5057
prev_ptr= &first_order;
5058
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5060
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5062
update_depend_map(join, first_order);
5063
for (order=first_order; order ; order=order->next)
5065
table_map order_tables=order->item[0]->used_tables();
5066
if (order->item[0]->with_sum_func)
5067
*simple_order=0; // Must do a temp table to sort
5068
else if (!(order_tables & not_const_tables))
5070
if (order->item[0]->with_subselect)
5071
order->item[0]->val_str(&order->item[0]->str_value);
5072
continue; // skip const item
5076
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5081
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5085
if ((ref=order_tables & (not_const_tables ^ first_table)))
5087
if (!(order_tables & first_table) &&
5088
only_eq_ref_tables(join,first_order, ref))
5092
*simple_order=0; // Must do a temp table to sort
5097
*prev_ptr= order; // use this entry
5098
prev_ptr= &order->next;
5102
if (prev_ptr == &first_order) // Nothing to sort/group
5104
return(first_order);
5107
static int return_zero_rows(JOIN *join,
5108
select_result *result,
5112
uint64_t select_options,
5116
if (select_options & SELECT_DESCRIBE)
5118
select_describe(join, false, false, false, info);
5126
for (TableList *table= tables; table; table= table->next_leaf)
5127
table->table->mark_as_null_row(); // All fields are NULL
5128
if (having && having->val_int() == 0)
5131
if (! (result->send_fields(fields)))
5135
List_iterator_fast<Item> it(fields);
5137
while ((item= it++))
5138
item->no_rows_in_result();
5139
result->send_data(fields);
5141
result->send_eof(); // Should be safe
5143
/* Update results for FOUND_ROWS */
5144
join->session->limit_found_rows= join->session->examined_row_count= 0;
5149
Simplify joins replacing outer joins by inner joins whenever it's
5152
The function, during a retrieval of join_list, eliminates those
5153
outer joins that can be converted into inner join, possibly nested.
5154
It also moves the on expressions for the converted outer joins
5155
and from inner joins to conds.
5156
The function also calculates some attributes for nested joins:
5160
- on_expr_dep_tables
5161
The first two attributes are used to test whether an outer join can
5162
be substituted for an inner join. The third attribute represents the
5163
relation 'to be dependent on' for tables. If table t2 is dependent
5164
on table t1, then in any evaluated execution plan table access to
5165
table t2 must precede access to table t2. This relation is used also
5166
to check whether the query contains invalid cross-references.
5167
The forth attribute is an auxiliary one and is used to calculate
5169
As the attribute dep_tables qualifies possibles orders of tables in the
5170
execution plan, the dependencies required by the straight join
5171
modifiers are reflected in this attribute as well.
5172
The function also removes all braces that can be removed from the join
5173
expression without changing its meaning.
5176
An outer join can be replaced by an inner join if the where condition
5177
or the on expression for an embedding nested join contains a conjunctive
5178
predicate rejecting null values for some attribute of the inner tables.
5182
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5184
the predicate t2.b < 5 rejects nulls.
5185
The query is converted first to:
5187
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5189
then to the equivalent form:
5191
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5195
Similarly the following query:
5197
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5202
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5206
One conversion might trigger another:
5208
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5209
LEFT JOIN t3 ON t3.b=t2.b
5210
WHERE t3 IS NOT NULL =>
5211
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5212
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5213
SELECT * FROM t1, t2, t3
5214
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5217
The function removes all unnecessary braces from the expression
5218
produced by the conversions.
5221
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5223
finally is converted to:
5225
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5230
It also will remove braces from the following queries:
5232
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5233
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5236
The benefit of this simplification procedure is that it might return
5237
a query for which the optimizer can evaluate execution plan with more
5238
join orders. With a left join operation the optimizer does not
5239
consider any plan where one of the inner tables is before some of outer
5243
The function is implemented by a recursive procedure. On the recursive
5244
ascent all attributes are calculated, all outer joins that can be
5245
converted are replaced and then all unnecessary braces are removed.
5246
As join list contains join tables in the reverse order sequential
5247
elimination of outer joins does not require extra recursive calls.
5250
Remove all semi-joins that have are within another semi-join (i.e. have
5251
an "ancestor" semi-join nest)
5254
Here is an example of a join query with invalid cross references:
5256
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5259
@param join reference to the query info
5260
@param join_list list representation of the join to be converted
5261
@param conds conditions to add on expressions for converted joins
5262
@param top true <=> conds is the where condition
5265
- The new condition, if success
5268
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5271
nested_join_st *nested_join;
5272
TableList *prev_table= 0;
5273
List_iterator<TableList> li(*join_list);
5276
Try to simplify join operations from join_list.
5277
The most outer join operation is checked for conversion first.
5279
while ((table= li++))
5281
table_map used_tables;
5282
table_map not_null_tables= (table_map) 0;
5284
if ((nested_join= table->nested_join))
5287
If the element of join_list is a nested join apply
5288
the procedure to its nested join list first.
5292
Item *expr= table->on_expr;
5294
If an on expression E is attached to the table,
5295
check all null rejected predicates in this expression.
5296
If such a predicate over an attribute belonging to
5297
an inner table of an embedded outer join is found,
5298
the outer join is converted to an inner join and
5299
the corresponding on expression is added to E.
5301
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5303
if (!table->prep_on_expr || expr != table->on_expr)
5307
table->on_expr= expr;
5308
table->prep_on_expr= expr->copy_andor_structure(join->session);
5311
nested_join->used_tables= (table_map) 0;
5312
nested_join->not_null_tables=(table_map) 0;
5313
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5314
used_tables= nested_join->used_tables;
5315
not_null_tables= nested_join->not_null_tables;
5319
if (!table->prep_on_expr)
5320
table->prep_on_expr= table->on_expr;
5321
used_tables= table->table->map;
5323
not_null_tables= conds->not_null_tables();
5326
if (table->embedding)
5328
table->embedding->nested_join->used_tables|= used_tables;
5329
table->embedding->nested_join->not_null_tables|= not_null_tables;
5332
if (!table->outer_join || (used_tables & not_null_tables))
5335
For some of the inner tables there are conjunctive predicates
5336
that reject nulls => the outer join can be replaced by an inner join.
5338
table->outer_join= 0;
5341
/* Add ON expression to the WHERE or upper-level ON condition. */
5344
conds= and_conds(conds, table->on_expr);
5345
conds->top_level_item();
5346
/* conds is always a new item as both cond and on_expr existed */
5347
assert(!conds->fixed);
5348
conds->fix_fields(join->session, &conds);
5351
conds= table->on_expr;
5352
table->prep_on_expr= table->on_expr= 0;
5360
Only inner tables of non-convertible outer joins
5361
remain with on_expr.
5365
table->dep_tables|= table->on_expr->used_tables();
5366
if (table->embedding)
5368
table->dep_tables&= ~table->embedding->nested_join->used_tables;
5370
Embedding table depends on tables used
5371
in embedded on expressions.
5373
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5376
table->dep_tables&= ~table->table->map;
5381
/* The order of tables is reverse: prev_table follows table */
5382
if (prev_table->straight)
5383
prev_table->dep_tables|= used_tables;
5384
if (prev_table->on_expr)
5386
prev_table->dep_tables|= table->on_expr_dep_tables;
5387
table_map prev_used_tables= prev_table->nested_join ?
5388
prev_table->nested_join->used_tables :
5389
prev_table->table->map;
5391
If on expression contains only references to inner tables
5392
we still make the inner tables dependent on the outer tables.
5393
It would be enough to set dependency only on one outer table
5394
for them. Yet this is really a rare case.
5396
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5397
prev_table->dep_tables|= used_tables;
5404
Flatten nested joins that can be flattened.
5405
no ON expression and not a semi-join => can be flattened.
5408
while ((table= li++))
5410
nested_join= table->nested_join;
5411
if (nested_join && !table->on_expr)
5414
List_iterator<TableList> it(nested_join->join_list);
5417
tbl->embedding= table->embedding;
5418
tbl->join_list= table->join_list;
5420
li.replace(nested_join->join_list);
5426
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5429
uint32_t reclength,offset;
5430
uint32_t field_count;
5431
Session *session= join->session;
5433
entry->reginfo.lock_type=TL_WRITE;
5435
/* Calculate how many saved fields there is in list */
5437
List_iterator<Item> it(fields);
5441
if (item->get_tmp_table_field() && ! item->const_item())
5445
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5446
{ // only const items with no OPTION_FOUND_ROWS
5447
join->unit->select_limit_cnt= 1; // Only send first row
5450
Field **first_field=entry->field+entry->s->fields - field_count;
5451
offset= (field_count ?
5452
entry->field[entry->s->fields - field_count]->
5453
offset(entry->record[0]) : 0);
5454
reclength= entry->s->reclength-offset;
5456
entry->free_io_cache(); // Safety
5457
entry->file->info(HA_STATUS_VARIABLE);
5458
if (entry->s->db_type() == heap_engine ||
5459
(!entry->s->blob_fields &&
5460
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->file->stats.records <
5461
session->variables.sortbuff_size)))
5462
error= remove_dup_with_hash_index(join->session, entry,
5463
field_count, first_field,
5466
error= remove_dup_with_compare(join->session, entry, first_field, offset,
5469
free_blobs(first_field);
5474
Function to setup clauses without sum functions.
5476
static int setup_without_group(Session *session,
5477
Item **ref_pointer_array,
5481
List<Item> &all_fields,
5485
bool *hidden_group_fields)
5488
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
5490
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5491
res= session->setup_conds(tables, conds);
5493
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
5494
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5496
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5497
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5498
group, hidden_group_fields);
5499
session->lex->allow_sum_func= save_allow_sum_func;
5504
Calculate the best possible join and initialize the join structure.
5511
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5515
uint32_t i,table_count,const_count,key;
5516
table_map found_const_table_map, all_table_map, found_ref, refs;
5517
key_map const_ref, eq_part;
5518
Table **table_vector;
5519
JoinTable *stat,*stat_end,*s,**stat_ref;
5520
KeyUse *keyuse,*start_keyuse;
5521
table_map outer_join=0;
5522
vector<optimizer::SargableParam> sargables;
5523
JoinTable *stat_vector[MAX_TABLES+1];
5524
optimizer::Position *partial_pos;
5526
table_count=join->tables;
5527
stat=(JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5528
stat_ref=(JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);
5529
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5530
if (! stat || ! stat_ref || ! table_vector)
5531
return 1; // Eom /* purecov: inspected */
5533
join->best_ref=stat_vector;
5535
stat_end=stat+table_count;
5536
found_const_table_map= all_table_map=0;
5541
s++, tables= tables->next_leaf, i++)
5543
TableList *embedding= tables->embedding;
5546
s->const_keys.reset();
5547
s->checked_keys.reset();
5548
s->needed_reg.reset();
5549
table_vector[i]=s->table=table=tables->table;
5550
table->pos_in_table_list= tables;
5551
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5554
table->file->print_error(error, MYF(0));
5557
table->quick_keys.reset();
5558
table->reginfo.join_tab=s;
5559
table->reginfo.not_exists_optimize=0;
5560
memset(table->const_key_parts, 0,
5561
sizeof(key_part_map)*table->s->keys);
5562
all_table_map|= table->map;
5564
s->info=0; // For describe
5566
s->dependent= tables->dep_tables;
5567
s->key_dependent= 0;
5568
if (tables->schema_table)
5569
table->file->stats.records= 2;
5570
table->quick_condition_rows= table->file->stats.records;
5572
s->on_expr_ref= &tables->on_expr;
5573
if (*s->on_expr_ref)
5575
/* s is the only inner table of an outer join */
5576
if (!table->file->stats.records && !embedding)
5578
s->dependent= 0; // Ignore LEFT JOIN depend.
5579
set_position(join,const_count++,s,(KeyUse*) 0);
5582
outer_join|= table->map;
5583
s->embedding_map.reset();
5584
for (;embedding; embedding= embedding->embedding)
5585
s->embedding_map|= embedding->nested_join->nj_map;
5588
if (embedding && !(false && ! embedding->embedding))
5590
/* s belongs to a nested join, maybe to several embedded joins */
5591
s->embedding_map.reset();
5594
nested_join_st *nested_join= embedding->nested_join;
5595
s->embedding_map|= nested_join->nj_map;
5596
s->dependent|= embedding->dep_tables;
5597
embedding= embedding->embedding;
5598
outer_join|= nested_join->used_tables;
5603
if ((table->file->stats.records <= 1) && !s->dependent &&
5604
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
5605
!join->no_const_tables)
5607
set_position(join,const_count++,s,(KeyUse*) 0);
5611
join->outer_join=outer_join;
5613
if (join->outer_join)
5616
Build transitive closure for relation 'to be dependent on'.
5617
This will speed up the plan search for many cases with outer joins,
5618
as well as allow us to catch illegal cross references/
5619
Warshall's algorithm is used to build the transitive closure.
5620
As we use bitmaps to represent the relation the complexity
5621
of the algorithm is O((number of tables)^2).
5623
for (i= 0, s= stat ; i < table_count ; i++, s++)
5625
for (uint32_t j= 0 ; j < table_count ; j++)
5627
table= stat[j].table;
5628
if (s->dependent & table->map)
5629
s->dependent |= table->reginfo.join_tab->dependent;
5632
s->table->maybe_null= 1;
5634
/* Catch illegal cross references for outer joins */
5635
for (i= 0, s= stat ; i < table_count ; i++, s++)
5637
if (s->dependent & s->table->map)
5639
join->tables=0; // Don't use join->table
5640
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5643
s->key_dependent= s->dependent;
5647
if (conds || outer_join)
5648
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5649
conds, join->cond_equal,
5650
~outer_join, join->select_lex, sargables))
5653
/* Read tables with 0 or 1 rows (system tables) */
5654
join->const_table_map= 0;
5656
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5657
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5658
while (p_pos < p_end)
5661
s= p_pos->getJoinTable();
5663
join->const_table_map|=s->table->map;
5664
if ((tmp= join_read_const_table(s, p_pos)))
5667
return 1; // Fatal error
5670
found_const_table_map|= s->table->map;
5674
/* loop until no more const tables are found */
5678
more_const_tables_found:
5683
We only have to loop from stat_vector + const_count as
5684
set_position() will move all const_tables first in stat_vector
5687
for (JoinTable **pos=stat_vector+const_count ; (s= *pos) ; pos++)
5692
If equi-join condition by a key is null rejecting and after a
5693
substitution of a const table the key value happens to be null
5694
then we can state that there are no matches for this equi-join.
5696
if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5699
When performing an outer join operation if there are no matching rows
5700
for the single row of the outer table all the inner tables are to be
5701
null complemented and thus considered as constant tables.
5702
Here we apply this consideration to the case of outer join operations
5703
with a single inner table only because the case with nested tables
5704
would require a more thorough analysis.
5705
TODO. Apply single row substitution to null complemented inner tables
5706
for nested outer join operations.
5708
while (keyuse->table == table)
5710
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
5711
keyuse->val->is_null() && keyuse->null_rejecting)
5714
table->mark_as_null_row();
5715
found_const_table_map|= table->map;
5716
join->const_table_map|= table->map;
5717
set_position(join,const_count++,s,(KeyUse*) 0);
5718
goto more_const_tables_found;
5724
if (s->dependent) // If dependent on some table
5726
// All dep. must be constants
5727
if (s->dependent & ~(found_const_table_map))
5729
if (table->file->stats.records <= 1L &&
5730
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
5731
!table->pos_in_table_list->embedding)
5735
join->const_table_map|=table->map;
5736
set_position(join,const_count++,s,(KeyUse*) 0);
5737
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5738
if ((tmp= join_read_const_table(s, partial_pos)))
5741
return 1; // Fatal error
5744
found_const_table_map|= table->map;
5748
/* check if table can be read by key or table only uses const refs */
5749
if ((keyuse=s->keyuse))
5752
while (keyuse->table == table)
5754
start_keyuse=keyuse;
5756
s->keys.set(key); // QQ: remove this ?
5763
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
5765
if (!((~found_const_table_map) & keyuse->used_tables))
5766
const_ref.set(keyuse->keypart);
5768
refs|=keyuse->used_tables;
5769
eq_part.set(keyuse->keypart);
5772
} while (keyuse->table == table && keyuse->key == key);
5774
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5775
!table->pos_in_table_list->embedding)
5777
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5779
if (const_ref == eq_part)
5780
{ // Found everything for ref.
5784
join->const_table_map|= table->map;
5785
set_position(join,const_count++,s,start_keyuse);
5786
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5788
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5789
if ((tmp=join_read_const_table(s, partial_pos)))
5792
return 1; // Fatal error
5795
found_const_table_map|= table->map;
5799
found_ref|= refs; // Table is const if all refs are const
5801
else if (const_ref == eq_part)
5802
s->const_keys.set(key);
5807
} while (join->const_table_map & found_ref && ref_changed);
5810
Update info on indexes that can be used for search lookups as
5811
reading const tables may has added new sargable predicates.
5813
if (const_count && ! sargables.empty())
5815
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
5816
while (iter != sargables.end())
5818
Field *field= (*iter).getField();
5819
JoinTable *join_tab= field->table->reginfo.join_tab;
5820
key_map possible_keys= field->key_start;
5821
possible_keys&= field->table->keys_in_use_for_query;
5822
bool is_const= true;
5823
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5824
is_const&= (*iter).isConstItem(j);
5826
join_tab[0].const_keys|= possible_keys;
5831
/* Calc how many (possible) matched records in each table */
5833
for (s=stat ; s < stat_end ; s++)
5835
if (s->type == AM_SYSTEM || s->type == AM_CONST)
5837
/* Only one matching row */
5838
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
5841
/* Approximate found rows and time to read them */
5842
s->found_records=s->records=s->table->file->stats.records;
5843
s->read_time=(ha_rows) s->table->file->scan_time();
5846
Set a max range of how many seeks we can expect when using keys
5847
This is can't be to high as otherwise we are likely to use
5850
s->worst_seeks= min((double) s->found_records / 10,
5851
(double) s->read_time*3);
5852
if (s->worst_seeks < 2.0) // Fix for small tables
5856
Add to stat->const_keys those indexes for which all group fields or
5857
all select distinct fields participate in one index.
5859
add_group_and_distinct_keys(join, s);
5861
if (s->const_keys.any() &&
5862
!s->table->pos_in_table_list->embedding)
5866
select= make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
5869
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
5870
s->quick=select->quick;
5871
s->needed_reg=select->needed_reg;
5873
if (records == 0 && s->table->reginfo.impossible_range)
5876
Impossible WHERE or ON expression
5877
In case of ON, we mark that the we match one empty NULL row.
5878
In case of WHERE, don't set found_const_table_map to get the
5879
caller to abort with a zero row result.
5881
join->const_table_map|= s->table->map;
5882
set_position(join,const_count++,s,(KeyUse*) 0);
5884
if (*s->on_expr_ref)
5886
/* Generate empty row */
5887
s->info= "Impossible ON condition";
5888
found_const_table_map|= s->table->map;
5890
s->table->mark_as_null_row(); // All fields are NULL
5893
if (records != HA_POS_ERROR)
5895
s->found_records=records;
5896
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
5902
join->join_tab=stat;
5903
join->map2table=stat_ref;
5904
join->table= join->all_tables=table_vector;
5905
join->const_tables=const_count;
5906
join->found_const_table_map=found_const_table_map;
5908
/* Find an optimal join order of the non-constant tables. */
5909
if (join->const_tables != join->tables)
5911
optimize_keyuse(join, keyuse_array);
5912
if (choose_plan(join, all_table_map & ~join->const_table_map))
5917
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
5918
join->best_read= 1.0;
5920
/* Generate an execution plan from the found optimal join order. */
5921
return (join->session->killed || get_best_combination(join));
5925
Assign each nested join structure a bit in the nested join bitset.
5927
Assign each nested join structure (except "confluent" ones - those that
5928
embed only one element) a bit in the nested join bitset.
5930
@param join Join being processed
5931
@param join_list List of tables
5932
@param first_unused Number of first unused bit in the nest joing bitset before the
5936
This function is called after simplify_joins(), when there are no
5937
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
5938
we will not run out of bits in the nested join bitset.
5941
First unused bit in the nest join bitset after the call.
5943
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
5945
List_iterator<TableList> li(*join_list);
5947
while ((table= li++))
5949
nested_join_st *nested_join;
5950
if ((nested_join= table->nested_join))
5953
It is guaranteed by simplify_joins() function that a nested join
5954
that has only one child is either
5955
- a single-table view (the child is the underlying table), or
5956
- a single-table semi-join nest
5958
We don't assign bits to such sj-nests because
5959
1. it is redundant (a "sequence" of one table cannot be interleaved
5961
2. we could run out of bits in the nested join bitset otherwise.
5963
if (nested_join->join_list.elements != 1)
5965
/* Don't assign bits to sj-nests */
5967
nested_join->nj_map.set(first_unused++);
5968
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
5973
return(first_unused);
5978
Return table number if there is only one table in sort order
5979
and group and order is compatible, else return 0.
5981
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
5983
table_map map= (table_map) 0;
5986
a= b; // Only one need to be given
5990
for (; a && b; a=a->next,b=b->next)
5992
if (!(*a->item)->eq(*b->item,1))
5993
return (Table *) NULL;
5994
map|= a->item[0]->used_tables();
5996
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
5997
return (Table *) NULL;
5999
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6000
if (map != tables->table->map)
6001
return (Table *) NULL; // More than one table
6002
return tables->table;
6006
Set nested_join_st::counter=0 in all nested joins in passed list.
6008
Recursively set nested_join_st::counter=0 for all nested joins contained in
6009
the passed join_list.
6011
@param join_list List of nested joins to process. It may also contain base
6012
tables which will be ignored.
6014
static void reset_nj_counters(List<TableList> *join_list)
6016
List_iterator<TableList> li(*join_list);
6018
while ((table= li++))
6020
nested_join_st *nested_join;
6021
if ((nested_join= table->nested_join))
6023
nested_join->counter_= 0;
6024
reset_nj_counters(&nested_join->join_list);
6031
Return 1 if second is a subpart of first argument.
6033
If first parts has different direction, change it to second part
6034
(group is sorted like order)
6036
static bool test_if_subpart(order_st *a,order_st *b)
6038
for (; a && b; a=a->next,b=b->next)
6040
if ((*a->item)->eq(*b->item,1))
6049
Nested joins perspective: Remove the last table from the join order.
6051
Remove the last table from the partial join order and update the nested
6052
joins counters and join->cur_embedding_map. It is ok to call this
6053
function for the first table in join order (for which
6054
check_interleaving_with_nj has not been called)
6056
@param last join table to remove, it is assumed to be the last in current
6059
static void restore_prev_nj_state(JoinTable *last)
6061
TableList *last_emb= last->table->pos_in_table_list->embedding;
6062
JOIN *join= last->join;
6065
if (last_emb->on_expr)
6067
if (!(--last_emb->nested_join->counter_))
6068
join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
6069
else if (last_emb->nested_join->join_list.elements-1 ==
6070
last_emb->nested_join->counter_)
6071
join->cur_embedding_map|= last_emb->nested_join->nj_map;
6075
last_emb= last_emb->embedding;
6080
Determine if the set is already ordered for order_st BY, so it can
6081
disable join cache because it will change the ordering of the results.
6082
Code handles sort table that is at any location (not only first after
6083
the const tables) despite the fact that it's currently prohibited.
6084
We must disable join cache if the first non-const table alone is
6085
ordered. If there is a temp table the ordering is done as a last
6086
operation and doesn't prevent join cache usage.
6088
static uint32_t make_join_orderinfo(JOIN *join)
6092
return join->tables;
6094
for (i=join->const_tables ; i < join->tables ; i++)
6096
JoinTable *tab= join->join_tab+i;
6097
Table *table= tab->table;
6098
if ((table == join->sort_by_table &&
6099
(!join->order || join->skip_sort_order)) ||
6100
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
6109
Create a condition for a const reference and add this to the
6110
currenct select for the table.
6112
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6114
if (!join_tab->ref.key_parts)
6117
Item_cond_and *cond=new Item_cond_and();
6118
Table *table=join_tab->table;
6123
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6125
Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
6127
Item *value=join_tab->ref.items[i];
6128
cond->add(new Item_func_equal(new Item_field(field), value));
6130
if (session->is_fatal_error)
6134
cond->fix_fields(session, (Item**)&cond);
6135
if (join_tab->select)
6137
error=(int) cond->add(join_tab->select->cond);
6138
join_tab->select_cond=join_tab->select->cond=cond;
6140
else if ((join_tab->select= make_select(join_tab->table, 0, 0, cond, 0,
6142
join_tab->select_cond=cond;
6144
return(error ? true : false);
6147
static void free_blobs(Field **ptr)
6149
for (; *ptr ; ptr++)
6151
if ((*ptr)->flags & BLOB_FLAG)
6152
((Field_blob *) (*ptr))->free();
6157
@} (end of group Query_Optimizer)
added
removed
drizzled/join.cc
