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
35
#include "drizzled/item/cache.h"
36
#include "drizzled/item/cmpfunc.h"
37
#include "drizzled/item/copy_string.h"
38
#include "drizzled/item/uint.h"
39
#include "drizzled/cached_item.h"
40
#include "drizzled/sql_base.h"
41
#include "drizzled/sql_select.h" /* include join.h */
42
#include "drizzled/lock.h"
43
#include "drizzled/nested_join.h"
44
#include "drizzled/join.h"
45
#include "drizzled/join_cache.h"
46
#include "drizzled/show.h"
47
#include "drizzled/field/blob.h"
48
#include "drizzled/optimizer/position.h"
49
#include "drizzled/optimizer/sargable_param.h"
50
#include "drizzled/optimizer/key_use.h"
51
#include "drizzled/optimizer/range.h"
52
#include "drizzled/optimizer/sum.h"
53
#include "drizzled/optimizer/explain_plan.h"
54
#include "drizzled/records.h"
55
#include "drizzled/probes.h"
56
#include "mysys/my_bit.h"
61
using namespace drizzled;
63
extern drizzled::plugin::StorageEngine *heap_engine;
64
extern std::bitset<12> test_flags;
66
/** Declarations of static functions used in this source file. */
67
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
68
static void calc_group_buffer(JOIN *join,order_st *group);
69
static bool alloc_group_fields(JOIN *join,order_st *group);
70
static uint32_t cache_record_length(JOIN *join, uint32_t index);
71
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
72
static bool get_best_combination(JOIN *join);
73
static void set_position(JOIN *join,
76
optimizer::KeyUse *key);
77
static bool choose_plan(JOIN *join,table_map join_tables);
78
static void best_access_path(JOIN *join, JoinTable *s,
80
table_map remaining_tables,
84
static void optimize_straight_join(JOIN *join, table_map join_tables);
85
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
86
static bool best_extension_by_limited_search(JOIN *join,
87
table_map remaining_tables,
92
uint32_t prune_level);
93
static uint32_t determine_search_depth(JOIN* join);
94
static bool make_simple_join(JOIN *join,Table *tmp_table);
95
static void make_outerjoin_info(JOIN *join);
96
static bool make_join_select(JOIN *join, optimizer::SqlSelect *select,COND *item);
97
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
98
static void update_depend_map(JOIN *join);
99
static void update_depend_map(JOIN *join, order_st *order);
100
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
101
static int return_zero_rows(JOIN *join,
106
uint64_t select_options,
109
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
110
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
111
static int setup_without_group(Session *session,
112
Item **ref_pointer_array,
116
List<Item> &all_fields,
120
bool *hidden_group_fields);
121
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
122
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
123
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
124
static void reset_nj_counters(List<TableList> *join_list);
125
static bool test_if_subpart(order_st *a,order_st *b);
126
static void restore_prev_nj_state(JoinTable *last);
127
static uint32_t make_join_orderinfo(JOIN *join);
128
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
129
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
132
Prepare of whole select (including sub queries in future).
135
Add check of calculation of GROUP functions and fields:
136
SELECT COUNT(*)+table.col1 from table1;
143
int JOIN::prepare(Item ***rref_pointer_array,
144
TableList *tables_init,
148
order_st *order_init,
149
order_st *group_init,
151
Select_Lex *select_lex_arg,
152
Select_Lex_Unit *unit_arg)
154
// to prevent double initialization on EXPLAIN
160
group_list= group_init;
162
tables_list= tables_init;
163
select_lex= select_lex_arg;
164
select_lex->join= this;
165
join_list= &select_lex->top_join_list;
166
union_part= unit_arg->is_union();
168
session->lex->current_select->is_item_list_lookup= 1;
170
If we have already executed SELECT, then it have not sense to prevent
171
its table from update (see unique_table())
173
if (session->derived_tables_processing)
174
select_lex->exclude_from_table_unique_test= true;
176
/* Check that all tables, fields, conds and order are ok */
178
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
179
setup_tables_and_check_access(session, &select_lex->context, join_list,
180
tables_list, &select_lex->leaf_tables,
184
TableList *table_ptr;
185
for (table_ptr= select_lex->leaf_tables;
187
table_ptr= table_ptr->next_leaf)
190
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
191
select_lex->setup_ref_array(session, og_num) ||
192
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
194
setup_without_group(session, (*rref_pointer_array), tables_list,
195
select_lex->leaf_tables, fields_list,
196
all_fields, &conds, order, group_list,
197
&hidden_group_fields))
200
ref_pointer_array= *rref_pointer_array;
204
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
205
session->where="having clause";
206
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
207
select_lex->having_fix_field= 1;
208
bool having_fix_rc= (!having->fixed &&
209
(having->fix_fields(session, &having) ||
210
having->check_cols(1)));
211
select_lex->having_fix_field= 0;
212
if (having_fix_rc || session->is_error())
214
session->lex->allow_sum_func= save_allow_sum_func;
218
Item_subselect *subselect;
219
Item_in_subselect *in_subs= NULL;
221
Are we in a subquery predicate?
222
TODO: the block below will be executed for every PS execution without need.
224
if ((subselect= select_lex->master_unit()->item))
226
if (subselect->substype() == Item_subselect::IN_SUBS)
227
in_subs= (Item_in_subselect*)subselect;
230
bool do_materialize= !test(session->variables.optimizer_switch &
231
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
233
Check if the subquery predicate can be executed via materialization.
234
The required conditions are:
235
1. Subquery predicate is an IN/=ANY subq predicate
236
2. Subquery is a single SELECT (not a UNION)
237
3. Subquery is not a table-less query. In this case there is no
238
point in materializing.
239
4. Subquery predicate is a top-level predicate
240
(this implies it is not negated)
241
TODO: this is a limitation that should be lifeted once we
242
implement correct NULL semantics (WL#3830)
243
5. Subquery is non-correlated
245
This is an overly restrictive condition. It can be extended to:
246
(Subquery is non-correlated ||
247
Subquery is correlated to any query outer to IN predicate ||
248
(Subquery is correlated to the immediate outer query &&
249
Subquery !contains {GROUP BY, order_st BY [LIMIT],
250
aggregate functions) && subquery predicate is not under "NOT IN"))
251
6. No execution method was already chosen (by a prepared statement).
253
(*) The subquery must be part of a SELECT statement. The current
254
condition also excludes multi-table update statements.
256
We have to determine whether we will perform subquery materialization
257
before calling the IN=>EXISTS transformation, so that we know whether to
258
perform the whole transformation or only that part of it which wraps
259
Item_in_subselect in an Item_in_optimizer.
261
if (do_materialize &&
263
!select_lex->master_unit()->first_select()->next_select() && // 2
264
select_lex->master_unit()->first_select()->leaf_tables && // 3
265
session->lex->sql_command == SQLCOM_SELECT) // *
267
if (in_subs->is_top_level_item() && // 4
268
!in_subs->is_correlated && // 5
269
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
270
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
273
Item_subselect::trans_res trans_res;
274
if ((trans_res= subselect->select_transformer(this)) !=
275
Item_subselect::RES_OK)
277
return((trans_res == Item_subselect::RES_ERROR));
286
for (ord= order; ord; ord= ord->next)
288
Item *item= *ord->item;
289
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
290
item->split_sum_func(session, ref_pointer_array, all_fields);
294
if (having && having->with_sum_func)
295
having->split_sum_func(session, ref_pointer_array, all_fields,
297
if (select_lex->inner_sum_func_list)
299
Item_sum *end=select_lex->inner_sum_func_list;
300
Item_sum *item_sum= end;
303
item_sum= item_sum->next;
304
item_sum->split_sum_func(session, ref_pointer_array,
305
all_fields, item_sum->ref_by, false);
306
} while (item_sum != end);
309
if (select_lex->inner_refs_list.elements &&
310
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
314
Check if there are references to un-aggregated columns when computing
315
aggregate functions with implicit grouping (there is no GROUP BY).
317
MODE_ONLY_FULL_GROUP_BY is enabled here by default
320
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
321
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
323
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
324
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
328
/* Caclulate the number of groups */
330
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
337
if (result && result->prepare(fields_list, unit_arg))
340
/* Init join struct */
341
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
342
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
343
this->group= group_list != 0;
346
#ifdef RESTRICTED_GROUP
347
if (sum_func_count && !group_list && (func_count || field_count))
349
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
353
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
355
if (alloc_func_list())
365
Remove the predicates pushed down into the subquery
368
JOIN::remove_subq_pushed_predicates()
369
where IN Must be NULL
370
OUT The remaining WHERE condition, or NULL
373
Given that this join will be executed using (unique|index)_subquery,
374
without "checking NULL", remove the predicates that were pushed down
377
If the subquery compares scalar values, we can remove the condition that
378
was wrapped into trig_cond (it will be checked when needed by the subquery
381
If the subquery compares row values, we need to keep the wrapped
382
equalities in the WHERE clause: when the left (outer) tuple has both NULL
383
and non-NULL values, we'll do a full table scan and will rely on the
384
equalities corresponding to non-NULL parts of left tuple to filter out
385
non-matching records.
387
TODO: We can remove the equalities that will be guaranteed to be true by the
388
fact that subquery engine will be using index lookup. This must be done only
389
for cases where there are no conversion errors of significance, e.g. 257
390
that is searched in a byte. But this requires homogenization of the return
391
codes of all Field*::store() methods.
393
void JOIN::remove_subq_pushed_predicates(Item **where)
395
if (conds->type() == Item::FUNC_ITEM &&
396
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
397
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
398
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
399
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
400
((Item_func *)conds)->arguments()[0]))
408
global select optimisation.
411
error code saved in field 'error'
420
// to prevent double initialization on EXPLAIN
425
session->set_proc_info("optimizing");
426
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
427
unit->select_limit_cnt);
428
/* select_limit is used to decide if we are likely to scan the whole table */
429
select_limit= unit->select_limit_cnt;
430
if (having || (select_options & OPTION_FOUND_ROWS))
431
select_limit= HA_POS_ERROR;
432
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
433
// Ignore errors of execution if option IGNORE present
434
if (session->lex->ignore)
435
session->lex->current_select->no_error= 1;
437
#ifdef HAVE_REF_TO_FIELDS // Not done yet
438
/* Add HAVING to WHERE if possible */
439
if (having && !group_list && !sum_func_count)
446
else if ((conds=new Item_cond_and(conds,having)))
449
Item_cond_and can't be fixed after creation, so we do not check
452
conds->fix_fields(session, &conds);
453
conds->change_ref_to_fields(session, tables_list);
454
conds->top_level_item();
460
/* Convert all outer joins to inner joins if possible */
461
conds= simplify_joins(this, join_list, conds, true);
462
build_bitmap_for_nested_joins(join_list, 0);
464
conds= optimize_cond(this, conds, join_list, &cond_value);
465
if (session->is_error())
472
having= optimize_cond(this, having, join_list, &having_value);
473
if (session->is_error())
478
if (select_lex->where)
479
select_lex->cond_value= cond_value;
480
if (select_lex->having)
481
select_lex->having_value= having_value;
483
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
484
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
485
{ /* Impossible cond */
486
zero_result_cause= having_value == Item::COND_FALSE ?
487
"Impossible HAVING" : "Impossible WHERE";
493
/* Optimize count(*), cmin() and cmax() */
494
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
498
optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
499
to the WHERE conditions,
500
or 1 if all items were resolved,
501
or 0, or an error number HA_ERR_...
503
if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
505
if (res == HA_ERR_KEY_NOT_FOUND)
507
zero_result_cause= "No matching min/max row";
518
zero_result_cause= "No matching min/max row";
522
zero_result_cause= "Select tables optimized away";
523
tables_list= 0; // All tables resolved
525
Extract all table-independent conditions and replace the WHERE
526
clause with them. All other conditions were computed by optimizer::sum_query
527
and the MIN/MAX/COUNT function(s) have been replaced by constants,
528
so there is no need to compute the whole WHERE clause again.
529
Notice that make_cond_for_table() will always succeed to remove all
530
computed conditions, because optimizer::sum_query() is applicable only to
532
Preserve conditions for EXPLAIN.
534
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
536
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
537
conds= table_independent_conds;
546
error= -1; // Error is sent to client
547
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
549
/* Calculate how to do the join */
550
session->set_proc_info("statistics");
551
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
552
session->is_fatal_error)
557
/* Remove distinct if only const tables */
558
select_distinct= select_distinct && (const_tables != tables);
559
session->set_proc_info("preparing");
560
if (result->initialize_tables(this))
562
return 1; // error == -1
564
if (const_table_map != found_const_table_map &&
565
!(select_options & SELECT_DESCRIBE) &&
567
!(conds->used_tables() & RAND_TABLE_BIT) ||
568
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
570
zero_result_cause= "no matching row in const table";
574
if (!(session->options & OPTION_BIG_SELECTS) &&
575
best_read > (double) session->variables.max_join_size &&
576
!(select_options & SELECT_DESCRIBE))
578
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
582
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
583
mysql_unlock_some_tables(session, table, const_tables);
584
if (!conds && outer_join)
586
/* Handle the case where we have an OUTER JOIN without a WHERE */
587
conds=new Item_int((int64_t) 1,1); // Always true
589
select= optimizer::make_select(*table, const_table_map,
590
const_table_map, conds, 1, &error);
597
reset_nj_counters(join_list);
598
make_outerjoin_info(this);
601
Among the equal fields belonging to the same multiple equality
602
choose the one that is to be retrieved first and substitute
603
all references to these in where condition for a reference for
608
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
609
conds->update_used_tables();
613
Permorm the the optimization on fields evaluation mentioned above
614
for all on expressions.
616
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
618
if (*tab->on_expr_ref)
620
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
623
(*tab->on_expr_ref)->update_used_tables();
627
if (conds &&!outer_join && const_table_map != found_const_table_map &&
628
(select_options & SELECT_DESCRIBE) &&
629
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
631
conds=new Item_int((int64_t) 0,1); // Always false
634
if (make_join_select(this, select, conds))
637
"Impossible WHERE noticed after reading const tables";
638
return(0); // error == 0
641
error= -1; /* if goto err */
643
/* Optimize distinct away if possible */
645
order_st *org_order= order;
646
order= remove_constants(this, order,conds,1, &simple_order);
647
if (session->is_error())
654
If we are using order_st BY NULL or order_st BY const_expression,
655
return result in any order (even if we are using a GROUP BY)
657
if (!order && org_order)
661
Check if we can optimize away GROUP BY/DISTINCT.
662
We can do that if there are no aggregate functions, the
663
fields in DISTINCT clause (if present) and/or columns in GROUP BY
664
(if present) contain direct references to all key parts of
665
an unique index (in whatever order) and if the key parts of the
666
unique index cannot contain NULLs.
667
Note that the unique keys for DISTINCT and GROUP BY should not
668
be the same (as long as they are unique).
670
The FROM clause must contain a single non-constant table.
672
if (tables - const_tables == 1 && (group_list || select_distinct) &&
673
! tmp_table_param.sum_func_count &&
674
(! join_tab[const_tables].select ||
675
! join_tab[const_tables].select->quick ||
676
join_tab[const_tables].select->quick->get_type() !=
677
optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
679
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
682
We have found that grouping can be removed since groups correspond to
683
only one row anyway, but we still have to guarantee correct result
684
order. The line below effectively rewrites the query from GROUP BY
685
<fields> to order_st BY <fields>. There are two exceptions:
686
- if skip_sort_order is set (see above), then we can simply skip
688
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
689
with the GROUP BY ones, i.e. either one is a prefix of another.
690
We only check if the order_st BY is a prefix of GROUP BY. In this case
691
test_if_subpart() copies the ASC/DESC attributes from the original
693
If GROUP BY is a prefix of order_st BY, then it is safe to leave
696
if (! order || test_if_subpart(group_list, order))
697
order= skip_sort_order ? 0 : group_list;
699
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
700
rewritten to IGNORE INDEX FOR order_st BY(fields).
702
join_tab->table->keys_in_use_for_order_by=
703
join_tab->table->keys_in_use_for_group_by;
707
if (select_distinct &&
708
list_contains_unique_index(join_tab[const_tables].table,
709
find_field_in_item_list,
710
(void *) &fields_list))
715
if (group_list || tmp_table_param.sum_func_count)
717
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
720
else if (select_distinct && tables - const_tables == 1)
723
We are only using one table. In this case we change DISTINCT to a
725
- The GROUP BY can be done through indexes (no sort) and the order_st
726
BY only uses selected fields.
727
(In this case we can later optimize away GROUP BY and order_st BY)
728
- We are scanning the whole table without LIMIT
730
- We are using CALC_FOUND_ROWS
731
- We are using an order_st BY that can't be optimized away.
733
We don't want to use this optimization when we are using LIMIT
734
because in this case we can just create a temporary table that
735
holds LIMIT rows and stop when this table is full.
737
JoinTable *tab= &join_tab[const_tables];
738
bool all_order_fields_used;
740
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
741
&tab->table->keys_in_use_for_order_by);
742
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
743
order, fields_list, all_fields,
744
&all_order_fields_used)))
746
bool skip_group= (skip_sort_order &&
747
test_if_skip_sort_order(tab, group_list, select_limit, 1,
748
&tab->table->keys_in_use_for_group_by) != 0);
749
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
750
if ((skip_group && all_order_fields_used) ||
751
select_limit == HA_POS_ERROR ||
752
(order && !skip_sort_order))
754
/* Change DISTINCT to GROUP BY */
757
if (all_order_fields_used)
759
if (order && skip_sort_order)
762
Force MySQL to read the table in sorted order to get result in
765
tmp_table_param.quick_group=0;
769
group=1; // For end_write_group
774
else if (session->is_fatal_error) // End of memory
779
order_st *old_group_list;
780
group_list= remove_constants(this, (old_group_list= group_list), conds,
781
rollup.state == ROLLUP::STATE_NONE,
783
if (session->is_error())
788
if (old_group_list && !group_list)
791
if (!group_list && group)
793
order=0; // The output has only one row
795
select_distinct= 0; // No need in distinct for 1 row
796
group_optimized_away= 1;
799
calc_group_buffer(this, group_list);
800
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
802
if (test_if_subpart(group_list, order) ||
803
(!group_list && tmp_table_param.sum_func_count))
806
// Can't use sort on head table if using row cache
816
Check if we need to create a temporary table.
817
This has to be done if all tables are not already read (const tables)
818
and one of the following conditions holds:
819
- We are using DISTINCT (simple distinct's are already optimized away)
820
- We are using an order_st BY or GROUP BY on fields not in the first table
821
- We are using different order_st BY and GROUP BY orders
822
- The user wants us to buffer the result.
824
need_tmp= (const_tables != tables &&
825
((select_distinct || !simple_order || !simple_group) ||
826
(group_list && order) ||
827
test(select_options & OPTION_BUFFER_RESULT)));
829
uint32_t no_jbuf_after= make_join_orderinfo(this);
830
uint64_t select_opts_for_readinfo=
831
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
833
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
834
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
837
/* Create all structures needed for materialized subquery execution. */
838
if (setup_subquery_materialization())
841
/* Cache constant expressions in WHERE, HAVING, ON clauses. */
845
is this simple IN subquery?
847
if (!group_list && !order &&
848
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
849
tables == 1 && conds &&
855
if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
857
remove_subq_pushed_predicates(&where);
858
save_index_subquery_explain_info(join_tab, where);
859
join_tab[0].type= AM_UNIQUE_SUBQUERY;
863
subselect_uniquesubquery_engine(session,
868
else if (join_tab[0].type == AM_REF &&
869
join_tab[0].ref.items[0]->name == in_left_expr_name)
871
remove_subq_pushed_predicates(&where);
872
save_index_subquery_explain_info(join_tab, where);
873
join_tab[0].type= AM_INDEX_SUBQUERY;
877
subselect_indexsubquery_engine(session,
885
else if (join_tab[0].type == AM_REF_OR_NULL &&
886
join_tab[0].ref.items[0]->name == in_left_expr_name &&
887
having->name == in_having_cond)
889
join_tab[0].type= AM_INDEX_SUBQUERY;
891
conds= remove_additional_cond(conds);
892
save_index_subquery_explain_info(join_tab, conds);
894
change_engine(new subselect_indexsubquery_engine(session,
904
Need to tell handlers that to play it safe, it should fetch all
905
columns of the primary key of the tables: this is because MySQL may
906
build row pointers for the rows, and for all columns of the primary key
907
the read set has not necessarily been set by the server code.
909
if (need_tmp || select_distinct || group_list || order)
911
for (uint32_t i = const_tables; i < tables; i++)
912
join_tab[i].table->prepare_for_position();
915
if (const_tables != tables)
918
Because filesort always does a full table scan or a quick range scan
919
we must add the removed reference to the select for the table.
920
We only need to do this when we have a simple_order or simple_group
921
as in other cases the join is done before the sort.
923
if ((order || group_list) &&
924
(join_tab[const_tables].type != AM_ALL) &&
925
(join_tab[const_tables].type != AM_REF_OR_NULL) &&
926
((order && simple_order) || (group_list && simple_group)))
928
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
933
if (!(select_options & SELECT_BIG_RESULT) &&
936
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
937
unit->select_limit_cnt, 0,
938
&join_tab[const_tables].table->
939
keys_in_use_for_group_by))) ||
941
tmp_table_param.quick_group)
943
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
948
Force using of tmp table if sorting by a SP or UDF function due to
949
their expensive and probably non-deterministic nature.
951
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
953
Item *item= *tmp_order->item;
954
if (item->is_expensive())
956
/* Force tmp table without sort */
957
need_tmp=1; simple_order=simple_group=0;
965
if (select_options & SELECT_DESCRIBE)
973
The loose index scan access method guarantees that all grouping or
974
duplicate row elimination (for distinct) is already performed
975
during data retrieval, and that all MIN/MAX functions are already
976
computed for each group. Thus all MIN/MAX functions should be
977
treated as regular functions, and there is no need to perform
978
grouping in the main execution loop.
979
Notice that currently loose index scan is applicable only for
980
single table queries, thus it is sufficient to test only the first
981
join_tab element of the plan for its access method.
983
if (join_tab->is_using_loose_index_scan())
984
tmp_table_param.precomputed_group_by= true;
986
/* Create a tmp table if distinct or if the sort is too complicated */
989
session->set_proc_info("Creating tmp table");
991
init_items_ref_array();
993
tmp_table_param.hidden_field_count= (all_fields.elements -
994
fields_list.elements);
995
order_st *tmp_group= ((!simple_group &&
996
! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
999
Pushing LIMIT to the temporary table creation is not applicable
1000
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1001
there are aggregate functions, because in all these cases we need
1004
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1006
!session->lex->current_select->with_sum_func) ?
1007
select_limit : HA_POS_ERROR;
1009
if (!(exec_tmp_table1=
1010
create_tmp_table(session, &tmp_table_param, all_fields,
1012
group_list ? 0 : select_distinct,
1013
group_list && simple_group,
1022
We don't have to store rows in temp table that doesn't match HAVING if:
1023
- we are sorting the table and writing complete group rows to the
1025
- We are using DISTINCT without resolving the distinct as a GROUP BY
1028
If having is not handled here, it will be checked before the row
1029
is sent to the client.
1031
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1034
/* if group or order on first table, sort first */
1035
if (group_list && simple_group)
1037
session->set_proc_info("Sorting for group");
1038
if (create_sort_index(session, this, group_list,
1039
HA_POS_ERROR, HA_POS_ERROR, false) ||
1040
alloc_group_fields(this, group_list) ||
1041
make_sum_func_list(all_fields, fields_list, 1) ||
1042
setup_sum_funcs(session, sum_funcs))
1050
if (make_sum_func_list(all_fields, fields_list, 0) ||
1051
setup_sum_funcs(session, sum_funcs))
1056
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1058
session->set_proc_info("Sorting for order");
1059
if (create_sort_index(session, this, order,
1060
HA_POS_ERROR, HA_POS_ERROR, true))
1069
Optimize distinct when used on some of the tables
1070
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1071
In this case we can stop scanning t2 when we have found one t1.a
1074
if (exec_tmp_table1->distinct)
1076
table_map used_tables= session->used_tables;
1077
JoinTable *last_join_tab= join_tab+tables-1;
1080
if (used_tables & last_join_tab->table->map)
1082
last_join_tab->not_used_in_distinct=1;
1083
} while (last_join_tab-- != join_tab);
1084
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1085
if (order && skip_sort_order)
1087
/* Should always succeed */
1088
if (test_if_skip_sort_order(&join_tab[const_tables],
1089
order, unit->select_limit_cnt, 0,
1090
&join_tab[const_tables].table->
1091
keys_in_use_for_order_by))
1097
If this join belongs to an uncacheable subquery save
1100
if (select_lex->uncacheable && !is_top_level_join() &&
1101
init_save_join_tab())
1110
Restore values in temporary join.
1112
void JOIN::restore_tmp()
1114
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1119
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1120
select_lex->offset_limit->val_uint() :
1125
if (exec_tmp_table1)
1127
exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1128
exec_tmp_table1->cursor->ha_delete_all_rows();
1129
exec_tmp_table1->free_io_cache();
1130
exec_tmp_table1->filesort_free_buffers();
1132
if (exec_tmp_table2)
1134
exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1135
exec_tmp_table2->cursor->ha_delete_all_rows();
1136
exec_tmp_table2->free_io_cache();
1137
exec_tmp_table2->filesort_free_buffers();
1140
set_items_ref_array(items0);
1143
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1148
/* Reset of sum functions */
1151
Item_sum *func, **func_ptr= sum_funcs;
1152
while ((func= *(func_ptr++)))
1160
@brief Save the original join layout
1162
@details Saves the original join layout so it can be reused in
1163
re-execution and for EXPLAIN.
1165
@return Operation status
1167
@retval 1 error occurred.
1169
bool JOIN::init_save_join_tab()
1171
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
1173
error= 0; // Ensure that tmp_join.error= 0
1178
bool JOIN::save_join_tab()
1180
if (!join_tab_save && select_lex->master_unit()->uncacheable)
1182
if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1183
sizeof(JoinTable) * tables)))
1193
Note, that create_sort_index calls test_if_skip_sort_order and may
1194
finally replace sorting with index scan if there is a LIMIT clause in
1195
the query. It's never shown in EXPLAIN!
1198
When can we have here session->net.report_error not zero?
1202
List<Item> *columns_list= &fields_list;
1205
session->set_proc_info("executing");
1208
if (!tables_list && (tables || !select_lex->with_sum_func))
1210
/* Only test of functions */
1211
if (select_options & SELECT_DESCRIBE)
1213
optimizer::ExplainPlan planner(this,
1217
(zero_result_cause ? zero_result_cause : "No tables used"));
1218
planner.printPlan();
1222
result->send_fields(*columns_list);
1224
We have to test for 'conds' here as the WHERE may not be constant
1225
even if we don't have any tables for prepared statements or if
1226
conds uses something like 'rand()'.
1228
if (cond_value != Item::COND_FALSE &&
1229
(!conds || conds->val_int()) &&
1230
(!having || having->val_int()))
1232
if (do_send_rows && result->send_data(fields_list))
1236
error= (int) result->send_eof();
1237
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1242
error= (int) result->send_eof();
1246
/* Single select (without union) always returns 0 or 1 row */
1247
session->limit_found_rows= send_records;
1248
session->examined_row_count= 0;
1252
Don't reset the found rows count if there're no tables as
1253
FOUND_ROWS() may be called. Never reset the examined row count here.
1254
It must be accumulated from all join iterations of all join parts.
1257
session->limit_found_rows= 0;
1259
if (zero_result_cause)
1261
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1263
send_row_on_empty_set(),
1270
if (select_options & SELECT_DESCRIBE)
1273
Check if we managed to optimize order_st BY away and don't use temporary
1274
table to resolve order_st BY: in that case, we only may need to do
1275
filesort for GROUP BY.
1277
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1279
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1281
simple_order= simple_group;
1284
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1286
if (const_tables == tables
1287
|| ((simple_order || skip_sort_order)
1288
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1292
optimizer::ExplainPlan planner(this,
1294
order != 0 && ! skip_sort_order,
1296
! tables ? "No tables used" : NULL);
1297
planner.printPlan();
1301
JOIN *curr_join= this;
1302
List<Item> *curr_all_fields= &all_fields;
1303
List<Item> *curr_fields_list= &fields_list;
1304
Table *curr_tmp_table= 0;
1306
Initialize examined rows here because the values from all join parts
1307
must be accumulated in examined_row_count. Hence every join
1308
iteration must count from zero.
1310
curr_join->examined_rows= 0;
1312
/* Create a tmp table if distinct or if the sort is too complicated */
1318
We are in a non cacheable sub query. Get the saved join structure
1320
(curr_join may have been modified during last exection and we need
1323
curr_join= tmp_join;
1325
curr_tmp_table= exec_tmp_table1;
1327
/* Copy data to the temporary table */
1328
session->set_proc_info("Copying to tmp table");
1329
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1330
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1331
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1336
curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
1338
if (curr_join->having)
1339
curr_join->having= curr_join->tmp_having= 0; // Allready done
1341
/* Change sum_fields reference to calculated fields in tmp_table */
1342
curr_join->all_fields= *curr_all_fields;
1345
items1= items0 + all_fields.elements;
1346
if (sort_and_group || curr_tmp_table->group)
1348
if (change_to_use_tmp_fields(session, items1,
1349
tmp_fields_list1, tmp_all_fields1,
1350
fields_list.elements, all_fields))
1355
if (change_refs_to_tmp_fields(session, items1,
1356
tmp_fields_list1, tmp_all_fields1,
1357
fields_list.elements, all_fields))
1360
curr_join->tmp_all_fields1= tmp_all_fields1;
1361
curr_join->tmp_fields_list1= tmp_fields_list1;
1362
curr_join->items1= items1;
1364
curr_all_fields= &tmp_all_fields1;
1365
curr_fields_list= &tmp_fields_list1;
1366
curr_join->set_items_ref_array(items1);
1368
if (sort_and_group || curr_tmp_table->group)
1370
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1371
+ curr_join->tmp_table_param.func_count;
1372
curr_join->tmp_table_param.sum_func_count= 0;
1373
curr_join->tmp_table_param.func_count= 0;
1377
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1378
curr_join->tmp_table_param.func_count= 0;
1381
if (curr_tmp_table->group)
1382
{ // Already grouped
1383
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1384
curr_join->order= curr_join->group_list; /* order by group */
1385
curr_join->group_list= 0;
1389
If we have different sort & group then we must sort the data by group
1390
and copy it to another tmp table
1391
This code is also used if we are using distinct something
1392
we haven't been able to store in the temporary table yet
1393
like SEC_TO_TIME(SUM(...)).
1396
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1397
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1398
{ /* Must copy to another table */
1399
/* Free first data from old join */
1400
curr_join->join_free();
1401
if (make_simple_join(curr_join, curr_tmp_table))
1403
calc_group_buffer(curr_join, group_list);
1404
count_field_types(select_lex, &curr_join->tmp_table_param,
1405
curr_join->tmp_all_fields1,
1406
curr_join->select_distinct && !curr_join->group_list);
1407
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1408
- curr_join->tmp_fields_list1.elements;
1410
if (exec_tmp_table2)
1411
curr_tmp_table= exec_tmp_table2;
1414
/* group data to new table */
1417
If the access method is loose index scan then all MIN/MAX
1418
functions are precomputed, and should be treated as regular
1419
functions. See extended comment in JOIN::exec.
1421
if (curr_join->join_tab->is_using_loose_index_scan())
1422
curr_join->tmp_table_param.precomputed_group_by= true;
1424
if (!(curr_tmp_table=
1425
exec_tmp_table2= create_tmp_table(session,
1426
&curr_join->tmp_table_param,
1429
curr_join->select_distinct &&
1430
!curr_join->group_list,
1431
1, curr_join->select_options,
1435
curr_join->exec_tmp_table2= exec_tmp_table2;
1437
if (curr_join->group_list)
1439
session->set_proc_info("Creating sort index");
1440
if (curr_join->join_tab == join_tab && save_join_tab())
1444
if (create_sort_index(session, curr_join, curr_join->group_list,
1445
HA_POS_ERROR, HA_POS_ERROR, false) ||
1446
make_group_fields(this, curr_join))
1450
sortorder= curr_join->sortorder;
1453
session->set_proc_info("Copying to group table");
1455
if (curr_join != this)
1459
curr_join->sum_funcs= sum_funcs2;
1460
curr_join->sum_funcs_end= sum_funcs_end2;
1464
curr_join->alloc_func_list();
1465
sum_funcs2= curr_join->sum_funcs;
1466
sum_funcs_end2= curr_join->sum_funcs_end;
1469
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1471
curr_join->group_list= 0;
1473
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1474
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1476
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1477
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1482
end_read_record(&curr_join->join_tab->read_record);
1483
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1484
curr_join->join_tab[0].table= 0; // Table is freed
1486
// No sum funcs anymore
1489
items2= items1 + all_fields.elements;
1490
if (change_to_use_tmp_fields(session, items2,
1491
tmp_fields_list2, tmp_all_fields2,
1492
fields_list.elements, tmp_all_fields1))
1494
curr_join->tmp_fields_list2= tmp_fields_list2;
1495
curr_join->tmp_all_fields2= tmp_all_fields2;
1497
curr_fields_list= &curr_join->tmp_fields_list2;
1498
curr_all_fields= &curr_join->tmp_all_fields2;
1499
curr_join->set_items_ref_array(items2);
1500
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1501
curr_join->tmp_table_param.sum_func_count= 0;
1503
if (curr_tmp_table->distinct)
1504
curr_join->select_distinct=0; /* Each row is unique */
1506
curr_join->join_free(); /* Free quick selects */
1507
if (curr_join->select_distinct && ! curr_join->group_list)
1509
session->set_proc_info("Removing duplicates");
1510
if (curr_join->tmp_having)
1511
curr_join->tmp_having->update_used_tables();
1513
if (remove_duplicates(curr_join, curr_tmp_table,
1514
*curr_fields_list, curr_join->tmp_having))
1517
curr_join->tmp_having=0;
1518
curr_join->select_distinct=0;
1520
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1521
if (make_simple_join(curr_join, curr_tmp_table))
1523
calc_group_buffer(curr_join, curr_join->group_list);
1524
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1528
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1530
if (make_group_fields(this, curr_join))
1536
init_items_ref_array();
1537
items3= ref_pointer_array + (all_fields.elements*4);
1538
setup_copy_fields(session, &curr_join->tmp_table_param,
1539
items3, tmp_fields_list3, tmp_all_fields3,
1540
curr_fields_list->elements, *curr_all_fields);
1541
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1542
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1543
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1544
curr_join->tmp_all_fields3= tmp_all_fields3;
1545
curr_join->tmp_fields_list3= tmp_fields_list3;
1549
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1550
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1551
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1553
curr_fields_list= &tmp_fields_list3;
1554
curr_all_fields= &tmp_all_fields3;
1555
curr_join->set_items_ref_array(items3);
1557
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1559
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1560
session->is_fatal_error)
1563
if (curr_join->group_list || curr_join->order)
1565
session->set_proc_info("Sorting result");
1566
/* If we have already done the group, add HAVING to sorted table */
1567
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1569
// Some tables may have been const
1570
curr_join->tmp_having->update_used_tables();
1571
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1572
table_map used_tables= (curr_join->const_table_map |
1573
curr_table->table->map);
1575
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1576
if (sort_table_cond)
1578
if (!curr_table->select)
1579
if (!(curr_table->select= new optimizer::SqlSelect))
1581
if (!curr_table->select->cond)
1582
curr_table->select->cond= sort_table_cond;
1583
else // This should never happen
1585
if (!(curr_table->select->cond=
1586
new Item_cond_and(curr_table->select->cond,
1590
Item_cond_and do not need fix_fields for execution, its parameters
1591
are fixed or do not need fix_fields, too
1593
curr_table->select->cond->quick_fix_field();
1595
curr_table->select_cond= curr_table->select->cond;
1596
curr_table->select_cond->top_level_item();
1597
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1604
curr_join->select_limit= HA_POS_ERROR;
1608
We can abort sorting after session->select_limit rows if we there is no
1609
WHERE clause for any tables after the sorted one.
1611
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1612
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1613
for (; curr_table < end_table ; curr_table++)
1616
table->keyuse is set in the case there was an original WHERE clause
1617
on the table that was optimized away.
1619
if (curr_table->select_cond ||
1620
(curr_table->keyuse && !curr_table->first_inner))
1622
/* We have to sort all rows */
1623
curr_join->select_limit= HA_POS_ERROR;
1628
if (curr_join->join_tab == join_tab && save_join_tab())
1631
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1632
chose FILESORT to be faster than INDEX SCAN or there is no
1633
suitable index present.
1634
Note, that create_sort_index calls test_if_skip_sort_order and may
1635
finally replace sorting with index scan if there is a LIMIT clause in
1636
the query. XXX: it's never shown in EXPLAIN!
1637
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1639
if (create_sort_index(session, curr_join,
1640
curr_join->group_list ?
1641
curr_join->group_list : curr_join->order,
1642
curr_join->select_limit,
1643
(select_options & OPTION_FOUND_ROWS ?
1644
HA_POS_ERROR : unit->select_limit_cnt),
1645
curr_join->group_list ? true : false))
1648
sortorder= curr_join->sortorder;
1649
if (curr_join->const_tables != curr_join->tables &&
1650
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1653
If no IO cache exists for the first table then we are using an
1654
INDEX SCAN and no filesort. Thus we should not remove the sorted
1655
attribute on the INDEX SCAN.
1661
/* XXX: When can we have here session->is_error() not zero? */
1662
if (session->is_error())
1664
error= session->is_error();
1667
curr_join->having= curr_join->tmp_having;
1668
curr_join->fields= curr_fields_list;
1670
session->set_proc_info("Sending data");
1671
result->send_fields(*curr_fields_list);
1672
error= do_select(curr_join, curr_fields_list, NULL);
1673
session->limit_found_rows= curr_join->send_records;
1675
/* Accumulate the counts from all join iterations of all join parts. */
1676
session->examined_row_count+= curr_join->examined_rows;
1679
With EXPLAIN EXTENDED we have to restore original ref_array
1680
for a derived table which is always materialized.
1681
Otherwise we would not be able to print the query correctly.
1683
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1684
set_items_ref_array(items0);
1693
Return error that hold JOIN.
1697
select_lex->join= 0;
1701
if (join_tab != tmp_join->join_tab)
1703
JoinTable *tab, *end;
1704
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1707
tmp_join->tmp_join= 0;
1708
tmp_table_param.copy_field=0;
1709
return(tmp_join->destroy());
1714
if (exec_tmp_table1)
1715
exec_tmp_table1->free_tmp_table(session);
1716
if (exec_tmp_table2)
1717
exec_tmp_table2->free_tmp_table(session);
1719
delete_dynamic(&keyuse);
1724
Setup for execution all subqueries of a query, for which the optimizer
1725
chose hash semi-join.
1727
@details Iterate over all subqueries of the query, and if they are under an
1728
IN predicate, and the optimizer chose to compute it via hash semi-join:
1729
- try to initialize all data structures needed for the materialized execution
1730
of the IN predicate,
1731
- if this fails, then perform the IN=>EXISTS transformation which was
1732
previously blocked during JOIN::prepare.
1734
This method is part of the "code generation" query processing phase.
1736
This phase must be called after substitute_for_best_equal_field() because
1737
that function may replace items with other items from a multiple equality,
1738
and we need to reference the correct items in the index access method of the
1741
@return Operation status
1742
@retval false success.
1743
@retval true error occurred.
1745
bool JOIN::setup_subquery_materialization()
1747
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1748
un= un->next_unit())
1750
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1752
Item_subselect *subquery_predicate= sl->master_unit()->item;
1753
if (subquery_predicate &&
1754
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1756
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1757
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1758
in_subs->setup_engine())
1767
Partially cleanup JOIN after it has executed: close index or rnd read
1768
(table cursors), free quick selects.
1770
This function is called in the end of execution of a JOIN, before the used
1771
tables are unlocked and closed.
1773
For a join that is resolved using a temporary table, the first sweep is
1774
performed against actual tables and an intermediate result is inserted
1775
into the temprorary table.
1776
The last sweep is performed against the temporary table. Therefore,
1777
the base tables and associated buffers used to fill the temporary table
1778
are no longer needed, and this function is called to free them.
1780
For a join that is performed without a temporary table, this function
1781
is called after all rows are sent, but before EOF packet is sent.
1783
For a simple SELECT with no subqueries this function performs a full
1784
cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1787
If a JOIN is executed for a subquery or if it has a subquery, we can't
1788
do the full cleanup and need to do a partial cleanup only.
1789
- If a JOIN is not the top level join, we must not unlock the tables
1790
because the outer select may not have been evaluated yet, and we
1791
can't unlock only selected tables of a query.
1792
- Additionally, if this JOIN corresponds to a correlated subquery, we
1793
should not free quick selects and join buffers because they will be
1794
needed for the next execution of the correlated subquery.
1795
- However, if this is a JOIN for a [sub]select, which is not
1796
a correlated subquery itself, but has subqueries, we can free it
1797
fully and also free JOINs of all its subqueries. The exception
1798
is a subquery in SELECT list, e.g: @n
1799
SELECT a, (select cmax(b) from t1) group by c @n
1800
This subquery will not be evaluated at first sweep and its value will
1801
not be inserted into the temporary table. Instead, it's evaluated
1802
when selecting from the temporary table. Therefore, it can't be freed
1803
here even though it's not correlated.
1806
Unlock tables even if the join isn't top level select in the tree
1808
void JOIN::join_free()
1810
Select_Lex_Unit *tmp_unit;
1813
Optimization: if not EXPLAIN and we are done with the JOIN,
1816
bool full= (!select_lex->uncacheable && !session->lex->describe);
1817
bool can_unlock= full;
1821
for (tmp_unit= select_lex->first_inner_unit();
1823
tmp_unit= tmp_unit->next_unit())
1824
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
1826
Item_subselect *subselect= sl->master_unit()->item;
1827
bool full_local= full && (!subselect || subselect->is_evaluated());
1829
If this join is evaluated, we can fully clean it up and clean up all
1830
its underlying joins even if they are correlated -- they will not be
1831
used any more anyway.
1832
If this join is not yet evaluated, we still must clean it up to
1833
close its table cursors -- it may never get evaluated, as in case of
1834
... HAVING false OR a IN (SELECT ...))
1835
but all table cursors must be closed before the unlock.
1837
sl->cleanup_all_joins(full_local);
1838
/* Can't unlock if at least one JOIN is still needed */
1839
can_unlock= can_unlock && full_local;
1843
We are not using tables anymore
1844
Unlock all tables. We may be in an INSERT .... SELECT statement.
1846
if (can_unlock && lock && session->lock &&
1847
!(select_options & SELECT_NO_UNLOCK) &&
1848
!select_lex->subquery_in_having &&
1849
(select_lex == (session->lex->unit.fake_select_lex ?
1850
session->lex->unit.fake_select_lex : &session->lex->select_lex)))
1853
TODO: unlock tables even if the join isn't top level select in the
1856
mysql_unlock_read_tables(session, lock); // Don't free join->lock
1865
Free resources of given join.
1867
@param fill true if we should free all resources, call with full==1
1868
should be last, before it this function can be called with
1872
With subquery this function definitely will be called several times,
1873
but even for simple query it can be called several times.
1875
void JOIN::cleanup(bool full)
1879
JoinTable *tab,*end;
1881
Only a sorted table may be cached. This sorted table is always the
1882
first non const table in join->table
1884
if (tables > const_tables) // Test for not-const tables
1886
table[const_tables]->free_io_cache();
1887
table[const_tables]->filesort_free_buffers(full);
1892
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1898
for (tab= join_tab, end= tab+tables; tab != end; tab++)
1901
tab->table->cursor->ha_index_or_rnd_end();
1906
We are not using tables anymore
1907
Unlock all tables. We may be in an INSERT .... SELECT statement.
1912
tmp_table_param.copy_field= 0;
1913
group_fields.delete_elements();
1915
We can't call delete_elements() on copy_funcs as this will cause
1916
problems in free_elements() as some of the elements are then deleted.
1918
tmp_table_param.copy_funcs.empty();
1920
If we have tmp_join and 'this' JOIN is not tmp_join and
1921
tmp_table_param.copy_field's of them are equal then we have to remove
1922
pointer to tmp_table_param.copy_field from tmp_join, because it qill
1923
be removed in tmp_table_param.cleanup().
1927
tmp_join->tmp_table_param.copy_field ==
1928
tmp_table_param.copy_field)
1930
tmp_join->tmp_table_param.copy_field=
1931
tmp_join->tmp_table_param.save_copy_field= 0;
1933
tmp_table_param.cleanup();
1939
used only in JOIN::clear
1941
static void clear_tables(JOIN *join)
1944
must clear only the non-const tables, as const tables
1945
are not re-calculated.
1947
for (uint32_t i= join->const_tables; i < join->tables; i++)
1948
join->table[i]->mark_as_null_row(); // All fields are NULL
1952
Make an array of pointers to sum_functions to speed up
1953
sum_func calculation.
1960
bool JOIN::alloc_func_list()
1962
uint32_t func_count, group_parts;
1964
func_count= tmp_table_param.sum_func_count;
1966
If we are using rollup, we need a copy of the summary functions for
1969
if (rollup.state != ROLLUP::STATE_NONE)
1970
func_count*= (send_group_parts+1);
1972
group_parts= send_group_parts;
1974
If distinct, reserve memory for possible
1975
disctinct->group_by optimization
1977
if (select_distinct)
1979
group_parts+= fields_list.elements;
1981
If the order_st clause is specified then it's possible that
1982
it also will be optimized, so reserve space for it too
1987
for (ord= order; ord; ord= ord->next)
1992
/* This must use calloc() as rollup_make_fields depends on this */
1993
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
1994
sizeof(Item_sum***) * (group_parts+1));
1995
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
1996
return(sum_funcs == 0);
2000
Initialize 'sum_funcs' array with all Item_sum objects.
2002
@param field_list All items
2003
@param send_fields Items in select list
2004
@param before_group_by Set to 1 if this is called before GROUP BY handling
2005
@param recompute Set to true if sum_funcs must be recomputed
2012
bool JOIN::make_sum_func_list(List<Item> &field_list,
2013
List<Item> &send_fields,
2014
bool before_group_by,
2017
List_iterator_fast<Item> it(field_list);
2021
if (*sum_funcs && !recompute)
2022
return(false); /* We have already initialized sum_funcs. */
2027
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2028
(!((Item_sum*) item)->depended_from() ||
2029
((Item_sum *)item)->depended_from() == select_lex))
2030
*func++= (Item_sum*) item;
2032
if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2034
rollup.state= ROLLUP::STATE_READY;
2035
if (rollup_make_fields(field_list, send_fields, &func))
2036
return(true); // Should never happen
2038
else if (rollup.state == ROLLUP::STATE_NONE)
2040
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2041
sum_funcs_end[i]= func;
2043
else if (rollup.state == ROLLUP::STATE_READY)
2044
return(false); // Don't put end marker
2045
*func=0; // End marker
2049
/** Allocate memory needed for other rollup functions. */
2050
bool JOIN::rollup_init()
2055
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2056
rollup.state= ROLLUP::STATE_INITED;
2059
Create pointers to the different sum function groups
2060
These are updated by rollup_make_fields()
2062
tmp_table_param.group_parts= send_group_parts;
2064
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
2066
sizeof(List<Item>) +
2067
ref_pointer_array_size)
2068
* send_group_parts )))
2071
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
2072
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
2073
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2076
Prepare space for field list for the different levels
2077
These will be filled up in rollup_make_fields()
2079
for (i= 0 ; i < send_group_parts ; i++)
2081
rollup.null_items[i]= new (session->mem_root) Item_null_result();
2082
List<Item> *rollup_fields= &rollup.fields[i];
2083
rollup_fields->empty();
2084
rollup.ref_pointer_arrays[i]= ref_array;
2085
ref_array+= all_fields.elements;
2087
for (i= 0 ; i < send_group_parts; i++)
2089
for (j=0 ; j < fields_list.elements ; j++)
2090
rollup.fields[i].push_back(rollup.null_items[i]);
2092
List_iterator<Item> it(all_fields);
2094
while ((item= it++))
2096
order_st *group_tmp;
2097
bool found_in_group= 0;
2099
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2101
if (*group_tmp->item == item)
2103
item->maybe_null= 1;
2105
if (item->const_item())
2108
For ROLLUP queries each constant item referenced in GROUP BY list
2109
is wrapped up into an Item_func object yielding the same value
2110
as the constant item. The objects of the wrapper class are never
2111
considered as constant items and besides they inherit all
2112
properties of the Item_result_field class.
2113
This wrapping allows us to ensure writing constant items
2114
into temporary tables whenever the result of the ROLLUP
2115
operation has to be written into a temporary table, e.g. when
2116
ROLLUP is used together with DISTINCT in the SELECT list.
2117
Usually when creating temporary tables for a intermidiate
2118
result we do not include fields for constant expressions.
2120
Item* new_item= new Item_func_rollup_const(item);
2123
new_item->fix_fields(session, (Item **) 0);
2124
session->change_item_tree(it.ref(), new_item);
2125
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2127
if (*tmp->item == item)
2128
session->change_item_tree(tmp->item, new_item);
2133
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2135
bool changed= false;
2136
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2139
We have to prevent creation of a field in a temporary table for
2140
an expression that contains GROUP BY attributes.
2141
Marking the expression item as 'with_sum_func' will ensure this.
2144
item->with_sum_func= 1;
2151
Fill up rollup structures with pointers to fields to use.
2153
Creates copies of item_sum items for each sum level.
2155
@param fields_arg List of all fields (hidden and real ones)
2156
@param sel_fields Pointer to selected fields
2157
@param func Store here a pointer to all fields
2161
In this case func is pointing to next not used element.
2165
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2167
List_iterator_fast<Item> it(fields_arg);
2168
Item *first_field= sel_fields.head();
2172
Create field lists for the different levels
2174
The idea here is to have a separate field list for each rollup level to
2175
avoid all runtime checks of which columns should be NULL.
2177
The list is stored in reverse order to get sum function in such an order
2178
in func that it makes it easy to reset them with init_sum_functions()
2180
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2182
rollup.fields[0] will contain list where a,b,c is NULL
2183
rollup.fields[1] will contain list where b,c is NULL
2185
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2187
sum_funcs_end[0] points to all sum functions
2188
sum_funcs_end[1] points to all sum functions, except grand totals
2192
for (level=0 ; level < send_group_parts ; level++)
2195
uint32_t pos= send_group_parts - level -1;
2196
bool real_fields= 0;
2198
List_iterator<Item> new_it(rollup.fields[pos]);
2199
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2200
order_st *start_group;
2202
/* Point to first hidden field */
2203
Item **ref_array= ref_array_start + fields_arg.elements-1;
2205
/* Remember where the sum functions ends for the previous level */
2206
sum_funcs_end[pos+1]= *func;
2208
/* Find the start of the group for this level */
2209
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2213
while ((item= it++))
2215
if (item == first_field)
2217
real_fields= 1; // End of hidden fields
2218
ref_array= ref_array_start;
2221
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2222
(!((Item_sum*) item)->depended_from() ||
2223
((Item_sum *)item)->depended_from() == select_lex))
2227
This is a top level summary function that must be replaced with
2228
a sum function that is reset for this level.
2230
NOTE: This code creates an object which is not that nice in a
2231
sub select. Fortunately it's not common to have rollup in
2234
item= item->copy_or_same(session);
2235
((Item_sum*) item)->make_unique();
2236
*(*func)= (Item_sum*) item;
2241
/* Check if this is something that is part of this group by */
2242
order_st *group_tmp;
2243
for (group_tmp= start_group, i= pos ;
2244
group_tmp ; group_tmp= group_tmp->next, i++)
2246
if (*group_tmp->item == item)
2249
This is an element that is used by the GROUP BY and should be
2250
set to NULL in this level
2252
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2255
item->maybe_null= 1; // Value will be null sometimes
2256
null_item->result_field= item->get_tmp_table_field();
2265
(void) new_it++; // Point to next item
2266
new_it.replace(item); // Replace previous
2273
sum_funcs_end[0]= *func; // Point to last function
2278
Send all rollup levels higher than the current one to the client.
2282
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2285
@param idx Level we are on:
2286
- 0 = Total sum level
2287
- 1 = First group changed (a)
2288
- 2 = Second group changed (a,b)
2293
1 If send_data_failed()
2295
int JOIN::rollup_send_data(uint32_t idx)
2298
for (i= send_group_parts ; i-- > idx ; )
2300
/* Get reference pointers to sum functions in place */
2301
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2302
ref_pointer_array_size);
2303
if ((!having || having->val_int()))
2305
if (send_records < unit->select_limit_cnt && do_send_rows &&
2306
result->send_data(rollup.fields[i]))
2311
/* Restore ref_pointer_array */
2312
set_items_ref_array(current_ref_pointer_array);
2317
Write all rollup levels higher than the current one to a temp table.
2321
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2324
@param idx Level we are on:
2325
- 0 = Total sum level
2326
- 1 = First group changed (a)
2327
- 2 = Second group changed (a,b)
2328
@param table reference to temp table
2333
1 if write_data_failed()
2335
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2338
for (i= send_group_parts ; i-- > idx ; )
2340
/* Get reference pointers to sum functions in place */
2341
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2342
ref_pointer_array_size);
2343
if ((!having || having->val_int()))
2347
List_iterator_fast<Item> it(rollup.fields[i]);
2348
while ((item= it++))
2350
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2351
item->save_in_result_field(1);
2353
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2354
if ((write_error= table_arg->cursor->ha_write_row(table_arg->record[0])))
2356
if (create_myisam_from_heap(session, table_arg,
2357
tmp_table_param.start_recinfo,
2358
&tmp_table_param.recinfo,
2364
/* Restore ref_pointer_array */
2365
set_items_ref_array(current_ref_pointer_array);
2370
clear results if there are not rows found for group
2371
(end_send_group/end_write_group)
2376
copy_fields(&tmp_table_param);
2380
Item_sum *func, **func_ptr= sum_funcs;
2381
while ((func= *(func_ptr++)))
2387
change select_result object of JOIN.
2389
@param res new select_result object
2396
bool JOIN::change_result(select_result *res)
2399
if (result->prepare(fields_list, select_lex->master_unit()))
2407
Cache constant expressions in WHERE, HAVING, ON conditions.
2410
void JOIN::cache_const_exprs()
2412
bool cache_flag= false;
2413
bool *analyzer_arg= &cache_flag;
2415
/* No need in cache if all tables are constant. */
2416
if (const_tables == tables)
2420
conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2421
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2424
having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2425
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2427
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2429
if (*tab->on_expr_ref)
2432
(*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2433
(unsigned char **)&analyzer_arg,
2434
&Item::cache_const_expr_transformer,
2435
(unsigned char *)&cache_flag);
2443
Process one record of the nested loop join.
2447
This function will evaluate parts of WHERE/ON clauses that are
2448
applicable to the partial record on hand and in case of success
2449
submit this record to the next level of the nested loop.
2451
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error)
2453
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2454
ha_rows found_records= join->found_records;
2455
COND *select_cond= join_tab->select_cond;
2457
if (error > 0 || (join->session->is_error())) // Fatal error
2458
return NESTED_LOOP_ERROR;
2460
return NESTED_LOOP_NO_MORE_ROWS;
2461
if (join->session->killed) // Aborted by user
2463
join->session->send_kill_message();
2464
return NESTED_LOOP_KILLED;
2466
if (!select_cond || select_cond->val_int())
2469
There is no select condition or the attached pushed down
2470
condition is true => a match is found.
2473
while (join_tab->first_unmatched && found)
2476
The while condition is always false if join_tab is not
2477
the last inner join table of an outer join operation.
2479
JoinTable *first_unmatched= join_tab->first_unmatched;
2481
Mark that a match for current outer table is found.
2482
This activates push down conditional predicates attached
2483
to the all inner tables of the outer join.
2485
first_unmatched->found= 1;
2486
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2488
if (tab->table->reginfo.not_exists_optimize)
2489
return NESTED_LOOP_NO_MORE_ROWS;
2490
/* Check all predicates that has just been activated. */
2492
Actually all predicates non-guarded by first_unmatched->found
2493
will be re-evaluated again. It could be fixed, but, probably,
2494
it's not worth doing now.
2496
if (tab->select_cond && !tab->select_cond->val_int())
2498
/* The condition attached to table tab is false */
2499
if (tab == join_tab)
2504
Set a return point if rejected predicate is attached
2505
not to the last table of the current nest level.
2507
join->return_tab= tab;
2508
return NESTED_LOOP_OK;
2513
Check whether join_tab is not the last inner table
2514
for another embedding outer join.
2516
if ((first_unmatched= first_unmatched->first_upper) &&
2517
first_unmatched->last_inner != join_tab)
2519
join_tab->first_unmatched= first_unmatched;
2522
JoinTable *return_tab= join->return_tab;
2523
join_tab->found_match= true;
2526
It was not just a return to lower loop level when one
2527
of the newly activated predicates is evaluated as false
2528
(See above join->return_tab= tab).
2530
join->examined_rows++;
2531
join->session->row_count++;
2535
enum enum_nested_loop_state rc;
2536
/* A match from join_tab is found for the current partial join. */
2537
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2538
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2540
if (return_tab < join->return_tab)
2541
join->return_tab= return_tab;
2543
if (join->return_tab < join_tab)
2544
return NESTED_LOOP_OK;
2546
Test if this was a SELECT DISTINCT query on a table that
2547
was not in the field list; In this case we can abort if
2548
we found a row, as no new rows can be added to the result.
2550
if (not_used_in_distinct && found_records != join->found_records)
2551
return NESTED_LOOP_NO_MORE_ROWS;
2554
join_tab->read_record.cursor->unlock_row();
2559
The condition pushed down to the table join_tab rejects all rows
2560
with the beginning coinciding with the current partial join.
2562
join->examined_rows++;
2563
join->session->row_count++;
2564
join_tab->read_record.cursor->unlock_row();
2566
return NESTED_LOOP_OK;
2571
Construct a NULL complimented partial join record and feed it to the next
2572
level of the nested loop. This function is used in case we have
2573
an OUTER join and no matching record was found.
2575
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab)
2578
The table join_tab is the first inner table of a outer join operation
2579
and no matches has been found for the current outer row.
2581
JoinTable *last_inner_tab= join_tab->last_inner;
2582
/* Cache variables for faster loop */
2584
for ( ; join_tab <= last_inner_tab ; join_tab++)
2586
/* Change the the values of guard predicate variables. */
2588
join_tab->not_null_compl= 0;
2589
/* The outer row is complemented by nulls for each inner tables */
2590
join_tab->table->restoreRecordAsDefault(); // Make empty record
2591
join_tab->table->mark_as_null_row(); // For group by without error
2592
select_cond= join_tab->select_cond;
2593
/* Check all attached conditions for inner table rows. */
2594
if (select_cond && !select_cond->val_int())
2595
return NESTED_LOOP_OK;
2599
The row complemented by nulls might be the first row
2600
of embedding outer joins.
2601
If so, perform the same actions as in the code
2602
for the first regular outer join row above.
2606
JoinTable *first_unmatched= join_tab->first_unmatched;
2607
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2609
join_tab->first_unmatched= first_unmatched;
2610
if (! first_unmatched)
2612
first_unmatched->found= 1;
2613
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2615
if (tab->select_cond && !tab->select_cond->val_int())
2617
join->return_tab= tab;
2618
return NESTED_LOOP_OK;
2623
The row complemented by nulls satisfies all conditions
2624
attached to inner tables.
2625
Send the row complemented by nulls to be joined with the
2628
return (*join_tab->next_select)(join, join_tab+1, 0);
2631
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last)
2633
enum_nested_loop_state rc= NESTED_LOOP_OK;
2637
join_tab->table->null_row= 0;
2638
if (!join_tab->cache.records)
2639
return NESTED_LOOP_OK; /* Nothing to do */
2641
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
2642
if (join_tab->use_quick == 2)
2644
if (join_tab->select->quick)
2645
{ /* Used quick select last. reset it */
2646
delete join_tab->select->quick;
2647
join_tab->select->quick=0;
2650
/* read through all records */
2651
if ((error=join_init_read_record(join_tab)))
2653
reset_cache_write(&join_tab->cache);
2654
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2657
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2659
tmp->status=tmp->table->status;
2660
tmp->table->status=0;
2663
info= &join_tab->read_record;
2666
if (join->session->killed)
2668
join->session->send_kill_message();
2669
return NESTED_LOOP_KILLED;
2671
optimizer::SqlSelect *select= join_tab->select;
2672
if (rc == NESTED_LOOP_OK &&
2673
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2676
reset_cache_read(&join_tab->cache);
2677
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2679
join_tab->readCachedRecord();
2680
if (!select || !select->skip_record())
2684
rc= (join_tab->next_select)(join,join_tab+1,0);
2685
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2687
reset_cache_write(&join_tab->cache);
2692
return NESTED_LOOP_ERROR;
2696
} while (!(error=info->read_record(info)));
2699
join_tab->readCachedRecord(); // Restore current record
2700
reset_cache_write(&join_tab->cache);
2701
if (error > 0) // Fatal error
2702
return NESTED_LOOP_ERROR;
2703
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2704
tmp2->table->status=tmp2->status;
2705
return NESTED_LOOP_OK;
2708
/*****************************************************************************
2710
Functions that end one nested loop iteration. Different functions
2711
are used to support GROUP BY clause and to redirect records
2712
to a table (e.g. in case of SELECT into a temporary table) or to the
2716
NESTED_LOOP_OK - the record has been successfully handled
2717
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2719
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2721
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2722
additionally, the nested loop produced the
2723
number of rows specified in the LIMIT clause
2725
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2726
additionally, there is a cursor and the nested
2727
loop algorithm produced the number of rows
2728
that is specified for current cursor fetch
2730
All return values except NESTED_LOOP_OK abort the nested loop.
2731
*****************************************************************************/
2732
enum_nested_loop_state end_send(JOIN *join, JoinTable *, bool end_of_records)
2734
if (! end_of_records)
2737
if (join->having && join->having->val_int() == 0)
2738
return NESTED_LOOP_OK; // Didn't match having
2740
if (join->do_send_rows)
2741
error=join->result->send_data(*join->fields);
2743
return NESTED_LOOP_ERROR;
2744
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2746
if (join->select_options & OPTION_FOUND_ROWS)
2748
JoinTable *jt=join->join_tab;
2749
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2750
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2751
!(jt->select && jt->select->quick) &&
2752
(jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
2755
/* Join over all rows in table; Return number of found rows */
2756
Table *table= jt->table;
2758
join->select_options^= OPTION_FOUND_ROWS;
2759
if (table->sort.record_pointers ||
2760
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2762
/* Using filesort */
2763
join->send_records= table->sort.found_records;
2767
table->cursor->info(HA_STATUS_VARIABLE);
2768
join->send_records= table->cursor->stats.records;
2773
join->do_send_rows= 0;
2774
if (join->unit->fake_select_lex)
2775
join->unit->fake_select_lex->select_limit= 0;
2776
return NESTED_LOOP_OK;
2779
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2781
else if (join->send_records >= join->fetch_limit)
2784
There is a server side cursor and all rows for
2785
this fetch request are sent.
2787
return NESTED_LOOP_CURSOR_LIMIT;
2791
return NESTED_LOOP_OK;
2794
enum_nested_loop_state end_write(JOIN *join, JoinTable *, bool end_of_records)
2796
Table *table= join->tmp_table;
2798
if (join->session->killed) // Aborted by user
2800
join->session->send_kill_message();
2801
return NESTED_LOOP_KILLED;
2803
if (!end_of_records)
2805
copy_fields(&join->tmp_table_param);
2806
copy_funcs(join->tmp_table_param.items_to_copy);
2807
if (!join->having || join->having->val_int())
2810
join->found_records++;
2811
if ((error=table->cursor->ha_write_row(table->record[0])))
2813
if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
2815
if (create_myisam_from_heap(join->session, table,
2816
join->tmp_table_param.start_recinfo,
2817
&join->tmp_table_param.recinfo,
2819
return NESTED_LOOP_ERROR; // Not a table_is_full error
2820
table->s->uniques= 0; // To ensure rows are the same
2822
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2824
if (!(join->select_options & OPTION_FOUND_ROWS))
2825
return NESTED_LOOP_QUERY_LIMIT;
2826
join->do_send_rows= 0;
2827
join->unit->select_limit_cnt= HA_POS_ERROR;
2828
return NESTED_LOOP_OK;
2833
return NESTED_LOOP_OK;
2836
/** Group by searching after group record and updating it if possible. */
2837
enum_nested_loop_state end_update(JOIN *join, JoinTable *, bool end_of_records)
2839
Table *table= join->tmp_table;
2844
return NESTED_LOOP_OK;
2845
if (join->session->killed) // Aborted by user
2847
join->session->send_kill_message();
2848
return NESTED_LOOP_KILLED;
2851
join->found_records++;
2852
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2853
/* Make a key of group index */
2854
for (group=table->group ; group ; group=group->next)
2856
Item *item= *group->item;
2857
item->save_org_in_field(group->field);
2858
/* Store in the used key if the field was 0 */
2859
if (item->maybe_null)
2860
group->buff[-1]= (char) group->field->is_null();
2862
if (!table->cursor->index_read_map(table->record[1],
2863
join->tmp_table_param.group_buff,
2866
{ /* Update old record */
2867
table->restoreRecord();
2868
update_tmptable_sum_func(join->sum_funcs,table);
2869
if ((error= table->cursor->ha_update_row(table->record[1],
2872
table->print_error(error,MYF(0));
2873
return NESTED_LOOP_ERROR;
2875
return NESTED_LOOP_OK;
2879
Copy null bits from group key to table
2880
We can't copy all data as the key may have different format
2881
as the row data (for example as with VARCHAR keys)
2883
KEY_PART_INFO *key_part;
2884
for (group=table->group,key_part=table->key_info[0].key_part;
2886
group=group->next,key_part++)
2888
if (key_part->null_bit)
2889
memcpy(table->record[0]+key_part->offset, group->buff, 1);
2891
init_tmptable_sum_functions(join->sum_funcs);
2892
copy_funcs(join->tmp_table_param.items_to_copy);
2893
if ((error=table->cursor->ha_write_row(table->record[0])))
2895
if (create_myisam_from_heap(join->session, table,
2896
join->tmp_table_param.start_recinfo,
2897
&join->tmp_table_param.recinfo,
2899
return NESTED_LOOP_ERROR; // Not a table_is_full error
2900
/* Change method to update rows */
2901
table->cursor->ha_index_init(0, 0);
2902
join->join_tab[join->tables-1].next_select= end_unique_update;
2904
join->send_records++;
2905
return NESTED_LOOP_OK;
2908
/** Like end_update, but this is done with unique constraints instead of keys. */
2909
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *, bool end_of_records)
2911
Table *table= join->tmp_table;
2915
return NESTED_LOOP_OK;
2916
if (join->session->killed) // Aborted by user
2918
join->session->send_kill_message();
2919
return NESTED_LOOP_KILLED;
2922
init_tmptable_sum_functions(join->sum_funcs);
2923
copy_fields(&join->tmp_table_param); // Groups are copied twice.
2924
copy_funcs(join->tmp_table_param.items_to_copy);
2926
if (!(error= table->cursor->ha_write_row(table->record[0])))
2927
join->send_records++; // New group
2930
if ((int) table->get_dup_key(error) < 0)
2932
table->print_error(error,MYF(0));
2933
return NESTED_LOOP_ERROR;
2935
if (table->cursor->rnd_pos(table->record[1],table->cursor->dup_ref))
2937
table->print_error(error,MYF(0));
2938
return NESTED_LOOP_ERROR;
2940
table->restoreRecord();
2941
update_tmptable_sum_func(join->sum_funcs,table);
2942
if ((error= table->cursor->ha_update_row(table->record[1],
2945
table->print_error(error,MYF(0));
2946
return NESTED_LOOP_ERROR;
2949
return NESTED_LOOP_OK;
2953
allocate group fields or take prepared (cached).
2955
@param main_join join of current select
2956
@param curr_join current join (join of current select or temporary copy
2964
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
2966
if (main_join->group_fields_cache.elements)
2968
curr_join->group_fields= main_join->group_fields_cache;
2969
curr_join->sort_and_group= 1;
2973
if (alloc_group_fields(curr_join, curr_join->group_list))
2975
main_join->group_fields_cache= curr_join->group_fields;
2981
calc how big buffer we need for comparing group entries.
2983
static void calc_group_buffer(JOIN *join,order_st *group)
2985
uint32_t key_length=0, parts=0, null_parts=0;
2989
for (; group ; group=group->next)
2991
Item *group_item= *group->item;
2992
Field *field= group_item->get_tmp_table_field();
2995
enum_field_types type;
2996
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
2997
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
2998
else if (type == DRIZZLE_TYPE_VARCHAR)
2999
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3001
key_length+= field->pack_length();
3005
switch (group_item->result_type()) {
3007
key_length+= sizeof(double);
3010
key_length+= sizeof(int64_t);
3012
case DECIMAL_RESULT:
3013
key_length+= my_decimal_get_binary_size(group_item->max_length -
3014
(group_item->decimals ? 1 : 0),
3015
group_item->decimals);
3019
enum enum_field_types type= group_item->field_type();
3021
As items represented as DATE/TIME fields in the group buffer
3022
have STRING_RESULT result type, we increase the length
3023
by 8 as maximum pack length of such fields.
3025
if (type == DRIZZLE_TYPE_DATE ||
3026
type == DRIZZLE_TYPE_DATETIME ||
3027
type == DRIZZLE_TYPE_TIMESTAMP)
3034
Group strings are taken as varstrings and require an length field.
3035
A field is not yet created by create_tmp_field()
3036
and the sizes should match up.
3038
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3043
/* This case should never be choosen */
3045
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3049
if (group_item->maybe_null)
3052
join->tmp_table_param.group_length=key_length+null_parts;
3053
join->tmp_table_param.group_parts=parts;
3054
join->tmp_table_param.group_null_parts=null_parts;
3058
Get a list of buffers for saveing last group.
3060
Groups are saved in reverse order for easyer check loop.
3062
static bool alloc_group_fields(JOIN *join,order_st *group)
3066
for (; group ; group=group->next)
3068
Cached_item *tmp= new_Cached_item(join->session, *group->item);
3069
if (!tmp || join->group_fields.push_front(tmp))
3073
join->sort_and_group=1; /* Mark for do_select */
3077
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3080
JoinTable **pos,**end;
3081
Session *session=join->session;
3083
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3087
JoinTable *join_tab= *pos;
3088
if (!join_tab->used_fieldlength) /* Not calced yet */
3089
calc_used_field_length(session, join_tab);
3090
length+=join_tab->used_fieldlength;
3096
Get the number of different row combinations for subset of partial join
3100
join The join structure
3101
idx Number of tables in the partial join order (i.e. the
3102
partial join order is in join->positions[0..idx-1])
3103
found_ref Bitmap of tables for which we need to find # of distinct
3107
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3108
tables within that join order (specified in found_ref), find out how many
3109
distinct row combinations of subset tables will be in the result of the
3112
This is used as follows: Suppose we have a table accessed with a ref-based
3113
method. The ref access depends on current rows of tables in found_ref.
3114
We want to count # of different ref accesses. We assume two ref accesses
3115
will be different if at least one of access parameters is different.
3116
Example: consider a query
3118
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3121
t1, ref access on t1.key=c1
3122
t2, ref access on t2.key=c2
3123
t3, ref access on t3.key=t1.field
3125
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3126
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3127
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3128
n_distinct_ref_scans = #records_read(t1)
3130
The reason for having this function (at least the latest version of it)
3131
is that we need to account for buffering in join execution.
3133
An edge-case example: if we have a non-first table in join accessed via
3134
ref(const) or ref(param) where there is a small number of different
3135
values of param, then the access will likely hit the disk cache and will
3136
not require any disk seeks.
3138
The proper solution would be to assume an LRU disk cache of some size,
3139
calculate probability of cache hits, etc. For now we just count
3140
identical ref accesses as one.
3143
Expected number of row combinations
3145
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3148
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3149
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3153
if (pos->examinePosition(found_ref))
3155
found_ref|= pos->getRefDependMap();
3157
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3158
with no matching row we will get position[t2].records_read==0.
3159
Actually the size of output is one null-complemented row, therefore
3160
we will use value of 1 whenever we get records_read==0.
3163
- the above case can't occur if inner part of outer join has more
3164
than one table: table with no matches will not be marked as const.
3166
- Ideally we should add 1 to records_read for every possible null-
3167
complemented row. We're not doing it because: 1. it will require
3168
non-trivial code and add overhead. 2. The value of records_read
3169
is an inprecise estimate and adding 1 (or, in the worst case,
3170
#max_nested_outer_joins=64-1) will not make it any more precise.
3172
if (pos->getFanout() > DBL_EPSILON)
3173
found*= pos->getFanout();
3180
Set up join struct according to best position.
3182
static bool get_best_combination(JOIN *join)
3185
table_map used_tables;
3186
JoinTable *join_tab,*j;
3187
optimizer::KeyUse *keyuse;
3188
uint32_t table_count;
3189
Session *session=join->session;
3190
optimizer::Position cur_pos;
3192
table_count=join->tables;
3193
if (!(join->join_tab=join_tab=
3194
(JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))
3199
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3200
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3203
cur_pos= join->getPosFromOptimalPlan(tablenr);
3204
*j= *cur_pos.getJoinTable();
3205
form=join->table[tablenr]=j->table;
3206
used_tables|= form->map;
3207
form->reginfo.join_tab=j;
3208
if (!*j->on_expr_ref)
3209
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
3210
if (j->type == AM_CONST)
3211
continue; // Handled in make_join_stat..
3216
if (j->type == AM_SYSTEM)
3218
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3221
if (tablenr != join->const_tables)
3224
else if (create_ref_for_key(join, j, keyuse, used_tables))
3225
return(true); // Something went wrong
3228
for (i=0 ; i < table_count ; i++)
3229
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3230
update_depend_map(join);
3234
/** Save const tables first as used tables. */
3235
static void set_position(JOIN *join,
3238
optimizer::KeyUse *key)
3240
optimizer::Position tmp_pos(1.0, /* This is a const table */
3245
join->setPosInPartialPlan(idx, tmp_pos);
3247
/* Move the const table as down as possible in best_ref */
3248
JoinTable **pos=join->best_ref+idx+1;
3249
JoinTable *next=join->best_ref[idx];
3250
for (;next != table ; pos++)
3252
JoinTable *tmp=pos[0];
3256
join->best_ref[idx]=table;
3260
Selects and invokes a search strategy for an optimal query plan.
3262
The function checks user-configurable parameters that control the search
3263
strategy for an optimal plan, selects the search method and then invokes
3264
it. Each specific optimization procedure stores the final optimal plan in
3265
the array 'join->best_positions', and the cost of the plan in
3268
@param join pointer to the structure providing all context info for
3270
@param join_tables set of the tables in the query
3277
static bool choose_plan(JOIN *join, table_map join_tables)
3279
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3280
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3281
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3283
join->cur_embedding_map.reset();
3284
reset_nj_counters(join->join_list);
3286
if (SELECT_STRAIGHT_JOIN option is set)
3287
reorder tables so dependent tables come after tables they depend
3288
on, otherwise keep tables in the order they were specified in the query
3290
Apply heuristic: pre-sort all access plans with respect to the number of
3293
my_qsort(join->best_ref + join->const_tables,
3294
join->tables - join->const_tables, sizeof(JoinTable*),
3295
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3298
optimize_straight_join(join, join_tables);
3302
if (search_depth == 0)
3303
/* Automatically determine a reasonable value for 'search_depth' */
3304
search_depth= determine_search_depth(join);
3305
if (greedy_search(join, join_tables, search_depth, prune_level))
3310
Store the cost of this query into a user variable
3311
Don't update last_query_cost for statements that are not "flat joins" :
3312
i.e. they have subqueries, unions or call stored procedures.
3313
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3315
if (join->session->lex->is_single_level_stmt())
3316
join->session->status_var.last_query_cost= join->best_read;
3321
Find the best access path for an extension of a partial execution
3322
plan and add this path to the plan.
3324
The function finds the best access path to table 's' from the passed
3325
partial plan where an access path is the general term for any means to
3326
access the data in 's'. An access path may use either an index or a scan,
3327
whichever is cheaper. The input partial plan is passed via the array
3328
'join->positions' of length 'idx'. The chosen access method for 's' and its
3329
cost are stored in 'join->positions[idx]'.
3331
@param join pointer to the structure providing all context info
3333
@param s the table to be joined by the function
3334
@param session thread for the connection that submitted the query
3335
@param remaining_tables set of tables not included into the partial plan yet
3336
@param idx the length of the partial plan
3337
@param record_count estimate for the number of records returned by the
3339
@param read_time the cost of the partial plan
3344
static void best_access_path(JOIN *join,
3347
table_map remaining_tables,
3349
double record_count,
3352
optimizer::KeyUse *best_key= NULL;
3353
uint32_t best_max_key_part= 0;
3354
bool found_constraint= 0;
3355
double best= DBL_MAX;
3356
double best_time= DBL_MAX;
3357
double records= DBL_MAX;
3358
table_map best_ref_depends_map= 0;
3363
{ /* Use key if possible */
3364
Table *table= s->table;
3365
optimizer::KeyUse *keyuse= NULL;
3366
optimizer::KeyUse *start_key= NULL;
3367
double best_records= DBL_MAX;
3368
uint32_t max_key_part=0;
3370
/* Test how we can use keys */
3371
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3372
for (keyuse= s->keyuse; keyuse->getTable() == table; )
3374
key_part_map found_part= 0;
3375
table_map found_ref= 0;
3376
uint32_t key= keyuse->getKey();
3377
KEY *keyinfo= table->key_info + key;
3378
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3379
key_part_map const_part= 0;
3380
/* The or-null keypart in ref-or-null access: */
3381
key_part_map ref_or_null_part= 0;
3383
/* Calculate how many key segments of the current key we can use */
3386
do /* For each keypart */
3388
uint32_t keypart= keyuse->getKeypart();
3389
table_map best_part_found_ref= 0;
3390
double best_prev_record_reads= DBL_MAX;
3392
do /* For each way to access the keypart */
3396
if 1. expression doesn't refer to forward tables
3397
2. we won't get two ref-or-null's
3399
if (! (remaining_tables & keyuse->getUsedTables()) &&
3400
! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3401
KEY_OPTIMIZE_REF_OR_NULL)))
3403
found_part|= keyuse->getKeypartMap();
3404
if (! (keyuse->getUsedTables() & ~join->const_table_map))
3405
const_part|= keyuse->getKeypartMap();
3407
double tmp2= prev_record_reads(join, idx, (found_ref |
3408
keyuse->getUsedTables()));
3409
if (tmp2 < best_prev_record_reads)
3411
best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
3412
best_prev_record_reads= tmp2;
3414
if (rec > keyuse->getTableRows())
3415
rec= keyuse->getTableRows();
3417
If there is one 'key_column IS NULL' expression, we can
3418
use this ref_or_null optimisation of this field
3420
if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3421
ref_or_null_part|= keyuse->getKeypartMap();
3425
} while (keyuse->getTable() == table && keyuse->getKey() == key &&
3426
keyuse->getKeypart() == keypart);
3427
found_ref|= best_part_found_ref;
3428
} while (keyuse->getTable() == table && keyuse->getKey() == key);
3431
Assume that that each key matches a proportional part of table.
3434
continue; // Nothing usable found
3436
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3437
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3440
found_constraint= 1;
3443
Check if we found full key
3445
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3448
max_key_part= UINT32_MAX;
3449
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3451
tmp = prev_record_reads(join, idx, found_ref);
3457
{ /* We found a const key */
3459
ReuseRangeEstimateForRef-1:
3460
We get here if we've found a ref(const) (c_i are constants):
3461
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3463
If range optimizer was able to construct a "range"
3464
access on this index, then its condition "quick_cond" was
3465
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3466
from the range optimizer.
3468
Proof of (*): By properties of range and ref optimizers
3469
quick_cond will be equal or tighther than ref_const_cond.
3470
ref_const_cond already covers "smallest" possible interval -
3471
a singlepoint interval over all keyparts. Therefore,
3472
quick_cond is equivalent to ref_const_cond (if it was an
3473
empty interval we wouldn't have got here).
3475
if (table->quick_keys.test(key))
3476
records= (double) table->quick_rows[key];
3479
/* quick_range couldn't use key! */
3480
records= (double) s->records/rec;
3485
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3486
{ /* Prefer longer keys */
3488
((double) s->records / (double) rec *
3490
((double) (table->s->max_key_length-keyinfo->key_length) /
3491
(double) table->s->max_key_length)));
3493
records=2.0; /* Can't be as good as a unique */
3496
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3497
E(#rows) from range optimizer. Make another try:
3499
If range optimizer produced E(#rows) for a prefix of the ref
3500
access we're considering, and that E(#rows) is lower then our
3501
current estimate, make an adjustment. The criteria of when we
3502
can make an adjustment is a special case of the criteria used
3503
in ReuseRangeEstimateForRef-3.
3505
if (table->quick_keys.test(key) &&
3506
const_part & (1 << table->quick_key_parts[key]) &&
3507
table->quick_n_ranges[key] == 1 &&
3508
records > (double) table->quick_rows[key])
3510
records= (double) table->quick_rows[key];
3513
/* Limit the number of matched rows */
3515
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3516
if (table->covering_keys.test(key))
3518
/* we can use only index tree */
3519
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3522
tmp= record_count * min(tmp,s->worst_seeks);
3528
Use as much key-parts as possible and a uniq key is better
3529
than a not unique key
3530
Set tmp to (previous record count) * (records / combination)
3532
if ((found_part & 1) &&
3533
(!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
3534
found_part == PREV_BITS(uint, keyinfo->key_parts)))
3536
max_key_part= max_part_bit(found_part);
3538
ReuseRangeEstimateForRef-3:
3539
We're now considering a ref[or_null] access via
3540
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3541
(same-as-above but with one cond replaced
3542
with "t.keypart_i IS NULL")] (**)
3544
Try re-using E(#rows) from "range" optimizer:
3545
We can do so if "range" optimizer used the same intervals as
3546
in (**). The intervals used by range optimizer may be not
3547
available at this point (as "range" access might have choosen to
3548
create quick select over another index), so we can't compare
3549
them to (**). We'll make indirect judgements instead.
3550
The sufficient conditions for re-use are:
3551
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3552
this is not satisfied we have no way to know which ranges
3553
will be actually scanned by 'ref' until we execute the
3555
(C2) max #key parts in 'range' access == K == max_key_part (this
3556
is apparently a necessary requirement)
3558
We also have a property that "range optimizer produces equal or
3559
tighter set of scan intervals than ref(const) optimizer". Each
3560
of the intervals in (**) are "tightest possible" intervals when
3561
one limits itself to using keyparts 1..K (which we do in #2).
3562
From here it follows that range access used either one, or
3563
both of the (I1) and (I2) intervals:
3565
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3566
(same-as-above but with one cond replaced
3567
with "t.keypart_i IS NULL") (I2)
3569
The remaining part is to exclude the situation where range
3570
optimizer used one interval while we're considering
3571
ref-or-null and looking for estimate for two intervals. This
3572
is done by last limitation:
3574
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3576
if (table->quick_keys.test(key) && !found_ref && //(C1)
3577
table->quick_key_parts[key] == max_key_part && //(C2)
3578
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3580
tmp= records= (double) table->quick_rows[key];
3584
/* Check if we have statistic about the distribution */
3585
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3588
Fix for the case where the index statistics is too
3590
(1) We're considering ref(const) and there is quick select
3592
(2) and that quick select uses more keyparts (i.e. it will
3593
scan equal/smaller interval then this ref(const))
3594
(3) and E(#rows) for quick select is higher then our
3597
We'll use E(#rows) from quick select.
3599
Q: Why do we choose to use 'ref'? Won't quick select be
3600
cheaper in some cases ?
3601
TODO: figure this out and adjust the plan choice if needed.
3603
if (!found_ref && table->quick_keys.test(key) && // (1)
3604
table->quick_key_parts[key] > max_key_part && // (2)
3605
records < (double)table->quick_rows[key]) // (3)
3606
records= (double)table->quick_rows[key];
3613
Assume that the first key part matches 1% of the cursor
3614
and that the whole key matches 10 (duplicates) or 1
3616
Assume also that more key matches proportionally more
3618
This gives the formula:
3619
records = (x * (b-a) + a*c-b)/(c-1)
3621
b = records matched by whole key
3622
a = records matched by first key part (1% of all records?)
3623
c = number of key parts in key
3624
x = used key parts (1 <= x <= c)
3627
if (!(rec_per_key=(double)
3628
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3629
rec_per_key=(double) s->records/rec+1;
3633
else if (rec_per_key/(double) s->records >= 0.01)
3637
double a=s->records*0.01;
3638
if (keyinfo->key_parts > 1)
3639
tmp= (max_key_part * (rec_per_key - a) +
3640
a*keyinfo->key_parts - rec_per_key)/
3641
(keyinfo->key_parts-1);
3644
set_if_bigger(tmp,1.0);
3646
records = (uint32_t) tmp;
3649
if (ref_or_null_part)
3651
/* We need to do two key searches to find key */
3657
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3658
E(#rows) from range optimizer. Make another try:
3660
If range optimizer produced E(#rows) for a prefix of the ref
3661
access we're considering, and that E(#rows) is lower then our
3662
current estimate, make the adjustment.
3664
The decision whether we can re-use the estimate from the range
3665
optimizer is the same as in ReuseRangeEstimateForRef-3,
3666
applied to first table->quick_key_parts[key] key parts.
3668
if (table->quick_keys.test(key) &&
3669
table->quick_key_parts[key] <= max_key_part &&
3670
const_part & (1 << table->quick_key_parts[key]) &&
3671
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3672
const_part) ? 1 : 0) &&
3673
records > (double) table->quick_rows[key])
3675
tmp= records= (double) table->quick_rows[key];
3679
/* Limit the number of matched rows */
3680
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3681
if (table->covering_keys.test(key))
3683
/* we can use only index tree */
3684
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3687
tmp= record_count * min(tmp,s->worst_seeks);
3690
tmp= best_time; // Do nothing
3694
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3696
best_time= tmp + records/(double) TIME_FOR_COMPARE;
3698
best_records= records;
3699
best_key= start_key;
3700
best_max_key_part= max_key_part;
3701
best_ref_depends_map= found_ref;
3704
records= best_records;
3708
Don't test table scan if it can't be better.
3709
Prefer key lookup if we would use the same key for scanning.
3711
Don't do a table scan on InnoDB tables, if we can read the used
3712
parts of the row from any of the used index.
3713
This is because table scans uses index and we would not win
3714
anything by using a table scan.
3716
A word for word translation of the below if-statement in sergefp's
3717
understanding: we check if we should use table scan if:
3718
(1) The found 'ref' access produces more records than a table scan
3719
(or index scan, or quick select), or 'ref' is more expensive than
3721
(2) This doesn't hold: the best way to perform table scan is to to perform
3722
'range' access using index IDX, and the best way to perform 'ref'
3723
access is to use the same index IDX, with the same or more key parts.
3724
(note: it is not clear how this rule is/should be extended to
3725
index_merge quick selects)
3726
(3) See above note about InnoDB.
3727
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3728
path, but there is no quick select)
3729
If the condition in the above brackets holds, then the only possible
3730
"table scan" access method is ALL/index (there is no quick select).
3731
Since we have a 'ref' access path, and FORCE INDEX instructs us to
3732
choose it over ALL/index, there is no need to consider a full table
3735
if ((records >= s->found_records || best > s->read_time) && // (1)
3736
! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)
3737
best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3738
! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) && // (3)
3739
! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3740
! (s->table->force_index && best_key && !s->quick)) // (4)
3741
{ // Check full join
3742
ha_rows rnd_records= s->found_records;
3744
If there is a filtering condition on the table (i.e. ref analyzer found
3745
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3746
preceding this table in the join order we're now considering), then
3747
assume that 25% of the rows will be filtered out by this condition.
3749
This heuristic is supposed to force tables used in exprZ to be before
3750
this table in join order.
3752
if (found_constraint)
3753
rnd_records-= rnd_records/4;
3756
If applicable, get a more accurate estimate. Don't use the two
3759
if (s->table->quick_condition_rows != s->found_records)
3760
rnd_records= s->table->quick_condition_rows;
3763
Range optimizer never proposes a RANGE if it isn't better
3764
than FULL: so if RANGE is present, it's always preferred to FULL.
3765
Here we estimate its cost.
3771
- read record range through 'quick'
3772
- skip rows which does not satisfy WHERE constraints
3774
We take into account possible use of join cache for ALL/index
3775
access (see first else-branch below), but we don't take it into
3776
account here for range/index_merge access. Find out why this is so.
3779
(s->quick->read_time +
3780
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3784
/* Estimate cost of reading table. */
3785
tmp= s->table->cursor->scan_time();
3786
if (s->table->map & join->outer_join) // Can't use join cache
3789
For each record we have to:
3790
- read the whole table record
3791
- skip rows which does not satisfy join condition
3795
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
3799
/* We read the table as many times as join buffer becomes full. */
3800
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
3802
(double) session->variables.join_buff_size));
3804
We don't make full cartesian product between rows in the scanned
3805
table and existing records because we skip all rows from the
3806
scanned table, which does not satisfy join condition when
3807
we read the table (see flush_cached_records for details). Here we
3808
take into account cost to read and skip these records.
3810
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
3815
We estimate the cost of evaluating WHERE clause for found records
3816
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
3817
tmp give us total cost of using Table SCAN
3819
if (best == DBL_MAX ||
3820
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
3821
best + record_count/(double) TIME_FOR_COMPARE*records))
3824
If the table has a range (s->quick is set) make_join_select()
3825
will ensure that this will be used
3828
records= rows2double(rnd_records);
3830
/* range/index_merge/ALL/index access method are "independent", so: */
3831
best_ref_depends_map= 0;
3835
/* Update the cost information for the current partial plan */
3836
optimizer::Position tmp_pos(records,
3840
best_ref_depends_map);
3841
join->setPosInPartialPlan(idx, tmp_pos);
3844
idx == join->const_tables &&
3845
s->table == join->sort_by_table &&
3846
join->unit->select_limit_cnt >= records)
3847
join->sort_by_table= (Table*) 1; // Must use temporary table
3853
Select the best ways to access the tables in a query without reordering them.
3855
Find the best access paths for each query table and compute their costs
3856
according to their order in the array 'join->best_ref' (thus without
3857
reordering the join tables). The function calls sequentially
3858
'best_access_path' for each table in the query to select the best table
3859
access method. The final optimal plan is stored in the array
3860
'join->best_positions', and the corresponding cost in 'join->best_read'.
3862
@param join pointer to the structure providing all context info for
3864
@param join_tables set of the tables in the query
3867
This function can be applied to:
3868
- queries with STRAIGHT_JOIN
3869
- internally to compute the cost of an arbitrary QEP
3871
Thus 'optimize_straight_join' can be used at any stage of the query
3872
optimization process to finalize a QEP as it is.
3874
static void optimize_straight_join(JOIN *join, table_map join_tables)
3877
optimizer::Position partial_pos;
3878
uint32_t idx= join->const_tables;
3879
double record_count= 1.0;
3880
double read_time= 0.0;
3882
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
3884
/* Find the best access method from 's' to the current partial plan */
3885
best_access_path(join, s, join->session, join_tables, idx,
3886
record_count, read_time);
3887
/* compute the cost of the new plan extended with 's' */
3888
partial_pos= join->getPosFromPartialPlan(idx);
3889
record_count*= partial_pos.getFanout();
3890
read_time+= partial_pos.getCost();
3891
join_tables&= ~(s->table->map);
3895
read_time+= record_count / (double) TIME_FOR_COMPARE;
3896
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3897
if (join->sort_by_table &&
3898
partial_pos.hasTableForSorting(join->sort_by_table))
3899
read_time+= record_count; // We have to make a temp table
3900
join->copyPartialPlanIntoOptimalPlan(idx);
3901
join->best_read= read_time;
3905
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
3907
The search procedure uses a hybrid greedy/exhaustive search with controlled
3908
exhaustiveness. The search is performed in N = card(remaining_tables)
3909
steps. Each step evaluates how promising is each of the unoptimized tables,
3910
selects the most promising table, and extends the current partial QEP with
3911
that table. Currenly the most 'promising' table is the one with least
3912
expensive extension.\
3914
There are two extreme cases:
3915
-# When (card(remaining_tables) < search_depth), the estimate finds the
3916
best complete continuation of the partial QEP. This continuation can be
3917
used directly as a result of the search.
3918
-# When (search_depth == 1) the 'best_extension_by_limited_search'
3919
consideres the extension of the current QEP with each of the remaining
3922
All other cases are in-between these two extremes. Thus the parameter
3923
'search_depth' controlls the exhaustiveness of the search. The higher the
3924
value, the longer the optimizaton time and possibly the better the
3925
resulting plan. The lower the value, the fewer alternative plans are
3926
estimated, but the more likely to get a bad QEP.
3928
All intermediate and final results of the procedure are stored in 'join':
3929
- join->positions : modified for every partial QEP that is explored
3930
- join->best_positions: modified for the current best complete QEP
3931
- join->best_read : modified for the current best complete QEP
3932
- join->best_ref : might be partially reordered
3934
The final optimal plan is stored in 'join->best_positions', and its
3935
corresponding cost in 'join->best_read'.
3938
The following pseudocode describes the algorithm of 'greedy_search':
3941
procedure greedy_search
3942
input: remaining_tables
3947
(t, a) = best_extension(pplan, remaining_tables);
3948
pplan = concat(pplan, (t, a));
3949
remaining_tables = remaining_tables - t;
3950
} while (remaining_tables != {})
3955
where 'best_extension' is a placeholder for a procedure that selects the
3956
most "promising" of all tables in 'remaining_tables'.
3957
Currently this estimate is performed by calling
3958
'best_extension_by_limited_search' to evaluate all extensions of the
3959
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
3960
mainly depends on that of 'best_extension_by_limited_search'.
3963
If 'best_extension()' == 'best_extension_by_limited_search()', then the
3964
worst-case complexity of this algorithm is <=
3965
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
3966
complexity of greedy_search is O(N!).
3969
In the future, 'greedy_search' might be extended to support other
3970
implementations of 'best_extension', e.g. some simpler quadratic procedure.
3972
@param join pointer to the structure providing all context info
3974
@param remaining_tables set of tables not included into the partial plan yet
3975
@param search_depth controlls the exhaustiveness of the search
3976
@param prune_level the pruning heuristics that should be applied during
3984
static bool greedy_search(JOIN *join,
3985
table_map remaining_tables,
3986
uint32_t search_depth,
3987
uint32_t prune_level)
3989
double record_count= 1.0;
3990
double read_time= 0.0;
3991
uint32_t idx= join->const_tables; // index into 'join->best_ref'
3993
uint32_t size_remain; // cardinality of remaining_tables
3994
optimizer::Position best_pos;
3995
JoinTable *best_table; // the next plan node to be added to the curr QEP
3997
/* number of tables that remain to be optimized */
3998
size_remain= my_count_bits(remaining_tables);
4001
/* Find the extension of the current QEP with the lowest cost */
4002
join->best_read= DBL_MAX;
4003
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
4004
read_time, search_depth, prune_level))
4007
if (size_remain <= search_depth)
4010
'join->best_positions' contains a complete optimal extension of the
4011
current partial QEP.
4016
/* select the first table in the optimal extension as most promising */
4017
best_pos= join->getPosFromOptimalPlan(idx);
4018
best_table= best_pos.getJoinTable();
4020
Each subsequent loop of 'best_extension_by_limited_search' uses
4021
'join->positions' for cost estimates, therefore we have to update its
4024
join->setPosInPartialPlan(idx, best_pos);
4026
/* find the position of 'best_table' in 'join->best_ref' */
4028
JoinTable *pos= join->best_ref[best_idx];
4029
while (pos && best_table != pos)
4030
pos= join->best_ref[++best_idx];
4031
assert((pos != NULL)); // should always find 'best_table'
4032
/* move 'best_table' at the first free position in the array of joins */
4033
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4035
/* compute the cost of the new plan extended with 'best_table' */
4036
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
4037
record_count*= partial_pos.getFanout();
4038
read_time+= partial_pos.getCost();
4040
remaining_tables&= ~(best_table->table->map);
4048
Find a good, possibly optimal, query execution plan (QEP) by a possibly
4051
The procedure searches for the optimal ordering of the query tables in set
4052
'remaining_tables' of size N, and the corresponding optimal access paths to
4053
each table. The choice of a table order and an access path for each table
4054
constitutes a query execution plan (QEP) that fully specifies how to
4057
The maximal size of the found plan is controlled by the parameter
4058
'search_depth'. When search_depth == N, the resulting plan is complete and
4059
can be used directly as a QEP. If search_depth < N, the found plan consists
4060
of only some of the query tables. Such "partial" optimal plans are useful
4061
only as input to query optimization procedures, and cannot be used directly
4064
The algorithm begins with an empty partial plan stored in 'join->positions'
4065
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4066
evaluates the cost of the partial plan extended by all access plans for
4067
each of the relations in 'remaining_tables', expands the current partial
4068
plan with the access plan that results in lowest cost of the expanded
4069
partial plan, and removes the corresponding relation from
4070
'remaining_tables'. The algorithm continues until it either constructs a
4071
complete optimal plan, or constructs an optimal plartial plan with size =
4074
The final optimal plan is stored in 'join->best_positions'. The
4075
corresponding cost of the optimal plan is in 'join->best_read'.
4078
The procedure uses a recursive depth-first search where the depth of the
4079
recursion (and thus the exhaustiveness of the search) is controlled by the
4080
parameter 'search_depth'.
4083
The pseudocode below describes the algorithm of
4084
'best_extension_by_limited_search'. The worst-case complexity of this
4085
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4086
the complexity of greedy_search is O(N!).
4089
procedure best_extension_by_limited_search(
4090
pplan in, // in, partial plan of tables-joined-so-far
4091
pplan_cost, // in, cost of pplan
4092
remaining_tables, // in, set of tables not referenced in pplan
4093
best_plan_so_far, // in/out, best plan found so far
4094
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4095
search_depth) // in, maximum size of the plans being considered
4097
for each table T from remaining_tables
4099
// Calculate the cost of using table T as above
4100
cost = complex-series-of-calculations;
4102
// Add the cost to the cost so far.
4105
if (pplan_cost >= best_plan_so_far_cost)
4106
// pplan_cost already too great, stop search
4109
pplan= expand pplan by best_access_method;
4110
remaining_tables= remaining_tables - table T;
4111
if (remaining_tables is not an empty set
4115
best_extension_by_limited_search(pplan, pplan_cost,
4118
best_plan_so_far_cost,
4123
best_plan_so_far_cost= pplan_cost;
4124
best_plan_so_far= pplan;
4131
When 'best_extension_by_limited_search' is called for the first time,
4132
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4133
The actual implementation provides a way to optionally use pruning
4134
heuristic (controlled by the parameter 'prune_level') to reduce the search
4135
space by skipping some partial plans.
4138
The parameter 'search_depth' provides control over the recursion
4139
depth, and thus the size of the resulting optimal plan.
4141
@param join pointer to the structure providing all context info
4143
@param remaining_tables set of tables not included into the partial plan yet
4144
@param idx length of the partial QEP in 'join->positions';
4145
since a depth-first search is used, also corresponds
4146
to the current depth of the search tree;
4147
also an index in the array 'join->best_ref';
4148
@param record_count estimate for the number of records returned by the
4150
@param read_time the cost of the best partial plan
4151
@param search_depth maximum depth of the recursion and thus size of the
4153
(0 < search_depth <= join->tables+1).
4154
@param prune_level pruning heuristics that should be applied during
4156
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4163
static bool best_extension_by_limited_search(JOIN *join,
4164
table_map remaining_tables,
4166
double record_count,
4168
uint32_t search_depth,
4169
uint32_t prune_level)
4171
Session *session= join->session;
4172
if (session->killed) // Abort
4176
'join' is a partial plan with lower cost than the best plan so far,
4177
so continue expanding it further with the tables in 'remaining_tables'.
4180
double best_record_count= DBL_MAX;
4181
double best_read_time= DBL_MAX;
4182
optimizer::Position partial_pos;
4184
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4186
table_map real_table_bit= s->table->map;
4189
partial_pos= join->getPosFromPartialPlan(idx - 1);
4191
if ((remaining_tables & real_table_bit) &&
4192
! (remaining_tables & s->dependent) &&
4193
(! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
4195
double current_record_count, current_read_time;
4198
psergey-insideout-todo:
4199
when best_access_path() detects it could do an InsideOut scan or
4200
some other scan, have it return an insideout scan and a flag that
4201
requests to "fork" this loop iteration. (Q: how does that behave
4202
when the depth is insufficient??)
4204
/* Find the best access method from 's' to the current partial plan */
4205
best_access_path(join, s, session, remaining_tables, idx,
4206
record_count, read_time);
4207
/* Compute the cost of extending the plan with 's' */
4208
partial_pos= join->getPosFromPartialPlan(idx);
4209
current_record_count= record_count * partial_pos.getFanout();
4210
current_read_time= read_time + partial_pos.getCost();
4212
/* Expand only partial plans with lower cost than the best QEP so far */
4213
if ((current_read_time +
4214
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4216
restore_prev_nj_state(s);
4221
Prune some less promising partial plans. This heuristic may miss
4222
the optimal QEPs, thus it results in a non-exhaustive search.
4224
if (prune_level == 1)
4226
if (best_record_count > current_record_count ||
4227
best_read_time > current_read_time ||
4228
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4230
if (best_record_count >= current_record_count &&
4231
best_read_time >= current_read_time &&
4232
/* TODO: What is the reasoning behind this condition? */
4233
(! (s->key_dependent & remaining_tables) ||
4234
partial_pos.isConstTable()))
4236
best_record_count= current_record_count;
4237
best_read_time= current_read_time;
4242
restore_prev_nj_state(s);
4247
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4248
{ /* Recursively expand the current partial plan */
4249
std::swap(join->best_ref[idx], *pos);
4250
if (best_extension_by_limited_search(join,
4251
remaining_tables & ~real_table_bit,
4253
current_record_count,
4258
std::swap(join->best_ref[idx], *pos);
4262
'join' is either the best partial QEP with 'search_depth' relations,
4263
or the best complete QEP so far, whichever is smaller.
4265
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4266
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4267
if (join->sort_by_table &&
4268
partial_pos.hasTableForSorting(join->sort_by_table))
4269
/* We have to make a temp table */
4270
current_read_time+= current_record_count;
4271
if ((search_depth == 1) || (current_read_time < join->best_read))
4273
join->copyPartialPlanIntoOptimalPlan(idx + 1);
4274
join->best_read= current_read_time - 0.001;
4277
restore_prev_nj_state(s);
4284
Heuristic procedure to automatically guess a reasonable degree of
4285
exhaustiveness for the greedy search procedure.
4287
The procedure estimates the optimization time and selects a search depth
4288
big enough to result in a near-optimal QEP, that doesn't take too long to
4289
find. If the number of tables in the query exceeds some constant, then
4290
search_depth is set to this constant.
4292
@param join pointer to the structure providing all context info for
4296
This is an extremely simplistic implementation that serves as a stub for a
4297
more advanced analysis of the join. Ideally the search depth should be
4298
determined by learning from previous query optimizations, because it will
4299
depend on the CPU power (and other factors).
4302
this value should be determined dynamically, based on statistics:
4303
uint32_t max_tables_for_exhaustive_opt= 7;
4306
this value could be determined by some mapping of the form:
4307
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4310
A positive integer that specifies the search depth (and thus the
4311
exhaustiveness) of the depth-first search algorithm used by
4314
static uint32_t determine_search_depth(JOIN *join)
4316
uint32_t table_count= join->tables - join->const_tables;
4317
uint32_t search_depth;
4318
/* TODO: this value should be determined dynamically, based on statistics: */
4319
uint32_t max_tables_for_exhaustive_opt= 7;
4321
if (table_count <= max_tables_for_exhaustive_opt)
4322
search_depth= table_count+1; // use exhaustive for small number of tables
4325
TODO: this value could be determined by some mapping of the form:
4326
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4328
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4330
return search_depth;
4333
static bool make_simple_join(JOIN *join,Table *tmp_table)
4336
JoinTable *join_tab;
4339
Reuse Table * and JoinTable if already allocated by a previous call
4340
to this function through JOIN::exec (may happen for sub-queries).
4342
if (!join->table_reexec)
4344
if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
4347
join->tmp_join->table_reexec= join->table_reexec;
4349
if (!join->join_tab_reexec)
4351
if (!(join->join_tab_reexec=
4352
(JoinTable*) join->session->alloc(sizeof(JoinTable))))
4355
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4357
tableptr= join->table_reexec;
4358
join_tab= join->join_tab_reexec;
4360
join->join_tab=join_tab;
4361
join->table=tableptr; tableptr[0]=tmp_table;
4363
join->const_tables=0;
4364
join->const_table_map=0;
4365
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4366
join->tmp_table_param.func_count=0;
4367
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4368
join->first_record=join->sort_and_group=0;
4369
join->send_records=(ha_rows) 0;
4371
join->row_limit=join->unit->select_limit_cnt;
4372
join->do_send_rows = (join->row_limit) ? 1 : 0;
4374
join_tab->cache.buff=0; /* No caching */
4375
join_tab->table=tmp_table;
4377
join_tab->select_cond=0;
4379
join_tab->type= AM_ALL; /* Map through all records */
4380
join_tab->keys.set(); /* test everything in quick */
4382
join_tab->on_expr_ref=0;
4383
join_tab->last_inner= 0;
4384
join_tab->first_unmatched= 0;
4385
join_tab->ref.key = -1;
4386
join_tab->not_used_in_distinct=0;
4387
join_tab->read_first_record= join_init_read_record;
4388
join_tab->join=join;
4389
join_tab->ref.key_parts= 0;
4390
memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4391
tmp_table->status=0;
4392
tmp_table->null_row=0;
4397
Fill in outer join related info for the execution plan structure.
4399
For each outer join operation left after simplification of the
4400
original query the function set up the following pointers in the linear
4401
structure join->join_tab representing the selected execution plan.
4402
The first inner table t0 for the operation is set to refer to the last
4403
inner table tk through the field t0->last_inner.
4404
Any inner table ti for the operation are set to refer to the first
4405
inner table ti->first_inner.
4406
The first inner table t0 for the operation is set to refer to the
4407
first inner table of the embedding outer join operation, if there is any,
4408
through the field t0->first_upper.
4409
The on expression for the outer join operation is attached to the
4410
corresponding first inner table through the field t0->on_expr_ref.
4411
Here ti are structures of the JoinTable type.
4413
EXAMPLE. For the query:
4417
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4418
ON (t1.a=t2.a AND t1.b=t3.b)
4422
given the execution plan with the table order t1,t2,t3,t4
4423
is selected, the following references will be set;
4424
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4425
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4426
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4427
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4429
@param join reference to the info fully describing the query
4432
The function assumes that the simplification procedure has been
4433
already applied to the join query (see simplify_joins).
4434
This function can be called only after the execution plan
4437
static void make_outerjoin_info(JOIN *join)
4439
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4441
JoinTable *tab=join->join_tab+i;
4442
Table *table=tab->table;
4443
TableList *tbl= table->pos_in_table_list;
4444
TableList *embedding= tbl->embedding;
4446
if (tbl->outer_join)
4449
Table tab is the only one inner table for outer join.
4450
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4451
is in the query above.)
4453
tab->last_inner= tab->first_inner= tab;
4454
tab->on_expr_ref= &tbl->on_expr;
4455
tab->cond_equal= tbl->cond_equal;
4457
tab->first_upper= embedding->nested_join->first_nested;
4459
for ( ; embedding ; embedding= embedding->embedding)
4461
/* Ignore sj-nests: */
4462
if (!embedding->on_expr)
4464
nested_join_st *nested_join= embedding->nested_join;
4465
if (!nested_join->counter_)
4468
Table tab is the first inner table for nested_join.
4469
Save reference to it in the nested join structure.
4471
nested_join->first_nested= tab;
4472
tab->on_expr_ref= &embedding->on_expr;
4473
tab->cond_equal= tbl->cond_equal;
4474
if (embedding->embedding)
4475
tab->first_upper= embedding->embedding->nested_join->first_nested;
4477
if (!tab->first_inner)
4478
tab->first_inner= nested_join->first_nested;
4479
if (++nested_join->counter_ < nested_join->join_list.elements)
4481
/* Table tab is the last inner table for nested join. */
4482
nested_join->first_nested->last_inner= tab;
4488
static bool make_join_select(JOIN *join,
4489
optimizer::SqlSelect *select,
4492
Session *session= join->session;
4493
optimizer::Position cur_pos;
4496
add_not_null_conds(join);
4497
table_map used_tables;
4498
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4499
{ /* there may be a select without a cond. */
4500
if (join->tables > 1)
4501
cond->update_used_tables(); // Tablenr may have changed
4502
if (join->const_tables == join->tables &&
4503
session->lex->current_select->master_unit() ==
4504
&session->lex->unit) // not upper level SELECT
4505
join->const_table_map|=RAND_TABLE_BIT;
4506
{ // Check const tables
4508
make_cond_for_table(cond,
4509
join->const_table_map,
4511
for (JoinTable *tab= join->join_tab+join->const_tables;
4512
tab < join->join_tab+join->tables ; tab++)
4514
if (*tab->on_expr_ref)
4516
JoinTable *cond_tab= tab->first_inner;
4517
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4518
join->const_table_map,
4522
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4525
tmp->quick_fix_field();
4526
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4527
new Item_cond_and(cond_tab->select_cond,
4529
if (! cond_tab->select_cond)
4531
cond_tab->select_cond->quick_fix_field();
4534
if (const_cond && ! const_cond->val_int())
4536
return 1; // Impossible const condition
4540
used_tables=((select->const_tables=join->const_table_map) |
4541
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4542
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4544
JoinTable *tab=join->join_tab+i;
4546
first_inner is the X in queries like:
4547
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4549
JoinTable *first_inner_tab= tab->first_inner;
4550
table_map current_map= tab->table->map;
4551
bool use_quick_range=0;
4555
Following force including random expression in last table condition.
4556
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4558
if (i == join->tables-1)
4559
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4560
used_tables|=current_map;
4562
if (tab->type == AM_REF && tab->quick &&
4563
(uint32_t) tab->ref.key == tab->quick->index &&
4564
tab->ref.key_length < tab->quick->max_used_key_length)
4566
/* Range uses longer key; Use this instead of ref on key */
4571
tab->ref.key_parts= 0; // Don't use ref key.
4572
cur_pos= join->getPosFromOptimalPlan(i);
4573
cur_pos.setFanout(rows2double(tab->quick->records));
4575
We will use join cache here : prevent sorting of the first
4576
table only and sort at the end.
4578
if (i != join->const_tables && join->tables > join->const_tables + 1)
4584
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4585
if (cond && !tmp && tab->quick)
4587
if (tab->type != AM_ALL)
4590
Don't use the quick method
4591
We come here in the case where we have 'key=constant' and
4592
the test is removed by make_cond_for_table()
4600
Hack to handle the case where we only refer to a table
4601
in the ON part of an OUTER JOIN. In this case we want the code
4602
below to check if we should use 'quick' instead.
4604
tmp= new Item_int((int64_t) 1,1); // Always true
4608
if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4609
tab->type == AM_EQ_REF)
4611
optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)
4612
session->memdup((unsigned char*) select,
4615
return 1; // End of memory
4617
If tab is an inner table of an outer join operation,
4618
add a match guard to the pushed down predicate.
4619
The guard will turn the predicate on only after
4620
the first match for outer tables is encountered.
4625
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4626
a cond, so neutralize the hack above.
4628
if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4630
tab->select_cond=sel->cond=tmp;
4633
tab->select_cond= sel->cond= NULL;
4635
sel->head=tab->table;
4638
/* Use quick key read if it's a constant and it's not used
4640
if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4641
&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4643
sel->quick=tab->quick; // Use value from get_quick_...
4644
sel->quick_keys.reset();
4645
sel->needed_reg.reset();
4653
uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4654
if (i == join->const_tables && ref_key)
4656
if (tab->const_keys.any() &&
4657
tab->table->reginfo.impossible_range)
4660
else if (tab->type == AM_ALL && ! use_quick_range)
4662
if (tab->const_keys.any() &&
4663
tab->table->reginfo.impossible_range)
4664
return 1; // Impossible range
4666
We plan to scan all rows.
4667
Check again if we should use an index.
4668
We could have used an column from a previous table in
4669
the index if we are using limit and this is the first table
4672
cur_pos= join->getPosFromOptimalPlan(i);
4673
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4674
(! tab->const_keys.none() && (i == join->const_tables) &&
4675
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4677
/* Join with outer join condition */
4678
COND *orig_cond= sel->cond;
4679
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4682
We can't call sel->cond->fix_fields,
4683
as it will break tab->on_expr if it's AND condition
4684
(fix_fields currently removes extra AND/OR levels).
4685
Yet attributes of the just built condition are not needed.
4686
Thus we call sel->cond->quick_fix_field for safety.
4688
if (sel->cond && ! sel->cond->fixed)
4689
sel->cond->quick_fix_field();
4691
if (sel->test_quick_select(session, tab->keys,
4692
used_tables & ~ current_map,
4693
(join->select_options &
4696
join->unit->select_limit_cnt), 0,
4700
Before reporting "Impossible WHERE" for the whole query
4701
we have to check isn't it only "impossible ON" instead
4703
sel->cond=orig_cond;
4704
if (! *tab->on_expr_ref ||
4705
sel->test_quick_select(session, tab->keys,
4706
used_tables & ~ current_map,
4707
(join->select_options &
4710
join->unit->select_limit_cnt),0,
4712
return 1; // Impossible WHERE
4715
sel->cond=orig_cond;
4717
/* Fix for EXPLAIN */
4720
cur_pos= join->getPosFromOptimalPlan(i);
4721
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4726
sel->needed_reg= tab->needed_reg;
4727
sel->quick_keys.reset();
4729
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4730
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4732
tab->keys= sel->quick_keys;
4733
tab->keys|= sel->needed_reg;
4734
tab->use_quick= (!sel->needed_reg.none() &&
4735
(select->quick_keys.none() ||
4737
(select->quick->records >= 100L)))) ?
4739
sel->read_tables= used_tables & ~current_map;
4741
if (i != join->const_tables && tab->use_quick != 2)
4742
{ /* Read with cache */
4744
(tmp=make_cond_for_table(cond,
4745
join->const_table_map |
4749
tab->cache.select= (optimizer::SqlSelect*)
4750
session->memdup((unsigned char*) sel, sizeof(optimizer::SqlSelect));
4751
tab->cache.select->cond= tmp;
4752
tab->cache.select->read_tables= join->const_table_map;
4759
Push down conditions from all on expressions.
4760
Each of these conditions are guarded by a variable
4761
that turns if off just before null complemented row for
4762
outer joins is formed. Thus, the condition from an
4763
'on expression' are guaranteed not to be checked for
4764
the null complemented row.
4767
/* First push down constant conditions from on expressions */
4768
for (JoinTable *join_tab= join->join_tab+join->const_tables;
4769
join_tab < join->join_tab+join->tables ; join_tab++)
4771
if (*join_tab->on_expr_ref)
4773
JoinTable *cond_tab= join_tab->first_inner;
4774
tmp= make_cond_for_table(*join_tab->on_expr_ref,
4775
join->const_table_map,
4779
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4782
tmp->quick_fix_field();
4783
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4784
new Item_cond_and(cond_tab->select_cond,tmp);
4785
if (! cond_tab->select_cond)
4787
cond_tab->select_cond->quick_fix_field();
4791
/* Push down non-constant conditions from on expressions */
4792
JoinTable *last_tab= tab;
4793
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
4796
Table tab is the last inner table of an outer join.
4797
An on expression is always attached to it.
4799
COND *on_expr= *first_inner_tab->on_expr_ref;
4801
table_map used_tables2= (join->const_table_map |
4802
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4803
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
4805
current_map= tab->table->map;
4806
used_tables2|= current_map;
4807
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
4811
JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
4813
First add the guards for match variables of
4814
all embedding outer join operations.
4816
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
4821
Now add the guard turning the predicate off for
4822
the null complemented row.
4824
tmp_cond= new Item_func_trig_cond(tmp_cond,
4828
tmp_cond->quick_fix_field();
4829
/* Add the predicate to other pushed down predicates */
4830
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
4831
new Item_cond_and(cond_tab->select_cond,
4833
if (! cond_tab->select_cond)
4835
cond_tab->select_cond->quick_fix_field();
4838
first_inner_tab= first_inner_tab->first_upper;
4846
Plan refinement stage: do various set ups for the executioner
4849
make_join_readinfo()
4850
join Join being processed
4851
options Join's options (checking for SELECT_DESCRIBE,
4852
SELECT_NO_JOIN_CACHE)
4853
no_jbuf_after Don't use join buffering after table with this number.
4856
Plan refinement stage: do various set ups for the executioner
4857
- set up use of join buffering
4858
- push index conditions
4859
- increment counters
4864
true - Out of memory
4866
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
4869
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
4872
for (i=join->const_tables ; i < join->tables ; i++)
4874
JoinTable *tab=join->join_tab+i;
4875
Table *table=tab->table;
4876
bool using_join_cache;
4877
tab->read_record.table= table;
4878
tab->read_record.cursor= table->cursor;
4879
tab->next_select=sub_select; /* normal select */
4881
TODO: don't always instruct first table's ref/range access method to
4882
produce sorted output.
4884
tab->sorted= sorted;
4885
sorted= 0; // only first must be sorted
4886
if (tab->insideout_match_tab)
4888
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
4893
switch (tab->type) {
4894
case AM_SYSTEM: // Only happens with left join
4895
table->status=STATUS_NO_RECORD;
4896
tab->read_first_record= join_read_system;
4897
tab->read_record.read_record= join_no_more_records;
4899
case AM_CONST: // Only happens with left join
4900
table->status=STATUS_NO_RECORD;
4901
tab->read_first_record= join_read_const;
4902
tab->read_record.read_record= join_no_more_records;
4903
if (table->covering_keys.test(tab->ref.key) &&
4907
table->cursor->extra(HA_EXTRA_KEYREAD);
4911
table->status=STATUS_NO_RECORD;
4914
delete tab->select->quick;
4915
tab->select->quick=0;
4919
tab->read_first_record= join_read_key;
4920
tab->read_record.read_record= join_no_more_records;
4921
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4924
table->cursor->extra(HA_EXTRA_KEYREAD);
4927
case AM_REF_OR_NULL:
4929
table->status=STATUS_NO_RECORD;
4932
delete tab->select->quick;
4933
tab->select->quick=0;
4937
if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
4940
table->cursor->extra(HA_EXTRA_KEYREAD);
4942
if (tab->type == AM_REF)
4944
tab->read_first_record= join_read_always_key;
4945
tab->read_record.read_record= tab->insideout_match_tab?
4946
join_read_next_same_diff : join_read_next_same;
4950
tab->read_first_record= join_read_always_key_or_null;
4951
tab->read_record.read_record= join_read_next_same_or_null;
4956
If previous table use cache
4957
If the incoming data set is already sorted don't use cache.
4959
table->status=STATUS_NO_RECORD;
4960
using_join_cache= false;
4961
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
4962
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
4963
!tab->insideout_match_tab)
4965
if ((options & SELECT_DESCRIBE) ||
4966
!join_init_cache(join->session,join->join_tab+join->const_tables,
4967
i-join->const_tables))
4969
using_join_cache= true;
4970
tab[-1].next_select=sub_select_cache; /* Patch previous */
4973
/* These init changes read_record */
4974
if (tab->use_quick == 2)
4976
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
4977
tab->read_first_record= join_init_quick_read_record;
4979
status_var_increment(join->session->status_var.select_range_check_count);
4983
tab->read_first_record= join_init_read_record;
4984
if (i == join->const_tables)
4986
if (tab->select && tab->select->quick)
4989
status_var_increment(join->session->status_var.select_range_count);
4993
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
4995
status_var_increment(join->session->status_var.select_scan_count);
5000
if (tab->select && tab->select->quick)
5003
status_var_increment(join->session->status_var.select_full_range_join_count);
5007
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
5009
status_var_increment(join->session->status_var.select_full_join_count);
5012
if (!table->no_keyread)
5014
if (tab->select && tab->select->quick &&
5015
tab->select->quick->index != MAX_KEY && //not index_merge
5016
table->covering_keys.test(tab->select->quick->index))
5019
table->cursor->extra(HA_EXTRA_KEYREAD);
5021
else if (!table->covering_keys.none() &&
5022
!(tab->select && tab->select->quick))
5023
{ // Only read index tree
5024
if (!tab->insideout_match_tab)
5027
See bug #26447: "Using the clustered index for a table scan
5028
is always faster than using a secondary index".
5030
if (table->s->primary_key != MAX_KEY &&
5031
table->cursor->primary_key_is_clustered())
5032
tab->index= table->s->primary_key;
5034
tab->index= table->find_shortest_key(&table->covering_keys);
5036
tab->read_first_record= join_read_first;
5037
tab->type= AM_NEXT; // Read with index_first / index_next
5049
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
5053
/** Update the dependency map for the tables. */
5054
static void update_depend_map(JOIN *join)
5056
JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
5058
for (; join_tab != end ; join_tab++)
5060
table_reference_st *ref= &join_tab->ref;
5061
table_map depend_map= 0;
5062
Item **item=ref->items;
5064
for (i=0 ; i < ref->key_parts ; i++,item++)
5065
depend_map|=(*item)->used_tables();
5066
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
5067
depend_map&= ~OUTER_REF_TABLE_BIT;
5068
for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5071
ref->depend_map|=(*tab)->ref.depend_map;
5076
/** Update the dependency map for the sort order. */
5077
static void update_depend_map(JOIN *join, order_st *order)
5079
for (; order ; order=order->next)
5081
table_map depend_map;
5082
order->item[0]->update_used_tables();
5083
order->depend_map=depend_map=order->item[0]->used_tables();
5084
// Not item_sum(), RAND() and no reference to table outside of sub select
5085
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5086
&& !order->item[0]->with_sum_func)
5088
for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5091
order->depend_map|=(*tab)->ref.depend_map;
5098
Remove all constants and check if order_st only contains simple
5101
simple_order is set to 1 if sort_order only uses fields from head table
5102
and the head table is not a LEFT JOIN table.
5104
@param join Join handler
5105
@param first_order List of SORT or GROUP order
5106
@param cond WHERE statement
5107
@param change_list Set to 1 if we should remove things from list.
5108
If this is not set, then only simple_order is
5110
@param simple_order Set to 1 if we are only using simple expressions
5113
Returns new sort order
5115
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5117
if (join->tables == join->const_tables)
5118
return change_list ? 0 : first_order; // No need to sort
5120
order_st *order,**prev_ptr;
5121
table_map first_table= join->join_tab[join->const_tables].table->map;
5122
table_map not_const_tables= ~join->const_table_map;
5125
prev_ptr= &first_order;
5126
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5128
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5130
update_depend_map(join, first_order);
5131
for (order=first_order; order ; order=order->next)
5133
table_map order_tables=order->item[0]->used_tables();
5134
if (order->item[0]->with_sum_func)
5135
*simple_order=0; // Must do a temp table to sort
5136
else if (!(order_tables & not_const_tables))
5138
if (order->item[0]->with_subselect)
5139
order->item[0]->val_str(&order->item[0]->str_value);
5140
continue; // skip const item
5144
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5149
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5153
if ((ref=order_tables & (not_const_tables ^ first_table)))
5155
if (!(order_tables & first_table) &&
5156
only_eq_ref_tables(join,first_order, ref))
5160
*simple_order=0; // Must do a temp table to sort
5165
*prev_ptr= order; // use this entry
5166
prev_ptr= &order->next;
5170
if (prev_ptr == &first_order) // Nothing to sort/group
5172
return(first_order);
5175
static int return_zero_rows(JOIN *join,
5176
select_result *result,
5180
uint64_t select_options,
5184
if (select_options & SELECT_DESCRIBE)
5186
optimizer::ExplainPlan planner(join,
5191
planner.printPlan();
5199
for (TableList *table= tables; table; table= table->next_leaf)
5200
table->table->mark_as_null_row(); // All fields are NULL
5201
if (having && having->val_int() == 0)
5204
if (! (result->send_fields(fields)))
5208
List_iterator_fast<Item> it(fields);
5210
while ((item= it++))
5211
item->no_rows_in_result();
5212
result->send_data(fields);
5214
result->send_eof(); // Should be safe
5216
/* Update results for FOUND_ROWS */
5217
join->session->limit_found_rows= join->session->examined_row_count= 0;
5222
Simplify joins replacing outer joins by inner joins whenever it's
5225
The function, during a retrieval of join_list, eliminates those
5226
outer joins that can be converted into inner join, possibly nested.
5227
It also moves the on expressions for the converted outer joins
5228
and from inner joins to conds.
5229
The function also calculates some attributes for nested joins:
5233
- on_expr_dep_tables
5234
The first two attributes are used to test whether an outer join can
5235
be substituted for an inner join. The third attribute represents the
5236
relation 'to be dependent on' for tables. If table t2 is dependent
5237
on table t1, then in any evaluated execution plan table access to
5238
table t2 must precede access to table t2. This relation is used also
5239
to check whether the query contains invalid cross-references.
5240
The forth attribute is an auxiliary one and is used to calculate
5242
As the attribute dep_tables qualifies possibles orders of tables in the
5243
execution plan, the dependencies required by the straight join
5244
modifiers are reflected in this attribute as well.
5245
The function also removes all braces that can be removed from the join
5246
expression without changing its meaning.
5249
An outer join can be replaced by an inner join if the where condition
5250
or the on expression for an embedding nested join contains a conjunctive
5251
predicate rejecting null values for some attribute of the inner tables.
5255
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5257
the predicate t2.b < 5 rejects nulls.
5258
The query is converted first to:
5260
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5262
then to the equivalent form:
5264
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5268
Similarly the following query:
5270
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5275
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5279
One conversion might trigger another:
5281
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5282
LEFT JOIN t3 ON t3.b=t2.b
5283
WHERE t3 IS NOT NULL =>
5284
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5285
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5286
SELECT * FROM t1, t2, t3
5287
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5290
The function removes all unnecessary braces from the expression
5291
produced by the conversions.
5294
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5296
finally is converted to:
5298
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5303
It also will remove braces from the following queries:
5305
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5306
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5309
The benefit of this simplification procedure is that it might return
5310
a query for which the optimizer can evaluate execution plan with more
5311
join orders. With a left join operation the optimizer does not
5312
consider any plan where one of the inner tables is before some of outer
5316
The function is implemented by a recursive procedure. On the recursive
5317
ascent all attributes are calculated, all outer joins that can be
5318
converted are replaced and then all unnecessary braces are removed.
5319
As join list contains join tables in the reverse order sequential
5320
elimination of outer joins does not require extra recursive calls.
5323
Remove all semi-joins that have are within another semi-join (i.e. have
5324
an "ancestor" semi-join nest)
5327
Here is an example of a join query with invalid cross references:
5329
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5332
@param join reference to the query info
5333
@param join_list list representation of the join to be converted
5334
@param conds conditions to add on expressions for converted joins
5335
@param top true <=> conds is the where condition
5338
- The new condition, if success
5341
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5344
nested_join_st *nested_join;
5345
TableList *prev_table= 0;
5346
List_iterator<TableList> li(*join_list);
5349
Try to simplify join operations from join_list.
5350
The most outer join operation is checked for conversion first.
5352
while ((table= li++))
5354
table_map used_tables;
5355
table_map not_null_tables= (table_map) 0;
5357
if ((nested_join= table->nested_join))
5360
If the element of join_list is a nested join apply
5361
the procedure to its nested join list first.
5365
Item *expr= table->on_expr;
5367
If an on expression E is attached to the table,
5368
check all null rejected predicates in this expression.
5369
If such a predicate over an attribute belonging to
5370
an inner table of an embedded outer join is found,
5371
the outer join is converted to an inner join and
5372
the corresponding on expression is added to E.
5374
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5376
if (!table->prep_on_expr || expr != table->on_expr)
5380
table->on_expr= expr;
5381
table->prep_on_expr= expr->copy_andor_structure(join->session);
5384
nested_join->used_tables= (table_map) 0;
5385
nested_join->not_null_tables=(table_map) 0;
5386
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5387
used_tables= nested_join->used_tables;
5388
not_null_tables= nested_join->not_null_tables;
5392
if (!table->prep_on_expr)
5393
table->prep_on_expr= table->on_expr;
5394
used_tables= table->table->map;
5396
not_null_tables= conds->not_null_tables();
5399
if (table->embedding)
5401
table->embedding->nested_join->used_tables|= used_tables;
5402
table->embedding->nested_join->not_null_tables|= not_null_tables;
5405
if (!table->outer_join || (used_tables & not_null_tables))
5408
For some of the inner tables there are conjunctive predicates
5409
that reject nulls => the outer join can be replaced by an inner join.
5411
table->outer_join= 0;
5414
/* Add ON expression to the WHERE or upper-level ON condition. */
5417
conds= and_conds(conds, table->on_expr);
5418
conds->top_level_item();
5419
/* conds is always a new item as both cond and on_expr existed */
5420
assert(!conds->fixed);
5421
conds->fix_fields(join->session, &conds);
5424
conds= table->on_expr;
5425
table->prep_on_expr= table->on_expr= 0;
5433
Only inner tables of non-convertible outer joins
5434
remain with on_expr.
5438
table->dep_tables|= table->on_expr->used_tables();
5439
if (table->embedding)
5441
table->dep_tables&= ~table->embedding->nested_join->used_tables;
5443
Embedding table depends on tables used
5444
in embedded on expressions.
5446
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5449
table->dep_tables&= ~table->table->map;
5454
/* The order of tables is reverse: prev_table follows table */
5455
if (prev_table->straight)
5456
prev_table->dep_tables|= used_tables;
5457
if (prev_table->on_expr)
5459
prev_table->dep_tables|= table->on_expr_dep_tables;
5460
table_map prev_used_tables= prev_table->nested_join ?
5461
prev_table->nested_join->used_tables :
5462
prev_table->table->map;
5464
If on expression contains only references to inner tables
5465
we still make the inner tables dependent on the outer tables.
5466
It would be enough to set dependency only on one outer table
5467
for them. Yet this is really a rare case.
5469
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5470
prev_table->dep_tables|= used_tables;
5477
Flatten nested joins that can be flattened.
5478
no ON expression and not a semi-join => can be flattened.
5481
while ((table= li++))
5483
nested_join= table->nested_join;
5484
if (nested_join && !table->on_expr)
5487
List_iterator<TableList> it(nested_join->join_list);
5490
tbl->embedding= table->embedding;
5491
tbl->join_list= table->join_list;
5493
li.replace(nested_join->join_list);
5499
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5502
uint32_t reclength,offset;
5503
uint32_t field_count;
5504
Session *session= join->session;
5506
entry->reginfo.lock_type=TL_WRITE;
5508
/* Calculate how many saved fields there is in list */
5510
List_iterator<Item> it(fields);
5514
if (item->get_tmp_table_field() && ! item->const_item())
5518
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5519
{ // only const items with no OPTION_FOUND_ROWS
5520
join->unit->select_limit_cnt= 1; // Only send first row
5523
Field **first_field=entry->field+entry->s->fields - field_count;
5524
offset= (field_count ?
5525
entry->field[entry->s->fields - field_count]->
5526
offset(entry->record[0]) : 0);
5527
reclength= entry->s->reclength-offset;
5529
entry->free_io_cache(); // Safety
5530
entry->cursor->info(HA_STATUS_VARIABLE);
5531
if (entry->s->db_type() == heap_engine ||
5532
(!entry->s->blob_fields &&
5533
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
5534
session->variables.sortbuff_size)))
5535
error= remove_dup_with_hash_index(join->session, entry,
5536
field_count, first_field,
5539
error= remove_dup_with_compare(join->session, entry, first_field, offset,
5542
free_blobs(first_field);
5547
Function to setup clauses without sum functions.
5549
static int setup_without_group(Session *session,
5550
Item **ref_pointer_array,
5554
List<Item> &all_fields,
5558
bool *hidden_group_fields)
5561
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
5563
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5564
res= session->setup_conds(tables, conds);
5566
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
5567
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5569
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
5570
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5571
group, hidden_group_fields);
5572
session->lex->allow_sum_func= save_allow_sum_func;
5577
Calculate the best possible join and initialize the join structure.
5584
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5589
uint32_t table_count;
5590
uint32_t const_count;
5592
table_map found_const_table_map;
5593
table_map all_table_map;
5594
table_map found_ref;
5598
Table **table_vector= NULL;
5599
JoinTable *stat= NULL;
5600
JoinTable *stat_end= NULL;
5602
JoinTable **stat_ref= NULL;
5603
optimizer::KeyUse *keyuse= NULL;
5604
optimizer::KeyUse *start_keyuse= NULL;
5605
table_map outer_join= 0;
5606
vector<optimizer::SargableParam> sargables;
5607
JoinTable *stat_vector[MAX_TABLES+1];
5608
optimizer::Position *partial_pos;
5610
table_count= join->tables;
5611
stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5612
stat_ref= (JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);
5613
table_vector= (Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5614
if (! stat || ! stat_ref || ! table_vector)
5617
join->best_ref=stat_vector;
5619
stat_end=stat+table_count;
5620
found_const_table_map= all_table_map=0;
5625
s++, tables= tables->next_leaf, i++)
5627
TableList *embedding= tables->embedding;
5630
s->const_keys.reset();
5631
s->checked_keys.reset();
5632
s->needed_reg.reset();
5633
table_vector[i]=s->table=table=tables->table;
5634
table->pos_in_table_list= tables;
5635
error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5638
table->print_error(error, MYF(0));
5641
table->quick_keys.reset();
5642
table->reginfo.join_tab=s;
5643
table->reginfo.not_exists_optimize=0;
5644
memset(table->const_key_parts, 0,
5645
sizeof(key_part_map)*table->s->keys);
5646
all_table_map|= table->map;
5648
s->info=0; // For describe
5650
s->dependent= tables->dep_tables;
5651
s->key_dependent= 0;
5652
table->quick_condition_rows= table->cursor->stats.records;
5654
s->on_expr_ref= &tables->on_expr;
5655
if (*s->on_expr_ref)
5657
/* s is the only inner table of an outer join */
5658
if (!table->cursor->stats.records && !embedding)
5660
s->dependent= 0; // Ignore LEFT JOIN depend.
5661
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5664
outer_join|= table->map;
5665
s->embedding_map.reset();
5666
for (;embedding; embedding= embedding->embedding)
5667
s->embedding_map|= embedding->nested_join->nj_map;
5670
if (embedding && !(false && ! embedding->embedding))
5672
/* s belongs to a nested join, maybe to several embedded joins */
5673
s->embedding_map.reset();
5676
nested_join_st *nested_join= embedding->nested_join;
5677
s->embedding_map|= nested_join->nj_map;
5678
s->dependent|= embedding->dep_tables;
5679
embedding= embedding->embedding;
5680
outer_join|= nested_join->used_tables;
5685
if ((table->cursor->stats.records <= 1) && !s->dependent &&
5686
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5687
!join->no_const_tables)
5689
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5693
join->outer_join=outer_join;
5695
if (join->outer_join)
5698
Build transitive closure for relation 'to be dependent on'.
5699
This will speed up the plan search for many cases with outer joins,
5700
as well as allow us to catch illegal cross references/
5701
Warshall's algorithm is used to build the transitive closure.
5702
As we use bitmaps to represent the relation the complexity
5703
of the algorithm is O((number of tables)^2).
5705
for (i= 0, s= stat ; i < table_count ; i++, s++)
5707
for (uint32_t j= 0 ; j < table_count ; j++)
5709
table= stat[j].table;
5710
if (s->dependent & table->map)
5711
s->dependent |= table->reginfo.join_tab->dependent;
5714
s->table->maybe_null= 1;
5716
/* Catch illegal cross references for outer joins */
5717
for (i= 0, s= stat ; i < table_count ; i++, s++)
5719
if (s->dependent & s->table->map)
5721
join->tables=0; // Don't use join->table
5722
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5725
s->key_dependent= s->dependent;
5729
if (conds || outer_join)
5730
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5731
conds, join->cond_equal,
5732
~outer_join, join->select_lex, sargables))
5735
/* Read tables with 0 or 1 rows (system tables) */
5736
join->const_table_map= 0;
5738
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5739
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5740
while (p_pos < p_end)
5743
s= p_pos->getJoinTable();
5745
join->const_table_map|=s->table->map;
5746
if ((tmp= join_read_const_table(s, p_pos)))
5749
return 1; // Fatal error
5752
found_const_table_map|= s->table->map;
5756
/* loop until no more const tables are found */
5760
more_const_tables_found:
5765
We only have to loop from stat_vector + const_count as
5766
set_position() will move all const_tables first in stat_vector
5769
for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
5774
If equi-join condition by a key is null rejecting and after a
5775
substitution of a const table the key value happens to be null
5776
then we can state that there are no matches for this equi-join.
5778
if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5781
When performing an outer join operation if there are no matching rows
5782
for the single row of the outer table all the inner tables are to be
5783
null complemented and thus considered as constant tables.
5784
Here we apply this consideration to the case of outer join operations
5785
with a single inner table only because the case with nested tables
5786
would require a more thorough analysis.
5787
TODO. Apply single row substitution to null complemented inner tables
5788
for nested outer join operations.
5790
while (keyuse->getTable() == table)
5792
if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5793
keyuse->getVal()->is_null() && keyuse->isNullRejected())
5796
table->mark_as_null_row();
5797
found_const_table_map|= table->map;
5798
join->const_table_map|= table->map;
5799
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5800
goto more_const_tables_found;
5806
if (s->dependent) // If dependent on some table
5808
// All dep. must be constants
5809
if (s->dependent & ~(found_const_table_map))
5811
if (table->cursor->stats.records <= 1L &&
5812
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5813
!table->pos_in_table_list->embedding)
5817
join->const_table_map|=table->map;
5818
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5819
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5820
if ((tmp= join_read_const_table(s, partial_pos)))
5823
return 1; // Fatal error
5826
found_const_table_map|= table->map;
5830
/* check if table can be read by key or table only uses const refs */
5831
if ((keyuse=s->keyuse))
5834
while (keyuse->getTable() == table)
5836
start_keyuse= keyuse;
5837
key= keyuse->getKey();
5838
s->keys.set(key); // QQ: remove this ?
5845
if (keyuse->getVal()->type() != Item::NULL_ITEM &&
5846
! keyuse->getOptimizeFlags())
5848
if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5849
const_ref.set(keyuse->getKeypart());
5851
refs|= keyuse->getUsedTables();
5852
eq_part.set(keyuse->getKeypart());
5855
} while (keyuse->getTable() == table && keyuse->getKey() == key);
5857
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5858
! table->pos_in_table_list->embedding)
5860
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5862
if (const_ref == eq_part)
5863
{ // Found everything for ref.
5867
join->const_table_map|= table->map;
5868
set_position(join, const_count++, s, start_keyuse);
5869
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5871
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5872
if ((tmp=join_read_const_table(s, partial_pos)))
5875
return 1; // Fatal error
5878
found_const_table_map|= table->map;
5882
found_ref|= refs; // Table is const if all refs are const
5884
else if (const_ref == eq_part)
5885
s->const_keys.set(key);
5890
} while (join->const_table_map & found_ref && ref_changed);
5893
Update info on indexes that can be used for search lookups as
5894
reading const tables may has added new sargable predicates.
5896
if (const_count && ! sargables.empty())
5898
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
5899
while (iter != sargables.end())
5901
Field *field= (*iter).getField();
5902
JoinTable *join_tab= field->table->reginfo.join_tab;
5903
key_map possible_keys= field->key_start;
5904
possible_keys&= field->table->keys_in_use_for_query;
5905
bool is_const= true;
5906
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5907
is_const&= (*iter).isConstItem(j);
5909
join_tab[0].const_keys|= possible_keys;
5914
/* Calc how many (possible) matched records in each table */
5916
for (s=stat ; s < stat_end ; s++)
5918
if (s->type == AM_SYSTEM || s->type == AM_CONST)
5920
/* Only one matching row */
5921
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
5924
/* Approximate found rows and time to read them */
5925
s->found_records=s->records=s->table->cursor->stats.records;
5926
s->read_time=(ha_rows) s->table->cursor->scan_time();
5929
Set a max range of how many seeks we can expect when using keys
5930
This is can't be to high as otherwise we are likely to use
5933
s->worst_seeks= min((double) s->found_records / 10,
5934
(double) s->read_time*3);
5935
if (s->worst_seeks < 2.0) // Fix for small tables
5939
Add to stat->const_keys those indexes for which all group fields or
5940
all select distinct fields participate in one index.
5942
add_group_and_distinct_keys(join, s);
5944
if (s->const_keys.any() &&
5945
!s->table->pos_in_table_list->embedding)
5948
optimizer::SqlSelect *select= NULL;
5949
select= optimizer::make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
5952
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
5953
s->quick=select->quick;
5954
s->needed_reg=select->needed_reg;
5956
if (records == 0 && s->table->reginfo.impossible_range)
5959
Impossible WHERE or ON expression
5960
In case of ON, we mark that the we match one empty NULL row.
5961
In case of WHERE, don't set found_const_table_map to get the
5962
caller to abort with a zero row result.
5964
join->const_table_map|= s->table->map;
5965
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5967
if (*s->on_expr_ref)
5969
/* Generate empty row */
5970
s->info= "Impossible ON condition";
5971
found_const_table_map|= s->table->map;
5973
s->table->mark_as_null_row(); // All fields are NULL
5976
if (records != HA_POS_ERROR)
5978
s->found_records=records;
5979
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
5985
join->join_tab=stat;
5986
join->map2table=stat_ref;
5987
join->table= join->all_tables=table_vector;
5988
join->const_tables=const_count;
5989
join->found_const_table_map=found_const_table_map;
5991
/* Find an optimal join order of the non-constant tables. */
5992
if (join->const_tables != join->tables)
5994
optimize_keyuse(join, keyuse_array);
5995
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->query, join->session->thread_id);
5996
bool res= choose_plan(join, all_table_map & ~join->const_table_map);
5997
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
6003
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
6004
join->best_read= 1.0;
6006
/* Generate an execution plan from the found optimal join order. */
6007
return (join->session->killed || get_best_combination(join));
6011
Assign each nested join structure a bit in the nested join bitset.
6013
Assign each nested join structure (except "confluent" ones - those that
6014
embed only one element) a bit in the nested join bitset.
6016
@param join Join being processed
6017
@param join_list List of tables
6018
@param first_unused Number of first unused bit in the nest joing bitset before the
6022
This function is called after simplify_joins(), when there are no
6023
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
6024
we will not run out of bits in the nested join bitset.
6027
First unused bit in the nest join bitset after the call.
6029
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
6031
List_iterator<TableList> li(*join_list);
6033
while ((table= li++))
6035
nested_join_st *nested_join;
6036
if ((nested_join= table->nested_join))
6039
It is guaranteed by simplify_joins() function that a nested join
6040
that has only one child is either
6041
- a single-table view (the child is the underlying table), or
6042
- a single-table semi-join nest
6044
We don't assign bits to such sj-nests because
6045
1. it is redundant (a "sequence" of one table cannot be interleaved
6047
2. we could run out of bits in the nested join bitset otherwise.
6049
if (nested_join->join_list.elements != 1)
6051
/* Don't assign bits to sj-nests */
6053
nested_join->nj_map.set(first_unused++);
6054
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
6059
return(first_unused);
6064
Return table number if there is only one table in sort order
6065
and group and order is compatible, else return 0.
6067
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
6069
table_map map= (table_map) 0;
6072
a= b; // Only one need to be given
6076
for (; a && b; a=a->next,b=b->next)
6078
if (!(*a->item)->eq(*b->item,1))
6079
return (Table *) NULL;
6080
map|= a->item[0]->used_tables();
6082
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
6083
return (Table *) NULL;
6085
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6086
if (map != tables->table->map)
6087
return (Table *) NULL; // More than one table
6088
return tables->table;
6092
Set nested_join_st::counter=0 in all nested joins in passed list.
6094
Recursively set nested_join_st::counter=0 for all nested joins contained in
6095
the passed join_list.
6097
@param join_list List of nested joins to process. It may also contain base
6098
tables which will be ignored.
6100
static void reset_nj_counters(List<TableList> *join_list)
6102
List_iterator<TableList> li(*join_list);
6104
while ((table= li++))
6106
nested_join_st *nested_join;
6107
if ((nested_join= table->nested_join))
6109
nested_join->counter_= 0;
6110
reset_nj_counters(&nested_join->join_list);
6117
Return 1 if second is a subpart of first argument.
6119
If first parts has different direction, change it to second part
6120
(group is sorted like order)
6122
static bool test_if_subpart(order_st *a,order_st *b)
6124
for (; a && b; a=a->next,b=b->next)
6126
if ((*a->item)->eq(*b->item,1))
6135
Nested joins perspective: Remove the last table from the join order.
6137
Remove the last table from the partial join order and update the nested
6138
joins counters and join->cur_embedding_map. It is ok to call this
6139
function for the first table in join order (for which
6140
check_interleaving_with_nj has not been called)
6142
@param last join table to remove, it is assumed to be the last in current
6145
static void restore_prev_nj_state(JoinTable *last)
6147
TableList *last_emb= last->table->pos_in_table_list->embedding;
6148
JOIN *join= last->join;
6151
if (last_emb->on_expr)
6153
if (!(--last_emb->nested_join->counter_))
6154
join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
6155
else if (last_emb->nested_join->join_list.elements-1 ==
6156
last_emb->nested_join->counter_)
6157
join->cur_embedding_map|= last_emb->nested_join->nj_map;
6161
last_emb= last_emb->embedding;
6166
Determine if the set is already ordered for order_st BY, so it can
6167
disable join cache because it will change the ordering of the results.
6168
Code handles sort table that is at any location (not only first after
6169
the const tables) despite the fact that it's currently prohibited.
6170
We must disable join cache if the first non-const table alone is
6171
ordered. If there is a temp table the ordering is done as a last
6172
operation and doesn't prevent join cache usage.
6174
static uint32_t make_join_orderinfo(JOIN *join)
6178
return join->tables;
6180
for (i=join->const_tables ; i < join->tables ; i++)
6182
JoinTable *tab= join->join_tab+i;
6183
Table *table= tab->table;
6184
if ((table == join->sort_by_table &&
6185
(!join->order || join->skip_sort_order)) ||
6186
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
6195
Create a condition for a const reference and add this to the
6196
currenct select for the table.
6198
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6200
if (!join_tab->ref.key_parts)
6203
Item_cond_and *cond=new Item_cond_and();
6204
Table *table=join_tab->table;
6209
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6211
Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
6213
Item *value=join_tab->ref.items[i];
6214
cond->add(new Item_func_equal(new Item_field(field), value));
6216
if (session->is_fatal_error)
6220
cond->fix_fields(session, (Item**)&cond);
6221
if (join_tab->select)
6223
error=(int) cond->add(join_tab->select->cond);
6224
join_tab->select_cond=join_tab->select->cond=cond;
6226
else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
6228
join_tab->select_cond=cond;
6230
return(error ? true : false);
6233
static void free_blobs(Field **ptr)
6235
for (; *ptr ; ptr++)
6237
if ((*ptr)->flags & BLOB_FLAG)
6238
((Field_blob *) (*ptr))->free();
6243
@} (end of group Query_Optimizer)
added
removed
drizzled/join.cc
