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 "drizzled/optimizer/key_use.h"
48
#include "mysys/my_bit.h"
53
using namespace drizzled;
55
/** Declarations of static functions used in this source file. */
56
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
57
static void calc_group_buffer(JOIN *join,order_st *group);
58
static bool alloc_group_fields(JOIN *join,order_st *group);
59
static uint32_t cache_record_length(JOIN *join, uint32_t index);
60
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
61
static bool get_best_combination(JOIN *join);
62
static void set_position(JOIN *join,
65
optimizer::KeyUse *key);
66
static bool choose_plan(JOIN *join,table_map join_tables);
67
static void best_access_path(JOIN *join, JoinTable *s,
69
table_map remaining_tables,
73
static void optimize_straight_join(JOIN *join, table_map join_tables);
74
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
75
static bool best_extension_by_limited_search(JOIN *join,
76
table_map remaining_tables,
81
uint32_t prune_level);
82
static uint32_t determine_search_depth(JOIN* join);
83
static bool make_simple_join(JOIN *join,Table *tmp_table);
84
static void make_outerjoin_info(JOIN *join);
85
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
86
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
87
static void update_depend_map(JOIN *join);
88
static void update_depend_map(JOIN *join, order_st *order);
89
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
90
static int return_zero_rows(JOIN *join,
95
uint64_t select_options,
98
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
99
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
100
static int setup_without_group(Session *session,
101
Item **ref_pointer_array,
105
List<Item> &all_fields,
109
bool *hidden_group_fields);
110
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
111
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
112
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
113
static void reset_nj_counters(List<TableList> *join_list);
114
static bool test_if_subpart(order_st *a,order_st *b);
115
static void restore_prev_nj_state(JoinTable *last);
116
static uint32_t make_join_orderinfo(JOIN *join);
117
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
118
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
121
Prepare of whole select (including sub queries in future).
124
Add check of calculation of GROUP functions and fields:
125
SELECT COUNT(*)+table.col1 from table1;
132
int JOIN::prepare(Item ***rref_pointer_array,
133
TableList *tables_init,
137
order_st *order_init,
138
order_st *group_init,
140
Select_Lex *select_lex_arg,
141
Select_Lex_Unit *unit_arg)
143
// to prevent double initialization on EXPLAIN
149
group_list= group_init;
151
tables_list= tables_init;
152
select_lex= select_lex_arg;
153
select_lex->join= this;
154
join_list= &select_lex->top_join_list;
155
union_part= unit_arg->is_union();
157
session->lex->current_select->is_item_list_lookup= 1;
159
If we have already executed SELECT, then it have not sense to prevent
160
its table from update (see unique_table())
162
if (session->derived_tables_processing)
163
select_lex->exclude_from_table_unique_test= true;
165
/* Check that all tables, fields, conds and order are ok */
167
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
168
setup_tables_and_check_access(session, &select_lex->context, join_list,
169
tables_list, &select_lex->leaf_tables,
173
TableList *table_ptr;
174
for (table_ptr= select_lex->leaf_tables;
176
table_ptr= table_ptr->next_leaf)
179
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
180
select_lex->setup_ref_array(session, og_num) ||
181
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
183
setup_without_group(session, (*rref_pointer_array), tables_list,
184
select_lex->leaf_tables, fields_list,
185
all_fields, &conds, order, group_list,
186
&hidden_group_fields))
189
ref_pointer_array= *rref_pointer_array;
193
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
194
session->where="having clause";
195
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
196
select_lex->having_fix_field= 1;
197
bool having_fix_rc= (!having->fixed &&
198
(having->fix_fields(session, &having) ||
199
having->check_cols(1)));
200
select_lex->having_fix_field= 0;
201
if (having_fix_rc || session->is_error())
203
session->lex->allow_sum_func= save_allow_sum_func;
207
Item_subselect *subselect;
208
Item_in_subselect *in_subs= NULL;
210
Are we in a subquery predicate?
211
TODO: the block below will be executed for every PS execution without need.
213
if ((subselect= select_lex->master_unit()->item))
215
if (subselect->substype() == Item_subselect::IN_SUBS)
216
in_subs= (Item_in_subselect*)subselect;
219
bool do_materialize= !test(session->variables.optimizer_switch &
220
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
222
Check if the subquery predicate can be executed via materialization.
223
The required conditions are:
224
1. Subquery predicate is an IN/=ANY subq predicate
225
2. Subquery is a single SELECT (not a UNION)
226
3. Subquery is not a table-less query. In this case there is no
227
point in materializing.
228
4. Subquery predicate is a top-level predicate
229
(this implies it is not negated)
230
TODO: this is a limitation that should be lifeted once we
231
implement correct NULL semantics (WL#3830)
232
5. Subquery is non-correlated
234
This is an overly restrictive condition. It can be extended to:
235
(Subquery is non-correlated ||
236
Subquery is correlated to any query outer to IN predicate ||
237
(Subquery is correlated to the immediate outer query &&
238
Subquery !contains {GROUP BY, order_st BY [LIMIT],
239
aggregate functions) && subquery predicate is not under "NOT IN"))
240
6. No execution method was already chosen (by a prepared statement).
242
(*) The subquery must be part of a SELECT statement. The current
243
condition also excludes multi-table update statements.
245
We have to determine whether we will perform subquery materialization
246
before calling the IN=>EXISTS transformation, so that we know whether to
247
perform the whole transformation or only that part of it which wraps
248
Item_in_subselect in an Item_in_optimizer.
250
if (do_materialize &&
252
!select_lex->master_unit()->first_select()->next_select() && // 2
253
select_lex->master_unit()->first_select()->leaf_tables && // 3
254
session->lex->sql_command == SQLCOM_SELECT) // *
256
if (in_subs->is_top_level_item() && // 4
257
!in_subs->is_correlated && // 5
258
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
259
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
262
Item_subselect::trans_res trans_res;
263
if ((trans_res= subselect->select_transformer(this)) !=
264
Item_subselect::RES_OK)
266
return((trans_res == Item_subselect::RES_ERROR));
275
for (ord= order; ord; ord= ord->next)
277
Item *item= *ord->item;
278
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
279
item->split_sum_func(session, ref_pointer_array, all_fields);
283
if (having && having->with_sum_func)
284
having->split_sum_func(session, ref_pointer_array, all_fields,
286
if (select_lex->inner_sum_func_list)
288
Item_sum *end=select_lex->inner_sum_func_list;
289
Item_sum *item_sum= end;
292
item_sum= item_sum->next;
293
item_sum->split_sum_func(session, ref_pointer_array,
294
all_fields, item_sum->ref_by, false);
295
} while (item_sum != end);
298
if (select_lex->inner_refs_list.elements &&
299
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
303
Check if there are references to un-aggregated columns when computing
304
aggregate functions with implicit grouping (there is no GROUP BY).
306
MODE_ONLY_FULL_GROUP_BY is enabled here by default
309
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
310
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
312
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
313
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
317
/* Caclulate the number of groups */
319
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
326
if (result && result->prepare(fields_list, unit_arg))
329
/* Init join struct */
330
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
331
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
332
this->group= group_list != 0;
335
#ifdef RESTRICTED_GROUP
336
if (sum_func_count && !group_list && (func_count || field_count))
338
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
342
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
344
if (alloc_func_list())
354
Remove the predicates pushed down into the subquery
357
JOIN::remove_subq_pushed_predicates()
358
where IN Must be NULL
359
OUT The remaining WHERE condition, or NULL
362
Given that this join will be executed using (unique|index)_subquery,
363
without "checking NULL", remove the predicates that were pushed down
366
If the subquery compares scalar values, we can remove the condition that
367
was wrapped into trig_cond (it will be checked when needed by the subquery
370
If the subquery compares row values, we need to keep the wrapped
371
equalities in the WHERE clause: when the left (outer) tuple has both NULL
372
and non-NULL values, we'll do a full table scan and will rely on the
373
equalities corresponding to non-NULL parts of left tuple to filter out
374
non-matching records.
376
TODO: We can remove the equalities that will be guaranteed to be true by the
377
fact that subquery engine will be using index lookup. This must be done only
378
for cases where there are no conversion errors of significance, e.g. 257
379
that is searched in a byte. But this requires homogenization of the return
380
codes of all Field*::store() methods.
382
void JOIN::remove_subq_pushed_predicates(Item **where)
384
if (conds->type() == Item::FUNC_ITEM &&
385
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
386
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
387
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
388
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
389
((Item_func *)conds)->arguments()[0]))
397
global select optimisation.
400
error code saved in field 'error'
409
// to prevent double initialization on EXPLAIN
414
session->set_proc_info("optimizing");
415
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
416
unit->select_limit_cnt);
417
/* select_limit is used to decide if we are likely to scan the whole table */
418
select_limit= unit->select_limit_cnt;
419
if (having || (select_options & OPTION_FOUND_ROWS))
420
select_limit= HA_POS_ERROR;
421
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
422
// Ignore errors of execution if option IGNORE present
423
if (session->lex->ignore)
424
session->lex->current_select->no_error= 1;
426
#ifdef HAVE_REF_TO_FIELDS // Not done yet
427
/* Add HAVING to WHERE if possible */
428
if (having && !group_list && !sum_func_count)
435
else if ((conds=new Item_cond_and(conds,having)))
438
Item_cond_and can't be fixed after creation, so we do not check
441
conds->fix_fields(session, &conds);
442
conds->change_ref_to_fields(session, tables_list);
443
conds->top_level_item();
449
/* Convert all outer joins to inner joins if possible */
450
conds= simplify_joins(this, join_list, conds, true);
451
build_bitmap_for_nested_joins(join_list, 0);
453
conds= optimize_cond(this, conds, join_list, &cond_value);
454
if (session->is_error())
461
having= optimize_cond(this, having, join_list, &having_value);
462
if (session->is_error())
467
if (select_lex->where)
468
select_lex->cond_value= cond_value;
469
if (select_lex->having)
470
select_lex->having_value= having_value;
472
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
473
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
474
{ /* Impossible cond */
475
zero_result_cause= having_value == Item::COND_FALSE ?
476
"Impossible HAVING" : "Impossible WHERE";
482
/* Optimize count(*), cmin() and cmax() */
483
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
487
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
488
to the WHERE conditions,
489
or 1 if all items were resolved,
490
or 0, or an error number HA_ERR_...
492
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
494
if (res == HA_ERR_KEY_NOT_FOUND)
496
zero_result_cause= "No matching min/max row";
507
zero_result_cause= "No matching min/max row";
511
zero_result_cause= "Select tables optimized away";
512
tables_list= 0; // All tables resolved
514
Extract all table-independent conditions and replace the WHERE
515
clause with them. All other conditions were computed by opt_sum_query
516
and the MIN/MAX/COUNT function(s) have been replaced by constants,
517
so there is no need to compute the whole WHERE clause again.
518
Notice that make_cond_for_table() will always succeed to remove all
519
computed conditions, because opt_sum_query() is applicable only to
521
Preserve conditions for EXPLAIN.
523
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
525
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
526
conds= table_independent_conds;
535
error= -1; // Error is sent to client
536
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
538
/* Calculate how to do the join */
539
session->set_proc_info("statistics");
540
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
541
session->is_fatal_error)
546
/* Remove distinct if only const tables */
547
select_distinct= select_distinct && (const_tables != tables);
548
session->set_proc_info("preparing");
549
if (result->initialize_tables(this))
551
return 1; // error == -1
553
if (const_table_map != found_const_table_map &&
554
!(select_options & SELECT_DESCRIBE) &&
556
!(conds->used_tables() & RAND_TABLE_BIT) ||
557
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
559
zero_result_cause= "no matching row in const table";
563
if (!(session->options & OPTION_BIG_SELECTS) &&
564
best_read > (double) session->variables.max_join_size &&
565
!(select_options & SELECT_DESCRIBE))
567
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
571
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
572
mysql_unlock_some_tables(session, table, const_tables);
573
if (!conds && outer_join)
575
/* Handle the case where we have an OUTER JOIN without a WHERE */
576
conds=new Item_int((int64_t) 1,1); // Always true
578
select= make_select(*table, const_table_map,
579
const_table_map, conds, 1, &error);
586
reset_nj_counters(join_list);
587
make_outerjoin_info(this);
590
Among the equal fields belonging to the same multiple equality
591
choose the one that is to be retrieved first and substitute
592
all references to these in where condition for a reference for
597
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
598
conds->update_used_tables();
602
Permorm the the optimization on fields evaluation mentioned above
603
for all on expressions.
605
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
607
if (*tab->on_expr_ref)
609
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
612
(*tab->on_expr_ref)->update_used_tables();
616
if (conds &&!outer_join && const_table_map != found_const_table_map &&
617
(select_options & SELECT_DESCRIBE) &&
618
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
620
conds=new Item_int((int64_t) 0,1); // Always false
622
if (make_join_select(this, select, conds))
625
"Impossible WHERE noticed after reading const tables";
626
return(0); // error == 0
629
error= -1; /* if goto err */
631
/* Optimize distinct away if possible */
633
order_st *org_order= order;
634
order= remove_constants(this, order,conds,1, &simple_order);
635
if (session->is_error())
642
If we are using order_st BY NULL or order_st BY const_expression,
643
return result in any order (even if we are using a GROUP BY)
645
if (!order && org_order)
649
Check if we can optimize away GROUP BY/DISTINCT.
650
We can do that if there are no aggregate functions, the
651
fields in DISTINCT clause (if present) and/or columns in GROUP BY
652
(if present) contain direct references to all key parts of
653
an unique index (in whatever order) and if the key parts of the
654
unique index cannot contain NULLs.
655
Note that the unique keys for DISTINCT and GROUP BY should not
656
be the same (as long as they are unique).
658
The FROM clause must contain a single non-constant table.
660
if (tables - const_tables == 1 && (group_list || select_distinct) &&
661
!tmp_table_param.sum_func_count &&
662
(!join_tab[const_tables].select ||
663
!join_tab[const_tables].select->quick ||
664
join_tab[const_tables].select->quick->get_type() !=
665
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
667
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
670
We have found that grouping can be removed since groups correspond to
671
only one row anyway, but we still have to guarantee correct result
672
order. The line below effectively rewrites the query from GROUP BY
673
<fields> to order_st BY <fields>. There are two exceptions:
674
- if skip_sort_order is set (see above), then we can simply skip
676
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
677
with the GROUP BY ones, i.e. either one is a prefix of another.
678
We only check if the order_st BY is a prefix of GROUP BY. In this case
679
test_if_subpart() copies the ASC/DESC attributes from the original
681
If GROUP BY is a prefix of order_st BY, then it is safe to leave
684
if (!order || test_if_subpart(group_list, order))
685
order= skip_sort_order ? 0 : group_list;
687
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
688
rewritten to IGNORE INDEX FOR order_st BY(fields).
690
join_tab->table->keys_in_use_for_order_by=
691
join_tab->table->keys_in_use_for_group_by;
695
if (select_distinct &&
696
list_contains_unique_index(join_tab[const_tables].table,
697
find_field_in_item_list,
698
(void *) &fields_list))
703
if (group_list || tmp_table_param.sum_func_count)
705
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
708
else if (select_distinct && tables - const_tables == 1)
711
We are only using one table. In this case we change DISTINCT to a
713
- The GROUP BY can be done through indexes (no sort) and the order_st
714
BY only uses selected fields.
715
(In this case we can later optimize away GROUP BY and order_st BY)
716
- We are scanning the whole table without LIMIT
718
- We are using CALC_FOUND_ROWS
719
- We are using an order_st BY that can't be optimized away.
721
We don't want to use this optimization when we are using LIMIT
722
because in this case we can just create a temporary table that
723
holds LIMIT rows and stop when this table is full.
725
JoinTable *tab= &join_tab[const_tables];
726
bool all_order_fields_used;
728
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
729
&tab->table->keys_in_use_for_order_by);
730
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
731
order, fields_list, all_fields,
732
&all_order_fields_used)))
734
bool skip_group= (skip_sort_order &&
735
test_if_skip_sort_order(tab, group_list, select_limit, 1,
736
&tab->table->keys_in_use_for_group_by) != 0);
737
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
738
if ((skip_group && all_order_fields_used) ||
739
select_limit == HA_POS_ERROR ||
740
(order && !skip_sort_order))
742
/* Change DISTINCT to GROUP BY */
745
if (all_order_fields_used)
747
if (order && skip_sort_order)
750
Force MySQL to read the table in sorted order to get result in
753
tmp_table_param.quick_group=0;
757
group=1; // For end_write_group
762
else if (session->is_fatal_error) // End of memory
767
order_st *old_group_list;
768
group_list= remove_constants(this, (old_group_list= group_list), conds,
769
rollup.state == ROLLUP::STATE_NONE,
771
if (session->is_error())
776
if (old_group_list && !group_list)
779
if (!group_list && group)
781
order=0; // The output has only one row
783
select_distinct= 0; // No need in distinct for 1 row
784
group_optimized_away= 1;
787
calc_group_buffer(this, group_list);
788
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
790
if (test_if_subpart(group_list, order) ||
791
(!group_list && tmp_table_param.sum_func_count))
794
// Can't use sort on head table if using row cache
804
Check if we need to create a temporary table.
805
This has to be done if all tables are not already read (const tables)
806
and one of the following conditions holds:
807
- We are using DISTINCT (simple distinct's are already optimized away)
808
- We are using an order_st BY or GROUP BY on fields not in the first table
809
- We are using different order_st BY and GROUP BY orders
810
- The user wants us to buffer the result.
812
need_tmp= (const_tables != tables &&
813
((select_distinct || !simple_order || !simple_group) ||
814
(group_list && order) ||
815
test(select_options & OPTION_BUFFER_RESULT)));
817
uint32_t no_jbuf_after= make_join_orderinfo(this);
818
uint64_t select_opts_for_readinfo=
819
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
821
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
822
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
825
/* Create all structures needed for materialized subquery execution. */
826
if (setup_subquery_materialization())
830
is this simple IN subquery?
832
if (!group_list && !order &&
833
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
834
tables == 1 && conds &&
840
if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
842
remove_subq_pushed_predicates(&where);
843
save_index_subquery_explain_info(join_tab, where);
844
join_tab[0].type= AM_UNIQUE_SUBQUERY;
848
subselect_uniquesubquery_engine(session,
853
else if (join_tab[0].type == AM_REF &&
854
join_tab[0].ref.items[0]->name == in_left_expr_name)
856
remove_subq_pushed_predicates(&where);
857
save_index_subquery_explain_info(join_tab, where);
858
join_tab[0].type= AM_INDEX_SUBQUERY;
862
subselect_indexsubquery_engine(session,
870
else if (join_tab[0].type == AM_REF_OR_NULL &&
871
join_tab[0].ref.items[0]->name == in_left_expr_name &&
872
having->name == in_having_cond)
874
join_tab[0].type= AM_INDEX_SUBQUERY;
876
conds= remove_additional_cond(conds);
877
save_index_subquery_explain_info(join_tab, conds);
879
change_engine(new subselect_indexsubquery_engine(session,
889
Need to tell handlers that to play it safe, it should fetch all
890
columns of the primary key of the tables: this is because MySQL may
891
build row pointers for the rows, and for all columns of the primary key
892
the read set has not necessarily been set by the server code.
894
if (need_tmp || select_distinct || group_list || order)
896
for (uint32_t i = const_tables; i < tables; i++)
897
join_tab[i].table->prepare_for_position();
900
if (const_tables != tables)
903
Because filesort always does a full table scan or a quick range scan
904
we must add the removed reference to the select for the table.
905
We only need to do this when we have a simple_order or simple_group
906
as in other cases the join is done before the sort.
908
if ((order || group_list) &&
909
(join_tab[const_tables].type != AM_ALL) &&
910
(join_tab[const_tables].type != AM_REF_OR_NULL) &&
911
((order && simple_order) || (group_list && simple_group)))
913
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
918
if (!(select_options & SELECT_BIG_RESULT) &&
921
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
922
unit->select_limit_cnt, 0,
923
&join_tab[const_tables].table->
924
keys_in_use_for_group_by))) ||
926
tmp_table_param.quick_group)
928
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
933
Force using of tmp table if sorting by a SP or UDF function due to
934
their expensive and probably non-deterministic nature.
936
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
938
Item *item= *tmp_order->item;
939
if (item->is_expensive())
941
/* Force tmp table without sort */
942
need_tmp=1; simple_order=simple_group=0;
950
if (select_options & SELECT_DESCRIBE)
958
The loose index scan access method guarantees that all grouping or
959
duplicate row elimination (for distinct) is already performed
960
during data retrieval, and that all MIN/MAX functions are already
961
computed for each group. Thus all MIN/MAX functions should be
962
treated as regular functions, and there is no need to perform
963
grouping in the main execution loop.
964
Notice that currently loose index scan is applicable only for
965
single table queries, thus it is sufficient to test only the first
966
join_tab element of the plan for its access method.
968
if (join_tab->is_using_loose_index_scan())
969
tmp_table_param.precomputed_group_by= true;
971
/* Create a tmp table if distinct or if the sort is too complicated */
974
session->set_proc_info("Creating tmp table");
976
init_items_ref_array();
978
tmp_table_param.hidden_field_count= (all_fields.elements -
979
fields_list.elements);
980
order_st *tmp_group= ((!simple_group &&
981
! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
984
Pushing LIMIT to the temporary table creation is not applicable
985
when there is order_st BY or GROUP BY or there is no GROUP BY, but
986
there are aggregate functions, because in all these cases we need
989
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
991
!session->lex->current_select->with_sum_func) ?
992
select_limit : HA_POS_ERROR;
994
if (!(exec_tmp_table1=
995
create_tmp_table(session, &tmp_table_param, all_fields,
997
group_list ? 0 : select_distinct,
998
group_list && simple_group,
1007
We don't have to store rows in temp table that doesn't match HAVING if:
1008
- we are sorting the table and writing complete group rows to the
1010
- We are using DISTINCT without resolving the distinct as a GROUP BY
1013
If having is not handled here, it will be checked before the row
1014
is sent to the client.
1016
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1019
/* if group or order on first table, sort first */
1020
if (group_list && simple_group)
1022
session->set_proc_info("Sorting for group");
1023
if (create_sort_index(session, this, group_list,
1024
HA_POS_ERROR, HA_POS_ERROR, false) ||
1025
alloc_group_fields(this, group_list) ||
1026
make_sum_func_list(all_fields, fields_list, 1) ||
1027
setup_sum_funcs(session, sum_funcs))
1035
if (make_sum_func_list(all_fields, fields_list, 0) ||
1036
setup_sum_funcs(session, sum_funcs))
1041
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1043
session->set_proc_info("Sorting for order");
1044
if (create_sort_index(session, this, order,
1045
HA_POS_ERROR, HA_POS_ERROR, true))
1054
Optimize distinct when used on some of the tables
1055
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1056
In this case we can stop scanning t2 when we have found one t1.a
1059
if (exec_tmp_table1->distinct)
1061
table_map used_tables= session->used_tables;
1062
JoinTable *last_join_tab= join_tab+tables-1;
1065
if (used_tables & last_join_tab->table->map)
1067
last_join_tab->not_used_in_distinct=1;
1068
} while (last_join_tab-- != join_tab);
1069
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1070
if (order && skip_sort_order)
1072
/* Should always succeed */
1073
if (test_if_skip_sort_order(&join_tab[const_tables],
1074
order, unit->select_limit_cnt, 0,
1075
&join_tab[const_tables].table->
1076
keys_in_use_for_order_by))
1082
If this join belongs to an uncacheable subquery save
1085
if (select_lex->uncacheable && !is_top_level_join() &&
1086
init_save_join_tab())
1095
Restore values in temporary join.
1097
void JOIN::restore_tmp()
1099
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1104
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1105
select_lex->offset_limit->val_uint() :
1110
if (exec_tmp_table1)
1112
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1113
exec_tmp_table1->file->ha_delete_all_rows();
1114
exec_tmp_table1->free_io_cache();
1115
exec_tmp_table1->filesort_free_buffers();
1117
if (exec_tmp_table2)
1119
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1120
exec_tmp_table2->file->ha_delete_all_rows();
1121
exec_tmp_table2->free_io_cache();
1122
exec_tmp_table2->filesort_free_buffers();
1125
set_items_ref_array(items0);
1128
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1133
/* Reset of sum functions */
1136
Item_sum *func, **func_ptr= sum_funcs;
1137
while ((func= *(func_ptr++)))
1145
@brief Save the original join layout
1147
@details Saves the original join layout so it can be reused in
1148
re-execution and for EXPLAIN.
1150
@return Operation status
1152
@retval 1 error occurred.
1154
bool JOIN::init_save_join_tab()
1156
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
1158
error= 0; // Ensure that tmp_join.error= 0
1163
bool JOIN::save_join_tab()
1165
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1167
if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1168
sizeof(JoinTable) * tables)))
1178
Note, that create_sort_index calls test_if_skip_sort_order and may
1179
finally replace sorting with index scan if there is a LIMIT clause in
1180
the query. It's never shown in EXPLAIN!
1183
When can we have here session->net.report_error not zero?
1187
List<Item> *columns_list= &fields_list;
1190
session->set_proc_info("executing");
1193
if (!tables_list && (tables || !select_lex->with_sum_func))
1195
/* Only test of functions */
1196
if (select_options & SELECT_DESCRIBE)
1197
select_describe(this, false, false, false, (zero_result_cause?zero_result_cause:"No tables used"));
1200
result->send_fields(*columns_list);
1202
We have to test for 'conds' here as the WHERE may not be constant
1203
even if we don't have any tables for prepared statements or if
1204
conds uses something like 'rand()'.
1206
if (cond_value != Item::COND_FALSE &&
1207
(!conds || conds->val_int()) &&
1208
(!having || having->val_int()))
1210
if (do_send_rows && result->send_data(fields_list))
1214
error= (int) result->send_eof();
1215
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1220
error= (int) result->send_eof();
1224
/* Single select (without union) always returns 0 or 1 row */
1225
session->limit_found_rows= send_records;
1226
session->examined_row_count= 0;
1230
Don't reset the found rows count if there're no tables as
1231
FOUND_ROWS() may be called. Never reset the examined row count here.
1232
It must be accumulated from all join iterations of all join parts.
1235
session->limit_found_rows= 0;
1237
if (zero_result_cause)
1239
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1241
send_row_on_empty_set(),
1248
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) && get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
1251
if (select_options & SELECT_DESCRIBE)
1254
Check if we managed to optimize order_st BY away and don't use temporary
1255
table to resolve order_st BY: in that case, we only may need to do
1256
filesort for GROUP BY.
1258
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1260
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1262
simple_order= simple_group;
1265
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1267
if (const_tables == tables
1268
|| ((simple_order || skip_sort_order)
1269
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1273
select_describe(this, need_tmp, order != 0 && !skip_sort_order, select_distinct, !tables ? "No tables used" : NULL);
1277
JOIN *curr_join= this;
1278
List<Item> *curr_all_fields= &all_fields;
1279
List<Item> *curr_fields_list= &fields_list;
1280
Table *curr_tmp_table= 0;
1282
Initialize examined rows here because the values from all join parts
1283
must be accumulated in examined_row_count. Hence every join
1284
iteration must count from zero.
1286
curr_join->examined_rows= 0;
1288
/* Create a tmp table if distinct or if the sort is too complicated */
1294
We are in a non cacheable sub query. Get the saved join structure
1296
(curr_join may have been modified during last exection and we need
1299
curr_join= tmp_join;
1301
curr_tmp_table= exec_tmp_table1;
1303
/* Copy data to the temporary table */
1304
session->set_proc_info("Copying to tmp table");
1305
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1306
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1307
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1312
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
1314
if (curr_join->having)
1315
curr_join->having= curr_join->tmp_having= 0; // Allready done
1317
/* Change sum_fields reference to calculated fields in tmp_table */
1318
curr_join->all_fields= *curr_all_fields;
1321
items1= items0 + all_fields.elements;
1322
if (sort_and_group || curr_tmp_table->group)
1324
if (change_to_use_tmp_fields(session, items1,
1325
tmp_fields_list1, tmp_all_fields1,
1326
fields_list.elements, all_fields))
1331
if (change_refs_to_tmp_fields(session, items1,
1332
tmp_fields_list1, tmp_all_fields1,
1333
fields_list.elements, all_fields))
1336
curr_join->tmp_all_fields1= tmp_all_fields1;
1337
curr_join->tmp_fields_list1= tmp_fields_list1;
1338
curr_join->items1= items1;
1340
curr_all_fields= &tmp_all_fields1;
1341
curr_fields_list= &tmp_fields_list1;
1342
curr_join->set_items_ref_array(items1);
1344
if (sort_and_group || curr_tmp_table->group)
1346
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1347
+ curr_join->tmp_table_param.func_count;
1348
curr_join->tmp_table_param.sum_func_count= 0;
1349
curr_join->tmp_table_param.func_count= 0;
1353
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1354
curr_join->tmp_table_param.func_count= 0;
1357
if (curr_tmp_table->group)
1358
{ // Already grouped
1359
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1360
curr_join->order= curr_join->group_list; /* order by group */
1361
curr_join->group_list= 0;
1365
If we have different sort & group then we must sort the data by group
1366
and copy it to another tmp table
1367
This code is also used if we are using distinct something
1368
we haven't been able to store in the temporary table yet
1369
like SEC_TO_TIME(SUM(...)).
1372
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1373
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1374
{ /* Must copy to another table */
1375
/* Free first data from old join */
1376
curr_join->join_free();
1377
if (make_simple_join(curr_join, curr_tmp_table))
1379
calc_group_buffer(curr_join, group_list);
1380
count_field_types(select_lex, &curr_join->tmp_table_param,
1381
curr_join->tmp_all_fields1,
1382
curr_join->select_distinct && !curr_join->group_list);
1383
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1384
- curr_join->tmp_fields_list1.elements;
1386
if (exec_tmp_table2)
1387
curr_tmp_table= exec_tmp_table2;
1390
/* group data to new table */
1393
If the access method is loose index scan then all MIN/MAX
1394
functions are precomputed, and should be treated as regular
1395
functions. See extended comment in JOIN::exec.
1397
if (curr_join->join_tab->is_using_loose_index_scan())
1398
curr_join->tmp_table_param.precomputed_group_by= true;
1400
if (!(curr_tmp_table=
1401
exec_tmp_table2= create_tmp_table(session,
1402
&curr_join->tmp_table_param,
1405
curr_join->select_distinct &&
1406
!curr_join->group_list,
1407
1, curr_join->select_options,
1411
curr_join->exec_tmp_table2= exec_tmp_table2;
1413
if (curr_join->group_list)
1415
session->set_proc_info("Creating sort index");
1416
if (curr_join->join_tab == join_tab && save_join_tab())
1420
if (create_sort_index(session, curr_join, curr_join->group_list,
1421
HA_POS_ERROR, HA_POS_ERROR, false) ||
1422
make_group_fields(this, curr_join))
1426
sortorder= curr_join->sortorder;
1429
session->set_proc_info("Copying to group table");
1431
if (curr_join != this)
1435
curr_join->sum_funcs= sum_funcs2;
1436
curr_join->sum_funcs_end= sum_funcs_end2;
1440
curr_join->alloc_func_list();
1441
sum_funcs2= curr_join->sum_funcs;
1442
sum_funcs_end2= curr_join->sum_funcs_end;
1445
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1447
curr_join->group_list= 0;
1449
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1450
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1452
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1453
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1458
end_read_record(&curr_join->join_tab->read_record);
1459
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1460
curr_join->join_tab[0].table= 0; // Table is freed
1462
// No sum funcs anymore
1465
items2= items1 + all_fields.elements;
1466
if (change_to_use_tmp_fields(session, items2,
1467
tmp_fields_list2, tmp_all_fields2,
1468
fields_list.elements, tmp_all_fields1))
1470
curr_join->tmp_fields_list2= tmp_fields_list2;
1471
curr_join->tmp_all_fields2= tmp_all_fields2;
1473
curr_fields_list= &curr_join->tmp_fields_list2;
1474
curr_all_fields= &curr_join->tmp_all_fields2;
1475
curr_join->set_items_ref_array(items2);
1476
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1477
curr_join->tmp_table_param.sum_func_count= 0;
1479
if (curr_tmp_table->distinct)
1480
curr_join->select_distinct=0; /* Each row is unique */
1482
curr_join->join_free(); /* Free quick selects */
1483
if (curr_join->select_distinct && ! curr_join->group_list)
1485
session->set_proc_info("Removing duplicates");
1486
if (curr_join->tmp_having)
1487
curr_join->tmp_having->update_used_tables();
1489
if (remove_duplicates(curr_join, curr_tmp_table,
1490
*curr_fields_list, curr_join->tmp_having))
1493
curr_join->tmp_having=0;
1494
curr_join->select_distinct=0;
1496
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1497
if (make_simple_join(curr_join, curr_tmp_table))
1499
calc_group_buffer(curr_join, curr_join->group_list);
1500
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1504
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1506
if (make_group_fields(this, curr_join))
1512
init_items_ref_array();
1513
items3= ref_pointer_array + (all_fields.elements*4);
1514
setup_copy_fields(session, &curr_join->tmp_table_param,
1515
items3, tmp_fields_list3, tmp_all_fields3,
1516
curr_fields_list->elements, *curr_all_fields);
1517
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1518
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1519
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1520
curr_join->tmp_all_fields3= tmp_all_fields3;
1521
curr_join->tmp_fields_list3= tmp_fields_list3;
1525
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1526
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1527
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1529
curr_fields_list= &tmp_fields_list3;
1530
curr_all_fields= &tmp_all_fields3;
1531
curr_join->set_items_ref_array(items3);
1533
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1535
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1536
session->is_fatal_error)
1539
if (curr_join->group_list || curr_join->order)
1541
session->set_proc_info("Sorting result");
1542
/* If we have already done the group, add HAVING to sorted table */
1543
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1545
// Some tables may have been const
1546
curr_join->tmp_having->update_used_tables();
1547
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1548
table_map used_tables= (curr_join->const_table_map |
1549
curr_table->table->map);
1551
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1552
if (sort_table_cond)
1554
if (!curr_table->select)
1555
if (!(curr_table->select= new SQL_SELECT))
1557
if (!curr_table->select->cond)
1558
curr_table->select->cond= sort_table_cond;
1559
else // This should never happen
1561
if (!(curr_table->select->cond=
1562
new Item_cond_and(curr_table->select->cond,
1566
Item_cond_and do not need fix_fields for execution, its parameters
1567
are fixed or do not need fix_fields, too
1569
curr_table->select->cond->quick_fix_field();
1571
curr_table->select_cond= curr_table->select->cond;
1572
curr_table->select_cond->top_level_item();
1573
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1580
curr_join->select_limit= HA_POS_ERROR;
1584
We can abort sorting after session->select_limit rows if we there is no
1585
WHERE clause for any tables after the sorted one.
1587
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1588
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1589
for (; curr_table < end_table ; curr_table++)
1592
table->keyuse is set in the case there was an original WHERE clause
1593
on the table that was optimized away.
1595
if (curr_table->select_cond ||
1596
(curr_table->keyuse && !curr_table->first_inner))
1598
/* We have to sort all rows */
1599
curr_join->select_limit= HA_POS_ERROR;
1604
if (curr_join->join_tab == join_tab && save_join_tab())
1607
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1608
chose FILESORT to be faster than INDEX SCAN or there is no
1609
suitable index present.
1610
Note, that create_sort_index calls test_if_skip_sort_order and may
1611
finally replace sorting with index scan if there is a LIMIT clause in
1612
the query. XXX: it's never shown in EXPLAIN!
1613
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1615
if (create_sort_index(session, curr_join,
1616
curr_join->group_list ?
1617
curr_join->group_list : curr_join->order,
1618
curr_join->select_limit,
1619
(select_options & OPTION_FOUND_ROWS ?
1620
HA_POS_ERROR : unit->select_limit_cnt),
1621
curr_join->group_list ? true : false))
1624
sortorder= curr_join->sortorder;
1625
if (curr_join->const_tables != curr_join->tables &&
1626
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1629
If no IO cache exists for the first table then we are using an
1630
INDEX SCAN and no filesort. Thus we should not remove the sorted
1631
attribute on the INDEX SCAN.
1637
/* XXX: When can we have here session->is_error() not zero? */
1638
if (session->is_error())
1640
error= session->is_error();
1643
curr_join->having= curr_join->tmp_having;
1644
curr_join->fields= curr_fields_list;
1646
session->set_proc_info("Sending data");
1647
result->send_fields(*curr_fields_list);
1648
error= do_select(curr_join, curr_fields_list, NULL);
1649
session->limit_found_rows= curr_join->send_records;
1651
/* Accumulate the counts from all join iterations of all join parts. */
1652
session->examined_row_count+= curr_join->examined_rows;
1655
With EXPLAIN EXTENDED we have to restore original ref_array
1656
for a derived table which is always materialized.
1657
Otherwise we would not be able to print the query correctly.
1659
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1660
set_items_ref_array(items0);
1669
Return error that hold JOIN.
1673
select_lex->join= 0;
1677
if (join_tab != tmp_join->join_tab)
1679
JoinTable *tab, *end;
1680
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1683
tmp_join->tmp_join= 0;
1684
tmp_table_param.copy_field=0;
1685
return(tmp_join->destroy());
1690
if (exec_tmp_table1)
1691
exec_tmp_table1->free_tmp_table(session);
1692
if (exec_tmp_table2)
1693
exec_tmp_table2->free_tmp_table(session);
1695
delete_dynamic(&keyuse);
1700
Setup for execution all subqueries of a query, for which the optimizer
1701
chose hash semi-join.
1703
@details Iterate over all subqueries of the query, and if they are under an
1704
IN predicate, and the optimizer chose to compute it via hash semi-join:
1705
- try to initialize all data structures needed for the materialized execution
1706
of the IN predicate,
1707
- if this fails, then perform the IN=>EXISTS transformation which was
1708
previously blocked during JOIN::prepare.
1710
This method is part of the "code generation" query processing phase.
1712
This phase must be called after substitute_for_best_equal_field() because
1713
that function may replace items with other items from a multiple equality,
1714
and we need to reference the correct items in the index access method of the
1717
@return Operation status
1718
@retval false success.
1719
@retval true error occurred.
1721
bool JOIN::setup_subquery_materialization()
1723
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1724
un= un->next_unit())
1726
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1728
Item_subselect *subquery_predicate= sl->master_unit()->item;
1729
if (subquery_predicate &&
1730
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1732
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1733
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1734
in_subs->setup_engine())
1743
Partially cleanup JOIN after it has executed: close index or rnd read
1744
(table cursors), free quick selects.
1746
This function is called in the end of execution of a JOIN, before the used
1747
tables are unlocked and closed.
1749
For a join that is resolved using a temporary table, the first sweep is
1750
performed against actual tables and an intermediate result is inserted
1751
into the temprorary table.
1752
The last sweep is performed against the temporary table. Therefore,
1753
the base tables and associated buffers used to fill the temporary table
1754
are no longer needed, and this function is called to free them.
1756
For a join that is performed without a temporary table, this function
1757
is called after all rows are sent, but before EOF packet is sent.
1759
For a simple SELECT with no subqueries this function performs a full
1760
cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1763
If a JOIN is executed for a subquery or if it has a subquery, we can't
1764
do the full cleanup and need to do a partial cleanup only.
1765
- If a JOIN is not the top level join, we must not unlock the tables
1766
because the outer select may not have been evaluated yet, and we
1767
can't unlock only selected tables of a query.
1768
- Additionally, if this JOIN corresponds to a correlated subquery, we
1769
should not free quick selects and join buffers because they will be
1770
needed for the next execution of the correlated subquery.
1771
- However, if this is a JOIN for a [sub]select, which is not
1772
a correlated subquery itself, but has subqueries, we can free it
1773
fully and also free JOINs of all its subqueries. The exception
1774
is a subquery in SELECT list, e.g: @n
1775
SELECT a, (select cmax(b) from t1) group by c @n
1776
This subquery will not be evaluated at first sweep and its value will
1777
not be inserted into the temporary table. Instead, it's evaluated
1778
when selecting from the temporary table. Therefore, it can't be freed
1779
here even though it's not correlated.
1782
Unlock tables even if the join isn't top level select in the tree
1784
void JOIN::join_free()
1786
Select_Lex_Unit *tmp_unit;
1789
Optimization: if not EXPLAIN and we are done with the JOIN,
1792
bool full= (!select_lex->uncacheable && !session->lex->describe);
1793
bool can_unlock= full;
1797
for (tmp_unit= select_lex->first_inner_unit();
1799
tmp_unit= tmp_unit->next_unit())
1800
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1802
Item_subselect *subselect= sl->master_unit()->item;
1803
bool full_local= full && (!subselect || subselect->is_evaluated());
1805
If this join is evaluated, we can fully clean it up and clean up all
1806
its underlying joins even if they are correlated -- they will not be
1807
used any more anyway.
1808
If this join is not yet evaluated, we still must clean it up to
1809
close its table cursors -- it may never get evaluated, as in case of
1810
... HAVING false OR a IN (SELECT ...))
1811
but all table cursors must be closed before the unlock.
1813
sl->cleanup_all_joins(full_local);
1814
/* Can't unlock if at least one JOIN is still needed */
1815
can_unlock= can_unlock && full_local;
1819
We are not using tables anymore
1820
Unlock all tables. We may be in an INSERT .... SELECT statement.
1822
if (can_unlock && lock && session->lock &&
1823
!(select_options & SELECT_NO_UNLOCK) &&
1824
!select_lex->subquery_in_having &&
1825
(select_lex == (session->lex->unit.fake_select_lex ?
1826
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1829
TODO: unlock tables even if the join isn't top level select in the
1832
mysql_unlock_read_tables(session, lock); // Don't free join->lock
1841
Free resources of given join.
1843
@param fill true if we should free all resources, call with full==1
1844
should be last, before it this function can be called with
1848
With subquery this function definitely will be called several times,
1849
but even for simple query it can be called several times.
1851
void JOIN::cleanup(bool full)
1855
JoinTable *tab,*end;
1857
Only a sorted table may be cached. This sorted table is always the
1858
first non const table in join->table
1860
if (tables > const_tables) // Test for not-const tables
1862
table[const_tables]->free_io_cache();
1863
table[const_tables]->filesort_free_buffers(full);
1868
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1874
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1877
tab->table->file->ha_index_or_rnd_end();
1882
We are not using tables anymore
1883
Unlock all tables. We may be in an INSERT .... SELECT statement.
1888
tmp_table_param.copy_field= 0;
1889
group_fields.delete_elements();
1891
We can't call delete_elements() on copy_funcs as this will cause
1892
problems in free_elements() as some of the elements are then deleted.
1894
tmp_table_param.copy_funcs.empty();
1896
If we have tmp_join and 'this' JOIN is not tmp_join and
1897
tmp_table_param.copy_field's of them are equal then we have to remove
1898
pointer to tmp_table_param.copy_field from tmp_join, because it qill
1899
be removed in tmp_table_param.cleanup().
1903
tmp_join->tmp_table_param.copy_field ==
1904
tmp_table_param.copy_field)
1906
tmp_join->tmp_table_param.copy_field=
1907
tmp_join->tmp_table_param.save_copy_field= 0;
1909
tmp_table_param.cleanup();
1915
used only in JOIN::clear
1917
static void clear_tables(JOIN *join)
1920
must clear only the non-const tables, as const tables
1921
are not re-calculated.
1923
for (uint32_t i= join->const_tables; i < join->tables; i++)
1924
join->table[i]->mark_as_null_row(); // All fields are NULL
1928
Make an array of pointers to sum_functions to speed up
1929
sum_func calculation.
1936
bool JOIN::alloc_func_list()
1938
uint32_t func_count, group_parts;
1940
func_count= tmp_table_param.sum_func_count;
1942
If we are using rollup, we need a copy of the summary functions for
1945
if (rollup.state != ROLLUP::STATE_NONE)
1946
func_count*= (send_group_parts+1);
1948
group_parts= send_group_parts;
1950
If distinct, reserve memory for possible
1951
disctinct->group_by optimization
1953
if (select_distinct)
1955
group_parts+= fields_list.elements;
1957
If the order_st clause is specified then it's possible that
1958
it also will be optimized, so reserve space for it too
1963
for (ord= order; ord; ord= ord->next)
1968
/* This must use calloc() as rollup_make_fields depends on this */
1969
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
1970
sizeof(Item_sum***) * (group_parts+1));
1971
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
1972
return(sum_funcs == 0);
1976
Initialize 'sum_funcs' array with all Item_sum objects.
1978
@param field_list All items
1979
@param send_fields Items in select list
1980
@param before_group_by Set to 1 if this is called before GROUP BY handling
1981
@param recompute Set to true if sum_funcs must be recomputed
1988
bool JOIN::make_sum_func_list(List<Item> &field_list,
1989
List<Item> &send_fields,
1990
bool before_group_by,
1993
List_iterator_fast<Item> it(field_list);
1997
if (*sum_funcs && !recompute)
1998
return(false); /* We have already initialized sum_funcs. */
2003
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2004
(!((Item_sum*) item)->depended_from() ||
2005
((Item_sum *)item)->depended_from() == select_lex))
2006
*func++= (Item_sum*) item;
2008
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2010
rollup.state= ROLLUP::STATE_READY;
2011
if (rollup_make_fields(field_list, send_fields, &func))
2012
return(true); // Should never happen
2014
else if (rollup.state == ROLLUP::STATE_NONE)
2016
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2017
sum_funcs_end[i]= func;
2019
else if (rollup.state == ROLLUP::STATE_READY)
2020
return(false); // Don't put end marker
2021
*func=0; // End marker
2025
/** Allocate memory needed for other rollup functions. */
2026
bool JOIN::rollup_init()
2031
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2032
rollup.state= ROLLUP::STATE_INITED;
2035
Create pointers to the different sum function groups
2036
These are updated by rollup_make_fields()
2038
tmp_table_param.group_parts= send_group_parts;
2040
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2042
sizeof(List<Item>) +
2043
ref_pointer_array_size)
2044
* send_group_parts )))
2047
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2048
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2049
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2052
Prepare space for field list for the different levels
2053
These will be filled up in rollup_make_fields()
2055
for (i= 0 ; i < send_group_parts ; i++)
2057
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2058
List<Item> *rollup_fields= &rollup.fields[i];
2059
rollup_fields->empty();
2060
rollup.ref_pointer_arrays[i]= ref_array;
2061
ref_array+= all_fields.elements;
2063
for (i= 0 ; i < send_group_parts; i++)
2065
for (j=0 ; j < fields_list.elements ; j++)
2066
rollup.fields[i].push_back(rollup.null_items[i]);
2068
List_iterator<Item> it(all_fields);
2070
while ((item= it++))
2072
order_st *group_tmp;
2073
bool found_in_group= 0;
2075
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2077
if (*group_tmp->item == item)
2079
item->maybe_null= 1;
2081
if (item->const_item())
2084
For ROLLUP queries each constant item referenced in GROUP BY list
2085
is wrapped up into an Item_func object yielding the same value
2086
as the constant item. The objects of the wrapper class are never
2087
considered as constant items and besides they inherit all
2088
properties of the Item_result_field class.
2089
This wrapping allows us to ensure writing constant items
2090
into temporary tables whenever the result of the ROLLUP
2091
operation has to be written into a temporary table, e.g. when
2092
ROLLUP is used together with DISTINCT in the SELECT list.
2093
Usually when creating temporary tables for a intermidiate
2094
result we do not include fields for constant expressions.
2096
Item* new_item= new Item_func_rollup_const(item);
2099
new_item->fix_fields(session, (Item **) 0);
2100
session->change_item_tree(it.ref(), new_item);
2101
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2103
if (*tmp->item == item)
2104
session->change_item_tree(tmp->item, new_item);
2109
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2111
bool changed= false;
2112
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2115
We have to prevent creation of a field in a temporary table for
2116
an expression that contains GROUP BY attributes.
2117
Marking the expression item as 'with_sum_func' will ensure this.
2120
item->with_sum_func= 1;
2127
Fill up rollup structures with pointers to fields to use.
2129
Creates copies of item_sum items for each sum level.
2131
@param fields_arg List of all fields (hidden and real ones)
2132
@param sel_fields Pointer to selected fields
2133
@param func Store here a pointer to all fields
2137
In this case func is pointing to next not used element.
2141
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2143
List_iterator_fast<Item> it(fields_arg);
2144
Item *first_field= sel_fields.head();
2148
Create field lists for the different levels
2150
The idea here is to have a separate field list for each rollup level to
2151
avoid all runtime checks of which columns should be NULL.
2153
The list is stored in reverse order to get sum function in such an order
2154
in func that it makes it easy to reset them with init_sum_functions()
2156
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2158
rollup.fields[0] will contain list where a,b,c is NULL
2159
rollup.fields[1] will contain list where b,c is NULL
2161
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2163
sum_funcs_end[0] points to all sum functions
2164
sum_funcs_end[1] points to all sum functions, except grand totals
2168
for (level=0 ; level < send_group_parts ; level++)
2171
uint32_t pos= send_group_parts - level -1;
2172
bool real_fields= 0;
2174
List_iterator<Item> new_it(rollup.fields[pos]);
2175
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2176
order_st *start_group;
2178
/* Point to first hidden field */
2179
Item **ref_array= ref_array_start + fields_arg.elements-1;
2181
/* Remember where the sum functions ends for the previous level */
2182
sum_funcs_end[pos+1]= *func;
2184
/* Find the start of the group for this level */
2185
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2189
while ((item= it++))
2191
if (item == first_field)
2193
real_fields= 1; // End of hidden fields
2194
ref_array= ref_array_start;
2197
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2198
(!((Item_sum*) item)->depended_from() ||
2199
((Item_sum *)item)->depended_from() == select_lex))
2203
This is a top level summary function that must be replaced with
2204
a sum function that is reset for this level.
2206
NOTE: This code creates an object which is not that nice in a
2207
sub select. Fortunately it's not common to have rollup in
2210
item= item->copy_or_same(session);
2211
((Item_sum*) item)->make_unique();
2212
*(*func)= (Item_sum*) item;
2217
/* Check if this is something that is part of this group by */
2218
order_st *group_tmp;
2219
for (group_tmp= start_group, i= pos ;
2220
group_tmp ; group_tmp= group_tmp->next, i++)
2222
if (*group_tmp->item == item)
2225
This is an element that is used by the GROUP BY and should be
2226
set to NULL in this level
2228
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2231
item->maybe_null= 1; // Value will be null sometimes
2232
null_item->result_field= item->get_tmp_table_field();
2241
(void) new_it++; // Point to next item
2242
new_it.replace(item); // Replace previous
2249
sum_funcs_end[0]= *func; // Point to last function
2254
Send all rollup levels higher than the current one to the client.
2258
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2261
@param idx Level we are on:
2262
- 0 = Total sum level
2263
- 1 = First group changed (a)
2264
- 2 = Second group changed (a,b)
2269
1 If send_data_failed()
2271
int JOIN::rollup_send_data(uint32_t idx)
2274
for (i= send_group_parts ; i-- > idx ; )
2276
/* Get reference pointers to sum functions in place */
2277
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2278
ref_pointer_array_size);
2279
if ((!having || having->val_int()))
2281
if (send_records < unit->select_limit_cnt && do_send_rows &&
2282
result->send_data(rollup.fields[i]))
2287
/* Restore ref_pointer_array */
2288
set_items_ref_array(current_ref_pointer_array);
2293
Write all rollup levels higher than the current one to a temp table.
2297
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2300
@param idx Level we are on:
2301
- 0 = Total sum level
2302
- 1 = First group changed (a)
2303
- 2 = Second group changed (a,b)
2304
@param table reference to temp table
2309
1 if write_data_failed()
2311
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2314
for (i= send_group_parts ; i-- > idx ; )
2316
/* Get reference pointers to sum functions in place */
2317
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2318
ref_pointer_array_size);
2319
if ((!having || having->val_int()))
2323
List_iterator_fast<Item> it(rollup.fields[i]);
2324
while ((item= it++))
2326
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2327
item->save_in_result_field(1);
2329
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2330
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
2332
if (create_myisam_from_heap(session, table_arg,
2333
tmp_table_param.start_recinfo,
2334
&tmp_table_param.recinfo,
2340
/* Restore ref_pointer_array */
2341
set_items_ref_array(current_ref_pointer_array);
2346
clear results if there are not rows found for group
2347
(end_send_group/end_write_group)
2352
copy_fields(&tmp_table_param);
2356
Item_sum *func, **func_ptr= sum_funcs;
2357
while ((func= *(func_ptr++)))
2363
change select_result object of JOIN.
2365
@param res new select_result object
2372
bool JOIN::change_result(select_result *res)
2375
if (result->prepare(fields_list, select_lex->master_unit()))
2385
Process one record of the nested loop join.
2389
This function will evaluate parts of WHERE/ON clauses that are
2390
applicable to the partial record on hand and in case of success
2391
submit this record to the next level of the nested loop.
2393
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error)
2395
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2396
ha_rows found_records= join->found_records;
2397
COND *select_cond= join_tab->select_cond;
2399
if (error > 0 || (join->session->is_error())) // Fatal error
2400
return NESTED_LOOP_ERROR;
2402
return NESTED_LOOP_NO_MORE_ROWS;
2403
if (join->session->killed) // Aborted by user
2405
join->session->send_kill_message();
2406
return NESTED_LOOP_KILLED;
2408
if (!select_cond || select_cond->val_int())
2411
There is no select condition or the attached pushed down
2412
condition is true => a match is found.
2415
while (join_tab->first_unmatched && found)
2418
The while condition is always false if join_tab is not
2419
the last inner join table of an outer join operation.
2421
JoinTable *first_unmatched= join_tab->first_unmatched;
2423
Mark that a match for current outer table is found.
2424
This activates push down conditional predicates attached
2425
to the all inner tables of the outer join.
2427
first_unmatched->found= 1;
2428
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2430
if (tab->table->reginfo.not_exists_optimize)
2431
return NESTED_LOOP_NO_MORE_ROWS;
2432
/* Check all predicates that has just been activated. */
2434
Actually all predicates non-guarded by first_unmatched->found
2435
will be re-evaluated again. It could be fixed, but, probably,
2436
it's not worth doing now.
2438
if (tab->select_cond && !tab->select_cond->val_int())
2440
/* The condition attached to table tab is false */
2441
if (tab == join_tab)
2446
Set a return point if rejected predicate is attached
2447
not to the last table of the current nest level.
2449
join->return_tab= tab;
2450
return NESTED_LOOP_OK;
2455
Check whether join_tab is not the last inner table
2456
for another embedding outer join.
2458
if ((first_unmatched= first_unmatched->first_upper) &&
2459
first_unmatched->last_inner != join_tab)
2461
join_tab->first_unmatched= first_unmatched;
2464
JoinTable *return_tab= join->return_tab;
2465
join_tab->found_match= true;
2468
It was not just a return to lower loop level when one
2469
of the newly activated predicates is evaluated as false
2470
(See above join->return_tab= tab).
2472
join->examined_rows++;
2473
join->session->row_count++;
2477
enum enum_nested_loop_state rc;
2478
/* A match from join_tab is found for the current partial join. */
2479
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2480
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2482
if (return_tab < join->return_tab)
2483
join->return_tab= return_tab;
2485
if (join->return_tab < join_tab)
2486
return NESTED_LOOP_OK;
2488
Test if this was a SELECT DISTINCT query on a table that
2489
was not in the field list; In this case we can abort if
2490
we found a row, as no new rows can be added to the result.
2492
if (not_used_in_distinct && found_records != join->found_records)
2493
return NESTED_LOOP_NO_MORE_ROWS;
2496
join_tab->read_record.file->unlock_row();
2501
The condition pushed down to the table join_tab rejects all rows
2502
with the beginning coinciding with the current partial join.
2504
join->examined_rows++;
2505
join->session->row_count++;
2506
join_tab->read_record.file->unlock_row();
2508
return NESTED_LOOP_OK;
2513
Construct a NULL complimented partial join record and feed it to the next
2514
level of the nested loop. This function is used in case we have
2515
an OUTER join and no matching record was found.
2517
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab)
2520
The table join_tab is the first inner table of a outer join operation
2521
and no matches has been found for the current outer row.
2523
JoinTable *last_inner_tab= join_tab->last_inner;
2524
/* Cache variables for faster loop */
2526
for ( ; join_tab <= last_inner_tab ; join_tab++)
2528
/* Change the the values of guard predicate variables. */
2530
join_tab->not_null_compl= 0;
2531
/* The outer row is complemented by nulls for each inner tables */
2532
join_tab->table->restoreRecordAsDefault(); // Make empty record
2533
join_tab->table->mark_as_null_row(); // For group by without error
2534
select_cond= join_tab->select_cond;
2535
/* Check all attached conditions for inner table rows. */
2536
if (select_cond && !select_cond->val_int())
2537
return NESTED_LOOP_OK;
2541
The row complemented by nulls might be the first row
2542
of embedding outer joins.
2543
If so, perform the same actions as in the code
2544
for the first regular outer join row above.
2548
JoinTable *first_unmatched= join_tab->first_unmatched;
2549
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2551
join_tab->first_unmatched= first_unmatched;
2552
if (! first_unmatched)
2554
first_unmatched->found= 1;
2555
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2557
if (tab->select_cond && !tab->select_cond->val_int())
2559
join->return_tab= tab;
2560
return NESTED_LOOP_OK;
2565
The row complemented by nulls satisfies all conditions
2566
attached to inner tables.
2567
Send the row complemented by nulls to be joined with the
2570
return (*join_tab->next_select)(join, join_tab+1, 0);
2573
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last)
2575
enum_nested_loop_state rc= NESTED_LOOP_OK;
2579
join_tab->table->null_row= 0;
2580
if (!join_tab->cache.records)
2581
return NESTED_LOOP_OK; /* Nothing to do */
2583
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
2584
if (join_tab->use_quick == 2)
2586
if (join_tab->select->quick)
2587
{ /* Used quick select last. reset it */
2588
delete join_tab->select->quick;
2589
join_tab->select->quick=0;
2592
/* read through all records */
2593
if ((error=join_init_read_record(join_tab)))
2595
reset_cache_write(&join_tab->cache);
2596
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2599
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2601
tmp->status=tmp->table->status;
2602
tmp->table->status=0;
2605
info= &join_tab->read_record;
2608
if (join->session->killed)
2610
join->session->send_kill_message();
2611
return NESTED_LOOP_KILLED;
2613
SQL_SELECT *select=join_tab->select;
2614
if (rc == NESTED_LOOP_OK &&
2615
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2618
reset_cache_read(&join_tab->cache);
2619
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2621
join_tab->readCachedRecord();
2622
if (!select || !select->skip_record())
2626
rc= (join_tab->next_select)(join,join_tab+1,0);
2627
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2629
reset_cache_write(&join_tab->cache);
2634
return NESTED_LOOP_ERROR;
2638
} while (!(error=info->read_record(info)));
2641
join_tab->readCachedRecord(); // Restore current record
2642
reset_cache_write(&join_tab->cache);
2643
if (error > 0) // Fatal error
2644
return NESTED_LOOP_ERROR;
2645
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2646
tmp2->table->status=tmp2->status;
2647
return NESTED_LOOP_OK;
2650
/*****************************************************************************
2652
Functions that end one nested loop iteration. Different functions
2653
are used to support GROUP BY clause and to redirect records
2654
to a table (e.g. in case of SELECT into a temporary table) or to the
2658
NESTED_LOOP_OK - the record has been successfully handled
2659
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2661
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2663
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2664
additionally, the nested loop produced the
2665
number of rows specified in the LIMIT clause
2667
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2668
additionally, there is a cursor and the nested
2669
loop algorithm produced the number of rows
2670
that is specified for current cursor fetch
2672
All return values except NESTED_LOOP_OK abort the nested loop.
2673
*****************************************************************************/
2674
enum_nested_loop_state end_send(JOIN *join, JoinTable *, bool end_of_records)
2676
if (! end_of_records)
2679
if (join->having && join->having->val_int() == 0)
2680
return NESTED_LOOP_OK; // Didn't match having
2682
if (join->do_send_rows)
2683
error=join->result->send_data(*join->fields);
2685
return NESTED_LOOP_ERROR;
2686
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2688
if (join->select_options & OPTION_FOUND_ROWS)
2690
JoinTable *jt=join->join_tab;
2691
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2692
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2693
!(jt->select && jt->select->quick) &&
2694
(jt->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
2697
/* Join over all rows in table; Return number of found rows */
2698
Table *table= jt->table;
2700
join->select_options^= OPTION_FOUND_ROWS;
2701
if (table->sort.record_pointers ||
2702
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2704
/* Using filesort */
2705
join->send_records= table->sort.found_records;
2709
table->file->info(HA_STATUS_VARIABLE);
2710
join->send_records= table->file->stats.records;
2715
join->do_send_rows= 0;
2716
if (join->unit->fake_select_lex)
2717
join->unit->fake_select_lex->select_limit= 0;
2718
return NESTED_LOOP_OK;
2721
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2723
else if (join->send_records >= join->fetch_limit)
2726
There is a server side cursor and all rows for
2727
this fetch request are sent.
2729
return NESTED_LOOP_CURSOR_LIMIT;
2733
return NESTED_LOOP_OK;
2736
enum_nested_loop_state end_write(JOIN *join, JoinTable *, bool end_of_records)
2738
Table *table= join->tmp_table;
2740
if (join->session->killed) // Aborted by user
2742
join->session->send_kill_message();
2743
return NESTED_LOOP_KILLED;
2745
if (!end_of_records)
2747
copy_fields(&join->tmp_table_param);
2748
copy_funcs(join->tmp_table_param.items_to_copy);
2749
if (!join->having || join->having->val_int())
2752
join->found_records++;
2753
if ((error=table->file->ha_write_row(table->record[0])))
2755
if (!table->file->is_fatal_error(error, HA_CHECK_DUP))
2757
if (create_myisam_from_heap(join->session, table,
2758
join->tmp_table_param.start_recinfo,
2759
&join->tmp_table_param.recinfo,
2761
return NESTED_LOOP_ERROR; // Not a table_is_full error
2762
table->s->uniques= 0; // To ensure rows are the same
2764
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2766
if (!(join->select_options & OPTION_FOUND_ROWS))
2767
return NESTED_LOOP_QUERY_LIMIT;
2768
join->do_send_rows= 0;
2769
join->unit->select_limit_cnt= HA_POS_ERROR;
2770
return NESTED_LOOP_OK;
2775
return NESTED_LOOP_OK;
2778
/** Group by searching after group record and updating it if possible. */
2779
enum_nested_loop_state end_update(JOIN *join, JoinTable *, bool end_of_records)
2781
Table *table= join->tmp_table;
2786
return NESTED_LOOP_OK;
2787
if (join->session->killed) // Aborted by user
2789
join->session->send_kill_message();
2790
return NESTED_LOOP_KILLED;
2793
join->found_records++;
2794
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2795
/* Make a key of group index */
2796
for (group=table->group ; group ; group=group->next)
2798
Item *item= *group->item;
2799
item->save_org_in_field(group->field);
2800
/* Store in the used key if the field was 0 */
2801
if (item->maybe_null)
2802
group->buff[-1]= (char) group->field->is_null();
2804
if (!table->file->index_read_map(table->record[1],
2805
join->tmp_table_param.group_buff,
2808
{ /* Update old record */
2809
table->restoreRecord();
2810
update_tmptable_sum_func(join->sum_funcs,table);
2811
if ((error= table->file->ha_update_row(table->record[1],
2814
table->file->print_error(error,MYF(0));
2815
return NESTED_LOOP_ERROR;
2817
return NESTED_LOOP_OK;
2821
Copy null bits from group key to table
2822
We can't copy all data as the key may have different format
2823
as the row data (for example as with VARCHAR keys)
2825
KEY_PART_INFO *key_part;
2826
for (group=table->group,key_part=table->key_info[0].key_part;
2828
group=group->next,key_part++)
2830
if (key_part->null_bit)
2831
memcpy(table->record[0]+key_part->offset, group->buff, 1);
2833
init_tmptable_sum_functions(join->sum_funcs);
2834
copy_funcs(join->tmp_table_param.items_to_copy);
2835
if ((error=table->file->ha_write_row(table->record[0])))
2837
if (create_myisam_from_heap(join->session, table,
2838
join->tmp_table_param.start_recinfo,
2839
&join->tmp_table_param.recinfo,
2841
return NESTED_LOOP_ERROR; // Not a table_is_full error
2842
/* Change method to update rows */
2843
table->file->ha_index_init(0, 0);
2844
join->join_tab[join->tables-1].next_select= end_unique_update;
2846
join->send_records++;
2847
return NESTED_LOOP_OK;
2850
/** Like end_update, but this is done with unique constraints instead of keys. */
2851
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *, bool end_of_records)
2853
Table *table= join->tmp_table;
2857
return NESTED_LOOP_OK;
2858
if (join->session->killed) // Aborted by user
2860
join->session->send_kill_message();
2861
return NESTED_LOOP_KILLED;
2864
init_tmptable_sum_functions(join->sum_funcs);
2865
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2866
copy_funcs(join->tmp_table_param.items_to_copy);
2868
if (!(error= table->file->ha_write_row(table->record[0])))
2869
join->send_records++; // New group
2872
if ((int) table->file->get_dup_key(error) < 0)
2874
table->file->print_error(error,MYF(0));
2875
return NESTED_LOOP_ERROR;
2877
if (table->file->rnd_pos(table->record[1],table->file->dup_ref))
2879
table->file->print_error(error,MYF(0));
2880
return NESTED_LOOP_ERROR;
2882
table->restoreRecord();
2883
update_tmptable_sum_func(join->sum_funcs,table);
2884
if ((error= table->file->ha_update_row(table->record[1],
2887
table->file->print_error(error,MYF(0));
2888
return NESTED_LOOP_ERROR;
2891
return NESTED_LOOP_OK;
2895
allocate group fields or take prepared (cached).
2897
@param main_join join of current select
2898
@param curr_join current join (join of current select or temporary copy
2906
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
2908
if (main_join->group_fields_cache.elements)
2910
curr_join->group_fields= main_join->group_fields_cache;
2911
curr_join->sort_and_group= 1;
2915
if (alloc_group_fields(curr_join, curr_join->group_list))
2917
main_join->group_fields_cache= curr_join->group_fields;
2923
calc how big buffer we need for comparing group entries.
2925
static void calc_group_buffer(JOIN *join,order_st *group)
2927
uint32_t key_length=0, parts=0, null_parts=0;
2931
for (; group ; group=group->next)
2933
Item *group_item= *group->item;
2934
Field *field= group_item->get_tmp_table_field();
2937
enum_field_types type;
2938
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
2939
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
2940
else if (type == DRIZZLE_TYPE_VARCHAR)
2941
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
2943
key_length+= field->pack_length();
2947
switch (group_item->result_type()) {
2949
key_length+= sizeof(double);
2952
key_length+= sizeof(int64_t);
2954
case DECIMAL_RESULT:
2955
key_length+= my_decimal_get_binary_size(group_item->max_length -
2956
(group_item->decimals ? 1 : 0),
2957
group_item->decimals);
2961
enum enum_field_types type= group_item->field_type();
2963
As items represented as DATE/TIME fields in the group buffer
2964
have STRING_RESULT result type, we increase the length
2965
by 8 as maximum pack length of such fields.
2967
if (type == DRIZZLE_TYPE_DATE ||
2968
type == DRIZZLE_TYPE_DATETIME ||
2969
type == DRIZZLE_TYPE_TIMESTAMP)
2976
Group strings are taken as varstrings and require an length field.
2977
A field is not yet created by create_tmp_field()
2978
and the sizes should match up.
2980
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
2985
/* This case should never be choosen */
2987
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
2991
if (group_item->maybe_null)
2994
join->tmp_table_param.group_length=key_length+null_parts;
2995
join->tmp_table_param.group_parts=parts;
2996
join->tmp_table_param.group_null_parts=null_parts;
3000
Get a list of buffers for saveing last group.
3002
Groups are saved in reverse order for easyer check loop.
3004
static bool alloc_group_fields(JOIN *join,order_st *group)
3008
for (; group ; group=group->next)
3010
Cached_item *tmp=new_Cached_item(join->session, *group->item, false);
3011
if (!tmp || join->group_fields.push_front(tmp))
3015
join->sort_and_group=1; /* Mark for do_select */
3019
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3022
JoinTable **pos,**end;
3023
Session *session=join->session;
3025
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3029
JoinTable *join_tab= *pos;
3030
if (!join_tab->used_fieldlength) /* Not calced yet */
3031
calc_used_field_length(session, join_tab);
3032
length+=join_tab->used_fieldlength;
3038
Get the number of different row combinations for subset of partial join
3042
join The join structure
3043
idx Number of tables in the partial join order (i.e. the
3044
partial join order is in join->positions[0..idx-1])
3045
found_ref Bitmap of tables for which we need to find # of distinct
3049
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3050
tables within that join order (specified in found_ref), find out how many
3051
distinct row combinations of subset tables will be in the result of the
3054
This is used as follows: Suppose we have a table accessed with a ref-based
3055
method. The ref access depends on current rows of tables in found_ref.
3056
We want to count # of different ref accesses. We assume two ref accesses
3057
will be different if at least one of access parameters is different.
3058
Example: consider a query
3060
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3063
t1, ref access on t1.key=c1
3064
t2, ref access on t2.key=c2
3065
t3, ref access on t3.key=t1.field
3067
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3068
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3069
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3070
n_distinct_ref_scans = #records_read(t1)
3072
The reason for having this function (at least the latest version of it)
3073
is that we need to account for buffering in join execution.
3075
An edge-case example: if we have a non-first table in join accessed via
3076
ref(const) or ref(param) where there is a small number of different
3077
values of param, then the access will likely hit the disk cache and will
3078
not require any disk seeks.
3080
The proper solution would be to assume an LRU disk cache of some size,
3081
calculate probability of cache hits, etc. For now we just count
3082
identical ref accesses as one.
3085
Expected number of row combinations
3087
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3090
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3091
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3095
if (pos->examinePosition(found_ref))
3097
found_ref|= pos->getRefDependMap();
3099
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3100
with no matching row we will get position[t2].records_read==0.
3101
Actually the size of output is one null-complemented row, therefore
3102
we will use value of 1 whenever we get records_read==0.
3105
- the above case can't occur if inner part of outer join has more
3106
than one table: table with no matches will not be marked as const.
3108
- Ideally we should add 1 to records_read for every possible null-
3109
complemented row. We're not doing it because: 1. it will require
3110
non-trivial code and add overhead. 2. The value of records_read
3111
is an inprecise estimate and adding 1 (or, in the worst case,
3112
#max_nested_outer_joins=64-1) will not make it any more precise.
3114
if (pos->getFanout() > DBL_EPSILON)
3115
found*= pos->getFanout();
3122
Set up join struct according to best position.
3124
static bool get_best_combination(JOIN *join)
3127
table_map used_tables;
3128
JoinTable *join_tab,*j;
3129
optimizer::KeyUse *keyuse;
3130
uint32_t table_count;
3131
Session *session=join->session;
3132
optimizer::Position cur_pos;
3134
table_count=join->tables;
3135
if (!(join->join_tab=join_tab=
3136
(JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))
3141
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3142
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3145
cur_pos= join->getPosFromOptimalPlan(tablenr);
3146
*j= *cur_pos.getJoinTable();
3147
form=join->table[tablenr]=j->table;
3148
used_tables|= form->map;
3149
form->reginfo.join_tab=j;
3150
if (!*j->on_expr_ref)
3151
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
3152
if (j->type == AM_CONST)
3153
continue; // Handled in make_join_stat..
3158
if (j->type == AM_SYSTEM)
3160
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3163
if (tablenr != join->const_tables)
3166
else if (create_ref_for_key(join, j, keyuse, used_tables))
3167
return(true); // Something went wrong
3170
for (i=0 ; i < table_count ; i++)
3171
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3172
update_depend_map(join);
3176
/** Save const tables first as used tables. */
3177
static void set_position(JOIN *join,
3180
optimizer::KeyUse *key)
3182
optimizer::Position tmp_pos(1.0, /* This is a const table */
3187
join->setPosInPartialPlan(idx, tmp_pos);
3189
/* Move the const table as down as possible in best_ref */
3190
JoinTable **pos=join->best_ref+idx+1;
3191
JoinTable *next=join->best_ref[idx];
3192
for (;next != table ; pos++)
3194
JoinTable *tmp=pos[0];
3198
join->best_ref[idx]=table;
3202
Selects and invokes a search strategy for an optimal query plan.
3204
The function checks user-configurable parameters that control the search
3205
strategy for an optimal plan, selects the search method and then invokes
3206
it. Each specific optimization procedure stores the final optimal plan in
3207
the array 'join->best_positions', and the cost of the plan in
3210
@param join pointer to the structure providing all context info for
3212
@param join_tables set of the tables in the query
3219
static bool choose_plan(JOIN *join, table_map join_tables)
3221
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3222
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3223
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3225
join->cur_embedding_map.reset();
3226
reset_nj_counters(join->join_list);
3228
if (SELECT_STRAIGHT_JOIN option is set)
3229
reorder tables so dependent tables come after tables they depend
3230
on, otherwise keep tables in the order they were specified in the query
3232
Apply heuristic: pre-sort all access plans with respect to the number of
3235
my_qsort(join->best_ref + join->const_tables,
3236
join->tables - join->const_tables, sizeof(JoinTable*),
3237
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3240
optimize_straight_join(join, join_tables);
3244
if (search_depth == 0)
3245
/* Automatically determine a reasonable value for 'search_depth' */
3246
search_depth= determine_search_depth(join);
3247
if (greedy_search(join, join_tables, search_depth, prune_level))
3252
Store the cost of this query into a user variable
3253
Don't update last_query_cost for statements that are not "flat joins" :
3254
i.e. they have subqueries, unions or call stored procedures.
3255
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3257
if (join->session->lex->is_single_level_stmt())
3258
join->session->status_var.last_query_cost= join->best_read;
3263
Find the best access path for an extension of a partial execution
3264
plan and add this path to the plan.
3266
The function finds the best access path to table 's' from the passed
3267
partial plan where an access path is the general term for any means to
3268
access the data in 's'. An access path may use either an index or a scan,
3269
whichever is cheaper. The input partial plan is passed via the array
3270
'join->positions' of length 'idx'. The chosen access method for 's' and its
3271
cost are stored in 'join->positions[idx]'.
3273
@param join pointer to the structure providing all context info
3275
@param s the table to be joined by the function
3276
@param session thread for the connection that submitted the query
3277
@param remaining_tables set of tables not included into the partial plan yet
3278
@param idx the length of the partial plan
3279
@param record_count estimate for the number of records returned by the
3281
@param read_time the cost of the partial plan
3286
static void best_access_path(JOIN *join,
3289
table_map remaining_tables,
3291
double record_count,
3294
optimizer::KeyUse *best_key= NULL;
3295
uint32_t best_max_key_part= NULL;
3296
bool found_constraint= 0;
3297
double best= DBL_MAX;
3298
double best_time= DBL_MAX;
3299
double records= DBL_MAX;
3300
table_map best_ref_depends_map= 0;
3305
{ /* Use key if possible */
3306
Table *table= s->table;
3307
optimizer::KeyUse *keyuse= NULL;
3308
optimizer::KeyUse *start_key= NULL;
3309
double best_records= DBL_MAX;
3310
uint32_t max_key_part=0;
3312
/* Test how we can use keys */
3313
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3314
for (keyuse= s->keyuse; keyuse->getTable() == table; )
3316
key_part_map found_part= 0;
3317
table_map found_ref= 0;
3318
uint32_t key= keyuse->getKey();
3319
KEY *keyinfo= table->key_info + key;
3320
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3321
key_part_map const_part= 0;
3322
/* The or-null keypart in ref-or-null access: */
3323
key_part_map ref_or_null_part= 0;
3325
/* Calculate how many key segments of the current key we can use */
3328
do /* For each keypart */
3330
uint32_t keypart= keyuse->getKeypart();
3331
table_map best_part_found_ref= 0;
3332
double best_prev_record_reads= DBL_MAX;
3334
do /* For each way to access the keypart */
3338
if 1. expression doesn't refer to forward tables
3339
2. we won't get two ref-or-null's
3341
if (! (remaining_tables & keyuse->getUsedTables()) &&
3342
! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3343
KEY_OPTIMIZE_REF_OR_NULL)))
3345
found_part|= keyuse->getKeypartMap();
3346
if (! (keyuse->getUsedTables() & ~join->const_table_map))
3347
const_part|= keyuse->getKeypartMap();
3349
double tmp2= prev_record_reads(join, idx, (found_ref |
3350
keyuse->getUsedTables()));
3351
if (tmp2 < best_prev_record_reads)
3353
best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
3354
best_prev_record_reads= tmp2;
3356
if (rec > keyuse->getTableRows())
3357
rec= keyuse->getTableRows();
3359
If there is one 'key_column IS NULL' expression, we can
3360
use this ref_or_null optimisation of this field
3362
if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3363
ref_or_null_part|= keyuse->getKeypartMap();
3367
} while (keyuse->getTable() == table && keyuse->getKey() == key &&
3368
keyuse->getKeypart() == keypart);
3369
found_ref|= best_part_found_ref;
3370
} while (keyuse->getTable() == table && keyuse->getKey() == key);
3373
Assume that that each key matches a proportional part of table.
3376
continue; // Nothing usable found
3378
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3379
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3382
found_constraint= 1;
3385
Check if we found full key
3387
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3390
max_key_part= UINT32_MAX;
3391
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3393
tmp = prev_record_reads(join, idx, found_ref);
3399
{ /* We found a const key */
3401
ReuseRangeEstimateForRef-1:
3402
We get here if we've found a ref(const) (c_i are constants):
3403
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3405
If range optimizer was able to construct a "range"
3406
access on this index, then its condition "quick_cond" was
3407
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3408
from the range optimizer.
3410
Proof of (*): By properties of range and ref optimizers
3411
quick_cond will be equal or tighther than ref_const_cond.
3412
ref_const_cond already covers "smallest" possible interval -
3413
a singlepoint interval over all keyparts. Therefore,
3414
quick_cond is equivalent to ref_const_cond (if it was an
3415
empty interval we wouldn't have got here).
3417
if (table->quick_keys.test(key))
3418
records= (double) table->quick_rows[key];
3421
/* quick_range couldn't use key! */
3422
records= (double) s->records/rec;
3427
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3428
{ /* Prefer longer keys */
3430
((double) s->records / (double) rec *
3432
((double) (table->s->max_key_length-keyinfo->key_length) /
3433
(double) table->s->max_key_length)));
3435
records=2.0; /* Can't be as good as a unique */
3438
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3439
E(#rows) from range optimizer. Make another try:
3441
If range optimizer produced E(#rows) for a prefix of the ref
3442
access we're considering, and that E(#rows) is lower then our
3443
current estimate, make an adjustment. The criteria of when we
3444
can make an adjustment is a special case of the criteria used
3445
in ReuseRangeEstimateForRef-3.
3447
if (table->quick_keys.test(key) &&
3448
const_part & (1 << table->quick_key_parts[key]) &&
3449
table->quick_n_ranges[key] == 1 &&
3450
records > (double) table->quick_rows[key])
3452
records= (double) table->quick_rows[key];
3455
/* Limit the number of matched rows */
3457
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3458
if (table->covering_keys.test(key))
3460
/* we can use only index tree */
3461
tmp= record_count * table->file->index_only_read_time(key, tmp);
3464
tmp= record_count * min(tmp,s->worst_seeks);
3470
Use as much key-parts as possible and a uniq key is better
3471
than a not unique key
3472
Set tmp to (previous record count) * (records / combination)
3474
if ((found_part & 1) &&
3475
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
3476
found_part == PREV_BITS(uint,keyinfo->key_parts)))
3478
max_key_part= max_part_bit(found_part);
3480
ReuseRangeEstimateForRef-3:
3481
We're now considering a ref[or_null] access via
3482
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3483
(same-as-above but with one cond replaced
3484
with "t.keypart_i IS NULL")] (**)
3486
Try re-using E(#rows) from "range" optimizer:
3487
We can do so if "range" optimizer used the same intervals as
3488
in (**). The intervals used by range optimizer may be not
3489
available at this point (as "range" access might have choosen to
3490
create quick select over another index), so we can't compare
3491
them to (**). We'll make indirect judgements instead.
3492
The sufficient conditions for re-use are:
3493
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3494
this is not satisfied we have no way to know which ranges
3495
will be actually scanned by 'ref' until we execute the
3497
(C2) max #key parts in 'range' access == K == max_key_part (this
3498
is apparently a necessary requirement)
3500
We also have a property that "range optimizer produces equal or
3501
tighter set of scan intervals than ref(const) optimizer". Each
3502
of the intervals in (**) are "tightest possible" intervals when
3503
one limits itself to using keyparts 1..K (which we do in #2).
3504
From here it follows that range access used either one, or
3505
both of the (I1) and (I2) intervals:
3507
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3508
(same-as-above but with one cond replaced
3509
with "t.keypart_i IS NULL") (I2)
3511
The remaining part is to exclude the situation where range
3512
optimizer used one interval while we're considering
3513
ref-or-null and looking for estimate for two intervals. This
3514
is done by last limitation:
3516
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3518
if (table->quick_keys.test(key) && !found_ref && //(C1)
3519
table->quick_key_parts[key] == max_key_part && //(C2)
3520
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3522
tmp= records= (double) table->quick_rows[key];
3526
/* Check if we have statistic about the distribution */
3527
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3530
Fix for the case where the index statistics is too
3532
(1) We're considering ref(const) and there is quick select
3534
(2) and that quick select uses more keyparts (i.e. it will
3535
scan equal/smaller interval then this ref(const))
3536
(3) and E(#rows) for quick select is higher then our
3539
We'll use E(#rows) from quick select.
3541
Q: Why do we choose to use 'ref'? Won't quick select be
3542
cheaper in some cases ?
3543
TODO: figure this out and adjust the plan choice if needed.
3545
if (!found_ref && table->quick_keys.test(key) && // (1)
3546
table->quick_key_parts[key] > max_key_part && // (2)
3547
records < (double)table->quick_rows[key]) // (3)
3548
records= (double)table->quick_rows[key];
3555
Assume that the first key part matches 1% of the file
3556
and that the whole key matches 10 (duplicates) or 1
3558
Assume also that more key matches proportionally more
3560
This gives the formula:
3561
records = (x * (b-a) + a*c-b)/(c-1)
3563
b = records matched by whole key
3564
a = records matched by first key part (1% of all records?)
3565
c = number of key parts in key
3566
x = used key parts (1 <= x <= c)
3569
if (!(rec_per_key=(double)
3570
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3571
rec_per_key=(double) s->records/rec+1;
3575
else if (rec_per_key/(double) s->records >= 0.01)
3579
double a=s->records*0.01;
3580
if (keyinfo->key_parts > 1)
3581
tmp= (max_key_part * (rec_per_key - a) +
3582
a*keyinfo->key_parts - rec_per_key)/
3583
(keyinfo->key_parts-1);
3586
set_if_bigger(tmp,1.0);
3588
records = (uint32_t) tmp;
3591
if (ref_or_null_part)
3593
/* We need to do two key searches to find key */
3599
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3600
E(#rows) from range optimizer. Make another try:
3602
If range optimizer produced E(#rows) for a prefix of the ref
3603
access we're considering, and that E(#rows) is lower then our
3604
current estimate, make the adjustment.
3606
The decision whether we can re-use the estimate from the range
3607
optimizer is the same as in ReuseRangeEstimateForRef-3,
3608
applied to first table->quick_key_parts[key] key parts.
3610
if (table->quick_keys.test(key) &&
3611
table->quick_key_parts[key] <= max_key_part &&
3612
const_part & (1 << table->quick_key_parts[key]) &&
3613
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3614
const_part) ? 1 : 0) &&
3615
records > (double) table->quick_rows[key])
3617
tmp= records= (double) table->quick_rows[key];
3621
/* Limit the number of matched rows */
3622
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3623
if (table->covering_keys.test(key))
3625
/* we can use only index tree */
3626
tmp= record_count * table->file->index_only_read_time(key, tmp);
3629
tmp= record_count * min(tmp,s->worst_seeks);
3632
tmp= best_time; // Do nothing
3636
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3638
best_time= tmp + records/(double) TIME_FOR_COMPARE;
3640
best_records= records;
3641
best_key= start_key;
3642
best_max_key_part= max_key_part;
3643
best_ref_depends_map= found_ref;
3646
records= best_records;
3650
Don't test table scan if it can't be better.
3651
Prefer key lookup if we would use the same key for scanning.
3653
Don't do a table scan on InnoDB tables, if we can read the used
3654
parts of the row from any of the used index.
3655
This is because table scans uses index and we would not win
3656
anything by using a table scan.
3658
A word for word translation of the below if-statement in sergefp's
3659
understanding: we check if we should use table scan if:
3660
(1) The found 'ref' access produces more records than a table scan
3661
(or index scan, or quick select), or 'ref' is more expensive than
3663
(2) This doesn't hold: the best way to perform table scan is to to perform
3664
'range' access using index IDX, and the best way to perform 'ref'
3665
access is to use the same index IDX, with the same or more key parts.
3666
(note: it is not clear how this rule is/should be extended to
3667
index_merge quick selects)
3668
(3) See above note about InnoDB.
3669
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3670
path, but there is no quick select)
3671
If the condition in the above brackets holds, then the only possible
3672
"table scan" access method is ALL/index (there is no quick select).
3673
Since we have a 'ref' access path, and FORCE INDEX instructs us to
3674
choose it over ALL/index, there is no need to consider a full table
3677
if ((records >= s->found_records || best > s->read_time) && // (1)
3678
! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)
3679
best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3680
! ((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
3681
! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3682
! (s->table->force_index && best_key && !s->quick)) // (4)
3683
{ // Check full join
3684
ha_rows rnd_records= s->found_records;
3686
If there is a filtering condition on the table (i.e. ref analyzer found
3687
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3688
preceding this table in the join order we're now considering), then
3689
assume that 25% of the rows will be filtered out by this condition.
3691
This heuristic is supposed to force tables used in exprZ to be before
3692
this table in join order.
3694
if (found_constraint)
3695
rnd_records-= rnd_records/4;
3698
If applicable, get a more accurate estimate. Don't use the two
3701
if (s->table->quick_condition_rows != s->found_records)
3702
rnd_records= s->table->quick_condition_rows;
3705
Range optimizer never proposes a RANGE if it isn't better
3706
than FULL: so if RANGE is present, it's always preferred to FULL.
3707
Here we estimate its cost.
3713
- read record range through 'quick'
3714
- skip rows which does not satisfy WHERE constraints
3716
We take into account possible use of join cache for ALL/index
3717
access (see first else-branch below), but we don't take it into
3718
account here for range/index_merge access. Find out why this is so.
3721
(s->quick->read_time +
3722
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3726
/* Estimate cost of reading table. */
3727
tmp= s->table->file->scan_time();
3728
if (s->table->map & join->outer_join) // Can't use join cache
3731
For each record we have to:
3732
- read the whole table record
3733
- skip rows which does not satisfy join condition
3737
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
3741
/* We read the table as many times as join buffer becomes full. */
3742
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
3744
(double) session->variables.join_buff_size));
3746
We don't make full cartesian product between rows in the scanned
3747
table and existing records because we skip all rows from the
3748
scanned table, which does not satisfy join condition when
3749
we read the table (see flush_cached_records for details). Here we
3750
take into account cost to read and skip these records.
3752
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
3757
We estimate the cost of evaluating WHERE clause for found records
3758
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
3759
tmp give us total cost of using Table SCAN
3761
if (best == DBL_MAX ||
3762
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
3763
best + record_count/(double) TIME_FOR_COMPARE*records))
3766
If the table has a range (s->quick is set) make_join_select()
3767
will ensure that this will be used
3770
records= rows2double(rnd_records);
3772
/* range/index_merge/ALL/index access method are "independent", so: */
3773
best_ref_depends_map= 0;
3777
/* Update the cost information for the current partial plan */
3778
optimizer::Position tmp_pos(records,
3782
best_ref_depends_map);
3783
join->setPosInPartialPlan(idx, tmp_pos);
3786
idx == join->const_tables &&
3787
s->table == join->sort_by_table &&
3788
join->unit->select_limit_cnt >= records)
3789
join->sort_by_table= (Table*) 1; // Must use temporary table
3795
Select the best ways to access the tables in a query without reordering them.
3797
Find the best access paths for each query table and compute their costs
3798
according to their order in the array 'join->best_ref' (thus without
3799
reordering the join tables). The function calls sequentially
3800
'best_access_path' for each table in the query to select the best table
3801
access method. The final optimal plan is stored in the array
3802
'join->best_positions', and the corresponding cost in 'join->best_read'.
3804
@param join pointer to the structure providing all context info for
3806
@param join_tables set of the tables in the query
3809
This function can be applied to:
3810
- queries with STRAIGHT_JOIN
3811
- internally to compute the cost of an arbitrary QEP
3813
Thus 'optimize_straight_join' can be used at any stage of the query
3814
optimization process to finalize a QEP as it is.
3816
static void optimize_straight_join(JOIN *join, table_map join_tables)
3819
optimizer::Position partial_pos;
3820
uint32_t idx= join->const_tables;
3821
double record_count= 1.0;
3822
double read_time= 0.0;
3824
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
3826
/* Find the best access method from 's' to the current partial plan */
3827
best_access_path(join, s, join->session, join_tables, idx,
3828
record_count, read_time);
3829
/* compute the cost of the new plan extended with 's' */
3830
partial_pos= join->getPosFromPartialPlan(idx);
3831
record_count*= partial_pos.getFanout();
3832
read_time+= partial_pos.getCost();
3833
join_tables&= ~(s->table->map);
3837
read_time+= record_count / (double) TIME_FOR_COMPARE;
3838
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3839
if (join->sort_by_table &&
3840
partial_pos.hasTableForSorting(join->sort_by_table))
3841
read_time+= record_count; // We have to make a temp table
3842
join->copyPartialPlanIntoOptimalPlan(idx);
3843
join->best_read= read_time;
3847
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
3849
The search procedure uses a hybrid greedy/exhaustive search with controlled
3850
exhaustiveness. The search is performed in N = card(remaining_tables)
3851
steps. Each step evaluates how promising is each of the unoptimized tables,
3852
selects the most promising table, and extends the current partial QEP with
3853
that table. Currenly the most 'promising' table is the one with least
3854
expensive extension.\
3856
There are two extreme cases:
3857
-# When (card(remaining_tables) < search_depth), the estimate finds the
3858
best complete continuation of the partial QEP. This continuation can be
3859
used directly as a result of the search.
3860
-# When (search_depth == 1) the 'best_extension_by_limited_search'
3861
consideres the extension of the current QEP with each of the remaining
3864
All other cases are in-between these two extremes. Thus the parameter
3865
'search_depth' controlls the exhaustiveness of the search. The higher the
3866
value, the longer the optimizaton time and possibly the better the
3867
resulting plan. The lower the value, the fewer alternative plans are
3868
estimated, but the more likely to get a bad QEP.
3870
All intermediate and final results of the procedure are stored in 'join':
3871
- join->positions : modified for every partial QEP that is explored
3872
- join->best_positions: modified for the current best complete QEP
3873
- join->best_read : modified for the current best complete QEP
3874
- join->best_ref : might be partially reordered
3876
The final optimal plan is stored in 'join->best_positions', and its
3877
corresponding cost in 'join->best_read'.
3880
The following pseudocode describes the algorithm of 'greedy_search':
3883
procedure greedy_search
3884
input: remaining_tables
3889
(t, a) = best_extension(pplan, remaining_tables);
3890
pplan = concat(pplan, (t, a));
3891
remaining_tables = remaining_tables - t;
3892
} while (remaining_tables != {})
3897
where 'best_extension' is a placeholder for a procedure that selects the
3898
most "promising" of all tables in 'remaining_tables'.
3899
Currently this estimate is performed by calling
3900
'best_extension_by_limited_search' to evaluate all extensions of the
3901
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
3902
mainly depends on that of 'best_extension_by_limited_search'.
3905
If 'best_extension()' == 'best_extension_by_limited_search()', then the
3906
worst-case complexity of this algorithm is <=
3907
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
3908
complexity of greedy_search is O(N!).
3911
In the future, 'greedy_search' might be extended to support other
3912
implementations of 'best_extension', e.g. some simpler quadratic procedure.
3914
@param join pointer to the structure providing all context info
3916
@param remaining_tables set of tables not included into the partial plan yet
3917
@param search_depth controlls the exhaustiveness of the search
3918
@param prune_level the pruning heuristics that should be applied during
3926
static bool greedy_search(JOIN *join,
3927
table_map remaining_tables,
3928
uint32_t search_depth,
3929
uint32_t prune_level)
3931
double record_count= 1.0;
3932
double read_time= 0.0;
3933
uint32_t idx= join->const_tables; // index into 'join->best_ref'
3935
uint32_t size_remain; // cardinality of remaining_tables
3936
optimizer::Position best_pos;
3937
JoinTable *best_table; // the next plan node to be added to the curr QEP
3939
/* number of tables that remain to be optimized */
3940
size_remain= my_count_bits(remaining_tables);
3943
/* Find the extension of the current QEP with the lowest cost */
3944
join->best_read= DBL_MAX;
3945
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
3946
read_time, search_depth, prune_level))
3949
if (size_remain <= search_depth)
3952
'join->best_positions' contains a complete optimal extension of the
3953
current partial QEP.
3958
/* select the first table in the optimal extension as most promising */
3959
best_pos= join->getPosFromOptimalPlan(idx);
3960
best_table= best_pos.getJoinTable();
3962
Each subsequent loop of 'best_extension_by_limited_search' uses
3963
'join->positions' for cost estimates, therefore we have to update its
3966
join->setPosInPartialPlan(idx, best_pos);
3968
/* find the position of 'best_table' in 'join->best_ref' */
3970
JoinTable *pos= join->best_ref[best_idx];
3971
while (pos && best_table != pos)
3972
pos= join->best_ref[++best_idx];
3973
assert((pos != NULL)); // should always find 'best_table'
3974
/* move 'best_table' at the first free position in the array of joins */
3975
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
3977
/* compute the cost of the new plan extended with 'best_table' */
3978
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
3979
record_count*= partial_pos.getFanout();
3980
read_time+= partial_pos.getCost();
3982
remaining_tables&= ~(best_table->table->map);
3990
Find a good, possibly optimal, query execution plan (QEP) by a possibly
3993
The procedure searches for the optimal ordering of the query tables in set
3994
'remaining_tables' of size N, and the corresponding optimal access paths to
3995
each table. The choice of a table order and an access path for each table
3996
constitutes a query execution plan (QEP) that fully specifies how to
3999
The maximal size of the found plan is controlled by the parameter
4000
'search_depth'. When search_depth == N, the resulting plan is complete and
4001
can be used directly as a QEP. If search_depth < N, the found plan consists
4002
of only some of the query tables. Such "partial" optimal plans are useful
4003
only as input to query optimization procedures, and cannot be used directly
4006
The algorithm begins with an empty partial plan stored in 'join->positions'
4007
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4008
evaluates the cost of the partial plan extended by all access plans for
4009
each of the relations in 'remaining_tables', expands the current partial
4010
plan with the access plan that results in lowest cost of the expanded
4011
partial plan, and removes the corresponding relation from
4012
'remaining_tables'. The algorithm continues until it either constructs a
4013
complete optimal plan, or constructs an optimal plartial plan with size =
4016
The final optimal plan is stored in 'join->best_positions'. The
4017
corresponding cost of the optimal plan is in 'join->best_read'.
4020
The procedure uses a recursive depth-first search where the depth of the
4021
recursion (and thus the exhaustiveness of the search) is controlled by the
4022
parameter 'search_depth'.
4025
The pseudocode below describes the algorithm of
4026
'best_extension_by_limited_search'. The worst-case complexity of this
4027
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4028
the complexity of greedy_search is O(N!).
4031
procedure best_extension_by_limited_search(
4032
pplan in, // in, partial plan of tables-joined-so-far
4033
pplan_cost, // in, cost of pplan
4034
remaining_tables, // in, set of tables not referenced in pplan
4035
best_plan_so_far, // in/out, best plan found so far
4036
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4037
search_depth) // in, maximum size of the plans being considered
4039
for each table T from remaining_tables
4041
// Calculate the cost of using table T as above
4042
cost = complex-series-of-calculations;
4044
// Add the cost to the cost so far.
4047
if (pplan_cost >= best_plan_so_far_cost)
4048
// pplan_cost already too great, stop search
4051
pplan= expand pplan by best_access_method;
4052
remaining_tables= remaining_tables - table T;
4053
if (remaining_tables is not an empty set
4057
best_extension_by_limited_search(pplan, pplan_cost,
4060
best_plan_so_far_cost,
4065
best_plan_so_far_cost= pplan_cost;
4066
best_plan_so_far= pplan;
4073
When 'best_extension_by_limited_search' is called for the first time,
4074
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4075
The actual implementation provides a way to optionally use pruning
4076
heuristic (controlled by the parameter 'prune_level') to reduce the search
4077
space by skipping some partial plans.
4080
The parameter 'search_depth' provides control over the recursion
4081
depth, and thus the size of the resulting optimal plan.
4083
@param join pointer to the structure providing all context info
4085
@param remaining_tables set of tables not included into the partial plan yet
4086
@param idx length of the partial QEP in 'join->positions';
4087
since a depth-first search is used, also corresponds
4088
to the current depth of the search tree;
4089
also an index in the array 'join->best_ref';
4090
@param record_count estimate for the number of records returned by the
4092
@param read_time the cost of the best partial plan
4093
@param search_depth maximum depth of the recursion and thus size of the
4095
(0 < search_depth <= join->tables+1).
4096
@param prune_level pruning heuristics that should be applied during
4098
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4105
static bool best_extension_by_limited_search(JOIN *join,
4106
table_map remaining_tables,
4108
double record_count,
4110
uint32_t search_depth,
4111
uint32_t prune_level)
4113
Session *session= join->session;
4114
if (session->killed) // Abort
4118
'join' is a partial plan with lower cost than the best plan so far,
4119
so continue expanding it further with the tables in 'remaining_tables'.
4122
double best_record_count= DBL_MAX;
4123
double best_read_time= DBL_MAX;
4124
optimizer::Position partial_pos;
4126
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4128
table_map real_table_bit= s->table->map;
4131
partial_pos= join->getPosFromPartialPlan(idx - 1);
4133
if ((remaining_tables & real_table_bit) &&
4134
! (remaining_tables & s->dependent) &&
4135
(! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
4137
double current_record_count, current_read_time;
4140
psergey-insideout-todo:
4141
when best_access_path() detects it could do an InsideOut scan or
4142
some other scan, have it return an insideout scan and a flag that
4143
requests to "fork" this loop iteration. (Q: how does that behave
4144
when the depth is insufficient??)
4146
/* Find the best access method from 's' to the current partial plan */
4147
best_access_path(join, s, session, remaining_tables, idx,
4148
record_count, read_time);
4149
/* Compute the cost of extending the plan with 's' */
4150
partial_pos= join->getPosFromPartialPlan(idx);
4151
current_record_count= record_count * partial_pos.getFanout();
4152
current_read_time= read_time + partial_pos.getCost();
4154
/* Expand only partial plans with lower cost than the best QEP so far */
4155
if ((current_read_time +
4156
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4158
restore_prev_nj_state(s);
4163
Prune some less promising partial plans. This heuristic may miss
4164
the optimal QEPs, thus it results in a non-exhaustive search.
4166
if (prune_level == 1)
4168
if (best_record_count > current_record_count ||
4169
best_read_time > current_read_time ||
4170
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4172
if (best_record_count >= current_record_count &&
4173
best_read_time >= current_read_time &&
4174
/* TODO: What is the reasoning behind this condition? */
4175
(! (s->key_dependent & remaining_tables) ||
4176
partial_pos.isConstTable()))
4178
best_record_count= current_record_count;
4179
best_read_time= current_read_time;
4184
restore_prev_nj_state(s);
4189
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4190
{ /* Recursively expand the current partial plan */
4191
std::swap(join->best_ref[idx], *pos);
4192
if (best_extension_by_limited_search(join,
4193
remaining_tables & ~real_table_bit,
4195
current_record_count,
4200
std::swap(join->best_ref[idx], *pos);
4204
'join' is either the best partial QEP with 'search_depth' relations,
4205
or the best complete QEP so far, whichever is smaller.
4207
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4208
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4209
if (join->sort_by_table &&
4210
partial_pos.hasTableForSorting(join->sort_by_table))
4211
/* We have to make a temp table */
4212
current_read_time+= current_record_count;
4213
if ((search_depth == 1) || (current_read_time < join->best_read))
4215
join->copyPartialPlanIntoOptimalPlan(idx + 1);
4216
join->best_read= current_read_time - 0.001;
4219
restore_prev_nj_state(s);
4226
Heuristic procedure to automatically guess a reasonable degree of
4227
exhaustiveness for the greedy search procedure.
4229
The procedure estimates the optimization time and selects a search depth
4230
big enough to result in a near-optimal QEP, that doesn't take too long to
4231
find. If the number of tables in the query exceeds some constant, then
4232
search_depth is set to this constant.
4234
@param join pointer to the structure providing all context info for
4238
This is an extremely simplistic implementation that serves as a stub for a
4239
more advanced analysis of the join. Ideally the search depth should be
4240
determined by learning from previous query optimizations, because it will
4241
depend on the CPU power (and other factors).
4244
this value should be determined dynamically, based on statistics:
4245
uint32_t max_tables_for_exhaustive_opt= 7;
4248
this value could be determined by some mapping of the form:
4249
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4252
A positive integer that specifies the search depth (and thus the
4253
exhaustiveness) of the depth-first search algorithm used by
4256
static uint32_t determine_search_depth(JOIN *join)
4258
uint32_t table_count= join->tables - join->const_tables;
4259
uint32_t search_depth;
4260
/* TODO: this value should be determined dynamically, based on statistics: */
4261
uint32_t max_tables_for_exhaustive_opt= 7;
4263
if (table_count <= max_tables_for_exhaustive_opt)
4264
search_depth= table_count+1; // use exhaustive for small number of tables
4267
TODO: this value could be determined by some mapping of the form:
4268
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4270
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4272
return search_depth;
4275
static bool make_simple_join(JOIN *join,Table *tmp_table)
4278
JoinTable *join_tab;
4281
Reuse Table * and JoinTable if already allocated by a previous call
4282
to this function through JOIN::exec (may happen for sub-queries).
4284
if (!join->table_reexec)
4286
if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
4289
join->tmp_join->table_reexec= join->table_reexec;
4291
if (!join->join_tab_reexec)
4293
if (!(join->join_tab_reexec=
4294
(JoinTable*) join->session->alloc(sizeof(JoinTable))))
4297
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4299
tableptr= join->table_reexec;
4300
join_tab= join->join_tab_reexec;
4302
join->join_tab=join_tab;
4303
join->table=tableptr; tableptr[0]=tmp_table;
4305
join->const_tables=0;
4306
join->const_table_map=0;
4307
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4308
join->tmp_table_param.func_count=0;
4309
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4310
join->first_record=join->sort_and_group=0;
4311
join->send_records=(ha_rows) 0;
4313
join->row_limit=join->unit->select_limit_cnt;
4314
join->do_send_rows = (join->row_limit) ? 1 : 0;
4316
join_tab->cache.buff=0; /* No caching */
4317
join_tab->table=tmp_table;
4319
join_tab->select_cond=0;
4321
join_tab->type= AM_ALL; /* Map through all records */
4322
join_tab->keys.set(); /* test everything in quick */
4324
join_tab->on_expr_ref=0;
4325
join_tab->last_inner= 0;
4326
join_tab->first_unmatched= 0;
4327
join_tab->ref.key = -1;
4328
join_tab->not_used_in_distinct=0;
4329
join_tab->read_first_record= join_init_read_record;
4330
join_tab->join=join;
4331
join_tab->ref.key_parts= 0;
4332
memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4333
tmp_table->status=0;
4334
tmp_table->null_row=0;
4339
Fill in outer join related info for the execution plan structure.
4341
For each outer join operation left after simplification of the
4342
original query the function set up the following pointers in the linear
4343
structure join->join_tab representing the selected execution plan.
4344
The first inner table t0 for the operation is set to refer to the last
4345
inner table tk through the field t0->last_inner.
4346
Any inner table ti for the operation are set to refer to the first
4347
inner table ti->first_inner.
4348
The first inner table t0 for the operation is set to refer to the
4349
first inner table of the embedding outer join operation, if there is any,
4350
through the field t0->first_upper.
4351
The on expression for the outer join operation is attached to the
4352
corresponding first inner table through the field t0->on_expr_ref.
4353
Here ti are structures of the JoinTable type.
4355
EXAMPLE. For the query:
4359
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4360
ON (t1.a=t2.a AND t1.b=t3.b)
4364
given the execution plan with the table order t1,t2,t3,t4
4365
is selected, the following references will be set;
4366
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4367
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4368
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4369
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4371
@param join reference to the info fully describing the query
4374
The function assumes that the simplification procedure has been
4375
already applied to the join query (see simplify_joins).
4376
This function can be called only after the execution plan
4379
static void make_outerjoin_info(JOIN *join)
4381
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4383
JoinTable *tab=join->join_tab+i;
4384
Table *table=tab->table;
4385
TableList *tbl= table->pos_in_table_list;
4386
TableList *embedding= tbl->embedding;
4388
if (tbl->outer_join)
4391
Table tab is the only one inner table for outer join.
4392
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4393
is in the query above.)
4395
tab->last_inner= tab->first_inner= tab;
4396
tab->on_expr_ref= &tbl->on_expr;
4397
tab->cond_equal= tbl->cond_equal;
4399
tab->first_upper= embedding->nested_join->first_nested;
4401
for ( ; embedding ; embedding= embedding->embedding)
4403
/* Ignore sj-nests: */
4404
if (!embedding->on_expr)
4406
nested_join_st *nested_join= embedding->nested_join;
4407
if (!nested_join->counter_)
4410
Table tab is the first inner table for nested_join.
4411
Save reference to it in the nested join structure.
4413
nested_join->first_nested= tab;
4414
tab->on_expr_ref= &embedding->on_expr;
4415
tab->cond_equal= tbl->cond_equal;
4416
if (embedding->embedding)
4417
tab->first_upper= embedding->embedding->nested_join->first_nested;
4419
if (!tab->first_inner)
4420
tab->first_inner= nested_join->first_nested;
4421
if (++nested_join->counter_ < nested_join->join_list.elements)
4423
/* Table tab is the last inner table for nested join. */
4424
nested_join->first_nested->last_inner= tab;
4430
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
4432
Session *session= join->session;
4433
optimizer::Position cur_pos;
4436
add_not_null_conds(join);
4437
table_map used_tables;
4438
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4439
{ /* there may be a select without a cond. */
4440
if (join->tables > 1)
4441
cond->update_used_tables(); // Tablenr may have changed
4442
if (join->const_tables == join->tables &&
4443
session->lex->current_select->master_unit() ==
4444
&session->lex->unit) // not upper level SELECT
4445
join->const_table_map|=RAND_TABLE_BIT;
4446
{ // Check const tables
4448
make_cond_for_table(cond,
4449
join->const_table_map,
4451
for (JoinTable *tab= join->join_tab+join->const_tables;
4452
tab < join->join_tab+join->tables ; tab++)
4454
if (*tab->on_expr_ref)
4456
JoinTable *cond_tab= tab->first_inner;
4457
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4458
join->const_table_map,
4462
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4465
tmp->quick_fix_field();
4466
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4467
new Item_cond_and(cond_tab->select_cond,
4469
if (! cond_tab->select_cond)
4471
cond_tab->select_cond->quick_fix_field();
4474
if (const_cond && ! const_cond->val_int())
4476
return 1; // Impossible const condition
4480
used_tables=((select->const_tables=join->const_table_map) |
4481
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4482
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4484
JoinTable *tab=join->join_tab+i;
4486
first_inner is the X in queries like:
4487
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4489
JoinTable *first_inner_tab= tab->first_inner;
4490
table_map current_map= tab->table->map;
4491
bool use_quick_range=0;
4495
Following force including random expression in last table condition.
4496
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4498
if (i == join->tables-1)
4499
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4500
used_tables|=current_map;
4502
if (tab->type == AM_REF && tab->quick &&
4503
(uint32_t) tab->ref.key == tab->quick->index &&
4504
tab->ref.key_length < tab->quick->max_used_key_length)
4506
/* Range uses longer key; Use this instead of ref on key */
4511
tab->ref.key_parts= 0; // Don't use ref key.
4512
cur_pos= join->getPosFromOptimalPlan(i);
4513
cur_pos.setFanout(rows2double(tab->quick->records));
4515
We will use join cache here : prevent sorting of the first
4516
table only and sort at the end.
4518
if (i != join->const_tables && join->tables > join->const_tables + 1)
4524
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4525
if (cond && !tmp && tab->quick)
4527
if (tab->type != AM_ALL)
4530
Don't use the quick method
4531
We come here in the case where we have 'key=constant' and
4532
the test is removed by make_cond_for_table()
4540
Hack to handle the case where we only refer to a table
4541
in the ON part of an OUTER JOIN. In this case we want the code
4542
below to check if we should use 'quick' instead.
4544
tmp= new Item_int((int64_t) 1,1); // Always true
4548
if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4549
tab->type == AM_EQ_REF)
4551
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
4552
session->memdup((unsigned char*) select,
4555
return 1; // End of memory
4557
If tab is an inner table of an outer join operation,
4558
add a match guard to the pushed down predicate.
4559
The guard will turn the predicate on only after
4560
the first match for outer tables is encountered.
4565
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4566
a cond, so neutralize the hack above.
4568
if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4570
tab->select_cond=sel->cond=tmp;
4573
tab->select_cond= sel->cond= NULL;
4575
sel->head=tab->table;
4578
/* Use quick key read if it's a constant and it's not used
4580
if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4581
&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4583
sel->quick=tab->quick; // Use value from get_quick_...
4584
sel->quick_keys.reset();
4585
sel->needed_reg.reset();
4593
uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4594
if (i == join->const_tables && ref_key)
4596
if (tab->const_keys.any() &&
4597
tab->table->reginfo.impossible_range)
4600
else if (tab->type == AM_ALL && ! use_quick_range)
4602
if (tab->const_keys.any() &&
4603
tab->table->reginfo.impossible_range)
4604
return 1; // Impossible range
4606
We plan to scan all rows.
4607
Check again if we should use an index.
4608
We could have used an column from a previous table in
4609
the index if we are using limit and this is the first table
4612
cur_pos= join->getPosFromOptimalPlan(i);
4613
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4614
(! tab->const_keys.none() && (i == join->const_tables) &&
4615
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4617
/* Join with outer join condition */
4618
COND *orig_cond= sel->cond;
4619
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4622
We can't call sel->cond->fix_fields,
4623
as it will break tab->on_expr if it's AND condition
4624
(fix_fields currently removes extra AND/OR levels).
4625
Yet attributes of the just built condition are not needed.
4626
Thus we call sel->cond->quick_fix_field for safety.
4628
if (sel->cond && ! sel->cond->fixed)
4629
sel->cond->quick_fix_field();
4631
if (sel->test_quick_select(session, tab->keys,
4632
used_tables & ~ current_map,
4633
(join->select_options &
4636
join->unit->select_limit_cnt), 0,
4640
Before reporting "Impossible WHERE" for the whole query
4641
we have to check isn't it only "impossible ON" instead
4643
sel->cond=orig_cond;
4644
if (! *tab->on_expr_ref ||
4645
sel->test_quick_select(session, tab->keys,
4646
used_tables & ~ current_map,
4647
(join->select_options &
4650
join->unit->select_limit_cnt),0,
4652
return 1; // Impossible WHERE
4655
sel->cond=orig_cond;
4657
/* Fix for EXPLAIN */
4660
cur_pos= join->getPosFromOptimalPlan(i);
4661
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4666
sel->needed_reg= tab->needed_reg;
4667
sel->quick_keys.reset();
4669
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4670
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4672
tab->keys= sel->quick_keys;
4673
tab->keys|= sel->needed_reg;
4674
tab->use_quick= (!sel->needed_reg.none() &&
4675
(select->quick_keys.none() ||
4677
(select->quick->records >= 100L)))) ?
4679
sel->read_tables= used_tables & ~current_map;
4681
if (i != join->const_tables && tab->use_quick != 2)
4682
{ /* Read with cache */
4684
(tmp=make_cond_for_table(cond,
4685
join->const_table_map |
4689
tab->cache.select= (SQL_SELECT*)
4690
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
4691
tab->cache.select->cond= tmp;
4692
tab->cache.select->read_tables= join->const_table_map;
4699
Push down conditions from all on expressions.
4700
Each of these conditions are guarded by a variable
4701
that turns if off just before null complemented row for
4702
outer joins is formed. Thus, the condition from an
4703
'on expression' are guaranteed not to be checked for
4704
the null complemented row.
4707
/* First push down constant conditions from on expressions */
4708
for (JoinTable *join_tab= join->join_tab+join->const_tables;
4709
join_tab < join->join_tab+join->tables ; join_tab++)
4711
if (*join_tab->on_expr_ref)
4713
JoinTable *cond_tab= join_tab->first_inner;
4714
tmp= make_cond_for_table(*join_tab->on_expr_ref,
4715
join->const_table_map,
4719
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4722
tmp->quick_fix_field();
4723
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4724
new Item_cond_and(cond_tab->select_cond,tmp);
4725
if (! cond_tab->select_cond)
4727
cond_tab->select_cond->quick_fix_field();
4731
/* Push down non-constant conditions from on expressions */
4732
JoinTable *last_tab= tab;
4733
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
4736
Table tab is the last inner table of an outer join.
4737
An on expression is always attached to it.
4739
COND *on_expr= *first_inner_tab->on_expr_ref;
4741
table_map used_tables2= (join->const_table_map |
4742
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4743
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
4745
current_map= tab->table->map;
4746
used_tables2|= current_map;
4747
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
4751
JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
4753
First add the guards for match variables of
4754
all embedding outer join operations.
4756
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
4761
Now add the guard turning the predicate off for
4762
the null complemented row.
4764
tmp_cond= new Item_func_trig_cond(tmp_cond,
4768
tmp_cond->quick_fix_field();
4769
/* Add the predicate to other pushed down predicates */
4770
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
4771
new Item_cond_and(cond_tab->select_cond,
4773
if (! cond_tab->select_cond)
4775
cond_tab->select_cond->quick_fix_field();
4778
first_inner_tab= first_inner_tab->first_upper;
4786
Plan refinement stage: do various set ups for the executioner
4789
make_join_readinfo()
4790
join Join being processed
4791
options Join's options (checking for SELECT_DESCRIBE,
4792
SELECT_NO_JOIN_CACHE)
4793
no_jbuf_after Don't use join buffering after table with this number.
4796
Plan refinement stage: do various set ups for the executioner
4797
- set up use of join buffering
4798
- push index conditions
4799
- increment counters
4804
true - Out of memory
4806
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
4809
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
4812
for (i=join->const_tables ; i < join->tables ; i++)
4814
JoinTable *tab=join->join_tab+i;
4815
Table *table=tab->table;
4816
bool using_join_cache;
4817
tab->read_record.table= table;
4818
tab->read_record.file=table->file;
4819
tab->next_select=sub_select; /* normal select */
4821
TODO: don't always instruct first table's ref/range access method to
4822
produce sorted output.
4824
tab->sorted= sorted;
4825
sorted= 0; // only first must be sorted
4826
if (tab->insideout_match_tab)
4828
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
4833
switch (tab->type) {
4834
case AM_SYSTEM: // Only happens with left join
4835
table->status=STATUS_NO_RECORD;
4836
tab->read_first_record= join_read_system;
4837
tab->read_record.read_record= join_no_more_records;
4839
case AM_CONST: // Only happens with left join
4840
table->status=STATUS_NO_RECORD;
4841
tab->read_first_record= join_read_const;
4842
tab->read_record.read_record= join_no_more_records;
4843
if (table->covering_keys.test(tab->ref.key) &&
4847
table->file->extra(HA_EXTRA_KEYREAD);
4851
table->status=STATUS_NO_RECORD;
4854
delete tab->select->quick;
4855
tab->select->quick=0;
4859
tab->read_first_record= join_read_key;
4860
tab->read_record.read_record= join_no_more_records;
4861
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4864
table->file->extra(HA_EXTRA_KEYREAD);
4867
case AM_REF_OR_NULL:
4869
table->status=STATUS_NO_RECORD;
4872
delete tab->select->quick;
4873
tab->select->quick=0;
4877
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4880
table->file->extra(HA_EXTRA_KEYREAD);
4882
if (tab->type == AM_REF)
4884
tab->read_first_record= join_read_always_key;
4885
tab->read_record.read_record= tab->insideout_match_tab?
4886
join_read_next_same_diff : join_read_next_same;
4890
tab->read_first_record= join_read_always_key_or_null;
4891
tab->read_record.read_record= join_read_next_same_or_null;
4896
If previous table use cache
4897
If the incoming data set is already sorted don't use cache.
4899
table->status=STATUS_NO_RECORD;
4900
using_join_cache= false;
4901
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
4902
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
4903
!tab->insideout_match_tab)
4905
if ((options & SELECT_DESCRIBE) ||
4906
!join_init_cache(join->session,join->join_tab+join->const_tables,
4907
i-join->const_tables))
4909
using_join_cache= true;
4910
tab[-1].next_select=sub_select_cache; /* Patch previous */
4913
/* These init changes read_record */
4914
if (tab->use_quick == 2)
4916
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
4917
tab->read_first_record= join_init_quick_read_record;
4919
status_var_increment(join->session->status_var.select_range_check_count);
4923
tab->read_first_record= join_init_read_record;
4924
if (i == join->const_tables)
4926
if (tab->select && tab->select->quick)
4929
status_var_increment(join->session->status_var.select_range_count);
4933
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
4935
status_var_increment(join->session->status_var.select_scan_count);
4940
if (tab->select && tab->select->quick)
4943
status_var_increment(join->session->status_var.select_full_range_join_count);
4947
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
4949
status_var_increment(join->session->status_var.select_full_join_count);
4952
if (!table->no_keyread)
4954
if (tab->select && tab->select->quick &&
4955
tab->select->quick->index != MAX_KEY && //not index_merge
4956
table->covering_keys.test(tab->select->quick->index))
4959
table->file->extra(HA_EXTRA_KEYREAD);
4961
else if (!table->covering_keys.none() &&
4962
!(tab->select && tab->select->quick))
4963
{ // Only read index tree
4964
if (!tab->insideout_match_tab)
4967
See bug #26447: "Using the clustered index for a table scan
4968
is always faster than using a secondary index".
4970
if (table->s->primary_key != MAX_KEY &&
4971
table->file->primary_key_is_clustered())
4972
tab->index= table->s->primary_key;
4974
tab->index= table->find_shortest_key(&table->covering_keys);
4976
tab->read_first_record= join_read_first;
4977
tab->type= AM_NEXT; // Read with index_first / index_next
4989
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
4993
/** Update the dependency map for the tables. */
4994
static void update_depend_map(JOIN *join)
4996
JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
4998
for (; join_tab != end ; join_tab++)
5000
table_reference_st *ref= &join_tab->ref;
5001
table_map depend_map= 0;
5002
Item **item=ref->items;
5004
for (i=0 ; i < ref->key_parts ; i++,item++)
5005
depend_map|=(*item)->used_tables();
5006
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
5007
depend_map&= ~OUTER_REF_TABLE_BIT;
5008
for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5011
ref->depend_map|=(*tab)->ref.depend_map;
5016
/** Update the dependency map for the sort order. */
5017
static void update_depend_map(JOIN *join, order_st *order)
5019
for (; order ; order=order->next)
5021
table_map depend_map;
5022
order->item[0]->update_used_tables();
5023
order->depend_map=depend_map=order->item[0]->used_tables();
5024
// Not item_sum(), RAND() and no reference to table outside of sub select
5025
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5026
&& !order->item[0]->with_sum_func)
5028
for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5031
order->depend_map|=(*tab)->ref.depend_map;
5038
Remove all constants and check if order_st only contains simple
5041
simple_order is set to 1 if sort_order only uses fields from head table
5042
and the head table is not a LEFT JOIN table.
5044
@param join Join handler
5045
@param first_order List of SORT or GROUP order
5046
@param cond WHERE statement
5047
@param change_list Set to 1 if we should remove things from list.
5048
If this is not set, then only simple_order is
5050
@param simple_order Set to 1 if we are only using simple expressions
5053
Returns new sort order
5055
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5057
if (join->tables == join->const_tables)
5058
return change_list ? 0 : first_order; // No need to sort
5060
order_st *order,**prev_ptr;
5061
table_map first_table= join->join_tab[join->const_tables].table->map;
5062
table_map not_const_tables= ~join->const_table_map;
5065
prev_ptr= &first_order;
5066
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5068
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5070
update_depend_map(join, first_order);
5071
for (order=first_order; order ; order=order->next)
5073
table_map order_tables=order->item[0]->used_tables();
5074
if (order->item[0]->with_sum_func)
5075
*simple_order=0; // Must do a temp table to sort
5076
else if (!(order_tables & not_const_tables))
5078
if (order->item[0]->with_subselect)
5079
order->item[0]->val_str(&order->item[0]->str_value);
5080
continue; // skip const item
5084
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5089
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5093
if ((ref=order_tables & (not_const_tables ^ first_table)))
5095
if (!(order_tables & first_table) &&
5096
only_eq_ref_tables(join,first_order, ref))
5100
*simple_order=0; // Must do a temp table to sort
5105
*prev_ptr= order; // use this entry
5106
prev_ptr= &order->next;
5110
if (prev_ptr == &first_order) // Nothing to sort/group
5112
return(first_order);
5115
static int return_zero_rows(JOIN *join,
5116
select_result *result,
5120
uint64_t select_options,
5124
if (select_options & SELECT_DESCRIBE)
5126
select_describe(join, false, false, false, info);
5134
for (TableList *table= tables; table; table= table->next_leaf)
5135
table->table->mark_as_null_row(); // All fields are NULL
5136
if (having && having->val_int() == 0)
5139
if (! (result->send_fields(fields)))
5143
List_iterator_fast<Item> it(fields);
5145
while ((item= it++))
5146
item->no_rows_in_result();
5147
result->send_data(fields);
5149
result->send_eof(); // Should be safe
5151
/* Update results for FOUND_ROWS */
5152
join->session->limit_found_rows= join->session->examined_row_count= 0;
5157
Simplify joins replacing outer joins by inner joins whenever it's
5160
The function, during a retrieval of join_list, eliminates those
5161
outer joins that can be converted into inner join, possibly nested.
5162
It also moves the on expressions for the converted outer joins
5163
and from inner joins to conds.
5164
The function also calculates some attributes for nested joins:
5168
- on_expr_dep_tables
5169
The first two attributes are used to test whether an outer join can
5170
be substituted for an inner join. The third attribute represents the
5171
relation 'to be dependent on' for tables. If table t2 is dependent
5172
on table t1, then in any evaluated execution plan table access to
5173
table t2 must precede access to table t2. This relation is used also
5174
to check whether the query contains invalid cross-references.
5175
The forth attribute is an auxiliary one and is used to calculate
5177
As the attribute dep_tables qualifies possibles orders of tables in the
5178
execution plan, the dependencies required by the straight join
5179
modifiers are reflected in this attribute as well.
5180
The function also removes all braces that can be removed from the join
5181
expression without changing its meaning.
5184
An outer join can be replaced by an inner join if the where condition
5185
or the on expression for an embedding nested join contains a conjunctive
5186
predicate rejecting null values for some attribute of the inner tables.
5190
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5192
the predicate t2.b < 5 rejects nulls.
5193
The query is converted first to:
5195
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5197
then to the equivalent form:
5199
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5203
Similarly the following query:
5205
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5210
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5214
One conversion might trigger another:
5216
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5217
LEFT JOIN t3 ON t3.b=t2.b
5218
WHERE t3 IS NOT NULL =>
5219
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5220
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5221
SELECT * FROM t1, t2, t3
5222
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5225
The function removes all unnecessary braces from the expression
5226
produced by the conversions.
5229
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5231
finally is converted to:
5233
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5238
It also will remove braces from the following queries:
5240
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5241
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5244
The benefit of this simplification procedure is that it might return
5245
a query for which the optimizer can evaluate execution plan with more
5246
join orders. With a left join operation the optimizer does not
5247
consider any plan where one of the inner tables is before some of outer
5251
The function is implemented by a recursive procedure. On the recursive
5252
ascent all attributes are calculated, all outer joins that can be
5253
converted are replaced and then all unnecessary braces are removed.
5254
As join list contains join tables in the reverse order sequential
5255
elimination of outer joins does not require extra recursive calls.
5258
Remove all semi-joins that have are within another semi-join (i.e. have
5259
an "ancestor" semi-join nest)
5262
Here is an example of a join query with invalid cross references:
5264
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5267
@param join reference to the query info
5268
@param join_list list representation of the join to be converted
5269
@param conds conditions to add on expressions for converted joins
5270
@param top true <=> conds is the where condition
5273
- The new condition, if success
5276
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5279
nested_join_st *nested_join;
5280
TableList *prev_table= 0;
5281
List_iterator<TableList> li(*join_list);
5284
Try to simplify join operations from join_list.
5285
The most outer join operation is checked for conversion first.
5287
while ((table= li++))
5289
table_map used_tables;
5290
table_map not_null_tables= (table_map) 0;
5292
if ((nested_join= table->nested_join))
5295
If the element of join_list is a nested join apply
5296
the procedure to its nested join list first.
5300
Item *expr= table->on_expr;
5302
If an on expression E is attached to the table,
5303
check all null rejected predicates in this expression.
5304
If such a predicate over an attribute belonging to
5305
an inner table of an embedded outer join is found,
5306
the outer join is converted to an inner join and
5307
the corresponding on expression is added to E.
5309
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5311
if (!table->prep_on_expr || expr != table->on_expr)
5315
table->on_expr= expr;
5316
table->prep_on_expr= expr->copy_andor_structure(join->session);
5319
nested_join->used_tables= (table_map) 0;
5320
nested_join->not_null_tables=(table_map) 0;
5321
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5322
used_tables= nested_join->used_tables;
5323
not_null_tables= nested_join->not_null_tables;
5327
if (!table->prep_on_expr)
5328
table->prep_on_expr= table->on_expr;
5329
used_tables= table->table->map;
5331
not_null_tables= conds->not_null_tables();
5334
if (table->embedding)
5336
table->embedding->nested_join->used_tables|= used_tables;
5337
table->embedding->nested_join->not_null_tables|= not_null_tables;
5340
if (!table->outer_join || (used_tables & not_null_tables))
5343
For some of the inner tables there are conjunctive predicates
5344
that reject nulls => the outer join can be replaced by an inner join.
5346
table->outer_join= 0;
5349
/* Add ON expression to the WHERE or upper-level ON condition. */
5352
conds= and_conds(conds, table->on_expr);
5353
conds->top_level_item();
5354
/* conds is always a new item as both cond and on_expr existed */
5355
assert(!conds->fixed);
5356
conds->fix_fields(join->session, &conds);
5359
conds= table->on_expr;
5360
table->prep_on_expr= table->on_expr= 0;
5368
Only inner tables of non-convertible outer joins
5369
remain with on_expr.
5373
table->dep_tables|= table->on_expr->used_tables();
5374
if (table->embedding)
5376
table->dep_tables&= ~table->embedding->nested_join->used_tables;
5378
Embedding table depends on tables used
5379
in embedded on expressions.
5381
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5384
table->dep_tables&= ~table->table->map;
5389
/* The order of tables is reverse: prev_table follows table */
5390
if (prev_table->straight)
5391
prev_table->dep_tables|= used_tables;
5392
if (prev_table->on_expr)
5394
prev_table->dep_tables|= table->on_expr_dep_tables;
5395
table_map prev_used_tables= prev_table->nested_join ?
5396
prev_table->nested_join->used_tables :
5397
prev_table->table->map;
5399
If on expression contains only references to inner tables
5400
we still make the inner tables dependent on the outer tables.
5401
It would be enough to set dependency only on one outer table
5402
for them. Yet this is really a rare case.
5404
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5405
prev_table->dep_tables|= used_tables;
5412
Flatten nested joins that can be flattened.
5413
no ON expression and not a semi-join => can be flattened.
5416
while ((table= li++))
5418
nested_join= table->nested_join;
5419
if (nested_join && !table->on_expr)
5422
List_iterator<TableList> it(nested_join->join_list);
5425
tbl->embedding= table->embedding;
5426
tbl->join_list= table->join_list;
5428
li.replace(nested_join->join_list);
5434
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5437
uint32_t reclength,offset;
5438
uint32_t field_count;
5439
Session *session= join->session;
5441
entry->reginfo.lock_type=TL_WRITE;
5443
/* Calculate how many saved fields there is in list */
5445
List_iterator<Item> it(fields);
5449
if (item->get_tmp_table_field() && ! item->const_item())
5453
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5454
{ // only const items with no OPTION_FOUND_ROWS
5455
join->unit->select_limit_cnt= 1; // Only send first row
5458
Field **first_field=entry->field+entry->s->fields - field_count;
5459
offset= (field_count ?
5460
entry->field[entry->s->fields - field_count]->
5461
offset(entry->record[0]) : 0);
5462
reclength= entry->s->reclength-offset;
5464
entry->free_io_cache(); // Safety
5465
entry->file->info(HA_STATUS_VARIABLE);
5466
if (entry->s->db_type() == heap_engine ||
5467
(!entry->s->blob_fields &&
5468
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->file->stats.records <
5469
session->variables.sortbuff_size)))
5470
error= remove_dup_with_hash_index(join->session, entry,
5471
field_count, first_field,
5474
error= remove_dup_with_compare(join->session, entry, first_field, offset,
5477
free_blobs(first_field);
5482
Function to setup clauses without sum functions.
5484
static int setup_without_group(Session *session,
5485
Item **ref_pointer_array,
5489
List<Item> &all_fields,
5493
bool *hidden_group_fields)
5496
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
5498
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5499
res= session->setup_conds(tables, conds);
5501
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
5502
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5504
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5505
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5506
group, hidden_group_fields);
5507
session->lex->allow_sum_func= save_allow_sum_func;
5512
Calculate the best possible join and initialize the join structure.
5519
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5524
uint32_t table_count;
5525
uint32_t const_count;
5527
table_map found_const_table_map;
5528
table_map all_table_map;
5529
table_map found_ref;
5533
Table **table_vector= NULL;
5534
JoinTable *stat= NULL;
5535
JoinTable *stat_end= NULL;
5537
JoinTable **stat_ref= NULL;
5538
optimizer::KeyUse *keyuse= NULL;
5539
optimizer::KeyUse *start_keyuse= NULL;
5540
table_map outer_join= 0;
5541
vector<optimizer::SargableParam> sargables;
5542
JoinTable *stat_vector[MAX_TABLES+1];
5543
optimizer::Position *partial_pos;
5545
table_count= join->tables;
5546
stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5547
stat_ref= (JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);
5548
table_vector= (Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5549
if (! stat || ! stat_ref || ! table_vector)
5552
join->best_ref=stat_vector;
5554
stat_end=stat+table_count;
5555
found_const_table_map= all_table_map=0;
5560
s++, tables= tables->next_leaf, i++)
5562
TableList *embedding= tables->embedding;
5565
s->const_keys.reset();
5566
s->checked_keys.reset();
5567
s->needed_reg.reset();
5568
table_vector[i]=s->table=table=tables->table;
5569
table->pos_in_table_list= tables;
5570
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5573
table->file->print_error(error, MYF(0));
5576
table->quick_keys.reset();
5577
table->reginfo.join_tab=s;
5578
table->reginfo.not_exists_optimize=0;
5579
memset(table->const_key_parts, 0,
5580
sizeof(key_part_map)*table->s->keys);
5581
all_table_map|= table->map;
5583
s->info=0; // For describe
5585
s->dependent= tables->dep_tables;
5586
s->key_dependent= 0;
5587
if (tables->schema_table)
5588
table->file->stats.records= 2;
5589
table->quick_condition_rows= table->file->stats.records;
5591
s->on_expr_ref= &tables->on_expr;
5592
if (*s->on_expr_ref)
5594
/* s is the only inner table of an outer join */
5595
if (!table->file->stats.records && !embedding)
5597
s->dependent= 0; // Ignore LEFT JOIN depend.
5598
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5601
outer_join|= table->map;
5602
s->embedding_map.reset();
5603
for (;embedding; embedding= embedding->embedding)
5604
s->embedding_map|= embedding->nested_join->nj_map;
5607
if (embedding && !(false && ! embedding->embedding))
5609
/* s belongs to a nested join, maybe to several embedded joins */
5610
s->embedding_map.reset();
5613
nested_join_st *nested_join= embedding->nested_join;
5614
s->embedding_map|= nested_join->nj_map;
5615
s->dependent|= embedding->dep_tables;
5616
embedding= embedding->embedding;
5617
outer_join|= nested_join->used_tables;
5622
if ((table->file->stats.records <= 1) && !s->dependent &&
5623
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
5624
!join->no_const_tables)
5626
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5630
join->outer_join=outer_join;
5632
if (join->outer_join)
5635
Build transitive closure for relation 'to be dependent on'.
5636
This will speed up the plan search for many cases with outer joins,
5637
as well as allow us to catch illegal cross references/
5638
Warshall's algorithm is used to build the transitive closure.
5639
As we use bitmaps to represent the relation the complexity
5640
of the algorithm is O((number of tables)^2).
5642
for (i= 0, s= stat ; i < table_count ; i++, s++)
5644
for (uint32_t j= 0 ; j < table_count ; j++)
5646
table= stat[j].table;
5647
if (s->dependent & table->map)
5648
s->dependent |= table->reginfo.join_tab->dependent;
5651
s->table->maybe_null= 1;
5653
/* Catch illegal cross references for outer joins */
5654
for (i= 0, s= stat ; i < table_count ; i++, s++)
5656
if (s->dependent & s->table->map)
5658
join->tables=0; // Don't use join->table
5659
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5662
s->key_dependent= s->dependent;
5666
if (conds || outer_join)
5667
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5668
conds, join->cond_equal,
5669
~outer_join, join->select_lex, sargables))
5672
/* Read tables with 0 or 1 rows (system tables) */
5673
join->const_table_map= 0;
5675
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5676
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5677
while (p_pos < p_end)
5680
s= p_pos->getJoinTable();
5682
join->const_table_map|=s->table->map;
5683
if ((tmp= join_read_const_table(s, p_pos)))
5686
return 1; // Fatal error
5689
found_const_table_map|= s->table->map;
5693
/* loop until no more const tables are found */
5697
more_const_tables_found:
5702
We only have to loop from stat_vector + const_count as
5703
set_position() will move all const_tables first in stat_vector
5706
for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
5711
If equi-join condition by a key is null rejecting and after a
5712
substitution of a const table the key value happens to be null
5713
then we can state that there are no matches for this equi-join.
5715
if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5718
When performing an outer join operation if there are no matching rows
5719
for the single row of the outer table all the inner tables are to be
5720
null complemented and thus considered as constant tables.
5721
Here we apply this consideration to the case of outer join operations
5722
with a single inner table only because the case with nested tables
5723
would require a more thorough analysis.
5724
TODO. Apply single row substitution to null complemented inner tables
5725
for nested outer join operations.
5727
while (keyuse->getTable() == table)
5729
if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5730
keyuse->getVal()->is_null() && keyuse->isNullRejected())
5733
table->mark_as_null_row();
5734
found_const_table_map|= table->map;
5735
join->const_table_map|= table->map;
5736
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5737
goto more_const_tables_found;
5743
if (s->dependent) // If dependent on some table
5745
// All dep. must be constants
5746
if (s->dependent & ~(found_const_table_map))
5748
if (table->file->stats.records <= 1L &&
5749
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
5750
!table->pos_in_table_list->embedding)
5754
join->const_table_map|=table->map;
5755
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5756
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5757
if ((tmp= join_read_const_table(s, partial_pos)))
5760
return 1; // Fatal error
5763
found_const_table_map|= table->map;
5767
/* check if table can be read by key or table only uses const refs */
5768
if ((keyuse=s->keyuse))
5771
while (keyuse->getTable() == table)
5773
start_keyuse= keyuse;
5774
key= keyuse->getKey();
5775
s->keys.set(key); // QQ: remove this ?
5782
if (keyuse->getVal()->type() != Item::NULL_ITEM &&
5783
! keyuse->getOptimizeFlags())
5785
if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5786
const_ref.set(keyuse->getKeypart());
5788
refs|= keyuse->getUsedTables();
5789
eq_part.set(keyuse->getKeypart());
5792
} while (keyuse->getTable() == table && keyuse->getKey() == key);
5794
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5795
! table->pos_in_table_list->embedding)
5797
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5799
if (const_ref == eq_part)
5800
{ // Found everything for ref.
5804
join->const_table_map|= table->map;
5805
set_position(join, const_count++, s, start_keyuse);
5806
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5808
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5809
if ((tmp=join_read_const_table(s, partial_pos)))
5812
return 1; // Fatal error
5815
found_const_table_map|= table->map;
5819
found_ref|= refs; // Table is const if all refs are const
5821
else if (const_ref == eq_part)
5822
s->const_keys.set(key);
5827
} while (join->const_table_map & found_ref && ref_changed);
5830
Update info on indexes that can be used for search lookups as
5831
reading const tables may has added new sargable predicates.
5833
if (const_count && ! sargables.empty())
5835
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
5836
while (iter != sargables.end())
5838
Field *field= (*iter).getField();
5839
JoinTable *join_tab= field->table->reginfo.join_tab;
5840
key_map possible_keys= field->key_start;
5841
possible_keys&= field->table->keys_in_use_for_query;
5842
bool is_const= true;
5843
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5844
is_const&= (*iter).isConstItem(j);
5846
join_tab[0].const_keys|= possible_keys;
5851
/* Calc how many (possible) matched records in each table */
5853
for (s=stat ; s < stat_end ; s++)
5855
if (s->type == AM_SYSTEM || s->type == AM_CONST)
5857
/* Only one matching row */
5858
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
5861
/* Approximate found rows and time to read them */
5862
s->found_records=s->records=s->table->file->stats.records;
5863
s->read_time=(ha_rows) s->table->file->scan_time();
5866
Set a max range of how many seeks we can expect when using keys
5867
This is can't be to high as otherwise we are likely to use
5870
s->worst_seeks= min((double) s->found_records / 10,
5871
(double) s->read_time*3);
5872
if (s->worst_seeks < 2.0) // Fix for small tables
5876
Add to stat->const_keys those indexes for which all group fields or
5877
all select distinct fields participate in one index.
5879
add_group_and_distinct_keys(join, s);
5881
if (s->const_keys.any() &&
5882
!s->table->pos_in_table_list->embedding)
5886
select= make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
5889
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
5890
s->quick=select->quick;
5891
s->needed_reg=select->needed_reg;
5893
if (records == 0 && s->table->reginfo.impossible_range)
5896
Impossible WHERE or ON expression
5897
In case of ON, we mark that the we match one empty NULL row.
5898
In case of WHERE, don't set found_const_table_map to get the
5899
caller to abort with a zero row result.
5901
join->const_table_map|= s->table->map;
5902
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5904
if (*s->on_expr_ref)
5906
/* Generate empty row */
5907
s->info= "Impossible ON condition";
5908
found_const_table_map|= s->table->map;
5910
s->table->mark_as_null_row(); // All fields are NULL
5913
if (records != HA_POS_ERROR)
5915
s->found_records=records;
5916
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
5922
join->join_tab=stat;
5923
join->map2table=stat_ref;
5924
join->table= join->all_tables=table_vector;
5925
join->const_tables=const_count;
5926
join->found_const_table_map=found_const_table_map;
5928
/* Find an optimal join order of the non-constant tables. */
5929
if (join->const_tables != join->tables)
5931
optimize_keyuse(join, keyuse_array);
5932
if (choose_plan(join, all_table_map & ~join->const_table_map))
5937
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
5938
join->best_read= 1.0;
5940
/* Generate an execution plan from the found optimal join order. */
5941
return (join->session->killed || get_best_combination(join));
5945
Assign each nested join structure a bit in the nested join bitset.
5947
Assign each nested join structure (except "confluent" ones - those that
5948
embed only one element) a bit in the nested join bitset.
5950
@param join Join being processed
5951
@param join_list List of tables
5952
@param first_unused Number of first unused bit in the nest joing bitset before the
5956
This function is called after simplify_joins(), when there are no
5957
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
5958
we will not run out of bits in the nested join bitset.
5961
First unused bit in the nest join bitset after the call.
5963
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
5965
List_iterator<TableList> li(*join_list);
5967
while ((table= li++))
5969
nested_join_st *nested_join;
5970
if ((nested_join= table->nested_join))
5973
It is guaranteed by simplify_joins() function that a nested join
5974
that has only one child is either
5975
- a single-table view (the child is the underlying table), or
5976
- a single-table semi-join nest
5978
We don't assign bits to such sj-nests because
5979
1. it is redundant (a "sequence" of one table cannot be interleaved
5981
2. we could run out of bits in the nested join bitset otherwise.
5983
if (nested_join->join_list.elements != 1)
5985
/* Don't assign bits to sj-nests */
5987
nested_join->nj_map.set(first_unused++);
5988
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
5993
return(first_unused);
5998
Return table number if there is only one table in sort order
5999
and group and order is compatible, else return 0.
6001
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
6003
table_map map= (table_map) 0;
6006
a= b; // Only one need to be given
6010
for (; a && b; a=a->next,b=b->next)
6012
if (!(*a->item)->eq(*b->item,1))
6013
return (Table *) NULL;
6014
map|= a->item[0]->used_tables();
6016
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
6017
return (Table *) NULL;
6019
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6020
if (map != tables->table->map)
6021
return (Table *) NULL; // More than one table
6022
return tables->table;
6026
Set nested_join_st::counter=0 in all nested joins in passed list.
6028
Recursively set nested_join_st::counter=0 for all nested joins contained in
6029
the passed join_list.
6031
@param join_list List of nested joins to process. It may also contain base
6032
tables which will be ignored.
6034
static void reset_nj_counters(List<TableList> *join_list)
6036
List_iterator<TableList> li(*join_list);
6038
while ((table= li++))
6040
nested_join_st *nested_join;
6041
if ((nested_join= table->nested_join))
6043
nested_join->counter_= 0;
6044
reset_nj_counters(&nested_join->join_list);
6051
Return 1 if second is a subpart of first argument.
6053
If first parts has different direction, change it to second part
6054
(group is sorted like order)
6056
static bool test_if_subpart(order_st *a,order_st *b)
6058
for (; a && b; a=a->next,b=b->next)
6060
if ((*a->item)->eq(*b->item,1))
6069
Nested joins perspective: Remove the last table from the join order.
6071
Remove the last table from the partial join order and update the nested
6072
joins counters and join->cur_embedding_map. It is ok to call this
6073
function for the first table in join order (for which
6074
check_interleaving_with_nj has not been called)
6076
@param last join table to remove, it is assumed to be the last in current
6079
static void restore_prev_nj_state(JoinTable *last)
6081
TableList *last_emb= last->table->pos_in_table_list->embedding;
6082
JOIN *join= last->join;
6085
if (last_emb->on_expr)
6087
if (!(--last_emb->nested_join->counter_))
6088
join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
6089
else if (last_emb->nested_join->join_list.elements-1 ==
6090
last_emb->nested_join->counter_)
6091
join->cur_embedding_map|= last_emb->nested_join->nj_map;
6095
last_emb= last_emb->embedding;
6100
Determine if the set is already ordered for order_st BY, so it can
6101
disable join cache because it will change the ordering of the results.
6102
Code handles sort table that is at any location (not only first after
6103
the const tables) despite the fact that it's currently prohibited.
6104
We must disable join cache if the first non-const table alone is
6105
ordered. If there is a temp table the ordering is done as a last
6106
operation and doesn't prevent join cache usage.
6108
static uint32_t make_join_orderinfo(JOIN *join)
6112
return join->tables;
6114
for (i=join->const_tables ; i < join->tables ; i++)
6116
JoinTable *tab= join->join_tab+i;
6117
Table *table= tab->table;
6118
if ((table == join->sort_by_table &&
6119
(!join->order || join->skip_sort_order)) ||
6120
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
6129
Create a condition for a const reference and add this to the
6130
currenct select for the table.
6132
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6134
if (!join_tab->ref.key_parts)
6137
Item_cond_and *cond=new Item_cond_and();
6138
Table *table=join_tab->table;
6143
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6145
Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
6147
Item *value=join_tab->ref.items[i];
6148
cond->add(new Item_func_equal(new Item_field(field), value));
6150
if (session->is_fatal_error)
6154
cond->fix_fields(session, (Item**)&cond);
6155
if (join_tab->select)
6157
error=(int) cond->add(join_tab->select->cond);
6158
join_tab->select_cond=join_tab->select->cond=cond;
6160
else if ((join_tab->select= make_select(join_tab->table, 0, 0, cond, 0,
6162
join_tab->select_cond=cond;
6164
return(error ? true : false);
6167
static void free_blobs(Field **ptr)
6169
for (; *ptr ; ptr++)
6171
if ((*ptr)->flags & BLOB_FLAG)
6172
((Field_blob *) (*ptr))->free();
6177
@} (end of group Query_Optimizer)
added
removed
drizzled/join.cc
